137

第 12 章 非線型方程式の解法
板谷 非線型では，線型で分かっている事を非常によく使うわけですね。だからまず線型解析をちゃんと勉強することですね。
山口 ちゃんとというのはどこまでやったらいいわけですか。
藤井 一生線型をやらねばいけない。(笑)
山口昌哉

編「非線型の現象と解析」(日本評論社)

本章では Newton 法を中心とする非線型方程式の解法について論じる。非線型方程式は線型方程式とは異なり，一般には解の存在や一意性は保証されない。後述の縮小写像が定義できる非線型方程式のみ，解の存在が証明される。以下，まず縮小写像の原理を解説した後，変数の数と方程式の次元数が同じ非線型方程式に適用される Newton 法と，準 Newton 法，Regula-Falsi 法について解説する。

12.1 方程式の分類
一般に，方程式 (equation) とは未知数を陰的に含む等式のことを言う。方程式は，等式の本数 (次元数, 1 次元か n(> 2) 次元か)，未知数の個数 (1 つか複数か)，そして未知数の線型性 (あるかないか) によって分類できる。本章の本論に入る前に，ここでその分類について再確認しておくことにする。なお，本章では未知数の個数と等式の数が一致している方程式のみを扱うことにする。
まず，未知数 1，次元数 1 の方程式を考える。未知数を x を書けば，これを独立変数とする一次元関数 f を用いて方程式を

f (x) = 0(12.1)と表現できる。左辺の変数 x に関して関数 g が線型性を持つとは，任意の定数 α と変数 y, z に対してg(αy) = αg(y)g(y + z) = g(y) + g(z)となることをいう。この場合，定数 a を用いて g(x) = ax と表現できる。これに定数 b を加えてf (x) = g(x) + b を作ると，(12.1) はax + b = 0 (a, b は定数)

第 12 章 非線型方程式の解法

138となる。これと線型 (一次) 方程式と呼ぶ。これ以外の方程式は全て非線型方程式 (nonlinear equation)とカテゴライズされる。但し，非線型方程式の中でも， f が m 次の多項式である場合，つまりm∑ai xi = 0i=0を代数方程式 (algebraic equation) と呼ぶ。代数方程式は解の存在が明らかであり，さまざまな問題に登場するため，これに特化した数値解法が用意されている (次章参照)。本書では，線型方程式以外の方程式を広義の非線型方程式，線型方程式と代数方程式を除いた方程式を狭義の非線型方程式と呼ぶことにする。
以上をまとめると，1 次元 1 変数方程式は下記のように分類できる。

ax + b = 0 (a, b は定数)


∑


mi
1 次元 1 変数方程式 f (x) = 0 
 i=0 ai x = 0 代数方程式

広義の非線型方程式
狭義の非線型方程式
n(> 2) 次元 n 変数方程式も同様に分類できる。この一般形は，未知数を x1 , x2 , ..., xn とすれば，n個の n 変数関数 f1 , f2 , ..., fn を用いて
f1 (x1 , x2 , ..., xn ) = 0






 f2 (x1 , x2 , ..., xn ) = 0

..



.





 fn (x1 , x2 , ..., xn ) = 0と表現される。これをベクトル表記を用いて

x = [x1 x2 · · · xn ]T , f = [ f1 f2 · · · fn ]Tとまとめることで，方程式もf(x) = 0(12.2)と簡潔に記述することが出来る。

n 次元方程式の場合も，関数 g(x) が変数 x に関して線型性を持つとは，1 次元の場合同様，任意の定数 α と，変数 y, z に対してg(αy) = αg(y)g(y + z) = g(y) + g(z)となることをいう。よって，このような g は n × n 行列 A を用いて g(x) = Ax と表現できる。これと定数ベクトル c を用いて f(x) を f(x) = g(x) + c とすると，(12.2) 式はAx + c = 0 (A ∈ Mn (R) or Mn (C), c ∈ Rn or Cn )となり，これは連立一次方程式 (7.1) に他ならない。この解法については既に第 7, 9, 10 章で解説した。

12.2. 縮小写像

139n 次元の代数方程式は，各 fi が x1 , x2 , ..., xn に関する多項式として表現できるものをいう。
以上より，n 次元 n 変数方程式は次のように分類される。


Ax + c = 0 (A ∈ Mn (R), c ∈ Rn )

n 次元 n 変数方程式 f(x) = 0 代数方程式
広義の非線型方程式





狭義の非線型方程式

問題 12.1.1次の方程式は，上記のどの分類に当てはまるか，答えよ。

1. 3x2 + 1 = 0
2. sin x − x = 02
2x1 x2 + x1 + x2 = 0
3.  x3 x2 + x1 x2 + 2 = 01 212.2 縮小写像
解くべき非線型方程式

f(x) = 0(12.3)

において，関数 f(x) を x ∈ Rn → f(x) ∈ Rn とする。この非線型方程式 (12.3) の解が存在したとして，それを a とした時，Φ(a) = aを満足する関数 Φ(x) を考える。この関数を用いた漸化式

xk+1 := Φ(xk )によって生成されたベクトル列 x0 , x1 , x2 .... に対して||Φ(xk+1 ) − Φ(xk )|| ≤ α||xk+1 − xk || (k = 0, 1, 2, ...)となる定数 0 < α < 1 が存在するとき，この Φ(x) を縮小写像と呼ぶ。このような Φ(x) が存在すればこのベクトル列は収束しlim xk = ak→∞(12.4)となることが証明される。しかしこれを言い換えれば，「解の近くに初期値を取ることが出来れば収束する」ということを言っているに過ぎない。解が一つであるとは限らないし，そもそも未知の解を求めようというのにその近傍を限定することはそれ程簡単なことではない。従って，実際にはある程度の範囲で関数 f(x) の図を描くか，もしくはその断面を描くかして，解の存在を確認することになる。
この非線型方程式を解くアルゴリズムは，f(x) から Φ(x) をどのように導くかということで決定される。が，それは必ずしも縮小写像にはならないことは言うまでもない。

第 12 章 非線型方程式の解法

140

12.3 1 次元 1 変数方程式に対する Newton 法
1 次元 1 変数方程式 (12.1) に対する解法を考える。まず，第 6 章の平方根の計算で用いた Newton法の一般形を示す。
アルゴリズム 26 (Newton 法 (1 次元 1 変数方程式))

1. 初期値 x0 ∈ R(or C) を設定する。
2. for k = 0, 1, 2, ...
(a) xk+1 := xk −f (xk )f ′ (xk )(b) 収束判定
(12.1) を満たす複素数解を求める場合は複素数の初期値を，実数解のみを求める場合は実数の初期値を設定する。どちらにしろ，反復過程が縮小写像になるよう，解の近くに初期値を設定することが望ましい。数学的には簡単なことではないが，実際の現象の数理モデルとして (12.1) が表現されている場合は，物理的条件から，解の「あたり」をつけることが出来ることも多いようである。
実数解を求める Newton 法は，図 12.1 のようにして幾何学的な解釈が出来る。
f (x)(x0, f (x0))(x1, f (x1))

x0x1

解x2

図 12.1: Newton 法の幾何学的意味

つまり，点 (x0 , f (x0 )) における接線と x 軸との交点が次の近似値 x1 になり，点 (x1 , f (x1 )) における接線と x 軸との交点が次の近似値 x2 になり，... という具合である。しかしこれでは収束の「速さ」が不明確な上，複素数解に収束する状況が説明できない。
そこで，Taylor 展開に基づく Newton 法の解釈を試みよう。x0 と x1 との差を h0 = x1 − x0 とすれば， f (x) が x0 の近傍で 2 階以上連続微分可能であれば Taylor 展開より

f (x1 ) ===f (x0 + h0 )
1 ′′f (x0 )h20 + · · ·2!
f (x0 ) + f ′ (x0 )h0 + O(h20 )f (x0 ) + f ′ (x0 )h0 +12.4. n 次元 n 変数方程式に対する Newton 法141

表 12.1: Newton 法の収束 (1 次元, IEEE754 倍精度計算)kxk

01.00000000000000000

10.750363867840243892

20.739112890911361675

30.739085133385283921

40.739085133215160672となる。本来の目的は f (x0 + h0 ) = 0 となる h0 を決めることであるが，とりあえず次善の策として右辺の下線部が 0 になるような h0 = − f (x0 )/ f ′ (x0 ) を取る。さすれば

f (x1 ) = O(h20 )となることは確実であるから，|h0 | < 1 であれば，少なくとも x1 は x0 よりも解に近いことになる。
同様なやり方で，h1 = − f (x1 )/ f ′ (x1 ), h2 = − f (x2 )/ f ′ (x2 ), ..., とし，これを用いて近似値 x2 = x1 + h1 ,x3 = x2 + h2 , ... を作っていけば，それぞれ O(h21 ), O(h22 ),... と，近似値との差の 2 乗の速さで収束していくことが分かる。この意味で Newton 法は 2 次収束する解法であると呼ばれている。これは，解の条件と初期値が良ければ，次の時点の近似解は 2 倍の精度を得ることができることを示している。
例題 12.3.1

1 次元の非線型方程式
x − cos x = 0を Newton 法で解くと，その漸化式は

xk+1 := xk −xk − cos xk
1 + sin xkとなる。初期値を x0 := 1.0 とした時の近似解の収束状況を表 12.1 に示す。
問題 12.3.1

x − sin x = 0 の実数解の一つを Newton 法を用いて求めよ。

12.4 n 次元 n 変数方程式に対する Newton 法
n 次元 n 変数方程式 (12.2) に対しても，前述の 1 次元問題と同様，Taylor 展開を考えることでNewton 法を得ることが出来る。
初期値 x0 ∈ Rn (or Cn ) と次の近似値 x1 との差を h0 とし，全ての成分が全ての変数 x = [x1 x2 · · · xn ]Tに対して１階微分可能である時，f(x1 )= f(x0 + h0 ) の周りで Taylor 展開すると，][∂f(x0 ) h0 + · · ·f(x1 ) = f(x0 + h0 ) = f(x0 ) +∂x

第 12 章 非線型方程式の解法

142となる。ここで，下線部は Jacobi 行列 (Jacobian matrix) であり，これを成分ごとに書くと

 ∂ f1 ∂x1[ ]  ∂ f2 ∂x
∂f=  . 1∂x
 ..
∂ fn∂x1

 []
 = ∂ fi.. ∂x j. ∂ fn

∂ f1
∂x2
∂ f2
∂x2······∂ f1∂xn∂ f2∂xn∂ fn∂x2···

∂xn..
.となる。

1 次元問題同様，h0 の一次項まで 0 になるような h0 は[][]−1∂f∂ff(x0 ) +(x0 ) h0 = 0 ⇔ h0 = −(x0 ) f(x0 )∂x∂xとなる。よって，n 次元 n 変数方程式に対する Newton 法は次のようになる。
アルゴリズム 27 (Newton 法 (n 次元 n 変数方程式))

1. 初期値 x0 ∈ Rn を設定する。
2. for k = 0, 1, 2, ...
]−1[k)f(xk )(a) xk+1 := xk − ∂f(x∂x(b) 収束判定
例題 12.4.1

2 次元の非線型方程式   x1 + x2 − 3   0  =  
0x1 x2 − 2を Newton 法で解くと，その漸化式は

 (k+1)   (k)    x   1 x 1(k+1)  :=  1(k)  −  (k)x2x2x2−1 1   x1(k) + x2(k) − 3  x1(k) x2(k) − 2x1(k)となる。初期値を x0 := [10 − 10]T とした時の近似解の収束状況を表 12.2 に示す。
問題 12.4.1

1. n 次元の非線型方程式に Newton 法を適用する時，反復 1 回毎の計算量を求めよ。
2. 3 次元の非線型方程式

  
 x1 + x2 + x3 − 6   0    =  0 
x1 x2 x3 − 6  
0x12 + x22 + x32 − 14に Newton 法を適用する時の漸化式を求めよ。また実際の計算において留意すべき点はどこか？

12.5. 準 Newton 法と Regula-Falsi 法

143

表 12.2: Newton 法収束 (2 次元, 2 進 128 桁計算)

kxk

010-1016.400000000000000000000000000000000000002

-3.4

2

3.975510204081632653061224489795918367352-0.9755102040816326530612244897959183673479

32.788249743425812204519070612581388697281

0.2117502565741877954809293874186113027228

42.241155746850199313542849724396028442936

0.7588442531498006864571502756039715570645

52.039233382784949106980013450642101121817

0.9607666172150508930199865493578988781865

62.001427265423368836896825250714132069516

0.9985727345766311631031747492858679304852

72.000002031288213879092684800652133329163

0.999997968711786120907315199347866670841

82.000000000004126115045186393794669669899

0.9999999999958738849548136062053303301013

92.000000000000000000000017024825365973028

0.9999999999999999999999829751746340269752

102.000000000000000000000000000000000000006

0.9999999999999999999999999999999999999979

12.5 準 Newton 法と Regula-Falsi 法
Newton 法のアルゴリズムは，必ず関数 f(x) の１階導関数，もしくは Jacobi 行列を必要とし，反復 1 回毎にそれを含む連立一次方程式を生成して解く必要がある。これは次元数が多いほど計算時間が必要となることになる。収束がある程度早ければその分相殺される可能性もあるが，効率が必ずしもよいとは言えない。
そこで，収束の早さはある程度犠牲にし，連立一次方程式を解く部分は固定にしておく方法が考えられる。これを準 Newton 法と呼ぶ。
アルゴリズム 28 (準 Newton 法)

1. 初期値 x0 ∈ Rn を設定する。
[]0)
2. Jacobi 行列 ∂f(xを LU 分解しておく。
∂x
3. for k = 0, 1, 2, ...
[]−10)f(xk ) をあらかじめ LU 分解しておいたものを使って求める。
(a) hk := ∂f(x∂x(b) xk+1 := xk − hk
更に，１次元の非線型方程式に対しては， f ′ (x) を差分商で置き換えたものを Regula-Falsi 法と呼ぶ。
アルゴリズム 29 (Regula-Falsi 法)

1. 初期値 x0 , x1 ∈ R を設定する。
2. for k = 1, 2, ...
(a) xk+1 := xk − (xk − xk−1 ) f (xk )/( f (xk ) − f (xk−1 ))第 12 章 非線型方程式の解法

144

表 12.3: Newton 法と準 Newton 法の収束 (1 次元, 2 進 128 桁計算)

Newton 法における xkk

準 Newton 法における xk

0

1.0

1.0

10.7503638678402438930349423066821768532468

0.7503638678402438930349423066821768532468

20.7391128909113616703605852909048902340029

0.7400878037706862141939434356308994683328

30.7390851333852839697601251208568043328895

0.7391763297791593372786183794757489770411

40.7390851332151606416617026256850263723252

0.7390934445525557316449579848622171459514

50.7390851332151606416553120876738734040134

0.7390858908197599946335879143106433805112

一般に，解の条件が良い場合は (1)Newton 法, (2) 準 Newton 法，(3)Regula-Falsi 法の順に反復回数が多くなる。が，計算量もその順に多くなるかどうかは判然としない。収束状態と方程式の形，初期値のとり方によって異なってくる。
また，解の条件が悪い場合，殊に複数の解が近いところに固まっていたり，重複解を持ったりすると，Newton 法は初期値が少しでも異なると別の解に収束したり，発散したりすることが知られている。丸め誤差の影響も受けやすくなり，１次元の代数方程式のようなものでも，ある特定の解に収束する Gauss 平面上 (図 2.2) の領域を求めて色分けしてみるとかなり複雑なものになることが知られている。
例題 12.5.1
先の例題 12.3.1 の方程式に対して Newton 法と準 Newton 法を適用した結果を表 12.3 に示す。この
初期値ではどちらも収束するが，準 Newton 法の収束速度は Newton 法のそれに比べてかなり遅いことが分かる。
問題 12.5.1

1. Regula-Falsi 法を多次元の方程式に適用するには，Jacobi 行列の各 (i, j) 要素を差分商(k)(k) (k)(k)(k)(k)(k) (k)(k)fi (x1(k) , ..., x(k)j−1 , x j + h j , x j+1 , ..., xn ) − fi (x1 , ..., x j−1 , x j , x j+1 , ..., xn )h(k)j(k)(k−1)に置き換えればよい。ここで h(k)。これを用いて先の 2 次元の例題に Regula-Falsi
j = xj − xj法を適用し，近似解を求めよ。

2. 1 次元の非線型方程式に対しては，解が存在する区間 [x0 , x1 ] を最初に設定し(a) for k = 1, 2, ...
(b) c = (xk + xk−1 )/2 とし，f (xk−1 ) f (c) < 0 ならば xk+1 := c, xk := xk−1 とする。
f (c) f (xk ) < 0 ならば xk+1 := xk , xk := c とする。
として，徐々に解が存在する区間を縮小していく方法を 2 分法 (bisection method) と呼ぶ。この解法の特徴を Newton 法，Regula-Falsi 法と比較しつつ述べよ。

12.5. 準 Newton 法と Regula-Falsi 法

145

演習問題
1. 次の非線型方程式の実数解のうちの一つを求めたい。この時，次の問に答えよ。
x2 = tan 2x − 2(a) Newton 法の漸化式を求めよ。
(b) 上の漸化式を用いて，10 進 3 桁以上の精度を持つ解の近似値を求めよ。またその手順も記述せよ。

2. 非線型方程式 x2 − exp(x) = 0 の実数解を全て求めたい。次の問いに答えよ。
(a) この方程式の実数解の個数を，理由を含めて答えよ。
(b) この方程式の実数解を全て求めよ。但し精度桁は 10 進 3 桁以上とする。
(c) この方程式を次のようにして求める。
i. exp(x) を 2 次までの Maclaurin 展開式に置き換える。
ii. 置き換えた 2 次方程式を解の公式を用いて求める。
このようにして求めた二つの解 xe1 ，xe2 のうち，実数解に近い方の値の相対誤差を求めよ。

3. 非線型方程式の解法は，線型方程式にも対応できることを説明せよ。
4. 図 12.1 に示すような幾何学的解釈によって，Newton 法の漸化式が得られることを説明せよ。
5. f (x) が 3 階以上連続微分可能であるとき， f (xk ) + f ′ (xk )hk + 2!1 f ′′ (xk )h2k = 0 となるよう hk を定める解法を Halley 法と呼ぶ。具体的には，まず{}1 ′′′f (xk ) + hk f (xk ) + f (xk )hk = 02
より

hk = −f (xk )f ′ (xk ) + 12 f ′′ (xk )hkとし，左辺を hk = xk+1 − xk と置きなおして

xk+1 = xk −f (xk )f ′ (xk ) + 21 f ′′ (xk )hkとする。次に，右辺の hk を Newton 法の漸化式 xk+1 − xk = f (xk )/ f ′ (xk ) に置き直すと

xk+1 = xk −2 f (xk ) f ′ (xk )2( f ′ (xk ))2 − f (xk ) f ′′ (xk )を得る。こうして作られる漸化式は 3 次収束する解法となる。先の 1 次元の例題に対してこの解法を適用し，3 次収束することを確認せよ。