非線形連立方程式 | 数値解析 I

1 Newton 法

定義 1.1. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、全微分 $DF(x)$ を標準基底に関する $n$ 次正方行列（Jacobi 行列）と同一視する。 $D_F:=\{x\in U\mid DF(x)\text{ は正則}\}$ と置き、 $x\in D_F$ に対して

N_F(x):=x-DF(x)^{-1}F(x)

と置く。 $s:=N_F(x)-x$ は連立一次方程式 $DF(x)s=-F(x)$ のただ一つの解である。 $s$ を $x$ における Newton 修正量 (Newton step) という。 $x\in D_F$ について、 $N_F(x)=x$ であることと $F(x)=0$ であることは同値である。 $x_0\in U$ とし、 $x_k\in D_F$ であるとき $x_{k+1}:=N_F(x_k)$ と置く。この反復を $F$ に対する Newton 法といい、すべての $k\in\N$ で $x_k\in D_F$ であるとき、Newton 法の反復列 $(x_k)_{k\in\N}$ が定まるという。 $n=1$ のとき $DF(x)$ は $1\times1$ 行列 $(F'(x))$ であり、 $N_F$ は§E20.4 定義 4.1の $N_f$ （ $f=F$ ）に一致する。

命題 1.2. $U$ 、 $F$ 、 $D_F$ 、 $N_F$ を定義 1.1のとおりとし、 $A,S\in M_n(\R)$ を正則行列とする。 $V:=\{z\in\R^n\mid Sz\in U\}$ と置き、 $G\colon V\to\R^n$ を $G(z):=AF(Sz)$ で定める。このとき $V$ は開集合、 $G$ は $C^1$ 級であり、 $z\in V$ に対して $DG(z)=A\,DF(Sz)\,S$ が成り立つ。さらに $D_G=\{z\in V\mid Sz\in D_F\}$ であり、任意の $z\in D_G$ に対して $N_G(z)=S^{-1}N_F(Sz)$ が成り立つ。したがって $x_0=Sz_0$ ならば、 $G$ に対する Newton 法の反復列が $z_0$ から定まることと $F$ に対する Newton 法の反復列が $x_0$ から定まることは同値であり、そのときすべての $k$ で $x_k=Sz_k$ である。

証明. 演習とする（問題 7.1）。▨

2 局所収束

定義 2.1. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とする。 $\R^n$ には Euclid ノルム $\lVert\cdot\rVert_2$ を、 $n$ 次正方行列にはそれに関する作用素ノルム $\lVert\cdot\rVert_2$ を用いる。

$x^*\in U$ が $F(x^*)=0$ を満たし、 $DF(x^*)$ が正則であるとき、 $x^*$ を $F$ の正則零点 (regular zero) という。
$x^*$ を $F$ の正則零点とし、 $r>0$ 、 $\gamma\ge0$ とする。閉球 $\overline B(x^*,r):=\{x\in\R^n\mid\lVert x-x^*\rVert_2\le r\}$ が $U$ に含まれ、任意の $x,y\in\overline B(x^*,r)$ に対して $\lVert DF(x)-DF(y)\rVert_2\le\gamma\lVert x-y\rVert_2$ が成り立つとき、 $x^*$ は半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすという。このとき $\beta:=\lVert DF(x^*)^{-1}\rVert_2,\qquad\kappa:=\beta\lVert DF(x^*)\rVert_2,\qquad\rho:=\min\Bigl\{r,\frac1{2\beta\gamma}\Bigr\},\qquad\rho':=\min\Bigl\{r,\frac1{4\beta\gamma}\Bigr\}$ と置く。ただし $\gamma=0$ のときは $\rho:=\rho':=r$ とする。 $\kappa$ は $DF(x^*)$ の条件数 $\kappa_2(DF(x^*))$ である。

補題 2.2. $n,m\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^m$ を $C^1$ 級の写像とする。 $\R^n$ と $\R^m$ には Euclid ノルム $\lVert\cdot\rVert_2$ を、線形写像 $\R^n\to\R^m$ にはそれらに関する作用素ノルム $\lVert\cdot\rVert_2$ を用いる。 $a\in U$ と $h\in\R^n$ が $\{a+th\mid0\le t\le1\}\subseteq U$ を満たし、 $\gamma\ge0$ が任意の $t\in[0,1]$ に対して $\lVert DF(a+th)-DF(a)\rVert_2\le\gamma t\lVert h\rVert_2$ を満たすならば、

\lVert F(a+h)-F(a)-DF(a)h\rVert_2\le\frac\gamma2\lVert h\rVert_2^2

が成り立つ。

証明. $R:=F(a+h)-F(a)-DF(a)h\in\R^m$ と置く。 $R=0$ ならば主張は成り立つ。 $R\ne0$ とし、 $u:=R/\lVert R\rVert_2\in\R^m$ と置く。 $f\colon U\to\R$ を $f(z):=u^{\mathsf T}F(z)$ で定めると、線形写像 $\R^m\to\R$ 、 $w\mapsto u^{\mathsf T}w$ との合成に§E4.3 定理 1.1を適用して、 $f$ は $C^1$ 級であり $Df(z)k=u^{\mathsf T}DF(z)k$ （ $k\in\R^n$ ）である。§E4.5 定理 1.1を $f$ 、 $r=0$ に適用すると

f(a+h)=f(a)+\int_0^1u^{\mathsf T}DF(a+th)h\,dt

である。 $u^{\mathsf T}DF(a)h=\int_0^1u^{\mathsf T}DF(a)h\,dt$ であるから、

\lVert R\rVert_2=u^{\mathsf T}R=f(a+h)-f(a)-u^{\mathsf T}DF(a)h=\int_0^1u^{\mathsf T}\bigl(DF(a+th)-DF(a)\bigr)h\,dt

である。Cauchy–Schwarz の不等式、 $\lVert u\rVert_2=1$ と§E20.2 補題 1.2 (1)により被積分関数は $\lVert DF(a+th)-DF(a)\rVert_2\lVert h\rVert_2\le\gamma t\lVert h\rVert_2^2$ 以下であり、 $\int_0^1t\,dt=1/2$ から主張を得る。▨

補題 2.3. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとし、 $\beta$ を定義 2.1のとおりとする。 $x\in\overline B(x^*,r)$ が $\beta\gamma\lVert x-x^*\rVert_2<1$ を満たすならば、 $DF(x)$ は正則であり、

\lVert DF(x)^{-1}\rVert_2\le\frac{\beta}{1-\beta\gamma\lVert x-x^*\rVert_2}

が成り立つ。

証明. $B:=DF(x^*)^{-1}DF(x)$ と置くと $I-B=DF(x^*)^{-1}\bigl(DF(x^*)-DF(x)\bigr)$ である。§E20.2 補題 1.2 (1)により行列 $X,Y$ について $\lVert XY\rVert_2\le\lVert X\rVert_2\lVert Y\rVert_2$ であるから、Lipschitz 条件から $q:=\lVert I-B\rVert_2\le\beta\gamma\lVert x-x^*\rVert_2<1$ である。§E4.7 補題 1.1（その作用素ノルムは Euclid ノルムに関するものであり $\lVert\cdot\rVert_2$ に一致する）により $B$ は正則であり、 $\lVert B^{-1}\rVert_2\le1/(1-q)$ である。 $DF(x)=DF(x^*)B$ は正則行列の積であるから正則であり、 $DF(x)^{-1}=B^{-1}DF(x^*)^{-1}$ から $\lVert DF(x)^{-1}\rVert_2\le\beta/(1-q)\le\beta/(1-\beta\gamma\lVert x-x^*\rVert_2)$ である。▨

補題 2.4. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとする。 $x\in\overline B(x^*,r)$ について $DF(x)$ が正則であるとし、 $\hat s\in\R^n$ を任意にとって $\hat r:=DF(x)\hat s+F(x)$ と置く。このとき

\lVert x+\hat s-x^*\rVert_2\le\lVert DF(x)^{-1}\rVert_2\Bigl(\frac\gamma2\lVert x-x^*\rVert_2^2+\lVert\hat r\rVert_2\Bigr)

が成り立つ。

証明. $e:=x-x^*$ と置く。 $\hat s=DF(x)^{-1}(\hat r-F(x))$ と $F(x^*)=0$ から

x+\hat s-x^*=DF(x)^{-1}\bigl(\hat r+(F(x^*)-F(x)-DF(x)(x^*-x))\bigr)

である。 $\overline B(x^*,r)$ は凸であるから、 $t\in[0,1]$ に対して $x+t(x^*-x)\in\overline B(x^*,r)\subseteq U$ であり、Lipschitz 条件から $\lVert DF(x+t(x^*-x))-DF(x)\rVert_2\le\gamma t\lVert e\rVert_2$ である。補題 2.2を $a=x$ 、 $h=x^*-x$ に適用すると $\lVert F(x^*)-F(x)-DF(x)(x^*-x)\rVert_2\le\frac\gamma2\lVert e\rVert_2^2$ であり、主張を得る。▨

定理 2.5. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとする。 $\beta$ 、 $\rho$ を定義 2.1のとおりとする。

任意の $x\in\overline B(x^*,\rho)$ に対して $DF(x)$ は正則であり、 $\lVert N_F(x)-x^*\rVert_2\le\beta\gamma\lVert x-x^*\rVert_2^2\le\frac12\lVert x-x^*\rVert_2$ が成り立つ。
任意の $x_0\in\overline B(x^*,\rho)$ に対して Newton 法の反復列 $(x_k)$ が定まり、すべての $k\in\N$ で $x_k\in\overline B(x^*,\rho)$ であって、 $e_k:=x_k-x^*$ は $\lVert e_{k+1}\rVert_2\le\beta\gamma\lVert e_k\rVert_2^2,\qquad\lVert e_{k+1}\rVert_2\le\frac12\lVert e_k\rVert_2$ を満たし、 $x_k\to x^*$ である。特に $(x_k)$ は $\lVert\cdot\rVert_2$ について $x^*$ へ少なくとも二次で収束する（§E20.4 定義 1.5）。ある $k$ で $x_k=x^*$ ならば、 $j\ge k$ を満たすすべての $j$ で $x_j=x^*$ である。すべての $k$ で $x_k\ne x^*$ ならば、 $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2\to0$ である。

証明.(1)を示す。 $x\in\overline B(x^*,\rho)$ をとり、 $e:=x-x^*$ と置く。 $\rho\le r$ であり、 $\rho$ の定め方から $\beta\gamma\lVert e\rVert_2\le1/2$ である。補題 2.3により $DF(x)$ は正則であり、 $\lVert DF(x)^{-1}\rVert_2\le\beta/(1-1/2)=2\beta$ である。 $N_F(x)=x+s$ 、 $s:=-DF(x)^{-1}F(x)$ であり、 $DF(x)s+F(x)=0$ であるから、補題 2.4を $\hat s=s$ 、 $\hat r=0$ に適用して

\lVert N_F(x)-x^*\rVert_2\le2\beta\cdot\frac\gamma2\lVert e\rVert_2^2=\beta\gamma\lVert e\rVert_2^2\le\frac12\lVert e\rVert_2

を得る。

(2)を示す。 $x_k\in\overline B(x^*,\rho)$ ならば、(1)により $x_k\in D_F$ であって $x_{k+1}=N_F(x_k)$ が定まり、 $\lVert e_{k+1}\rVert_2\le\beta\gamma\lVert e_k\rVert_2^2\le\lVert e_k\rVert_2/2\le\rho$ である。 $x_0\in\overline B(x^*,\rho)$ から、 $k$ に関する帰納法により、反復列が定まり、すべての $k$ で $x_k\in\overline B(x^*,\rho)$ と二つの不等式が成り立つ。 $\lVert e_k\rVert_2\le2^{-k}\lVert e_0\rVert_2$ であるから $x_k\to x^*$ であり、すべての $k$ で $\lVert e_{k+1}\rVert_2\le\beta\gamma\lVert e_k\rVert_2^2$ であるから、 $(x_k)$ は $C=\beta\gamma$ 、 $k_0=0$ について $x^*$ へ少なくとも二次で収束する。 $x^*\in D_F$ かつ $F(x^*)=0$ であるから定義 1.1により $N_F(x^*)=x^*$ であり、 $x_k=x^*$ ならばそれ以後の項はすべて $x^*$ である。すべての $k$ で $x_k\ne x^*$ ならば $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2\le\beta\gamma\lVert e_k\rVert_2\to0$ である。▨

注意 2.6. $n=1$ の場合、§E20.4 定理 4.3は $f$ が $C^2$ 級であることを仮定して、 $e_{k+1}/e_k^2$ が $f''(r)/(2f'(r))$ に収束することを与え、零点の近傍の半径を明示しない。定理 2.5は $F'$ が Lipschitz 連続であることだけを仮定し、半径 $\rho$ と定数 $\beta\gamma$ を $\lvert F'(x^*)\rvert$ と Lipschitz 定数で与えて反復列が少なくとも二次で収束することを示すが、 $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2^2$ の極限の存在は与えない。 $F$ が $C^2$ 級で $\overline B(x^*,r)$ 上 $\lvert F''\rvert\le M$ ならば、平均値の定理により $\gamma=M$ ととることができ、定数 $\beta\gamma=M/\lvert F'(x^*)\rvert$ は漸近定数 $\lvert F''(x^*)\rvert/(2\lvert F'(x^*)\rvert)$ の $2M/\lvert F''(x^*)\rvert$ 倍である（ $F''(x^*)\ne0$ のとき）。

3 残差と誤差

命題 3.1. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとし、 $\beta$ 、 $\rho$ を定義 2.1のとおりとする。任意の $x\in\overline B(x^*,\rho)$ に対して次が成り立つ。

$\lVert x-x^*\rVert_2\le\dfrac43\beta\lVert F(x)\rVert_2$ 。
$\lVert F(x)\rVert_2\le\dfrac54\lVert DF(x^*)\rVert_2\lVert x-x^*\rVert_2$ 。
$F$ の $\overline B(x^*,\rho)$ に属する零点は $x^*$ だけである。

証明. $e:=x-x^*$ 、 $R:=F(x)-DF(x^*)e$ と置く。 $\overline B(x^*,\rho)$ は凸であり、Lipschitz 条件から $t\in[0,1]$ について $\lVert DF(x^*+te)-DF(x^*)\rVert_2\le\gamma t\lVert e\rVert_2$ であるから、補題 2.2を $a=x^*$ 、 $h=e$ に適用し、 $F(x^*)=0$ を用いて $\lVert R\rVert_2\le\frac\gamma2\lVert e\rVert_2^2$ を得る。 $\rho$ の定め方から $\beta\gamma\lVert e\rVert_2\le1/2$ である。

(1)を示す。 $e=DF(x^*)^{-1}(F(x)-R)$ であるから

\lVert e\rVert_2\le\beta\lVert F(x)\rVert_2+\frac{\beta\gamma}2\lVert e\rVert_2^2\le\beta\lVert F(x)\rVert_2+\frac14\lVert e\rVert_2

であり、 $\lVert e\rVert_2\le\frac43\beta\lVert F(x)\rVert_2$ である。

(2)を示す。 $F(x)=DF(x^*)e+R$ と $\gamma\lVert e\rVert_2\le1/(2\beta)$ から $\lVert F(x)\rVert_2\le\bigl(\lVert DF(x^*)\rVert_2+\frac1{4\beta}\bigr)\lVert e\rVert_2$ である。§E20.5 命題 4.4 (2)により $1\le\lVert DF(x^*)\rVert_2\beta$ であるから $1/(4\beta)\le\frac14\lVert DF(x^*)\rVert_2$ であり、主張を得る。

(3)は(1)から従う。▨

例 3.2. $0<\varepsilon\le1$ とし、 $A:=\begin{pmatrix}1&1\\1&1+\varepsilon\end{pmatrix}$ 、 $b:=(2,2+\varepsilon)^{\mathsf T}$ 、 $F(x):=Ax-b$ （ $x\in\R^2$ ）とする。 $DF\equiv A$ は正則であり、 $x^*=(1,1)^{\mathsf T}$ は $F$ の正則零点で、任意の $r>0$ について半径 $r$ 、定数 $\gamma=0$ の Lipschitz 条件を満たすから、 $\rho=r$ である。 $A^{-1}=\varepsilon^{-1}\begin{pmatrix}1+\varepsilon&-1\\-1&1\end{pmatrix}$ は実対称であるから $\lVert A^{-1}\rVert_2$ はその固有値の絶対値の最大値であり、 $\beta=\bigl(2+\varepsilon+\sqrt{4+\varepsilon^2}\bigr)/(2\varepsilon)$ である。 $\sqrt{4+\varepsilon^2}\le2+\varepsilon$ から $\beta\le(2+\varepsilon)/\varepsilon\le3/\varepsilon$ である。 $\hat x:=(2,0)^{\mathsf T}$ では $F(\hat x)=(0,-\varepsilon)^{\mathsf T}$ であり、

\frac{\lVert\hat x-x^*\rVert_2}{\lVert F(\hat x)\rVert_2}=\frac{\sqrt2}{\varepsilon}\ge\frac{\sqrt2}3\beta

である。したがって命題 3.1 (1)の係数 $\frac43\beta$ は、 $\beta$ によらない定数に置き換えることができない。 $\varepsilon=10^{-8}$ では残差のノルムは $10^{-8}$ 、誤差のノルムは $\sqrt2$ である。

4 残差の二乗の下降と後退探索

命題 4.1. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $\phi\colon U\to\R$ を $\phi(x):=\frac12\lVert F(x)\rVert_2^2$ で定める。 $x\in U$ とする。

$\phi$ は $x$ で全微分可能であり、任意の $h\in\R^n$ に対して $D\phi(x)h=F(x)^{\mathsf T}DF(x)h$ が成り立つ。すなわち $\nabla\phi(x)=DF(x)^{\mathsf T}F(x)$ である。
$DF(x)$ が正則で $F(x)\ne0$ ならば、Newton 修正量 $s:=-DF(x)^{-1}F(x)$ は $D\phi(x)s=-\lVert F(x)\rVert_2^2=-2\phi(x)<0$ を満たす。
$F(x)\ne0$ とし、 $0\le\eta<1$ とする。 $\hat s\in\R^n$ が $\lVert DF(x)\hat s+F(x)\rVert_2\le\eta\lVert F(x)\rVert_2$ を満たすならば、 $D\phi(x)\hat s\le-(1-\eta)\lVert F(x)\rVert_2^2<0$ である。
$\nabla\phi(x)=0$ かつ $F(x)\ne0$ ならば、 $DF(x)$ は正則でない。

証明. $g\colon\R^n\to\R$ を $g(y):=\frac12\lVert y\rVert_2^2$ で定めると、 $g(y+k)-g(y)-y^{\mathsf T}k=\frac12\lVert k\rVert_2^2$ であるから、 $g$ は全微分可能で $Dg(y)k=y^{\mathsf T}k$ である。 $\phi=g\circ F$ に§E4.3 定理 1.1を適用して(1)を得る。

(2)は(1)に $DF(x)s=-F(x)$ を代入して得る。

(3)を示す。 $\hat r:=DF(x)\hat s+F(x)$ と置くと、(1)と Cauchy–Schwarz の不等式により

D\phi(x)\hat s=F(x)^{\mathsf T}(\hat r-F(x))\le\lVert F(x)\rVert_2\lVert\hat r\rVert_2-\lVert F(x)\rVert_2^2\le-(1-\eta)\lVert F(x)\rVert_2^2

である。

(4)を示す。 $DF(x)^{\mathsf T}F(x)=0$ かつ $F(x)\ne0$ であるから $DF(x)^{\mathsf T}$ は正則でなく、したがって $DF(x)$ も正則でない。▨

定義 4.2. $U$ 、 $F$ 、 $\phi$ を命題 4.1のとおりとし、 $c_1,\tau\in(0,1)$ を固定する。 $x\in U$ 、 $s\in\R^n$ が $D\phi(x)s<0$ を満たすとする。

実数 $\alpha>0$ が $x+\alpha s\in U$ と $\phi(x+\alpha s)\le\phi(x)+c_1\alpha\,D\phi(x)s$ を満たすとき、 $\alpha$ は $x$ と $s$ について Armijo 条件 (Armijo condition) を満たすという。
$j=0,1,2,\dots$ の順に $\alpha=\tau^j$ が Armijo 条件を満たすかを調べ、初めて満たす $\tau^j$ を出力する手続きを後退探索 (backtracking line search) という。
$x_0\in U$ とする。 $x_k\in U$ について $DF(x_k)$ が正則かつ $F(x_k)\ne0$ であるとき、 $s_k:=-DF(x_k)^{-1}F(x_k)$ と、 $x_k$ と $s_k$ についての後退探索の出力 $\alpha_k$ から $x_{k+1}:=x_k+\alpha_ks_k$ と置く。 $F(x_k)=0$ ならば $x_k$ を出力して停止する。この反復を減衰 Newton 法 (damped Newton method) という。

命題 4.1 (2)により $D\phi(x_k)s_k<0$ であるから、3 の後退探索は 2 の仮定を満たす点と方向に対して行われる。

命題 4.3.定義 4.2の記号と仮定の下で、 $\bar\alpha>0$ が存在して、任意の $\alpha\in(0,\bar\alpha]$ は $x$ と $s$ について Armijo 条件を満たす。したがって後退探索は、 $\tau^j\le\bar\alpha$ を満たす最小の整数 $j\ge0$ を $\bar j$ として、高々 $\bar j+1$ 回の判定で停止し、出力 $\alpha$ は $\alpha\ge\min\{1,\tau\bar\alpha\}$ を満たす。

証明. $U$ は開集合であるから、 $\varepsilon>0$ が存在して $\lvert t\rvert<\varepsilon$ ならば $x+ts\in U$ である。 $\psi(t):=\phi(x+ts)$ （ $\lvert t\rvert<\varepsilon$ ）と置くと、§E4.3 定理 1.1と命題 4.1 (1)により $\psi$ は $0$ で微分可能であり $\psi'(0)=D\phi(x)s<0$ である。 $c_1<1$ から $\psi'(0)<c_1\psi'(0)$ であり、 $(\psi(\alpha)-\psi(0))/\alpha\to\psi'(0)$ （ $\alpha\to+0$ ）であるから、 $\bar\alpha\in(0,\varepsilon)$ が存在して、任意の $\alpha\in(0,\bar\alpha]$ に対して $(\psi(\alpha)-\psi(0))/\alpha\le c_1\psi'(0)$ 、すなわち $\phi(x+\alpha s)\le\phi(x)+c_1\alpha D\phi(x)s$ であり、 $x+\alpha s\in U$ である。 $0<\tau<1$ から $\bar j$ は存在し、 $\tau^{\bar j}$ は Armijo 条件を満たすから、後退探索は $j\le\bar j$ で停止する。停止した $j$ が $j\ge1$ ならば $j-1<\bar j$ から $\tau^{j-1}>\bar\alpha$ であり、 $\tau^j>\tau\bar\alpha$ である。▨

命題 4.4. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとし、 $\beta$ 、 $\kappa$ 、 $\rho$ を定義 2.1のとおりとする。 $\phi$ を命題 4.1のとおりとし、 $0<c_1<1/2$ とする。 $x\in\overline B(x^*,\rho)$ が $F(x)\ne0$ と

\frac53\kappa\beta\gamma\lVert x-x^*\rVert_2\le\sqrt{1-2c_1}

を満たすならば、 $\alpha=1$ は $x$ と Newton 修正量 $s=-DF(x)^{-1}F(x)$ について Armijo 条件を満たす。したがって $x$ での後退探索の出力は $1$ であり、 $x$ からの減衰 Newton 法の一段は Newton 法の一段 $N_F(x)$ に一致する。

証明. 演習とする（問題 7.2）。▨

5 線形系の誤差と停止条件

定義 5.1. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $(\eta_k)_{k\in\N}$ を $[0,1)$ の数列とする。 $U$ の点列 $(x_k)_{k\in\N}$ が、すべての $k$ について

\lVert DF(x_k)(x_{k+1}-x_k)+F(x_k)\rVert_2\le\eta_k\lVert F(x_k)\rVert_2

を満たすとき、 $(x_k)$ を $(\eta_k)$ に関する非厳密 Newton 法 (inexact Newton method) の反復列といい、 $\hat s_k:=x_{k+1}-x_k$ と書く。 $DF(x_k)$ が正則ならば、左辺のノルムの中のベクトルは連立一次方程式 $DF(x_k)s=-F(x_k)$ の近似解 $\hat s_k$ の残差の符号を変えたものであり、Newton 法の反復列は $\eta_k=0$ （ $k\in\N$ ）に関する非厳密 Newton 法の反復列である。

定理 5.2. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $x^*$ を $F$ の正則零点で半径 $r$ 、定数 $\gamma$ の Lipschitz 条件を満たすものとする。 $\beta$ 、 $\kappa$ 、 $\rho'$ を定義 2.1のとおりとし、 $(\eta_k)$ を $[0,1/(5\kappa)]$ の数列とする。 $(x_k)$ を $\R^n$ の点列で、 $x_0\in\overline B(x^*,\rho')$ であり、 $x_k\in U$ を満たす各 $k$ について $\lVert DF(x_k)(x_{k+1}-x_k)+F(x_k)\rVert_2\le\eta_k\lVert F(x_k)\rVert_2$ を満たすものとする。 $e_k:=x_k-x^*$ 、 $\hat s_k:=x_{k+1}-x_k$ と置く。

すべての $k\in\N$ で $x_k\in\overline B(x^*,\rho')$ かつ $DF(x_k)$ は正則であり、 $(x_k)$ は $(\eta_k)$ に関する非厳密 Newton 法の反復列である。さらに $\lVert e_{k+1}\rVert_2\le\frac23\beta\gamma\lVert e_k\rVert_2^2+\frac53\kappa\eta_k\lVert e_k\rVert_2\le\frac12\lVert e_k\rVert_2$ が成り立つ。特に $x_k\to x^*$ である。
$\eta_k\to0$ であり、すべての $k$ で $x_k\ne x^*$ ならば、 $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2\to0$ である。
$K\ge0$ について、すべての $k$ で $\eta_k\le K\lVert F(x_k)\rVert_2$ ならば、すべての $k$ で $\lVert e_{k+1}\rVert_2\le\Bigl(\frac23\beta\gamma+\frac{25}{12}\kappa K\lVert DF(x^*)\rVert_2\Bigr)\lVert e_k\rVert_2^2$ が成り立つ。

証明.(1)を示す。 $x_k\in\overline B(x^*,\rho')$ とする。 $\rho'\le\rho\le r$ であるから $x_k\in U$ であり、 $\beta\gamma\lVert e_k\rVert_2\le1/4$ である。補題 2.3により $DF(x_k)$ は正則であり $\lVert DF(x_k)^{-1}\rVert_2\le\frac43\beta$ である。補題 2.4を $x=x_k$ 、 $\hat s=\hat s_k$ に適用し、 $\lVert DF(x_k)\hat s_k+F(x_k)\rVert_2\le\eta_k\lVert F(x_k)\rVert_2$ と命題 3.1 (2)を用いると

\lVert e_{k+1}\rVert_2\le\frac43\beta\Bigl(\frac\gamma2\lVert e_k\rVert_2^2+\eta_k\cdot\frac54\lVert DF(x^*)\rVert_2\lVert e_k\rVert_2\Bigr)=\frac23\beta\gamma\lVert e_k\rVert_2^2+\frac53\kappa\eta_k\lVert e_k\rVert_2

である。 $\frac23\beta\gamma\lVert e_k\rVert_2\le\frac16$ 、 $\frac53\kappa\eta_k\le\frac13$ であるから右辺は $\frac12\lVert e_k\rVert_2$ 以下であり、 $x_{k+1}\in\overline B(x^*,\rho')$ である。 $x_0\in\overline B(x^*,\rho')$ から、 $k$ に関する帰納法によりすべての $k$ で $x_k\in\overline B(x^*,\rho')\subseteq U$ と主張の不等式が成り立ち、 $(x_k)$ は非厳密 Newton 法の反復列であって、 $\lVert e_k\rVert_2\le2^{-k}\lVert e_0\rVert_2\to0$ である。

(2)は、(1)の不等式を $\lVert e_k\rVert_2$ で割った $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2\le\frac23\beta\gamma\lVert e_k\rVert_2+\frac53\kappa\eta_k$ の右辺が $0$ に収束することから従う。

(3)は、命題 3.1 (2)による $\eta_k\le K\lVert F(x_k)\rVert_2\le\frac54K\lVert DF(x^*)\rVert_2\lVert e_k\rVert_2$ を(1)の不等式に代入して得る。▨

例 5.3. $n=1$ 、 $U=\R$ 、 $F(x):=x$ とする。 $DF\equiv1$ であり、 $x^*=0$ は $F$ の正則零点で、任意の $r>0$ について半径 $r$ 、定数 $\gamma=0$ の Lipschitz 条件を満たし、 $\beta=\kappa=\lVert DF(x^*)\rVert_2=1$ 、 $\rho'=r$ である。 $r=1$ とし、 $x_0=1$ と $[0,1/5]$ の数列 $(\eta_k)$ について $x_{k+1}:=\eta_kx_k$ と置く。 $\hat s_k=-(1-\eta_k)x_k$ であり、 $DF(x_k)\hat s_k+F(x_k)=\eta_kx_k=\eta_kF(x_k)$ であるから、 $(x_k)$ は定理 5.2の仮定を等号で満たし、 $e_{k+1}=\eta_ke_k$ である。 $\gamma=0$ であるから、定理 5.2 (1)の不等式は $\lvert e_{k+1}\rvert\le\frac53\eta_k\lvert e_k\rvert$ となり、定理 5.2 (3)の不等式は $\lvert e_{k+1}\rvert\le\frac{25}{12}K\lvert e_k\rvert^2$ となる。

$\eta_k=1/5$ ならば $x_k=5^{-k}$ であり、 $\lvert e_{k+1}\rvert/\lvert e_k\rvert=1/5$ はすべての $k$ で等しい。これは定理 5.2 (1)の係数 $\frac53\eta_k=\frac13$ 以下であり、比は $0$ に収束しない。
$\eta_k=1/(5(k+1))$ ならば $\eta_k\to0$ であり、 $x_k=1/(5^kk!)$ 、 $\lvert e_{k+1}\rvert/\lvert e_k\rvert=1/(5(k+1))\to0$ であって、定理 5.2 (2)の結論が成り立つ。一方 $\lvert e_{k+1}\rvert/\lvert e_k\rvert^2=5^{k-1}k!/(k+1)$ は $k=0,1,2,3$ で $1/5$ 、 $1/2$ 、 $10/3$ 、 $75/2$ であり、 $k\to\infty$ で発散するから、 $\lvert e_{k+1}\rvert\le M\lvert e_k\rvert^2$ をすべての $k$ で満たす定数 $M$ は存在しない。
$\eta_k=\frac15\lvert F(x_k)\rvert$ とする。 $x_{k+1}=x_k^2/5$ から $x_k=5^{1-2^k}$ であり、 $x_k$ は正で減少するから $\eta_k\le\frac15$ である。 $\lvert e_{k+1}\rvert=\frac15\lvert e_k\rvert^2$ であり、係数 $\frac15$ は定理 5.2 (3)を $K=\frac15$ で適用した係数 $\frac{25}{12}K=\frac5{12}$ 以下である。

系 5.4.定理 5.2の $F$ 、 $x^*$ 、 $\beta$ 、 $\kappa$ 、 $\rho'$ をとり、 $x_0\in\overline B(x^*,\rho')$ とする。 $x_k\in U$ である各 $k$ について、正則行列 $J_k\in M_n(\R)$ と $\delta_k\ge0$ が $\lVert J_k-DF(x_k)\rVert_2\le\delta_k$ と $\delta_k\lVert J_k^{-1}\rVert_2\le1/(5\kappa)$ を満たし、 $x_{k+1}:=x_k-J_k^{-1}F(x_k)$ と置くとする。このとき $\eta_k:=\delta_k\lVert J_k^{-1}\rVert_2$ について定理 5.2の結論が成り立つ。

証明. $x_k\in U$ ならば、 $\hat s_k:=x_{k+1}-x_k=-J_k^{-1}F(x_k)$ について $DF(x_k)\hat s_k+F(x_k)=(DF(x_k)-J_k)\hat s_k$ であるから、§E20.2 補題 1.2 (1)により $\lVert DF(x_k)\hat s_k+F(x_k)\rVert_2\le\delta_k\lVert J_k^{-1}\rVert_2\lVert F(x_k)\rVert_2$ である。 $\eta_k\le1/(5\kappa)$ であるから、定理 5.2を $(\eta_k)$ と $(x_k)$ に適用することができる。▨

注意 5.5. $F$ が§E20.22 定義 1.1の計算グラフの定める写像であり、 $x$ がその定義域に属するとき、§E20.22 定理 2.2により方向 $e_1,\dots,e_n$ の前進モードの出力は厳密な実数演算で $DF(x)$ の各列に等しい。さらに§E20.22 命題 4.1の費用のモデルの仮定、すなわち加算・減算・乗算の費用をそれぞれ $1$ と数え、各節点の値とその局所偏導関数をあわせてその節点の値の計算の費用 $t_k$ の $C$ 倍以下で計算することができるという仮定の下で、 $F(x)$ の評価の費用を $T:=\sum_kt_k$ とすると、§E20.22 命題 4.1 (3)により方向 $e_1,\dots,e_n$ の前進モードの費用の総和は $(C+2n)T$ 以下である。この場合、厳密な実数演算では系 5.4の $\delta_k$ を $0$ とすることができる。前進モードを浮動小数点演算で実行したときの誤差と、差分で $DF(x_k)$ を近似したときの誤差は、系 5.4では $\delta_k$ の値として現れ、 $\delta_k\lVert J_k^{-1}\rVert_2\to0$ ならば定理 5.2 (2)により超線形の評価が、ある $K'\ge0$ について $\delta_k\lVert J_k^{-1}\rVert_2\le K'\lVert F(x_k)\rVert_2$ ならば定理 5.2 (3)により二次の評価が成り立つ。

定義 5.6. $n\in\NN$ 、 $U\subseteq\R^n$ を開集合、 $F\colon U\to\R^n$ を $C^1$ 級の写像とし、 $F$ に対する非厳密 Newton 法の反復列 $(x_k)$ を考えて、実数 $\tau_F\ge0$ 、 $\tau_s\ge0$ をとる。

$\lVert F(x_k)\rVert_2\le\tau_F$ が成り立つ最初の $k$ で $x_k$ を出力する判定を、残差判定という。
$\lVert x_{k+1}-x_k\rVert_2\le\tau_s$ が成り立つ最初の $k$ で $x_{k+1}$ を出力する判定を、修正量判定という。
各 $k$ で連立一次方程式 $DF(x_k)s=-F(x_k)$ の近似解を生成する反復について、 $\lVert DF(x_k)\hat s+F(x_k)\rVert_2\le\eta_k\lVert F(x_k)\rVert_2$ を満たす最初の近似解 $\hat s$ を $\hat s_k$ とする判定を、線形系の相対残差判定という。

$n=1$ のとき、残差判定は§E20.4 定義 6.1 (1)に、 $\tau_{\mathrm{rel}}=0$ の§E20.4 定義 6.1 (2)は修正量判定を一段ずらしたものに一致する。

命題 5.7.定理 5.2の仮定と記号の下で、各 $k\in\N$ について次が成り立つ。

$\lVert x_k-x^*\rVert_2\le\frac43\beta\lVert F(x_k)\rVert_2$ である。特に残差判定が $x_k$ で成り立つならば $\lVert x_k-x^*\rVert_2\le\frac43\beta\tau_F$ である。
$\frac23\lVert\hat s_k\rVert_2\le\lVert x_k-x^*\rVert_2\le2\lVert\hat s_k\rVert_2$ であり、 $\lVert x_{k+1}-x^*\rVert_2\le\frac83\beta\gamma\lVert\hat s_k\rVert_2^2+\frac{10}3\kappa\eta_k\lVert\hat s_k\rVert_2$ である。特に修正量判定が $k$ で成り立つならば、 $\lVert x_{k+1}-x^*\rVert_2\le\frac83\beta\gamma\tau_s^2+\frac{10}3\kappa\eta_k\tau_s$ である。
$F(x_k)\ne0$ ならば、Newton 修正量 $s_k:=-DF(x_k)^{-1}F(x_k)$ について $\frac{\lVert\hat s_k-s_k\rVert_2}{\lVert s_k\rVert_2}\le\kappa_2(DF(x_k))\,\eta_k$ である。

証明.(1)は、定理 5.2 (1)による $x_k\in\overline B(x^*,\rho')\subseteq\overline B(x^*,\rho)$ に命題 3.1 (1)を適用して得る。

(2)を示す。 $e_k:=x_k-x^*$ と置くと $e_k=e_{k+1}-\hat s_k$ である。定理 5.2 (1)の $\lVert e_{k+1}\rVert_2\le\frac12\lVert e_k\rVert_2$ から $\lVert e_k\rVert_2\le\lVert\hat s_k\rVert_2+\frac12\lVert e_k\rVert_2$ 、 $\lVert\hat s_k\rVert_2\le\lVert e_k\rVert_2+\lVert e_{k+1}\rVert_2\le\frac32\lVert e_k\rVert_2$ であり、両側の評価を得る。 $\lVert e_k\rVert_2\le2\lVert\hat s_k\rVert_2$ を定理 5.2 (1)の不等式に代入して $\lVert e_{k+1}\rVert_2$ の評価を得る。

(3)を示す。定理 5.2 (1)により $DF(x_k)$ は正則である。§E20.5 命題 4.5を $A=DF(x_k)$ 、 $b=-F(x_k)\ne0$ 、 $\widehat x=\hat s_k$ に適用すると、 $A^{-1}b=s_k$ 、 $b-A\hat s_k=-(DF(x_k)\hat s_k+F(x_k))$ であり、その相対残差は $\eta_k$ 以下であるから主張を得る。▨

注意 5.8.命題 5.7の係数 $\beta$ 、 $\gamma$ 、 $\kappa$ と、 $x_0\in\overline B(x^*,\rho')$ という仮定は、未知の零点 $x^*$ における量であり、反復の中で計算される量ではない。命題 5.7 (3)は $DF(x_k)$ が正則であることだけを用い、線形系の相対残差 $\eta_k$ は $\hat s_k$ を得た後に計算することができる。零点で Jacobi 行列が正則でない場合には残差判定の誤差が $\sqrt{\tau_F}$ の程度になり（例 6.2）、零点が存在しない場合にも修正量判定は成り立ちうる（例 6.4）。

注意 5.9. 変数の成分と方程式の成分が異なる単位をもつとき、正則行列 $W_x$ 、 $W_F$ （たとえば正の対角行列）をとり、 $\lVert v\rVert_{W_x}:=\lVert W_xv\rVert_2$ 、 $\lVert w\rVert_{W_F}:=\lVert W_Fw\rVert_2$ によって誤差と残差を測ることができる。命題 1.2を $A=W_F$ 、 $S=W_x^{-1}$ に適用すると、 $G(z):=W_FF(W_x^{-1}z)$ に対する Newton 法の反復列は $z_k=W_xx_k$ であり、 $\lVert z_k-W_xx^*\rVert_2=\lVert x_k-x^*\rVert_{W_x}$ 、 $\lVert G(z_k)\rVert_2=\lVert F(x_k)\rVert_{W_F}$ 、 $DG(z)=W_F\,DF(W_x^{-1}z)\,W_x^{-1}$ である。したがって $G$ に定理 2.5と命題 3.1を適用すると、Newton 法の反復列そのものは変えずに、重み付きのノルムでの誤差と残差について同じ形の評価が成り立ち、その $\beta$ 、 $\gamma$ は $W_x\,DF(x^*)^{-1}W_F^{-1}$ の作用素ノルムと $x\mapsto W_F\,DF(x)\,W_x^{-1}$ の $\lVert\cdot\rVert_{W_x}$ に関する Lipschitz 定数である。残差判定と修正量判定に用いるノルム、非厳密 Newton 法の条件、命題 4.1の $\phi$ は重みに依存し、したがって減衰 Newton 法の反復列は重みに依存する。

6 例

例 6.1. $F\colon\R^2\to\R^2$ を $F(x,y):=\bigl(x^2+y^2-4,\ (x-2)^2+y^2-4\bigr)$ とする。 $F$ の零点は $(1,\sqrt3)$ と $(1,-\sqrt3)$ であり、

DF(x,y)=\begin{pmatrix}2x&2y\\2x-4&2y\end{pmatrix},\qquad\det DF(x,y)=8y

であるから、 $D_F=\{(x,y)\mid y\ne0\}$ である。 $A:=\begin{pmatrix}1&0\\1&-1\end{pmatrix}$ について $AF(x,y)=(x^2+y^2-4,\ 4x-4)$ であり、命題 1.2（ $S=I$ ）により $F$ と $AF$ の Newton 法の反復列は一致する。 $AF$ の Newton 修正量 $(s_x,s_y)$ は $4s_x=-(4x-4)$ と $2xs_x+2ys_y=-(x^2+y^2-4)$ を満たすから、 $y\ne0$ に対して

N_F(x,y)=\Bigl(1,\ \frac{y^2+(x-1)^2+3}{2y}\Bigr)

である。 $y_0>0$ ならば $x_1=(1,y_1)$ 、 $y_1>0$ であり、 $k\ge1$ では $y_{k+1}=(y_k+3/y_k)/2$ である。 $y_{k+1}-\sqrt3=(y_k-\sqrt3)^2/(2y_k)\ge0$ であるから $k\ge2$ で $y_k\ge\sqrt3$ であり、 $y_k\ge\sqrt3$ ならば $0\le y_{k+1}-\sqrt3\le(y_k-\sqrt3)/2$ である。したがって $x_k\to(1,\sqrt3)$ である。 $N_F(x,-y)$ は $N_F(x,y)$ の第二成分の符号を変えたものであるから、 $y_0<0$ ならば $x_k\to(1,-\sqrt3)$ である。 $y_0=0$ ならば $DF(x_0)$ は正則でなく、 $x_1$ は定まらない。収束先は $y_0$ の符号で決まる。

$x^*=(1,\sqrt3)$ で定理 2.5の定数を求める。 $DF(p)-DF(q)=2\begin{pmatrix}1\\1\end{pmatrix}(p-q)^{\mathsf T}$ であるから $\lVert DF(p)-DF(q)\rVert_2=2\sqrt2\lVert p-q\rVert_2$ であり、任意の $r>0$ について $\gamma=2\sqrt2$ である。 $DF(x^*)=\begin{pmatrix}2&2\sqrt3\\-2&2\sqrt3\end{pmatrix}$ の二つの列は直交し、そのノルムは $2\sqrt2$ と $2\sqrt6$ であるから、 $DF(x^*)$ の特異値は $2\sqrt6$ と $2\sqrt2$ であり、 $\beta=1/(2\sqrt2)$ 、 $\lVert DF(x^*)\rVert_2=2\sqrt6$ 、 $\kappa=\sqrt3$ である。 $\beta\gamma=1$ であるから、 $r=1/2$ として $\rho=1/2$ であり、 $\lVert x_0-x^*\rVert_2\le1/2$ ならば $\lVert e_{k+1}\rVert_2\le\lVert e_k\rVert_2^2$ である。 $y_0>0$ を満たす任意の $x_0$ から反復列は $x^*$ に収束するので、半径 $\rho$ は収束のための十分条件を与える。

$x_0=(2,1)$ から有理数演算で計算すると、 $x_1=(1,5/2)$ 、 $x_2=(1,37/20)$ 、 $x_3=(1,2569/1480)$ 、 $x_4=(1,13170961/7604240)$ であり、誤差のノルムは十進 50 桁で計算して

\lVert e_0\rVert_2\approx1.24,\quad\lVert e_1\rVert_2\approx7.68\times10^{-1},\quad\lVert e_2\rVert_2\approx1.18\times10^{-1},\quad\lVert e_3\rVert_2\approx3.76\times10^{-3},\quad\lVert e_4\rVert_2\approx4.07\times10^{-6},\quad\lVert e_5\rVert_2\approx4.79\times10^{-12}

である。 $x_0$ と $x_1$ は $\overline B(x^*,1/2)$ に属さず、 $x_2$ から先は属し、 $k\ge2$ で $\lVert e_{k+1}\rVert_2\le\lVert e_k\rVert_2^2$ を満たす。 $k=1,\dots,4$ の $\lVert e_{k+1}\rVert_2/\lVert e_k\rVert_2^2$ は約 $0.200$ 、 $0.270$ 、 $0.288$ 、 $0.2887$ であり、 $f(y)=y^2-3$ の Newton 法である $y_{k+1}=(y_k+3/y_k)/2$ の十分先の項から始まる列に§E20.4 定理 4.3 (2)を適用した極限 $1/(2\sqrt3)\approx0.2887$ に近づく。

例 6.2. $F\colon\R^2\to\R^2$ を $F(x,y):=\bigl(x^2+y^2-1,\ (x-2)^2+y^2-1\bigr)$ とする。二つの円は点 $(1,0)$ で接し、 $F$ の零点は $x^*=(1,0)$ だけである。 $DF(x^*)=\begin{pmatrix}2&0\\-2&0\end{pmatrix}$ は正則でなく、 $x^*$ は正則零点でない。 $\lVert DF(p)-DF(q)\rVert_2=2\sqrt2\lVert p-q\rVert_2$ は例 6.1と同じであり、破れる仮定は $DF(x^*)$ の正則性だけである。

例 6.1と同じく $AF(x,y)=(x^2+y^2-1,\ 4x-4)$ を用いると、 $y\ne0$ に対して $N_F(x,y)=\bigl(1,\ (y^2+(x-1)^2)/(2y)\bigr)$ である。 $x_0=(2,1)$ から $x_1=(1,1)$ であり、 $k\ge1$ で $y_{k+1}=y_k/2$ であるから $x_k=(1,2^{-(k-1)})$ である。したがって $k\ge1$ で

\lVert e_{k+1}\rVert_2=\frac12\lVert e_k\rVert_2,\qquad\lVert F(x_k)\rVert_2=\sqrt2\,\lVert e_k\rVert_2^2,\qquad\lVert x_{k+1}-x_k\rVert_2=\frac12\lVert e_k\rVert_2

であり、反復列は $x^*$ に線形収束する。比 $1/2$ は、 $y$ についての方程式 $y^2=0$ に§E20.4 命題 4.6を $m=2$ で適用した漸近定数 $(m-1)/m$ である。

残差は誤差の二乗に比例する。残差判定を $\tau_F=10^{-12}$ で行うと、 $\sqrt2\cdot4^{-(k-1)}\le10^{-12}$ を満たす最初の $k$ は $22$ であり、出力の誤差は $2^{-21}\approx4.77\times10^{-7}$ である。修正量との間では $\lVert e_k\rVert_2=2\lVert x_{k+1}-x_k\rVert_2$ が成り立つが、次の反復の誤差は $\lVert e_{k+1}\rVert_2=\lVert x_{k+1}-x_k\rVert_2$ であり、命題 5.7 (2)の修正量の二乗による評価は成り立たない。

例 6.3.例 6.1の $F$ に対して、 $x_0=(3,1/10)$ から $c_1=10^{-4}$ 、 $\tau=1/2$ の減衰 Newton 法を有理数演算で実行する。 $x_0$ での Newton 修正量は $s_0=(-2,\ 699/20)$ であり、 $\phi(x_0)=170201/10000\approx17.0$ 、 $\phi(x_0+s_0)\approx1.50\times10^6$ であるから、 $\alpha=1$ は Armijo 条件を満たさない。後退探索の出力 $\alpha_k$ と $\phi(x_k)$ は次のとおりである（値は有理数から十進に丸めて示す）。

\begin{array}{c|cccccc} k&0&1&2&3&4&5\\\hline x_k&(3,\ 0.1)&(2.984,\ 0.373)&(2.860,\ 0.943)&(2.395,\ 1.682)&(1,\ 2.312)&(1,\ 1.805)\\ \phi(x_k)&1.70\times10^{1}&1.69\times10^{1}&1.57\times10^{1}&1.09\times10^{1}&5.49&6.60\times10^{-2}\\ \alpha_k&1/128&1/16&1/4&1&1&1 \end{array}

$k\ge3$ ではすべて $\alpha_k=1$ であり、 $\phi(x_6)\approx2.57\times10^{-5}$ 、 $\phi(x_7)\approx4.57\times10^{-12}$ 、 $\phi(x_8)\approx1.45\times10^{-25}$ である。 $\phi(x_k)$ は各段で減少する。同じ $x_0$ からの Newton 法では $x_1=(1,\ 701/20)$ 、 $\phi(x_1)\approx1.50\times10^6$ であり、以後 $y_k$ は $x^*=(1,\sqrt3)$ に向かって減少し、 $\phi(x_9)\approx1.46\times10^{-20}$ である。 $\kappa=\sqrt3$ 、 $\beta\gamma=1$ であるから、命題 4.4の条件は $\lVert x-x^*\rVert_2\le\sqrt{1-2c_1}/(\frac53\sqrt3)\approx0.346$ であり、 $\lVert x_5-x^*\rVert_2\approx7.3\times10^{-2}$ を満たす $x_5$ 以後で $\alpha_k=1$ が保証される。 $k=3,4$ の $\alpha_k=1$ はこの条件の外で受理された。

例 6.4. 次の二つの写像は、 $\phi=\frac12\lVert F\rVert_2^2$ の停留点で $F\ne0$ となる点をもつ。

例 6.1の $F$ について、 $x$ 軸上の点 $(x,0)$ ではすべて $DF(x,0)$ は正則でなく、Newton 修正量は定まらない。 $\nabla\phi(x,0)=DF(x,0)^{\mathsf T}F(x,0)$ の第二成分は $2y\bigl(F_1+F_2\bigr)\big|_{y=0}=0$ である。 $(1,0)$ では $F(1,0)=(-3,-3)$ 、 $DF(1,0)^{\mathsf T}F(1,0)=(2\cdot(-3)-2\cdot(-3),\ 0)=0$ であり、 $(1,0)$ は $F$ の零点が存在するにもかかわらず $\phi$ の停留点で $F\ne0$ となる点である。

$F\colon\R^2\to\R^2$ を $F(x,y):=\bigl(x^2+y^2-1,\ (x-3)^2+y^2-1\bigr)$ とする。 $F_1+F_2=2(x-3/2)^2+2y^2+5/2$ であり、 $\phi\ge\frac14(F_1+F_2)^2\ge25/16$ であるから $F$ は零点をもたず、 $\phi$ の最小値 $25/16$ は $(3/2,0)$ でだけとられる。 $(3/2,0)$ では $F=(5/4,5/4)$ であり、 $DF(3/2,0)=\begin{pmatrix}3&0\\-3&0\end{pmatrix}$ は正則でない。

例 6.1と同じく $AF(x,y)=(x^2+y^2-1,\ 6x-9)$ （ $A=\begin{pmatrix}1&0\\1&-1\end{pmatrix}$ ）を用いると、 $y\ne0$ での Newton 修正量は $s_x=3/2-x$ 、 $s_y=-(x^2+y^2-1+2xs_x)/(2y)$ である。 $x_0=(0,1)$ から $c_1=10^{-4}$ 、 $\tau=1/2$ の減衰 Newton 法を有理数演算で実行すると、 $\alpha_0=1$ 、 $x_1=(3/2,1)$ であり、 $s_x=0$ から、 $y_k\ne0$ である限り $x_k=(3/2,y_k)$ 、 $s_y=-(y_k^2+5/4)/(2y_k)$ である。 $y_k$ が $0$ でない有理数ならば、後退探索の出力は $j\in\N$ について $\alpha_k=2^{-j}$ であり、 $y_{k+1}=y_k-\alpha_k(y_k^2+5/4)/(2y_k)$ が $0$ になるのは $\alpha_k(4y_k^2+5)=8y_k^2$ 、すなわち $y_k^2=5/\bigl(4(2^{j+1}-1)\bigr)$ のときに限る。 $m:=j+1$ について $5(2^m-1)$ は、 $m=1$ では $5$ であり、 $m\ge2$ では $4$ で割ると $3$ 余るから、平方数でない。したがって $5/\bigl(4(2^m-1)\bigr)$ は有理数の平方でなく、 $y_{k+1}$ は $0$ でない有理数である。 $y_1=1$ から、 $k$ に関する帰納法によりすべての $k\ge1$ で $y_k$ は $0$ でない有理数であり、 $F$ は零点をもたないから、各段で $DF(x_k)$ は正則かつ $F(x_k)\ne0$ であって、反復は停止せずに続く。 $\phi(3/2,y)=(5/4+y^2)^2$ であり、Armijo 条件と $D\phi(x_k)s_k<0$ から $\phi(x_{k+1})<\phi(x_k)$ であるから $\lvert y_{k+1}\rvert<\lvert y_k\rvert$ であり、 $s_y$ は $y_k$ と逆の符号をもつから $\alpha_k\lvert s_y\rvert<2\lvert y_k\rvert$ 、すなわち $\alpha_k<4y_k^2/(y_k^2+5/4)$ （ $k\ge1$ ）である。また $\lVert F(x_k)\rVert_2^2=2\phi(x_k)\ge25/8$ であるから、Armijo 条件と命題 4.1 (2)により $c_1\alpha_k\cdot25/8\le\phi(x_k)-\phi(x_{k+1})$ であり、右辺の $k$ についての和は $\phi(x_0)-25/16$ 以下であるから $\alpha_k\to0$ である。

$k\ge1$ での修正量は $\lVert x_{k+1}-x_k\rVert_2=\alpha_k\lvert s_y\rvert$ である。 $\lvert y_k\rvert$ （ $k\ge1$ ）は減少して極限 $L\ge0$ をもつ。 $L>0$ ならば、 $L\le\lvert y_k\rvert\le y_1$ から $\lvert s_y\rvert\le(y_1^2+5/4)/(2L)$ であり、 $\alpha_k\to0$ とあわせて修正量は $0$ に収束する。 $L=0$ ならば、修正量は $2\lvert y_k\rvert$ 未満であるから $0$ に収束する。したがってこの反復では、任意の $\tau_s>0$ に対して修正量判定は有限の $k$ で成り立つが、 $F$ は零点をもたない。

計算では $y_2=-1/8$ 、 $y_3\approx3.32\times10^{-2}$ 、 $y_4\approx-3.59\times10^{-3}$ 、 $y_{13}\approx1.71\times10^{-8}$ 、 $\alpha_{13}=2^{-50}$ であり、反復列は $\phi$ の停留点 $(3/2,0)$ に近づく。

7 演習

問題 7.1.命題 1.2の証明を完成させよ。

解答.

$z\mapsto Sz$ は連続であり $V$ は開集合 $U$ の逆像であるから、 $V$ は開集合である。 $z\mapsto Sz$ と $w\mapsto Aw$ は線形写像であって全微分がそれぞれ $S$ 、 $A$ であるから、§E4.3 定理 1.1により $G$ は全微分可能で $DG(z)=A\,DF(Sz)\,S$ であり、 $z\mapsto DG(z)$ は連続であるから $G$ は $C^1$ 級である。 $A$ 、 $S$ は正則であるから、 $DG(z)$ が正則であることと $DF(Sz)$ が正則であることは同値であり、 $D_G=\{z\in V\mid Sz\in D_F\}$ である。 $z\in D_G$ に対して

N_G(z)=z-S^{-1}DF(Sz)^{-1}A^{-1}AF(Sz)=S^{-1}\bigl(Sz-DF(Sz)^{-1}F(Sz)\bigr)=S^{-1}N_F(Sz)

である。 $x_k=Sz_k$ とすると、 $z_k\in D_G$ と $x_k\in D_F$ は同値であり、そのとき $z_{k+1}=N_G(z_k)=S^{-1}N_F(x_k)=S^{-1}x_{k+1}$ である。 $x_0=Sz_0$ から、 $k$ に関する帰納法により主張を得る。▨

問題 7.2.命題 4.4の証明を完成させよ。

解答.

$e:=x-x^*$ と置く。定理 2.5 (1)により $DF(x)$ は正則であり、 $\lVert N_F(x)-x^*\rVert_2\le\beta\gamma\lVert e\rVert_2^2\le\frac12\lVert e\rVert_2$ であるから $N_F(x)\in\overline B(x^*,\rho)$ である。命題 3.1 (2)を $N_F(x)$ に、命題 3.1 (1)を $x$ に適用すると

\lVert F(N_F(x))\rVert_2\le\frac54\lVert DF(x^*)\rVert_2\,\beta\gamma\lVert e\rVert_2^2,\qquad\lVert e\rVert_2\le\frac43\beta\lVert F(x)\rVert_2

であり、 $\lVert DF(x^*)\rVert_2\beta=\kappa$ から

\lVert F(N_F(x))\rVert_2\le\frac54\cdot\frac43\kappa\beta\gamma\lVert e\rVert_2\lVert F(x)\rVert_2=\frac53\kappa\beta\gamma\lVert e\rVert_2\lVert F(x)\rVert_2\le\sqrt{1-2c_1}\,\lVert F(x)\rVert_2

である。両辺を二乗して $2$ で割ると $\phi(x+s)\le(1-2c_1)\phi(x)$ である。命題 4.1 (2)により $D\phi(x)s=-2\phi(x)$ であるから、 $\phi(x)+c_1\cdot1\cdot D\phi(x)s=(1-2c_1)\phi(x)$ であり、 $x+s=N_F(x)\in U$ とあわせて、 $\alpha=1$ は Armijo 条件を満たす。後退探索は $j=0$ で停止して $1$ を出力し、減衰 Newton 法の一段は $x+s=N_F(x)$ である。▨

§E20.23非線形連立方程式

1 Newton 法

2 局所収束

3 残差と誤差

4 残差の二乗の下降と後退探索

5 線形系の誤差と停止条件

6 例

7 演習

前提記事