高次ニュートン法(Householder法）をExcelで試してみる。

最近、twitterでニュートン法より高次の反復計算があるのを知った。それとはちょっと違うけど、同様に高次のニュートン法が↓に記載されていたので試してみよう。

http://www.sztaki.hu/~bozoki/oktatas/nemlinearis/SebahGourdon-Newton.pdf

Householder法は

x_n+1= x_n + (p+1) *( (1/f) ^(p)/ (1/f) ^(p+1) )_xn

です。(1/f) ^(p)はfの逆数のp階微分。

ではp=0のときは普通のニュートン法になる。2次収束

xn+1 = xn - f '/f

p=1のときは3次収束で

xn+1 = xn - f / (f ' - f ''*f /(2* f ' ) )

p=2のときは4次収束で

xn+1 = xn - f * (f ' ^2 - f ''*f / 2)/(f ' ^3 - f * f ' * f '' + f '''*f^2 /6)

ここまでは頑張って手計算。もう無理。なのでMaximaでやってみよう。

p=3のときは5次収束で、

xn+1=xn+(4*f(xn)*(f(xn)^2*(f(xn) ''')-6*f(xn)*(f(xn) ')*(f(xn) '')+6*(f(xn) ')^3))/(f(xn)^3*(f(xn) '''')-8*f(xn)^2*(f(xn) ')*(f(xn) ''')-6*f(xn)^2*(f(xn) '')^2+36*f(xn)*(f(xn) ')^2*(f(xn) '')-24*(f(xn) ')^4)

でした。

ではExcelで計算して比較してみる。√10の計算を初期値1としてグラフにしてみた。

予想通り収束は速いなあ。でもそのtwitterでも言われていたけど、結局高次の方法は乗算数など多くなるので有利ともいえないという。でもおもしろいな。