ホーナー法

ホーナー法は、 $n$ 次の多項式

$p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n$

の $x=x_0$ における多項式の値 $p(x_0)$ の値を求めるアルゴリズムである。名前は、英国の数学者で教師であったウィリアム・G・ホーナーに由来する。なお、ホーナー法の語は、これをニュートン法と併せて利用し、代数方程式の数値解を求める手法を指して使われることもある。

通常通り各項を計算すると、 $\frac{n(n+1)}{2}$ 回の乗算が必要になるが、ホーナー法では

$p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x)\dots))$

と書きかえることにより、乗算を $n$ 回に済ませることができる。

応用 [編集]

多項式の除法への応用を示す。

筆記の場合、たとえば、

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

を

$x^2 - 3x + 2 \,$

で除したとき、商は

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

であり、余りは

$-15 x + 11 \,$

であるが、運算を示せば、

  1 | 1 - 5 + 9 - 6 | - 16 + 13
+ 3 |   + 3 - 2     |
- 2 |       - 6 + 4 |
    |           + 3 | -  2
    |               | +  3 -  2
    |               |
      1 - 2 + 1 + 1 | - 15 + 11

となる。すなわち、まず、第1列に被除数の係数を独特の符号で、左の行に除数の係数を重ねて、それぞれ書く。ただし第1項は独特の符号で、第2項以下は符号を変えて、それぞれ書く。被除数の第1項の係数を左の行の第2項から下に掛け、これを第2列に第2項の下から書く。そして第2項を加え、その和 $-2 \,$ を商の第2項の係数とし（ただし、商の第1項の係数は被除数の第1項の係数である）、これを罫線の左の行の第2項から下に掛け、これを第3列に第3項から書く。そして第3項を加え、その和 $+1 \,$ を商の第3項の係数にする。商は被除数の第1項を除数の第1項で除し、 $x^3 \,$ を得るから、商の第1項は $x^3 \,$ であり、したがって商は第4項にとどまることは明らかであろう。