非線形方程式の数値解法(numerical methods for nonlinear equations)とは、方程式 $f(x)=0$ の解に近づく数列を反復で作り、必要な桁数で止める計算の方法の総称である。二分法は連続性と符号の変化だけで必ず収束して誤差の上界が 1 回で半分になり、不動点反復は不動点での傾きが率を決める。Newton 法は単根で 2 次収束するが、$m$ 重根では率 $1-1/m$ の 1 次収束に落ち、初期値が悪いと発散や巡回も起きる。工学の方程式の計算では、二分法で根を挟みながら Newton 法を試す手順と、残差と誤差を分けた止める判定を使う。
$x^3-2x-5=0$ の実数解は 1 つで、$2$ と $3$ の間にある。解の公式はあるが、工学で出会う $\cos x=x$ や管の摩擦の式のような方程式は、初等関数の式で解を書き下せないのが普通である。そこで、解に近づく数列を作り、必要な桁数がそろったところで止める。
たとえば Newton 法を $x_0=2$ から始めると、次のように桁が増えていく。
| $n$ | $x_n$ | 誤差 $\lvert x_n-x^*\rvert$ |
|---|---|---|
| 0 | $2$ | $9.46\times10^{-2}$ |
| 1 | $2.1$ | $5.45\times10^{-3}$ |
| 2 | $2.0945681211$ | $1.66\times10^{-5}$ |
| 3 | $2.0945514817$ | $1.56\times10^{-10}$ |
| 4 | $2.0945514815$ | $1.37\times10^{-20}$ |
方法を選ぶときの問いは 3 つある。どんな情報(符号、導関数)が要るか。初期値が悪くても解にたどり着くか。解の近くでどれだけ速いか。速い方法ほど初期値を選び、遅い方法ほど確実である。この記事は、二分法・不動点反復・Newton 法・割線法を公式の表にまとめ、誤差の評価を証明し、止める判定と、確実さと速さを両立させる手順を与える。
Newton 法の局所収束の定理は Newton法 が、割線法の次数の定理は 割線法 が持つので、ここでは見出しで引く。この記事が証明するのは、二分法の誤差、不動点反復の収束、次数の判定、重根での Newton 法、止める判定の根拠、手順が止まることである。
区間 $I$ 上の実数値関数 $f$ について、方程式 $f(x)=0$ の解 $x^*$($f$ の 根 あるいは 零点)に近づく数列 $(x_n)$ を、有限回の四則演算と関数値の計算を繰り返して作る手順を 非線形方程式の数値解法 という。$x_{n+1}$ を前の項から定める式を 反復 といい、$x_0$ を 初期値 という。
$f(x)=0$ は、$g(x):=x-f(x)$ などとおけば $x=g(x)$ の形にも書ける。$g(x^*)=x^*$ を満たす点を 不動点 といい、$x_{n+1}=g(x_n)$ を 不動点反復 という。
$x_n\to x^*$ で、$e_n:=x_n-x^*\ne0$ がすべての $n$ で成り立つとする。
$p=1$ の率 $C$ のもとでは、誤差は 1 回の反復でおよそ $C$ 倍になるので、1 桁増やすのに $\log(1/10)/\log C$ 回ほどかかる。$p=2$ では、$C$ が極端でなければ正しい桁数が 1 回ごとにおよそ 2 倍になる。
各方法を使ってよい条件は次のとおりである。
| 方法 | 反復 | 使える条件 | 誤差・次数 | 根拠 |
|---|---|---|---|---|
| 二分法 | $c_n=\frac{a_n+b_n}2$、符号の変わる側を残す | $f$ 連続、$f(a)f(b)< 0$ | $\lvert c_n-x^*\rvert\le\frac{b-a}{2^{n+1}}$ | prop-nle-bisection |
| 不動点反復 | $x_{n+1}=g(x_n)$ | $g\colon[a,b]\to[a,b]$、Lipschitz 定数 $L< 1$ | $\lvert e_n\rvert\le L^n(b-a)$ | thm-nle-fixed |
| 不動点反復(局所) | 同上 | $g$ は $C^1$ 級、$\lvert g'(x^*)\rvert< 1$、$x_0$ が近い | $g'(x^*)\ne0$ なら 1 次、率 $\lvert g'(x^*)\rvert$ | prop-nle-local |
| Newton 法(単根) | $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ | $f$ は $C^2$ 級、$f'(x^*)\ne0$、$x_0$ が近い | $f''(x^*)\ne0$ なら 2 次、$C=\bigl\lvert\frac{f''(x^*)}{2f'(x^*)}\bigr\rvert$ | Newton法、thm-nle-multiple |
| Newton 法($m$ 重根、$m\ge2$) | 同上 | $m$ 重根、$x_0$ が近い | 1 次、率 $1-\frac1m$ | thm-nle-multiple |
| 修正 Newton 法 | $x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)}$ | $m$ 重根で $m$ が既知、$x_0$ が近い | $h'(x^*)\ne0$ なら 2 次、$C=\bigl\lvert\frac{h'(x^*)}{mh(x^*)}\bigr\rvert$ | thm-nle-multiple |
| 割線法 | $x_{n+1}=x_n-f(x_n)\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}$ | $f$ は $C^2$ 級、単根、2 点が近い | $f''(x^*)\ne0$ なら次数 $\frac{1+\sqrt5}2$ | 割線法 |
二分法の誤差は単調に減るとは限らないので(ex-nle-cubic の表)、次数の定義は当てはまらない。上界が 1 回ごとに半分になるという意味で、率 $\frac12$ の 1 次収束と同じ速さとみる。
方法を比べると次のようになる。関数値の回数は、$f$ と $f'$ の計算をそれぞれ 1 回と数える。
| 方法 | 要る情報 | 1 回の反復の計算 | 速さ | 初期値が悪いとき |
|---|---|---|---|---|
| 二分法 | $f$ の符号、符号の変わる区間 | $f$ 1 回 | 1 回で上界が半分 | 必ず根に収束する |
| 不動点反復 | 収束する $g$ | $g$ 1 回 | 率 $\lvert g'(x^*)\rvert$ | $g$ の作り方しだいで発散する |
| Newton 法 | $f$、$f'$ | $f$ と $f'$ で 2 回 | 2 次 | 発散・周期的な振動がありうる |
| 割線法 | $f$ と 2 つの初期値 | $f$ 1 回 | 次数 $1.618\ldots$ | 発散がありうる |
二分法:$f$ が $[a,b]$ で連続で $f(a)f(b)< 0$ とする。$a_0:=a$、$b_0:=b$ とする。$c_n:=\frac{a_n+b_n}2$ とおき、$f(c_n)=0$ なら止める。$f(a_n)f(c_n)< 0$ なら $[a_{n+1},b_{n+1}]:=[a_n,c_n]$、そうでなければ $[a_{n+1},b_{n+1}]:=[c_n,b_n]$ とする。
二分法が止まらないとき、どの $n$ でも $f(a_n)f(b_n)< 0$ で、$[a_n,b_n]$ は $f$ の根を含み、その根 $x^*$ について
$$
\lvert c_n-x^*\rvert\le\frac{b-a}{2^{n+1}}
$$
である。さらに $c_n$ は $f$ のある根に収束する。許容誤差 $\varepsilon>0$ に対し、$n+1\ge\log_2\frac{b-a}{\varepsilon}$ なら $[a_n,b_n]$ のどの根についても誤差は $\varepsilon$ 以下である。
$n$ についての帰納法で $f(a_n)f(b_n)< 0$ を示す。$n=0$ は仮定である。$f(c_n)\ne0$ のとき、$f(a_n)$ と $f(b_n)$ は異符号なので、$f(c_n)$ は一方と異符号であり、残す区間の両端は異符号である。中間値の定理 により $[a_n,b_n]$ は根を含む。区間の幅は $b_n-a_n=(b-a)/2^n$ で、$c_n$ はその中点だから、区間内の任意の点 $x^*$ について $\lvert c_n-x^*\rvert\le(b_n-a_n)/2=(b-a)/2^{n+1}$ である。
$(a_n)$ は単調増加、$(b_n)$ は単調減少で有界であり、幅が $0$ に近づくので、共通の極限 $c$ をもち、$c_n\to c$ である。$f$ の連続性から $f(c)^2=\lim f(a_n)f(b_n)\le0$ となり、$f(c)=0$ である。最後の主張は、上界が $\varepsilon$ 以下になる条件を書き直したものである。$\square$
$g\colon[a,b]\to[a,b]$ は、ある $0\le L< 1$ について $\lvert g(x)-g(y)\rvert\le L\lvert x-y\rvert$($x,y\in[a,b]$)を満たすとする。このとき次が成り立つ。
1. $g$ は Lipschitz なので連続である。$k(x):=g(x)-x$ は連続で、$g$ の値が $[a,b]$ にあるから $k(a)\ge0\ge k(b)$ である。中間値の定理 により $k(x^*)=0$ となる $x^*$ がある。$x^*,y^*$ がともに不動点なら $\lvert x^*-y^*\rvert=\lvert g(x^*)-g(y^*)\rvert\le L\lvert x^*-y^*\rvert$ で、$L< 1$ より $x^*=y^*$ である。
2. $x_n\in[a,b]$ であるから、$\lvert x_{n+1}-x^*\rvert=\lvert g(x_n)-g(x^*)\rvert\le L\lvert x_n-x^*\rvert$ である。これを繰り返し、$\lvert x_0-x^*\rvert\le b-a$ を使う。
3. $\lvert x_n-x^*\rvert\le L\lvert x_{n-1}-x^*\rvert\le L\bigl(\lvert x_{n-1}-x_n\rvert+\lvert x_n-x^*\rvert\bigr)$ を $\lvert x_n-x^*\rvert$ について解く。$\square$
3 は、計算の途中で分かる量 $\lvert x_n-x_{n-1}\rvert$ で誤差を上から押さえる式である。一般の完備距離空間での同じ主張は 縮小写像の不動点定理 の定理「Banach の不動点定理」にある。
$g$ を自分で選ぶときは、不動点での傾きが収束を決める。
$g$ は $x^*$ の近くで $C^1$ 級で、$g(x^*)=x^*$ とする。
1. $\lvert g'(x^*)\rvert< L< 1$ となる $L$ と、$J:=[x^*-\delta,x^*+\delta]$ で $\lvert g'\rvert\le L$ となる $\delta>0$ をとる。平均値の定理 により $x\in J$ で $\lvert g(x)-x^*\rvert=\lvert g(x)-g(x^*)\rvert\le L\lvert x-x^*\rvert\le L\delta$ だから、$g(J)\subset J$ である。thm-nle-fixed より $x_n\to x^*$ である。$x_n\ne x^*$ なら、$x_n$ と $x^*$ の間の $\xi_n$ で $e_{n+1}=g'(\xi_n)e_n$ となり、$\xi_n\to x^*$ と $g'$ の連続性から比は $g'(x^*)$ に近づく。
2. $1< K< \lvert g'(x^*)\rvert$ となる $K$ と、$J$ で $\lvert g'\rvert\ge K$ となる $\delta>0$ をとる。$x_n\to x^*$ なら、ある $N$ 以降 $x_n\in J$ である。平均値の定理により $n\ge N$ で $\lvert e_{n+1}\rvert\ge K\lvert e_n\rvert$ である。$e_N\ne0$ なら $\lvert e_{N+j}\rvert\ge K^j\lvert e_N\rvert\to\infty$ となり、$e_n\to0$ に反する。よって $x_N=x^*$ である。$\square$
整数 $p\ge2$ について、$g$ は $x^*$ の近くで $C^p$ 級、$g(x^*)=x^*$、$g^{(j)}(x^*)=0$($1\le j\le p-1$)とする。$x_n\to x^*$ かつすべての $n$ で $x_n\ne x^*$ なら
$$
\frac{e_{n+1}}{e_n^{\,p}}\longrightarrow\frac{g^{(p)}(x^*)}{p!}
$$
である。とくに $g^{(p)}(x^*)\ne0$ なら次数 $p$ で収束する。
Lagrange の剰余項をもつ Taylorの定理 により、$x_n$ と $x^*$ の間の $\xi_n$ で $g(x_n)=x^*+\frac{g^{(p)}(\xi_n)}{p!}e_n^{\,p}$ である。$e_{n+1}=g(x_n)-x^*$ を $e_n^{\,p}$ で割り、$\xi_n\to x^*$ と $g^{(p)}$ の連続性を使う。$\square$
Newton 法は $g(x)=x-f(x)/f'(x)$ の不動点反復である。$f$ が $C^3$ 級で単根なら、$g'(x)=f(x)f''(x)/f'(x)^2$ から $g'(x^*)=0$、$g''(x^*)=f''(x^*)/f'(x^*)$ となり、prop-nle-order は表の 2 次収束の定数を与える。
Newton法 の定理「局所収束と2次収束」は $f'(x^*)\ne0$ を仮定している。$m$ 重根では Newton 法の速さは 1 次に落ち、$m$ を掛ければ 2 次に戻る。次の定理は単根の場合の定数も同時に与える。
$I$ を開区間とし、$x^*\in I$、整数 $m\ge1$、$f(x)=(x-x^*)^mh(x)$、$h$ は $I$ で $C^1$ 級、$h(x^*)\ne0$ とする。$x_n=x^*$ となったら反復を止めることにする。
$e:=x-x^*$ と書き、$D(x):=mh(x)+eh'(x)$ とおく。$D$ は連続で $D(x^*)=mh(x^*)\ne0$ である。積の微分により $f'(x)=e^{m-1}D(x)$ である。$\delta_0>0$ を、$\lvert e\rvert\le\delta_0$ で $x\in I$、$h(x)\ne0$、$D(x)\ne0$ となるようにとる。$0< \lvert e\rvert\le\delta_0$ では $f'(x)\ne0$ で、$f(x)/f'(x)=eh(x)/D(x)$ である。よって
$$
x-\frac{f(x)}{f'(x)}-x^*=e\cdot\frac{D(x)-h(x)}{D(x)}=:e\,A(x),\qquad
x-m\frac{f(x)}{f'(x)}-x^*=e\cdot\frac{D(x)-mh(x)}{D(x)}=e^2\,B(x)
$$
である。ここで $B(x):=h'(x)/D(x)$ で、$D-mh=eh'$ を使った。$A,B$ は連続で、$A(x^*)=1-\frac1m$、$B(x^*)=\dfrac{h'(x^*)}{mh(x^*)}$ である。
1. $1-\frac1m< L< 1$ をとり、$\delta\le\delta_0$ を $\lvert e\rvert\le\delta$ で $\lvert A(x)\rvert\le L$ となるようにとる。$\lvert e_{n+1}\rvert=\lvert e_n\rvert\,\lvert A(x_n)\rvert\le L\lvert e_n\rvert$ だから、列は $\lvert e\rvert\le\delta$ の中にとどまり、$e_n\to0$ である。$m\ge2$ なら $A(x^*)\ne0$ なので、$\delta$ を小さくして $\lvert e\rvert\le\delta$ で $A\ne0$ とできる。すると $x_0\ne x^*$ なら $e_{n+1}=e_nA(x_n)\ne0$ で、比 $e_{n+1}/e_n=A(x_n)$ は $A(x^*)$ に近づく。
2. $M:=\max_{\lvert e\rvert\le\delta_0}\lvert B\rvert$ とし、$\delta\le\delta_0$ を $M\delta\le\frac12$ となるようにとる。$\lvert e_{n+1}\rvert\le M\lvert e_n\rvert^2\le\frac12\lvert e_n\rvert$ だから $e_n\to0$ で、比 $e_{n+1}/e_n^{\,2}=B(x_n)$ は $B(x^*)$ に近づく。
$f$ が $C^2$ 級で $m=1$ のとき、$h(x)=\int_0^1f'(x^*+te)\,dt$ から $h(x^*)=f'(x^*)$、$h'(x^*)=\int_0^1tf''(x^*)\,dt=\frac12f''(x^*)$ である。$\square$
計算で分かるのは $\lvert f(x_n)\rvert$(残差)であって、誤差 $\lvert x_n-x^*\rvert$ ではない。両者の関係は導関数で決まる。
$f$ は $C^1$ 級で $f(x^*)=0$ とする。$x$ と $x^*$ を含む区間で $\lvert f'\rvert\ge\mu>0$ なら $\lvert x-x^*\rvert\le\lvert f(x)\rvert/\mu$ である。$x^*$ が $m$ 重根なら、$x\to x^*$ で $\lvert f(x)\rvert/\bigl(\lvert h(x^*)\rvert\lvert x-x^*\rvert^m\bigr)\to1$ である。
平均値の定理 により、$x$ と $x^*$ の間の $\xi$ で $f(x)=f(x)-f(x^*)=f'(\xi)(x-x^*)$ であり、$\lvert f'(\xi)\rvert\ge\mu$ から前半が出る。後半は $\lvert f(x)\rvert=\lvert x-x^*\rvert^m\lvert h(x)\rvert$ と $h$ の連続性による。$\square$
したがって単根でも $\lvert f'(x^*)\rvert$ が小さいと、残差が小さくても誤差は小さいとは限らない。$1/\lvert f'(x^*)\rvert$ は、根の計算の 条件数 にあたる。関数値に大きさ $\varepsilon$ の丸め誤差があると、$m$ 重根では誤差がおよそ $(\varepsilon/\lvert h(x^*)\rvert)^{1/m}$ までしか減らない(ex-nle-precision)。
標準の手順は、二分法で根を挟み続けながら Newton 法を試す方法である。Newton 法の 1 歩が使えないときだけ二分法に切り替えるので、止まることは常に保証され(prop-nle-safeguard)、Newton 法が効く場面ではその速さが出る。
| 止まった理由 | 分かること | 確かめること |
|---|---|---|
| $b_k-a_k\le\mathrm{tol}_x$ | 区間内に根があり、誤差は $\mathrm{tol}_x$ 以下 | 不連続な $f$ では根とは限らない(ex-nle-counterexamples) |
| $\lvert f(x_k)\rvert\le\mathrm{tol}_f$ | 残差だけが小さい | $\lvert f'(x_k)\rvert$ を見て prop-nle-residual で誤差を見積もる |
| $k=N_{\max}$ | 収束していない | 区間・関数の実装・上限を見直す |
$f$ が $[a,b]$ で連続、$(a,b)$ で微分可能で $f(a)f(b)< 0$ とし、$\mathrm{tol}_x,\mathrm{tol}_f>0$ とする。$N_{\max}$ を置かないとき、上の手順は有限回で止まる。止まるまでのどの $k$ でも、$[a_k,b_k]$ は両端で $f$ が異符号であり、$f$ の根を含む。
段 3 で止まらなければ $f(x_k)\ne0$ なので、段 4 は両端が異符号の区間を残す(prop-nle-bisection の証明と同じ)。中間値の定理 により区間は根を含む。段 5・6 の $x_{k+1}$ はいつも $(a_{k+1},b_{k+1})$ の中にあるので、次の段 4 も実行でき、区間は縮む一方である。
止まらないと仮定する。段 6 が無限回起きるなら、段 6 のたびに次の段 4 で幅が半分になり、ほかの回で幅は増えないから、幅は $0$ に近づいて $\mathrm{tol}_x$ 以下になる。段 6 が有限回なら、ある $K$ から先はすべて段 5 が採用され、$\lvert f(x_k)\rvert\le2^{-(k-K)}\lvert f(x_K)\rvert$ となって $\mathrm{tol}_f$ 以下になる。どちらも止まらないことに反する。$\square$
使う公式:prop-nle-bisection、thm-nle-multiple、割線法。二分法は $[2,3]$、Newton 法は $x_0=2$、割線法は $x_0=2$、$x_1=3$ から始める。
答え:$x^*\approx2.0945514815$($f(2)=-1< 0< f(3)=16$)。
| $n$ | 二分法 $c_n$ | 誤差 | 上界 $2^{-(n+1)}$ | 割線法 $x_n$ | 誤差 |
|---|---|---|---|---|---|
| 2 | $2.125$ | $3.04\times10^{-2}$ | $1.25\times10^{-1}$ | $2.0588235294$ | $3.57\times10^{-2}$ |
| 3 | $2.0625$ | $3.21\times10^{-2}$ | $6.25\times10^{-2}$ | $2.0812636598$ | $1.33\times10^{-2}$ |
| 4 | $2.09375$ | $8.01\times10^{-4}$ | $3.13\times10^{-2}$ | $2.0948241461$ | $2.73\times10^{-4}$ |
| 5 | $2.109375$ | $1.48\times10^{-2}$ | $1.56\times10^{-2}$ | $2.0945494310$ | $2.05\times10^{-6}$ |
| 6 | $2.1015625$ | $7.01\times10^{-3}$ | $7.81\times10^{-3}$ | $2.0945514812$ | $3.15\times10^{-10}$ |
Newton 法の値は冒頭の表のとおりで、$\lvert e_{n+1}\rvert/e_n^{\,2}$ は $0.60946,\ 0.56051,\ 0.56297,\ 0.56298$ と進み、$f''(x^*)/(2f'(x^*))=3x^*/(3x^{*2}-2)\approx0.56298$ に近づく。二分法の誤差は $n=4$ で偶然小さくなったあとまた増えるので、単調ではない。誤差を $10^{-10}$ 以下にするのに、上界からは $n+1\ge\log_210^{10}\approx33.2$、すなわち $n=33$ までかかる。
図: 方程式 x^3-2x-5=0 の根に向かう 4 つの方法の誤差。横軸は反復の番号、縦軸は対数目盛の誤差
片対数のグラフでは、1 次収束は直線になり、2 次収束や割線法は下に折れ曲がる。二分法の誤差は単調でないが、1 回あたりおよそ $\log_{10}2\approx0.30$ 桁減る直線に沿う。
$x^3-2x-5=0$ を $x=g(x)$ の形に 2 通りに直す:$g_1(x)=(2x+5)^{1/3}$、$g_2(x)=\frac{x^3-5}2$。
使う公式:thm-nle-fixed、prop-nle-local。
答え:$g_1$ は $[2,3]$ で収束し、率は $\lvert g_1'(x^*)\rvert=\frac2{3x^{*2}}\approx0.15196$ である。$g_2$ は $\lvert g_2'(x^*)\rvert=\frac32x^{*2}\approx6.5807$ なので、反復の途中でちょうど $x^*$ に落ちる場合を除き、根に収束しない。
$g_1(2)=9^{1/3}\approx2.0801$、$g_1(3)=11^{1/3}\approx2.2240$ で、$g_1$ は増加なので $[2,3]$ を自分の中へ写す。$g_1'(x)=\frac23(2x+5)^{-2/3}$ は減少で $\lvert g_1'\rvert\le g_1'(2)\approx0.15408=:L$ である。thm-nle-fixed の 2 から、$L^n\le10^{-8}$、すなわち $n=10$ で誤差は $10^{-8}$ 以下である。$x_0=2$ から計算すると
$$
x_1\approx2.0800838,\quad x_2\approx2.0923507,\quad x_3\approx2.0942170,\quad x_{10}\approx2.0945514809
$$
で、誤差は $x_{10}$ で $6.26\times10^{-10}$、比 $e_{n+1}/e_n$ は $0.15196$ に落ち着く。
一方 $g_2$ は、$x_0=2.1$ からでも $2.1305,\ 2.3352,\ 3.8671,\ 26.416$ と発散する。根のすぐ近くから始めても、傾きが $1$ より大きいと離れていく。
管の中の流れの摩擦係数 $\lambda$ は、無次元量の Reynolds 数 $\mathrm{Re}$ と相対粗さ $r$ から、Colebrook の式 $\frac1{\sqrt\lambda}=-2\log_{10}\bigl(\frac r{3.7}+\frac{2.51}{\mathrm{Re}\sqrt\lambda}\bigr)$ で決まる。$\mathrm{Re}=10^5$、$r=10^{-3}$ のとき $\lambda$ を求める。
使う公式:thm-nle-fixed。$x:=1/\sqrt\lambda$ とおくと、方程式は $x=g(x):=-2\log_{10}\bigl(\frac r{3.7}+\frac{2.51\,x}{\mathrm{Re}}\bigr)$ である。
答え:$x^*\approx6.7154130$、$\lambda=1/x^{*2}\approx0.022175$。
$g$ は減少で、$g(4)\approx6.862$、$g(10)\approx6.566$ だから $[4,10]$ を自分の中へ写す。$\lvert g'\rvert$ は $x$ について減少で、$[4,10]$ で $\lvert g'\rvert\le\lvert g'(4)\rvert\approx0.0588=:L$ である。$\lambda=0.02$ に当たる $x_0=7.0710678$ から
$$
x_1\approx6.6979209,\quad x_2\approx6.7162825,\quad x_3\approx6.7153699,\quad x_4\approx6.7154152
$$
となり、比 $e_{n+1}/e_n$ は $g'(x^*)\approx-0.04968$ に近づく。傾きが負なので、近似値は根の両側を交互に動く。$g'$ を計算せず、1 回ごとに 1 桁以上増える。
$f(x)=x^3-3x+2=(x-1)^2(x+2)$ の 2 重根 $x^*=1$ を、$x_0=2$ から求める。
使う公式:thm-nle-multiple($m=2$、$h(x)=x+2$)。
答え:Newton 法は率 $\frac12$ の 1 次収束で、修正 Newton 法は 2 次収束で定数は $\frac{h'(1)}{2h(1)}=\frac16$ である。
| $n$ | Newton 法の誤差 | $e_n/e_{n-1}$ | 修正 Newton 法の誤差 | $e_n/e_{n-1}^{\,2}$ |
|---|---|---|---|---|
| 1 | $5.556\times10^{-1}$ | $0.55556$ | $1.111\times10^{-1}$ | $0.11111$ |
| 2 | $2.979\times10^{-1}$ | $0.53623$ | $1.949\times10^{-3}$ | $0.15789$ |
| 3 | $1.554\times10^{-1}$ | $0.52161$ | $6.327\times10^{-7}$ | $0.16650$ |
| 4 | $7.956\times10^{-2}$ | $0.51202$ | $6.672\times10^{-14}$ | $0.16667$ |
| 5 | $4.029\times10^{-2}$ | $0.50638$ | $7.418\times10^{-28}$ | $0.16667$ |
この $f$ では Newton 法の反復は $x\mapsto\frac{2(x^2+x+1)}{3(x+1)}$、修正 Newton 法の反復は $x\mapsto\frac{x^2+x+4}{3(x+1)}$ に約分できる。前者から $1$ を引くと $\frac{(x-1)(2x+1)}{3(x+1)}$ で、$x\to1$ の比は $\frac12$ である。後者から $1$ を引くと $\frac{(x-1)^2}{3(x+1)}$ で、比の極限は $\frac16$ である。
$f(x)=(x-1)^3$ を展開した $x^3-3x^2+3x-1$ として、Horner 法 $((x-3)x+3)x-1$ により倍精度(IEEE 754 の 64 ビット、$\varepsilon\approx2.2\times10^{-16}$)で計算する。
使う公式:prop-nle-residual($m=3$、$h=1$)。
答え:計算された関数の符号は $\lvert x-1\rvert\approx5\times10^{-6}$ の範囲で不規則に変わり、これより小さい誤差は保証できない。見積もり $\varepsilon^{1/3}\approx6\times10^{-6}$ と合う。
$[1-2\times10^{-5},1+2\times10^{-5}]$ を $4000$ 等分して符号を調べると、$\lvert x-1\rvert$ がおよそ $5.4\times10^{-6}$ 以下の範囲で 100 回以上変わる(回数は分点の丸め方で変わる)。二分法を $[0.5,1.7]$ から走らせると、$18$ 回目の中点で計算された値がちょうど $0$ になって止まり、誤差は $1.53\times10^{-6}$ である。Newton 法を、$f'$ も Horner 法 $(3x-6)x+3$ で計算して $x_0=1.5$ から走らせると、誤差は率 $\frac23$ で減ったあと、最良でも $2.57\times10^{-6}$ である。
$f(x)=x^3-2x+2$ は、Newton 法を $x_0=0$ から始めると $0,1,0,1,\ldots$ と巡回する(Newton法 の注意「反例:収束しない初期値と2次収束しない零点」)。prop-nle-safeguard の手順を $[a,b]=[-3,1]$ で使う。
答え:$x^*\approx-1.7692923542$($\mathrm{tol}_f=10^{-13}$、$\mathrm{tol}_x=10^{-12}$ で $k=6$ で止まる)。
$x_0=-1$ では $f(-1)=3$、$f'(-1)=1$ で、Newton の 1 歩は $y=-4$ となり区間の外に出る。よって二分して $x_1=-2$ とする。以後は Newton の 1 歩がすべて採用される。
| $k$ | 使った段 | $x_k$ |
|---|---|---|
| 0 | 初期値 | $-1$ |
| 1 | 二分 | $-2$ |
| 2 | Newton | $-1.8$ |
| 3 | Newton | $-1.7699481865$ |
| 4 | Newton | $-1.7692926629$ |
| 5 | Newton | $-1.7692923542$ |
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 二分法:$f$ の連続性 | $[-1,1]$ で $f(x)=1/x$($x\ne0$)、$f(0)=1$ | $f(-1)f(1)< 0$ だが根がなく、区間は $0$ に縮む |
| 二分法:$f(a)f(b)< 0$ | $[-1,1]$ で $f(x)=x^2$ | 根 $0$ があるのに符号が変わらず、挟めない |
| 不動点反復:$g$ が区間を自分へ写す | $[0,1]$ で $g(x)=\frac x2+1$ | $L=\frac12$ だが区間に不動点がなく、列は外の $2$ へ向かう |
| 不動点反復:$L< 1$ | $[0,1]$ で $g(x)=\sin x$ | $\lvert g(x)-g(y)\rvert< \lvert x-y\rvert$($x\ne y$)でも $L=1$ で、誤差は $\sqrt{3/n}$ 程度にしか減らない |
| Newton 法:$f$ の微分可能性 | $f(x)=\operatorname{sgn}(x)\lvert x\rvert^{1/3}$ | $x_{n+1}=-2x_n$ となり、どの $x_0\ne0$ からも発散する |
| Newton 法:$C^2$ 級 | $f(x)=x+\lvert x\rvert^{3/2}$($C^1$ 級、$f'(0)=1$) | 収束はするが次数は $\frac32$ に落ちる |
| Newton 法:単根 | $f(x)=x^3-3x+2$ の根 $1$ | 1 次に落ちる(ex-nle-double) |
| Newton 法:初期値が近い | $f(x)=\arctan x$、$x_0=1.5$;$f(x)=x^3-2x+2$、$x_0=0$ | 発散、巡回(Newton法 の注意「反例:収束しない初期値と2次収束しない零点」) |
$1/x$ の二分法. $f$ は $0$ だけで不連続である。$c_0=0$ で $f(0)=1>0$ なので $[-1,0]$ が残り、以後の中点はどれも負で $f< 0$ だから、右端 $0$ を保ったまま左端が $0$ に近づく。極限の $0$ は根ではない($f(0)=1$)。prop-nle-bisection の証明で、連続性を使う段だけが通らない。
$g(x)=\frac x2+1$. $g(0)=1$、$g(1)=1.5$ なので $g([0,1])\not\subset[0,1]$ である。$x_{n+1}-2=\frac12(x_n-2)$ から列は $2$ に収束するが、$2\notin[0,1]$ である。
$g(x)=\sin x$. $x_n\to0$ で、$\frac{x_{n+1}}{x_n}\to1$ である。$\frac1{\sin^2x}-\frac1{x^2}\to\frac13$($x\to0$)から $\frac1{x_{n+1}^2}-\frac1{x_n^2}\to\frac13$ となり、平均をとると $nx_n^2\to3$ である。$x_0=1$ から $x_{10^4}\approx0.0173136$ で、$\sqrt{3/10^4}\approx0.0173205$ に近い。
$f(x)=\operatorname{sgn}(x)\lvert x\rvert^{1/3}$. $x\ne0$ で $f(x)/f'(x)=3x$ だから $x_{n+1}=-2x_n$ である。$f$ は $0$ で微分できない(接線が縦になる)。
$f(x)=x+\lvert x\rvert^{3/2}$. $f'(x)=1+\frac32\sqrt{\lvert x\rvert}\operatorname{sgn}x$ は連続だが $0$ で微分できない。$x>0$ で反復の値は $\dfrac{\frac12x^{3/2}}{1+\frac32\sqrt x}$ であり、$x_0=0.1$ からの列は正のまま $0$ に近づくので、$e_{n+1}/e_n^{3/2}\to\frac12$ である。実際に $e_8/e_7^{3/2}\approx0.5000$ となる。
| 誤り | 正しくは | なぜ |
|---|---|---|
| $\lvert x_{n+1}-x_n\rvert$ が小さいだけで止める | 収束の遅い列では誤差のほうがずっと大きい。率 $\rho$ が分かれば thm-nle-fixed の 3 の形で見積もる | $x_{n+1}=\sin x_n$ の $n=10^4$ では差が $8.7\times10^{-7}$ なのに誤差は $0.017$ |
| $\lvert f(x_n)\rvert$ が小さければ根に近いとする | 導関数の大きさで割って誤差を見積もる | prop-nle-residual。$f(x)=10^{-8}(x-1)$ は $x=2$ で残差 $10^{-8}$ だが誤差は $1$ |
| 反復の上限を置かない | $N_{\max}$ を置き、失敗として報告する | Newton 法は巡回しうる(ex-nle-safeguard) |
| 符号の変化がないので根がないとする | 偶数重根では符号が変わらない。$\lvert f\rvert$ の最小点も調べる | $f(x)=x^2$ の例 |
| $x=g(x)$ の変形をどれでも同じとする | 不動点での傾き $\lvert g'(x^*)\rvert$ を見積もって選ぶ | ex-nle-rearrange |
| 重根でも 2 次収束を見込んで回数を見積もる | 誤差の比が $1-\frac1m$ に近づくなら $m$ 重根を疑う | thm-nle-multiple |
連立方程式 $F(x)=0$($F\colon\mathbb{R}^n\to\mathbb{R}^n$)では、Newton 法は Jacobi 行列についての連立 1 次方程式を毎回解く反復になる(Newton法 の定理「多変数のNewton法の局所2次収束」)。Jacobi 行列の計算を省くのが 準Newton法 であり、最適化での Newton 法は BV04 §9.5 にある。
多項式の根をすべて求めるときは、コンパニオン行列 の固有値として計算する方法がある。$x^3-2x-5$ の根は $\begin{pmatrix}0&0&5\\1&0&2\\0&1&0\end{pmatrix}$ の固有値で、$2.09455$ と $-1.04728\pm1.13594\,i$ である。
二分法は Leb26 §3.3 の中間値の定理の証明で使われ、計算の例が同書 Example 3.3.9(p. 134)にある。縮小写像の原理は同書 Theorem 7.6.2(p. 296)にある。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する