はじめに
Gauss-Seidel法が厳密解へ収束する主要な十分条件の一つに、係数行列が狭義優対角であることが知られている。腕試しに証明を試みたらできたので書き残しておく。
\[
% 汎用
\newcommand{\ctext}[1]{\raise0.2ex\hbox{\textcircled{\scriptsize{#1}}}}
% 数学
% 汎用
\DeclarePairedDelimiterX{\parens}[1]{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterX{\braces}[1]{\lbrace}{\rbrace}{#1}
\DeclarePairedDelimiterX{\bracks}[1]{\lbrack}{\rbrack}{#1}
\DeclarePairedDelimiterX{\verts}[1]{|}{|}{#1}
\DeclarePairedDelimiterX{\Verts}[1]{\|}{\|}{#1}
\newcommand{\as}{{\quad\textrm{as}\quad}}
\newcommand{\st}{{\textrm{ s.t. }}}
\DeclarePairedDelimiterX{\setComprehension}[2]{\lbrace}{\rbrace}{#1\,\delimsize\vert\,#2}
\newcommand{\naturalNumbers}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\rationalNumbers}{\mathbb{Q}}
\newcommand{\realNumbers}{\mathbb{R}}
\newcommand{\complexNumbers}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\func}[2]{{#1}\parens*{#2}}
\newcommand{\argmax}{\mathop{\textrm{arg~max}}}
\newcommand{\argmin}{\mathop{\textrm{arg~min}}}
% 集合論
\newcommand{\range}[2]{\braces*{#1,\dotsc,#2}}
\providecommand{\complement}{}\renewcommand{\complement}{\mathrm{c}}
\newcommand{\ind}[2]{\mathbbm{1}_{#1}\parens*{#2}}
\newcommand{\indII}[1]{\mathbbm{1}\braces*{#1}}
% 数論
\newcommand{\abs}[1]{\verts*{#1}}
\newcommand{\combi}[2]{{_{#1}\mathrm{C}_{#2}}}
\newcommand{\perm}[2]{{_{#1}\mathrm{P}_{#2}}}
\newcommand{\GaloisField}[1]{\mathrm{GF}\parens*{#1}}
% 解析学
\newcommand{\NapierE}{\mathrm{e}}
\newcommand{\sgn}[1]{\operatorname{sgn}\parens*{#1}}
\newcommand{\cl}[1]{\operatorname{cl}#1}
\newcommand{\Img}[1]{\operatorname{Img}\parens*{#1}}
\newcommand{\dom}[1]{\operatorname{dom}\parens*{#1}}
\newcommand{\norm}[1]{\Verts*{#1}}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\expo}[1]{\exp\parens*{#1}}
\newcommand{\sinc}{\mathop{\textrm{sinc}}}
\newcommand{\GammaFunc}[1]{\Gamma\parens*{#1}}
\newcommand{\erf}{\mathop{\mathrm{erf}}}
% 逆三角関数
\newcommand{\asin}[1]{\operatorname{Sin}^{-1}{#1}}
\newcommand{\acos}[1]{\operatorname{Cos}^{-1}{#1}}
\newcommand{\atan}[1]{\operatorname{{Tan}^{-1}}{#1}}
\newcommand{\atanEx}[2]{\atan{\parens*{#1,#2}}}
% 畳み込み
\newcommand{\cycConv}[2]{{#1}\underset{\text{cyc}}{*}{#2}}
% 微分
\newcommand{\deriv}[3]{\frac{\operatorname{d}^{#3}#1}{\operatorname{d}{#2}^{#3}}}
\newcommand{\derivLong}[3]{\frac{\operatorname{d}^{#3}}{\operatorname{d}{#2}^{#3}}#1}
\newcommand{\partDeriv}[3]{\frac{\operatorname{\partial}^{#3}#1}{\operatorname{\partial}{#2}^{#3}}}
\newcommand{\partDerivLong}[3]{\frac{\operatorname{\partial}^{#3}}{\operatorname{\partial}{#2}^{#3}}#1}
\newcommand{\partDerivIIHetero}[3]{\frac{\operatorname{\partial}^2#1}{\partial#2\operatorname{\partial}#3}}
\newcommand{\partDerivIIHeteroLong}[3]{{\frac{\operatorname{\partial}^2}{\partial#2\operatorname{\partial}#3}#1}}
% 積分
\newcommand{\integrate}[5]{\int_{#1}^{#2}{#3}{\mathrm{d}^{#4}}#5}
\newcommand{\LebInteg}[4]{\int_{#1} {#2} {#3}\parens*{\mathrm{d}#4}}
% 複素解析
\newcommand{\conj}[1]{\overline{#1}}
\providecommand{\Re}{}\renewcommand{\Re}[1]{{\operatorname{Re}{\parens*{#1}}}}
\providecommand{\Im}{}\renewcommand{\Im}[1]{{\operatorname{Im}{\parens*{#1}}}}
\newcommand{\Arg}[1]{\operatorname{Arg}{\parens*{#1}}}
\newcommand{\Log}[1]{\operatorname{Log}{#1}}
% ラプラス変換
\newcommand{\LPLC}[1]{\operatorname{\mathcal{L}}\parens*{#1}}
\newcommand{\ILPLC}[1]{\operatorname{\mathcal{L}}^{-1}\parens*{#1}}
% 離散Fourier変換
\newcommand{\DFT}[1]{\mathrm{DFT}\parens*{#1}}
% Z変換
\newcommand{\ZTrans}[1]{\operatorname{\mathcal{Z}}\parens*{#1}}
\newcommand{\IZTrans}[1]{\operatorname{\mathcal{Z}}^{-1}\parens*{#1}}
% 線形代数
\newcommand{\bm}[1]{{\boldsymbol{#1}}}
\newcommand{\matEntry}[3]{#1\bracks*{#2}\bracks*{#3}}
\newcommand{\matPart}[5]{\matEntry{#1}{#2:#3}{#4:#5}}
\newcommand{\diag}[1]{\operatorname{diag}\parens*{#1}}
\newcommand{\tr}[1]{\operatorname{tr}{\parens*{#1}}}
\newcommand{\inprod}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\HadamardProd}{\odot}
\newcommand{\HadamardDiv}{\oslash}
\newcommand{\Span}[1]{\operatorname{span}\bracks*{#1}}
\newcommand{\Ker}[1]{\operatorname{Ker}\parens*{#1}}
\newcommand{\rank}[1]{\operatorname{rank}\parens*{#1}}
% ベクトル
% 単位ベクトル
\newcommand{\vix}{\bm{i}_x}
\newcommand{\viy}{\bm{i}_y}
\newcommand{\viz}{\bm{i}_z}
% 確率論
\newcommand{\PDF}[2]{\operatorname{PDF}\bracks*{#1,\;#2}}
\newcommand{\Ber}[1]{\operatorname{Ber}\parens*{#1}}
\newcommand{\Beta}[2]{\operatorname{Beta}\parens*{#1,#2}}
\newcommand{\ExpDist}[1]{\operatorname{ExpDist}\parens*{#1}}
\newcommand{\ErlangDist}[2]{\operatorname{ErlangDist}\parens*{#1,#2}}
\newcommand{\PoissonDist}[1]{\operatorname{PoissonDist}\parens*{#1}}
\newcommand{\GammaDist}[2]{\operatorname{Gamma}\parens*{#1,#2}}
\newcommand{\cind}[2]{\ind{#1\left| #2\right.}} %条件付き指示関数
\providecommand{\Pr}{}\renewcommand{\Pr}[1]{\operatorname{Pr}\parens*{#1}}
\newcommand{\cPr}[2]{\operatorname{Pr}\cPrParens{#1}{#2}}
\newcommand{\E}[2]{\operatorname{E}_{#1}\bracks*{#2}}
\newcommand{\cE}[3]{\E{#1}{\left.#2\right|#3}}
\newcommand{\Var}[2]{\operatorname{Var}_{#1}\bracks*{#2}}
\newcommand{\Cov}[2]{\operatorname{Cov}\bracks*{#1,#2}}
\newcommand{\CovMat}[1]{\operatorname{Cov}\bracks*{#1}}
% グラフ理論
\newcommand{\neighborhood}{\mathcal{N}}
% プログラミング
\newcommand{\plpl}{\mathrel{++}}
\newcommand{\pleq}{\mathrel{+}=}
\newcommand{\asteq}{\mathrel{*}=}
\]
Gauss-Seidel法
以下に述べる定義はWikipediaの英語記事“Gauss Seidel method”からの引用である。
$n\in\naturalNumbers,\;A\in\complexNumbers^{n\times n},\;\bm{b}\in\complexNumbers^n$ とする。$A$ は正定値対称、または狭義優対角であるとする。Gauss-Seidel法とは、線型方程式 $A\bm{x}=\bm{b}$ の解を求める反復法である。$\bm{x}_1\in\complexNumbers^n$ を任意の初期解とし、次の漸化式で解候補を更新してゆく。
\[ L_* \bm{x}_{k+1} = -U\bm{x}_k \quad (k=1,2,\dots)\]ここに $L_*$ は $A$ の対角成分およびその下側の要素からなる下三角行列であり、 $U$ は $A$ の対角成分の上側の要素からなる上三角行列である。
係数行列が狭義優対角ならば厳密解に収束すること
$\textit{Proof}$
$A$ の次数を $n$ とする。$\mathring{\bm{x}}$ を厳密解とすると $L_* \mathring{\bm{x}} = \bm{b} – U\mathring{\bm{x}}$ である。これを解の更新式から減じると次式を得る。
\[ L_* (\bm{x}_{k+1} – \mathring{\bm{x}}) = -U(\bm{x}_k – \mathring{\bm{x}}) \tag{1} \]$\bm{v}_k \coloneqq \bm{x}_k – \mathring{\bm{x}}$ とおくと、式 (1) より次式が成り立つ。
\[ L_* \bm{v}_{k+1} = -U\bm{v}_k \tag{2} \]$M_k \coloneqq \max_{i=1,\dots,n} |v_{k,i}|\;(v_{k,i}$ は $\bm{v}_k$ の第 $i$ 要素)とする。次の2つが同時に成り立つことが、$\bm{v}_k$ が $\bm{0}_n$ に収束するための十分条件である。
- ある $k \in \mathbb{N}$ に対して $M_k = 0$ ならば $M_l = 0\;(l=k+1,k+2,\dots)$
- 適当な $0 < \alpha < 1$ が存在して $M_k > 0 \Rightarrow M_{k+1} < \alpha M_k$
$L_*$ が正則であることと式 (2) より直ちに 1. が成り立つ。次に 2. を数学的帰納法で示す。$\tilde{\alpha}$ を次式で定義する。
\[ \tilde{\alpha} \coloneqq \min_{i=1,2,\dots,n} \frac{1}{|a_{i,i}|} \sum_{j=1,\dots,n \wedge j\neq i} |a_{i,j}| \]$A$ は優対角だから $0 < \tilde{\alpha} < 1$ である。
\[ \begin{align*} a_{1,1} v_{k+1, 1} &= -\sum_{j=2}^n a_{1,j}v_{k,j} \\ |a_{1,1}| |v_{k+1, 1}| &= \left|\sum_{j=2}^n a_{1,j}v_{k,j}\right| \leq \sum_{j=2}^n |a_{1,j}||v_{k,j}| \leq M_k \sum_{j=2}^n |a_{1,j}| \\ |v_{k+1, 1}| &\leq \frac{M_k}{|a_{1,1}|} \sum_{j=2}^n |a_{1,j}| \leq \tilde{\alpha}M_k \end{align*} \]$|v_{k+1, j}| \leq \tilde{\alpha} M_k\;(j=1,2,\dots,l)\;(l\in\{1,2,\dots,n-1\})$ ならば $|v_{k+1, l+1}| \leq \tilde{\alpha} M_k$ であることを示す。式 (2) の $l+1$ 行目を展開すると次式を得る。
\[ \begin{align*} \sum_{j=1}^{l+1} a_{l+1,j} v_{k+1, j} &= -\sum_{j=l+2}^n a_{l+1,j}v_{k,j} \\ a_{l+1,l+1} v_{k+1, l+1} &= -\sum_{j=1}^l a_{l+1,j} v_{k+1, j} – \sum_{j=l+2}^n a_{l+1,j}v_{k,j} \\ |a_{l+1,l+1}| |v_{k+1, l+1}| &= \left|-\sum_{j=1}^l a_{l+1,j} v_{k+1, j} – \sum_{j=l+2}^n a_{l+1,j}v_{k,j}\right| \leq \sum_{j=1}^l |a_{l+1,j}||v_{k+1, j}| + \sum_{j=l+2}^n |a_{l+1,j}||v_{k,j}| \\ &\leq M_k \sum_{j=1,\dots,n \wedge j\neq l+1} |a_{l+1,j}| \\ |v_{k+1, l+1}| &\leq \frac{M_k}{|a_{l+1,l+1}|} \sum_{j=1,\dots,n \wedge j\neq l+1} |a_{l+1,j}| \leq \tilde{\alpha} M_k \end{align*} \]以上より帰納的に $|v_{k+1,j}| \leq \tilde{\alpha} M_k\;(j=1,2,\dots,n)$ が成り立つ。すなわち $M_{k+1} \leq \tilde{\alpha} M_k$ が成り立つ。$\tilde{\alpha} < \alpha < 1$ となるように $\alpha $ を定めることで 2. が示される。
$\square$
