数值方法/线性方程组的解

定义和基础

线性方程组是指一组需要同时求解的线性方程。线性方程的形式为

a_{1}*x_{1}+a_{2}*x_{2}+\ldots +a_{n}*x_{n}=b\quad ,\,

其中 $n+1\,$ 个系数 $a_{0}\ldots a_{n}\,$ 和 $b\,$ 是常数，而 $x_{1}\ldots x_{n}\,$ 是n个未知数。根据上面的符号，线性方程组可以表示为

{\begin{matrix}a_{11}*x_{1}+a_{12}*x_{2}+\ldots +a_{1n}*x_{n}&=&b_{1}&\\a_{21}*x_{1}+a_{22}*x_{2}+\ldots +a_{2n}*x_{n}&=&b_{2}&\\&\vdots &&\\a_{m1}*x_{1}+a_{m2}*x_{2}+\ldots +a_{mn}*x_{n}&=&b_{m}&\quad .\end{matrix}}\,

该系统包含 $m\,$ 个线性方程，每个方程有 $n+1\,$ 个系数，并有 $n\,$ 个未知数，这些未知数必须同时满足这组方程。为了简化符号，可以使用矩阵符号重写上述方程

\mathbf {A} \cdot \mathbf {x} =\mathbf {b} \quad .\,

矩阵 $\mathbf {A} \,$ 的元素是方程的系数， $a_{ij}\,$ ，向量 $\mathbf {x} \,$ 和 $\mathbf {b} \,$ 的元素分别为 $x_{i}\,$ 和 $b_{i}\,$ 。在这个记号中，每行都构成一个线性方程。

超定和欠定系统

为了使解 $\mathbf {x} \,$ 是唯一的，必须至少有与未知数一样多的方程。用矩阵表示法来说，这意味着 $m\geq n\,$ 。但是，如果一个系统包含的方程比未知数多 ( $m>n$ )，则很有可能（不说是规律）根本不存在解。这样的系统被称为 **超定系统**，因为它们包含的方程比未知数多。它们需要特殊的数学方法来近似求解。最常用的方法是 **最小二乘法**，它旨在将试图求解系统时每个未知数产生的误差平方和最小化。这种问题通常出现在测量或数据拟合过程中。

示例
假设一个任意三角形：假设一个人用 $\pm 0.2^{\circ }\,$ 的精度测量了所有三个内角 $\alpha ,\beta ,\gamma$ 。此外，假设边 a、b 和 c 的长度是精确已知的。从三角学可知，使用余弦定理，如果已知所有其他边和角，则可以计算角或边的长度。但众所周知，平面三角形的内角之和始终为 $180^{\circ }\,$ 。因此，我们有三个余弦定理和角之和规则。这总共构成了四个方程和三个未知数，形成了一个超定问题。

另一方面，如果 $m<n\,$ ，则会出现问题，即解不是唯一的，因为可以自由选择一个未知数。同样，也存在数学方法来处理这类问题。但是，这些方法在本课文中将不予介绍。

本章主要集中讨论 $m=n\,$ 的情况，除非另有说明，否则默认此条件成立。

线性系统的精确解

用线性代数求解方程组 $\mathbf {Ax} =\mathbf {b} \,$ 很容易：只需从左侧乘以 $\mathbf {A} ^{-1}$ ，得到 $\mathbf {x} =\mathbf {A} ^{-1}\mathbf {b}$ 。但是，求解 $\mathbf {A} ^{-1}$ （除了平凡的情况）非常困难。以下部分将介绍几种求解该问题精确解（直到舍入误差）的方法。

对角和三角形系统

对角矩阵只有主对角线上有元素

a_{ij}\equiv 0\;\forall \;i\neq j

在这种情况下， $\mathbf {A}$ 的逆矩阵就是一个对角矩阵，其元素为逆元素，即

\mathbf {A} ^{-1}={\mbox{diag}}(1/a_{ii})\quad .

因此，对角系统的解为 $x_{i}=b_{i}/a_{ii}$ ，这很容易计算。

上三角系统定义为

a_{ij}=0\quad \forall j<i\quad ,

而下三角系统定义为

a_{ij}=0\quad \forall j>i\quad .

回代法是求解上三角系统的过程

x_{i}={\begin{cases}b_{i}/a_{ii}\quad &{\mbox{if}}\;i=N\\{\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=i+1}^{N}{a_{ij}x_{j}}\right)\quad &{\mbox{else}}\quad .\end{cases}}

另一方面，前代法是对下三角系统执行相同过程。

x_{i}={\begin{cases}b_{i}/a_{ii}\quad &{\mbox{if}}\;i=1\\{\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j=1}^{i-1}{a_{ij}x_{j}}\right)\quad &{\mbox{else}}\quad .\end{cases}}

高斯-约旦消元法

该方法不求解 $\mathbf {A} ^{-1}$ ，而是依赖于行操作。根据线性代数的定律，方程组的行可以乘以一个常数而不改变解。此外，行之间可以相加和相减。这引出了改变方程组结构的想法，使得 $\mathbf {A}$ 具有便于求解 $\mathbf {x}$ 的结构。其中一个结构是如上所述的对角矩阵。

高斯-约旦消元法将矩阵 $\mathbf {A}$ 转换为对角形式。为了简化过程，人们通常使用一种改进的方案。首先，将矩阵 $\mathbf {A}$ 和右端向量 $\mathbf {b}$ 组合成增广矩阵

\left[\mathbf {A} ,\mathbf {b} \right]={\begin{bmatrix}a_{11}&a_{12}&\cdots a_{1N}&b_{1}\\\vdots &\ddots &\vdots &\vdots \\a_{N1}&a_{N2}&\cdots a_{NN}&b_{N}\end{bmatrix}}

为了说明，考虑一个易于理解但有效的算法，它可以由四个基本部分构成

gelim：主函数遍历一个简化方程组的堆栈，通过一系列部分解，一次构建一个变量的完整解。

stack：重复调用reduce，生成一个堆栈，包含简化方程组，从小到大排序（例如，包含 2 个元素，如 <ax = b>）。

solve：在给定简化方程组和部分解的情况下，求解一个变量。例如，给定简化方程组 <aw bx cy = d> 和部分解 <x y>，则 w = (d - bx - cy)/a。现在，部分解 <w x y> 可用于下一轮，例如 <au bv cw dx , e>。

reduce：从顶部获取第一个方程并将其压入堆栈；然后生成一个残差 - 简化矩阵，通过从剩余较下方程的对应元素中减去第一个原始方程的元素，例如 b[j][k]/b[j][0] - a[k]/a[0]。正如您所见，这通过将一个元素从一个元素中减去来消除每个较下方程的第一个元素，并且只需要保留剩余的元素 - 最终，残差是一个输出矩阵，其行和列比输入矩阵少一行和一列。然后将其用作下一次迭代的输入。

需要注意的是，乘法也可以用作除法的替代；但是，对于较大的矩阵（例如 n=10），这会产生级联效应，导致产生 NAN（无穷大）。从统计学上看，除法具有将简化矩阵归一化的效果 - 生成均值更接近零且标准差更小的数字；对于随机生成的数据，这会生成具有接近 +-1 的条目的简化矩阵。

继续的内容仍待撰写

正如它所示，将方程组转换为完全对角形式并非必要。将其转换为三角形形式（上三角或下三角）就足够了，因为然后可以通过反向或正向替换分别求解它。

LU分解

本节内容待撰写

线性方程组的近似解

本节内容待撰写

雅可比迭代法

这是一个迭代方案。

高斯-赛德尔迭代法

本节内容待撰写

10v+w+x-2y+z=-1
v-20w-2x+y+z=20
v+w+10x-y-z=-1
-v-2w+x+50y+z=2
v+w+x+y+100z=-1 
;find result:

超松弛迭代法 (SOR)

SOR 是连续超松弛法的缩写。它是一种迭代方案，使用松弛参数 $\omega$ ，并且是 $\omega =1$ 特殊情况下的高斯-赛德尔方法的推广。

给定一个具有未知数 x 的 n 个线性方程的方阵系统

A\mathbf {x} =\mathbf {b}

其中

A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}},\qquad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\qquad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{bmatrix}}.

那么 A 可以分解为一个对角分量 D，以及严格的下三角和上三角分量 L 和 U

A=D+L+U,

其中

D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}},\quad L={\begin{bmatrix}0&0&\cdots &0\\a_{21}&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}},\quad U={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\0&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &0\end{bmatrix}}.

线性方程组可以改写为

(D+\omega L)\mathbf {x} =\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x}

其中ω > 1为常数。

逐次超松弛法是一种迭代技术，它使用表达式右侧的x先前值求解左侧的x。用分析方法表示，可以写成

\mathbf {x} ^{(k+1)}=(D+\omega L)^{-1}{\big (}\omega \mathbf {b} -[\omega U+(\omega -1)D]\mathbf {x} ^{(k)}{\big )}.

但是，利用(D+ωL)的三角形式，可以使用前向替换按顺序计算x^(k+1)的元素

x_{i}^{(k+1)}=(1-\omega )x_{i}^{(k)}+{\frac {\omega }{a_{ii}}}\left(b_{i}-\sum _{j>i}a_{ij}x_{j}^{(k)}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}\right),\quad i=1,2,\ldots ,n.

松弛因子的选择并不容易，它取决于系数矩阵的性质。对于对称、正定矩阵，可以证明0 < ω < 2将导致收敛，但我们通常更关注更快地收敛而不是仅仅收敛。

共轭梯度法

本节内容待撰写

多重网格法

本节内容待撰写

主页 - 数学书架 - 数值方法