漫步线性代数五——三角分解和行交换

我们继续消去法，看看它对矩阵意味着什么。我们从 $Ax=b$ 开始：

A x = ⎡ ⎣ ⎢ 24 - 2 1 - 6 7 102 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ u v w ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 5 - 2 9 ⎤ ⎦ ⎥ = b (1)

$\begin{equation} Ax= \begin{bmatrix} 2&1&1\\4&-6&0\\-2&7&2 \end{bmatrix} \begin{bmatrix} u\\v\\w \end{bmatrix}= \begin{bmatrix} 5\\-2\\9 \end{bmatrix} =b\tag1 \end{equation}$

然后有三个消去步骤，乘数分别为

$2，-1，-1$ ：

Step 1. 第二个方程减去第一个方程的2倍；

Step 2. 第三个方程减去第一个方程的-1倍；

Step 3. 第三个方程减去第二个方程的-1倍；

这个结果等价于

$Ux=c$ ，其中

$U$ 是一个新系数矩阵：

U p p e r t r i a n g u l a r U x = ⎡ ⎣ ⎢ 200 1 - 8 0 1 - 2 1 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ u v w ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 5 - 12 2 ⎤ ⎦ ⎥ = c (2)

$\begin{equation} {\rm {Upper\ triangular}}\quad Ux= \begin{bmatrix} 2&1&1\\0&-8&-2\\0&0&1 \end{bmatrix} \begin{bmatrix} u\\v\\w \end{bmatrix}= \begin{bmatrix} 5\\-12\\2 \end{bmatrix} =c\tag2 \end{equation}$

矩阵

$U$ 是上三角矩阵，主对角线下面的元素都为零。

对于原始向量 $b$ ，用相同的方法(即将

$A$ 变为 $U$ )推导出新值

$c$ ，前向消元一共执行了三个行操作：

开始是 $A$ 和

$b$ ；
一次应用步骤1,2,3；
最后是 $U$ 和

$c$ 。

然后用回代求解 $Ux=c$ 。这里我们先集中考虑

$A$ 和 $U$ 的关系。

第一步的矩阵 $E$ ，第二步的矩阵 $F$ ，第三步的矩阵 $G$ 之前已经介绍了。他们都叫做初等矩阵，很容易看出他们是如何得出的。方程 $i$ 减去方程 $j$ 的 $\ell$ 倍，也就是将数 $-\ell$ 放到 $(i,j)$ 的位置，其他地方跟单位矩阵保持一致，即对角线上为1其他地方为0，这样矩阵乘法就执行了行操作。

三次操作的结果是 $GFEA=U$ ，注意 $E$ 首先乘以 $A$ ，然后是 $F$ ，最后是 $G$ 。我们可以将 $GFE$ 乘在以前得到一个下三角矩阵(0省略掉了)：

G F E = ⎡ ⎣ ⎢ 1111 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 1111 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 1 - 2 11 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 1 - 2 - 1 111 ⎤ ⎦ ⎥ (3)

$\begin{equation} GFE= \begin{bmatrix} 1&&\\&1&\\&1&1 \end{bmatrix} \begin{bmatrix} 1&&\\&1&\\1&&1 \end{bmatrix} \begin{bmatrix} 1&&\\-2&1&\\&&1 \end{bmatrix}= \begin{bmatrix} 1&&\\-2&1&\\-1&1&1 \end{bmatrix}\tag3 \end{equation}$

但是最重要的问题是反过来的：我们怎样从

$U$ 回到 $A$ ？如何撤销高斯消元法的步骤？

撤销第一步不难，不用减法而是用第二行加上第一行的二倍。做一次加法和一次减法最后回到了单位矩阵：

⎡ ⎣ ⎢ 120010001 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 1 - 2 0 010001 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 100010001 ⎤ ⎦ ⎥ (4)

$\begin{equation} \begin{bmatrix} 1&0&0\\2&1&0\\0&0&1 \end{bmatrix} \begin{bmatrix} 1&0&0\\-2&1&0\\0&0&1 \end{bmatrix}= \begin{bmatrix} 1&0&0\\0&1&0\\0&0&1 \end{bmatrix}\tag4 \end{equation}$

一个操作取消了另一个操作。用矩阵的语言来描述就是：一个矩阵是另一个矩阵的逆。如果初等矩阵

$E$ 在 $(i,j)$ 处有值

$-\ell$ ，那么它的逆在同样的位置处为

$\ell$ 。所以

$E^{-1}E=I$ ，也就是等式(4)。

我们可以用 $E^{-1},F^{-1},G^{-1}$ 将消元的每步都取逆。最终的问题就是一次撤销整个操作，知道什么矩阵将 $U$ 回到 $A$ 。

因为从 $A$ 到 $U$ 的过程中步骤三是最后一步，所以矩阵 $G$ 肯定是第一个取逆的。和正向的顺序正好相反！第二个取逆步骤是 $F^{-1}$ ，第三个是 $E^{-1}$ ：

E - 1 F - 1 G - 1 U = A i s L U = A (5)

$\begin{equation} E^{-1}F^{-1}G^{-1}U=A\ is \ LU=A\tag5 \end{equation}$

现在我们将 $U$ 变为 $A$ 的矩阵称为 $L$ ，因为它是下三角矩阵。通过将他们按顺序乘起来就能看出这个性质：

E - 1 F - 1 G - 1 = ⎡ ⎣ ⎢ 1211 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 1 - 1 11 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 1 1 - 1 1 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 12 - 1 1 - 1 1 ⎤ ⎦ ⎥ = L (6)

$\begin{equation} E^{-1}F^{-1}G^{-1}= \begin{bmatrix} 1&&\\2&1&\\&&1 \end{bmatrix} \begin{bmatrix} 1&&\\&1&\\-1&&1 \end{bmatrix} \begin{bmatrix} 1&&\\&1&\\&-1&1 \end{bmatrix}= \begin{bmatrix} 1&&\\2&1&\\-1&-1&1 \end{bmatrix} =L\tag6 \end{equation}$
对角线下面的元素分别是 $\ell=2,-1,-1$ 。当矩阵相乘时，通常无法直接给出答案。但这里比较特殊直接按从左到右的顺序立马写出来。如果计算机存储每个乘数 $\ell_{ij}$ (也就是第 $i$ 行减去第 $j$ 行的倍数)，并且在第 $i,j$ 的位置得到零，那么这些乘数就记录了消元法。

8、没有行交换的三角分解 $A=LU$ 。 $L$ 是下三角矩阵，其中对角线元素为1，下面的元素为 $\ell_{ij}$ 。 $U$ 是上三角矩阵，它的对角线元素是主元。

例1：

A = ⎡ ⎣ ⎢ 111122123 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 111011001 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 100110111 ⎤ ⎦ ⎥ = L U

$A= \begin{bmatrix} 1&1&1\\1&2&2\\1&2&3 \end{bmatrix}= \begin{bmatrix} 1&0&0\\1&1&0\\1&1&1 \end{bmatrix} \begin{bmatrix} 1&1&1\\0&1&1\\0&0&1 \end{bmatrix}= LU$
从 $A$ 到 $U$ 执行行的减法操作，从 $U$ 到 $A$ 执行加法操作。

例2：当 $U$ 是单位矩阵时， $L$ 和 $A$ 相等

$A = ⎡ ⎣ ⎢ 1 ℓ 21 ℓ 31 01 ℓ 32 001 ⎤ ⎦ ⎥$
$A= \begin{bmatrix} 1&0&0\\ \ell_{21}&1&0\\ \ell_{31}&\ell_{32}&1 \end{bmatrix}$
在 $A$ 上的消元步骤很容易： $(i)$ 第二行减去第一行的 $\ell_{21}$ 倍， $(ii)$ 第三行减去第一行的 $\ell_{31}$ 倍， $(iii)$ 第三行减去第二行的 $\ell_{32}$ 倍。结果是单位矩阵 $U=I$ 。将他们的逆相乘即可得到 $A$ :

$⎡ ⎣ ⎢ 1 ℓ 21 11 ⎤ ⎦ ⎥ \times ⎡ ⎣ ⎢ 1 ℓ 31 11 ⎤ ⎦ ⎥ \times ⎡ ⎣ ⎢ 1 1 ℓ 32 1 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 1 ℓ 21 ℓ 31 01 ℓ 32 001 ⎤ ⎦ ⎥$
$\begin{bmatrix} 1&&\\ \ell_{21}&1&\\&&1 \end{bmatrix} \times \begin{bmatrix} 1&&\\&1&\\ \ell_{31}&&1 \end{bmatrix} \times \begin{bmatrix} 1&&\\&1&\\& \ell_{32}&1 \end{bmatrix}= \begin{bmatrix} 1&0&0\\ \ell_{21}&1&0\\ \ell_{31}& \ell_{32}&1 \end{bmatrix}$
三角分解 $A=LU$ 非常重要，所以我在多说一点。以前在线性代数中不讲这些知识，或许是因为它太难(但是相信大家已经掌握了)。如果例2中的 $U$ 是任何一个矩阵而不是单位矩阵 $U=I$ ，那么我们就是会看到一般的处理过程：

$A = L U ⎡ ⎣ ⎢ 1 ℓ 21 ℓ 31 01 ℓ 32 001 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ r o w 1 o f U r o w 2 o f U r o w 3 o f U ⎤ ⎦ ⎥ = A (7)$
$\begin{equation} A=LU\qquad \begin{bmatrix} 1&0&0\\ \ell_{21}&1&0\\ \ell_{31}& \ell_{32}&1 \end{bmatrix} \begin{bmatrix} row\ 1\ of \ U\\ row\ 2\ of \ U\\ row\ 3\ of \ U \end{bmatrix} =A\tag7 \end{equation}$
它的证明就是利用消元步骤，右边将 $A$ 变为 $U$ ，左边将 $L$ 变为 $I$ ，和例2一样。最终方程两边都等于 $U$ ，这些步骤都是双效的，所有(7)是正确的即 $A=LU$

$A=LU$ 非常重要，形式也很美。我们目前用的是 $3\times 3$ 矩阵，但是对于更大的矩阵它也适用。这里我们给出一个例子

例3：

$A = ⎡ ⎣ ⎢ ⎢ ⎢ 1 - 1 - 1 2 - 1 - 1 2 - 1 - 1 2 ⎤ ⎦ ⎥ ⎥ ⎥ = ⎡ ⎣ ⎢ ⎢ ⎢ 1 - 1 1 - 1 1 - 1 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎡ ⎣ ⎢ ⎢ ⎢ 1 - 1 1 - 1 1 - 1 1 ⎤ ⎦ ⎥ ⎥ ⎥$
$A= \begin{bmatrix} 1&-1&&\\-1&2&-1&\\&-1&2&-1\\&&-1&2 \end{bmatrix}= \begin{bmatrix} 1&&&\\-1&1&&\\&-1&1&\\&&-1&1 \end{bmatrix} \begin{bmatrix} 1&-1&&\\&1&-1&\\&&1&-1\\&&&1 \end{bmatrix}$
$A$ 有三条对角线， $L,U$ 有两条。

一个线性系统=两个三角系统

$A=LU$ 有一个很实际的应用，它不仅记录了消元法的步骤； $L,U$ 也是求解 $Ax=b$ 的矩阵。事实上 $A$ 可以被抛弃了！通过前向消元(利用 $L$ )可以将 $b$ 变成 $c$ ，然后利用回代(利用 $U$ )可以将 $c$ 变为 $x$ ：

$L c = b t h e n U x = c (8)$
$\begin{equation} Lc=b\quad then\quad Ux=c\tag8 \end{equation}$
用 $L$ 乘以第二个方程得 $LUx=Lc$ ，其中 $Ax=b$ 。每一个三角系统可以很快的求解出来，这样我们的消元法就变为：

分解(从 $A$ 中求出因子 $L,U$ )

求解(从 $L,U,b$ 中求出解 $x$ )

求解子过程满足方程(8)：两个三角方程每个需要 $n^2/2$ 步，所以对于右边任何一个 $b$ ，我们只需要 $n^2$ 步就能找出答案。这远小于 $n^3/3$ 。

例4：考虑上个例子中的矩阵，右边的 $b=(1,1,1,1)$

$A x = b x 1 - x 1 - + - x 2 2 x 2 x 2 - + - x 3 2 x 3 x 3 - + x 4 2 x 4 = = = = 1111 分解成 L c = b, U x = c L c = b c 1 - c 1 + - c 2 c 2 + - c 3 c 3 + c 4 = = = = 1111 求出 c = ⎡ ⎣ ⎢ ⎢ ⎢ 1234 ⎤ ⎦ ⎥ ⎥ ⎥ U x = c x 1 - x 2 x 2 - x 3 x 3 - x 4 x 4 = = = = 1234 求出 x = ⎡ ⎣ ⎢ ⎢ ⎢ 10974 ⎤ ⎦ ⎥ ⎥ ⎥$
$\begin{align*} &Ax=b\quad \begin{matrix} x_1&-&x_2&&&&&=&1\\ -x_1&+&2x_2&-&x_3&&&=&1\\ &-&x_2&+&2x_3&-&x_4&=&1\\ &&&-&x_3&+&2x_4&=&1 \end{matrix} {\text{分解成$Lc=b,Ux=c$}} \\ &Lc=b\quad \begin{matrix} c_1&&&&&&&=&1\\ -c_1&+&c_2&&&&&=&1\\ &-&c_2&+&c_3&&&=&1\\ &&&-&c_3&+&c_4&=&1 \end{matrix} \quad {\text{求出}} c=\begin{bmatrix} 1\\2\\3\\4 \end{bmatrix} \\ &Ux=c\quad \begin{matrix} x_1&-&x_2&&&&&=&1\\ &&x_2&-&x_3&&&=&2\\ &&&&x_3&-&x_4&=&3\\ &&&&&&x_4&=&4 \end{matrix} \quad {\text{求出}} x=\begin{bmatrix} 10\\9\\7\\4 \end{bmatrix} \end{align*}$
对于这些特殊的三角矩阵，操作步骤由 $n^2$ 变为 $2n$ 。可以清楚的看到 $Lc=b$ 通过前向步骤求解出来 $c$ ( $c_1$ 在 $c_2$ 之前)，而 $Ux=c$ 通过回代过程求解出来 $x$ ( $x_4$ 在 $x_3$ 之前)。

注解1： $LU$ 关于在对角线上是不对称的： $L$ 是1而 $U$ 是主元。我们可以让它变得一样，提出一个主元矩阵 $D$ 即可：

$U = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ d 1 d 2 ⋱ d n ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ 1 u 12 / d 1 1 u 13 / d 1 u 23 / d 2 ⋱ ⋮ ⋮ ⋮ 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ (9)$
$\begin{equation} U= \begin{bmatrix} d_1&&&\\&d_2&&\\ &&\ddots&\\&&&d_n \end{bmatrix} \begin{bmatrix} 1&u_{12}/d_1&u_{13}/d_1&\vdots\\&1&u_{23}/d_2&\vdots\\ &&\ddots&\vdots\\&&&1 \end{bmatrix}\tag9 \end{equation}$
上面的例子中主元为1，所以 $D=I$ 。但是这只是个特例，一般情况下 $LU$ 和 $LDU$ (也写成 $LDV$ )是不相同的。

当看到 $LDU,LDV$ 时，可以将 $U,V$ 理解为每行是除以主元得到的。举例说明

$A = [1324] = [131] [1 2 - 2] = [131] [1 - 2] [121] = L D U$
$A= \begin{bmatrix} 1&2\\3&4 \end{bmatrix}= \begin{bmatrix} 1&\\3&1 \end{bmatrix} \begin{bmatrix} 1&2\\&-2 \end{bmatrix}= \begin{bmatrix} 1&\\3&1 \end{bmatrix} \begin{bmatrix} 1&\\&-2 \end{bmatrix} \begin{bmatrix} 1&2\\&1 \end{bmatrix}= LDU$
$L,U$ 的对角线上都是1， $D$ 的对角线上是主元1和-2。

注解2：我们已经给出了每个消元步骤的表达式，其中计算必须按顺序进行。对于这一点不全对，有一种克劳特算法计算方法跟他有点不同，在顺序上稍微自由一下。但是最终结果 $L,D,U$ 不存在自由：

9、如果 $A=L_1D_1U_1,A=L_2D_2U_2$ ，其中 $L$ 是下三角矩阵， $U$ 是上三角矩阵， $D$ 是对角矩阵且对角线上没有零元素，那么 $L_1=L_2,D_1=D_2,U_1=U_2$ 。 $LDU$ 分解和 $LU$ 分解由 $A$ 唯一确定。

这个证明需要用到逆矩阵，等学到时再给出详细证明。

行交换和置换矩阵

我们现在必须面对无法避免的问题：主元可能是零。这种情况可能发生在中间的计算过程中，如果 $a_{11}=0$ 那就是在开始就发生了。如简单的一个例子

[0324] [u v] = [b 1 b 2]

$\begin{bmatrix} 0&2\\3&4 \end{bmatrix} \begin{bmatrix} u\\v \end{bmatrix}= \begin{bmatrix} b_1\\b_2 \end{bmatrix}$
明显这种情况比较麻烦，我们无法利用第一个方程消去系数3。

但是修正也比较明显，交换两个方程，将元素3上移变为主元。对于这个例子矩阵将变成上三角矩阵：

$3 u + 4 v 2 v = = b 2 b 1$
$\begin{matrix} 3u&+&4v&=&b_2\\ &&2v&=&b_1 \end{matrix}$
为了用矩阵形式表示，我们需要置换矩阵 $P$ 来产生行交换，通过对单位矩阵 $I$ 进行交换即可得到：

$P = [0110] P A = [0110] [0324] = [3042]$
$P= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \quad PA= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \begin{bmatrix} 0&2\\ 3&4 \end{bmatrix}= \begin{bmatrix} 3&4\\ 0&2 \end{bmatrix}$
对于 $b$ ， $P$ 可以产生相同的效果，即交换 $b_1,b_2$ 。新的系统就变为 $PAx=Pb$ ，行交换中未知量 $u,v$ 没有改变顺序。

置换矩阵 $P$ 和单位矩阵有相同的行，每行每列都有1。最普通的置换矩阵是单位矩阵 $P=I$ (没有发生任何交换)。两个置换矩阵的乘积是另一个置换矩阵。

如果 $P=I$ ，那么最简单的置换就是只交换两行，其他的置换交换更多。对于大小为 $n$ 的矩阵存在 $n!=(n)(n-1)\cdots(1)$ 中置换结果，第一行有 $n$ 种选择，那么第二行有 $n-1$ 种选择，最后一行只有1种选择。下面我们给出所有的 $3\times 3$ 置换矩阵(有 $3!=(3)(2)(1)=6$ 个矩阵)：

$I = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥ P 31 = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥ P 21 = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥ P 32 = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥ P 32 P 21 = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥ P 21 P 32 = ⎡ ⎣ ⎢ 111 ⎤ ⎦ ⎥$
$\begin{array}{ccc} I=\begin{bmatrix}1&&\\&1&\\&&1\end{bmatrix}& P_{21}=\begin{bmatrix}&1&\\1&&\\&&1\end{bmatrix}& P_{32}P_{21}=\begin{bmatrix}&1&\\&&1\\1&&\end{bmatrix}\\ P_{31}=\begin{bmatrix}&&1\\&1&\\1&&\end{bmatrix}& P_{32}=\begin{bmatrix}1&&\\&&1\\&1&\end{bmatrix}& P_{21}P_{32}=\begin{bmatrix}&&1\\1&&\\&1&\end{bmatrix} \end{array}$
如果 $n=4$ ，将会有24种置换矩阵，如果 $n=2$ 那么只有两种置换矩阵，即

$[1001] [0110]$
$\begin{bmatrix} 1&0\\0&1 \end{bmatrix} \quad \begin{bmatrix} 0&1\\1&0 \end{bmatrix}$

如果我们知道逆和转置(之后将他们定义为 $A^{-1}$ 和 $A^{T}$ )，那么我们将发现一个重要的事实： $P^{-1}$ 总是等于 $P^{T}$ 。

主元位置上是零会产生两种可能：这个问题可能很容易修改，或者比较麻烦。这完全取决于零元素，如果一列下方有非零元素，那么就能执行行交换，将非零元素变成主元然后就能继续消元过程：

$A = ⎡ ⎣ ⎢ 00 d a 0 e b c f ⎤ ⎦ ⎥ d = 0 \Rightarrow 没有第一主元 a = 0 \Rightarrow 没有第二主元 c = 0 \Rightarrow 没有第三主元$
$A= \begin{matrix} \begin{bmatrix} 0&a&b\\0&0&c\\d&e&f \end{bmatrix} & \begin{matrix} d=0\Rightarrow{\text{没有第一主元}}\\a=0\Rightarrow{\text{没有第二主元}}\\c=0\Rightarrow{\text{没有第三主元}} \end{matrix} \end{matrix}$
如果 $d=0$ ，那么这个问题将无法解决，矩阵就是奇异的，对 $Ax=b$ 不存在唯一解。如果 $d$ 不是零，那么通过交换1,3行可以将 $d$ 变成主元。然而下一个主元是零，它下面是 $a$ ，如果 $a$ 不是零，那么用置换矩阵 $P_{23}$ 进行行交换：

$P 13 = ⎡ ⎣ ⎢ 001010100 ⎤ ⎦ ⎥ P 23 = ⎡ ⎣ ⎢ 100001010 ⎤ ⎦ ⎥ P 23 P 13 A = ⎡ ⎣ ⎢ d 00 e a 0 f b c ⎤ ⎦ ⎥$
$P_{13}= \begin{bmatrix} 0&0&1\\0&1&0\\1&0&0 \end{bmatrix} \quad P_{23}= \begin{bmatrix} 1&0&0\\0&0&1\\0&1&0 \end{bmatrix} \quad P_{23}P_{13}A= \begin{bmatrix} d&e&f\\0&a&b\\0&0&c \end{bmatrix}$

还有一点是：置换矩阵 $P_{23}P_{13}$ 可以执行一次行交换：

$P 23 P 13 A = ⎡ ⎣ ⎢ 100001010 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 001010100 ⎤ ⎦ ⎥ = ⎡ ⎣ ⎢ 010001100 ⎤ ⎦ ⎥ = P$
$P_{23}P_{13}A= \begin{bmatrix} 1&0&0\\0&0&1\\0&1&0 \end{bmatrix} \begin{bmatrix} 0&0&1\\0&1&0\\1&0&0 \end{bmatrix}= \begin{bmatrix} 0&0&1\\1&0&0\\0&1&0 \end{bmatrix} =P$
这样的话我们就直接用 $P$ 乘以 $A$ ，执行了正确的行交换后，那么就可以进行消元了。

消元法： $PA=LU$

主要的观点是这样的：如果在行交换的帮助下可以完成消元，那么我们可以首先用 $P$ 来完成这个步骤。矩阵 $PA$ 不需要行交换。换句话说， $PA$ 可以分解成标准的 $L,U$ 。高斯消元理论可以概括为下面几行：

10、对于奇异的情况，存在一个置换矩阵，它重排矩阵 $A$ 的行来避免主元位置出现零，然后 $Ax=b$ 就存在唯一解：

提前进行行排序， $PA$ 可以分解成 $LU$ 。

如果不存在 $P$ 使得产生所有主元集合，那么消元法将失效。

实际中，当原始主元接近零时，我们也考虑行交换，选择一个更大的主元是为了减小舍入误差。

仔细留意一下 $L$ ，如果消元过程是先从第二行减去第一行，也就是 $\ell_{21}=1$ ，然后2,3行进行交换。或者如果提前进行交换，那么乘因子就变为 $\ell_{31}=1$ 。

例5：

$A = ⎡ ⎣ ⎢ 112115138 ⎤ ⎦ ⎥ \to ⎡ ⎣ ⎢ 100103136 ⎤ ⎦ ⎥ \to ⎡ ⎣ ⎢ 100130162 ⎤ ⎦ ⎥ = U (10)$
$\begin{equation} A= \begin{bmatrix} 1&1&1\\1&1&3\\2&5&8 \end{bmatrix} \to \begin{bmatrix} 1&1&1\\0&0&3\\0&3&6 \end{bmatrix} \to \begin{bmatrix} 1&1&1\\0&3&6\\0&0&2 \end{bmatrix} =U\tag{10} \end{equation}$
然后利用行交换来恢复 $LU$ ，但是此时 $\ell_{31}=1,\ell_{21}=2$ ：

$P = ⎡ ⎣ ⎢ 100001010 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 121010001 ⎤ ⎦ ⎥ P A = L U (11)$
$\begin{equation} P= \begin{bmatrix} 1&0&0\\0&0&1\\0&1&0 \end{bmatrix} \quad \begin{bmatrix} 1&0&0\\2&1&0\\1&0&1 \end{bmatrix} \quad PA=LU\tag{11} \end{equation}$

一个线性系统=两个三角系统

行交换和置换矩阵

消元法： PA=LU PA=LU

你可能也喜欢

消元法： $PA=LU$