不動点反復法

1. 定義と原理

方程式 $f(x) = 0$ を解く際、これを同値な形

に書き換え、初期値 $x_0$ から反復

を行って解（不動点）を求める手法を不動点反復法（Fixed-Point Iteration）と呼ぶ。

例えば $f(x) = x^2 - 3x + 1 = 0$ を解くには、$x = \dfrac{x^2 + 1}{3}$（すなわち $g(x) = \dfrac{x^2+1}{3}$）とおいて反復を行えばよい。ただし、$g$ の選び方によって収束・発散が変わるため、注意が必要である。

2. 収束条件

不動点反復法 $x_{n+1} = g(x_n)$ が不動点 $x^*$ に収束するかどうかは、$g$ の導関数の大きさで判定できる。

直感的には、$|g'(x^*)| < 1$ であれば $g$ は不動点の近傍で「縮小的」であり、反復ごとに誤差が小さくなる。逆に $|g'(x^*)| > 1$ のとき反復は発散する。

幾何学的解釈

• $0 < g'(x^*) < 1$: 反復は単調に（一方向から）不動点に接近する。
• $-1 < g'(x^*) < 0$: 反復は不動点を挟んで振動しながら収束する。
• $|g'(x^*)| > 1$: 反復は不動点から離れていき、発散する。
• $|g'(x^*)| = 1$: 境界ケースであり、収束・発散は高次の項に依存する。

3. Banach の不動点定理

不動点反復法の理論的基盤となるのが、Banach の不動点定理（縮小写像の原理）である。

この定理から、さらに誤差の事前評価（a priori）と事後評価（a posteriori）が導かれる。

事前誤差評価（a priori）

事後誤差評価（a posteriori）

事後評価は実用上重要であり、連続する2つの反復値の差から現在の誤差を見積もることができる。

4. アルゴリズム

擬似コードを以下に示す。

function fixedPointIteration(g, x0, tol, maxIter):
    x = x0
    for i = 1 to maxIter:
        x_new = g(x)
        if |x_new - x| < tol:
            return x_new
        x = x_new
    return x  // 収束しなかった場合

5. 収束の速さ

不動点 $x^*$ における $g$ の導関数の値によって、収束の次数が決まる。

線形収束

$g'(x^*) \neq 0$ かつ $|g'(x^*)| < 1$ のとき、誤差 $e_n = |x_n - x^*|$ は

を満たし、線形収束（1次収束）する。$|g'(x^*)|$ が小さいほど収束は速い。

2次収束

$g'(x^*) = 0$ かつ $g''(x^*) \neq 0$ のとき

となり、2次収束する。Newton 法はまさにこの条件を満たすように $g$ を構成している。

p次収束の一般条件

$g'(x^*) = g''(x^*) = \cdots = g^{(p-1)}(x^*) = 0$ かつ $g^{(p)}(x^*) \neq 0$ のとき、$p$ 次収束が得られる。

6. 計算例

7. Newton 法との関係

Newton 法は $g(x) = x - \dfrac{f(x)}{f'(x)}$ とおいた不動点反復法の特殊ケースである。この $g$ に対し

であるから、$f(x^*) = 0$ のとき $g'(x^*) = 0$ となり、2次収束が保証される。

同様に、割線法、Steffensen 法なども不動点反復法の枠組みで理解できる。

8. よくある質問

9. 参考資料

• Wikipedia「不動点定理」（日本語版）
• Wikipedia「Fixed-point iteration」（英語版）
• Wikipedia「Banach fixed-point theorem」（英語版）
• R. L. Burden & J. D. Faires, Numerical Analysis, 10th ed., Cengage, 2016.
• W. H. Press et al., Numerical Recipes, 3rd ed., Cambridge, 2007.