数理解析研究所講究録
915 巻 1995 年 53-6053非対称行列に対する多段階外挿反復法

岡山理科大学理学研究科
岡山理科大学理学部
順正短期大学

木梨陽介
仁木薄井正孝$\backslash \grave{\mathit{1}}\ovalbox{\tt\small REJECT}$(Kinashi Yousuke)(Niki Hiroshi)(Usui Masataka)

1. はじめに線形方程式 $Ax$ =b の解法として基本反復法がある. そして与えられた問題の係数行
列 $A$ が持つ条件によって基本反復法に種々の工夫がなされている.
例えば係数行列の Jacobi 行列が歪対称行列のとき, W.Niethammer は基本反復法に外挿法を適用している [4]. それに基づいて, AHadjidimos,.Varga らによって研究がなされている [1] [2] [3] [5]. この外挿法は基本反復法の加速係数と外挿係数の推定を必を与えている [2].
要とする. 上記の例で AHadjidimos は最適外挿係数
したがって,との推定が問題となる. このように, 反復計算実行以前に両方の係数の値を得ることは困難である. したがって反復計算実行中に推定しなければならない.
そこで, 本論文でパラメーターの値を簡単に推定できる反復法を提案する. その方法の収束定理を導き, 実用性について結果を報告する.
$\mathrm{R}.\mathrm{S}$$\gamma_{opt}=\frac{2}{2-(\lambda_{M+}\lambda_{m})}$$\lambda_{M}$$\lambda_{m}$2. 多段階外挿 Gauss-Seidel 反復法
係数行列 $A$ を次のように正則分離する.
$A=$$I-L+U=M-N$ .

ここで $I$ は単位行列, 垣ま狭義上三角行列,$U$は狭義下三角行列,(1)$M$は正則である. そのとき基本反復公式は$x^{(k+1)}$である.

$=M^{-1(k)}Nx+M^{-1}b$ .

(2)$M=$$(I-L)$

(3)

$N=$

$-U$

(4)

ここで $M$ と $N$ を

54と選ぶとき,よく知られた Gauss-Seidel 反復公式

$x^{\mathrm{t}^{k+}1)}$

$=$

(5)

$-(I-L)-1UX(k)+(I-L)^{-1}b$が得られる.

これに対して我々は新しい分離を考える. ここで

$l$

$M$

$=$

$l(I-L)$

(6)

$N$

$=$

$(l-1)(I-L)-U$(7)

は非零の正の整数とする. このときの反復公式は,$x^{\mathrm{t}^{k+}1)}$$\frac{1}{l}(I-L)-1((l-1)(I-L)-U)X(k)$

$=$

(8)

$+ \frac{1}{l}(I-L)-1b$$\frac{1}{l}((l-1)I-(I-L)-1U)x^{(}k)+\frac{1}{l}(I-L)-1b$$=$.
(9)$U$を消去することによって$x^{(k+1)}$$\frac{1}{l}(I-L)-1((l-1)(I-L)$$=$$-(A-I+L))x)(k+ \frac{1}{l}(I-L)-1b$ .

を得る.

Richardson 反復公式で表すと$x^{(k+1)}$$=$$\frac{1}{l}(I-L)-1(\iota(I-L)-A)x^{\mathrm{t}^{k})}$$+ \frac{1}{l}(I-L)-1b$$=x^{(k)}- \frac{1}{l}(I-L)-1(AX-(k)b)$(10)

この反復法を多段階外挿 Gauss-Seidel 反復法と名付ける. ここで $l=1$ とおくと通常の Gauss-Seidel 反復法, $l=2$ のとき 2 段階外挿 Gauss-Seidel 反復法である.となる.

55

3. 多段階外挿 Gauss-Seidel 反復法の収束条件
ここで多段階外挿 Gauss-Seidel 反復法の収束条件について考察する. 多段階外挿 GaussSeidel 反復法の反復行列 は$T_{1}$$T_{1}$$=$(11)$\frac{1}{l}((l-1)I+\tau_{\mathrm{G}})$

である.
ここで,

2 段階外挿 Gauss-Seidel 反復法に対し次の定理が成立する.ととし,をそれぞれ中心 $0$ , 半径 で表される円をGauss-Seidel 反復行列と 2 段階外挿 Gauss-Seidel 反復行列の固有値の集合とする.
をそのとき共通集合 Ac

定理 1$\lambda(T_{\mathrm{G}})$$\mathrm{D}(\mathrm{O}, r)$$r$$(T_{\mathrm{G}})$$\Lambda_{\mathrm{C}}(T_{\mathrm{G}})=\mathrm{D}(0, \rho(T_{\mathrm{G}}))$$\cap$$\mathrm{D}(-1,2\rho(T_{\mathrm{G}}))$とおく (図 1). このとき$\lambda(\tau_{\mathrm{G}})$

$\in$

Ac

$(T_{\mathrm{G}})$を満たすならば, 次の不等式が成立する$\rho(T_{2})$$\leq\rho(\tau_{\mathrm{G}})$.

,$\lambda(T_{2})$56

証明
まず $\lambda(T_{\mathrm{G}})=x+iy$ とおく,

ここで $i=\sqrt{-1}$ とする.

そのとき次の不等式が保たれる.

$x^{2}+y^{2}$

これは\mbox{\boldmath $\lambda$}(TG) が円$\rho(T_{2})\leq\rho(T_{\mathrm{G}})$$\mathrm{D}(\mathrm{O}, \rho(\tau_{\mathrm{G}}))$

を満たすためには,$\leq$$\rho^{2}(\tau_{\mathrm{G}})$

.

(12)

内に含まれることを意味する.
$\lambda(T_{2})=\frac{1}{2}\lambda(I+T_{\mathrm{G}})=\frac{1}{2}+\frac{1}{2}\lambda(\tau_{\mathrm{G}})$であるので, 次の不等式を満たさなければならない.

$| \lambda(T_{2})|=|\frac{1}{2}+\frac{1}{2}x+i\frac{1}{2}y|$$\leq$$\rho(T_{\mathrm{G}})$

,

よって,

$(1+x)2+y2$

これは\mbox{\boldmath $\lambda$}(TG) が円したがってき$\lambda(T_{\mathrm{G}})$$\rho(T_{2})\leq\rho(\tau_{\mathrm{G}})$.

$\leq$$(2\rho(\tau_{\mathrm{G}}))^{2}$.

(13)に含まれることを意味する.
が (12) (13) 式を満たす共通集合 AC
内に存在するならばそのと$\mathrm{D}(-1,2\rho(\tau \mathrm{G}))$$(T_{\mathrm{G}})$

口

次に多段階外挿 Gauss-Seidel 反復法の収束定理を示す.の各固有値を\mbox{\boldmath $\lambda$}y$n),$$1,2,$$(j=1,2,\cdots,n)$とする. そのとき次の定理が成立する.の各固有値を\mbox{\boldmath $\lambda$}j(Tl)$T_{\mathrm{G}}$$\cdots,$

定理 2$(T_{\mathrm{G}})(j=$$T_{1}$

多段階外挿 Gauss-Seidel 反復法は段階数 l が次の不等式を満たすときに収束する.
$-2l+1<\lambda_{j}(T_{\mathrm{G}})<1$,$j=1(1)n$ .

(14)

証明
(11) 式より$\lambda_{j}(T_{1})$$=$$\frac{1}{l}\{(l-1)+\lambda_{j}(\tau_{\mathrm{G}})\}$$|j=1(1)n$が成立する. したがってこの多段階外挿 Gauss-Seidel 反復法が収束するためには次の不等式を満たさなければならない57$| \frac{1}{l}\{(l-1)+\lambda j(T\mathrm{G})\}|<1$$|j=1(1)n$ .

したがって$-2l+1<\lambda_{j}(T\mathrm{G})<1$が得られる$j=1(1)n$ .

,

(15)

口の不等式を満たす の推定が必要になってくる. そのための推定方法のつとして Gerschgorin の定理を利用した.
ここで (15)$l$Gerschgorin の定理
正方行列 の最大固有値の絶対値は任意の行または列のすべての要素の絶対値の和の$A$最大値を越えない.の固有値の絶対値最大の上限を計算し (15) 式からこの定理を用いて与えられた推定する. この の選択の妥当性を数値例で示す.
$T_{\mathrm{G}}$$l$

4. 数値例
2 段階 Gauss-Seidel 反復法に対して, 次に示す係数行列を用いて数値実験を行う.

$A=$
ここで$a= \frac{1}{n+2}$,$b= \frac{1}{n+1}$,$c= \frac{1}{n}$

$l$

を

58

Gauss-Seidel 反復法と 2 段階 Gauss-Seidel 反復法の反復回数を表 1 に示す.
表1

Gauss-Seidel 法 2
279
584
1381
3217

$n$

50
100
225
500

$\mathrm{B}^{J\mathrm{L}}\mathfrak{p}\mathrm{g}$Gauss-Seidel ‘&
29
31
3234

多段階 Gauss-Seidel 反復法に対して, 次のような行列に対して数値実験を行う.

この行列に対する$T_{\mathrm{G}}$の固有値は次のようになる.

表 2.

実数部
$|$

虚数部

0.
-7.525-1.041-0.456-0.014$\mathrm{O}\mathrm{O}\mathrm{O}$

0.
0.000
0.000
0.000
0.000

$\mathrm{O}\mathrm{O}\mathrm{O}$

このことからスペクトル半径は,$\rho(T_{\mathrm{G}})$となり,調べた.

$=$$7.525575$

Gauss-Seidel 反復法では収束しないことが分かる.

そこで

$l$

を推定し反復回数を

59

表 3.
$l$

最適外挿

反復回数

$696$

$5 79$
発散
4$(\gamma_{opt})$$75 (0.2)$を増加していくと条件不等式は満たすが スペクトル半径が増大するために反復とスペクトル半径の関係を回数も増大する. $l=4$ の場合は条件不等式を満たさない.
次の表に示す.
ここで$l$

$l$

表 4.
$l$

スペクトル半径0.9000000
90.8888889
80.8750000
70.8571429
60.8333333
50.8000000
41.131394
31841859
23262788
17.525575

10

表 5.
$l$

NO.
12

3

段階 Gauss-Seidel 反復法による反復回数$\rho(T_{\mathrm{G}})$

69.14713
8.999225
7.525575

$l$

反復回数

597
92
575

36
6

最適外挿$(\gamma_{opt})$593(0.028)
87(0.18)75(0.2)$\frac{}{64.80515146151(0.29)}\frac{46.49858157565(0.2)}{55.81036746464(0.25)}$

$7$

89

4.165901
3.709351
3.740937

33362728
4749(0.32)
833(0.42)
46(0.34)

60

6. まとめ与えられた問題 $Ax=b$ の係数行列が非対称であるとき外挿反復法が有効である. 今回我々の提案した多段階外挿 Gauss-Seidel 反復法は Gauss-Seidel 反復法が適用できない問題に対しても優れた収束比が得られた. また, Gerschgorin の定理を用いる推定法が有効であることが分かった. 今後,のより正確な推定方法の開発が課題である.
$l$

謝辞
本研究に対して, 貴重なご示唆を戴いた愛媛大学理学部山本哲朗教授に深甚なる敬意を表します.

参考文献[1] M.Eiermann,W.Niethammer and.Varga, Acceleration of relaxation method for
non-Hermitian linear systems, SIAM J. Matrix Anal. Apl.,13(1992)979-991.
$\mathrm{R}.\mathrm{S}$[2] A.Hadjidimos,The Optimal Solution of the Extrapolation Probrem of First Order
Scheme,J. Comput.Math.,.
$\mathrm{v}\mathrm{o}113,(1983)1\bm{5}3- 168$[3]

. Neuman and.Varga, On the Sharpness of some upper bounds for the spectral
radii of S.O.R iteration matrices, Numer.Math.,35(1980)69-79.
$\mathrm{H}.\mathrm{M}$$\mathrm{R}.\mathrm{S}$[4] W.Niethammer,On Different Spilitting and the Associated Iteration Methods,
SIA MJ.Numer.Anal.,vol.16(1979),186-200.
[5].Varga, Extention of the successive overrrelaxation theory with applications
to finite element approximations in Topics in Numerical Analysis,H.H.J.Miller,
ed.,Academic Press,New York,1973,329-343.
$\mathrm{R}.\mathrm{S}$