特異な非対称差分行列の
SOR
法
大阪女子大学 石原和夫
(Kazuo Ishihara)
1. SOR
法. $A=D-L-U=(a_{ij}),$ $1\leq i,$$j\leq n$ とし, $D,$ $-L,$$-U$ は $A$ の対角, 狭義の下三角, 狭義の上三角成分 y $a_{i}:\neq 0,1\leq i\leq n,$ $J=D^{-1}(L+U),$ $\lambda_{1},$$\lambda_{2},$
$\ldots,$
$\lambda_{n}$を $J$の固
有値, $\omega$を加速係数, $H_{\omega}=(D-\omega L)-1[(1-\omega.)D+\omega U],$ $\rho(J)=\max 1\leq*\leq n|\lambda:|,$ $\gamma(J)=$
$\max_{1\leq:\leq n}\{|\lambda:|;\lambda_{i}\neq 1\},$ $\delta(J)=\max 1\leq*\cdot\leq n\{|\lambda_{i}|;|\lambda_{i}|\neq 1\}$
,
とする. $A\mathrm{r}=b$ のSOR
法は$xk+1=H(vx_{k}+\omega(D-\omega L)-1b,$$k=0,1,2,$ $.\text{。}$
.
となる。補題1 $[1, 6]$
.
(i)
$A$ がconvergent
$( \lim_{karrow\infty}A^{k}=O)\Leftrightarrow\rho(A)<1$.
(ii)
$\rho(A)=1$ とする. $A$ がsemiconvergent
$( \lim_{karrow\infty}A^{k}\text{が存在})\Leftrightarrow\gamma(A)<1$ かっ $A$の固有値 1 に関するすべての
elementary
divisor
がlinear.
仮定1. $A$ が
consistently
ordered
かつ2-cyclic
である.仮定2. $\det A=0$ かっ $J$の固有値1に関するすべての
elementary
divisor
がlinear
である.
補題 2[6].
$A$ は仮定1を満たす正則行列, $J$の固有値はすべて実数で $\rho(J)<1$ とする. \Rightarrow H。は
convergent
$(\rho(H_{\omega})<1,0<\omega<2),$$\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}=\frac{2}{1+\sqrt{1-\rho(J)^{2}}}$ は$\rho(H_{\omega_{\circ \mathrm{p}\mathrm{t}}})=$
而nO$<\omega<2\rho(H\omega)$ となる.
補題3 $[1, 2]$
.
$A$ は仮定1と2を満たす特異行列, $J\text{の固有値はすべて実数で}\rho(J)=1$とする. $\Rightarrow H_{\omega}$ は
semiconvergent
$(\gamma(H_{\omega})<1,0<\omega<2)$.
$\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}=\frac{2}{1+\vee^{\overline{1-\delta(J}})^{z}\wedge}$ は$\gamma(H_{\omega_{\text{。}\mathrm{p}}})5=\mathrm{m}\mathrm{i}\mathrm{n}0<\omega<2\gamma(H_{\omega})$ となる. $b\in{\rm Im} A$ の時, $x_{k}$ は $Ax=b$ の解に収束する。
2. Neumann
境界条件の差分行列.
次のような2
点境界値問題を考える.
(1)
$\{$$y”(x)=p(x)y’(x)+r(x)$
,
$a\leq x\leq b$,
$y’(a)=\alpha$,
$y’(b)=\beta$.
ここで $p(x),$ $r(x)$ は連続とする. $[a, b]$ を $(n-1)$ 等分し, $h= \frac{b-a}{n-1},$ $x_{i}=a+(i-1)h,$ $1\leq$
$i\leq n$
.
(1)
を中心差分により近似し, $y(x\dot{.})$ の近似解を $v_{i}$ とすれば(1)
の差分方程式は$Av=b$ となる $(\det A=0)$
.
数理解析研究所講究録
定理 1. $h \cdot\max_{a\leq x\leq b}|p(x)|<2$ とする. $\Rightarrow H_{\omega}$ は
semiconvergent
$(\gamma(H_{\omega})<1,0<$$\omega<2)$ で $\omega_{\mathrm{o}_{\mathrm{P}}}\mathrm{t}=\frac{2}{1+\sqrt{1-\delta(J)^{2}}}$ は$\gamma(H_{\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}})=\min_{0}<\omega<2\gamma(H_{\omega})$ となる. さらに, $h= \frac{b-a}{n-1}$ が
$+$分小ならば, $\omega_{\mathrm{o}_{\mathrm{P}}\mathrm{t}}\approx\frac{2}{1+\sin\frac{\pi}{n-1}}$
.
3.
周期境界条件の差分行列. 次のような2
点境界値問題を考える.
(2)
$\{$$y”(X)=p(x)y’(X)+r(x)$
,
$a\leq x\leq b$,
$y(a)=y(b)$,
$y’(a)=y(\prime b)$.
ここで $p(x),$ $r(x)$ は連続とする. $[a, b]$ を $n$ 等分し, $h= \frac{b-a}{n}$
,
$x_{i}=\{$
$a+(j-1)h$
, if $i=2j-1$ ,
$i=1,2,$$\cdots,$ $n$.
b-jh,
if
$i=2j$,
を
mesh type II
とする.(2)
の申心差分による差分方程式は$Av=b$ となる $(\det A=0)$.
定理 2. $n$ は偶数,
mesh
tyPe
$\mathrm{I}\mathrm{I},$ $h \cdot\max_{a\leq x\leq b}|p(x)|<2,$ $\Pi_{=1}^{n}\dot{.}\{1+\frac{1}{2}p(x_{i})h\}=$ $\Pi_{i=1}^{n}\{1-\frac{1}{2}p(xi)h\}$ とする. $\Rightarrow H_{\omega}$ はsemiconvergent
$(\gamma(H_{\omega})<1,0<\omega<2)$で
$\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}=\frac{2}{1+\sqrt{1-\delta(J)^{2}}}$ は$\gamma(H_{\omega \mathrm{o}\mathrm{p}\mathrm{t}})=\mathrm{m}\mathrm{i}\mathrm{n}0<\omega<2\gamma(H_{\omega})$ となる. さらに, $h= \frac{b-a}{n}$ が$+$分小なら
ば, $\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}\approx\frac{2}{1+\sin\frac{2\pi}{n}}$
.
定理 3. $n$ は偶数,
mesh
type
$\mathrm{I}\mathrm{I},$ $h \cdot\max_{a\leq x\leq b}|p(X)|<2,$ $\text{」}$は複素固有値をもっ とする. $\Rightarrow 0<\omega<\omega_{\max}$ で $H_{\omega}$ は
semiconvergent
となる $\omega_{\max}<2$ が存在し,
$\gamma(H_{\omega_{\text{。}\mathrm{p}\mathrm{t}}})=\min_{0<\omega<}\omega \mathrm{m}*\mathrm{x}\gamma(H_{\omega})$ となる
$\omega_{\text{。}\mathrm{p}\mathrm{t}}$ が存在する. さらに, $h= \frac{b-a}{n}$ が十分小なら
ば\sim $\omega_{\max}\approx 2,$ $\omega_{\mathrm{o}\mathrm{p}\mathrm{t}}\approx\frac{2}{1+\sin\frac{2\pi}{n}}$
.
注意. 境界値問題
(1), (2)
の解は次の例のように存在しないこともある.(3)
$\{$$y”(_{X})=2,0\leq x\leq 1$
,
$y’(0)=0,$ $y’(1)=0$
,
(4)
$\{$$y”(_{X})=2$
,
$0\leq x\leq 1$,
$y(0)=y(1)$
,
$y’(0)=y(/1)$.
また解 $y(x)$ が存在する時は, $y(x)+c$ も解となる
(
$c$は任意定数).
特に(1)
の場合,$y’(x)$ を初期値問題 $y”(X)=P(x)y’(X)+r(x),$$a\leq x\leq b,$ $y’(a)=\alpha$ の解とし, $y’(b)\neq\beta$ と
なる時
(1)
の解 $y(x)$ は存在しない. なお(3),(4)
の差分方程式 $Av=b$ は $b\not\in{\rm Im} A$ すなわち
inconsistent
な方程式となり,SOR
法はsemiconvergence
しないことが言える.参考文献
[1] Bermann, A. and Plemmons, R. J., Nonnegative matrices in the mathematical sciences, Academic Press, 1979.
[2] Hadjidimos, A., On the optimization of the classical iterative schemes for the solution of complex singular linear systems, SIAM J. Alg. Disc. Meth., 6 (1985), 555–566.
[3] Ishihara, K., Projectedsuccessiveoverrelaxation method for finite element solutionstothe Dirichlet
$\mathrm{p}\mathrm{r}o$blem for asystemofnonlinear ellipticequations, J. Comput. Appl. Math., 38 (1991), 185–200.
[4] Ishihara, K. and Yamamoto, M., Optimum relaxation parameter of SOR iterations for discrete
Neumann type arising from two-point boundary value problems, Math. Japon., 39 (1994), 385
-393.
$\iota|5]$ Ishihara,K. &\mbox{\boldmath$\gamma$}tdYamamoto, M., $\mathrm{O},\mathrm{n}$the optimum SOR iterations for finite difference approximation
to periodic boundary value problems, Math. Japon., 41 (1995), 199$-209$
.
[6] Varga, R. S., Matrixiterative analysis, Prentice-Hall, 1962.
