第六章 解线性方程组的迭代法

6.1 迭代法的基本概念

6.1.1 迭代法的介绍

• 迭代法的思路

  • 将 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 改写为 $\mathit{x}=\mathit{B}\mathit{x}+\mathit{f}$$\bm x = \bm B \bm x + \bm f$.

    • 一般取 $\mathit{B}=\mathit{I}-\mathit{A}$$\bm B = \bm I - \bm A$，于是 $\mathit{f}=\mathit{b}$$\bm f = \bm b$.

    • 或者取 $\mathit{A}=\mathit{M}-\mathit{N}$$\bm A = \bm M - \bm N$，于是 $\mathit{M}\mathit{x}=\mathit{N}\mathit{x}+\mathit{b}$$\bm M \bm x = \bm N \bm x + \bm b$.

    • 其中 $\mathit{M}$$\bm M$ 称为分裂矩阵，$\mathit{B}$$\bm B$ 称为迭代矩阵.

  • 唯一解：${\mathit{x}}^{\ast }=\mathit{B}{\mathit{x}}^{\ast }+\mathit{f}$$\bm x^* = \bm B \bm x^* + \bm f$.

  • 迭代：${\mathit{x}}^{(k+1)}=\mathit{B}{\mathit{x}}^{(k)}+\mathit{f}$$\bm x^{(k+1)} = \bm B \bm x^{(k)} + \bm f$.

• 迭代法的性能

  • 收敛：即 ${\mathit{x}}^{\ast }=\underset{k\to \mathrm{\infty }}{lim}{\mathit{x}}^k$$\bm x^* = \clim k \bm x^{k}$ 存在.

  • 误差向量：${\mathit{\epsilon }}^{(k+1)}={\mathit{x}}^{(k+1)}-{\mathit{x}}^{\ast }=\mathit{B}{\mathit{\epsilon }}^{(k)}$$\bm \ve^{(k+1)} = \bm x^{(k+1)} - \bm x^* = \bm B \bm \ve^{(k)}$.

  • 收敛等价条件：$\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}$$\clim k \bm B^k = \bm 0$.

6.1.2 序列的极限

• 极限的定义

  • 向量序列：$\underset{k\to \mathrm{\infty }}{lim}{\mathit{x}}^{(k)}=\mathit{x}\iff \underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{x}}^{(k)}-\mathit{x}\Vert =0$$\clim k \bm x^{(k)} = \bm x \RLA \clim k \Norm{\bm x^{(k)} - \bm x} = 0$.

  • 矩阵序列：$\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k=\mathit{A}\iff \underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{A}}_k-\mathit{A}\Vert =0$$\clim k \bm A_k = \bm A \RLA \clim k \Norm{\bm A_k - \bm A} = 0$.

• 极限的定理

  • $\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k=\mathbf{0}\iff \mathrm{\forall }\mathit{x}\in {\mathbb{R}}^n:\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k\mathit{x}=\mathbf{0}$$\clim k \bm A_k = \bm 0 \RLA \forall \bm x \in \R^n \colon \clim k \bm A_k \bm x = \bm 0$.

  • $\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}\iff \rho (\mathit{B})<1\iff \mathrm{\exists }\Vert \cdot {\Vert }_c:\Vert \mathit{B}{\Vert }_c<1$$\clim k \bm B^k = \bm 0 \RLA \rho(\bm B) < 1 \RLA \exist \Norm{\cdot}_c \colon \Norm{\bm B}_c < 1$.

  • $\underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{B}}^k{\Vert }^{\frac{1}{k}}=\rho (\mathit{B})$$\clim k \Norm{\bm B^k}^\tfrac{1}{k} = \rho(\bm B)$.

证明

1. $\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k=\mathbf{0}\iff \mathrm{\forall }\mathit{x}\in {\mathbb{R}}^n:\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k\mathit{x}=\mathbf{0}$$\clim k \bm A_k = \bm 0 \RLA \forall \bm x \in \R^n \colon \clim k \bm A_k \bm x = \bm 0$.

1.1 充分性

若 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k=\mathbf{0}$$\clim k \bm A_k = \bm 0$，则 $\underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{A}}_k\Vert =0$$\clim k \Norm{\bm A_k} = 0$，从而对于 $\mathrm{\forall }\mathit{x}\in {\mathbb{R}}^n$$\forall \bm x \in \R^n$，

有 $\underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{A}}_k\mathit{x}\Vert \le \underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{A}}_k\Vert \Vert \mathit{x}\Vert =0$$\clim k \Norm{\bm A_k \bm x} \le \clim k \Norm{\bm A_k} \Norm{\bm x} = 0$，即 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k\mathit{x}=\mathbf{0}$$\clim k \bm A_k \bm x = \bm 0$.

1.2 必要性

取 $\mathit{x}={\mathit{e}}_i$$\bm x = \bm e_i$，即可得到 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{A}}_k$$\clim k \bm A_k$ 的第 $i$$i$ 个分量为零. 证毕.

2. $\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}\iff \rho (\mathit{B})<1\iff \mathrm{\exists }\Vert \cdot {\Vert }_c:\Vert \mathit{B}{\Vert }_c<1$$\clim k \bm B^k = \bm 0 \RLA \rho(\bm B) < 1 \RLA \exist \Norm{\cdot}_c \colon \Norm{\bm B}_c < 1$.

2.1 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}\Rightarrow \rho (\mathit{B})<1$$\clim k \bm B^k = \bm 0 \RA \rho(\bm B) < 1$.

若 $\lambda \ge 1$$\lambda \ge 1$，则 $\mathrm{\exists }\mathit{x}\ne \mathbf{0}:\mathit{B}\mathit{x}=\lambda \mathit{x}$$\exist \bm x \ne \bm 0 \colon \bm B \bm x = \lambda \bm x$，于是 $\Vert {\mathit{B}}^k\mathit{x}\Vert ={\left|\lambda \right|}^k\Vert \mathit{x}\Vert \ne 0$$\Norm{\bm B^k \bm x} = \vqty{\lambda}^k \Norm{\bm x} \ne 0$，矛盾.

2.2 $\rho (\mathit{B})<1\Rightarrow \mathrm{\exists }\Vert \cdot {\Vert }_c:\Vert \mathit{B}{\Vert }_c<1$$\rho(\bm B) < 1 \RA \exist \Norm{\cdot}_c \colon \Norm{\bm B}_c < 1$.

由第 5 章定理 18 即得.

2.3 $\mathrm{\exists }\Vert \cdot {\Vert }_c:\Vert \mathit{B}{\Vert }_c<1\Rightarrow \underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}$$\exist \Norm{\cdot}_c \colon \Norm{\bm B}_c < 1 \RA \clim k \bm B^k = \bm 0$.

$\underset{k\to \mathrm{\infty }}{lim}\Vert {\mathit{B}}^k{\Vert }_c\le \underset{k\to \mathrm{\infty }}{lim}\Vert \mathit{B}{\Vert }_c^k=\mathbf{0}$$\clim k \Norm{\bm B^k}_c \le \clim k \Norm{\bm B}_c^k = \bm 0$.

证毕.

6.1.3 迭代法的收敛性

定理 5 一阶定常迭代法收敛 $\iff \rho (\mathit{B})<1$$\RLA \rho(\bm B) < 1$.

证明

1. 充分性：$\rho (\mathit{B})<1\Rightarrow$$\rho(\bm B) < 1 \RA$ 迭代法收敛.

由

得

又 $\rho (\mathit{B})<1$$\rho(\bm B) < 1$，知

2. 必要性：迭代法收敛 $\Rightarrow \rho (\mathit{B})<1$$\RA \rho(\bm B) < 1$.

若 $\mathrm{\forall }{\mathit{x}}^{(0)}:\underset{k\to \mathrm{\infty }}{lim}{\mathit{x}}^{(k)}={\mathit{x}}^{\ast }$$\forall \bm x^{(0)} \colon \clim k \bm x^{(k)} = \bm x^*$，

则 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{\epsilon }}^{(k)}=\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k{\mathit{\epsilon }}^{(0)}=\mathbf{0}$$\clim k \bm \ve^{(k)} = \clim k \bm B^{k} \bm \ve^{(0)} = \bm 0$，

于是 $\underset{k\to \mathrm{\infty }}{lim}{\mathit{B}}^k=\mathbf{0}$$\clim k \bm B^k = \bm 0$，从而 $\rho (\mathit{B})<1$$\rho(\bm B) < 1$. 证毕.

定理 6（误差估计） 对于一阶定常迭代法，若存在某种算子范数使得 $\Vert \mathit{B}\Vert =q<1$$\Norm{\bm B} = q < 1$，则

1. 迭代法收敛，即 $\mathrm{\forall }{\mathit{x}}^{(0)}:(\underset{k\to \mathrm{\infty }}{lim}{\mathit{x}}^{(k)}={\mathit{x}}^{\ast })\wedge ({\mathit{x}}^{\ast }=\mathit{B}{\mathit{x}}^{\ast }+\mathit{f})$$\forall \bm x^{(0)} \colon \pqty{\clim k \bm x^{(k)} = \bm x^*} \and \pqty{\bm x^{*} = \bm B \bm x^* + \bm f}$.

2. $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert \le q^k\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(0)}\Vert$$\Norm{\bm x^* - \bm x^{(k)}} \le q^k \Norm{\bm x^* - \bm x^{(0)}}$.

3. $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert \le {\displaystyle \frac{q}{1-q}}\Vert {\mathit{x}}^{(k)}-{\mathit{x}}^{(k-1)}\Vert$$\Norm{\bm x^* - \bm x^{(k)}} \le \dfrac{q}{1 - q} \Norm{\bm x^{(k)} - \bm x^{(k-1)}}$.

4. $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert \le {\displaystyle \frac{q^k}{1-q}}\Vert {\mathit{x}}^{(1)}-{\mathit{x}}^{(0)}\Vert$$\Norm{\bm x^* - \bm x^{(k)}} \le \dfrac{q^k}{1 - q} \Norm{\bm x^{(1)} - \bm x^{(0)}}$.

证明

1. $\rho (\mathit{B})\le \Vert \mathit{B}\Vert <1$$\rho(\bm B) \le \Norm{\bm B} < 1$，由定理 5 得证.

2. $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert =\Vert {\mathit{B}}^k({\mathit{x}}^{\ast }-{\mathit{x}}^{(0)})\Vert \le q^k\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(0)}\Vert$$\Norm{\bm x^* - \bm x^{(k)}} = \Norm{\bm B^k (\bm x^* - \bm x^{(0)})} \le q^k \Norm{\bm x^* - \bm x^{(0)}}$.

3. $\Vert {\mathit{x}}^{(k+1)}-{\mathit{x}}^{(k)}\Vert \ge \Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert -\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k+1)}\Vert \ge (1-q)\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert$$\Norm{\bm x^{(k+1)} - \bm x^{(k)}} \ge \Norm{\bm x^* - \bm x^{(k)}} - \Norm{\bm x^* - \bm x^{(k+1)}} \ge (1 - q) \Norm{\bm x^* - \bm x^{(k)}}$.

   于是 $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert \le {\displaystyle \frac{1}{1-q}}\Vert {\mathit{x}}^{(k+1)}-{\mathit{x}}^{(k)}\Vert \le {\displaystyle \frac{q}{1-q}}\Vert {\mathit{x}}^{(k)}-{\mathit{x}}^{(k-1)}\Vert$$\Norm{\bm x^* - \bm x^{(k)}} \le \dfrac{1}{1 - q} \Norm{\bm x^{(k + 1)} - \bm x^{(k)}} \le \dfrac{q}{1 - q} \Norm{\bm x^{(k)} - \bm x^{(k-1)}}$.

4. 由 ${\mathit{x}}^{(k+1)}-{\mathit{x}}^{(k)}=\mathit{B}({\mathit{x}}^{(k)}-{\mathit{x}}^{(k-1)})$$\bm x^{(k+1)} - \bm x^{(k)} = \bm B (\bm x^{(k)} - \bm x^{(k-1)})$ 和第三点即得.

命题（收敛速度）

1. $\Vert {\mathit{B}}^k\Vert =sup\{\Vert {\mathit{\epsilon }}^{(k)}\Vert /\Vert {\mathit{\epsilon }}^{(0)}\Vert |{\mathit{\epsilon }}^{(0)}\ne \mathbf{0}\}$$\Norm{\bm B^k} = \sup \Bqty{ \left. \left. {\Norm{\bm \ve^{(k)}}} \right/ {\Norm{\bm \ve^{(0)}}} \ \right |\ \bm \ve^{(0)} \ne \bm 0 }$.

2. $\mathrm{\forall }{\mathit{\epsilon }}^{(0)}:{\displaystyle \frac{\Vert {\mathit{\epsilon }}^{(k)}\Vert }{\Vert {\mathit{\epsilon }}^{(0)}\Vert }}\le \sigma ={10}^{-s}\iff k\ge {\displaystyle \frac{s\ln 10}{-\ln \Vert {\mathit{B}}^k{\Vert }^{\frac{1}{k}}}}$$\forall \bm \ve^{(0)} \colon \dfrac{\Norm{\bm \ve^{(k)}}}{\Norm{\bm \ve^{(0)}}} \le \sigma = 10^{-s} \RLA k \ge \dfrac{s \ln 10}{-\ln \Norm{\bm B^k}^\tfrac{1}{k}}$.

证明

1. 上确界

   1. 由 ${\mathit{\epsilon }}^{(k)}={\mathit{B}}^k{\mathit{\epsilon }}^{(0)}$$\bm \ve^{(k)} = \bm B^k \bm \ve^{(0)}$，有 ${\displaystyle \frac{\Vert {\mathit{\epsilon }}^{(k)}\Vert }{\Vert {\mathit{\epsilon }}^{(0)}\Vert }}\le \Vert {\mathit{B}}^k\Vert$$\dfrac{\Norm{\bm \ve^{(k)}}}{\Norm{\bm \ve^{(0)}}} \le \Norm{\bm B^k}$，

   2. 并且 ${\displaystyle \Vert {\mathit{B}}^k\Vert =\underset{{\mathit{\epsilon }}^{(0)}\ne \mathbf{0}}{max}{\displaystyle \frac{\Vert {\mathit{B}}^k{\mathit{\epsilon }}^{(0)}\Vert }{{\mathit{\epsilon }}^{(0)}}}=\underset{{\mathit{\epsilon }}^{(0)}\ne \mathbf{0}}{max}{\displaystyle \frac{\Vert {\mathit{\epsilon }}^{(k)}\Vert }{{\mathit{\epsilon }}^{(0)}}}}$$\d \Norm{\bm B^k} = \max_{\bm \ve^{(0)} \ne \bm 0} \dfrac{\Norm{\bm B^k \bm \ve^{(0)}}}{\bm \ve^{(0)}} = \max_{\bm \ve^{(0)} \ne \bm 0} \dfrac{\Norm{\bm \ve^{(k)}}}{\bm \ve^{(0)}}$.

2. 由 $\Vert {\mathit{B}}^k\Vert \le \sigma ={10}^{-s}$$\Norm{\bm B^k} \le \sigma = 10^{-s}$ 即得.

定义（收敛速度） 对于一阶定常迭代法，

1. 平均收敛速度：$R_k(\mathit{B}):=-\ln \Vert {\mathit{B}}^k{\Vert }^{\frac{1}{k}}$$R_k(\bm B) := -\ln\Norm{\bm B^k}^\tfrac{1}{k}$.

2. 渐进收敛速度：$R(\mathit{B}):=-\ln \rho (\mathit{B})$$R(\bm B) := -\ln\rho(\bm B)$.

备注

• $R(\mathit{B})=\underset{k\to \mathrm{\infty }}{lim}{R}_k(\mathit{B})$$R(\bm B) = \clim k R_k(\bm B)$，与迭代次数和范数类型无关.

• 收敛所需迭代次数：$k\ge {\displaystyle \frac{s\ln 10}{R(\mathit{B})}}$$k \ge \dfrac{s \ln 10}{R(\bm B)}$.

6.2 J 迭代法与 GS 迭代法

6.2.1 雅可比迭代法

1. $\mathit{A}$$\bm A$ 的分解

   1. $\mathit{A}=\mathit{D}-\mathit{L}-\mathit{U}$$\bm A = \bm D - \bm L - \bm U$.

   2. $\mathit{M}:=\mathit{D},\mathit{N}:=\mathit{L}+\mathit{U}$$\bm M := \bm D, \bm N := \bm L + \bm U$.

2. $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 的转换

   1. $\mathit{D}{\mathit{x}}^{(k+1)}=(\mathit{L}+\mathit{U}){\mathit{x}}^{(k)}+\mathit{b}$$\bm D \bm x^{(k+1)} = (\bm L + \bm U) \bm x^{(k)} + \bm b$.

   2. ${\mathit{x}}^{(k+1)}={\mathit{D}}^{-1}(\mathit{L}+\mathit{U}){\mathit{x}}^{(k)}+{\mathit{D}}^{-1}\mathit{b},k\in \mathbb{N}$$\bm x^{(k+1)} = \bm D\inv (\bm L + \bm U) \bm x^{(k)} + \bm D\inv \bm b, k \in \N$.

   3. $\mathit{J}:={\mathit{D}}^{-1}(\mathit{L}+\mathit{U})$$\bm J := \bm D\inv (\bm L + \bm U)$.

6.2.2 高斯-塞德尔迭代法

1. $\mathit{A}$$\bm A$ 的分解

   1. $\mathit{A}=\mathit{D}-\mathit{L}-\mathit{U}$$\bm A = \bm D - \bm L - \bm U$.

   2. $\mathit{M}=\mathit{D}-\mathit{L},\mathit{N}=\mathit{U}$$\bm M = \bm D - \bm L, \bm N = \bm U$.

2. $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 的转换

   1. $(\mathit{D}-\mathit{L}){\mathit{x}}^{(k+1)}=\mathit{U}{\mathit{x}}^{(k)}+\mathit{b},k\in \mathbb{N}$$(\bm D - \bm L) \bm x^{(k+1)} = \bm U \bm x^{(k)} + \bm b, k \in \N$.

   2. $\mathit{D}{\mathit{x}}^{(k+1)}=\mathit{L}{\mathit{x}}^{(k+1)}+\mathit{U}{\mathit{x}}^{(k)}+\mathit{b},k\in \mathbb{N}$$\bm D \bm x^{(k+1)} = \bm L \bm x^{(k+1)} + \bm U \bm x^{(k)} + \bm b, k \in \N$.

   3. $\mathit{G}:=(\mathit{D}-\mathit{L}{)}^{-1}\mathit{U}$$\bm G := (\bm D - \bm L)\inv \bm U$.

6.2.3 雅可比迭代与高斯-塞德尔迭代收敛性

• 迭代法收敛的条件：设 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$，各矩阵如上定义，且 $\mathit{D}$$\bm D$ 非奇异，则

  • 雅可比迭代法收敛 $\iff \rho (\mathit{J})<1\Leftarrow \Vert \mathit{J}\Vert <1$$\RLA \rho(\bm J) < 1 \LA \Norm{\bm J} < 1$.

  • 高斯-塞德尔迭代法收敛 $\iff \rho (\mathit{G})<1\Leftarrow \Vert \mathit{G}\Vert <1$$\RLA \rho(\bm G) < 1 \LA \Norm{\bm G} < 1$.

• 对角占优矩阵

  • 严格对角占优矩阵：$\left|a_{ii}\right|>{\displaystyle \sum _{j=1,j\ne i}^n\left|a_{ij}\right|,i=1,2,\cdots ,n}$$\vqty{a_{ii}} > \dsum_{j=1, j\ne i}^n \vqty{a_{ij}}, i = \oneton$.

  • 弱对角占优矩阵：$\left|a_{ii}\right|\ge {\displaystyle \sum _{j=1,j\ne i}^n\left|a_{ij}\right|,i=1,2,\cdots ,n}$$\vqty{a_{ii}} \ge \dsum_{j=1, j\ne i}^n \vqty{a_{ij}}, i = \oneton$，且至少一个不等式严格成立.

• 可约矩阵

  • 可约矩阵：存在置换阵 $\mathit{P}$$\bm P$ 使得 $\begin{array}{c}{\mathit{P}}^{\mathrm{T}}\mathit{A}\mathit{P}=\left(\begin{array}{cc}{\mathit{A}}_{11}& {\mathit{A}}_{12}\\ \mathbf{0}& {\mathit{A}}_{22}\end{array}\right)\end{array}$$\bm P\trans \bm A \bm P = \begin{pmatrix} \bm A_{11} & \bm A_{12} \\ \bm 0 & \bm A_{22} \end{pmatrix}$，其中 ${\mathit{A}}_{11}$$\bm A_{11}$ 和 ${\mathit{A}}_{22}$$\bm A_{22}$ 均为方阵.

    • 三对角方阵是不可约阵.

    • 若所有元素非零，则为不可约阵.

  • 若可约，则 ${\mathit{P}}^{\mathrm{T}}\mathit{A}\mathit{P}({\mathit{P}}^{\mathrm{T}}\mathit{x})={\mathit{P}}^{\mathrm{T}}\mathit{b}$$\bm P\trans \bm A \bm P (\bm P\trans \bm x) = \bm P\trans \bm b$，于是可化为低阶方程组求解.

    • 记 ${\mathit{P}}^{\mathrm{T}}\mathit{x}={({\mathit{y}}_1,{\mathit{y}}_2)}^{\mathrm{T}},{\mathit{P}}^{\mathrm{T}}\mathit{b}=({\mathit{d}}_1,{\mathit{d}}_2{)}^{\mathrm{T}}$$\bm P\trans \bm x = \pqty{\bm y_1, \bm y_2}\trans, \bm P\trans \bm b = (\bm d_1, \bm d_2)\trans$，其中 ${\mathit{y}}_1,{\mathit{d}}_1$$\bm y_1, \bm d_1$ 与 ${\mathit{A}}_{11}$$\bm A_{11}$ 维度相同.

    • 则 $\begin{array}{c}\mathit{A}\mathit{x}=\mathit{b}\iff \{\begin{array}{l}{\mathit{A}}_{11}{\mathit{y}}_1+{\mathit{A}}_{12}{\mathit{y}}_2={\mathit{d}}_1,\\ {\mathit{A}}_{22}{\mathit{y}}_2={\mathit{d}}_2.\end{array}\end{array}$$\bm A \bm x = \bm b \RLA \begin{cases} \bm A_{11} \bm y_1 + \bm A_{12} \bm y_2 = \bm d_1, \\ \hspace{3.95em} \bm A_{22} \bm y_2 = \bm d_2. \end{cases}$，求解顺序：${\mathit{y}}_2\to {\mathit{y}}_1\to \mathit{x}$$\bm y_2 \ra \bm y_1 \ra \bm x$.

定理 8（对角占优定理） 严格对角占优矩阵、不可约弱对角占优矩阵，是非奇异矩阵.

证明

1. 严格对角占优矩阵是非奇异矩阵.

若 $\det \left(\mathit{A}\right)=0$$\det(\bm A) = 0$，则 $\mathit{A}\mathit{x}=\mathbf{0}$$\bm A \bm x = \bm 0$ 有非零解 $\mathit{x}=(x_1,x_2,\cdots ,x_n{)}^{\mathrm{T}}$$\bm x = (\soneto{x}{n})\trans$，

记 $\left|x_k\right|={\displaystyle \underset{1\le i\le n}{max}\left|x_i\right|}$$\vqty{x_k} = \d\max_{1 \le i \le n} \vqty{x_i}$，由齐次方程组第 $k$$k$ 个方程 ${\displaystyle \sum _{j=1}^n{a}_{kj}{x}_j=0}$$\dsum_{j=1}^n a_{kj} x_j = 0$ 有，

从而 $\left|a_{kk}\right|\le {\displaystyle \sum _{j=1,j\ne k}^n\left|a_{kj}\right|}$$\vqty{a_{kk}} \le \dsum_{j=1, j \ne k}^n \vqty{a_{kj}}$，矛盾.

2. 不可约弱对角占优矩阵是非奇异矩阵.

若 $\det \left(\mathit{A}\right)=0$$\det(\bm A) = 0$，则 $\mathit{A}\mathit{x}=\mathbf{0}$$\bm A \bm x = \bm 0$ 有非零解 $\mathit{x}=(x_1,x_2,\cdots ,x_n{)}^{\mathrm{T}}$$\bm x = (\soneto{x}{n})\trans$，

2.1 对于弱对角占优矩阵，如下定义集合，并证明集合非空.

若 $J$$J$ 为空，则 $\left|x_1\right|=\left|x_2\right|=\cdots =\left|x_n\right|$$\vqty{x_1} = \vqty{x_2} = \cdots = \vqty{x_n}$，

于是对于 $\mathrm{\forall }i$$\forall i$，由 ${\displaystyle \sum _{j=1}^n{a}_{ij}{x}_j=0}$$\dsum_{j=1}^n a_{ij} x_j = 0$ 有

从而 $\mathrm{\forall }i:\left|a_{ii}\right|\le {\displaystyle \sum _{j\ne i}\left|a_{ij}\right|}$$\forall i \colon \vqty{a_{ii}} \le \dsum_{j \ne i} \vqty{a_{ij}}$，与弱对角占优矩阵矛盾.

2.2 对于不可约矩阵，进一步证明非奇异性.

于是 $\mathrm{\forall }j(\left|x_j\right|<\left|x_k\right|):a_{kj}=0$$\forall j \pqty{\vqty{x_j} < \vqty{x_k}} \colon a_{kj} = 0$，即 $\mathrm{\forall }k\in J,\mathrm{\forall }j\notin J:a_{kj}=0$$\forall k \in J, \forall j \notin J \colon a_{kj} = 0$，

从而可排列为分块上三角矩阵，矛盾. 证毕.

备注 弱对角占优矩阵不一定非奇异，如 $\begin{array}{c}\left|\begin{array}{ccc}1& 0& -1\\ 1& 2& 0\\ -3& 0& 3\end{array}\right|=0\end{array}$$\left| \begin{array}{ccc} 1 & 0 & -1 \\ 1 & 2 & 0 \\ -3 & 0 & 3 \\ \end{array} \right| = 0$.

定理 9 若满足下述条件之一，则解 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$ 的 J 迭代法与 GS 迭代法均收敛.

1. $\mathit{A}$$\bm A$ 为严格对角占优矩阵.

2. $\mathit{A}$$\bm A$ 为不可约弱对角占优矩阵.

证明

1. 严格对角占优矩阵 → GS 迭代法收敛.

考虑 $\mathit{G}=(\mathit{D}-\mathit{L}{)}^{-1}\mathit{U}$$\bm G = (\bm D - \bm L) \inv \bm U$ 的特征值，即下述方程的解

其中系数 $\det ((\mathit{D}-\mathit{L}{)}^{-1})\ne 0$$\det((\bm D - \bm L)\inv) \ne 0$，于是特征值即 $\det (\lambda (\mathit{D}-\mathit{L})-\mathit{U})=0$$\det(\lambda(\bm D - \bm L) - \bm U) = 0$ 的根. 记

当 $\left|\lambda \right|\ge 1$$\vqty{\lambda} \ge 1$ 时，

从而 $\mathit{C}$$\bm C$ 为严格对角占优矩阵，从而 $\det \left(\mathit{C}\right)\ne 0$$\det(\bm C) \ne 0$，从而 $\mathrm{\forall }\lambda :\left|\lambda \right|<1$$\forall \lambda \colon \vqty{\lambda} < 1$.

2. 其余条件同理可证. 证毕.

定理 10 设 $\mathit{A}$$\bm A$ 对称，且 $\mathrm{\forall }i:a_{ii}>0$$\forall i \colon a_{ii} > 0$，则

1. J 迭代法收敛 $\iff$$\RLA$ $\mathit{A}$$\bm A$ 和 $2\mathit{D}-\mathit{A}$$2 \bm D -\bm A$ 均为正定矩阵.

2. GS 迭代法收敛 $\Leftarrow \mathit{A}$$\LA \bm A$ 正定.

证明 略.

特殊的，对于二阶矩阵有

$$\begin{array}{c}{\mathit{B}}_{\mathrm{J}}=\left(\begin{array}{cc}0& -{\displaystyle \frac{a_{12}}{a_{11}}}\\ -{\displaystyle \frac{a_{21}}{a_{22}}}& 0\end{array}\right),\rho ({\mathit{B}}_{\mathrm{J}})=\sqrt{\left|{\displaystyle \frac{a_{12}{a}_{21}}{a_{11}{a}_{22}}}\right|},\end{array}$$

$$\begin{array}{c}{\mathit{B}}_{\mathrm{S}}=\left(\begin{array}{cc}0& -{\displaystyle \frac{a_{12}}{a_{11}}}\\ 0& {\displaystyle \frac{a_{12}{a}_{21}}{a_{11}{a}_{22}}}\end{array}\right),\rho ({\mathit{B}}_{\mathrm{S}})=\left|{\displaystyle \frac{a_{12}{a}_{21}}{a_{11}{a}_{22}}}\right|.\end{array}$$

故 J 迭代法与 GS 迭代法同时收敛或发散.

$$\begin{array}{rl}R({\mathit{B}}_{\mathrm{J}})& =-\ln \rho ({\mathit{B}}_{\mathrm{J}})=-{\displaystyle \frac{1}{2}}\ln \left|{\displaystyle \frac{a_{12}{a}_{21}}{a_{11}{a}_{22}}}\right|,\\ R({\mathit{B}}_{\mathrm{S}})& =-\ln \rho ({\mathit{B}}_{\mathrm{S}})=-\ln \left|{\displaystyle \frac{a_{12}{a}_{21}}{a_{11}{a}_{22}}}\right|,\end{array}$$

故二者收敛速度之比为 $1:2$$1 : 2$.

---

6.3 超松弛迭代法

6.3.1 逐次超松弛迭代法 SOR

• $\mathit{A}=\mathit{M}-\mathit{N}$$\bm A = \bm M - \bm N$.

  • $\mathit{A}=\mathit{D}-\mathit{L}-\mathit{U}$$\bm A = \bm D - \bm L - \bm U$.

  • $\mathit{M}={\displaystyle \frac{1}{\omega }}(\mathit{D}-\omega \mathit{L})$$\bm M = \dfrac{1}{\omega} (\bm D - \omega \bm L)$.

  • $\mathit{N}={\displaystyle \frac{1-\omega }{\omega }}\mathit{D}+\mathit{U}$$\bm N = \dfrac{1-\omega}{\omega} \bm D + \bm U$.

• $\mathit{A}\mathit{x}=\mathit{b}\iff \mathit{x}={\mathit{L}}_{\omega }\mathit{x}+\mathit{f}$$\bm A \bm x = \bm b \RLA \bm x = \bm L_\omega \bm x + \bm f$.

  • $(\mathit{D}-\omega \mathit{L})\mathit{x}=((1-\omega )\mathit{D}+\omega \mathit{U})\mathit{x}+\omega \mathit{b}$$(\bm D - \omega \bm L) \bm x = \pqty{(1 - \omega) \bm D + \omega \bm U} \bm x + \omega \bm b$.

  • ${\mathit{L}}_{\omega }=(\mathit{D}-\omega \mathit{L}{)}^{-1}((1-\omega )\mathit{D}+\omega \mathit{U})$$\bm L_\omega = (\bm D - \omega \bm L)\inv ((1 - \omega) \bm D + \omega \bm U)$.

  • $\mathit{f}=\omega (\mathit{D}-\omega \mathit{L}{)}^{-1}\mathit{b}$$\bm f = \omega(\bm D - \omega \bm L)\inv \bm b$.

• 迭代

  • 写法一：${\mathit{x}}^{(k+1)}={\mathit{L}}_{\omega }{\mathit{x}}^{(k)}+\mathit{f},k\in \mathbb{N}$$\bm x^{(k+1)} = \bm L_\omega \bm x^{(k)} + \bm f, k \in \N$.

  • 写法二：${\mathit{x}}^{(k+1)}={\mathit{x}}^{(k)}+\omega {\mathit{D}}^{-1}(\mathit{b}+\mathit{L}{\mathit{x}}^{(k+1)}+\mathit{U}{\mathit{x}}^{(k)}-\mathit{D}{\mathit{x}}^{(k)})$$\bm x^{(k+1)} = \bm x^{(k)} + \omega \bm D\inv (\bm b + \bm L \bm x^{(k+1)} + \bm U \bm x^{(k)} - \bm D \bm x^{(k)})$.

  • 写法三：$\mathrm{\Delta }{x}_i={\displaystyle \frac{\omega }{a_{ii}}}(b_i-{\displaystyle \sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-{\displaystyle \sum _{j=i}^n{a}_{ij}{x}_j^{(k)}}})$$\Delta x_i = \dfrac{\omega}{a_{ii}} \pqty{b_i - \dsum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \dsum_{j=i}^n a_{ij} x_j^{(k)}}$.

  • 写法四：利用高斯-塞德尔迭代法得到 ${\tilde{\mathit{x}}}^{(k+1)}$$\wt{\bm x}^{(k+1)}$，则 ${\mathit{x}}^{(k+1)}=(1-\omega ){\mathit{x}}^{(k)}+\omega {\tilde{\mathit{x}}}^{(k+1)}$$\bm x^{(k+1)} = (1 - \omega) \bm x^{(k)} + \omega \wt{\bm x}^{(k+1)}$.

• 参数说明

  • 当 $\omega =1$$\omega = 1$ 时，退化为高斯-塞德尔迭代法.

  • 当 $\omega >1$$\omega > 1$ 时，称为超松弛迭代法.

  • 当 $\omega <1$$\omega < 1$ 时，称为低松弛迭代法.

6.3.2 SOR 迭代法的收敛性

定理（SOR 迭代法的收敛性） 对于 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \bm b$，SOR 迭代法收敛性的条件为：

1. 必要条件：$0<\omega <2$$0 < \omega < 2$.

2. 充分条件：$0<\omega <2$$0 < \omega < 2$ 且 $\mathit{A}$$\bm A$ 对称正定.

3. 充分条件：$0<\omega \le 1$$0 < \omega \le 1$ 且 $\mathit{A}$$\bm A$ 严格对角占优或不可约弱对角占优.

证明

1. 必要条件：$0<\omega <2$$0 < \omega < 2$.

2. 充分条件：$0<\omega <2$$0 < \omega < 2$ 且 $\mathit{A}$$\bm A$ 对称正定.

由 ${\mathit{L}}_{\omega }=(\mathit{D}-\omega \mathit{L}{)}^{-1}((1-\omega )\mathit{D}+\omega \mathit{U})$$\bm L_\omega = (\bm D - \omega \bm L)\inv ((1 - \omega) \bm D + \omega \bm U)$，对于某一特征值 $\lambda$$\lambda$，${\mathit{L}}_{\omega }\mathit{y}=\lambda \mathit{y}$$\bm L_\omega \bm y = \lambda \bm y$，故

记

由于 $\mathit{A}={\mathit{A}}^{\mathrm{T}}$$\bm A = \bm A\trans$，有 $\mathit{U}={\mathit{L}}^{\mathrm{T}}$$\bm U = \bm L\trans$，于是

从而

由于 $0<\omega <2$$0 < \omega < 2$，分子不为零，且有

从而 $\left|\lambda \right|<1$$\vqty{\lambda} < 1$，从而 SOR 迭代法收敛.

3. 充分条件：$0<\omega \le 1$$0 < \omega \le 1$ 且 $\mathit{A}$$\bm A$ 严格对角占优或不可约弱对角占优.

此时 GS 迭代法收敛，其相关量均用波浪线区分（如迭代矩阵为 $\tilde{\mathit{B}}$$\wt{\bm B}$）则存在算子范数使得 $\Vert \tilde{\mathit{B}}\Vert =\tilde{q}<1$$\Norm{\wt{\bm B}} = \wt q < 1$. 将迭代方程拆分为：

注意第一式右侧是 ${\mathit{x}}^{(k)}$$\bm x^{(k)}$ 而不是 ${\tilde{\mathit{x}}}^{(k)}$$\wt{\bm x}^{(k)}$. 于是

其中 $1-\omega +\omega \tilde{q}<1$$1 - \omega + \omega \wt q < 1$，故 SOR 迭代法收敛.

备注 对称正定三对角矩阵有最优松弛参数 ${\omega }_{\mathrm{opt}}={\displaystyle \frac{2}{1+\sqrt{1-\rho (\mathit{J}{)}^2}}}$$\omega_\rm{opt} = \dfrac{2}{ 1 + \sqrt{1 - \rho(\bm J)^2} }$.