べっこう色の記録

かつては日記でしたが、現在は数学のことを多く書いています

ホーナー法

ホーナー法は多項式の値を求めるアルゴリズムである.

例えば三次の整式p(x)=ax^{3}+bx^{2}+cx+dについて,x=\alphaの値を求めるとする.
通常であれば\alpha^{3},\alpha^{2}や係数に掛け算の計算が要る.
この場合であれば3+2+1=6回の掛け算をせねばならない.

計算はできればやらないほうがいい.ミスが減らせるからだ.

ホーナー法の場合は次の変形がミソである.
  p(x)=x(x(ax+b)+c)+d
ここにx=\alphaを代入すると3乗や2乗の計算の必要がなくなる.
掛け算の回数は3回で済む.素晴らしい簡約である.