ホーナー法

ホーナー法（ほーなーほう、英: 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 

表 話 編 歴 多項式
元数	多変数
次数	多項式 零多項式 定数多項式 斉次多項式 函数 次数不確定 (or −∞)（零函数） 零次（非零定数函数） 一次 二次 三次 四次 五次 方程式 一次 二次 三次 四次 五次 六次 七次 八次
項数	零項 定数項 単項 二項 三項 無限変数（フランス語版） 座標に依らない記述（英語版）
係数条件	容量 1（原始的） 主係数 1（モニック）
アルゴリズム	因数分解 最大公約式（英語版） 除法（英語版） ホーナー法 終結式 判別式 グレブナー基底
関連項目	代数方程式 多項式の根 重根 (多項式) 根と係数の関係 剰余の定理 因数定理 多項式の展開 多項定理 二項定理 整式 解の公式 二次方程式の解の公式 陰計算
カテゴリ

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集