# 非線形方程式の反復解法：二分法・不動点反復・Newton 法・割線法の収束を証明する
> 二分法の誤差評価、不動点反復の大域・局所収束、Newton 法の局所 2 次収束と重根での 1 次収束、割線法の黄金比の次数、多変数の Newton 法と Kantorovich 型の存在定理を、Taylor の定理と縮小写像の原理から証明する。
> https://rikai.mugen-giken.com/mathematics/numerical-analysis/nonlinear-equations
## 0. この記事の要点
電卓で $\sqrt2$ を求めるとき、中では「だいたいの答えを出し、それを少し直して、また直す」という繰り返しが行われています。式で解けない方程式でも、同じ発想で答えに近づけます。この記事では、そのやり方がいくつかあること、どれが速いか、そして本当に答えに近づいていると言える理由を、順に確かめます。読み終えると、状況に応じてどの方法を選べばよいかと、その根拠を説明できるようになります。
- 方程式 $f(x) = 0$ の解を求める反復法は、**誤差 $e_k = x_k - x^*$ がどんな速さで $0$ に近づくか**で比べます。速さは「次数」（誤差が次の回に何乗になるか）と「漸近誤差定数」（そのときの比例係数）の 2 つの数で表します。
- **二分法**は連続性だけで動き、$k$ 回で誤差が $(b-a)/2^{k+1}$ 以下になります。遅いが必ず収束します。
- **不動点反復** $x_{k+1} = g(x_k)$ は、$|g'(x^*)| \lt 1$ なら 1 次収束し、$g$ の $p-1$ 階までの導関数が $x^*$ で消えれば $p$ 次収束します。証明は平均値の定理と Taylor の定理です。
- **Newton 法**は単根の近くで 2 次収束し、$e_{k+1}/e_k^2 \to f''(x^*)/(2f'(x^*))$ です。重根では 1 次収束に落ち、比は $(m-1)/m$ です。[凸関数](/mathematics/real-analysis/convex-analysis#def-convex)では初期値を解の右に取れば単調に収束します。
- **割線法**は導関数を使わずに、次数が黄金比 $(1+\sqrt5)/2 \approx 1.618$ 以上になります。
- 多変数の Newton 法も 2 次収束し、**Kantorovich 型の定理**は初期値での計算だけから解の存在と一意性を保証します。証明は[縮小写像](/mathematics/real-analysis/metric-spaces#def-contraction)の原理に帰着します。
## 1. 動機
$x^2 = 2$ の正の解、$x = \cos x$ の解、ある固有値問題の特性方程式の根。解を式で書けない方程式は、近似解の列 $x_0, x_1, x_2, \ldots$ を作って解に近づけるしかありません。ここで問うべきことは 3 つあります。
1. 列は解に**収束するか**。どんな初期値から出発すればよいか。
2. 収束するなら**どれだけ速いか**。正しい桁数が 1 回の反復で 1 桁ずつ増えるのか、2 倍ずつ増えるのか。
3. 計算をいつ**止めてよいか**。止めたときの誤差をどう見積もるか。
二分法は 1 に強く、Newton 法は 2 に強い、という対照がこの章の軸です。二分法は区間の端で符号が違えば必ず収束しますが、1 回あたり 1 ビットしか進みません。Newton 法は解の近くでは 1 回ごとに正しい桁数がおよそ 2 倍になりますが、初期値が悪いと発散したり周期軌道に入ったりします。実用の算法（Brent 法など。二分法のような確実な方法と、速い方法を切り替えて使う算法）は両者を組み合わせています。
3 の問いには、不動点反復の**事後誤差評価**と、Kantorovich 型の定理が答えます。前者は「直前の 2 つの反復値の差」から誤差の上界を出し、後者は初期値での値と導関数だけから、解が存在する球の半径を出します。後者は計算機援用証明（計算機の出力を数学の証明として使う方法）で使う区間 Newton 法（誤差の範囲を区間で追いながら行う Newton 法）の考え方の土台です（[浮動小数と区間演算](/mathematics/computer-assisted-proofs/floating-point-interval-arithmetic)）。
## 2. 準備：収束の次数
以下、実数列 $(x_k)$ が $x^*$ に収束するとき $e_k = x_k - x^*$ と書きます。
次の定義のねらいは、「誤差が 0 に近づく速さ」を 1 つの数で言えるようにすることです。次の回の誤差が今の誤差の何乗に比例するかを見て、その指数を次数と呼びます。
$x_k \to x^*$ で、すべての $k$ で $e_k \ne 0$ とする。$p \ge 1$ と $0 \lt C \lt \infty$ について
$$
\lim_{k\to\infty} \frac{|e_{k+1}|}{|e_k|^p} = C
$$
が成り立ち、さらに $p = 1$ のときは $C \lt 1$ であるとき、列は **$p$ 次収束**する（Q 次数が $p$ である）といい、$C$ を**漸近誤差定数**という。$p = 1, 2, 3$ をそれぞれ 1 次（線形）・2 次・3 次収束という。また $|e_{k+1}|/|e_k| \to 0$ のとき**超 1 次収束**するという。
$p = 2$ で $C$ がほどほどの大きさなら、$|e_{k+1}| \approx C|e_k|^2$ から、正しい桁数（$-\log_{10}|e_k|$）が 1 回ごとにほぼ 2 倍になります。1 次収束では、桁数が 1 回ごとに $-\log_{10} C$ ずつ増えるだけです。
Q 次数の定義は極限の存在を要求するので、誤差が規則正しく減らない列には使えません。そこで上界だけで速さを測る定義も用意します。2 種類あるのは、毎回きれいな比が取れる場合（Q 次数）と、上から押さえることしかできない場合（R 次数）の両方に使えるようにするためです。
$x_k \to x^*$ とする。$p \gt 1$ について、定数 $A \gt 0$ と $0 \lt q \lt 1$ があってすべての $k$ で
$$
|e_k| \le A\, q^{p^k}
$$
が成り立つとき、列は **R 次数 $p$ 以上**で収束するという。$p = 1$ では $|e_k| \le A q^k$ を条件とする。
$q^{p^k}$ は $p^k$ が指数に乗るので、$p = 2$ なら $q, q^2, q^4, q^8, \ldots$ と桁数が倍々に増える上界です。以下の定理では、多くの場合に両方の意味での次数を示します。
## 3. 二分法
$a \lt b$、$f : [a,b] \to \mathbb{R}$ は連続で $f(a) f(b) \lt 0$ とする。$a_0 = a$、$b_0 = b$ とし、$k = 0, 1, 2, \ldots$ について $c_k = (a_k + b_k)/2$ とおいて、$f(a_k) f(c_k) \lt 0$ なら $(a_{k+1}, b_{k+1}) = (a_k, c_k)$、$f(c_k) f(b_k) \lt 0$ なら $(a_{k+1}, b_{k+1}) = (c_k, b_k)$ と定める（$f(c_k) = 0$ なら $c_k$ を解として止める）。止まらないとき、
1. 各 $[a_k, b_k]$ は $f$ の零点を含み、$b_k - a_k = (b-a)/2^k$ である。
2. $(a_k)$ と $(b_k)$ は共通の極限 $x^*$ に収束し、$f(x^*) = 0$ である。
3. すべての $k$ で $|c_k - x^*| \le (b-a)/2^{k+1}$ が成り立つ。
**1.** 帰納法で $f(a_k) f(b_k) \lt 0$ と $b_k - a_k = (b-a)/2^k$ を示します。$k = 0$ は仮定です。$k$ で成り立つとき、$f(c_k) \ne 0$ なので $f(c_k)$ は $f(a_k)$ と $f(b_k)$ のどちらか一方と異符号であり、選んだ半分の区間の端点で $f$ は異符号です。幅はちょうど半分になります。端点で異符号なら $0$ は $f(a_k)$ と $f(b_k)$ の間にあるので、中間値の定理（
## 5. Newton 法
$x_k$ での $f$ の接線 $y = f(x_k) + f'(x_k)(x - x_k)$ と $x$ 軸の交点を次の近似とするのが **Newton 法**
$$
x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
$$
です。$f$ を $x_k$ のまわりで 1 次式に置き換えて解く、と言っても同じです。置き換えの誤差は Taylor の定理の 2 次の剰余なので、誤差が 2 乗で効くことが予想できます。
次の定理は文字が多いですが、言っていることは 1 つです。解の近くの範囲 $J$ で、$m$ は $|f'|$ の最小値、$M$ は $|f''|$ の最大値、$K = M/(2m)$ はそこから決まる 1 つの定数です。$K\delta \lt 1$ は「範囲の幅が十分狭い」という条件で、これが成り立てば 1 回の反復で誤差が必ず小さくなり、2 乗の形で減っていきます。
$I$ を開区間、$f : I \to \mathbb{R}$ を $C^2$ 級とし、$x^* \in I$ で $f(x^*) = 0$、$f'(x^*) \ne 0$ とする。
1. $\delta \gt 0$ が $J = [x^* - \delta, x^* + \delta] \subset I$ と $m = \min_J |f'| \gt 0$ を満たすとし、$M = \max_J |f''|$、$K = M/(2m)$ とおく。$K\delta \lt 1$ ならば、任意の $x_0 \in J$ について Newton 法の列は定義されて $J$ にとどまり、
$$
|e_{k+1}| \le K e_k^2, \qquad K|e_k| \le (K|e_0|)^{2^k}
$$
が成り立つ。とくに $x_k \to x^*$ で、R 次数 2 以上で収束する。
2. 1 の条件を満たす $\delta \gt 0$ は存在する。
3. 1 の状況で、すべての $k$ で $e_k \ne 0$ ならば
$$
\frac{e_{k+1}}{e_k^2} \to \frac{f''(x^*)}{2f'(x^*)}
$$
である。とくに $f''(x^*) \ne 0$ なら 2 次収束で、漸近誤差定数は $|f''(x^*)|/(2|f'(x^*)|)$ である。
$m$ と $M$ は、連続関数 $|f'|$、$|f''|$ の閉区間 $J$ 上の最小値・最大値として存在します（