極限メモ#2〈Newton法〉(ニュートン――)


方程式の解を求める数値計算手法を用いて平方根の値を求める数列の問題.はじめに漸化式が与えられる場合もあるが,今回はあえて漸化式を導出する過程も取り入れる.

スポンサーリンク
Question 1
s > 0p > 0 とする.曲線 C \colon y = x^2 - p に対して,x=s である点を T_0 とし,点T_0 における C の接線を \ell_0\ell_0x 軸の交点の x 座標を a_1 とする.n = 1,2,\ldots に対して,x 座標が a_n である点を T_n,点 T_n における C の接線を \ell_n\ell_nx 軸の交点の x 座標を a_{n+1} \cdots と帰納的に定めることが出来たとして,以下の問に答えよ.ただし,すべての自然数 n に対して,a_n0 にならないとしてよい.

(1) a_1s,p を用いて表せ.また,a_{n+1}a_np を用いて表せ.

(2) すべての自然数 n に対して

    \[ 	a_n \geqq \sqrt{p} \]

が成り立つことを示せ.さらに

    \[ 	\bigl|a_{n+1} - \sqrt{p}\bigr| \leqq \frac{1}{2}\bigl|a_n - \sqrt{p}\bigr| \]

が成り立つことを示せ.

(3) 極限

    \[ \lim_{n \to \infty}a_n \]

を求めよ.

コメント

解答

(1) 解答

(2) 解答

(3) 解答


Newton法

Newton法は曲線の接線を用いて方程式の解を数値計算するアルゴリズムである.方程式 f(x) = 0 の解は,y=f(x) のグラフと x 軸との交点の x 座標と一致する.上の問題のようにあるグラフ上の点(普通は予想される解の値に近い x 座標の点)から接線を引き,その x 切片の値を計算すると,f(x) がある程度よい関数であれば,解の真の値に近づくことが多い.今回の例(2次関数)は非常によい関数で,初期値を x=0 にさえ設定しなければ,x = \pm \sqrt{n} の値を得ることができる.収束の速さも悪くなく,接線が引ける(=微分可能な)関数であればだいたい上手く動く.

導関数や漸化式を自分で計算して入力するなら,プログラミングでの実装も非常に簡単である.Python を用いて, \sqrt{p} の値を求めるプログラムの例は,初期値を s ,繰り返しの回数を n として

などとすれば動く.Decimal はよく覚えていないが,付けておけば小数点以下の計算が精密になったはず.

なお,これを用いて初期値 1 から \sqrt{2} の値を求めてみると

1
1.5
1.416666666666666666666666666
1.414215686274509803921568628
1.414213562374689910626295579
1.414213562373095048801689624
1.414213562373095048801689624

初期値 3 から \sqrt{2} の値を求めてみると

3
1.833333333333333333333333333
1.462121212121212121212121212
1.414998429894802951797770450
1.414213780047197583920023414
1.414213562373111800871136417
1.414213562373095048801688724
1.414213562373095048801688724

となった.5,6回でかなり正確な値を出すことができている.



スポンサーリンク