ホーナー法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ホーナー法は、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項にとどまることは明らかであろう。