ホーナーの方法

数学とコンピュータ科学において、ホーナー法（またはホーナーのスキーム）は多項式評価のためのアルゴリズムである。これはウィリアム・ジョージ・ホーナーにちなんで名付けられたが、実際にはもっと古く、ホーナーはジョセフ＝ルイ・ラグランジュに帰属させており、数百年前に中国とペルシャの数学者によって発見されていた。^{[ 1 ]}コンピュータの導入後、このアルゴリズムは多項式を効率的に計算するための基礎となった。

このアルゴリズムはホーナーの規則に基づいており、多項式は入れ子の形式で記述されます。 $${\displaystyle {\begin{aligned}&a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n}\\={}&a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}.\end{aligned}}}$$

これにより、 n次の多項式をわずかで評価することが可能になります。${\displaystyle n}$乗算と${\displaystyle n}$加算。これは最適です。なぜなら、xと係数a ₀、...、a _nの両方が入力として与えられた場合、より少ない算術演算で次数nの多項式を評価することは不可能だからです。 ^{[ 2 ]}

ホーナーの方法とホーナー・ルフィニ法は、 1819年にホーナーによって提唱された、多項式の根を近似する方法のことである。これはニュートン・ラフソン法の変形であり、ホーナーの法則を適用することで手計算の効率を高めたものである。1970年頃にコンピュータが普及するまで広く用いられていた。

多項式が与えられた場合$${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$$どこ${\displaystyle a_{0},\ldots ,a_{n}}$は定数係数であり、問​​題は特定の値における多項式の評価である。${\displaystyle x_{0}}$の${\displaystyle x.}$

このため、新しい定数列が以下のように再帰的に定義される。

それから${\displaystyle b_{0}}$の値は${\displaystyle p(x_{0})}$。

これが機能する理由を確認するために、多項式を次の形式で記述できます。 $${\displaystyle p(x)=a_{0}+x{\bigg (}a_{1}+x{\Big (}a_{2}+x{\big (}a_{3}+\cdots +x(a_{n-1}+x\,a_{n})\cdots {\big )}{\Big )}{\bigg )}\ .}$$

したがって、反復的に置換することで${\displaystyle b_{i}}$表現に、 $${\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})\cdots {\big )}{\Big )}\\&=a_{0}+x_{0}{\Big (}a_{1}+x_{0}{\big (}a_{2}+\cdots +x_{0}b_{n-1}{\big )}{\Big )}\\&~~\vdots \\&=a_{0}+x_{0}b_{1}\\&=b_{0}.\end{aligned}}}$$

同様に、以下のことが示せる。

多項式の除算結果を決定するための便利な手順を提案する $${\displaystyle p(x)/(x-x_{0})}$$ と${\displaystyle b_{0}}$（これは${\displaystyle p(x_{0})}$）分割の残余である。${\displaystyle x_{0}}$は${\displaystyle p(x)}$、 それから${\displaystyle b_{0}=0}$（つまり、残りは${\displaystyle 0}$） そして${\displaystyle x-x_{0}}$の係数${\displaystyle p(x)}$。

長除法アルゴリズムとニュートン法を組み合わせることで、多項式の実根を近似することが可能です。アルゴリズムは次のように動作します。多項式が与えられた場合、${\displaystyle p_{n}(x)}$学位${\displaystyle n}$ゼロ付き${\displaystyle z_{n}<z_{n-1}<\cdots <z_{1},}$最初に推測する${\displaystyle x_{0}}$そのため${\displaystyle z_{1}<x_{0}}$次に、以下の2つの手順を繰り返します。

1. ニュートン法を用いて、最大の零点を見つけよ。${\displaystyle z_{1}}$の${\displaystyle p_{n}(x)}$推測を用いて${\displaystyle x_{0}}$。
2. ホーナーの方法を用いて、${\displaystyle (x-z_{1})}$取得する${\displaystyle p_{n-1}}$ステップ1に戻りますが、多項式を使用します。${\displaystyle p_{n-1}}$そして最初の推測${\displaystyle z_{1}}$。

これらの 2 つの手順は、多項式のすべての実数零点が見つかるまで繰り返されます。近似零点の精度が十分でない場合は、得られた値をニュートン法の初期推定値として使用できますが、簡約多項式ではなく完全な多項式を使用します。^{[ 9 ]}

例

多項式を考える $${\displaystyle p_{6}(x)=(x+8)(x+5)(x+3)(x-2)(x-3)(x-7)}$$ これは以下のように展開できます $${\displaystyle p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.}$$

上記から、この多項式の最大の根は7であることがわかっているので、初期値として8を推測できます。ニュートン法を用いると、7の最初の零点は右図の黒線で示されているように見つかります。次に${\displaystyle p(x)}$で割る${\displaystyle (x-7)}$取得する $${\displaystyle p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720}$$ 右の図に赤で示されている。ニュートン法を用いて、初期推定値7でこの多項式の最大の零点を求める。元の多項式の2番目に大きい零点に対応するこの多項式の最大の零点は3で見つかり、赤丸で囲まれている。5次多項式は、${\displaystyle (x-3)}$取得する $${\displaystyle p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240}$$ これは黄色で示されています。この多項式の零点は、ニュートン法を用いて再び2で求められ、黄色で囲まれています。次にホーナー法を用いて、 $${\displaystyle p_{3}(x)=x^{3}+16x^{2}+79x+120}$$これは緑色で示されており、 −3 に零点があることがわかります。この多項式はさらに簡略化され、  $${\displaystyle p_{2}(x)=x^{2}+13x+40}$$これは青色で示されており、 -5 の零点が得られます。元の多項式の最終的な根は、ニュートン法の初期推定値として最終的な零点を使用するか、または、 ${\displaystyle p_{2}(x)}$そして、線形方程式を解きます。ご覧のとおり、期待される根である−8、−5、−3、2、3、および 7 が見つかりました。

ホーナー法は分割差を計算するように修正できる。${\displaystyle (p(y)-p(x))/(y-x).}$与えられた多項式（前述のとおり） $${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$$ 以下のように進めてください^{[ 10 ]}$${\displaystyle {\begin{aligned}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{aligned}}}$$

完成時には、 $${\displaystyle {\begin{aligned}p(x)&=b_{0},\\{\frac {p(y)-p(x)}{y-x}}&=d_{1},\\p(y)&=b_{0}+(y-x)d_{1}.\end{aligned}}}$$この分割差の計算は、評価するよりも丸め誤差 が少ない。${\displaystyle p(x)}$そして${\displaystyle p(y)}$別々に、特に${\displaystyle x\approx y}$。

ホーナーの論文「連続近似による全次数数値方程式の新しい解法」^{[ 12 ]}は、 1819年7月1日のロンドン王立協会の会合で発表され、1823年に続編が発表された。 ^{[ 12 ]} 1819年のロンドン王立協会の哲学的トランザクション第2部に掲載されたホーナーの論文は、1820年4月のマンスリー・レビュー：または文学ジャーナルの書評で、ある評論家から温かく広く歓迎された。これに対し、チャールズ・バベッジの技術論文はこの書評で簡潔に却下されている。1821年9月のマンスリー・レビューの書評の一連の論評は、数値方程式の直接的かつ一般的な実用的解法を発見した最初の人物はホルドレッドであると結論付けている。フラー^{[ 13 ]}は、ホーナーの1819年の論文の方法は、後に「ホーナーの方法」として知られるようになった方法とは異なり、したがってこの方法の優先権はホルドレッド(1820)に与えられるべきであることを示した。

ホーナーは、同時代のイギリス人とは異なり、大陸ヨーロッパの文学、特にアーボガストの著作から影響を受けた。また、ジョン・ボニーキャッスルの代数学に関する著書を綿密に読んだことでも知られているが、パオロ・ルフィーニの著作は無視した。

ホーナーはこの方法を普及させ、実用化した功績があるとされているが、実際にはホーナー以前から知られていた方法である。時系列を逆にすると、ホーナーの方法はすでに以下の目的で知られていた。

• 1809 年のパオロ・ルッフィーニ(ルッフィーニの法則を参照) ^{[ 14 ] [ 15 ]}
• アイザック・ニュートンは1669年に^{[ 16 ] [ 17 ]}
• 14世紀の中国の数学者、朱世傑^{[ 15 ]}
• 13世紀の中国の数学者、秦九韶は、著書『九章数学論』の中で、
• 12世紀のペルシャの数学者 シャラフ・アルディン・アルトゥーシー（三次方程式の一般の場合にこの方法を初めて使用した人物）^{[ 18 ]}
• 11世紀（宋代）の中国の数学者、賈賢
• 『九章算術』は、劉徽（3世紀頃に活躍）が編纂した漢王朝（紀元前202年の中国の著作である^{。 [ 19 ]} 

秦九韶は、著書『書書九章』 （ 1247年）の中で、11世紀の宋代の数学者、賈賢の先行研究に基づいた、多項式方程式を解くためのホーナー型の手法を紹介しています。例えば、ある手法は特に双五次方程式に適しており、秦九韶は当時の中国の事例研究の慣習に従って、その例を挙げています。三上義雄は『中国と日本の数学の発展』（ライプツィヒ、1913年）の中で次のように書いています。

「… ホーナーの輝かしい製法が、ヨーロッパよりも少なくとも6世紀近くも早く中国で使用されていたという事実を否定できる人がいるだろうか …もちろん、我々はホーナーの発明を中国起源に帰するつもりは全くないが、時間の経過を考えると、ヨーロッパ人が直接的または間接的に中国の製法を知っていた可能性は全くあり得ないとは言えない。」^{[ 20 ]}

ウルリッヒ・リブレヒトは次のように結論づけた。「この手順が中国の発明であることは明らかである …この方法はインドでは知られていなかった。」彼は、フィボナッチはおそらくアラブ人からそれを学んだのだろうが、アラブ人はおそらく中国人からそれを借用したのだろうと述べた。^{[ 21 ]}同様の方法で平方根と立方根を抽出することは、劉慧が『九章算書』のIV.16と22の問題に関連して既に論じており、 7世紀の王孝通は、彼の著書『九谷算経』で説明されている近似法によって読者が3次方程式を解くことができると想定している。

• チェビシェフ形式の多項式を評価するためのクレンショーアルゴリズム
• Bスプライン形式のスプラインを評価するためのデ・ブールのアルゴリズム
• ベジェ形式で多項式を評価するDe Casteljau のアルゴリズム
• エストリンによる、現代のコンピュータアーキテクチャにおける並列処理を促進するための構想
• リルの方法による根の近似図法
• ルフィニの法則と合成除法を用いて、多項式を x − r の形の二項式で割る。

• 「ホーナー方式」、数学百科事典、EMS Press、2001年 [1994年]
• 邱金少。「ホーナーの方法」（PDF）。turing.une.edu.au （中国語）。2014年1月6日にオリジナル（PDF）からアーカイブ。 2026年1月17日取得。
• Weisstein, Eric W. (2018-09-28). "Horner's Method" . mathworld.wolfram.com . 2026-01-17に取得.ルート探索アプリケーションの詳細