READMEatcoderbookdiarydiary-2022draft

https://ja.wikipedia.org/wiki/%E3%83%8B%E3%83%A5%E3%83%BC%E3%83%88%E3%83%B3%E6%B3%95

ニュートン・ラフソン法

下記の式を満たす xx を求めることを考えてみる。

f(x)=0f(x) = 0

まず、適当な推定値を xnx_n とおく。これに対して、次の推定値を xn+1x_{n+1} とおき、下記のルールにより計算する。

「xn+1x_{n+1} は、f(x)f(x) のグラフ上の点 (xn,f(xn))(x_n, f(x_n)) における接線の x 切片である」

これを繰り返していくと xx の近似値を求めることができる。この方法をニュートン・ラフソン法という。

漸化式

推定値の選び方を漸化式で表現する。

xnx_n における f(x)f(x) の接線の傾きはその導関数により定まる。

f′(xn)f'(x_n)

そして接線は二つの点 (xn,f(xn))(x_n, f(x_n)) と (xn+1,0)(x_{n+1}, 0) を通過する。

二つの点から計算した傾きと導関数は一致するから

f′(xn)=0−f(xn)xn+1−xnxn+1−xn=−f(xn)f′(xn)xn+1=xn−f(xn)f′(xn)\begin{align} f'(x_n) &= \frac{ 0 - f(x_n)}{ x_{n+1} - x_n } \\ x_{n+1} - x_n &= - \frac{ f(x_n) }{ f'(x_n) } \\ x_{n+1} &= x_n - \frac{ f(x_n) }{ f'(x_n) } \tag{1} \end{align}

こうして完成した漸化式は、推定値からある数

f(xn)f′(xn)\frac{f(x_n)}{f'(x_n)}

を差し引くとより精度の良い推定値が計算できることを表している。

平方根を計算する例

最後に平方根を計算してみよう。 a=x\sqrt{a}=x とおく。

a=xa=x20=x2−a\begin{align} \sqrt{a} &= x \\ a &= x^2 \\ 0 &= x^2 - a \\ \end{align}

この等式から、 xx を変数とする関数を下記のように定める。

f(x)=x2−af(x) = x^2 - a

この関数に対して式(1)の漸化式を繰り返し使えば a の平方根を求められる。

たとえば a=2a = 2 で最初の推定値 x0=1x_0 = 1 とすると

x0=1x1=1.5x2=1.416666…x3=1.4142156862745…x4=1.4142135623746899…\begin{align} x_0 &= 1 \\ x_1 &= 1.5 \\ x_2 &= 1.416666… \\ x_3 &= 1.4142156862745… \\ x_4 &= 1.4142135623746899… \\ \end{align}

となり xnx_n の nn が大きくなるほど 2\sqrt{2} の真の値に近づいていることがわかる。