数値解析

Newton 法
Newton 法は最も基本的な非線形方程式の反復解法であり，Newton–Raphson 法とも呼ばれる．

■ 全般的注意
x = (x1 , . . . , xn ) ∈ Rn に関する非線形連立方程式 f(x) = 0, すなわちfi (x) = 0(i = 1, . . . , n)(1)を考える1 ．解 x = α を有限回の四則演算で求めるのは一般に不可能であり，通常は，適当な初期値 x(0) から出発して，なんらかの反復法
x(ν+1) = x(ν) + ∆x(ν)(ν = 0, 1, . . .)(2)

によって α に収束する近似解列 {x(ν) } を数値的に生成する．
近似解列 {x(ν) } は，有限桁の演算によって計算される fi (x) の値などに基づいて生成されるので，必然的に丸め誤差を含み，その結果，数学的な意味で limν→∞ x(ν) = α となる
ようにはできない．使用する計算機などによって自然に定まる丸め誤差限界を δfi とする
とき，|fi (x)| が δfi 程度以下ならば fi (x) = 0 と見なさざるをえない．
すなわち，数値計算の立場からは，方程式 (1) を解くというのは |fi (x)| ≤ δfi (i = 1, . . . , n) を満たす x を求めることであると考え，|fi (x(ν) )| ≤ δfi(i = 1, . . . , n)(3)を反復法の停止規則にするのが健全である．これとは対照的に，適当に定めたノルムと要求精度 ε (例えば，ε = 10−5 など) によって ∥x(ν+1) − x(ν) ∥ ≤ ε の形の規準が停止規則に用いられることもあるが，ε の設定に関する恣意性もあり，上記のような立場からは推奨されない．

■ Newton 法の算法 (1 変数の場合)
1 変数の場合の公式は
x(ν+1) = x(ν) − f (x(ν) )/f ′ (x(ν) )(4)となる．これは，式 (2) における修正量 ∆x(ν) を，f (x) の x = x(ν) 付近での線形近似に基づいて定めたものである．実際，f の線形近似式

f (x) ≃ f (x(ν) ) + f ′ (x(ν) )(x − x(ν) )1(5)本来は，fi が多項式の場合に代数方程式，そうでないとき超越方程式と呼ぶが，fi が多項式でない一般の場合にも微分方程式に対するものとして代数方程式と呼ぶことがある．

1

で x = α とおいた式

0 ≃ f (x(ν) ) + f ′ (x(ν) )(α − x(ν) )(6)α ≃ x(ν) − f ′ (x(ν) )−1 f (x(ν) )(7)を α について解けばとなる．この右辺を新たな近似解としたものが式 (4) である．
幾何学的には，曲線 y = f (x) の点 (x(ν) , f (x(ν) )) における接線と x 軸との交点の x 座標が x(ν+1) である．なお，式 (4) の右辺を変形してx(ν+1) = [x(ν) f ′ (x(ν) ) − f (x(ν) )]/f ′ (x(ν) )(8)の形で計算するのは，丸め誤差の観点から不利である．
導関数の値は数値微分で代用することも多い．その場合，刻み幅 h の前進差分 [f (x +h) − f (x)]/h で近似する．h の選び方は，f (x) の計算における丸め誤差から決まる精度の限界を δf として，√h ≃ 2 δf /|f ′′ (x)|(9)とするとよい．
実際に方程式を解くときには初期値の選び方が重要となる2 ．また，近似解の振舞いを安定化する工夫として減速の手法（後述）がある．

■ Newton 法の算法 (多変数の場合)
多変数の場合の公式は
x(ν+1) = x(ν) − J(x(ν) )−1 f(x(ν) )(10)J = J(x) = (Jij (x)) = (∂fi /∂xj )(11)となる．ここで，は f(x) の Jacobi 行列であり，その存在と正則性は仮定している．実際の計算は，d(ν) に関する線形方程式
J(x(ν) )d(ν) = −f(x(ν) )(12)を解いて，x(ν+1) = x(ν) + d(ν) とする．
式 (10) は，式 (2) における修正量 ∆x(ν) を，f(x) の x = x(ν) 付近での線形近似に基づいて定めたものである．線形近似式
f(x) ≃ f(x(ν) ) + J(x(ν) )(x − x(ν) )(13)

0 ≃ f(x(ν) ) + J(x(ν) )(α − x(ν) )(14)

α ≃ x(ν) − J(x(ν) )−1 f(x(ν) )(15)

で x = α とおいた式

を α について解けば

2

例えば，連続変形法と呼ばれる方法で粗い近似解を求めて，これを初期値とすることができる．

2

表 1: Newton 法による方程式の解法
f (x) = x3 − 3x + 3; α1 = −2.1038034 · · ·ν012
34x(ν)−3.00000−2.37500−2.14001−2.10458−2.10380f (x(ν) )−1.50 E+1
−3.27 E+0−3.80 E−1
−8.01 E−3−9.54 E−7ν012345678910111213141516
17x(ν)
2.50000
1.79365
1.28406
0.634163
1.38830
0.845229
2.09196
1.51152
1.01366−11.1105−7.47567−5.09281−3.57146−2.66858−2.23305−2.11298−2.10385−2.10380f (x(ν) )1.11 E+1
3.39 E+01.26 E+01.35 E+01.51 E+0
1.07 E+0
5.88 E+0
1.92 E+0
1.00 E+0−1.34 E+3
−3.92 E+2
−1.14 E+2
−3.18 E+1
−8.00 E+0−1.44 E+0
−9.48 E−2−5.20 E−4−9.54 E−7となる．この右辺を新たな近似解としたものが式 (10) である．このような Newton 法の考
え方は，x が複素数ベクトルのときにも適用できる．さらに，抽象的な関数空間における作用素を含んだ方程式に対しても Newton 法を拡張することができる．
多変数の場合も，導関数の値を数値微分で代用することが多い．各方向の刻み幅 hj (j =1, . . . , n) を適当に定めて，Jij (x) ≃ [fi (x + hj ej ) − fi (x)]/hj(16)(ただし ej は第 j 単位ベクトル) と近似することにすれば，1 反復あたり関数 f を n + 1 回計算すれば済む．刻み幅 h の選び方は，1 変数の場合と同様である．

■ 例題
3 次方程式 f (x) = x3 −3x+3 = 0 は唯一の実根 α1 = −2.1038034 · · · をもつ．x(0) = −3として Newton 法を適用すると，表 1(a) のように速やかに x(ν) → α1 となる．δf = 10−5とすると，x(4) = −2.10380, f (x(4) ) = −9.5 × 10−7 で反復を停止する．x(0) = 2.5 とすると，x(ν) は表 1(b) のような激しい挙動を示す．結局は x(ν) → α1 となるが安心して使えない．初期値の取り方が大切である．

■ Newton 法の収束性
Newton 法の解の近傍での振舞い (局所的収束性) は理論上も実用上も十分満足できるものであり，よい初期値から出発すれば十分速く解に収束することが保証される．一方，解3

から遠い所での振舞い (大域的収束性) については，近似解が大きく変動したり，周期的に振動したりするなど，問題点もある．
近似解 x(ν) が真の解 α に十分近いとき，1 回の Newton 反復でどの程度近似が改善されるかを調べよう．まず 1 変数 (n = 1) の場合を考え，ε = x(ν) − α, εe = x(ν+1) − α とおく．
x = α が f (x) = 0 の M 重根とすると，x が α に近いとき

f (x) ≃ a(x − α)M [1 + b(x − α)]とかけるので，式 (4) よりaεM [1 + bε]εe ≃ ε − M −1≃aε
[M + (M + 1)bε](a ̸= 0)(17))(b1ε + 2 ε21−MM(18)である．したがって，α が単根 (M = 1) なら 2 次収束，重根 (M ≥ 2) なら 1 次収束である．なお，M が既知ならば，修正量を M 倍してx(ν+1) = x(ν) − M f (x(ν) )/f ′ (x(ν) )(19)とすると，{x(ν) } は α に 2 次収束する．
多変数 (n ≥ 2) の場合も，J(α) が正則ならば (n = 1 の単根の場合に対応して) 2 次収束する．次の定理では，J(x) の Lipschitz 連続性∥J(x) − J(y)∥ ≤ L∥x − y∥(x, y ∈ D)

(20)が仮定されるが，これは “f(x) が適当に滑らかならば” と読みかえても実用上差し支えな
い．f(x) が C2 級ならば J(x) は Lipschitz 連続である．
定理 1 J(x) が (1) の解 α の近傍で Lipschitz 連続 (20) で，J(α) が正則ならば，α に十分近い初期値から出発する Newton 法の近似解列は α に 2 次収束する．
補足：十分大きい ν に対して ∥x(ν+1) − α∥ ≤ C∥x(ν) − α∥p (C は定数) のとき，{x(ν) } はα に p 次収束するといい，p を収束次数と呼ぶ．とくに，p = 1 のとき，C < 1 を収束率という．

■ 減速
Newton 法の大域的収束性を改善するために，減速と呼ばれる手法が有効な場合がある．
これは，(12) で定めた修正方向ベクトル d(ν) を用いながら，(適当なノルムで測った) 関数値の大きさ ∥f(x(ν) )∥ を単調に減らそうとするものである．
適当にパラメタ 0 < β < 1, λ > 1 を定めておいて，∥f(x(ν) + µd(ν) )∥ ≤ (1 − (1 − β)µ)∥f(x(ν) )∥(21)を満たす µ (> 0) を µ = 1, λ−1 , λ−2 , · · · の順に探していき，そのような µ が見つかったら ∆x(ν) = µd(ν) とする．J(x(ν) ) が正則ならば，このような正の数 µ = µ(ν) が存在する
ことが知られている．このとき {∥f(x(ν) )∥}ν は単調減少列になる（しかし，0 に収束するとはかぎらない）．
以上 (2013-08-05)[この資料は，杉原正顯, 室田一雄，数値計算法の数理，４章 (岩波書店, 1994) の記述に基づいて編集したものである．]

4