物理のノート

反復法

ニュートン法

与えられた問題を数学的に解くための一連の手続きをアルゴリズム（Algorithm）と称する.
アルゴリズムには,必要な数学的な手続きの回数が,有限回か無限回かで大きく分けられる.有限回の解法を直接法といい,無限回の解法を反復法という.
直接法の例には,連立1次方程式の解法であるガウスの消去法がある.

反復法の例には,ここで取り上げるニュートン法（Newton's method）が知られている.

ニュートン法は,1変数関数$f(x)$において,$f(x)=0$を満たす$x$を求める解法である.

この問題を解くためにニュートン法では,$y=f(x)$および,その接線を考える.
$y=f(x)$が$x$の2次関数である場合,接線の傾きは$f'(x)$である.
$x=x_0$における接線の方程式は, \begin{equation} y-f(x_0)=f'(x_0)(x-x_0) \end{equation} となり,接線と$y=0$すなわち$x$軸との交点を$(x_1,0)$とすると,(1)式に代入して, \begin{equation} 0-f(x_0)=f'(x_0)(x_1-x_0) \end{equation} \begin{equation} -f(x_0)=f'(x_0)(x_1-x_0) \\ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \end{equation} を得る.

ここで,適当な$x_0$を選んで$x_1$を求める.そして$x_1$を$x_0$に置き換えて計算を反復すると,$f(x)=0$を満たす$x$にやがてたどり着く,というアルゴリズムがニュートン法である.すなわち \begin{equation} x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)} \end{equation}

正数$a$の平方根$\sqrt a$の計算

ニュートン法を用いて,$2$の平方根$\sqrt 2$を求めてみる.

求める平方根を$x$とすると,代数的には$x^2-2=0$を解くことに等しい.
ここで$f(x)=x^2-2$とおくと,$f'(x)=2x$である.(4)式に代入して \begin{equation} x_{n+1} = x_{n} - \frac{x_n^2-2}{2x_n}=\frac12\left(x_n + \frac{2}{x_n}\right) \end{equation} このアルゴリズムをpythonで実装した例を示す.

#!/usr/bin/python2.7
# -*- coding: utf-8 -*-
import numpy as np
print('=============')
print('Newton法')
print('=============')
eps = 0.5*10.0**-5.0 ## 収束判定定数 e:epsilon
X = 0                ## 平方根（正数）
n = 0                ## 収束判定定数に至るまでの計算の反復回数
print("入力値の平方根（正の値）を表示する.")
print('収束判定定数（eps）は {} .'.format(eps)) 
num = float(input("> "))
print('入力値は {} である.'.format(num)) 

X0 = (num + 1.0)/2.0

while True:
    X = (X0 + num/X0)/2.0   

    if np.abs(X-X0) < eps * np.abs(X):
        break
        
    X0 = X
    n += 1
    
print('平方根は {} .'.format(X)) 
print('収束条件に至るまでの反復計算は {} 回.'.format(n))

実行結果は次のようになった.

	
=============
Newton法
=============
入力値の平方根（正の値）を表示する.
収束判定定数（eps）は 5e-06 .

> 2
入力値は 2.0 である.
平方根は 1.41421356237 .
収束条件に至るまでの反復計算は 2 回.

コンピュータでは無限回の演算は実行しない.ある程度の精度に達したと判定したならば演算を有限回で終了する.そのときの値を近似値として用いる.

なお,$\sqrt 10$の値を上述のpythonプログラムで計算すると次のような結果が得られる.

 
=============
Newton法
=============
入力値の平方根（正の値）を表示する.
収束判定定数（eps）は 5e-06 .

> 10
入力値は 10.0 である.
平方根は 3.16227766017 .
収束条件に至るまでの反復計算は 4 回.

index.htmlに戻る