一変数多項式の解を近似で求める求根アルゴリズムについて(9.5割Newton法です)
※数学的記述はおきもちであって正確でない場合があります(指摘お待ちしております)
Newton法(Newton-Raphson法)

目標
一変数実多項式f(x)=0(の係数)が与えられたときに、∣f(x0)∣が十分小さいx0を求める
概要
x0′とx0を方程式f(x)=0の解に対する近似値とし、この方程式が区間(x0′,x0)に唯一の解ξを持つとします。x1を、座標(x0,f(x0))におけるf(x)の接線とx座標の交点とします。このときx1は
0=f′(x0)(x1−x0)+f(x0)⇔x1=x0−f′(x0)f(x0)
なので、一般に1以上の整数nに対して
xn=xn−1−f′(xn−1)f(xn−1)
であることが分かります。グラフを見ると、これを繰り返していけば目標が達成できそうです。
誤差の評価
実際に誤差がどのような振る舞いをするのか気になるので、具体的にみるためにf(x)をxn−1まわりでTaylor展開することを考えます。
f(x)はξを含む開区間(x0′,xn−1)でC∞級なのでこの展開は可能で、2次まで展開すると、
f(x)=f(xn−1)+f′(xn−1)(x−xn−1)+21f′′(x−xn−1)(x−xn−1)2+O((x−xn−1)3)
これにx=ξを代入すると、
f(ξ)=f(xn−1)+f′(xn−1)(ξ−xn−1)+21f′′(xn−1)(ξ−xn−1)2+O((ξ−xn−1)3)
変形して、
−f′(xn−1)f(xn−1)−f(ξ)=ξ−xn−1+21f′(xn−1)f′′(xn−1)(ξ−xn−1)2+O((ξ−xn−1)3)
いま、
xn−ξ=xn−1−ξ−f′(xn−1)f(xn−1)=xn−1−ξ−f′(xn−1)f(xn−1)−f(ξ)
であるから(∵f(ξ)=0)、2つ前の式を代入すれば
xn−ξ=xn−1−ξ+ξ−xn−1+21f′(xn−1)f′′(xn−1)(ξ−xn−1)2+O((ξ−xn−1)3)=21f′(xn−1)f′′(xn−1)(xn−1−ξ)2+O((ξ−xn−1)3)
よって、誤差xn−ξは前の誤差xn−1−ξの2乗に比例して小さくなることが分かります(二次収束)。
つまり、nが1増える毎に正確な桁数がだいたい2倍になるということです←すごい
※注意※
グラフを見ると、x0ではなくx0′から始めた場合は解の近似は得られません。また、f′(xn)=0の場合にもxn+1が求まりません。適用できるのは、
「f′(x)とf′′(x)が区間(x0′,x0)で0とならず、f(x0′)とf(x0)の符号が異なり、f(x)とf′′(x)が同符号である端点から始める場合」です。このとき(x0′,x0)に含まれる唯一の解ξの近似が求まります。(力不足により証明略)
使用例
- αの近似
これはx2=α⇔x2−α=0を解く事と同じなので、これについてNewton法を適用します
f(x)=x2−αとすればf′′(x)=2>0より初期値を適当な大きい数にすれば適用できる条件を満たせます
C++での実装例:
double newton_sqrt(double x,double eps=1e-8){
if(x < 0)return -1;
if(!x)return 0;
double res = x < 1 ? 1 : x;
while(res*res - x > eps){
res = res - (res*res - x) / (2*res);
}
return res;
}
mt19997で107回実行したら1700msかかりました 尚 std::sqrt 17ms …
- 3αの近似
さっきみたいにf(x)=x3−α=0を解きます、f′′(x)=6xの符号はxの符号と必ず同じなのでα<0なら十分小さい負数を、α>0なら十分大きい正数を初期値にします
C++での実装例:
double newton_cbrt(double x,double eps=1e-8){
if(!x)return 0;
double res = abs(x) < 1 ? (x < 0 ? -1 : 1) : x ;
while(abs(res*res*res - x) > eps){
res = res - (res*res*res - x) / (3*res*res);
}
return res;
}
mt19997で107実行すると2670ms ( std::cbrt 750ms STLすごい)
- eαとかlog(α)とか三角関数の近似
Taylor展開である程度の次数まで展開してやれば、これらも有限次数の多項式で表せるので、Newton法が使えます
DKA法(Durand-Kerner-Aberth法)
Newton法を改良し、複素数の解も含んだ一般の代数方程式にも適用できるようにしたもの
謝罪
DKA法を読んでください(丸投げ)
まとめ
- Newton法は実多項式の近似解を素早く求められる(例外アリ)
- Newton法とTaylor展開で色んな初等関数の求根もできる
- DKA法はすごい
- Wolfram Alpha は最高
参考文献
A Tutorial of BNCpack[暫定版]
数値計算の常識-Newton法
DKA法