Newton-Raphson 法

Newton(-Raphson) 法 (Newton の反復法) というのは, 方程式 f(x) = 0 の近似解を求める方法の一つである。 どちらかというと補遺で扱うような内容であるが, 「微分 3」 自体が非常に小さい block であるから, 別建てせずに書いてしまうことにした。

x = α を真の解, 即ち f(α) = 0 とする。 α の適当な近傍 I で, f ∈ C²(I) (つまり f''(x) までは存在して I で連続),  f'(x) ≠ 0 on I, f''(α) ≠ 0 を仮定しておく。 x₀ ∈ I を十分 α に近い値に採れるならば, 初期条件 x₀ の元で漸化式

x_n+1 = x_n - f(x_n)/f'(x_n)

が定める数列 {x_n} は α に収束する。 これを Newton-Raphson 法 (又は Newton の反復法) という。

先ず I を α の h 近傍としておこう, 即ち I = [α - h, α + h], h > 0. h の大きさは後で考えるとする。 x ∈ I  に関し

f(α) - f(x) = ∫₀¹f'(x + t(α - x))(α - x)dt

であることはすぐに分かる。 簡単の為に F(x) = x - f(x)/f'(x) とすると (仮定により I 上では well-defined で)

F(x) - F(α) = x - f(x)/f'(x) - (α - f(α)/f'(α)) = x - α - f(x)/f'(x)
= -(α - x) + (f(α) - f(x))/f'(x) = (1/f'(x))(f(α) - f(x) - f'(x)(α - x))
= (1/f'(x))∫₀¹(f'(x + t(α - x)) - f'(x))(α - x)dt.

更に, 平均値の定理から

f'(x + t(α - x)) - f'(x) = t(α - x)f''(x + θt(α - x)), 0 < θ < 1

となる θ が存在する。 そこで I 上 |f''(x)| ≦ M となる M を採り (それは C² だから存在する), |1/f'(x)| ≦ K となる K を採る (f'(x) ≠ 0 on I だから存在する) とすると

|F(x) - F(α)| ≦ |1/f'(x)|∫₀¹|(f'(x + t(α - x)) - f'(x))(α - x)|dt
≦ K∫₀¹ tM(α - x)² dt = KM(α - x)² [t²/2]₀¹ = KM(α - x)²/2 ≦ (KM/2)h².

だから最初から h ≦ 2/(KM) としておけば |F(x) - α| = |F(x) - F(α)| ≦ h なので, F は I から I への写像 (函数) である。 つまり, 漸化式は初期条件 x₀ が I から採られている限り, その後の全ての数 x_n を I の中の数として定める。 更に

F'(x) = 1 - (f'(x)² - f(x)f''(x))/f'(x)² = f(x)f''(x)/f'(x)²

であるから, K と M の定め方によって

|F'(x)| ≦ MK²|f(x)|.

Weierstrass の定理により, 閉区間 I 上で |f(x)| は最大値を採るので, それを A_h と置くと, 仮定によって (f(α) = 0 だから) A_h → 0 (as h → 0) であるから, h を充分小さく採れば r = MK²A_h < 1 と出来る。 即ち

|F'(x)| ≦ MK²|f(x)| ≦ MK²A_h = r < 1.

従って, 再び平均値の定理により x, y ∈ I に対し

|F(x) - F(y)| = |F'(y + θ(x - y))||x - y| ≦ r|x - y|.

これはつまり, 最初に与えた漸化式が Cauchy 列であることを示している。

実際: x = x_n, y = x_m とすると|x_n+1 - x_n| ≦ rⁿ|x₁ -x₀| が示せるので, |x_n - x_m| ≦ |x_n - x_n-1| + |x_n-1 - x_n-2| + … +  |x_m+1 - x_m| ≦ (r^n-1 + r^n-2 + … + r^m)|x₁ -x₀| ≦ (r^m/(1 - r))|x₁ -x₀| であるから。

又, 極限値を x とすると x = x - f(x)/f'(x) であるから f(x) = 0 でなければならない。□

さて, 上記の証明中に

|F(x) - F(α)| ≦ KM(α - x)²/2

という式が表れているが, これから |x_n+1 - α| ≦ (KM/2)|x_n - α|² であることが分かる。 これを右辺の |x_n - α|² に因んで二位の収束をする (或いは二次収束をする) という。 これは誤差が自乗の level で小さくなっていくことを示している。 即ち, この方法の収束はかなり速い。

尚, この方法を n 元連立非線型方程式にも拡張できる。 又 Kantorovich はこの方法で解を求められる初期条件 x₀ の条件と収束測度の評価を与えている (1948)。

実際に Newton-Raphson 法を用いるのに, 何でも良いが, 例えば a > 0 として √a を求める式を考えてみよう。

f(x) = x² - a とすれば, これの解の一つが √a であり, f'(x) = 2x, f'''(x) = 2 だから, 例えば, [1, 3/2] 位のところでやれば, 多分条件を満たしているであろう。 このとき

x_n+1 = x_n - f(x_n)/f'(x_n) = x_n - (x_n² - a)/(2x_n) = (2x_n - x_n + a/x_n)/2 = (x_n + a/x_n)/2.

(これは漸化式の定義の例の 8 に掲げたものである)

実は円周率を computer で何億桁も計算するのに用いられる方法のうち J. M. Borwein, P. B. Borwein 兄弟の公式や Ramanujan の公式, Salamin-Brent の algorithm 等では √2 を Newton-Raphson method で求めておく必要がある。 但し, 上記の方法ではなくて f(x) = 1/x² - a にこれを適用した x_n+1 = x_n(3−ax_n⁴)/4 から 1/√a を求めておいて, a = a×(1/√a) で計算するそうである。

参考文献:

山本哲朗: 方程式と不動点 --- 特集 不動点から何が見えるか, 数学セミナー (2), 2002.

次へ
微分 3 の目次へ