算法导论28.3 Exercises 答案

发表于 2023-08-01 更新于 2025-12-23 分类于算法导论阅读次数：本文字数： 2.7k 阅读时长 ≈ 2 分钟

28.3-1

构造$n$维单位向量$ei=(0,0,\dots,1,0,\dots,0)$，即$e_i$的第$i$个值为$1$，其余值为$0$。可见$e_i$是一个非零向量。那么可以得到$e_i^TAe_i=a{ii}$。由于$A$是一个正定矩阵，$ei$是一个非零向量，因此$a{ii}>0$。

故一个正定矩阵中，对角线的元素都是正数。

28.3-2

令$x=(y,z)^T$是一个二维向量，那么考虑求$x^TAx$的值，有

$\begin{aligned}
x^TAx&=(y,z)\begin{bmatrix}a&b\b&c\end{bmatrix}\begin{bmatrix}y\z\end{bmatrix}\
&=(y,z)\begin{bmatrix}ay+bz\by+cz\end{bmatrix}\
&=ay^2+2byz+cz^2\
\end{aligned}$

类似的，构造$y=-bz/a$，那么有$x^TAx=-b^2z^2/a+cz^2=z^2(c-b^2/a)=z^2(ca-b^2)/a$。

当$z\neq 0$时，$x$是一个非零向量。由于$a$是对角线上的元素，按照题目28.3-1的结论，有$a>0$。由于$A$是对称正定的，由此推出$ca-b^2>0$。

28.3-3

使用反证法证明。假设这个最大元素出现在矩阵$A$的位置$a{ij}$中，由于$A$是对称的，因此有$a{ij}=a{ji}$。构造向量$x=e_i-e_j$，其中$e_i$表示第$i$个位置为$1$的单位向量。考虑计算$x^TAx$的值，有$x^TAx=a{ii}-a{ij}-a{ji}+a{jj}=a{ii}+a{jj}-2a{ij}\le 0$。非$0$向量$x$的存在说明了矩阵$A$不是正定矩阵。

因此，元素的最大值一定出现在正定矩阵的主对角线中。

28.3-4

假设$A$中的某个主子矩阵是从$A$的第$i_1,i_2,\dots,i_k$行和列构成的，令$J={i_1,i_2,\dots,i_k}$。

由于$A$是正定矩阵，因此对于满足如下条件$x$的向量，都有$f(\mathbf{x})=\mathbf{x}^TA\mathbf{x}>0$：

如果$i\not\in J$，那么$\mathbf{x}_i=0$；否则，$\mathbf{x}_i$可以取任意值。
$\mathbf{x}$是非$0$向量。

针对这种形式的$\mathbf{x}$向量，可以将二次型$f(\mathbf{x})$化简成：

$f(\mathbf{x})=\sum_{i\in J}\sum_{j\in J} a_{ij}x_ix_j$

由于这个二次型只有$x{i_1},x{i2},\dots,x{i_k}$这些变量，因此可以重新构建出一个从$A$的第$i_1,i_2,\dots,i_k$行和列构成的主子矩阵$A’$。

由于$f(\mathbf{x})>0$对于任意非$0$向量$(\mathbf{x}{i_1},\mathbf{x}{i2},\dots,\mathbf{x}{i_k})$均成立，因此$A’$是一个正定矩阵。

28.3-5

LU分解并不会做出任何行变换，因此LU分解的每一轮的主元都是矩阵左上角的函数。

在LU分解一开始时，有$\det A1=a{11}$，并且主元为$a{11}$，因此当$k=1$时，有$\dfrac{\det A_1}{\det A{0}}=a_{11}$，因为题目假定了$\det A_0=1$。

由于LU分解的过程是对矩阵$A$进行高斯消元，即对$A$进行行变换；此外，由于高斯消元的过程只对下面的行进行消元；而不会使用下面的行对上面的行进行行变换操作，因此顺序主子式$A1,A_2,\dots,A_n$的行列式都不会改变。到了选取第$k$个主元时$a{kk}’$，第$k$行在$a{kk}$左边的元素都已经变成了$0$，因此有$\det A_k=a{kk}’\cdot \det A{k-1}$，即第$k$个主元的值为$\dfrac{\det A_k}{\det A{k-1}}$。原结论成立。

28.3-6

通过这些数据点和$F$形式的函数，可以写出$A$为：

$A=\begin{bmatrix}
1 & 0 & e\
1 & 2 & e^2\
1 &3\lg 3 & e^3\
1 & 8 & e^4
\end{bmatrix}$

通过如下Python代码，可以求出$A^{+}$和$\mathbf{c}$的结果大约为：

import numpy as np
from math import log2, e

A = np.array([[1, 0, e], [1, 2, e ** 2], [1, 3 * log2(3), e ** 3], [1, 8, e ** 4]])
y = np.array([[1, 1, 3, 8]]).transpose()
AT = A.transpose()
mA = AT @ A
Ap = np.linalg.inv(mA) @ AT

print(Ap)
print(Ap @ y)

$\begin{aligned}
A^+&\approx\begin{bmatrix}
0.73633742 & 0.36355436& -0.02219508 & -0.0776967\
-0.36756766& 0.0944919 & 0.4232796 & -0.15020383\
0.04101932& -0.02179989 & -0.06081614 & 0.04159671
\end{bmatrix}\
C&\approx (0.41173294,-0.20486764,0.16954468)^T
\end{aligned}$

28.3-7

这$4$个等式的证明过程如下：

$\begin{aligned}
AA^{+}A&=A((A^TA)^{-1} A^T)A\
&=A(A^TA)^{-1}(A^TA)\
&=A\
\
A^{+}AA^{+}&=((A^TA)^{-1} A^T)AA^+\
&=(A^TA)^{-1} (A^TA)A^+\
&=A^+\
\
(AA^+)^T&=(A((A^TA)^{-1} A^T))^T\
&=(A(A^TA)^{-1} A^T)^T\
&=(A^T)^T((A^TA)^{-1})^T A^T\
&=A((A^TA)^T)^{-1}A^T\
&=A(A^T(A^T)^T)^{-1}A^T\
&=A(A^TA)^{-1}A^T\
&=A((A^TA)^{-1}A^T)\
&=AA^+\
\
(A^+A)^T&=(((A^TA)^{-1} A^T)A)^T\
&=((A^TA)^{-1} (A^TA))^T\
&=I^T\
&=I\
&=(A^TA)^{-1}(A^TA)\
&=((A^TA)^{-1}A^T)A\
&=A^+A
\end{aligned}$