0 引言

对角占优矩阵是应用非常广泛的矩阵类, 它较多出现于经济价值模型和反网络系统的系数矩阵及微分方程的数值解法中, 在信息论、系统论、现代经济学和程序设计等众多领域都有着十分重要的应用.文献[1]和[2]分别研究了广义对角矩阵、广义次对角矩阵、$\alpha$-次对角占优矩阵和广义严格次对角占优矩阵, 给出了相应的判定定理.文献[3]研究了弱严格对角占优矩阵, 给出了矩阵非奇异的判定条件.文献[4]研究了Ostrowski对角占优矩阵的判定方法.文献[5]给出了几类对角占优矩阵行列式的界.对于系数矩阵为对角占优矩阵的线性方程组, 文献[6]给出了系数矩阵严格对角占优时, Jacobi、Guass-Seidel和SOR迭代法的收敛定理.文献[7]研究了系数矩阵为$\alpha$严格对角占优矩阵时, 几种常用迭代法的收敛性.文献[8]建立了对角占优三对角型线性方程组解的分量扰动界和精确算法.文献[9]讨论了系数矩阵为严格对角占优矩阵时, Jacobi迭代矩阵与Gauss-Seidel迭代矩阵的谱半径, 进而对两种迭代法的收敛速度进行了比较.

本文考虑线性方程组的系数矩阵为严格次对角占优阵时, 几类常用迭代法的收敛性和收敛速度, 尝试解决如下两个问题:

问题Ⅰ  若$A=(a_{ij})_{n\times n}$为严格次对角占优矩阵, 则解线性方程组$Ax=b$的Jacobi迭代法、Guass-Seidel迭代法和SOR迭代法是否收敛?若收敛, 给出相应的误差估计式.

问题Ⅱ  Jacobi迭代法、Guass-Seidel迭代法及SOR迭代法的误差上界比较.

1 预备知识

定义1.1^[10]  设$A=(a_{ij})_{n\times n}$, 若$|a_{ii}|\geqslant \sum_{j\neq i}|a_{ij}|, \forall i\in \{1, 2, \ldots, n\}$, 则称$A$为对角占优矩阵.当上式的每个不等号都严格成立时, 则称$A$为严格对角占优矩阵.

定义1.2^[10]  设$A=(a_{ij})_{n\times n}$, 若$|a_{i, n-i+1}|\geqslant \sum_{\begin{smallmatrix}j\neq n-i+1\end{smallmatrix}}|a_{ij}|, \forall i\in \{1, 2, \cdots, n\}$, 则称$A$为次对角占优矩阵.当上式的每个不等号都严格成立时, 则称$A$为严格次对角占优矩阵.

引理1.1^[10]  设$A=(a_{ij})_{n\times n}, B=(b_{ij})_{n\times m}$, 若矩阵$A$严格对角占优, 则

$ \begin{align} \|A^{-1}B\|_{\infty}\leqslant \max\limits_{1\leqslant i\leqslant n} \frac{\sum\nolimits_{j=1}^m|b_{ij}|}{|a_{ii}|- \sum\nolimits_{j\neq i}|a_{ij}|}. \end{align} $

(1)

引理1.2^[11]  若迭代矩阵$B$的范数$\|B\|_{\infty} < 1$, 则迭代公式$x^{(k+1)}=Bx^{(k)}+f, k=0, 1, 2, \cdots, $收敛于方程组的解$x^*$.相应的误差估计式为

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{\|B\|_{\infty}^k}{1 -\|B\|_{\infty}}\|x^{(1)}-x^{(0)}\|_{\infty}. \end{align} $

(2)

2 三种迭代法的收敛性

本文常用如下矩阵:

$ \begin{align*} &D=\left( {{\begin{array}{*{20}c} a_{1n}&&&&\\ &a_{2, n-1}&&& \\ & &\ddots&& \\ &&& a_{n-1, 2}& \\ && &&a_{n1} \end{array} }} \right) , \quad L= \left( {{\begin{array}{*{20}c} && &&0\\ && &0&a_{2n} \\ & &{\mathinner{\mskip1mu\raise1pt{\kern7pt\hbox{.}} \mskip2mu\raise4pt\hbox{.}\mskip2mu\raise7pt\hbox{.}\mskip1mu}} &\vdots&\vdots \\ &0 &\cdots &a_{n-1, n-1} &a_{n-1, n} \\ 0&a_{n2} &\cdots &a_{n, n-1} &a_{nn} \end{array} }} \right)\\ &U=\left( {{\begin{array}{*{20}c} a_{11}&a_{12} &\cdots &a_{1, n-1}&0\\ a_{21}&a_{22}&\cdots&0& \\ \vdots&\vdots&{\mathinner{\mskip1mu\raise1pt{\kern7pt\hbox{.}} \mskip2mu\raise4pt\hbox{.}\mskip2mu\raise7pt\hbox{.}\mskip1mu}}&& \\ a_{n-1, 1} &0 &&&\\ 0&&&& \end{array} }} \right). \end{align*} $

定理2.1  设$A=(a_{ij})_{n\times n}$严格次对角占优, 则线性方程组$Ax=b$的Jacobi迭代法$x^{(k+1)}=C_Mx^{(k)}+D_M$收敛于方程组的解$x^*$.相应的误差估计式为

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{M^k}{1-M} \|x^{(1)}-x^{(0)}\|_{\infty}, \end{align} $

(3)

其中$C_M=-D^{-1}(L+U)S_n, D_M=D^{-1}b, M=\max\limits_{1\leqslant i\leqslant n}\frac{\sum_{j\neq n-i+1}|a_{ij}|}{|a_{i, n-i+1}|}.$

证 明  由Jacobi迭代法得:

$ \begin{align} \begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k+1)}=-D^{-1}(L+U)S_n\begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k)}+D^{-1}b, \end{align} $

(4)

其中$S_n$为$n$阶反单位矩阵.记上式为

$ \begin{align} x^{(k+1)}=C_Mx^{(k)}+D_M. \end{align} $

(5)

由引理1.1得, $\|C_M\|_{\infty}\leqslant \max\limits_{1\leqslant i\leqslant n}\frac{\sum_{j\neq n-i+1}|a_{ij}|}{|a_{i, n-i+1}|}.$记$M=\max\limits_{1\leqslant i\leqslant n}\frac{\sum_{j\neq n-i+1}|a_{ij}|}{|a_{i, n-i+1}|}.$因为$A$为严格次对角占优矩阵, 所以$|a_{i, n-i+1}|>\sum_{j\neq n-i+1}|a_{ij}|$, 从而$\|C_M\|_{\infty}\leqslant M < 1$.结合引理1.2可得, 解线性方程组$Ax=b$的Jacobi迭代法敛于方程组的解$x^*$.相应的误差估计式为$\|x^{(k)}-x^*\|_{\infty}\leqslant \frac{M^k}{1-M}\|x^{(1)}-x^{(0)}\|_{\infty}.$

定理2.2  设$A=(a_{ij})_{n\times n}$严格次对角占优, 则线性方程组$Ax=b$的Guass-Seidel迭代法$x^{(k+1)}=E_Nx^{(k)}+F_N$收敛于方程组的解$x^*$.相应的误差估计式为

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N} \|x^{(1)}-x^{(0)}\|_{\infty}, \end{align} $

(6)

其中$E_N=-(D+LS_n)^{-1}US_n, F_N=(D+LS_n)^{-1}b, N=\max\{N_1, N_2, 0\}, N_1=\frac{\sum_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, $ $N_2=\max\limits_{1\leqslant i\leqslant n}\frac{\sum_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|- \sum_{j=n-i+2}^{n}|a_{ij}|}, $

证 明  由Guass-Seidel迭代法原理得:

$ \begin{align} \begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k+1)}=-(D+LS_n)^{-1}US_n\begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k)}+(D+LS_n)^{-1}b, \end{align} $

(7)

其中

$ \begin{align*} US_n\!=\!\!\begin{pmatrix}0&a_{1, n-1}&\cdots&a_{12}&a_{11}\\ &0&\cdots&a_{22}&a_{21}\\ &&\ddots&\vdots&\vdots\\ &&&0&a_{n-1, 1}\\ &&&&0\end{pmatrix}, \\ D+LS_n\!=\!\!\begin{pmatrix}a_{1n}&&&&\\ a_{2n}&a_{2, n-1}&&&\\ \vdots&\vdots&\ddots&&\\ a_{n-1, n}&a_{n-1, n-1}&\cdots&a_{n-1, 2}&\\ a_{nn}&a_{n, n-1}&\cdots&a_{n2}&a_{n1}\end{pmatrix}. \end{align*} $

将式$(7)$记为

$ \begin{align} x^{(k+1)}=E_Nx^{(k)}+F_N. \end{align} $

(8)

由引理1.1得,

$ \begin{align*} \|E_N\|_{\infty}\leqslant \max\limits_{1\leqslant i\leqslant n} \left\{\begin{array}{ll} \dfrac{\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, &i=1, \\[4mm] \dfrac{\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}| -\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}, &1<i<n, \\[4mm] 0, &i=n.\end{array}\right. \end{align*} $

记$N_1=\frac{\sum_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, N_2=\max\limits_{1\leqslant i\leqslant n}\frac{\sum_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\sum_{j=n-i+2}^{n}|a_{ij}|}.$因为$A$为严格次对角占优矩阵, 故$N_1 < 1$成立.且$|a_{i, n-i+1}|>\sum_{j\neq n-i+1}|a_{ij}|$, 从而$|a_{i, n-i+1}|>\sum_{j=1}^{n-i}{|a_{ij}|+\sum_{j=n-i+2}^{n}|a_{ij}|}$, 进而$|a_{i, n-i+1}|-\sum_{j=n-i+2}^{n}{|a_{ij}|}>\sum_{j=1}^{n-i}{|a_{ij}}|$, 故$N_2 < 1$.从而$N=\max\{N_1, N_2, 0\} < 1$.结合引理1.2, 线性方程组$Ax=b$的Guass-Seidel迭代法$x^{(k+1)}=E_Nx^{(k)}+F_N$收敛于方程组的解$x^*$.相应的误差估计式为$\|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N}\|x^{(1)}-x^{(0)}\|_{\infty}.$

定理2.3  设$A=(a_{ij})_{n\times n}$严格次对角占优，则当$0 < \omega\leqslant 1$时, 线性方程组$Ax=b$的SOR迭代法$x^{(k+1)}=G_Px^{(k)}+H_P$收敛于方程组的解$x^*$.相应的误差估计式为

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{P^k}{1-P}\|x^{(1)}-x^{(0)}\|_{\infty}, \end{align} $

(9)

其中$G_N=(D+\omega LS_n)^{-1}[(1-\omega)D-\omega US_n], F_N=\omega(D+\omega LS_n)^{-1}b, P=\max\{P_1, P_2, P_3\}, $ $P_1=\frac{(1-\omega)|a_{1n}|+\omega\sum_{j=1}^{n-1}|a_{1j}|} {|a_{1n}|}, $$P_2=\max\limits_{1 < i < n}\frac{(1-\omega)|a_{i, n-i+1}| +\omega\sum_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\omega\sum_{j=n-i+2}^{n} |a_{ij}|}, $$P_3=\frac{(1-\omega)|a_{n1}|}{|a_{n1}|-\omega\sum_{j=2}^{n} |a_{nj}|}.$

证 明  由SOR迭代法原理得:

$ \begin{align} \begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k+1)}=(D+\omega LS_n)^{-1} [(1-\omega)D-\omega US_n]\begin{pmatrix} x_n\\ x_{n-1}\\ \vdots\\ x_2\\ x_1\end{pmatrix}^{(k)}+\omega(D+\omega LS_n)^{-1}b. \end{align} $

(10)

将式(10)记为

$ \begin{align} x^{(k+1)}=G_Px^{(k)}+H_P. \end{align} $

(11)

由引理1.1得,

$ \begin{align*} \|G_P\|_{\infty}\leqslant \max\limits_{1\leqslant i\leqslant n} \left\{\begin{array}{ll}\dfrac{(1-\omega)|a_{1n}| +\omega\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, &i=1, \\ \dfrac{(1-\omega)|a_{i, n-i+1}|+\omega\sum\nolimits_{j=1}^{n-i}|a_{ij}|} {|a_{i, n-i+1}|-\omega\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}, &1<i<n, \\ \dfrac{(1-\omega)|a_{n1}|}{|a_{n1}|-\omega\sum\nolimits_{j=2}^{n} |a_{nj}|}, &i=n.\end{array}\right. \end{align*} $

记$P_1=\frac{(1-\omega)|a_{1n}|+\omega\sum_{j=1}^{n-1}|a_{1j}|} {|a_{1n}|}, P_2=\max\limits_{1 < i < n}\frac{(1-\omega)|a_{i, n-i+1}| +\omega\sum_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\omega\sum_{j=n-i+2} ^{n}|a_{ij}|}, P_3=\frac{(1-\omega)|a_{n1}|}{|a_{n1}|-\omega \sum_{j=2}^{n}|a_{nj}|}.$

(ⅰ) 当$\omega=1$时, 由于$A$严格次对角占优, $|a_{1n}|>\sum_{j=1}^{n-1}|a_{1j}|$, 故$P_1 < 1$.由于$|a_{i, n-i+1}|>\sum_{j=1}^{n-i}{|a_{ij}|+\sum_{j=n-i+2}^{n}|a_{ij}|}$, 故$|a_{i, n-i+1}|-\sum_{j=n-i+2}^{n}|a_{ij}|>\sum_{j=1}^{n-i}{|a_{ij}|}$, 从而$P_2 < 1$.而且$P_3=0 < 1$.从而$P=\max\{P_1, P_2, P_3\} < 1$.

(ⅱ) 当$0 < \omega < 1$时, $\omega|a_{1n}|>\omega\sum_{j=1}^{n-1}|a_{1j}|+(1-\omega)|a_{1n}| -(1-\omega)|a_{1n}|$, 即$|a_{1n}|>(1-\omega)|a_{1n}|+\omega\sum_{j=1}^{n-1}|a_{1j}|$, 故$P_1 < 1$.又因为$|a_{i, n-i+1}|>\sum_{j=1}^{n-i}{|a_{ij}|+\sum_{j=n-i+2}^{n}| a_{ij}|}$.故有$\omega|a_{i, n-i+1}|>\omega\sum_{j=1}^{n-i}|a_{ij}|+\omega \sum_{j=n-i+2}^{n}|a_{ij}|+(1-\omega)|a_{i, n-i+1}|-(1-\omega)|a_{i, n-i+1}|$.所以$|a_{i, n-i+1}|-\omega\sum_{j=n-i+2}^{n}|a_{ij}|>(1-\omega) |a_{i, n-i+1}|+\omega\sum_{j=1}^{n-i}|a_{ij}|$, 故$P_2 < 1$.由于$\omega|a_{n1}|>\omega\sum_{j=2}^{n}|a_{nj}|+(1-\omega)|a_{n1} |-(1-\omega)|a_{n1}|$, 即$|a_{n1}|-\omega\sum_{j=2}^{n}|a_{nj}|>(1-\omega)|a_{n1}|$, 故$P_3 < 1$.从而$P=\max\{P_1, P_2, P_3\} < 1$.根据引理1.2, 线性方程组$Ax=b$的SOR迭代法$x^{(k+1)}=G_Px^{(k)}+H_P$收敛于方程组的解$x^*$.相应的误差估计式为$\|x^{(k)}-x^*\|_{\infty}\leqslant \frac{P^k}{1-P}\|x^{(1)}-x^{(0)}\|_{\infty}.$

3 三种迭代法的误差上界比较

定理3.1  设$A=(a_{ij})_{n\times n}$为严格次对角占优矩阵, 则关于线性方程组$Ax=b$的Jacobi迭代法和Guass-Seidel迭代法, 有

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N}\|x^{(1)}-x^{(0)}\|_{\infty}\leqslant \frac{M^k}{1-M}\|x^{(1)}-x^{(0)}\|_{\infty}. \end{align} $

(12)

证 明  由定理2.1和定理2.2知,

$ \begin{align*} &M=\max\limits_{1\leqslant i\leqslant n}\frac{\sum\nolimits_{j\neq n-i+1} |a_{ij}|}{|a_{i, n-i+1}|}, \quad N_1=\frac{\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, \\ &N_2=\max\limits_{1\leqslant i\leqslant n}\frac{\sum\nolimits_{j=1}^{n-i}| a_{ij}|}{|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}, \quad N=\max\{N_1, N_2, 0\}. \end{align*} $

(ⅰ) 当$M, N_1$同行时, $M=\frac{\sum_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}=N_1$.

(ⅱ) 当$M, N_1$不同行时, 记与$N_1$同行为$\hat{M}$, 则$N_1=\hat{M} < M$.

(ⅲ) 当$M, N_2$同行时,

$ \begin{align*} &\frac{\sum\nolimits_{j\neq n-i+1}|a_{ij}|}{|a_{i, n-i+1}|}-\frac{\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}\\[3mm] =\, &\frac{|a_{i, n-i+1}|\sum\nolimits_{j\neq n-i+1}|a_{ij}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|\sum\nolimits_{j\neq n-i+1}|a_{ij}|-|a_{i, n-i+1}|\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|(|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}&\\[3mm] =\, &\frac{|a_{i, n-i+1}|\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|\sum\nolimits_{j\neq n-i+1}|a_{ij}|}{|a_{i, n-i+1}|(|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}\\[3mm] =\, &\frac{(|a_{i, n-i+1}|-\sum\nolimits_{j\neq n-i+1}|a_{ij}|)\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}{|a_{i, n-i+1}|(|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}. \end{align*} $

因为$A$是严格次对角占优阵, 所以$|a_{i, n-i+1}|-\sum_{j\neq n-i+1} |a_{ij}|>0, |a_{i, n-i+1}|-\sum_{j=n-i+2}^{n}|a_{ij}|>0$, 故上式大于0, 从而$M>N_2$.

(ⅳ)当$M, N_2$不同行时, 记与$N_2$同行为$\bar{M}$, 则$M>\bar{M}>N_2$.综上所述, $N=\max\{N_1, N_2, 0\}\leqslant M$.所以

$ \begin{align*} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N}\|x^{(1)}-x^{(0)}\|_{\infty}\leqslant \frac{M^k}{1-M}\|x^{(1)}-x^{(0)}\|_{\infty}. \end{align*} $

定理3.2  设$A=(a_{ij})_{n\times n}$为严格次对角占优矩阵, 则关于线性方程组$Ax=b$的Guass-Seidel迭代法和SOR迭代法, 有

$ \begin{align} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N}\|x^{(1)}-x^{(0)}\|_{\infty}\leqslant \frac{P^k}{1-P}\|x^{(1)}-x^{(0)}\|_{\infty}. \end{align} $

(13)

证 明  由定理2.2和定理2.3知,

$\begin{array}{l} N_1=\frac{\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, \\ N_2=\max\limits_{1\leqslant i\leqslant n}\frac{\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}, P_1=\frac{(1-\omega)|a_{1n}|+\omega\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|}, \\ P_2=\max\limits_{1<i<n}\frac{(1-\omega)|a_{i, n-i+1}|+\omega\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\omega\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}, P_3=\frac{(1-\omega)|a_{n1}|}{|a_{n1}|-\omega\sum\nolimits_{j=2}^{n}|a_{nj}|}. \end{array} $

(ⅰ)比较$N_1, P_1$,

$ \begin{align*} P_1-N_1=\frac{(1-\omega)|a_{1n}|+\omega\sum\nolimits_{j=1}^{n-1}|a_{1j}|} {|a_{1n}|}-\frac{\sum\nolimits_{j=1}^{n-1}|a_{1j}|}{|a_{1n}|} =\frac{(1-\omega)(|a_{1n}|-\sum\nolimits_{j=1}^{n-1}|a_{1j}|)}{|a_{1n}|}>0, \end{align*} $

故$N_1 < P_1$.

(ⅱ)比较$N_2, P_2$.若$N_2, P_2$同行,

$ \begin{align*} P_2-N_2=\, &\frac{(1-\omega)|a_{i, n-i+1}|+\omega\sum\nolimits_{j=1}^{n-i}|a_{ij}|}{|a_{i, n-i+1}|-\omega\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}-\frac{\sum\nolimits_{j=1}^{n-i}|a_{ij}|} {|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|}\\[3mm] =\, &\frac{(1-\omega)|a_{i, n-i+1}|^2-(1-\omega)|a_{i, n-i+1}| \sum\nolimits_{j=1}^{n-i}|a_{ij}|-(1-\omega)|a_{i, n-i+1}|\sum\nolimits_{j= n-i+2}^{n}|a_{ij}|}{(|a_{i, n-i+1}|-\omega\sum\nolimits_{j=n-i+ 2}^{n}|a_{ij}|)(|a_{i, n-i+1}|-\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}\\[3mm] =\, &\frac{(1-\omega)|a_{i, n-i+1}|(|a_{i, n-i+1}|-\sum\nolimits_{j=1}^{n-i}|a_{ij}| -\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}{(|a_{i, n-i+1}| -\omega\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)(|a_{i, n-i+1}| -\sum\nolimits_{j=n-i+2}^{n}|a_{ij}|)}. \end{align*} $

因为$A$严格次对角占优, 故上式大于0.即$N_2 < P_2.$

若$N_2, P_2$不同行, 设与$N_2$同行的为$\hat{P}_1$, 则$N_2 < \hat{P}_2.$又因为$\hat{P}_2 < P_2$, 所以$N_2 < P_2.$综上所述, $N=\max\{N_1, N_2, 0\} < \max\{P_1, P_2\}\leqslant \max\{P_1, P_2, P_3\}=P.$所以

$\begin{align*} \|x^{(k)}-x^*\|_{\infty}\leqslant \frac{N^k}{1-N}\|x^{(1)}-x^{(0)}\|_{\infty}\leqslant \frac{P^k}{1-P}\|x^{(1)}-x^{(0)}\|_{\infty}. \end{align*} $

4 小结

本文证明了当线性方程组的系数矩阵严格次对角占优时, Jacobi、Guass-Seidel和SOR迭代法均收敛, 并给出了相应的误差估计.通过比较三种迭代法的误差上界, 发现Guass-Seidel迭代法的误差上界最小.