5.5.4 线性方程组的求解：迭代法

另一种非常流行的求解线性方程组的方法是迭代法。它的优点是易于编程。在实践中，由于计算机程序库中提供了高效的程序，对于小规模问题通常更倾向于使用消元法。然而，当变量数目变大时，比如说几百个，消元法就会陷入困境，因为矩阵可能包含 $10^6$ 个或更多元素。这种规模的问题常见于那些需要在网格上进行数值求解的科学和工程计算中。典型地，在涡轮流动中，我们会遇到一个三维流体流动问题，需要在一个 $30 \times 30 \times 30$ 网格上求解三个速度分量和压强。该问题需要求解一个 $27\ 000 \times 27\ 000$ 矩阵方程。这类问题的可取之处在于，矩阵中几乎所有元素都为零是非常常见的情况。绝大多数元素为零的矩阵称为稀疏矩阵。除非方程具有特殊结构，否则消元法会很快破坏稀疏性。另一方面，迭代法只需处理非零项，因此可以大大节省计算量。和往常一样，这是有代价的：

• (a) 判断方法何时收敛并不总是容易的；
• (b) 如果该方法需要非常多的迭代次数才能收敛，任何节省都会很快被消耗殆尽。

一个简单的例子将说明该方法的进行方式；在这个例子中将使用精确分数。

为了求解方程组

$$4x + y = 2$$

$$x + 4y = -7$$

我们首先将其改写为

$$x = \frac{1}{4} (2 - y)$$

$$y = \frac{1}{4}(-7 - x)$$

并从 $x = 0, y = 0$ 开始。

将这些值代入右端得到 $x = \frac{1}{2}$ , $y = -\frac{1}{4}$ 。

将这些新值代入右端得到 $x = \frac{15}{16}$ , $y = -\frac{15}{8}$ 。

将这些新值代入等式右边可得 $x = \frac{31}{32}$ , $y = -\frac{127}{64}$ 。

将这些新值代入等式右边可得 $x = \frac{255}{256}, y = -\frac{255}{128}$

将这些新值代入等式右边可得 $x = \frac{511}{512}, y = -\frac{2047}{1024}$

重复执行同样的步骤，通常称为迭代，会得到一组看起来趋于解的数值 $x = 1$ , $y = -2$ .