线性方程组

#线性方程组| 来源: 网络整理| 查看: 265

0 迭代法与直接法的对比

继续讨论线性方程组 $Ax=b$ 的求解方法。

之前所讨论的Gauss消去/LU分解之类的方法是直接对矩阵求解，我们称其为直接法。LU分解后的求解复杂度为 $\bbox[lightgray,2pt]{O(n^2)}$ ，对于 $b$ 变化且 $A$ 稠密的小规模问题有较好的表现。

现在我们面对的是大规模的 $A$ ，可能有几十万几百万阶。而分解矩阵的复杂度为 $O(n^3)$ ，对这种规模的矩阵已经难以适用了。实际应用中， $A$ 经常是大规模且稀疏的，我们引入迭代法，能够将求解的复杂度直接降低到 $\bbox[lightgray,2pt]{O(n)}$ 。例如 $A$ 每行只有5个非零元，迭代法求解过程中每步迭代需要 $5n$ 次乘法，若 $n$ 很大且收敛较快，总体复杂度只有 $O(n)$ 。

直接法和迭代法有何本质区别？

假设我们已知 $Ax=b$ 的精确解是 $x^*$ 。直接法顾名思义，就是直接找到 $x^*$ 本身。而迭代法是通过多步迭代，找到 $x*$ 的一个近似： $x$ ，使得误差在允许范围内（如 $10^{-6}$ ）： $\left\|x-x^{*}\right\|\tau=10^{-6}\\$ 迭代法会把原方程改造为等价的某种迭代形式，然后逐步迭代求解，得到解序列： $\boldsymbol{x}^{(0)}, x^{(1)}, \ldots, x^{(k)}, \ldots\\$ 原理上只要解序列收敛，则一定能在有限步内找到满足误差精度的近似解。如何利用范数判断向量序列收敛的方法已经在线性方程组-迭代法 0.1：范数与谱半径中讲过。

1 迭代法一般求解过程1.1 迭代形式

假设 $Ax=b$ 为： $\begin{cases}2 x_1+4 x_2-2 x_3 & =2 \\ 4 x_1+9 x_2-3 x_3 & =8 \\ -2 x_1-3 x_2+7 x_3 & =10\end{cases}\\$ 我们将其改写为 $\left\{\begin{array} { l } { 2 x_1 = 2 - ( 4 x_2 - 2 x_3 ) } \\ { 9 x_2 = 8 - ( 4 x_1 - 3 x_3 ) } \\ { 7 x_3 = 1 0 - ( - 2 x_1 - 3 x_2 ) } \end{array} \rightarrow \left\{\begin{array}{l} x_1=[2-(4 x_2-2 x_3)] / 2 \\ x_2=[8-(4 x_1-3 x_3)] / 9 \\ x_3=[10-(-2 x_1-3 x_2)] / 7 \end{array}\right.\right. \\$

这样原式 $Ax=b$ 就变成了： $x=B x+f \tag1$ 显然这种改写是和原式完全等价的。（1）式等号两边都有未知量 $x$ ，我们就可以由右边的 $x$ 计算出左边新的 $x$ ，即一步迭代。我们把（1）称为原线性方程组的迭代形式。迭代形式是必然存在的，例如 $x=x-c *(b-A x)$ ， $c$ 为任意常数。

1.2 求解过程

利用迭代形式进行迭代法求解的过程为：

把原式 $Ax=b$ 改写为迭代形式 $x=B x+f$ ；给定任意初始值 $x^{(0)}$ ，代入迭代形式；迭代求解： $x^{(k+1)}=B x^{(k)}+f \tag2$ 得到解序列 $\boldsymbol{x}^{(0)}, x^{(1)}, \ldots, x^{(k)}, \ldots \\$ 直到解序列收敛于某个值。

注意，迭代法得到的解序列不一定是收敛的，也可能发散，此时迭代法失效。

2 迭代格式的收敛条件2.1 收敛条件分析

如果迭代法产生的解序列满足： $\lim _{k \rightarrow \infty} \boldsymbol{x}^{(k)}=\boldsymbol{x}^{*} \tag3$ 则称该迭代法收敛，若不满足则发散。例如最开始的例子就不收敛。

那么如何判断 $x^{(k+1)}=B x^{(k)}+f$ 是否收敛呢？首先对解的误差进行分析。假设精确解为 $x^*$ ，定义第 $k$ 步迭代的误差向量为： $\boldsymbol{\varepsilon}^{(k)}=\boldsymbol{x}^{(k)}-\boldsymbol{x}^{*}\\$ 则收敛表达式（3）等价于： $\lim _{k \rightarrow \infty} \varepsilon^{(k)}=\overrightarrow{0} \\$ 显然精确解满足迭代形式： $\boldsymbol{x}^{*}=B \boldsymbol{x}^{*}+f \tag4$

（4）与迭代格式 $x^{(k+1)}=B x^{(k)}+f$ 合并得： $\varepsilon^{(k+1)}=B \varepsilon^{(k)}=\ldots=B^{k+1} \varepsilon^{(0)} \\$ 即： $\varepsilon^{(k+1)}=\bbox[pink,2pt]{B^{k+1}} \varepsilon^{(0)} \tag5$ 其中 $\varepsilon^{(0)}$ 为初始误差， $\varepsilon^{(k+1)}$ 为第 $k+1$ 步迭代的误差。

由（5）式可以看出，误差只和矩阵 $B$ 有关系。这意味着迭代形式中的 $B$ 完全决定了该迭代法的收敛与否。下面就研究 $B$ 矩阵与迭代法收敛性的关系，并引出收敛定理。

2.2 收敛定理

根据（5），可以得出迭代法的收敛定义为： $\lim _{k \rightarrow \infty} \varepsilon^{(k+1)}=\lim _{k \rightarrow \infty} B^{k+1} \varepsilon^{(0)}=\overrightarrow{0} \tag6$ 根据向量范数的性质“任一种范数收敛等价于该向量序列收敛”可得： $\lim _{k \rightarrow \infty}\left\|\varepsilon^{(k+1)}\right\|=\lim _{k \rightarrow \infty}\bbox[lightgray,2pt]{\left\|B^{k+1} \varepsilon^{(0)}\right\|}=0 \tag7$ 对（7）应用范数的不等式： $\bbox[lightgray,2pt]{\left\|B^{k+1} \varepsilon^{(0)}\right\|} \leq\left\|B^{k+1}\right\| \left\|\varepsilon^{(0)}\right\| \leq \bbox[pink,2pt]{\|B\|^{k+1}} \left\|\varepsilon^{(0)}\right\| \tag8$ 由（8）可知，如果存在一种矩阵范数 $\|B\|1$ ，则一定收敛。

由线性方程组-迭代法 0.1：范数与谱半径中引入的谱半径与范数的关系可知，从数值计算角度，谱半径就是最小的矩阵范数。因此迭代法是否收敛就取决于 $B$ 的谱半径 $\rho(B)$ 是否小于1。

收敛定理

对于迭代形式 $x=B x+f$ 中的矩阵 $B$ ，如下四个命题等价：

迭代形式 $x^{(k+1)}=B x^{(k)}+f,(k=0, 1,2,...) \\$ 对任意初值 $x^{(0)}$ 收敛； $\rho(B)1$ ；存在某种范数 $\|\cdot\|_{\diamond}$ 满足 $\|B\|_{\diamond}1$ ；对任意矩阵范数： $\lim _{k \rightarrow \infty}\left\|B^{k}\right\|_p=0\\$ 即 $B^{k}$ 收敛到零矩阵： $\lim _{k \rightarrow \infty}\left(B^{k}\right)_{i j}=0, \quad 1 \leq i, j \leq n$ 。其中第4条可由第3条结合矩阵范数的性质“任意两种范数是等价的”推出。首先放缩： $\|B^{k}\|_{\diamond}\leq\|B\|_{\diamond}^{k}$ ， $\lim _{k \rightarrow \infty}\left\|B\right\|^{k}_{\diamond}=0 \Rightarrow \lim _{k \rightarrow \infty}\left\|B^{k}\right\|_{\diamond}=0\\$ 由范数等价性：存在某正数 $c$ 满足 $\frac{1}{c}\|B^k\|_{\diamond} \leq \|B^k\|_p \leq c\|B^k\|_{\diamond} \\$ 根据夹逼准则，当 $k\rightarrow \infty$ ， $\lim _{k \rightarrow \infty}\left\|B^{k}\right\|_p=0$ ，证毕。2.3 误差估计

下面推导随着迭代步数 $k$ 的增长，误差 $\varepsilon$ 是如何变化的。

假设已经找到了某种范数满足 $\|B\|_{\diamond} =q1$ ，根据迭代格式（5）：

$\varepsilon^{(k+1)}=B \varepsilon^{(k)} \tag9$

对（8）取范数并放缩： $\begin{gathered} \left\|\varepsilon^{(k+1)}\right\|=\left\|B * \varepsilon^{(k)}\right\| \leq\|B\| *\left\|\varepsilon^{(k)}\right\| \rightarrow \\ \bbox[pink,2pt]{\left\|\varepsilon^{(k+1)}\right\|} \leq\|B\|^{k+1} *\left\|\varepsilon^{(0)}\right\|=\bbox[pink,2pt]{q^{k+1}\left\|\varepsilon^{(0)}\right\|} \\ \left\|\varepsilon^{(k+1)}-\varepsilon^{(k)}\right\|=\left\|B \varepsilon^{(k)}-\varepsilon^{(k)}\right\| \geq\left\|\varepsilon^{(k)}\right\|-q *\left\|\varepsilon^{(k)}\right\| \end{gathered} \\$ 代入 $\boldsymbol{\varepsilon}^{(k)}=\boldsymbol{x}^{(k)}-\boldsymbol{x}^{*}$ 得： $\bbox[cyan,2pt]{\left\|\boldsymbol{x}^{(k+1)}-\boldsymbol{x}^{(k)}\right\|}=\left\|\boldsymbol{\varepsilon}^{(k+1)}-\boldsymbol{\varepsilon}^{(k)}\right\| \geq \bbox[cyan,2pt]{(1-q) \left\|\varepsilon^{(k)}\right\| }\\$ 红色部分表明我们可以利用 $q$ 和初始误差估计当前步的误差；

蓝色部分表明我们可以通过前后两步结果的差值来估计当前误差，来确定是否收敛。这种方式更常用，可在迭代每一步进行收敛判定。

把两种估计方式稍加整理，就推出了误差估计的两种范式：

先验估计： $\left\|x^{*}-x^{(k)}\right\| \leq q^{k}\left\|x^{*}-x^{(0)}\right\| \\$ 意味着 $q$ 越小，收敛越快。当然真正计算 $q$ 代价是很大的，并且我们也并不知道真正的解 $x^*$ ，这种估计方法只是理论上成立。后验估计： $\left\|x^{*}-x^{(k)}\right\| \leq \frac{q}{1-q}\left\|x^{(k)}-x^{(k-1)}\right\| \leq \frac{q^{k}}{1-q}\left\|x^{(1)}-x^{(0)}\right\| \\$ 意味着第 $k$ 步的误差可以通过第 $k$ 步和第 $k-1$ 步结果的差值来估计，在计算中是更有意义的。

实际中计算 $q$ （计算 $B$ 的谱半径）是不现实的，因此最常用的收敛判断方法是残差法：

残差法：定义第 $k$ 步的残差 $r_{k}=b-A x^{(k)}$ ，即： $\bbox[lightgray,2pt]{r_{k}}=b-A x^{(k)}=A x^{*}-A x^{(k)}=A *\left(x^{*}-x^{(k)}\right)=\bbox[lightgray,2pt]{A} * \bbox[lightgray,2pt]{\varepsilon^{(k)}}\\$ 残差的计算十分简单的。这给出了一个实用的估计方法：可以认为残差是真实误差的倍数（数值上可认为是 $A$ 的谱半径倍），当残差较小时，就可以认为误差较小。

【本文地址】

线性方程组

线性方程组

今日新闻

推荐新闻