求解线性方程组 | 彩潭有鲤的札记

考虑线性方程组：

末知数的数量不大于方程的数量，因此，如果不属于矩阵的值域空间，即，则称该方程是矛盾的或过定的，这种情况下方程组无解。求解该方程就变成了寻找一个(组) 向量，使得达到最小。这是非线性最小二乘问题的一个特例。

如果向量能够使达到最小，即对于所有，都有

则称为的最小二乘解。若有解时，其解自然是一个最小二乘解；若无解，则只能寻求其最小二乘解，即能使和之间差值的范数达到最小的向量。

矩阵，当且仅当（即方阵非奇异）时, 。在定义方程组模型时，已经要求，那么逆矩阵存在。

能够最小化的向量具有唯一性，可通过求解方程组得到，即

证明：令，注意

可以证明上式中等号右端的最后一项为零，将代入，可得

因此，

由于，因此当时，有，由此可得

可知是的唯一极小点。

如果向量使得正交于子空间，那么

矩阵在最小二乘解中扮演着重要的角色，通常称其为格拉姆矩阵。

另外一种获取最小二乘解的方法：

构造目标函数

很明显，函数为二次型函数。由于，因此二次项是正定的。利用局部极小点的一阶必要条件，可求得的唯一极小点，即极小点满足

该方程的唯一解为

给出3组实验数据和，利用最小二乘法确定了参数和，由此确定的直线能够对这 3 组实验数据进行最好的拟合。假定又给出了一组测量数据，这样共有 4 组数据、和。显然，可以按照前面步骤，利用这4组数据，重新计算参数和。但是，还存在一种更为高效的方法，利用前面已经得到的参数和来计算加人新数据之后的参数和。实际上，这一过程只是对已经得到的和进行更新，以适应新的数据，称为递推最小二乘算法。

某个优化问题为寻找合适的，使得最小，已知这一问题的解为，其中，。如果增加了新的数据，用矩阵和向量表示，那么整个问题就成为寻找，使得

达到最小。

这一问题的解为：

其中：

目标是将写为、新数据和的表达式。首先，将写为

接下来

将展开为

联合以上方程，可得的表达式为

其中，可利用下式求出：

可以看出，可以只通过、新数据和得到。这意味着增加新数据之后，可以利用已有的计算结果计算，不需要从头重新计算。对增加一个修正项，即可得到。注意，如果新数据与已有的数据是一致的，即，则修正项为与是相等的。

可以给出递推最小二乘算法的迭代公式，利用该公式，当新数据到来之后，可对已有的计算结果进行更新，从而得到新的结果。在第次递推中，计算公式为：

向量通常称为新息。如果新息为零，那么更新得到的就是更新前的解。

由迭代公式可以看出，在从到的更新过程中，需要用到逆矩阵，而不是矩阵。可以给出关于的更新公式，为此需要引人新的引理。该引理是对谢尔曼-莫里森公式的推广。这一工作是由伍德伯里完成的，相应的，公式称为谢尔曼-莫里森-伍德伯里公式。

为非奇异矩阵，矩阵和能够使得非奇异，则有非奇异，且：

可得

为了简化描述，记为，代人递推最小二乘算法的迭代公式中, 可得

考虑一种特殊情况，每次只新来一行新数据，即矩阵只有一行， , 是标量，，此时，有：

例：令

首先确定能够使得最小化的向量，然后利用递推最小二乘算法计算，使得

最小化。计算

重复使用递推最小二乘算法两次，可得

很容易验证，由递推最小二乘算法得到的与直接利用公式得到的结果是一致的，其中

某线性方程组为

其中，。注意方程的数量不超过未知数的数量。因此，该方程组可能存在无数个解。但是，只存在一个最接近原点的解，即的解中范数最小的。令表示这个解，可知，且对于任意满足的，都有。也就是说，是如下优化问题的解：

的解中范数最小的解是唯一的，可由下式给出：

证明：令，注意

由于：故有

因此：

由于对于所有，都有成立，因此，对于所有，都有

即：

显然，是唯一的。

继续考虑方程组。

Kaczmarz算法是一种迭代求解算法，由Kaczmarz于1937年首次提出，能够在不直接计算逆矩阵的情况下收敛到。这一点使得该算法非常实用，尤其是在矩阵的行数非常多的情况下。

令表示矩阵的第行，表示向量的第个元素，为正实数，满足。Kaczmarz算法的步骤为：

可得在前次迭代中，有

在每次迭代中，依次使用了矩阵的各行及其对应的向量中的元素。对于第次迭代，重新使用的第1行以及的第1个元素，即

第次迭代使用的第2行以及的第2个元素，以此类推，每进行次迭代就从头循环一次。可视为算法的步长，为了保证算法的收敛性，限定步长的取值范围为。

Kaczmarz 算法的收敛性

在Kaczmarz 算法中，如果，那么当时，。

当时，Kaczmarz 算法收玫到集合中唯一能够使得距离最小的点。

如果设定，则 Kaczmarz 算法具有如下性质：

在第次迭代中，误差满足

将代人，可得

由此可得，和之间的差与正交。

考虑一般意义下的线性方程组

其中，，且有。当且时，方程有唯一解。因此，为了求解该方程组，必须求解矩阵的逆矩阵。这里讨论求解的一般方法，该方法定义了矩阵的伪逆或广义逆，当的逆矩阵不存在时(如不是方阵时)，伪逆或广义逆将扮演着的角色。矩阵的Moore-Penrose 逆矩阵，用表示。

一个秩为的矩阵可以表示一个列满秩 (秩为 ) 的矩阵和一个行满秩 (秩为 ) 的矩阵的乘积。矩阵的这种分解方式称为满秩分解，这是由 Gantmacher 和 Ben-Israel and Greville定义的

矩阵，那么，存在矩阵和矩阵，使得

其中，

注意，如果，那么可按照如下方式选择和 :

其中,，为的单位阵。反之，如果，那么和可以表示为

例：令，，可对进行满秩分解

考虑矩阵方程

其中，已知，为末知待求的矩阵。注意，如果是非奇异的方阵，那么该方程有唯一解。可以将认定为 Moore-Penrose 逆矩阵，也称为伪逆或广义逆矩阵。

给定矩阵，如果矩阵满足且存在两个矩阵，使得

则称是矩阵的伪逆。

条件可以作如下解释：的伪逆矩阵中的每一行都是矩阵中所有行向量的线性组合，中的每一列都是矩阵中所有列向量的线性组合。

对于矩阵，且，可以很容易验证下式就是矩阵的伪逆:

实际上，，如果定义 , 那么。注意，。因此，经常称为矩阵的左伪逆。这一伪逆公式出现在最小二乘分析过程中。

对于矩阵 , 且 , 与上面类似，可以很容易验证下式就是矩阵的伪逆:

注意，。因此，经常称为矩阵的右伪逆。这一公式出现在求方程的最小范数解的场合。

矩阵，如果的伪逆存在，那么是唯一的。

证明：令和是矩阵的伪送，只需要证明即可。根据伪逆的定义，可知

存在矩阵和，使得

令有因此，由这两个方程可得这意味着

由于 , 有

这说明

因此，

证明伪逆存在性。可以证明，任意矩阵的伪逆可以由下式给出：

和分别是矩阵和的伪逆，而矩阵和是的满秩分解，即, 和都是满秩的。已知和的计算公式分别为

矩阵的满秩分解为，那么

证明：需要证明

满足关于伪逆矩阵的条件。首先，注意

接下来，定义

很容易验证矩阵和满足

因此，就是矩阵的伪逆。

利用可以将表达式

简化为

某线性方程组为。向量可在空间中最小化; 而且，在中所有能够最小化的向量中，向量的范数最小，且是唯一的。

证明：首先证明向量可在空间中最小化。注意对于任意向量，有

需要证明

实际上，

由于

因此

故有

由于

因此可得

这意味着能够最小化。

接下来证明在中所有能够最小化的向量中，向量的范数最小，且是唯一的。

令表示某个能够最小化的向量。有

可以证明

注意

其中, 上标表示逆矩阵的转置。根据满秩分解，可得。由于最小化，矩阵满秩，因此，能够在空间中最小化。由于矩阵满秩，因此。将其代入到上式中，可得。

这样，可得对于所有，有

因此，

即

这说明，在中所有能够最小化的向量中，向量的范数最小，且是唯一的。广义逆矩阵有以下重要性质:

普通的逆矩阵也存在类似的性质。需要指出的是，却不总是成立

广义逆矩阵还可以按照另外的方式进行定义，即 Penrose 定义。具体而言，按照 Penrose 定义，矩阵的广义逆矩阵为满足下列性质的矩阵 , 具有唯一性:

最小二乘分析

递推最小二乘算法

线性方程组的最小范数解

Kaczmarz 算法

一般意义下的线性方程组的求解

满秩分解

Moore-Penrose 逆矩阵

在求解线性方程时表现出的两个重要性质