不動点反復と線形収束

$x_{n + 1} = g (x_{n})$ の形の反復について、不動点 $α$ で $∣ g^{'} (α) ∣ < 1$ なら近くの初期値から収束することを判定し、収束率 $lim \frac{x _{n + 1} - α}{x _{n} - α} = g^{'} (α)$ を求められる

前提

平均値の定理（数学III 微分法）

この技能までの道筋（31 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）

説明

方程式 $x = g (x)$ の解（不動点）を、同じ関数を $x_{n + 1} = g (x_{n})$ と繰り返し当てはめて近似する方法を不動点反復といいます。この技能を使うと、不動点 $α$ での微分係数 $g^{'} (α)$ を見るだけで、近くの初期値から反復が $α$ に収束するかどうかを判定できます。さらに、誤差が 1 回ごとにおよそ何倍になるか（収束率）を $lim_{n \to \infty} \frac{x _{n + 1} - α}{x _{n} - α} = g^{'} (α)$ として求められます。数値解法の収束の速さを比べたり、反復の作り方を選んだりするときに使います。

なぜそうしてよいのか

$g$ は不動点 $α$ を含む区間で微分可能で、 $g^{'}$ が連続だとします。 $α = g (α)$ なので、平均値の定理から、 $x_{n}$ と $α$ の間のある $ξ_{n}$ について $x_{n + 1} - α = g (x_{n}) - g (α) = g^{'} (ξ_{n}) (x_{n} - α)$ が成り立ちます（ $x_{n} = α$ のときは両辺とも $0$ で、 $ξ_{n} = α$ とすればよい）。つまり、1 回の反復で誤差は $g^{'} (ξ_{n})$ 倍になります。

【 $∣ g^{'} (α) ∣ < 1$ のとき】 $g^{'}$ の連続性から、ある $δ > 0$ と定数 $L < 1$ をとって、区間 $I = [α - δ, α + δ]$ 上でつねに $∣ g^{'} (x) ∣ \leq L$ とできます。 $x_{n} \in I$ なら $ξ_{n} \in I$ なので $∣ x_{n + 1} - α ∣ \leq L ∣ x_{n} - α ∣ \leq δ$ となり、 $x_{n + 1}$ も $I$ に入ります。これを繰り返すと $∣ x_{n} - α ∣ \leq L^{n} ∣ x_{0} - α ∣ \to 0$ となり、 $x_{n} \to α$ です。このように誤差がほぼ一定の比で縮むことを線形収束といいます。さらに、すべての $n$ で $x_{n} \neq = α$ なら、両辺を $x_{n} - α$ で割って $\frac{x _{n + 1} - α}{x _{n} - α} = g^{'} (ξ_{n})$ が得られます。 $ξ_{n}$ は $x_{n}$ と $α$ の間にあるので $ξ_{n} \to α$ となり、 $g^{'}$ の連続性から、この比は $g^{'} (α)$ に収束します。 $g^{'} (α) < 0$ なら誤差の符号が毎回入れ替わり、 $x_{n}$ は $α$ の両側を行き来しながら近づきます。

【 $∣ g^{'} (α) ∣ > 1$ のとき】 $g^{'}$ の連続性から、ある $δ > 0$ と定数 $L^{'} > 1$ をとって、 $J = [α - δ, α + δ]$ 上でつねに $∣ g^{'} (x) ∣ \geq L^{'}$ とできます。すべての $n$ で $x_{n} \neq = α$ なのに $x_{n} \to α$ となったと仮定します。すると、ある $N$ があって $n \geq N$ ではすべて $x_{n} \in J$ となり、 $ξ_{n} \in J$ なので $∣ x_{n + 1} - α ∣ = ∣ g^{'} (ξ_{n}) ∣∣ x_{n} - α ∣ \geq L^{'} ∣ x_{n} - α ∣$ です。繰り返すと $∣ x_{n} - α ∣ \geq L^{' n - N} ∣ x_{N} - α ∣$ で、 $∣ x_{N} - α ∣ > 0$ 、 $L^{'} > 1$ なので誤差は増え続け、 $0$ に収束できません。これは矛盾です。したがって、ある $n$ で $x_{n} = α$ となる場合（そのあとは $x_{n} = α$ のまま）を除いて、反復は $α$ に収束しません。 $∣ g^{'} (α) ∣ = 1$ のときは、 $g^{'} (α)$ だけでは収束するかどうかを判定できません。

手順

不動点を求める: 方程式 $g (x) = x$ を解いて、不動点 $α$ をすべて求める。
判定する: $g^{'} (x)$ を計算して各不動点で $g^{'} (α)$ を求める。 $∣ g^{'} (α) ∣ < 1$ なら近くの初期値から収束する。 $∣ g^{'} (α) ∣ > 1$ なら、ある $n$ で $x_{n} = α$ となる場合を除いて収束しない。 $∣ g^{'} (α) ∣ = 1$ なら判定できない。
初期値が決まっているときは収束を確かめる: $x_{0}$ と $α$ を含む区間 $I$ で、 $g (I) \subset I$ と $∣ g^{'} (x) ∣ \leq L < 1$ （ $x \in I$ ）を示す。すると平均値の定理から $∣ x_{n} - α ∣ \leq L^{n} ∣ x_{0} - α ∣ \to 0$ となる。
収束率を求める: すべての $n$ で $x_{n} \neq = α$ であることを確かめ、 $lim_{n \to \infty} \frac{x _{n + 1} - α}{x _{n} - α} = g^{'} (α)$ とする。誤差は 1 回ごとにおよそ $∣ g^{'} (α) ∣$ 倍になる。

例題

$g (x) = \frac{x ^{2} + 2}{3}$ とし、 $x_{0} = 0$ 、 $x_{n + 1} = g (x_{n})$ （ $n = 0, 1, 2, \dots$ ）で数列を定める。この数列はある不動点 $α$ に収束する。極限 $n \to \infty lim \frac{x _{n + 1} - α}{x _{n} - α}$ を求めよ。

例題の解答

【手順 1：不動点を求める】 $\frac{x ^{2} + 2}{3} = x$ を整理すると $x^{2} - 3 x + 2 = 0$ 、つまり $(x - 1) (x - 2) = 0$ なので、不動点は $1$ と $2$ である。

【手順 2：判定する】 $g^{'} (x) = \frac{2 x}{3}$ より、 $g^{'} (1) = \frac{2}{3}$ 、 $g^{'} (2) = \frac{4}{3}$ である。 $∣ g^{'} (2) ∣ > 1$ なので、ある $n$ で $x_{n} = 2$ となる場合を除き $2$ には収束しない（例えば $x_{0} = - 2$ なら $x_{1} = 2$ となり、その後ずっと $2$ になる）。後で見るように今の数列ではつねに $x_{n} < 1$ なので $x_{n} = 2$ とはならず、収束先の候補は $α = 1$ である。

【手順 3：収束を確かめる】 $I = [0, 1]$ とする。 $I$ 上で $g^{'} (x) = \frac{2 x}{3} \geq 0$ なので $g$ は増加し、 $g (0) = \frac{2}{3}$ 、 $g (1) = 1$ より $g (I) = [\frac{2}{3}, 1] \subset I$ である。また $I$ 上で $∣ g^{'} (x) ∣ \leq \frac{2}{3}$ が成り立つ。 $x_{0} = 0 \in I$ なので、すべての $x_{n}$ は $I$ に入る。平均値の定理より $∣ x_{n + 1} - 1∣ \leq \frac{2}{3} ∣ x_{n} - 1∣$ となるので、 $∣ x_{n} - 1∣ \leq (\frac{2}{3})^{n} ∣ x_{0} - 1∣ = (\frac{2}{3})^{n} \to 0$ であり、 $x_{n} \to 1$ である。よって $α = 1$ である。

【手順 4：収束率を求める】すべての $n$ で $x_{n} < 1$ であることを帰納法で示す。 $x_{0} = 0 < 1$ である。 $x_{n} \in I$ かつ $x_{n} < 1$ なら、 $g$ は $I$ 上で増加するので $x_{n + 1} = g (x_{n}) < g (1) = 1$ となる。したがってすべての $n$ で $x_{n} \neq = 1$ であり、 $n \to \infty lim \frac{x _{n + 1} - 1}{x _{n} - 1} = g^{'} (1) = \frac{2}{3}$ である。

（検算）直接計算すると $x_{n + 1} - 1 = \frac{x _{n}^{2} - 1}{3} = \frac{( x _{n} + 1 ) ( x _{n} - 1 )}{3}$ なので、比は $\frac{x _{n} + 1}{3} \to \frac{2}{3}$ となり、結果が一致する。

答え: $\frac{2}{3}$

よくある誤り

初期値での値 $∣ g^{'} (x_{0}) ∣$ を見て収束を判定してしまう誤り。正しくは不動点での値 $∣ g^{'} (α) ∣$ を見る。例題では $g^{'} (0) = 0$ だが、これは収束の判定や収束率とは関係がなく、収束率は $g^{'} (1) = \frac{2}{3}$ である。
収束率に絶対値を付けて $∣ g^{'} (α) ∣$ と答えてしまう誤り。正しくは $lim \frac{x _{n + 1} - α}{x _{n} - α} = g^{'} (α)$ で、符号も含めて答える。例えば $g (x) = 1 - \frac{x}{2}$ では $α = \frac{2}{3}$ で、比は $g^{'} (α) = - \frac{1}{2}$ になる（ $x_{0} \neq = \frac{2}{3}$ なら $x_{n}$ は $α$ の両側を交互に行き来する）。
$∣ g^{'} (α) ∣ < 1$ ならどんな初期値からでも収束すると考えてしまう誤り。正しくは保証されるのは $α$ の近くの初期値だけである。例題の $g$ でも $x_{0} = 3$ とすると $x_{1} = \frac{11}{3}$ となり、 $x_{n} \to \infty$ と発散する。
$∣ g^{'} (α) ∣ = 1$ のときにも収束・発散を決めてしまう誤り。正しくはこの場合は $g^{'} (α)$ だけでは判定できない。どちらも $g^{'} (0) = 1$ だが、 $g (x) = x - x^{3}$ では $0$ の近くの初期値（例えば $∣ x_{0} ∣ \leq 1$ ）から $0$ に（遅く）収束し、 $g (x) = x + x^{3}$ では $x_{0} \neq = 0$ なら $∣ x_{n + 1} ∣ = ∣ x_{n} ∣ (1 + x_{n}^{2}) > ∣ x_{n} ∣$ なので $0$ に収束しない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

難易度 3（期末試験の応用レベル）
$a$ を正の実数とし、 $α = \frac{1}{a}$ とする。実数の定数 $p, q, r$ を用いた割り算を含まない反復
$x_{n + 1} = x_{n} (p + q a x_{n}^{2} + r a^{2} x_{n}^{4}) (n = 0, 1, 2, \dots)$
を考える。この反復関数を $g (x) = x (p + q a x^{2} + r a^{2} x^{4})$ とおく。 $g (α) = α, g^{'} (α) = 0, g^{''} (α) = 0$ がすべて成り立つように $p, q, r$ を定める。これにより、 $α$ に十分近い初期値 $x_{0}$ から反復すると $x_{n}$ は $α$ に 3 次以上で収束する。
このように定めた $p, q, r$ を用い、 $x_{0}$ を $α$ に十分近くとる。さらに、すべての $n$ について $x_{n} \neq = α$ であるとする。このとき、極限
$n \to \infty lim \frac{x _{n + 1} - α}{( x _{n} - α ) ^{3}}$
を $a$ を用いて表せ。

この技能の次に学べること

ニュートン法の収束の次数（大学数学数値解析）
1 次元写像の周期軌道の乗数と安定性（大学院数学力学系・エルゴード理論）