非線形方程式の反復解法：二分法・不動点反復・Newton 法・割線法の収束を証明する

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$ です。凸関数では初期値を解の右に取れば単調に収束します。
• 割線法は導関数を使わずに、次数が黄金比 $(1+\sqrt5)/2 \approx 1.618$ 以上になります。
• 多変数の Newton 法も 2 次収束し、Kantorovich 型の定理は初期値での計算だけから解の存在と一意性を保証します。証明は縮小写像の原理に帰着します。

この記事で使う事前知識

• 平均値の定理・Taylor の定理: 関数の変化量や 1 次近似の誤差を、途中のある点での導関数の値で表す定理。→ 平均値の定理とテイラーの定理
• 収束: 点列が限りなくある点に近づくこと。→ 収束
• 縮小写像: 2 点の距離を一定の割合 $L \lt 1$ 以下に縮める写像。→ 縮小写像
• 凸関数: グラフの 2 点を結ぶ線分が、グラフより上にある関数。→ 凸関数

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 法）の考え方の土台です（浮動小数と区間演算）。

2. 準備：収束の次数

以下、実数列 $(x_k)$ が $x^*$ に収束するとき $e_k = x_k - x^*$ と書きます。

次の定義のねらいは、「誤差が 0 に近づく速さ」を 1 つの数で言えるようにすることです。次の回の誤差が今の誤差の何乗に比例するかを見て、その指数を次数と呼びます。

定義 2.1（収束の次数（Q 次数）と漸近誤差定数）↗

$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 次数）の両方に使えるようにするためです。

定義 2.2（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. 二分法

定理 3.1（二分法の収束）✓

$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}$ が成り立つ。

証明（定理 3.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.7［極限と連続性］）から $[a_k, b_k]$ に零点があります。

2. 作り方から $a_k \le a_{k+1}$、$b_{k+1} \le b_k$、$a_k \lt b_k \le b$ です。$(a_k)$ は単調増加で上に有界なので、単調有界定理（定理 2.1［級数と収束判定］）から収束します。極限を $x^*$ とします。$b_k = a_k + (b-a)/2^k$ なので $b_k \to x^*$ でもあります。$a_k$ と $b_k$ は $[a,b]$ の点で、$f$ は $x^*$ で連続なので、数列による特徴づけ（定理 4.5［極限と連続性］。$a_k = x^*$ となる項では $f(a_k) = f(x^*)$ は自明）から $f(a_k) \to f(x^*)$、$f(b_k) \to f(x^*)$ です。積の極限をとると、$f(a_k) f(b_k) \lt 0$ から $f(x^*)^2 \le 0$、すなわち $f(x^*) = 0$ です。

3. $a_k$ は増加して $x^*$ に、$b_k$ は減少して $x^*$ に収束するので、$a_k \le x^* \le b_k$ です。$c_k$ はこの区間の中点なので、$|c_k - x^*| \le (b_k - a_k)/2 = (b-a)/2^{k+1}$ です。

∎

誤差の上界が $f$ によらず決まることが二分法の強みです。許容誤差 $\tau$ を達成する回数は $k \ge \log_2((b-a)/\tau) - 1$ で、$[0,1]$ から $10^{-12}$ まで縮めるには約 40 回かかります。1 回で 1 ビットずつ、10 進では約 3.3 回で 1 桁ずつ進みます。Q 次数の言葉では、$|c_k - x^*|$ そのものは規則正しく減るとは限りませんが、上界 $(b-a)/2^{k+1}$ が比 $1/2$ で減るので、R 次数 1 で収束します。

例 3.2（二分法と Brent 法の反復回数）

$f(x) = \cos x - x$ を $[0,1]$ で考えます。$f(0) = 1 \gt 0$、$f(1) = \cos 1 - 1 \lt 0$ です。二分法と、SciPy の brentq（二分法・割線法・逆 2 次補間を組み合わせた Brent 法）で、区間幅の許容値ごとに反復回数を比べます。

# Python 3.12.10 / SciPy 1.18.1 / mpmath 1.3.0
import math
from scipy.optimize import brentq
from mpmath import mp, findroot, cos as mcos

def bisect(f, a, b, tol):
    """f(a)f(b) < 0。区間幅が tol 以下になるまで二分する"""
    fa, n = f(a), 0
    while b - a > tol:
        c = (a + b) / 2
        fc = f(c)
        n += 1
        if fc == 0:
            return c, n
        if (fa < 0) == (fc < 0):
            a, fa = c, fc
        else:
            b = c
    return (a + b) / 2, n
f = lambda x: math.cos(x) - x            # 根は x = cos x の解
mp.dps = 30
ref = float(findroot(lambda x: mcos(x) - x, 0.7))
print(" tol     二分法: 回数 誤差      brentq: 回数 誤差")
for tol in [1e-4, 1e-8, 1e-12]:
    xb, nb = bisect(f, 0.0, 1.0, tol)
    xr, res = brentq(f, 0.0, 1.0, xtol=tol, full_output=True)
    print(f"{tol:.0e}      {nb:3d}  {abs(xb - ref):.2e}"
          f"          {res.iterations:2d}  {abs(xr - ref):.2e}")
print("理論の回数 ceil(log2(1/tol)):",
      [math.ceil(math.log2(1 / t)) for t in [1e-4, 1e-8, 1e-12]])

 tol     二分法: 回数 誤差      brentq: 回数 誤差
1e-04       14  2.01e-05           5  5.93e-06
1e-08       27  9.04e-10           6  1.35e-09
1e-12       40  5.17e-14           7  4.77e-15
理論の回数 ceil(log2(1/tol)): [14, 27, 40]

検算. (a) 参照値は mpmath の findroot で 30 桁まで求めた $x = \cos x$ の解 $0.739085\ldots$ です。(b) 二分法の誤差はどれも許容値の半分以下で、定理 3.1 の 3 の評価（最後の区間の中点なので幅の半分以下）の内側にあります。Brent 法は別の算法で、同じ解に許容値以下の誤差で達しています。(c) 二分法の回数は幅 $2^{-n} \le \tau$ となる最小の $n = \lceil \log_2(1/\tau) \rceil$ に一致し、許容値を $10^{-4}$ 倍するごとに約 13.3 回ずつ増えます。Brent 法は 1 回ずつしか増えず、超 1 次収束していることが読み取れます。

4. 不動点反復

方程式 $f(x) = 0$ を $x = g(x)$ の形に書き直し、$x_{k+1} = g(x_k)$ と反復するのが不動点反復です。$g(x) = x - f(x)$、$g(x) = x - f(x)/f'(x)$ など書き直し方はいくらでもあり、どれを選ぶかで収束の速さが変わります。

定理 4.1（不動点反復の大域収束と誤差評価）✓

$a \lt b$ とし、$g : [a,b] \to [a,b]$ が定数 $0 \le L \lt 1$ について

$$|g(x) - g(y)| \le L |x - y| \qquad (x, y \in [a,b])$$

を満たすとする。このとき $g$ は $[a,b]$ にただ 1 つの不動点 $x^*$ をもち、任意の $x_0 \in [a,b]$ から $x_{k+1} = g(x_k)$ で作った列は $x^*$ に収束して、$k \ge 1$ について次が成り立つ。

1. （事前評価）$|x_k - x^*| \le \dfrac{L^k}{1-L}|x_1 - x_0|$。
2. （事後評価）$|x_k - x^*| \le \dfrac{L}{1-L}|x_k - x_{k-1}|$。
3. $|x_k - x^*| \le L^k |x_0 - x^*|$。

$g$ が $[a,b]$ で微分可能で $|g'(x)| \le L$ なら、上の Lipschitz 条件が成り立つ。

証明（定理 4.1）

$[a,b]$ は $\mathbb{R}$ の空でない閉集合で、$g$ はそれ自身への縮小率 $L$ の縮小写像です。縮小写像の原理（定理 3.2［逆関数定理・陰関数定理と条件付き極値］。$n = 1$ の場合）から、不動点がただ 1 つ存在し、列は $x^*$ に収束して 1 が成り立ちます（一般の完備距離空間での形は 定理 6.2［距離空間］）。

3 は $|x_{j+1} - x^*| = |g(x_j) - g(x^*)| \le L|x_j - x^*|$ を $j = 0, \ldots, k-1$ について繰り返せば得られます。

2 は三角不等式と 3 の 1 段分から

$$|x_k - x^*| \le |x_k - x_{k+1}| + |x_{k+1} - x^*| = |g(x_{k-1}) - g(x_k)| + |g(x_k) - g(x^*)| \le L|x_{k-1} - x_k| + L|x_k - x^*|$$

となり、$|x_k - x^*|$ について解けば得られます。

最後の主張は、$x \ne y$ について平均値の定理（定理 3.3［平均値の定理とテイラーの定理］）から $g(x) - g(y) = g'(c)(x - y)$ となる $c$ が $x$ と $y$ の間にあることから従います。

∎

事前評価は反復を始める前に必要な回数を見積もるのに、事後評価は計算しながら止めどきを決めるのに使います。事後評価の右辺は計算済みの量 $|x_k - x_{k-1}|$ だけで書けているので、「差が $\tau(1-L)/L$ 以下になったら止める」とすれば誤差は $\tau$ 以下に保証されます。ただし $L$ が $1$ に近いと係数 $L/(1-L)$ が大きくなり、差が小さくても誤差は小さいとは限りません。

例 4.2（x = cos x の不動点反復）

$g(x) = \cos x$ は $[0,1]$ を $[\cos 1, 1] \subset [0,1]$ に写し、$|g'(x)| = |\sin x| \le \sin 1 \approx 0.8415 = L$ です。定理 4.1 から不動点 $x^* \approx 0.739085$ がただ 1 つあり、$x_0 = 0$ から反復すると $x_1 = 1$ です。事前評価で誤差 $10^{-10}$ を保証するには $L^k/(1-L) \le 10^{-10}$、すなわち $k \ge 145$ 回が必要と見積もられます。実際に倍精度で反復すると、56 回目で誤差が $10^{-10}$ を下回ります。差が出るのは、$x^*$ の近くでの縮小率 $|g'(x^*)| = \sin x^* \approx 0.674$ が区間全体での最悪値 $0.8415$ より小さいためです。次の定理はこの「解の近くでの縮小率」を正確に述べます。

定理 4.3（不動点反復の局所収束と次数）✓

$I$ を開区間、$g : I \to \mathbb{R}$ を $C^1$ 級、$x^* \in I$ を $g(x^*) = x^*$ を満たす点とする。

1. $|g'(x^*)| \lt 1$ ならば $\delta \gt 0$ があって、$x_0 \in [x^* - \delta, x^* + \delta]$ から作った $x_{k+1} = g(x_k)$ はこの区間にとどまり、$x^*$ に収束する。さらにすべての $k$ で $e_k \ne 0$ なら $e_{k+1}/e_k \to g'(x^*)$ である。とくに $g'(x^*) \ne 0$ なら 1 次収束で、漸近誤差定数は $|g'(x^*)|$ である。
2. $p \ge 2$ とし、$g$ が $C^p$ 級で $g'(x^*) = \cdots = g^{(p-1)}(x^*) = 0$ ならば、1 の $\delta$ について、すべての $k$ で $e_k \ne 0$ のとき $$\frac{e_{k+1}}{e_k^p} \to \frac{g^{(p)}(x^*)}{p!}$$ である。とくに $g^{(p)}(x^*) \ne 0$ なら $p$ 次収束で、漸近誤差定数は $|g^{(p)}(x^*)|/p!$ である。

証明（定理 4.3）

1. $|g'(x^*)| \lt L \lt 1$ となる $L$ を取ります。$g'$ は $x^*$ で連続なので、$\delta \gt 0$ を小さく取れば $J = [x^* - \delta, x^* + \delta] \subset I$ かつ $J$ 上で $|g'| \le L$ にできます。$x \in J$、$x \ne x^*$ なら平均値の定理（定理 3.3［平均値の定理とテイラーの定理］）から $x$ と $x^*$ の間の $\eta$ があって

$$g(x) - x^* = g(x) - g(x^*) = g'(\eta)(x - x^*)$$

です。$\eta \in J$ なので $|g(x) - x^*| \le L|x - x^*| \le \delta$、すなわち $g(J) \subset J$ です。よって列は $J$ にとどまり、$|e_k| \le L^k |e_0| \to 0$ です。$e_k \ne 0$ のとき上の式で $x = x_k$ とすると $e_{k+1}/e_k = g'(\eta_k)$ で、$\eta_k$ は $x_k$ と $x^*$ の間にあるので $\eta_k \to x^*$ です。$g'$ の連続性から $g'(\eta_k) \to g'(x^*)$ です。

2. $g'(x^*) = 0$ なので 1 が適用でき、列は $J$ にとどまって $x^*$ に収束します。$e_k \ne 0$ のとき、Taylor の定理（定理 5.3［平均値の定理とテイラーの定理］。$a = x^*$、$n = p - 1$）を $x = x_k$ に使うと、$x_k$ と $x^*$ の間の $\xi_k$ があって

$$g(x_k) = g(x^*) + \sum_{j=1}^{p-1} \frac{g^{(j)}(x^*)}{j!} e_k^j + \frac{g^{(p)}(\xi_k)}{p!} e_k^p = x^* + \frac{g^{(p)}(\xi_k)}{p!} e_k^p$$

です。よって $e_{k+1}/e_k^p = g^{(p)}(\xi_k)/p!$ で、$\xi_k \to x^*$ と $g^{(p)}$ の連続性から主張を得ます。

∎

この定理は「反復関数の導関数が解で消えるほど速い」ことを述べています。Newton 法はちょうど $g'(x^*) = 0$ となるように $g$ を設計した反復と見ることができ、次の節の 2 次収束はその具体化です。

同じ方程式 $x = \cos x$ を 2 通りに書き直した反復で、$|g'(x^*)|$ が 1 より小さいか大きいかの違いを見ます。左は $g = \cos$ で、折れ線が不動点に巻き込むように近づきます。右は逆関数 $g = \arccos$ で、同じ不動点から離れていきます。

x = cos x の不動点 x* ≈ 0.7391（星印）に向かう反復。左は |g'(x*)| ≈ 0.674 で収束し、右は |g'(x*)| ≈ 1.484 で、初期値 0.70 が x* のすぐ近くでも離れていく。

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 乗で効くことが予想できます。

凸関数 f(x) = x² − 2 での Newton 法。x₀ = 2 での接線が x 軸と交わる点が x₁ = 1.5、x₁ での接線から x₂ ≈ 1.4167 が得られ、解 √2 ≈ 1.4142 に右から近づく。

次の定理は文字が多いですが、言っていることは 1 つです。解の近くの範囲 $J$ で、$m$ は $|f'|$ の最小値、$M$ は $|f''|$ の最大値、$K = M/(2m)$ はそこから決まる 1 つの定数です。$K\delta \lt 1$ は「範囲の幅が十分狭い」という条件で、これが成り立てば 1 回の反復で誤差が必ず小さくなり、2 乗の形で減っていきます。

定理 5.1（Newton 法の局所 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^*)|)$ である。

証明（定理 5.1）

$m$ と $M$ は、連続関数 $|f'|$、$|f''|$ の閉区間 $J$ 上の最小値・最大値として存在します（定理 2.3［平均値の定理とテイラーの定理］）。

1. $x_k \in J$ と仮定します。$|f'(x_k)| \ge m \gt 0$ なので $x_{k+1}$ は定義されます。$x_k = x^*$ なら $f(x_k) = 0$ で $x_{k+1} = x^*$ となり、以後の主張は自明です。$x_k \ne x^*$ なら、Taylor の定理（定理 5.3［平均値の定理とテイラーの定理］。$a = x_k$、$n = 1$）を $x = x^*$ に使うと、$x_k$ と $x^*$ の間の $\xi_k$ があって

$$0 = f(x^*) = f(x_k) + f'(x_k)(x^* - x_k) + \frac{f''(\xi_k)}{2}(x^* - x_k)^2$$

です。両辺を $f'(x_k)$ で割って整理すると

$$e_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} - x^* = \frac{f''(\xi_k)}{2f'(x_k)}\, e_k^2$$

を得ます。$\xi_k \in J$ なので $|e_{k+1}| \le K e_k^2 \le (K\delta)|e_k| \lt |e_k| \le \delta$ となり、$x_{k+1} \in J$ です。帰納法で列は $J$ にとどまり、$|e_{k+1}| \le K e_k^2$ がすべての $k$ で成り立ちます。両辺に $K$ を掛けると $K|e_{k+1}| \le (K|e_k|)^2$ で、これを繰り返すと $K|e_k| \le (K|e_0|)^{2^k}$ です。$K|e_0| \le K\delta \lt 1$ なので右辺は $0$ に収束します（$K = 0$ なら $e_1 = 0$ です）。$K \gt 0$ なら $A = 1/K$、$q = K\delta$ として R 次数 2 以上の定義（定義 2.2）を満たします。

2. $f'$ は $x^*$ で連続で $f'(x^*) \ne 0$ なので、$\delta_0 \gt 0$ を $J_0 = [x^* - \delta_0, x^* + \delta_0] \subset I$ かつ $J_0$ 上で $|f'| \ge |f'(x^*)|/2$ となるように取れます。$M_0 = \max_{J_0} |f''|$ とします。$0 \lt \delta \le \delta_0$ なら $m \ge |f'(x^*)|/2$、$M \le M_0$ なので $K \le M_0/|f'(x^*)|$ です。よって $\delta \lt |f'(x^*)|/M_0$（$M_0 = 0$ なら任意）かつ $\delta \le \delta_0$ と取れば $K\delta \lt 1$ です。

3. 1 の式から $e_{k+1}/e_k^2 = f''(\xi_k)/(2f'(x_k))$ です。$x_k \to x^*$ で、$\xi_k$ は $x_k$ と $x^*$ の間にあるので $\xi_k \to x^*$ です。$f'$、$f''$ の連続性と $f'(x^*) \ne 0$ から主張が従います。

∎

1 の評価は、解を知らなくても使える形にはなっていません（$J$ が解を中心にしているため）。それでも「$K|e_0| \lt 1$ なら収束し、正しい桁数がほぼ倍々に増える」という見通しを与え、$K$ が大きい（$f'$ が小さい、または $f''$ が大きい）ほど収束域が狭いことを教えます。解を含む球を計算だけで保証する形は、後の節の Kantorovich 型の定理（定理 7.4）で扱います。

例 5.2（√2 の Newton 法）

$f(x) = x^2 - 2$ では Newton 法は $x_{k+1} = (x_k + 2/x_k)/2$ です。定理 5.1 の 3 が予言する極限は $f''(x^*)/(2f'(x^*)) = 2/(4\sqrt2) = 1/(2\sqrt2) \approx 0.35355$ です。倍精度では誤差がすぐ丸めの水準（$10^{-16}$）で止まってしまうので、mpmath の 60 桁で反復して 2 次収束を最後まで追います。

# Python 3.12.10 / mpmath 1.3.0
from mpmath import mp, mpf, sqrt

mp.dps = 60                      # 10 進 60 桁で反復する
r = sqrt(mpf(2))                 # 参照値 √2
x, xd = mpf(2), 2.0              # x0 = 2（xd は倍精度で同じ反復）
ep = None
print(" k  e_k(60桁)  e_k/e_{k-1}^2  e_k(倍精度)")
for k in range(7):
    e, ed = abs(x - r), abs(mpf(xd) - r)
    q = f"{float(e / ep**2):.5f}" if ep else "   -   "
    print(f"{k:2d}  {float(e):.2e}    {q}      {float(ed):.2e}")
    ep = e
    x = x - (x * x - 2) / (2 * x)            # Newton 法
    xd = xd - (xd * xd - 2) / (2 * xd)
print("1/(2√2) =", f"{float(1 / (2 * r)):.5f}")

 k  e_k(60桁)  e_k/e_{k-1}^2  e_k(倍精度)
 0  5.86e-01       -         5.86e-01
 1  8.58e-02    0.25000      8.58e-02
 2  2.45e-03    0.33333      2.45e-03
 3  2.12e-06    0.35294      2.12e-06
 4  1.59e-12    0.35355      1.59e-12
 5  8.99e-25    0.35355      9.67e-17
 6  2.86e-49    0.35355      1.25e-16
1/(2√2) = 0.35355

検算. (a) この例では証明の式が閉じた形になり、$e_{k+1} = e_k^2/(2x_k)$ です。表の比 $0.25000 = 1/(2 \cdot 2)$、$0.33333 = 1/(2 \cdot 1.5)$ はちょうど $1/(2x_{k-1})$ に一致します。(b) 60 桁の計算と倍精度の計算は $k = 4$ まで表示の桁で一致し、倍精度は $k = 5$ 以降、$\sqrt2$ に最も近い倍精度数の誤差 $9.67 \times 10^{-17}$ の近くで止まります（この先は丸め誤差の問題で、Newton 法の収束の問題ではありません）。(c) 誤差の指数は $-1, -3, -6, -12, -25, -49$ とほぼ倍々に増え、比 $e_k/e_{k-1}^2$ は理論値 $1/(2\sqrt2)$ に近づきます。

定理 5.3（凸関数での Newton 法の単調な大域収束）✓

$I$ を区間、$f : I \to \mathbb{R}$ を微分可能で $f'$ が広義単調増加（$f$ が凸）な関数とし、$x^* \in I$ で $f(x^*) = 0$、$f'(x^*) \gt 0$ とする。$x_0 \in I$、$x_0 \gt x^*$ ならば、Newton 法の列は定義されて

$$x^* \le x_{k+1} \le x_k \qquad (k \ge 0)$$

を満たし、$x^*$ に収束する。

証明（定理 5.3）

$x_k \in I$、$x_k \gt x^*$ と仮定します。$f'$ は増加なので $f'(x_k) \ge f'(x^*) \gt 0$ で、$x_{k+1}$ は定義されます。平均値の定理（定理 3.3［平均値の定理とテイラーの定理］）から $f(x_k) = f(x_k) - f(x^*) = f'(c)(x_k - x^*)$ となる $c \in (x^*, x_k)$ があり、$0 \lt f'(x^*) \le f'(c) \le f'(x_k)$ です。よって

$$x_k - x_{k+1} = \frac{f(x_k)}{f'(x_k)} = \frac{f'(c)}{f'(x_k)}(x_k - x^*) \in (0,\, x_k - x^*]$$

で、$x^* \le x_{k+1} \lt x_k$ です。$x_{k+1} = x^*$ なら以後 $x_j = x^*$ で主張は自明です。そうでなければ $x_{k+1} \in (x^*, x_0] \subset I$ で同じ議論を繰り返せます。

列 $(-x_k)$ は単調増加で $-x^*$ で上に有界なので、単調有界定理（定理 2.1［級数と収束判定］）から $x_k$ はある $\ell \ge x^*$ に収束します。$f'(x_k)$ は $[f'(x^*), f'(x_0)]$ に入るので、$f(x_k) = (x_k - x_{k+1}) f'(x_k)$ から $|f(x_k)| \le f'(x_0)|x_k - x_{k+1}| \to 0$ です。$f$ は連続なので（定理 4.5［極限と連続性］）$f(\ell) = 0$ です。一方 $x \gt x^*$ なら上と同じく平均値の定理から $f(x) = f'(c)(x - x^*) \gt 0$ なので、$\ell = x^*$ です。

∎

$f(x) = x^2 - 2$ は凸で、$x_0 \gt \sqrt2$ ならどこから始めても単調に減少して $\sqrt2$ に収束します。$0 \lt x_0 \lt \sqrt2$ から始めても、1 回目で $x_1 = (x_0 + 2/x_0)/2 \ge \sqrt2$（相加相乗平均）となるので、2 回目以降はこの定理の状況に入ります。

5.1. 重根での Newton 法

$f'(x^*) = 0$ のとき、定理 5.1 は使えません。重根では Newton 法は収束はしますが、1 次収束に落ちます。

次の命題の $h$ は、解 $x^*$ を $m$ 回掛けて取り出した残りの部分です。$h(x^*) \ne 0$ なので、解の近くでは $f$ は $(x - x^*)^m$ とほぼ同じ形に振る舞います。たとえば $(x-1)^2$ なら $m = 2$、$h \equiv 1$ です。

命題 5.4（重根での Newton 法と修正 Newton 法）✓

$I$ を開区間、$x^* \in I$、$m \ge 2$ を整数とし、$f(x) = (x - x^*)^m h(x)$（$h : I \to \mathbb{R}$ は $C^1$ 級、$h(x^*) \ne 0$）とする。

1. $\delta \gt 0$ があって、$x_0 \in [x^* - \delta, x^* + \delta]$ から Newton 法の列は定義されて $x^*$ に収束し、すべての $k$ で $e_k \ne 0$ なら $e_{k+1}/e_k \to (m-1)/m$ である。すなわち 1 次収束で、漸近誤差定数は $(m-1)/m$ である。
2. 重複度 $m$ を掛けた修正 Newton 法 $x_{k+1} = x_k - m f(x_k)/f'(x_k)$ では、$\delta$ を小さく取り直せば列は $x^*$ に収束し、すべての $k$ で $e_k \ne 0$ なら $$\frac{e_{k+1}}{e_k^2} \to \frac{h'(x^*)}{m\, h(x^*)}$$ である。

証明（命題 5.4）

積の微分から $f'(x) = (x - x^*)^{m-1} D(x)$、$D(x) = m h(x) + (x - x^*) h'(x)$ です。$D$ は連続で $D(x^*) = m h(x^*) \ne 0$ なので、$\delta_0 \gt 0$ を $J_0 = [x^* - \delta_0, x^* + \delta_0] \subset I$ 上で $D$ も $h$ も $0$ にならないように取れます。このとき $x \in J_0$、$x \ne x^*$ で $f'(x) \ne 0$ であり、

$$\frac{f(x)}{f'(x)} = (x - x^*)\,\varphi(x), \qquad \varphi(x) = \frac{h(x)}{D(x)}$$

と書けます。$\varphi$ は $J_0$ 上連続で $\varphi(x^*) = 1/m$ です。

1. Newton 法では $e_{k+1} = e_k - e_k\varphi(x_k) = e_k(1 - \varphi(x_k))$ です（$e_k = 0$ なら止める）。$1 - \varphi$ は連続で $1 - \varphi(x^*) = (m-1)/m \lt 1$ なので、$(m-1)/m \lt L \lt 1$ を取り、$\delta \le \delta_0$ を $[x^* - \delta, x^* + \delta]$ 上で $|1 - \varphi| \le L$ となるように取れます。すると $|e_{k+1}| \le L|e_k|$ で列はこの区間にとどまり、$e_k \to 0$ です。さらに $e_{k+1}/e_k = 1 - \varphi(x_k) \to 1 - 1/m$ です。

2. 修正 Newton 法では $e_{k+1} = e_k(1 - m\varphi(x_k))$ で、

$$1 - m\varphi(x) = \frac{D(x) - m h(x)}{D(x)} = \frac{(x - x^*)\, h'(x)}{D(x)}$$

です。よって $e_{k+1} = e_k^2\, h'(x_k)/D(x_k)$ です。$\psi = h'/D$ は $J_0$ 上連続なので $|\psi| \le N$ と有界です（定理 2.3［平均値の定理とテイラーの定理］）。$\delta \le \delta_0$ を $N\delta \lt 1$ となるように取れば、$|e_{k+1}| \le N\delta|e_k|$ で列は区間にとどまり $e_k \to 0$ です。最後に $e_{k+1}/e_k^2 = \psi(x_k) \to h'(x^*)/D(x^*) = h'(x^*)/(m h(x^*))$ です。

∎

例 5.5（(x − 1)² での遅い収束）

$f(x) = (x-1)^2$ では Newton 法は $x_{k+1} = x_k - (x_k - 1)/2$、すなわち $e_{k+1} = e_k/2$ です。誤差は 1 回で半分にしかならず、二分法と同じ速さです。命題 5.4 の比 $(m-1)/m = 1/2$ がちょうど実現しています。修正 Newton 法 $x_{k+1} = x_k - 2f(x_k)/f'(x_k)$ では 1 回で $x_1 = 1$ に到達します（$h \equiv 1$ で $h' = 0$）。実際の問題では重複度 $m$ は未知のことが多く、$e_{k+1}/e_k$ の観測値から $m$ を推定するか、$f/f'$（単根しかもたない）に Newton 法を使う工夫をします。

重根は収束が遅いだけでなく、達成できる精度そのものが低い根でもあります。$f$ の値の計算に含まれる誤差を $f$ に加わる小さな摂動 $\varepsilon q$ とみなすと、多項式の単根は 1 次で $-\varepsilon q(x^*)/f'(x^*)$ だけ動きます（命題 3.1［条件数と安定性］）。$|f'(x^*)|$ が小さい根、つまり重根に近い根ほど、反復法をどう選んでも計算できる桁数は少なくなります。これは算法ではなく問題の性質（条件数）で、条件数と安定性の章で扱います。

例 5.6（周期軌道に入る Newton 法）

$f(x) = x^3 - 2x + 2$ に $x_0 = 0$ から Newton 法を使います。$f(0) = 2$、$f'(0) = -2$ なので $x_1 = 1$、$f(1) = 1$、$f'(1) = 1$ なので $x_2 = 0$ です。列は $0, 1, 0, 1, \ldots$ と周期 2 で回り続け、実数解 $x^* \approx -1.769$ には近づきません。$f'$ は $\pm\sqrt{2/3}$ で $0$ になり、その間では接線が大きく外れた点に飛ばします。局所収束の定理の「解の十分近くから始めれば」という仮定は飾りではなく、実用では二分法で区間を絞ってから Newton 法に切り替える、減速（$x_{k+1} = x_k - \lambda_k f(x_k)/f'(x_k)$、$0 \lt \lambda_k \le 1$）を入れる、などの対策をとります。

6. 割線法

Newton 法は毎回 $f'(x_k)$ を必要とします。導関数の式がない、あるいは計算が高くつくときは、接線の傾きを直前の 2 点を結ぶ直線の傾きで置き換えます。これが割線法

$$x_{k+1} = x_k - f(x_k)\,\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}$$

です。1 回の反復で新しく計算する関数値は $f(x_k)$ の 1 つだけです。解析には差分商を使います。$f[a,b]$ は 2 点 $a, b$ を結ぶ線分の傾き、$f[a,b,c]$ はその傾きの変化の割合で、導関数と 2 階導関数の「差分版」です。相異なる点 $a, b, c$ について

$$f[a,b] = \frac{f(b) - f(a)}{b - a}, \qquad f[a,b,c] = \frac{f[a,b] - f[b,c]}{a - c}$$

と書きます。定義から $f[a,b] = f[b,a]$ です。割線法は $x_{k+1} = x_k - f(x_k)/f[x_{k-1}, x_k]$ と書けます。

次の補題のねらいは、割線法の誤差の式に出てくる差分商を、導関数の値に置き換えることです。1 つ目は平均値の定理の言い換えで、2 つ目は 3 点を通る 2 次式を作り、Rolle の定理を 2 回使って示します。

補題 6.1（2 階の差分商の平均値定理）✓

$I$ を開区間、$f : I \to \mathbb{R}$ を 2 回微分可能とし、$a, b, c \in I$ を相異なる点とする。このとき $a$ と $b$ の間の $\eta$ と、$a, b, c$ の最小値と最大値の間の $\xi$ があって

$$f[a,b] = f'(\eta), \qquad f[a,b,c] = \frac{f''(\xi)}{2}$$

が成り立つ。

証明（補題 6.1）

1 つ目は平均値の定理（定理 3.3［平均値の定理とテイラーの定理］）そのものです。2 つ目のために 2 次式

$$p(x) = f(a) + f[a,b](x - a) + f[a,b,c](x - a)(x - b)$$

を考えます。$p(a) = f(a)$、$p(b) = f(a) + f[a,b](b-a) = f(b)$ です。また定義から $f[a,b,c](c - a) = f[b,c] - f[a,b]$ なので

$$f[a,b,c](c-a)(c-b) = \bigl(f[b,c] - f[a,b]\bigr)(c - b) = f(c) - f(b) - f[a,b](c - b)$$

となり、$p(c) = f(a) + f[a,b](c - a) + f(c) - f(b) - f[a,b](c-b) = f(a) + f[a,b](b - a) + f(c) - f(b) = f(c)$ です。

$g = f - p$ は $I$ 上 2 回微分可能で、3 点 $a, b, c$ で $0$ になります。3 点を小さい順に $t_1 \lt t_2 \lt t_3$ とすると、Rolle の定理（定理 3.1［平均値の定理とテイラーの定理］）を $[t_1, t_2]$ と $[t_2, t_3]$ に使って $g'(s_1) = g'(s_2) = 0$ となる $t_1 \lt s_1 \lt t_2 \lt s_2 \lt t_3$ を得ます。$g'$ は微分可能なので連続で、もう一度 Rolle の定理を $[s_1, s_2]$ に使うと $g''(\xi) = 0$ となる $\xi \in (s_1, s_2) \subset (t_1, t_3)$ があります。$p'' = 2f[a,b,c]$ なので $f''(\xi) = 2f[a,b,c]$ です。

∎

一般の $n$ 階の差分商についての同じ形の定理は、多項式補間の章で補間多項式を使って示します。ここでは割線法に必要な 2 階の場合だけを使います。

定理 6.2（割線法の局所収束）✓

$I$ を開区間、$f : I \to \mathbb{R}$ を $C^2$ 級とし、$x^* \in I$ で $f(x^*) = 0$、$f'(x^*) \ne 0$ とする。$\delta \gt 0$ が $J = [x^* - \delta, x^* + \delta] \subset I$ と $m = \min_J |f'| \gt 0$ を満たし、$M = \max_J |f''|$ に対して $K \ge M/(2m)$ かつ $K\delta \lt 1$ とする（このような $\delta$ と $K$ は存在する）。相異なる $x_0, x_1 \in J$ から割線法を始め、$f(x_k) = 0$ となったら止める。このとき

1. 列は定義されて $J$ にとどまり、$|e_{k+1}| \le K|e_k||e_{k-1}|$ を満たして $x^*$ に収束する。
2. 止まらないならば、 $$\frac{e_{k+1}}{e_k\, e_{k-1}} \to \frac{f''(x^*)}{2f'(x^*)}$$ である。

証明（定理 6.2）

$\delta$ と $K$ の存在は、定理 5.1 の 2 と同じ議論で $\delta$ を取り、$K = M/(2m)$ とすれば得られます。

1. $x_{k-1}, x_k \in J$ が相異なり、$f(x_{k-1}) \ne 0$、$f(x_k) \ne 0$ と仮定します（$k = 1$ では仮定どおりで、止まっていなければ以下で帰納的に保たれます）。補題 6.1 から $f[x_{k-1}, x_k] = f'(\eta)$（$\eta \in J$）で、$|f'(\eta)| \ge m \gt 0$ なので $x_{k+1}$ は定義されます。$f(x_k) = f(x_k) - f(x^*) = f[x_k, x^*]\, e_k$ なので

$$e_{k+1} = e_k - \frac{f[x_k, x^*]}{f[x_{k-1}, x_k]}\, e_k = e_k\,\frac{f[x_{k-1}, x_k] - f[x_k, x^*]}{f[x_{k-1}, x_k]} = e_k\, e_{k-1}\,\frac{f[x_{k-1}, x_k, x^*]}{f[x_{k-1}, x_k]}$$

です。最後の等号は 2 階の差分商の定義そのものです（3 点 $x_{k-1}, x_k, x^*$ は相異なります。$f(x_{k-1}) \ne 0$、$f(x_k) \ne 0$ だからです）。補題 6.1 から分子は $f''(\xi_k)/2$（$\xi_k \in J$）なので、$|e_{k+1}| \le \frac{M}{2m}|e_k||e_{k-1}| \le K|e_k||e_{k-1}|$ です。$|e_{k-1}| \le \delta$ なので $|e_{k+1}| \le K\delta|e_k| \lt |e_k|$ で、$x_{k+1} \in J$ です。さらに $x_{k+1} = x_k$ となるのは $f(x_k) = 0$ のときだけなので、$x_k \ne x_{k+1}$ です。帰納法ですべての段で成り立ち、$|e_{k+1}| \le (K\delta)^k |e_1| \to 0$ です。

2. 1 の式から $e_{k+1}/(e_k e_{k-1}) = f''(\xi_k)/(2f'(\eta_k))$ です。$\eta_k$ と $\xi_k$ はいずれも $x_{k-1}, x_k, x^*$ の最小値と最大値の間にあるので $x^*$ に収束し、$f'$、$f''$ の連続性から主張が従います。

∎

系 6.3（割線法の R 次数は黄金比以上）✓

定理 6.2 の状況で割線法が止まらないならば、$\varphi = (1 + \sqrt5)/2$ について、列は R 次数 $\varphi$ 以上で $x^*$ に収束する。

証明の方針は、$d_{k+1} \le d_k d_{k-1}$ という「前の 2 回の積」の形の不等式から、指数がどう増えるかを調べることです。指数が $\varphi^k$ のとき、$\varphi^k + \varphi^{k-1} = \varphi^{k+1}$ となって指数の足し算がぴったり合います。これが黄金比が出てくる理由で、$q$ の取り方は最初の 2 項でこの形を満たすためのものです。

証明（系 6.3）

$\tilde K = \max(K, 1/(2\delta))$ とおくと $\tilde K \gt 0$、$\tilde K\delta \lt 1$ で、定理 6.2 の 1 の不等式は $K$ を $\tilde K$ に替えても成り立ちます。$d_k = \tilde K|e_k|$ とおくと $d_{k+1} \le d_k d_{k-1}$、$0 \lt d_k \le \tilde K\delta \lt 1$ です。$q = \max(d_0, d_1^{1/\varphi})$ とすると $0 \lt q \lt 1$ で、$d_0 \le q = q^{\varphi^0}$、$d_1 \le q^{\varphi}$ です。$d_{k-1} \le q^{\varphi^{k-1}}$、$d_k \le q^{\varphi^k}$ なら、$\varphi^2 = \varphi + 1$ を使って

$$d_{k+1} \le q^{\varphi^k + \varphi^{k-1}} = q^{\varphi^{k-1}(\varphi + 1)} = q^{\varphi^{k+1}}$$

です。帰納法で $|e_k| \le \tilde K^{-1} q^{\varphi^k}$ がすべての $k$ で成り立ち、R 次数 $\varphi$ 以上の定義（定義 2.2）を満たします。

∎

1 回あたりの関数値の計算が Newton 法では $f$ と $f'$ の 2 回、割線法では $f$ の 1 回です。$f'$ の計算が $f$ と同じ手間なら、割線法の 2 回分（次数 $\varphi^2 \approx 2.618$）は Newton 法の 1 回分（次数 2）より速いことになります。

注意 6.4（割線法の Q 次数）

$f''(x^*) \ne 0$ なら、$C = |f''(x^*)/(2f'(x^*))|$ として $|e_{k+1}|/|e_k|^{\varphi} \to C^{\varphi - 1}$ が成り立ち、割線法は Q 次数の意味でもちょうど $\varphi$ 次収束します。定理 6.2 の 2 の漸化式の対数をとって線形差分方程式として解析する証明が知られています（Atkinson『An Introduction to Numerical Analysis』第 2 章の割線法の節、Ortega–Rheinboldt『Iterative Solution of Nonlinear Equations in Several Variables』の収束の速さを扱う章）。本章では R 次数の評価だけを使います。

例 6.5（割線法の次数を誤差から推定する）

$f(x) = x^2 - 2$、$x_0 = 2$、$x_1 = 1.5$ から割線法を mpmath の 300 桁で回し、誤差の比から次数を $p_k = \log(e_k/e_{k-1})/\log(e_{k-1}/e_{k-2})$ で推定します。

# Python 3.12.10 / mpmath 1.3.0
from mpmath import mp, mpf, sqrt, log

mp.dps = 300                     # 誤差が 1e-250 程度まで追えるように
f = lambda x: x * x - 2
r = sqrt(mpf(2))
xs = [mpf(2), mpf("1.5")]        # x0, x1
for k in range(10):              # 割線法
    a, b = xs[-2], xs[-1]
    xs.append(b - f(b) * (b - a) / (f(b) - f(a)))
e = [abs(x - r) for x in xs]
C = 2 / (2 * 2 * r)              # f''(x*)/(2 f'(x*)) = 1/(2√2)
print(" k   e_k        e_k/(e_{k-1}e_{k-2})  推定次数")
for k in range(2, len(e)):
    q = e[k] / (e[k - 1] * e[k - 2])
    p = log(e[k] / e[k - 1]) / log(e[k - 1] / e[k - 2])
    s = f"{float(e[k]):.2e}".ljust(10)
    print(f"{k:2d}  {s} {float(q):.5f}            {float(p):.4f}")
print(f"1/(2√2) = {float(C):.5f}, 黄金比 = {float((1+sqrt(5))/2):.4f}")

 k   e_k        e_k/(e_{k-1}e_{k-2})  推定次数
 2  1.44e-02   0.28571            0.9305
 3  4.21e-04   0.34146            1.9750
 4  2.12e-06   0.35172            1.4980
 5  3.16e-10   0.35350            1.6666
 6  2.37e-16   0.35355            1.6000
 7  2.65e-26   0.35355            1.6250
 8  2.22e-42   0.35355            1.6154
 9  2.08e-68   0.35355            1.6190
10  1.63e-110  0.35355            1.6176
11  1.20e-178  0.35355            1.6182
1/(2√2) = 0.35355, 黄金比 = 1.6180

検算. (a) 極限値 $1/(2\sqrt2)$ は Newton 法の例と同じ $f''(x^*)/(2f'(x^*))$ で、表の第 3 列はそこに収束します（定理 6.2 の 2）。(b) $x^2 - 2$ では $f[a,b] = a + b$、$f[a,b,c] = 1$ なので、証明の式は $e_{k+1} = e_k e_{k-1}/(x_{k-1} + x_k)$ と閉じた形になり、第 3 列は $1/(x_{k-2} + x_{k-1})$ に等しくなります（$k = 2$ で $1/3.5 = 0.28571$）。(c) 推定次数は $1.5, 1.667, 1.6, 1.625, 1.615, \ldots$ と黄金比 $1.618$ のまわりを振動しながら近づきます。これは誤差の指数が Fibonacci 数列に似た漸化式 $\log e_{k+1} \approx \log e_k + \log e_{k-1}$ に従うためで、連続する Fibonacci 数の比が黄金比に近づく様子と同じです。

注意 6.6（Brent 法）

実用の 1 変数の求根では、符号の変わる区間を保ちながら、割線法や逆 2 次補間（3 点を通る $x$ の 2 次式で $f = 0$ となる点を求める）の候補が区間の中に入り十分に縮むときはそれを採用し、そうでなければ二分法の 1 歩に戻る、という組み合わせ（Dekker 法・Brent 法）が標準です。二分法と同じく収束は保証され、解の近くでは超 1 次収束します。SciPy の brentq はこの算法です。正確な規則と、関数値の評価回数が最悪でも二分法の回数の 2 乗程度で済むことの証明は、R. P. Brent『Algorithms for Minimization without Derivatives』（Prentice-Hall, 1973）第 4 章にあります。

7. 多変数の Newton 法と Kantorovich 型の定理

$U \subset \mathbb{R}^n$ を開集合、$F : U \to \mathbb{R}^n$ を全微分可能な写像とし、ヤコビ行列を $J(x) = J_F(x)$ と書きます。$\mathbb{R}^n$ にはユークリッドノルム $\|\cdot\|$、行列には作用素ノルム $\|A\| = \sup\{\|Ax\| : \|x\| \le 1\}$ を使います（多変数関数の微分と同じ記法です）。閉球を $\bar B(a, r) = \{x : \|x - a\| \le r\}$、開球を $B(a, r)$ と書きます。多変数の Newton 法は

$$x_{k+1} = x_k - J(x_k)^{-1} F(x_k)$$

です。実際の計算では逆行列を作らず、連立 1 次方程式 $J(x_k)\, d_k = -F(x_k)$ を解いて $x_{k+1} = x_k + d_k$ とします。証明の道具を 2 つ用意します。

補題 7.1（逆行列の摂動）✓

$A, B$ を $n$ 次の実正方行列とし、$A$ は正則で $\|A^{-1}(B - A)\| \le q \lt 1$ とする。このとき $B$ は正則で

$$\|B^{-1}\| \le \frac{\|A^{-1}\|}{1 - q}$$

である。

証明（補題 7.1）

$Bx = 0$ とすると $0 = A^{-1}Bx = x + A^{-1}(B - A)x$ なので $\|x\| = \|A^{-1}(B - A)x\| \le q\|x\|$ で、$q \lt 1$ から $x = 0$ です。斉次方程式が自明な解しかもたないので、正則性の判定（定理 7.1［行列式とその性質］ の 4 ⇒ 2）から $B$ は正則です。任意の $y$ について $x = B^{-1}y$ とおくと、上と同じ変形で $x = A^{-1}y - A^{-1}(B - A)x$ なので

$$\|x\| \le \|A^{-1}\|\,\|y\| + q\|x\|, \qquad \|B^{-1}y\| = \|x\| \le \frac{\|A^{-1}\|}{1 - q}\|y\|$$

です。$\|y\| \le 1$ について上限をとれば主張を得ます。

∎

これは Banach 空間でのノイマン級数（定理 6.1［有界作用素と共役作用素］）による評価の、有限次元での形です。有限次元では単射と全射が同値なので、級数を使わずに示せます。

次の補題は、多変数の場合に「1 次式で近似した誤差は距離の 2 乗程度」と言うためのものです。証明では、ベクトル値の量を $v$ の向きの単位ベクトル $w$ との内積で 1 つの実数にして、1 変数の単調性の議論に持ち込みます。

補題 7.2（1 次近似の剰余の評価）✓

$U \subset \mathbb{R}^n$ を開集合、$F : U \to \mathbb{R}^n$ を全微分可能、$a, b \in U$ を結ぶ線分 $[a, b]$ が $U$ に含まれるとする。$\gamma \ge 0$ について、線分上のすべての点 $z$ で $\|J(z) - J(a)\| \le \gamma\|z - a\|$ ならば

$$\|F(b) - F(a) - J(a)(b - a)\| \le \frac{\gamma}{2}\|b - a\|^2$$

である。

証明（補題 7.2）

$v = F(b) - F(a) - J(a)(b - a)$ とし、$v \ne 0$ としてよいとします。$w = v/\|v\|$ とおきます。$V = \{s \in \mathbb{R} : a + s(b - a) \in U\}$ は開集合 $U$ の連続写像による逆像なので開集合で、$[0,1]$ を含みます。$V$ 上の実数値関数

$$\phi(s) = w^{\mathsf{T}}\bigl(F(a + s(b - a)) - s\,J(a)(b - a)\bigr)$$

は、連鎖律（定理 9.4［多変数関数の微分と偏微分］）から微分可能で、$z_s = a + s(b-a)$ とおくと $\phi'(s) = w^{\mathsf{T}}\bigl(J(z_s) - J(a)\bigr)(b - a)$ です。$s \in [0,1]$ では、コーシー・シュワルツの不等式（定理 4.2［内積空間とグラム・シュミット直交化］）と $\|w\| = 1$、$\|z_s - a\| = s\|b - a\|$ から

$$|\phi'(s)| \le \|J(z_s) - J(a)\|\,\|b - a\| \le \gamma s \|b - a\|^2$$

です。$c = \gamma\|b - a\|^2$ とし、$\psi(s) = \phi(s) - c s^2/2$ とおくと $[0,1]$ 上で $\psi'(s) = \phi'(s) - cs \le 0$ なので、導関数の符号と単調性（系 3.4［平均値の定理とテイラーの定理］。$-\psi$ に適用）から $\psi(1) \le \psi(0)$、すなわち $\phi(1) - \phi(0) \le c/2$ です。一方 $\phi(1) - \phi(0) = w^{\mathsf{T}} v = \|v\|$ なので、$\|v\| \le c/2$ です。

∎

平均値不等式（定理 9.7［多変数関数の微分と偏微分］）をそのまま使うと係数は $\gamma$ になり、$1/2$ が出ません。この $1/2$ が、Kantorovich 型の定理の条件 $h \lt 1/2$ の $1/2$ の出どころです。

定理 7.3（多変数の Newton 法の局所 2 次収束）✓

$U \subset \mathbb{R}^n$ を開集合、$F : U \to \mathbb{R}^n$ を全微分可能、$x^* \in U$ で $F(x^*) = 0$、$J(x^*)$ は正則とし、$\beta = \|J(x^*)^{-1}\|$ とおく。$r \gt 0$ と $\gamma \gt 0$ が $\bar B(x^*, r) \subset U$ と

$$\|J(x) - J(y)\| \le \gamma\|x - y\| \qquad (x, y \in \bar B(x^*, r))$$

を満たすとし、$\rho = \min(r, 1/(2\beta\gamma))$ とする。このとき $\|x_0 - x^*\| \le \rho$ なら Newton 法の列は定義されて $\bar B(x^*, \rho)$ にとどまり、$e_k = x_k - x^*$ について

$$\|e_{k+1}\| \le \beta\gamma\|e_k\|^2, \qquad \beta\gamma\|e_k\| \le (\beta\gamma\|e_0\|)^{2^k} \le 2^{-2^k}$$

が成り立つ。とくに $x_k \to x^*$ である。

証明（定理 7.3）

$\|e_k\| \le \rho$ と仮定します。$\|J(x^*)^{-1}(J(x_k) - J(x^*))\| \le \beta\gamma\|e_k\| \le 1/2$ なので、補題 7.1（$A = J(x^*)$、$B = J(x_k)$、$q = 1/2$）から $J(x_k)$ は正則で $\|J(x_k)^{-1}\| \le 2\beta$ です。$F(x^*) = 0$ を使うと

$$e_{k+1} = x_k - x^* - J(x_k)^{-1}F(x_k) = J(x_k)^{-1}\bigl[F(x^*) - F(x_k) - J(x_k)(x^* - x_k)\bigr]$$

です。閉球は凸なので線分 $[x_k, x^*]$ は $\bar B(x^*, r)$ に含まれ、その上で $\|J(z) - J(x_k)\| \le \gamma\|z - x_k\|$ です。補題 7.2（$a = x_k$、$b = x^*$）から括弧の中のノルムは $(\gamma/2)\|e_k\|^2$ 以下なので、

$$\|e_{k+1}\| \le 2\beta \cdot \frac{\gamma}{2}\|e_k\|^2 = \beta\gamma\|e_k\|^2 \le \beta\gamma\rho\,\|e_k\| \le \frac12\|e_k\|$$

です。よって $x_{k+1} \in \bar B(x^*, \rho)$ で、帰納法ですべての $k$ で成り立ちます。$\beta\gamma\|e_{k+1}\| \le (\beta\gamma\|e_k\|)^2$ を繰り返せば 2 つ目の不等式を得ます。

∎

この定理も解 $x^*$ を中心に述べているので、解が存在することは前提です。次の定理は、解を知らないまま、初期値 $x_0$ で計算できる 3 つの量 $\beta, \eta, \gamma$ から、解の存在と一意性と、解を含む球の半径を結論します。

定理 7.4（Kantorovich 型の存在と一意性（簡易 Newton 法））✓

$U \subset \mathbb{R}^n$ を開集合、$F : U \to \mathbb{R}^n$ を全微分可能、$x_0 \in U$ で $J_0 = J(x_0)$ は正則とする。正の数 $\beta, \eta, \gamma, R$ が

$$\|J_0^{-1}\| \le \beta, \qquad \|J_0^{-1}F(x_0)\| \le \eta, \qquad \|J(x) - J_0\| \le \gamma\|x - x_0\| \quad (x \in \bar B(x_0, R))$$

と $\bar B(x_0, R) \subset U$ を満たすとし、$L = \beta\gamma$、$h = L\eta$ とおく。$h \lt 1/2$ かつ

$$t_- = \frac{1 - \sqrt{1 - 2h}}{L} \le R$$

ならば次が成り立つ。

1. $F$ は $\bar B(x_0, t_-)$ に零点 $x^*$ をもち、$\bar B(x_0, t_-)$ の中の零点はそれだけである。
2. 簡易 Newton 法 $x_{k+1} = x_k - J_0^{-1}F(x_k)$ の列は $\bar B(x_0, t_-)$ にとどまって $x^*$ に収束し、$q = L t_- = 1 - \sqrt{1 - 2h} \lt 1$ について $\|x_k - x^*\| \le q^k\eta/(1 - q)$ である。
3. $F$ は開球 $B(x_0, \min(R, 1/L))$ の中に $x^*$ 以外の零点をもたない。

証明（定理 7.4）

$T(x) = x - J_0^{-1}F(x)$ とおきます。$J_0^{-1}$ は正則なので、$T(x) = x$ と $F(x) = 0$ は同値です。

縮小性. $0 \lt t \le R$ とします。$T$ は全微分可能で $J_T(z) = I - J_0^{-1}J(z) = J_0^{-1}(J_0 - J(z))$ なので、$z \in \bar B(x_0, t)$ で $\|J_T(z)\| \le \beta\gamma\|z - x_0\| \le Lt$ です。$x, y \in \bar B(x_0, t)$ を結ぶ線分は閉球に含まれるので、平均値不等式（定理 9.7［多変数関数の微分と偏微分］）から

$$\|T(x) - T(y)\| \le Lt\,\|x - y\|$$

です。

閉球を自分自身に写すこと. $x \in \bar B(x_0, t)$ について

$$T(x) - x_0 = -J_0^{-1}\bigl[F(x) - F(x_0) - J_0(x - x_0)\bigr] - J_0^{-1}F(x_0)$$

です。仮定から線分 $[x_0, x]$ 上で $\|J(z) - J_0\| \le \gamma\|z - x_0\|$ なので、補題 7.2（$a = x_0$、$b = x$）から

$$\|T(x) - x_0\| \le \beta\cdot\frac{\gamma}{2}\|x - x_0\|^2 + \eta \le \frac{L}{2}t^2 + \eta$$

です。$t_-$ は 2 次方程式 $\frac{L}{2}t^2 - t + \eta = 0$ の小さいほうの根（$h \lt 1/2$ なので実根）なので、$t = t_-$ のとき右辺はちょうど $t_-$ です。よって $T$ は $\bar B(x_0, t_-)$ を自分自身に写します。

1・2. $\bar B(x_0, t_-)$ は $\mathbb{R}^n$ の空でない閉集合で、$T$ はそこで縮小率 $q = Lt_- = 1 - \sqrt{1 - 2h}$ の縮小写像です。$h \lt 1/2$ から $q \lt 1$ です。縮小写像の原理（定理 3.2［逆関数定理・陰関数定理と条件付き極値］）から $T$ は $\bar B(x_0, t_-)$ にただ 1 つの不動点 $x^*$ をもち、簡易 Newton 法の列（$T$ の反復そのもの）はそこに収束して $\|x_k - x^*\| \le q^k\|x_1 - x_0\|/(1-q)$ です。$\|x_1 - x_0\| = \|J_0^{-1}F(x_0)\| \le \eta$ から 2 の評価を得ます。不動点の一意性は、この閉球の中の零点の一意性です。

3. $y$ を $\|y - x_0\| \lt \min(R, 1/L)$ を満たす零点とし、$t = \max(\|y - x_0\|, t_-)$ とおきます。$t_- \le R$ と $Lt_- = q \lt 1$ から $t \le R$、$Lt \lt 1$ です。$x^*$ と $y$ はともに $\bar B(x_0, t)$ の中の $T$ の不動点なので、縮小性から $\|x^* - y\| = \|T(x^*) - T(y)\| \le Lt\|x^* - y\|$ となり、$x^* = y$ です。

∎

条件 $h = \beta\gamma\eta \lt 1/2$ は、「初期値での Newton 補正の大きさ $\eta$」が「ヤコビ行列の変化の速さ $\gamma$」と「ヤコビ行列の逆の大きさ $\beta$」に比べて十分小さい、という意味です。左辺の 3 つの量はすべて $x_0$ と $F$ の情報から計算でき、とくに区間演算で上界を計算すれば、計算機の出力がそのまま「この球の中に解がただ 1 つある」ことの証明になります。

Kantorovich 型の定理の状況（模式図）。初期値 x₀ を中心とする半径 t₋ の閉球の中に零点 x* があり、より大きい開球（半径 min(R, 1/L)）の中では零点は x* だけである。

注意 7.5（Kantorovich の定理の完全な形）

本章で証明したのは簡易 Newton 法（ヤコビ行列を $J_0$ に固定）が縮小写像になる形です。L. V. Kantorovich による元の定理は、同じ $\beta, \eta$ と、$x_0$ を中心とする条件より強い球の中での Lipschitz 条件 $\|J(x) - J(y)\| \le \gamma\|x - y\|$（$x, y \in \bar B(x_0, R)$）を満たす $\gamma$ について、$h \le 1/2$ のもとで、Newton 法そのものの列が定義されて $\bar B(x_0, t_-)$ の中の零点に収束し、$h \lt 1/2$ なら 2 次収束することを述べます。証明は Newton 法の列を 1 変数の多項式 $\frac{L}{2}t^2 - t + \eta$ に Newton 法を使った列で上から抑える「優級数」の議論で、不等式の帰納法が 2〜3 頁続きます。J. M. Ortega, W. C. Rheinboldt『Iterative Solution of Nonlinear Equations in Several Variables』（Academic Press, 1970）§12.6、P. Deuflhard『Newton Methods for Nonlinear Problems』（Springer, 2004）第 2 章を参照してください。ここでは定理環境にせず、後の章の証明でも使いません。

8. 演習

演習 8.1易

$f$ が $[1, 2]$ で連続、$f(1) f(2) \lt 0$ とします。二分法の中点 $c_k$ の誤差が $10^{-6}$ 以下であることが定理 3.1から保証される最小の $k$ を求めてください。

解答

誤差の上界は $(2 - 1)/2^{k+1} = 2^{-(k+1)}$ です。$2^{-(k+1)} \le 10^{-6}$ は $k + 1 \ge 6\log_2 10 \approx 19.93$、すなわち $k \ge 19$ と同値です。よって $k = 19$ で、$c_0, \ldots, c_{19}$ の 20 回の関数値の計算で保証されます。

演習 8.2標準

$a \gt 0$ とします。$f(x) = 1/x - a$ に Newton 法を使うと $x_{k+1} = x_k(2 - a x_k)$ となり、割り算なしで $1/a$ を計算できることを確かめてください。さらに $r_k = 1 - a x_k$ とおいて $r_{k+1} = r_k^2$ を示し、列が $1/a$ に収束するための $x_0$ の必要十分条件と、$e_{k+1}/e_k^2$ の値を求めてください。

解答

$f'(x) = -1/x^2$ なので $x_{k+1} = x_k + x_k^2(1/x_k - a) = x_k(2 - a x_k)$ です。$r_{k+1} = 1 - a x_k(2 - a x_k) = 1 - 2a x_k + a^2 x_k^2 = (1 - a x_k)^2 = r_k^2$ なので $r_k = r_0^{2^k}$ です。$x_k \to 1/a$ は $r_k \to 0$ と同値で、それは $|r_0| \lt 1$、すなわち $0 \lt x_0 \lt 2/a$ と同値です（$|r_0| = 1$ なら $r_k = 1$ で $x_k = 0$ にとどまり、$|r_0| \gt 1$ なら $|r_k| \to \infty$ です）。$e_k = x_k - 1/a = -r_k/a$ なので $e_{k+1} = -r_k^2/a = -a e_k^2$、すなわち $e_{k+1}/e_k^2 = -a$ です。これは 定理 5.1 の極限 $f''(x^*)/(2f'(x^*)) = (2a^3)/(2 \cdot (-a^2)) = -a$ と一致します。

演習 8.3標準

$a \gt 0$ とし、$g(x) = x(x^2 + 3a)/(3x^2 + a)$ とします。$g(\sqrt a) = \sqrt a$ と

$$g(x) - \sqrt a = \frac{(x - \sqrt a)^3}{3x^2 + a}$$

を示し、$x_0$ が $\sqrt a$ に十分近いとき不動点反復が 3 次収束することと、漸近誤差定数を求めてください。

解答

$s = \sqrt a$ とおくと $(x - s)^3 = x^3 - 3sx^2 + 3ax - as$ です。一方 $g(x) - s = \bigl(x^3 + 3ax - s(3x^2 + a)\bigr)/(3x^2 + a) = (x^3 - 3sx^2 + 3ax - as)/(3x^2 + a)$ なので等式が成り立ち、とくに $g(s) = s$ です。$e_k \ne 0$ なら $e_{k+1}/e_k^3 = 1/(3x_k^2 + a)$ です。$g$ は $x \gt 0$ で $C^1$ 級で、等式から $g'(s) = 0$ なので、定理 4.3 の 1 により $s$ の近くから始めた列は $s$ に収束します。よって $e_{k+1}/e_k^3 \to 1/(3a + a) = 1/(4a)$ で、3 次収束、漸近誤差定数は $1/(4a)$ です（定理 4.3 の 2 で $p = 3$ としても同じ結論で、$g'''(s)/3! = 1/(4a)$ です）。

演習 8.4難

$F(x, y) = (x^2 + y^2 - 1,\ x - y)$ とします。(i) $(1, 0)$ から多変数の Newton 法を 2 回行い、$(3/4, 3/4)$ を得ることを確かめてください。(ii) $x_0 = (3/4, 3/4)$ で定理 7.4の $\beta, \eta, \gamma$（$R$ は任意）を求め、$h$ と $t_-$ を計算して、零点 $(1/\sqrt2, 1/\sqrt2)$ が $\bar B(x_0, t_-)$ に入っていることを確かめてください。

解答

(i) $J(x, y) = \begin{pmatrix} 2x & 2y \\ 1 & -1 \end{pmatrix}$ です。$(1,0)$ では $J = \begin{pmatrix} 2 & 0 \\ 1 & -1\end{pmatrix}$、$F = (0, 1)$ で、$J d = -F$ を解くと $d = (0, 1)$、次の点は $(1, 1)$ です。そこでは $J = \begin{pmatrix} 2 & 2 \\ 1 & -1\end{pmatrix}$、$F = (1, 0)$ で、$d = (-1/4, -1/4)$、次の点は $(3/4, 3/4)$ です。

(ii) $J(p) - J(p') = \begin{pmatrix} 2(p_1 - p'_1) & 2(p_2 - p'_2) \\ 0 & 0\end{pmatrix}$ の作用素ノルムは第 1 行のベクトルのノルム $2\|p - p'\|$ なので、$\gamma = 2$（どこでも成り立つので $R$ は任意）です。$J_0 = \begin{pmatrix} 3/2 & 3/2 \\ 1 & -1\end{pmatrix}$、$\det J_0 = -3$ で、$J_0^{-1} = \begin{pmatrix} 1/3 & 1/2 \\ 1/3 & -1/2\end{pmatrix}$ です。この行列の 2 つの列は直交し、ノルムは $\sqrt2/3$ と $\sqrt2/2$ なので、$\|J_0^{-1}v\|^2 = v_1^2 \cdot 2/9 + v_2^2 \cdot 1/2$ から $\beta = \|J_0^{-1}\| = \sqrt2/2$ です。$F(x_0) = (1/8, 0)$、$J_0^{-1}F(x_0) = (1/24, 1/24)$ なので $\eta = \sqrt2/24$ です。$L = \beta\gamma = \sqrt2$、$h = L\eta = 1/12 \lt 1/2$ で、

$$t_- = \frac{1 - \sqrt{5/6}}{\sqrt2} \approx 0.06161$$

です。零点との距離は $\sqrt2\,(3/4 - 1/\sqrt2) \approx 0.06066 \lt t_-$ で、たしかに球に入っています。さらに 3 から、半径 $1/L \approx 0.707$ の開球には零点がこれ以外にありません（もう 1 つの零点 $(-1/\sqrt2, -1/\sqrt2)$ との距離は約 $2.06$ です）。

参考文献

• 山本哲朗『数値解析入門』（増訂版）サイエンス社、2003 — 非線形方程式の章（二分法・Newton 法・Kantorovich の定理）。
• 杉原正顯・室田一雄『数値計算法の数理』岩波書店、1994 — 非線形方程式の章。
• K. E. Atkinson, An Introduction to Numerical Analysis, 2nd ed., Wiley, 1989 — Chapter 2（求根法、割線法の次数）。
• J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, 1970（SIAM Classics in Applied Mathematics 30, 2000）— 収束の次数と Newton–Kantorovich の定理。
• P. Deuflhard, Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms, Springer, 2004 — Chapter 2。
• R. P. Brent, Algorithms for Minimization without Derivatives, Prentice-Hall, 1973 — Chapter 4（Brent 法）。