算法导论28.3 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

28.3-1

构造\(n\)维单位向量\(e_i=(0,0,\dots,1,0,\dots,0)\)，即\(e_i\)的第\(i\)个值为\(1\)，其余值为\(0\)。可见\(e_i\)是一个非零向量。那么可以得到\(e_i^TAe_i=a_{ii}\)。由于\(A\)是一个正定矩阵，\(e_i\)是一个非零向量，因此\(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_{i_2},\dots,x_{i_k}\)这些变量，因此可以重新构建出一个从\(A\)的第\(i_1,i_2,\dots,i_k\)行和列构成的主子矩阵\(A'\)。

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

28.3-5

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

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

由于LU分解的过程是对矩阵\(A\)进行高斯消元，即对\(A\)进行行变换；此外，由于高斯消元的过程只对下面的行进行消元；而不会使用下面的行对上面的行进行行变换操作，因此顺序主子式\(A_1,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}\)的结果大约为：

1
2
3
4
5
6
7
8
9
10
11
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}\)