호너의 방법

3. 다항식 나눗셈 (조립제법)

호너의 방법(조립제법)은 다항식 $p(x)$를 $(x\; -\; x\_0)$ 형태의 일차식으로 나눌 때 몫과 나머지를 구하는 방법이다. 한국에서는 조립제법이라는 이름으로 고등학교 수학 교육과정에서 다항식 나눗셈을 가르칠 때 사용된다.^[1]

주어진 다항식은 다음과 같다.

$$p(x)\; =\; \backslash sum\_\{i=0\}^n\; a\_i\; x^i\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; a\_3\; x^3\; +\; \backslash cdots\; +\; a\_n\; x^n,$$

여기서 계수 $a\_0,\; \backslash ldots,\; a\_n$은 상수이다. $x$의 특정 값 $x\_0$에서 다항식의 값을 계산하기 위해 다음과 같은 새로운 상수 수열을 재귀적으로 정의한다.

$$\backslash begin\{align\}$$

b_n & := a_n \\

b_{n-1} & := a_{n-1} + b_n x_0 \\

& ~~~ \vdots \\

b_1 & := a_1 + b_2 x_0 \\

b_0 & := a_0 + b_1 x_0.

\end{align}

그러면 $b\_0$는 $p(x\_0)$의 값이 된다. 이를 통해 다음 식을 얻을 수 있다.

$$$$

p(x) = \left(b_1 + b_2 x + b_3 x^2 + b_4x^3 + \cdots + b_{n-1} x^{n-2} +b_nx^{n-1}\right) \left(x - x_0\right) + b_0



이 식은 $p(x)\; /\; (x-x\_0)$의 결과를 빠르게 제공하며, $b\_0$ (즉, $p(x\_0)$)은 나눗셈의 나머지이다. 만약 $x\_0$가 $p(x)$의 근이면 $b\_0\; =\; 0$ (나머지가 0)이 되고, $p(x)$는 $x-x\_0$로 인수분해될 수 있다.^[1]

연속적인 $b$ 값을 찾기 위해, $b\_n$ ($a\_n$과 같음)을 먼저 결정하고, 다음 공식을 사용하여 $b\_0$에 도달할 때까지 재귀적으로 계산한다.

$$b\_\{n-1\}\; =\; a\_\{n-1\}\; +\; b\_\{n\}x\_0$$

3. 1. 나눗셈 예시

세 번째 행은 첫 번째 행과 두 번째 행의 합으로 구해진다. 두 번째 행의 각 항은 ''x'' 값 (이 예시에서는 3)과 바로 왼쪽에 있는 세 번째 행의 값을 곱하여 얻어진다. 첫 번째 행은 나누어지는 다항식 $f(x)$의 계수이다. 따라서 $f(x)$를 $x-3$으로 나눈 나머지는 5이다.

다항식 나머지 정리에 의해 나머지는 $f(3)$이므로, $f(3)\; =\; 5$임을 알 수 있다.

세 번째 행의 값들은 몫인 2차 다항식($2x^2\; +\; 2$)의 계수들이고, 나머지는 5이다.

'''예시 2'''

$x^3-6x^2+11x-6$을 $x-2$로 나누는 경우:

몫은 $x^2-4x+3$이다.

'''예시 3'''

$f\_1(x)=4x^4-6x^3+3x-5$를 $f\_2(x)=2x-1$로 나누는 경우:

세 번째 행은 첫 번째 행과 두 번째 행의 합을 2로 나눈 값이다. 두 번째 행의 각 항은 1과 왼쪽에 있는 세 번째 행의 값을 곱하여 얻어진다. 따라서,

$$\backslash frac\{f\_1(x)\}\{f\_2(x)\}=2x^3-2x^2-x+1-\backslash frac\{4\}\{2x-1\}.$$

'''예시 4'''

$x\; ^5\; -\; 5\; x^4\; +\; 9\; x^3\; -\; 6\; x^2\; -\; 16\; x\; +\; 13\; \backslash ,$을

$x^2\; -\; 3x\; +\; 2\; \backslash ,$로 나누는 경우: 몫은

$x^3\; -2\; x^2\; +\; x\; +\; 1\; \backslash ,$

이고, 나머지는

$-15\; x\; +\; 11\; \backslash ,$

이다.

4. 효율성

호너의 방법은 주어진 다항식을 효율적으로 계산하는 방법이다. 일반적인 다항식은 다음과 같이 표현된다.

:$p(x)\; =\; \backslash sum\_\{i=0\}^n\; a\_i\; x^i\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; a\_3\; x^3\; +\; \backslash cdots\; +\; a\_n\; x^n,$

여기서 $a\_0,\; \backslash ldots,\; a\_n$은 상수 계수이다. 이 다항식을 $x$의 특정 값 $x\_0$에서 계산하려면, 호너의 방법을 사용하면 효율적이다.

호너의 방법은 다음과 같이 다항식을 변형하여 계산한다.

:$p(x)\; =\; a\_0\; +\; x\; \backslash bigg(a\_1\; +\; x\; \backslash Big(a\_2\; +\; x\; \backslash big(a\_3\; +\; \backslash cdots\; +\; x(a\_\{n-1\}\; +\; x\; \backslash ,\; a\_n)\; \backslash cdots\; \backslash big)\; \backslash Big)\; \backslash bigg)\; \backslash \; .$

이렇게 하면 곱셈 횟수를 줄일 수 있다. 예를 들어, 모노미얼 형태의 $n$차 다항식을 계산하려면 최대 $n$번의 덧셈과 $(n^2+n)/2$번의 곱셈이 필요하다. 하지만 호너의 방법을 사용하면 $n$번의 덧셈과 $n$번의 곱셈만으로 계산할 수 있다.^[3]

이는 알렉산더 오스트로프스키가 1954년에 필요한 덧셈 횟수가 최소임을 증명했고,^[4] 빅터 판이 1966년에 곱셈 횟수가 최소임을 증명했다.^[5]

컴퓨터 연산에서 호너의 방법은 단순 계산보다 더 빠르고, 메모리 사용량도 적다. 특히, 부동 소수점 연산에서 호너의 방법은 단순 계산보다 더 빠르다.

4. 1. 병렬 계산

5. 부동소수점 곱셈과 나눗셈에의 응용

호너의 방법은 마이크로컨트롤러와 같이 하드웨어 곱셈기가 없는 환경에서 이진수 곱셈과 나눗셈을 수행하는 데 유용하다. 곱할 이진수 중 하나를 $a\_i\; =\; 1$이고 $x\; =\; 2$인 간단한 다항식으로 표현하여 계산을 단순화한다. 이진법에서 $x\; =\; 2$이므로, 2의 거듭제곱을 반복적으로 인수분해하여 곱셈을 수행한다.

이진수 곱셈은 산술 시프트 연산, 덧셈 및 뺄셈만으로 빠르게 계산될 수 있다. 이진법에서 2의 거듭제곱을 곱하는 것은 레지스터 시프트 연산으로 간단히 처리된다. 예를 들어, 2를 곱하는 것은 왼쪽 산술 시프트, 2^-1을 곱하는 것은 오른쪽 산술 시프트로 계산된다.^[7]

5. 1. 응용 예시

6. 기타 응용

호너의 방법은 다른 위치적 기수법 간의 변환에도 사용될 수 있다. 이때 'x'는 수 체계의 밑수가 되며, 'a'_'i' 계수는 주어진 숫자의 밑수 'x' 표현의 자릿수가 된다.^[8] 또한 'x'가 행렬인 경우에도 호너의 방법을 사용할 수 있으며, 이 경우 계산 효율성이 더욱 커진다. 그러나 이러한 경우에는 더 빠른 방법이 알려져 있다.^[8]

7. 다항식의 근 찾기

뉴턴 방법과 긴 나눗셈 알고리즘을 결합하여 다항식의 실근을 근사할 수 있다. 주어진 다항식에서 가장 큰 영점부터 차례대로 찾아 나가는 방식이다. 이 방법은 다음 두 단계로 이루어진다.^[9]

1. 뉴턴 방법을 사용하여 주어진 다항식의 가장 큰 영점을 찾는다.

2. 호너의 방법을 사용하여 찾은 영점으로 다항식을 나누어 차수를 낮춘다.

위의 두 단계를 모든 실근을 찾을 때까지 반복한다. 만약 근사값이 충분히 정확하지 않다면, 그 값을 초기 추측값으로 사용하여 뉴턴 방법을 다시 적용할 수 있다.^[9]

7. 1. 근 찾기 예시

8. 다항식의 나눗셈 차분

다음과 같은 다항식이 주어졌을 때,

$$p(x)\; =\; \backslash sum\_\{i=0\}^n\; a\_i\; x^i\; =\; a\_0\; +\; a\_1\; x\; +\; a\_2\; x^2\; +\; a\_3\; x^3\; +\; \backslash cdots\; +\; a\_n\; x^n,$$

호너의 방법을 수정하여 나눗셈 차분 $(p(y)\; -\; p(x))/(y\; -\; x)$를 계산할 수 있다.^[10] 이 때, 다음과 같이 진행한다.

$$\backslash begin\{align\}$$

b_n & = a_n, &\quad d_n &= b_n, \\

b_{n-1} & = a_{n-1} + b_n x, &\quad d_{n-1} &= b_{n-1} + d_n y, \\

& {}\ \ \vdots &\quad & {}\ \ \vdots\\

b_1 & = a_1 + b_2 x, &\quad d_1 &= b_1 + d_2 y,\\

b_0 & = a_0 + b_1 x.

\end{align}

계산이 완료되면 다음을 얻는다.

$$\backslash begin\{align\}$$

p(x) &= b_0, \\

\frac{p(y) - p(x)}{y - x} &= d_1, \\

p(y) &= b_0 + (y - x) d_1.

\end{align}

이 나눗셈 차분 계산은 $p(x)$와 $p(y)$를 개별적으로 평가하는 것보다 반올림 오류가 적으며, 특히 $x\; \backslash approx\; y$일 때 그렇다. 이 방법에서 $y\; =\; x$를 대입하면 $d\_1\; =\; p\text{'}(x)$, 즉 $p(x)$의 도함수를 얻는다.

9. 역사

결과: ''x''=840^[11]||right||200px]]

"연속 근사를 통한 모든 차수의 수치 방정식 풀이의 새로운 방법"이라는 제목의 호너의 논문^[12]은 1819년 7월 1일 런던 왕립 학회 회의에서 발표되었으며, 1823년에 후속 논문이 발표되었다.^[12] 1819년 호너의 논문은 1820년 4월호 ''The Monthly Review: or, Literary Journal''에서 따뜻하고 폭넓게 환영받았지만, 찰스 배비지의 기술 논문은 무시되었다. 1821년 9월 ''The Monthly Review''의 리뷰는 홀드레드가 수치 방정식의 직접적이고 일반적인 실용적 해법을 최초로 발견한 사람이라고 결론지었다. 풀러^[13]는 호너의 1819년 논문이 이후 "호너의 방법"으로 알려진 것과 다르며, 이 방법의 우선순위는 홀드레드(1820)에게 주어져야 한다고 밝혔다.

영국 동시대 사람들과 달리, 호너는 아르보가스트의 연구를 비롯한 유럽 대륙의 문헌에 의존했다. 호너는 존 보네캐슬의 대수학 책을 자세히 읽었지만, 파올로 루피니의 연구는 무시했다.

호너가 이 방법을 접근 가능하고 실용적으로 만드는 데 기여했지만, 호너 이전에도 오랫동안 알려져 있었다. 다음은 호너의 방법이 알려진 순서를 역순으로 나열한 것이다.

• 파올로 루피니 (1809년, 루피니 규칙 참조)^[14][15]
• 아이작 뉴턴 (1669년)^[16][17]
• 14세기 중국 수학자 주세걸^[15]
• 13세기 중국 수학자 친 지우샤오 (''수학 구장''에 등장)
• 12세기 페르시아 수학자 샤라프 알딘 알 투시 (삼차 방정식의 일반적인 경우에 이 방법을 처음 사용)^[18]
• 11세기 (송나라) 중국 수학자 자 셴
• 유 휘 (3세기)가 편집한 한나라 (기원전 202년~서기 220년)의 중국 작품 ''구장산술''^[19]

참조

_[1] 문서 600 years earlier, by the Chinese mathematician [[Qin Jiushao]] and 700 years earlier, by the Persian mathematician [[Sharaf al-Dīn al-Ṭūsī]]
_[2] harvnb Pan
_[3] harvnb Pankiewicz
_[4] harvnb Ostrowski
_[5] harvnb Pan
_[6] harvnb Knuth
_[7] harvnb Kripasagar
_[8] harvnb Higham
_[9] harvnb Kress
_[10] harvnb Fateman
_[11] harvnb Libbrecht
_[12] harvnb Horner
_[13] harvnb Fuller
_[14] harvnb Cajori
_[15] MacTutor
_[16] 문서 Analysis Per Quantitatum Series, Fluctiones ac Differentias : Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Anno MDCCXI, p. 10, 4th paragraph.
_[17] 문서 Newton's collected papers, the edition 1779, in a footnote, vol. I, p. 270-271
_[18] harvnb Berggren
_[19] harvnb Temple
_[20] harvnb Mikami
_[21] harvnb Libbrecht
_[22] 문서 "Structure and Interpretation of Computer Programs 2nd Edition," https://web.mit.edu/[...]
_[23] harvnb Cormen
_[24] 매스월드 Horner's Rule