ホーナー法

ホーナー法は、与えられた多項式の値を、より少ない計算量で求めるためのアルゴリズムです。特に、多項式の評価において、乗算回数を削減することで計算効率を向上させる効果があります。

ホーナー法の基本

一般に、n次の多項式は以下のように表されます。


p(x) = a_n x^n + a_{n-1} x^(n-1) + ... + a_1 x + a_0


この多項式において、x=x₀ のときの p(x₀) の値を計算することを考えます。

素朴な方法では、各項を個別に計算し、最後にそれらを足し合わせる必要があります。例えば、xⁿ を計算する際に n 回の乗算が必要となり、多項式の次数が高いほど計算量が増加します。この方法では、全部で n(n+1)/2 回の乗算が必要となります。

しかし、ホーナー法では、多項式を以下のように変形します。


p(x) = (...((a_n x + a_{n-1}) x + ... + a_1) x + a_0


この形に変形することで、多項式の計算に必要な乗算回数を n 回に減らすことができます。つまり、多項式の次数と同じ回数の乗算で済むため、計算効率が大幅に向上します。

ホーナー法のアルゴリズム

ホーナー法の具体的な計算手順は次の通りです。

1. 多項式の最高次の係数 a_n を初期値とする。
2. 現在の値に x を掛け、次の次数の係数を足す。
3. 上記の手順を多項式の最低次の係数まで繰り返す。

例えば、多項式 p(x) = 2x³ + 3x² - 4x + 5 において、x=2 の時の値を計算する場合、以下のようになります。

1. 初期値: 2
2. 2 2 + 3 = 7
3. 7 2 - 4 = 10
4. 10 * 2 + 5 = 25

結果として、p(2) = 25 となります。

ホーナー法の応用

ホーナー法は、多項式の計算だけでなく、多項式の除法にも応用できます。

例えば、多項式 x⁵ - 5x⁴ + 9x³ - 6x² - 16x + 13 を x² - 3x + 2 で割る場合、ホーナー法を応用した筆算を用いると、商が x³ - 2x² + x + 1、余りが -15x + 11 と求められます。

この筆算では、除数の係数を符号を反転させて並べ、被除数の係数を順に書き出すことで、計算を進めます。商の係数は、計算の過程で順次得られ、最終的に余りの係数も得られます。

ホーナー法のメリット

• - 計算効率の向上: 多項式評価時の乗算回数を削減し、計算量を減らすことができます。
• - 実装の容易さ: アルゴリズムがシンプルであるため、プログラムでの実装が容易です。
• - 様々な応用: 多項式計算だけでなく、除法など他の分野にも応用できます。

ホーナー法は、数値計算やコンピュータグラフィックスなど、多項式を扱うさまざまな分野で活用されています。効率的な計算手法として、その重要性は高いと言えるでしょう。

もう一度検索