§E20.37方程式の精度保証

証明.(1)は、区間演算を選んだ場合には§E20.36 定理 2.3 (2)から、外向き丸めの区間演算を選んだ場合には§E20.36 定理 3.3 (2)から従う。

(2)を示す。和と差の各成分については(1)から従う。$(i,j)$を固定し、$P_1,\dots,P_p$を定義 1.1 (4)の区間とする。(1)により$a_{i1}b_{1j}\in P_1$である。$\sum_{k\le\ell}a_{ik}b_{kj}\in P_\ell$ならば、(1)により$a_{i,\ell+1}b_{\ell+1,j}\in[A]_{i,\ell+1}\odot[B]_{\ell+1,j}$であり、再び(1)により$\sum_{k\le\ell+1}a_{ik}b_{kj}\in P_{\ell+1}$である。$\ell$に関する帰納法により$(AB)_{ij}\in P_p$である。▨

証明.(1)を示す。$y\in\R^n\setminus X$をとると、ある$i$について$y_i\notin X_i$であり、$X_i$は閉区間であるから、$r>0$が存在して$(y_i-r,y_i+r)\cap X_i=\emptyset$である。$z\in\R^n$が$d_\infty(z,y)<r$を満たすならば$|z_i-y_i|<r$であるから$z\notin X$である。$d_\infty\le d_2$であるから、$X$の補集合は$d_\infty$と$d_2$のいずれに関しても開集合であり、$X$は両方の距離に関して閉集合である。$\rho_0:=\bigl(\sum_{i=1}^n(\operatorname{mag}X_i)^2\bigr)^{1/2}$と置くと、$x\in X$に対して$|x_i|\le\operatorname{mag}X_i$であるから$d_2(x,0)\le\rho_0<\rho_0+1$であり、$X$は$d_2$に関して有界である。§E2.9 定理 4.3により$X$はコンパクトである。§E2.5 命題 4.2により$(\R^n,d_\infty)$は完備であり、§E2.5 定理 3.2により$(X,d_\infty)$は完備である。各$X_i$は空でないので$X$は空でない。

(2)を示す。$X_i=[a_i,b_i]$とし、$p_i\colon\R\to X_i$を$p_i(t):=\min\{\max\{t,a_i\},b_i\}$で定め、$P_X\colon\R^n\to X$を$P_X(x):=(p_1(x_1),\dots,p_n(x_n))$で定める。$s,t\in\R$に対して$|\max\{s,a_i\}-\max\{t,a_i\}|\le|s-t|$かつ$|\min\{s,b_i\}-\min\{t,b_i\}|\le|s-t|$であるから、$|p_i(s)-p_i(t)|\le|s-t|$であり、$d_2(P_X(x),P_X(x'))\le d_2(x,x')$である。$x\in X$ならば$P_X(x)=x$である。$\rho:=\rho_0+1$と置き、$D^n:=\{u\in\R^n\mid d_2(u,0)\le1\}$に対して$g\colon D^n\to\R^n$を$g(u):=\rho^{-1}T(P_X(\rho u))$で定める。$T(P_X(\rho u))\in X$であるから$d_2(g(u),0)\le\rho_0/\rho<1$である。$g$は連続写像の合成であるから、$D^n$から$D^n$への連続写像である。§E18.18 定理 2.1により$g(u)=u$を満たす$u\in D^n$が存在する。$x:=\rho u$と置くと$x=T(P_X(x))\in X$であるから$P_X(x)=x$であり、$T(x)=x$が成り立つ。▨

証明.$a,b\in X$、$t\in[0,1]$に対して、各座標$(1-t)a_i+tb_i$は$a_i$と$b_i$の間にあるので$X_i$に属し、$a+t(b-a)\in X$である。$F$は$C^1$級であるから、$t\mapsto\partial_jF_i(a+t(b-a))$は$[0,1]$上で連続であり、$A(a,b)$の各成分の積分は定まる。

(1)を示す。$h:=b-a$と置く。各$F_i\colon U\to\R$は$C^1$級であり、$\{a+th\mid0\le t\le1\}\subset X\subset U$である。§E4.5 定理 1.1を$F_i$と$r=0$に適用し、全微分を偏導関数で$DF_i(y)[h]=\sum_{j=1}^n\partial_jF_i(y)h_j$と表すと

を得る。

(2)を示す。各$t\in[0,1]$で$\partial_jF_i(a+t(b-a))\in[J]_{ij}$であるから、積分の単調性により$\inf[J]_{ij}\le A(a,b)_{ij}\le\sup[J]_{ij}$である。

(3)を示す。補題 2.1 (1)により$X$は$d_2$に関してコンパクトであり、$\partial_jF_i$の$X$への制限は連続であるから、§E2.9 定理 5.1により一様連続である。$\ep>0$に対して、$x,x'\in X$かつ$d_2(x,x')<\delta$ならば$|\partial_jF_i(x)-\partial_jF_i(x')|<\ep$となる$\delta>0$をとる。$b,b'\in X$が$d_2(b,b')<\delta$を満たすならば、各$t\in[0,1]$で$d_2(a+t(b-a),a+t(b'-a))=t\,d_2(b,b')<\delta$であるから、

である。▨

証明.$T_R(x)=x$であることは$RF(x)=0$と同値である。$F(x)=0$ならば$RF(x)=0$であり、$R$が正則ならば$RF(x)=0$から$F(x)=R^{-1}0=0$である。▨

証明.$x\in X$とし、$A:=A(x_0,x)$を補題 2.2の行列とする。補題 2.2 (1)により$F(x)=F(x_0)+A(x-x_0)$であるから

である。補題 2.2 (2)により$A\in[J]$であり、$F(x_0)\in F_0$、$x\in X$であるから、命題 1.2 (2)により$RF(x_0)\in[d]$、$I-RA\in[M]$、$x-x_0\in[e]$である。再び命題 1.2 (2)により$x_0-RF(x_0)\in x_0\ominus[d]$、$(I-RA)(x-x_0)\in[M]\odot[e]$であり、$T_R(x)\in K$である。$x\in X$が$F(x)=0$を満たすならば、補題 3.2により$x=T_R(x)\in K$である。▨

証明.$F$は連続であるから、$T_R$の$X$への制限は$d_2$に関して連続である。定理 3.3により$T_R(X)\subset K\subset X$である。補題 2.1 (2)により$T_R(x^*)=x^*$を満たす$x^*\in X$が存在し、$R$は正則であるから、補題 3.2により$F(x^*)=0$である。▨

証明.(1)を示す。$A\in[J]$とすると、命題 1.2 (2)により$I-RA\in[M]$であるから、各$i,j$について$|(I-RA)_{ij}|\le\operatorname{mag}[M]_{ij}$である。命題 1.2 (1)を加える順に適用すると、$\sum_{j=1}^n\operatorname{mag}[M]_{ij}$は$\bar q_i$を上端とする区間に属するので、$\sum_{j=1}^n|(I-RA)_{ij}|\le\bar q_i\le\bar q$である。§E20.5 補題 3.5 (1)により$\lVert I-RA\rVert_\infty\le\bar q$である。

(2)を示す。$A\in[J]$と$v\in\R^n$が$RAv=0$を満たすとすると、$v=(I-RA)v$であり、作用素ノルムの定義により$\lVert v\rVert_\infty\le q\lVert v\rVert_\infty$である。$q<1$であるから$v=0$であり、$RA$は正則である。$\det R\det A=\det(RA)\ne0$であるから、$R$と$A$は正則である。

(3)を示す。$[J]$の各成分は空でない区間であるから$[J]$は元$A$をもち、$0\le\lVert I-RA\rVert_\infty\le q$から$0\le q<1$である。$x,y\in X$に対して補題 2.2 (1)を$a=y$、$b=x$として適用すると$F(x)-F(y)=A(y,x)(x-y)$であるから、

である。補題 2.2 (2)により$A(y,x)\in[J]$であるから、$\lVert T_R(x)-T_R(y)\rVert_\infty\le q\lVert x-y\rVert_\infty$である。定理 3.3により$T_R(X)\subset K\subset X$であるから、$T_R$の$X$への制限は$(X,d_\infty)$上の縮小比$q$の縮小写像である。補題 2.1 (1)により$(X,d_\infty)$は空でない完備距離空間であるから、§E2.7 定理 2.2により$T_R$は$X$にただ一つの不動点$x^*$をもち、任意の$y_0\in X$から始まる反復列$(y_k)_{k\in\N}$は$X$に属して$x^*$に収束する。(2)により$R$は正則であるから、補題 3.2により$X$における$T_R$の不動点と$F$の零点は一致する。▨

証明.(1)を示す。$x^*,y^*\in X$を$F$の零点とする。補題 2.2 (1)により$0=F(y^*)-F(x^*)=A(x^*,y^*)(y^*-x^*)$であり、補題 2.2 (2)により$A(x^*,y^*)\in[J]$は正則であるから、$y^*=x^*$である。

(2)を示す。$x^*\in X$を$F$の零点とし、$A:=A(x_0,x^*)$と置く。補題 2.2 (1)により$0=F(x^*)=F(x_0)+A(x^*-x_0)$であり、補題 2.2 (2)により$A\in[J]$は正則であるから、$x^*=x_0-A^{-1}F(x_0)\in N$である。

(3)を示す。$x\in X$に対して$A(x_0,x)\in[J]$は正則であるから、$H(x):=x_0-A(x_0,x)^{-1}F(x_0)$と置くと$H(x)\in N\subset\widehat N\subset X$である。$\R^n$に Euclid ノルム$\lVert\cdot\rVert_2$を入れ、$M_n(\R)$の元にその作用素ノルム$\lVert\cdot\rVert_{\mathrm{op}}$を入れる。行列$Y=(y_{ij})$と$\lVert h\rVert_2\le1$について、Cauchy–Schwarz の不等式により$|(Yh)_i|\le\sqrt n\max_{i,j}|y_{ij}|$であるから、$\lVert Y\rVert_{\mathrm{op}}\le n\max_{i,j}|y_{ij}|$である。$x'\in X$を固定し、$B':=A(x_0,x')$、$\beta:=\lVert B'^{-1}\rVert_{\mathrm{op}}$と置き、$0<\eta\le1/(2\beta)$をとる。補題 2.2 (3)により、$\delta>0$が存在して、$x\in X$が$d_2(x,x')<\delta$を満たすならば$B:=A(x_0,x)$の各成分は$|b_{ij}-b'_{ij}|<\eta/n$を満たし、$\lVert B-B'\rVert_{\mathrm{op}}<\eta$である。作用素ノルムの定義から従う不等式$\lVert YZ\rVert_{\mathrm{op}}\le\lVert Y\rVert_{\mathrm{op}}\lVert Z\rVert_{\mathrm{op}}$と$\lVert Yv\rVert_2\le\lVert Y\rVert_{\mathrm{op}}\lVert v\rVert_2$により