算法导论28.1 Exercises 答案

28.1-1

根据前向替代的过程，可以知道：

\(\begin{aligned} x_1&=b_1=3\\ x_2&=b_2-\sum_{j=1}^1 a_{2,j} x_j=14-4\cdot 3=2\\ x_3&=b_3-\sum_{j=1}^2 a_{3,j} x_j=-7-(-6)\cdot 3-5\cdot 2=1\\ \end{aligned}\)

也就是有解\(\begin{bmatrix} x_1\\ x_2\\ x_3\\ \end{bmatrix}= \begin{bmatrix} 3\\ 2\\ 1\\ \end{bmatrix}\)。

28.1-2

以下是多轮进行迭代的结果：

\(\begin{array}{c|c} L&U\\ \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\\ \end{bmatrix}& \begin{bmatrix} 0&0&0\\ 0&0&0\\ 0&0&0\\ \end{bmatrix}\\ \begin{bmatrix} 1&0&0\\ 2&1&0\\ 3&0&1\\ \end{bmatrix}& \begin{bmatrix} 4&-5&6\\ 0&0&0\\ 0&0&0\\ \end{bmatrix}\\ \begin{bmatrix} 1&0&0\\ 2&1&0\\ 3&2&1\\ \end{bmatrix}& \begin{bmatrix} 4&-5&6\\ 0&4&-5\\ 0&0&0\\ \end{bmatrix}\\ \begin{bmatrix} 1&0&0\\ 2&1&0\\ 3&2&1\\ \end{bmatrix}& \begin{bmatrix} 4&-5&6\\ 0&4&-5\\ 0&0&4\\ \end{bmatrix}\\ \end{array}\)

28.1-3

令\(A=\begin{bmatrix} 1&5&4\\ 2&0&3\\ 5&8&2\\ \end{bmatrix},b=\begin{bmatrix} 12\\ 9\\ 5 \end{bmatrix}\)。

那么首先对\(A\)进行LUP分解，得到

\[L=\begin{bmatrix} 1&0&0\\ \frac{1}{5}&1&0\\ \frac{2}{5}&-\frac{16}{17}&2\\ \end{bmatrix},U=\begin{bmatrix} 5&8&2\\ 0&\frac{17}{5}&\frac{18}{5}\\ 0&0&\frac{95}{17}\\ \end{bmatrix},P=\begin{bmatrix} 0&0&1\\ 1&0&0\\ 0&1&0\\ \end{bmatrix}\]

那么使用前向替代求解关于\(y\)的未知数的方程\(Ly=Pb\)，最终可以得到：

\[\begin{bmatrix} y_1\\ y_2\\ y_3\\ \end{bmatrix}= \begin{bmatrix} 5\\ 11\\ \frac{295}{17}\\ \end{bmatrix}\]

再使用后向替代可以得到：

\[\begin{bmatrix} x_1\\ x_2\\ x_3\\ \end{bmatrix}= \begin{bmatrix} -\frac{3}{19}\\ -\frac{1}{19}\\ \frac{49}{19}\\ \end{bmatrix}\]

28.1-4

根据对角矩阵\(A\)的性质，我们可以构造\(I_nA=I_nA\)，其中\(I_n\)是单位矩阵，它可以视为是单位下三角矩阵\(L\)，而\(A\)可以视为是上三角矩阵\(U\)。

28.1-5

结论：令\(L=U=I_n\)，\(P=A^{-1}\)，其中\(A\)是给定的排列矩阵.\(I_n\)是单位矩阵。接下来证明这种构造是唯一的。

根据题目D.2-3的结论，可以知道\(A\)是可逆的，因此\(U\)中主对角线上的所有元素都是非\(0\)。由于\(P,A\)都是排列矩阵，因此根据题目D.1-4的结论，\(PA=LU\)仍是排列矩阵。

接下来使用反证法证明：\(L=I_n\)，也就是说\(\forall 1\le j<i\le n,l_{ij}=u_{ji}=0\)均成立：假设\(\exists i>1,l_{i,1}\neq 0\)，那么g观察此时\(LU\)的第一列，那么将会导致\((LU)_{11}\neq 0,(LU)_{i1}\neq 0\)，这说明\(LU\)不可能是排列矩阵；类似的论证可以证明\(\forall j>1,u_{ij}=0\)必然成立。因此我们抛弃矩阵\(L,U\)的第\(1\)行和第\(1\)列递归进行论证，可以发现，递归情形和原本的情形一样。因此，\(\forall 1\le j<i\le n,l_{ij}=u_{ji}=0\)均成立。也就是说，\(L,U\)都是对角矩阵，那么可知\(L=I_n\)。由于\(PA\)是排列矩阵，因此\(U\)也是排列矩阵，那么有\(U=I_n\)。因此得到\(P=A^{-1}\)。

28.1-6

零矩阵\(O_n\)显而易见地拥有一个LU分解：\(O_n=I_nO_n\)。其中\(I_n\)是单位矩阵，它可以视为是单位下三角矩阵\(L\)，而\(O_n\)可以视为是上三角矩阵\(U\)。

28.1-7

对于算法LU-DECOMPOSITION，执行最后一次外层for循环是必须的。因为\(u_{nn}\)上三角处的所有值一开始都是未定义的，而执行最后一次循环后，才会有\(u_{nn}=a_{nn}\)，从而有定义。

对于算法LUP-DECOMPOSITION，执行最后一次外层for循环不是必须的。因为此时\(U\)和\(L\)都在原来的矩阵\(A\)上表示，当第\(n-1\)次循环执行完成后，第\(n\)行的结果已经是\(U\)中的值。此外，无论\(a_{nn}\)结果如何，都不会改变\(\pi\)中前\(n-1\)个元素的值。因此此处的外层for循环没有必要执行最后一次。