ニュートン法の収束の次数

テイラー展開で誤差 $e_{n} = x_{n} - α$ の漸化式を調べ、単純根では 2 次収束で $lim \frac{e _{n + 1}}{e _{n}^{2}} = \frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ 、 $m$ 重根では線形収束で収束率 $1 - \frac{1}{m}$ となることを使い、収束の次数と誤差定数（修正ニュートン法 $x_{n + 1} = x_{n} - λ \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ の場合も含む）を求められる

前提

ニュートン法の反復（大学数学数値解析）
不動点反復と線形収束（大学数学数値解析）
テイラー展開（大学数学微分積分）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
接線の方程式（数学II 微分法と積分法）
ニュートン法の反復（大学数学数値解析）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
不動点反復と線形収束（大学数学数値解析）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）

説明

ニュートン法 $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ が根 $α$ に収束するとき、その速さを誤差 $e_{n} = x_{n} - α$ で調べる技能です。一般に $lim \frac{∣ e _{n + 1} ∣}{∣ e _{n} ∣ ^{p}} = C$ （ $0 < C < \infty$ ）となるとき、 $p$ を収束の次数、 $C$ を誤差定数といいます。 $p = 1$ のときは $C < 1$ が必要で、これを線形収束といいます。この技能を使うと、単純根では 2 次収束で $lim \frac{e _{n + 1}}{e _{n}^{2}} = \frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ となること、重根では線形収束に落ちることがわかります。修正ニュートン法 $x_{n + 1} = x_{n} - λ \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ の収束率も同じ方法で求められます。

なぜそうしてよいのか

【単純根の場合】 $f$ は 2 回連続微分可能で、 $f (α) = 0$ 、 $f^{'} (α) \neq = 0$ とします。 $x_{n}$ のまわりで $f (α)$ をテイラー展開し、剰余項まで書きます。すると、 $x_{n}$ と $α$ の間のある $ξ_{n}$ について $0 = f (α) = f (x_{n}) + f^{'} (x_{n}) (α - x_{n}) + \frac{f ^{''} ( ξ _{n} )}{2} (α - x_{n})^{2}$ が成り立ちます。ここに $α - x_{n} = - e_{n}$ を代入し、両辺を $f^{'} (x_{n})$ で割ります（ $x_{n}$ が $α$ に十分近ければ $f^{'} (x_{n}) \neq = 0$ です）。その結果は $\frac{f ( x _{n} )}{f ^{'} ( x _{n} )} - e_{n} + \frac{f ^{''} ( ξ _{n} )}{2 f ^{'} ( x _{n} )} e_{n}^{2} = 0$ です。一方 $e_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )} - α = e_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ なので、 $e_{n + 1} = \frac{f ^{''} ( ξ _{n} )}{2 f ^{'} ( x _{n} )} e_{n}^{2}$ となります。 $x_{n} \to α$ なら $ξ_{n} \to α$ であり、 $f^{''}$ と $f^{'}$ は連続です。よって $e_{n} \neq = 0$ のとき $\frac{e _{n + 1}}{e _{n}^{2}} \to \frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ です。つまり誤差は毎回ほぼ 2 乗されて小さくなり、有効桁数がほぼ倍増します。なお $f^{''} (α) = 0$ のときは、この極限が $0$ になり「2 次より速い」ことまでしか言えません。正確な次数を知るには、さらに高い階数の導関数の仮定が必要です。

【 $m$ 重根の場合（ $m \geq 2$ ）】 $f (x) = (x - α)^{m} h (x)$ 、 $h (α) \neq = 0$ と書けるとします（ $h$ は微分可能で $h^{'}$ は連続）。積の微分より $f^{'} (x) = (x - α)^{m - 1} {mh (x) + (x - α) h^{'} (x)}$ です。したがって $\frac{f ( x )}{f ^{'} ( x )} = \frac{( x - α ) h ( x )}{mh ( x ) + ( x - α ) h ^{'} ( x )}$ となります。これを修正ニュートン法に代入すると $e_{n + 1} = e_{n} (1 - \frac{λh ( x _{n} )}{mh ( x _{n} ) + e _{n} h ^{'} ( x _{n} )})$ となり、 $\frac{e _{n + 1}}{e _{n}} \to 1 - \frac{λ}{m}$ が得られます。これは不動点反復の収束率 $g^{'} (α)$ と同じ考え方です。

通常のニュートン法（ $λ = 1$ ）では収束率は $1 - \frac{1}{m}$ で、 $0$ でないので線形収束にとどまります。 $λ = m$ にすると収束率は $0$ になり、上の式は $e_{n + 1} = \frac{h ^{'} ( x _{n} )}{mh ( x _{n} ) + e _{n} h ^{'} ( x _{n} )} e_{n}^{2}$ となります。よって $h^{'} (α) \neq = 0$ なら 2 次収束が回復します（ $h^{'} (α) = 0$ なら 2 次より速くなります）。

手順

根の重複度を調べる： $f (α) = 0$ かつ $f^{'} (α) \neq = 0$ なら単純根である。そうでなければ、 $f (α) = \dots = f^{(m - 1)} (α) = 0$ 、 $f^{(m)} (α) \neq = 0$ となる $m$ を求めるか、 $f (x) = (x - α)^{m} h (x)$ （ $h (α) \neq = 0$ ）と因数分解する。
単純根に通常のニュートン法を使う場合は、誤差定数 $C = \frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ を計算する。 $C \neq = 0$ なら 2 次収束で、 $lim \frac{e _{n + 1}}{e _{n}^{2}} = C$ となる。 $C = 0$ なら 2 次より速い収束になる（何次かは $f^{'''} (α)$ などを調べて別に決める）。
$m$ 重根の場合や修正ニュートン法の場合は、収束率 $lim \frac{e _{n + 1}}{e _{n}} = 1 - \frac{λ}{m}$ を計算する（通常のニュートン法は $λ = 1$ ）。 $1 - \frac{λ}{m} < 1$ で、かつ $0$ でなければ線形収束である。
収束率が $0$ になる場合（ $λ = m$ ）は、 $e_{n + 1} = \frac{h ^{'} ( x _{n} )}{mh ( x _{n} ) + e _{n} h ^{'} ( x _{n} )} e_{n}^{2}$ から $lim \frac{e _{n + 1}}{e _{n}^{2}} = \frac{h ^{'} ( α )}{mh ( α )}$ を求めて次数を確定する。この値が $0$ でなければ 2 次収束である。

例題

$f (x) = x^{2} - 3$ にニュートン法を適用すると、初期値 $x_{0} = 2$ から得られる列 ${x_{n}}$ は $α = 3$ に収束する。 $e_{n} = x_{n} - 3$ とするとき、極限 $n \to \infty lim \frac{e _{n + 1}}{e _{n}^{2}}$ を求めよ。

例題の解答

手順 1（重複度）： $f (3) = 0$ である。 $f^{'} (x) = 2 x$ より $f^{'} (3) = 23 \neq = 0$ なので、 $3$ は単純根である。また $x_{n}$ はすべて有理数なので $e_{n} \neq = 0$ であり、 $\frac{e _{n + 1}}{e _{n}^{2}}$ は定義される。

手順 2（誤差定数）： $f^{''} (x) = 2$ なので、 $n \to \infty lim \frac{e _{n + 1}}{e _{n}^{2}} = \frac{f ^{''} ( 3 )}{2 f ^{'} ( 3 )} = \frac{2}{2 \cdot 2 3} = \frac{1}{2 3} = \frac{3}{6}$ となる。この値は $0$ でないので、収束は 2 次である。

（確認）反復式は $x_{n + 1} = x_{n} - \frac{x _{n}^{2} - 3}{2 x _{n}} = \frac{x _{n}^{2} + 3}{2 x _{n}}$ である。よって $e_{n + 1} = \frac{x _{n}^{2} + 3}{2 x _{n}} - 3 = \frac{( x _{n} - 3 ) ^{2}}{2 x _{n}} = \frac{e _{n}^{2}}{2 x _{n}}$ となる。したがって $\frac{e _{n + 1}}{e _{n}^{2}} = \frac{1}{2 x _{n}} \to \frac{1}{2 3}$ であり、上の結果と一致する。

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

よくある誤り

誤差定数を $\frac{f ^{''} ( α )}{f ^{'} ( α )}$ としてしまう誤り。テイラー展開の 2 次の項の係数は $\frac{f ^{''}}{2}$ なので、正しくは $\frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ である。例えば $f (x) = x^{2} - 3$ では、 $\frac{3}{3}$ ではなく $\frac{3}{6}$ になる。
重根にも 2 次収束の公式を当てはめてしまう誤り。 $m$ 重根では $f^{'} (α) = 0$ なので、 $\frac{f ^{''} ( α )}{2 f ^{'} ( α )}$ は定義されない。正しくは線形収束で、 $lim \frac{e _{n + 1}}{e _{n}} = 1 - \frac{1}{m}$ となる。例えば $f (x) = (x - 1)^{2} (x + 2)$ の根 $1$ では、収束率は $\frac{1}{2}$ である。
修正ニュートン法でも収束率を $1 - \frac{1}{m}$ のままにしてしまう誤り。正しくは $1 - \frac{λ}{m}$ である。例えば 3 重根に $λ = 2$ を使うと、収束率は $\frac{1}{3}$ になる。また単純根（ $m = 1$ ）に $λ = 2$ を使うと収束率は $- 1$ になり、 $1 - \frac{λ}{m} < 1$ を満たさないので収束は保証されない。
$f^{''} (α) = 0$ で $lim \frac{e _{n + 1}}{e _{n}^{2}} = 0$ になったとき、「誤差定数が 0 だから収束しない」とか「2 次収束」と判断してしまう誤り。正しくは「2 次より速い」であり、 $f$ が 2 回連続微分可能というだけでは 3 次とまでは言えない。 $f$ が 3 回連続微分可能で $f^{'''} (α) \neq = 0$ なら、 $lim \frac{e _{n + 1}}{e _{n}^{3}} = \frac{f ^{'''} ( α )}{3 f ^{'} ( α )}$ となり 3 次収束である。例えば $f (x) = sin x$ の根 $0$ （ $f^{'''} (0) = - 1 \neq = 0$ ）では $e_{n + 1} = e_{n} - tan e_{n}$ となる。 $tan x = x + \frac{x ^{3}}{3} + \dots$ より $\frac{e _{n + 1}}{e _{n}^{3}} \to - \frac{1}{3}$ となり、3 次収束である。

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

ニュートン法の収束の次数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題