恰定方程组的解 | 彩潭有鲤的札记

type

status

date

slug

summary

Cramer法则

将上述列向量替换中的第个列向量，把产生的新矩阵记作，那么解向量的第项：

它要求系数矩阵是满秩的

对于满秩的系数矩阵，可以有如下推导：

由伴随矩阵的定义：

由矩阵运算法则，解向量的第个分量可以描述为：

是的代数余子式

故由行列式的Laplace展开运算，不难得到：

复杂度

一个阶行列式具有个Laplace展开项，每一个展开项由项相乘，故计算单个阶行列式需要次乘法运算。而对于阶系数矩阵，Cramer法则要求计算个矩阵，故最终的计算复杂度为，过大，不可接受.

Gauss消元法

Gauss消元法的核心任务是，对于增广矩阵，执行次消元，第次消元通过基本矩阵变换将下方的所有元素归零

简单Gauss消元法

数学语言描述：

对于的第至行向量，重复执行下述步骤：

，令

经过这样的消元，系数矩阵化为了上三角矩阵，可以立即解出，从而逐个回代求解出解向量

复杂度分析

根据上述算法，对于第次执行来讲，赋值表达式首先执行了1次，而行向量中共有个非零元素，故每次执行赋值表达式均要求次乘法运算。对于每一个行向量，均执行次，故Gauss消元法的复杂度可以表述为：

失效情况

实际计算中应尽量避免小数除大数，而上述的算法实际上无法避免这种情况，可能在某些矩阵的解决过程中会有某一极小的数作主元的情况发生。为了避免这样的问题，提出了如下的改进算法：

(列)主元素法

(列)主元素法在算法执行过程中，每面对一个新的i值，它都会遍历矩阵的第i列，将拥有绝对值最大的第列元素的行向量替换至第行。这样的算法附加一个开销，但可以很大程度上保证算法的数值稳定。

全主元素法

继续改进，在在算法执行过程中，每面对一个新的值，它都会遍历整个矩阵，将拥有绝对值最大的元素的行向量替换至第行，列向量替换至第列，同时记录这个列变换，便于修正解向量的顺序。这样的算法附加一个开销，但可以极大程度上保证算法的数值稳定，是求解中小型稠密恰定方程组的最优方法之一.

在不少应用场景中，系数矩阵是保持不变的，而方程右值来源于输入值，是时刻变化的。因此在这样的情境下，使用简单Gauss消元法及其衍生方法就会产生复用性低的问题：面对每一个新的，都需要重新执行一遍完全一样的Gauss消元步骤，这是愚蠢的。故需要找到某一种方式来记录Gauss消元法的步骤，可以将步骤记录在某种数据结构中，但这种方式太过于随意，也太过于工程化，故难以与理论的误差分析等兼容，故提出了结构化描述Gauss消元步骤的方式，这种方式将实践的具体情况祓除，将上述的"记录"抽象为理论.

分解法

用基本初等矩阵刻画线性变换

任何一个基本矩阵变换均可以被一个基本初等矩阵刻画，假使有基本初等矩阵，矩阵，那么代表对执行一系列初等行变换，而代表对执行一系列初等列变换

在上述的情况下，对执行的变换操作相当于将单位矩阵变换为所需的行或列操作

例：设矩阵，

可以视为“将的第二行的1倍加到第三行上”，故

同理，可以视为“将的第三列的1倍加到第二列上”，故

Doolittle分解

为了方便，将彻底不考虑增广矩阵，只考虑系数矩阵.

因此，可以通过一个基本初等矩阵，将上述对系数矩阵执行的一系列消元法结构化地描述。根据消元算法，面对行向量，执行的操作可以刻画为：

其中：

其中，

因此，消元算法的一系列操作可以记作：

用新的符号重写上式以避免在下述推导中出现歧义：

左乘移项:

而上述的各个Li有着很好的运算性质(实际上，与线性变换的性质息息相关)：

在时，

且在时，有

故可以根据上述的运算性质，将所有项合并为一个项：

其中：

是一个单位下三角矩阵。而Gauss消元的结果是一个上三角矩阵，故可以藉由Gauss消元的原理，将矩阵分解为一个单位下三角矩阵和一个一般上三角矩阵的积，这种分解被称为Doolittle分解

有效条件

Doolittle分解是使用基本初等矩阵来记录Gauss消元的步骤，因此Gauss消元与Doolittle分解理应是等价的. 因此，适用Gauss消元的矩阵也理应适用Doolittle分解

，若的1至阶顺序主子式均非零，则矩阵存在唯一的Doolittle分解

在执行消元时，需要一个非零的主元来执行消元操作。而易证明，经过先前的消元操作之后，主元非零当且仅当主子式矩阵是满秩的

条件( 至阶顺序主子式均非零)弱于方程可解条件(系数矩阵满秩)。这一差距的来源在于，在执行消元的过程中，不需要对最后一列元素执行消元操作，因此，最后一个主元是否非零并不重要。这表明，可以执行Doolittle分解是矩阵可解的必要非充分条件。这也表示着，Doolittle分解已将消元法从解方程的实际情景中彻底地抽象了出来。

LC的计算方法

考察Doolittle分解的定义式:

是一个单位下三角矩阵，是一个上三角矩阵。故将上式表示如下：

由矩阵的乘法法则：

根据和矩阵中1和0的分布，将计算简化

由此可以反解出

在解方程中应用Doolittle分解

假设通过上述计算方法求出了系数矩阵的Doolittle分解：

将其回代到方程组中：

将向量表示为，有

相当于解两个已经过消元的恰定(如果系数矩阵是满秩的)方程组

开销分析

由于基本原理相同，Doolittle分解法与Gauss消元法具有相同的运算量，但Doolittle分解法有着复用性的优势

Cholesky分解

在实践中，有相当一部分线性求解问题应用到了正定二次型的系数矩阵，而正定二次型具有更优的性质，可能可以简化求解运算。因此有必要针对正定二次型来提出一种新的算法

正定二次型

若一个矩阵满足A = AT，则将其称为对称矩阵，而术语“二次型”常被用于提及一个对称矩阵.

当一个二次型满足以下四个等价条件之一：

的所有顺序主子式均大于

则被称为正定二次型，上述四个条件均为命题“是正定二次型”的充分必要条件

平方根法

由上述性质4：，一个正定二次型可以被分解为一个实矩阵和其转置的积

若属正定二次型，则存在唯一的可逆下三角矩阵，使得

其中，的对角元素均为正实数

证明：

存在，其中是下三角单位矩阵，为上三角矩阵. 将的对角线元素抄到矩阵中，即记矩阵，再记矩阵，则。注意：此时的之对角元素全部为1. 又属二次型，属对角矩阵，故：

而，同一个矩阵的Doolittle分解是唯一的，因此不难得到，即

接下来，将对角矩阵拆分为形如的形式。但这要求着也为对角矩阵，且的对角线元素值为相应对角线元素值的平方，这就要求的对角线元素均为正。因此证明：

由正定性质：任取一非零列向量，有

这种形式表示：也是一个正定二次型，而是一个对角阵，对角阵的对角元素就是它的特征值，因此的对角线元素为正.

故，即

易知是上三角矩阵，故是一个下三角矩阵

计算方法

Cholesky分解的计算原理与Doolittle分解一致，均是应用矩阵乘法法则

完成Cholesky分解后的解方程步骤与Doolittle分解一致.

容易得知，Cholesky分解应用了对称性，故计算复杂度为Gauss消元法的一半，为

但是，Cholesky分解法调用了平方运算，可能会导致运算时间的延长.

改进的平方根法

在Cholesky分解的证明过程中，我们提到：

其中，是单位下三角矩阵，为对角矩阵

因此我们可以将矩阵作分解以避免平方根运算

计算方法

改进的平方根法在求矩阵和的过程中采用了与Doolittle分解完全一致的方式：首先将组合为一个新的矩阵处理，再通过与Doolittle分解完全一致的计算方式得到如下的计算式：

这样的运算式尚未把正定二次型的性质充分发挥，故提出了一个使用辅助量 (实际上就是将的积中的元素显式地记录了下来)的计算式

使用改进的平方根法解方程的步骤与上述两方法稍有出入：