非線形方程式の数値解法

同義語:方程式の数値解法numerical methods for nonlinear equationsroot-finding methods

概要

非線形方程式の数値解法(numerical methods for nonlinear equations)とは、方程式 $f(x)=0$ の解に近づく数列を反復で作り、必要な桁数で止める計算の方法の総称である。二分法は連続性と符号の変化だけで必ず収束して誤差の上界が 1 回で半分になり、不動点反復は不動点での傾きが率を決める。Newton 法は単根で 2 次収束するが、$m$ 重根では率 $1-1/m$ の 1 次収束に落ち、初期値が悪いと発散や巡回も起きる。工学の方程式の計算では、二分法で根を挟みながら Newton 法を試す手順と、残差と誤差を分けた止める判定を使う。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 中間値の定理, 平均値の定理, Taylorの定理, 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$ で成り立つとする。

  1. ある $p\ge1$ と定数 $C$ について $\lvert e_{n+1}\rvert/\lvert e_n\rvert^p\to C$ であるとき、$p=1$ なら $0< C< 1$、$p>1$ なら $0< C< \infty$ を要求して、列は 次数 $p$ で収束する という。$C$ を 漸近誤差定数 という。$p=1$ を 1 次収束、$p=2$ を 2 次収束 ともいい、1 次収束の $C$ を 率 ともいう。
  2. $\lvert e_{n+1}\rvert/\lvert e_n\rvert\to0$ のとき、超 1 次収束 するという。
  3. 整数 $m\ge1$ について、$x^*$ の近くで $f(x)=(x-x^*)^mh(x)$、$h$ は $C^1$ 級で $h(x^*)\ne0$ と書けるとき、$x^*$ を $m$ 重根 といい、$m=1$ のとき 単根 という。

$p=1$ の率 $C$ のもとでは、誤差は 1 回の反復でおよそ $C$ 倍になるので、1 桁増やすのに $\log(1/10)/\log C$ 回ほどかかる。$p=2$ では、$C$ が極端でなければ正しい桁数が 1 回ごとにおよそ 2 倍になる。
各方法を使ってよい条件は次のとおりである。

  • (連続性と符号) 二分法には、$f$ が $[a,b]$ で連続で $f(a)f(b)< 0$ であることが要る。
  • (縮小性) 不動点反復には、$g$ が $[a,b]$ を自分の中へ写し、$\lvert g(x)-g(y)\rvert\le L\lvert x-y\rvert$($L< 1$)を満たすことが要る。$g$ が微分可能なら、$\lvert g'\rvert\le L$ で足りる(平均値の定理)。
  • (なめらかさと単根) Newton 法の 2 次収束には、$f$ が $C^2$ 級で $f'(x^*)\ne0$ であり、初期値が $x^*$ に十分近いことが要る。

公式の表

方法反復使える条件誤差・次数根拠
二分法$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$ は $[a,b]$ にただ 1 つの不動点 $x^*$ をもつ。
  2. 任意の $x_0\in[a,b]$ について、$x_{n+1}=g(x_n)$ は $\lvert x_n-x^*\rvert\le L^n\lvert x_0-x^*\rvert\le L^n(b-a)$ を満たす。
  3. $n\ge1$ で $\lvert x_n-x^*\rvert\le\dfrac{L}{1-L}\lvert x_n-x_{n-1}\rvert$ である。
中間値の定理と等比の評価

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< 1$ なら、ある $\delta>0$ があり、$\lvert x_0-x^*\rvert\le\delta$ なら $x_n\to x^*$ である。すべての $n$ で $x_n\ne x^*$ なら $e_{n+1}/e_n\to g'(x^*)$ である。
  2. $\lvert g'(x^*)\rvert>1$ なら、$x_n\to x^*$ となるのは、ある $n$ で $x_n=x^*$ となる場合に限る。
平均値の定理で 1 歩を比べる

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$ で収束する。

Taylor の定理を当てる

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 法

Newton法 の定理「局所収束と2次収束」は $f'(x^*)\ne0$ を仮定している。$m$ 重根では Newton 法の速さは 1 次に落ち、$m$ を掛ければ 2 次に戻る。次の定理は単根の場合の定数も同時に与える。

重根での Newton 法と修正 Newton 法

$I$ を開区間とし、$x^*\in I$、整数 $m\ge1$、$f(x)=(x-x^*)^mh(x)$、$h$ は $I$ で $C^1$ 級、$h(x^*)\ne0$ とする。$x_n=x^*$ となったら反復を止めることにする。

  1. ある $\delta>0$ があり、$\lvert x_0-x^*\rvert\le\delta$ なら Newton 法の列は定義され、$x_n\to x^*$ である。$m\ge2$ のときはどの $n$ でも $x_n\ne x^*$($x_0\ne x^*$ のとき)で、$e_{n+1}/e_n\to1-\frac1m$ である。
  2. ある $\delta>0$ があり、$\lvert x_0-x^*\rvert\le\delta$ なら $x_{n+1}=x_n-mf(x_n)/f'(x_n)$ の列は定義されて $x_n\to x^*$ であり、どの $n$ でも $x_n\ne x^*$ なら
    $$ \frac{e_{n+1}}{e_n^{\,2}}\longrightarrow\frac{h'(x^*)}{mh(x^*)} $$
    である。
    $m=1$ のとき 2 の反復は Newton 法そのもので、$f$ が $C^2$ 級なら右辺は $\dfrac{f''(x^*)}{2f'(x^*)}$ である。
1 歩を誤差の式として書く

$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 法が効く場面ではその速さが出る。

  1. 根を挟む. 関数の値を何点かで計算し、$f(a)f(b)< 0$ となる $[a,b]$ を探す。見つからないときは区間を広げるか細かく刻む。$f(x)=x^2$ のような偶数重根は符号が変わらないので、この段では見つからない。
  2. 許容誤差を決める. $\mathrm{tol}_x>0$、$\mathrm{tol}_f>0$、反復の上限 $N_{\max}$ を決める。$k:=0$、$[a_0,b_0]:=[a,b]$、$x_0:=\frac{a+b}2$ とする。
  3. 止める判定. $\lvert f(x_k)\rvert\le\mathrm{tol}_f$ か $b_k-a_k\le\mathrm{tol}_x$ なら止めて $x_k$ を返す。$k=N_{\max}$ なら失敗として止める。
  4. 区間を縮める. $f(a_k)f(x_k)< 0$ なら $[a_{k+1},b_{k+1}]:=[a_k,x_k]$、そうでなければ $[x_k,b_k]$ とする。
  5. Newton の 1 歩を試す. $f'(x_k)\ne0$ なら $y:=x_k-f(x_k)/f'(x_k)$ を計算する。$y$ が $a_{k+1}< y< b_{k+1}$ を満たし、$\lvert f(y)\rvert\le\frac12\lvert f(x_k)\rvert$ なら $x_{k+1}:=y$ とする。
  6. だめなら二分する. 5 の条件が満たされないときは $x_{k+1}:=\frac{a_{k+1}+b_{k+1}}2$ とする。$k$ を 1 増やして 3 へ戻る。
    止まった理由によって、結果の読み方を分ける。
    止まった理由分かること確かめること
    $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$

例題

$x^3-2x-5=0$ を 3 つの方法で解く

使う公式: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 つの方法の誤差。横軸は反復の番号、縦軸は対数目盛の誤差 図: 方程式 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$ より大きいと離れていく。

管の摩擦係数(Colebrook の式)

管の中の流れの摩擦係数 $\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 桁以上増える。

2 重根:Newton 法の速さの低下と修正

$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$ である。

3 重根の近くの精度の限界

$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$
2Newton$-1.8$
3Newton$-1.7699481865$
4Newton$-1.7692926629$
5Newton$-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アソシエイト)の紹介料で運営されています。 支援について / 寄付する