ホーナー法

ホーナー法（ほーなーほう、英: Horner's rule）とは、最も少ない加算と乗算の演算回数でn次の多項式の評価を行うことができるアルゴリズムを言う。

名称は、19世紀初頭にこの定式化を行った英国の数学者で教師であったウィリアム・ジョージ・ホーナーに由来する^[1]。なお、ホーナー法の語は、これをニュートン法と併せて利用し、代数方程式の数値解を求める手法を指して使われることもある。

概要

係数 ${\displaystyle a_{n},a_{n-1},\cdots ,a_{1},a_{0}}$ からなる一変数 x の n 次多項式

${\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$

の${\displaystyle x=x_{0}}$ における値 ${\displaystyle p(x_{0})}$ を求めることを考える。

直接的には、まず第一項 ${\displaystyle a_{n}x^{n}}$ を計算し、次に第二項 ${\displaystyle a_{n-1}x^{n-1}}$ を計算し、・・・と順番に計算して最後に足し合わせるという方法がある。ただし、この素朴な方法では、 n(n+1)/2 回の乗算が必要になってしまう。

一方で、上の多項式 p(x) は

${\displaystyle p(x)=(\cdots (a_{n}x+a_{n-1})x+\cdots +a_{1})x+a_{0}}$

と変形することができる。この変形した状態で計算すると、乗算を n 回で済ませることができ、直接的な方法に比べて少ない演算の回数で多項式評価を行うことができる。この多項式評価の方法をホーナー法（Horner's rule）と言う。

応用

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

筆記の場合、たとえば、

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

を

${\displaystyle x^{2}-3x+2\,}$

で除したとき、商は

${\displaystyle x^{3}-2x^{2}+x+1\,}$

であり、余りは

${\displaystyle -15x+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項を加え、その和${\displaystyle -2\,}$を商の第2項の係数とし（ただし、商の第1項の係数は被除数の第1項の係数である）、これを罫線の左の行の第2項から下に掛け、これを第3列に第3項から書く。そして第3項を加え、その和${\displaystyle +1\,}$を商の第3項の係数にする。商は被除数の第1項を除数の第1項で除し、${\displaystyle x^{3}\,}$を得るから、商の第1項は${\displaystyle x^{3}\,}$であり、したがって商は第4項にとどまることは明らかであろう。

脚注

1. ^ "Structure and Interpretation of Computer Programs 2nd Edition," Harold Abelson, Gerald Jay Sussman and Julie Sussman, 2.2.3, Excercise 2.34, p162 (PDF)

参考文献

• Harold Abelson, Gerald Jay Sussman, Julie Sussman (1996). Structure and Interpretation of Computer Programs (2nd ed.). The MIT Press