ある点での多項式の値の計算は、最も単純な古典的なプログラミング問題の1つです。

さまざまな種類の計算を実行する場合、引数の特定の値に対して多項式の値を決定することがしばしば必要です。多くの場合、関数の近似計算は、近似多項式の計算に帰着します。

平均的な読者のHabrahabrは、あらゆる種類の倒錯の適用に不慣れであるとは言えません。 2人に1人は、ホーナーの規則に従って多項式を計算する必要があると言います。しかし、常に小さな「しかし」がありますが、ホーナースキームは常に最も効率的ですか？

多項式を計算するアルゴリズムを正確に記述するという目標は設定していませんが、場合によっては、優れたホーナールールを持つスキームを適用できる（必要な）ことを示しています。資料に興味のある方のために、記事の最後に文献のリストがあり、問題のより詳細な研究のために見つけることができます。

さらに、ロシアの数学者の名前がほとんど知られていないことがthat辱されることもあります。さらに、数学者の仕事についてお話しできることを嬉しく思います。

ホーナーのスキーム

多項式の値を計算する際に、ホーナーの規則は広く適用されています。この方法は、英国の数学者ウィリアム・ジョージ・ホーナーにちなんで名付けられました。

この規則に従って、n次多項式：

${{P} _ {n}}（x）= {{a} _ {0}} {{x} ^ {n}} + {{a} _ {1}} {{x} ^ {n-1 }} + ... + {{a} _ {n-1}} x + {{a} _ {n}}$

として表される

${{P} _ {n}}（x）=（...（（{{a} _ {0}} x + {{a} _ {1}}）x + {{a} _ {2}}） x + ... + {{a} _ {n-1}}）x + {{a} _ {n}}。$

多項式の値の計算は、括弧で決定された順序で実行されます。何がありますか？多項式を計算するには ${{P} _ {n}}（x）$ Hornerのスキームによれば、n回の乗算とnk回の加算を実行する必要があります（ここで、kは0に等しい多項式の係数の数です）。もし ${{a} _ {0}} = 1$ 乗算はn-1になります。

一般的な形式の多項式を計算するために、Hornerスキームよりも操作の数が経済的なスキームを構築することは不可能であることを示すことができます。

ホーナーのスキームの最大の魅力は、多項式の値を計算するアルゴリズムの単純さです。

例外

特別な種類の多項式を計算する場合、ユニバーサルホーナースキームを適用する場合よりも少ない操作で済みます。たとえば、学位を計算する ${{x} ^ {n}}$ Hornerのスキームによれば、n個の係数の順次乗算を意味し、n-1乗算が必要です。ただし、最初の読者はすべて、たとえば計算のために、 ${{x} ^ {8}}$ 順次計算する必要があります ${{x} ^ {2}} = x \ cdot x$ 、 ${{x} ^ {4}} = {{x} ^ {2}} \ cdot {{x} ^ {2}}$ 、 ${{x} ^ {8}} = {{x} ^ {4}} \ cdot {{x} ^ {4}}$ 、つまり 7ではなく3回の乗算のみを完了します。

結局のところ、ホーナースキームが最も経済的です。

実際、すべては計算の量によって決まります。多項式の1つの値を計算する必要がある場合、ホーナーのスキームより優れたものはありません。しかし、多項式の値が多くのポイントで計算される場合、一度だけ実行される予備計算により、多数の乗算演算を保存することが可能になります。これにより、プログラムを大幅に高速化できます。

場合によっては、2段階のスキームを使用して多項式値を取得することをお勧めします。最初の段階では、多項式の係数に対してのみアクションが実行され、特殊な形式に変換されます。 2番目の段階では、多項式の値が引数の特定の値に対して計算されます。この場合、第2段階で実行される操作の数は、ホーナー方式による計算の場合よりも少なくなることが判明する場合があります。

繰り返しますが、このような計算方法は、多項式の値を計算するのに役立ちます ${{P} _ {n}}（x）$ 多数のx値の場合。ゲインは、多項式の最初のステージが一度だけ実行されるという事実により得られます。例は、事前に近似多項式が用意されている初等関数の計算です。

さらなる考慮事項として、計算する操作の数について ${{P} _ {n}}（x）$ 、計算の第2段階の複雑さを念頭に置いてください。

J. 6次の多項式のTodtスキーム

次の多項式があります。

${{P} _ {6}}（x）= {{x} ^ {6}} + A {{x} ^ {5}} + B {{x} ^ {4}} + C {{x} ^ {3}} + D {{x} ^ {2}} + Ex + F$

計算には、次の補助多項式を使用します。

${{p} _ {1}}（x）= x（x + {{b} _ {1}}）$ 、

${{p} _ {2}}（x）=（{{p} _ {1}} + x + {{b} _ {2}}）（{{p} _ {1}} + {{b} _ {3}}）$ 、

${{p} _ {3}}（x）=（{{p} _ {2}} + {{b} _ {4}}）（{{p} _ {1}} + {{b} _ {5}}）+ {{b} _ {6}}$ 。

オッズ ${{b} _ {j}}$ 条件に基づいて不確実な係数の方法によって決定される ${{p} _ {3}}（x）\ equiv {{P} _ {6}}（x）$ 。最後の条件から、等度の多項式の係数を等しくする方程式系を構成します。

システム自体は、ここでは説明しません。しかし、それは置換の方法によって簡単に解かれ、二次方程式を解かなければなりません。係数は複雑な場合がありますが、係数が有効な場合、計算にはホーナー方式による5つの乗算と6つの加算の代わりに3つの乗算と7つの加算が必要です。

この方式の普遍性について話す必要はありませんが、読者はホーナー方式と比較して操作の数の減少を視覚的に評価できます。

スキームYu.L. ケトコバ

最後に、私は数学者に到達しました。

ゆうケトコフは、n> 5のn次多項式の一般的なアイデアを与え、常に実際の式につながり、[（n + 1）/ 2] + [n / 4]乗算とn + 1加算を実行するためにn次多項式の計算を必要とします。

たとえば、n = 2kの場合、ケトコフスキームは多項式を見つけることになります。

${{N} _ {2}}（x）= x（{{b} _ {0}} + x）、$

${{N} _ {4}}（x）=（{{N} _ {2}} + {{b} _ {1}} + x）（{{N} _ {2}} + {{b } _ {2}}）+ {{b} _ {3}}、$

${{N} _ {6}}（x）= {{N} _ {2}} {{N} _ {4}} + {{b} _ {4}} x + {{b} _ {5} }、$

$\ cdots \ cdots \ cdots$

${{N} _ {2k}}（x）=（{{N} _ {2}} + {{s} _ {k}} {{b} _ {2k-2}}）{{N} _ {2k-2}} + {{r} _ {k}} {{b} _ {2k-2}} x + {{b} _ {2k-1}}、$

どこで ${{r} _ {k}} = 0$ 、 ${{s} _ {k}} = 1$ kが偶数の場合、および ${{r} _ {k}} = 1$ 、 ${{s} _ {k}} = 0$ kが奇数の場合（k> 2）。

すべての未知の係数は等式から発見されます ${{P} _ {n}}（x）= {{N} _ {2k}}$ 。ケトコフの作品では、結果のシステムを解くために、常に実係数を与える方法が与えられています ${{b} _ {j}}$ 。

スキームV.Ya. パン

E.ベラガは、第2段階で[（n + 1）/ 2] +1乗算とn加算よりも小さい値を使用して、n次の任意の多項式を計算するスキームを構築できないことを厳密に証明しました。

V.Ya. パンは、最適な多項式計算を扱いました。特に、彼は、実際の多項式を計算するためのいくつかのスキームを提案しました。これは、E。Belagiの推定に非常に近づきました。実際の多項式のパンスキームをいくつか示します。

1. 4次の多項式を計算するスキーム。

多項式が考慮されます ${{P} _ {4}}（x）= {{a} _ {0}} {{x} ^ {4}} + {{a} _ {1}} {{x} ^ {3}} + {{a} _ {2}} {{x} ^ {2}} + {{a} _ {3}} x + {{a} _ {4}}$ 。

想像してみて ${{P} _ {4}}（x）$ 次の形式で：

$g（x）= x（x + {{\ lambda} _ {1}}）、$

${{P} _ {4}}（x）\ equiv {{a} _ {0}} \ left（\ left（g（x）+ {{\ lambda} _ {2}} \ right）\ left（ g（x）+ x + {{\ lambda} _ {3}} \右）+ {{\ lambda} _ {4}}右）$

どこで

${{\ lambda} _ {1}} = \ frac {{{a} _ {1}}-{{a} _ {0}}} {2 {{a} _ {0}}}、{{\ラムダ} _ {2}} = \ frac {{{a} _ {3}}} {{{a} _ {0}}}-{{\ lambda} _ {1}} \ frac {{{a} _ {2}}} {{{a} _ {0}}} +（{{\ \ lambda} _ {1}} + 1）\ lambda _ {1} ^ {2}、$

${{\ lambda} _ {3}} = \ frac {{{a} _ {2}}} {{{a} _ {0}}}-{{\ lambda} _ {1}}（{{\ lambda} _ {1}} + 1）-{{\ lambda} _ {2}}、{{\ lambda} _ {4}} = \ frac {{{a} _ {4}}} {{{a } _ {0}}}-{{\ lambda} _ {2}} {{\ lambda} _ {3}}。$

2.計算のスキーム ${{P} _ {n}}（x）$ 、 $n \ ge 5$ 。

補助多項式を構築します $g（x）$ 、 $h（x）$ 、 ${{p} _ {s}}（x）$ ：

$g（x）= x（x + {{\ lambda} _ {1}}）、h（x）= g（x）+ x、{{p} _ {0}}（x）= x、$

${{p} _ {s}}（x）= {{p} _ {s-1}}（x）\左（（g（x）+ {{\ lambda} _ {4s-2}}）（ h（x）+ {{\ lambda} _ {4s-1}}）+ {{\ lambda} _ {4s}}右）+ {{\ lambda} _ {4s + 1}}$ 、s = 1,2、...、k。

多項式の値を計算するには、次の式を使用します。

${{P} _ {n}}（x）\ equiv {{a} _ {0}} {{p} _ {k}}（x）$ で $n = 4k + 1$ 、

${{P} _ {n}}（x）\ equiv {{a} _ {0}} x {{p} _ {k}}（x）+ {{\ lambda} _ {n}}$ で $n = 4k + 2$ 、

${{P} _ {n}}（x）\ equiv {{a} _ {0}} \ left（{{p} _ {k}}（x）（g（x）+ {{\ lambda} _ {n-1}}）+ {{\ lambda} _ {n}} \右）$ で $n = 4k + 3$ 、

${{P} _ {n}}（x）\ equiv {{a} _ {0}} x \ left（{{p} _ {k}}（x）（g（x）+ {{\ lambda} _ {n-2}}）+ {{\ lambda} _ {n-1}} \右）+ {{\ lambda} _ {n}}$ で $n = 4k + 4$ 、

第2段階のこのスキームには、 $[n / 2] +2$ 乗算と $n + 1$ 追加。

このスキームの特徴は、係数が ${{\ lambda} _ {j}}$ 常に存在する $n \ ge 5$ 元の多項式の実際の係数。

V.Yaで複雑なものを含む、多項式を計算する他のスキームがあります。

おわりに

上記を要約すると、多項式の1つまたは複数の値の計算は、ホーナースキームを使用して間違いなく実行する必要があることに注意してください。

ただし、計算する必要がある多項式値の数が多く、パフォーマンスが非常に重要な場合は、多項式を計算するための特別な方法の使用を検討することは理にかなっています。

一部の読者は、ホーナー以外のスキームをいじるのは難しく、退屈で、いじる価値がないと言うでしょう。ただし、実際には、大きな次数の膨大な数の多項式値を計算するだけで問題が発生し（たとえば、計算に数か月かかることがあります）、乗算の数を半分にすると、数日を費やす必要がある場合でも、時間を大幅に短縮できます多項式を計算するための特定のスキームを実装します。

文学

ケトコフ・ユー数学マシンで多項式を計算する1つの方法について。 //大学の議事録。放射線物理学、t.1。、No。4、1958
V. Ya。Pan、「係数の予備処理と自動的にパラメータを見つけるためのプログラムを備えたスキームによる多項式の計算」、J。Comput。仲間。そしてマット。フィズ、2：1（1962）、133–140
V. Ya。Pan、「多項式の値を計算する方法について」、UMN、21：1（127）（1966）、103–134
V. Ya。Pan、「実際の係数を使用した5次および7次の多項式の計算について」、J。Comput。仲間。そしてマット。フィズ、5：1（1965）、116–118
Pan V. Ya。実際の係数を持つ多項式の値を計算するためのいくつかのスキーム。サイバネティックスの問題。巻 5. M。：Nauka、1961、17–29。
Belaga E. G.係数の予備処理による1つの変数の多項式の値の計算。サイバネティックスの問題。巻 5. M。：Fizmatgiz、1961、7–15。

多項式値の計算。この問題ではすべてが些細なことですか？

ホーナーのスキーム

例外

結局のところ、ホーナースキームが最も経済的です。

J. 6次の多項式のTodtスキーム

スキームYu.L. ケトコバ

スキームV.Ya. パン

おわりに

文学

More articles:

多項式値の計算。 この問題ではすべてが些細なことですか？

ホーナーのスキーム

例外

結局のところ、ホーナースキームが最も経済的です。

J. 6次の多項式のTodtスキーム

スキームYu.L. ケトコバ

スキームV.Ya. パン

おわりに

文学

More articles:

多項式値の計算。この問題ではすべてが些細なことですか？