第六章作业

6.1 复习与思考题

6.1.1 迭代法的一般形式与收敛条件

一般的，对于 $\mathit{A}\mathit{x}=\mathit{b}$$\bm A \bm x = \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}}^{-1}$$\bm M\inv$ 得 $\mathit{x}=\mathit{B}\mathit{x}+\mathit{f}$$\bm x = \bm B \bm x + \bm f$，

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

迭代法的一般形式即为 ${\mathit{x}}^{(k+1)}=\mathit{B}{\mathit{x}}^{(k)}+\mathit{f},k\in {\mathbb{N}}^{+}$$\bm x^{(k+1)} = \bm B \bm x^{(k)} + \bm f, k \in \N^+$.

当且仅当 $\rho (\mathit{B})<1$$\rho(\bm B) < 1$ 时，上述迭代法收敛.

6.1.2 迭代法收敛的充分条件与速度

1. 充分条件：存在某种算子范数使得 $\Vert \mathit{B}\Vert =q<1$$\Norm{\bm B} = q < 1$，则迭代法收敛.

2. 误差估计：

   1. $\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)}}$.

   2. $\Vert {\mathit{x}}^{\ast }-{\mathit{x}}^{(k)}\Vert \le {\displaystyle \frac{q}{1-q}}\Vert {\mathit{x}}^{(k)}-{\mathit{x}}^{(k-1)}\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}{1 - q} \Norm{\bm x^{(k)} - \bm x^{(k-1)}} \le \dfrac{q^k}{1 - q} \Norm{\bm x^{(1)} - \bm x^{(0)}}$.

3. 收敛速度：

   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)$.

   3. 若要求 $\mathrm{\forall }{\mathit{\epsilon }}^{(0)}:{\displaystyle \frac{\Vert {\mathit{\epsilon }}^{(k)}\Vert }{\Vert {\mathit{\epsilon }}^{(0)}\Vert }}\le \sigma ={10}^{-s}$$\forall \bm \ve^{(0)} \colon \dfrac{\Norm{\bm \ve^{(k)}}}{\Norm{\bm \ve^{(0)}}} \le \sigma = 10^{-s}$，

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

6.1.3 由分裂矩阵构造迭代法

一般的，见 6.1.1 迭代法的一般形式与收敛条件.

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}=(\mathit{L}+\mathit{U})\mathit{x}+\mathit{b}$$\bm D \bm x = (\bm L + \bm U) \bm x + \bm b$.

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

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{G}:=(\mathit{D}-\mathit{L}{)}^{-1}\mathit{U}$$\bm G := (\bm D - \bm L)\inv \bm U$.

6.1.4 J 迭代法和 GS 迭代法

1. 雅可比迭代法

   1. $\mathit{D}\mathit{x}=(\mathit{L}+\mathit{U})\mathit{x}+\mathit{b}$$\bm D \bm x = (\bm L + \bm U) \bm x + \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$.

2. 高斯-塞德尔迭代法

   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. 基本区别

   1. 分裂矩阵 $\mathit{M}$$\bm M$ 从 $\mathit{D}$$\bm D$ 改成了 $\mathit{D}-\mathit{L}$$\bm D - \bm L$.

   2. 体现在计算公式上，便是 $\mathit{L}{\mathit{x}}^{(k)}$$\bm L \bm x^{(k)}$ 改为了 $\mathit{L}{\mathit{x}}^{(k+1)}$$\bm L \bm x^{(k+1)}$，使用了变量的最新信息.

6.1.5 严格对角占优与不可约

• 对角占优矩阵

  • 严格对角占优矩阵：$\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$.

6.1.6 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$ 时，称为低松弛迭代法.

• 对称正定三对角矩阵有最优松弛参数 ${\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} }$.

6.1.7 三种迭代法方法的收敛速度比较

从慢到快：雅可比迭代、高斯-塞德尔迭代、具有最优松弛参数的 SOR 迭代.

6.1.8

6.1.9

6.1.10 一些命题

1. ×

   1. J 迭代法的收敛条件更严格.

   2. GS 迭代法的收敛条件宽松，并且速度更快.

2. √，令 $\omega =1$$\omega = 1$ 即得.

3. ×，还要求 $\omega \in (0,2)$$\omega \in (0, 2)$.

4. √，严格对角占优或不可约对角占优的 J 迭代法与 GS 迭代法均收敛.

5. ×

   1. J 迭代法收敛的充分条件：$\mathit{A}$$\bm A$ 和 $2\mathit{D}-\mathit{A}$$2 \bm D - \bm A$ 对称正定.

   2. GS 迭代法收敛的充分条件：$\mathit{A}$$\bm A$ 对称正定.

6. √，这是必要条件.

7.  

8.  

9.  

10.  

6.2 习题

6.2.1 迭代法的收敛性分析与求解

1. 该矩阵不对称，但是严格对角占优，因此 J 迭代法与 G-S 迭代法均收敛.

2.  

6.2.2 J 迭代法与 GS 迭代法的收敛性

1. 方程组一

   1. 法一：该矩阵对称并且正定，因此 G-S 迭代法收敛；$2\mathit{D}-\mathit{A}$$2 \bm D - \bm A$ 不正定，故 J 迭代法不收敛.

   2. 法二：

      1. 雅可比迭代法

         $$\begin{array}{c}{\mathit{B}}_{\mathrm{J}}={\mathit{D}}^{-1}(\mathit{L}+\mathit{U})=\left(\begin{array}{ccc}0& -0.4& -0.4\\ -0.4& 0& -0.8\\ -0.4& -0.8& 0\end{array}\right),\\ |\lambda \mathit{I}-{\mathit{B}}_{\mathrm{J}}|=(\lambda -0.8)({\lambda }^2+0.8\lambda -0.32).\end{array}$$

         于是 $\rho ({\mathit{B}}_1)=|-0.4-\sqrt{0.48}|\approx 1.09282>1$$\rho(\bm B_1) = \vqty{-0.4 - \sqrt{0.48}} \approx1.09282 > 1$，从而不收敛.

      2. 高斯-塞德尔迭代法

         $$\begin{array}{c}{\mathit{B}}_{\mathrm{S}}=(\mathit{D}-\mathit{L}{)}^{-1}\mathit{U}=\left(\begin{array}{ccc}0& -0.4& -0.4\\ 0& 0.16& -0.64\\ 0& 0.032& 0.672\end{array}\right),\end{array}$$

         思路一：$\rho ({\mathit{B}}_{\mathrm{S}})\le \Vert {\mathit{B}}_{\mathrm{S}}{\Vert }_{\mathrm{\infty }}=0.6<1$$\rho(\bm B_\rm S) \le \Norm{\bm B_\rm S}_\infty = 0.6 < 1$，故收敛.

         思路二：$|\lambda \mathit{I}-{\mathit{B}}_{\mathrm{S}}|=\lambda ({\lambda }^2-0.832\lambda +0.128)$$\vqty{\lambda \bm I - \bm B_\rm S} = \lambda \pqty{ \lambda^2 - 0.832 \lambda + 0.128 }$，于是 $\rho ({\mathit{B}}_{\mathrm{S}})=0.628264$$\rho(\bm B_\rm S) = 0.628264$，从而收敛.

2. 方程组二

   该矩阵不对称，也不严格对角占优或不可约弱对角占优，直接考察其迭代矩阵.

   1. 雅可比迭代法

      $$\begin{array}{c}{\mathit{B}}_{\mathrm{J}}={\mathit{D}}^{-1}(\mathit{L}+\mathit{U})=\left(\begin{array}{ccc}0& -2& 2\\ -1& 0& -1\\ -2& -2& 0\end{array}\right),\\ |\lambda \mathit{I}-{\mathit{B}}_{\mathrm{J}}|={\lambda }^3,\end{array}$$

      $\rho ({\mathit{B}}_{\mathrm{J}})=0<1$$\rho(\bm B_\rm J) = 0 < 1$，故收敛.

   2. 高斯-塞德尔迭代法

      $$\begin{array}{c}{\mathit{B}}_{\mathrm{S}}=(\mathit{D}-\mathit{L}{)}^{-1}\mathit{U}=\left(\begin{array}{ccc}0& -2& 2\\ 0& 2& -3\\ 0& 0& 2\end{array}\right),\\ |\lambda \mathit{I}-{\mathit{B}}_{\mathrm{S}}|=\lambda (\lambda -2{)}^2,\end{array}$$

      $\rho ({\mathit{B}}_{\mathrm{S}})=2>1$$\rho(\bm B_\rm S) = 2 > 1$，故发散.

6.2.3 J 迭代法与 GS 迭代法的收敛速度

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

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

6.2.4 J 迭代法与 GS 迭代法收敛的充要条件

因此 J 迭代法收敛 $\iff \left|ab\right|<{\displaystyle \frac{100}{3}}$$\RLA \vqty{ab} < \dfrac{100}{3}$.

因此 GS 迭代法收敛 $\iff \left|ab\right|<{\displaystyle \frac{100}{3}}$$\RLA \vqty{ab} < \dfrac{100}{3}$.

6.2.5 其他迭代法的收敛条件与速度

$\mathit{A}$$\bm A$ 的特征值为 $2.5\pm \sqrt{{2.5}^2-4}$$2.5 \pm \sqrt{2.5^2 - 4}$ 即 1 和 4，

故由哈密顿-凯莱定理，$\mathit{B}$$\bm B$ 的特征值为 $1+\alpha ,1+4\alpha$$1 + \alpha, 1 + 4 \alpha$，

解 $\rho (\mathit{B})<1$$\rho(\bm B) < 1$，得 $-{\displaystyle \frac{1}{2}}<\alpha <0$$-\dfrac{1}{2} < \alpha < 0$ 时收敛.

由收敛速度定义式 $R(\mathit{B})=-\ln \rho (\mathit{B})$$R(\bm B) = -\ln\rho(\bm B)$，当 $\alpha =-{\displaystyle \frac{2}{5}}$$\alpha = -\dfrac{2}{5}$ 时收敛最快.

6.2.6 J 迭代法与 GS 迭代法的收敛速度

$\mathit{A}$$\bm A$ 对称正定，$2\mathit{D}-\mathit{A}$$2 \bm D - \bm A$ 也正定，因此 J 迭代法与 GS 迭代法均收敛.

因此两种迭代法均收敛，并且收敛速度之比为 $1:2$$1 : 2$，即 GS 迭代法收敛更快.

6.2.7

6.2.8

6.2.9 一种迭代法的收敛性

迭代矩阵 $\mathit{B}=\mathit{I}-\omega \mathit{A}$$\bm B = \bm I - \omega \bm A$ 的特征值为 $1-\omega \lambda (\mathit{A})\in (-1,1)$$1 - \omega \lambda(\bm A) \in (-1, 1)$，从而 $\rho (\mathit{B})<1$$\rho(\bm B) < 1$，于是收敛.

6.2.10

6.2.11