3¶

习题1

证明上三角矩阵与上三角矩阵的乘积仍是上三角矩阵。

解 (上三角矩阵的元素中,当坐标行序号大于列序号时该元素为0。) 假设A, B为上三角矩阵,且其乘积为C。下证C为上三角矩阵,只需证 \(C_{ij},(i>j)\) 时为0。易知,

\[C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj}=\sum_{k=1}^{j}A_{ik}B_{kj}+\sum_{k=j+1}^{n}A_{ik}B_{kj}\]

因为A, B为上三角矩阵,所以右边第一项中 \(A_{ik}=0,i>j>=k\),右边第二项中 \(B_{kj}=0,k>j\)。故得证。

习题2

判定矩阵

\[A=\begin{bmatrix}3&2&-1\\ -1&0&0\\ -1&3&0\end{bmatrix} B=\begin{bmatrix}0&2&-1\\ -1&4&-1\\ 1&3&-5\end{bmatrix}\]

能否进行LU 分解,为什么?

解

A 可以, \(|A_{1}|=3\ne0\), \(|A_{2}|=2\ne0\),前n-1阶顺序主子式均不为0

B 不可以, \(|B_{1}|=0\) 0,1阶顺序主子式为0

习题3

对下列矩阵进行LU分解:

\[A=\begin{bmatrix}2&1&1\\ 1&3&2\\ 1&2&2\end{bmatrix} \quad B=\begin{bmatrix}12&-3&3\\ -18&3&-1\\ 1&1&1\end{bmatrix} \quad C=\begin{bmatrix}2&1&1\\ 1&2&1\\ 1&1&0\end{bmatrix}\]

\[D=\begin{bmatrix}5&3&-1&3\\ 0&1&1&-2\\ -5&-3&4&-4\\ 0&1&1&0\end{bmatrix}\]

解

\[A=\begin{bmatrix}1&0&0\\ \frac{1}{2}&1&0\\ \frac{1}{2}&\frac{3}{5}&1\end{bmatrix}\begin{bmatrix}2&1&1\\ 0&\frac{5}{2}&\frac{3}{2}\\ 0&0&\frac{3}{5}\end{bmatrix} \quad B=\begin{bmatrix}1&0&0\\ -\frac{3}{2}&1&0\\ \frac{1}{12}&-\frac{5}{6}&1\end{bmatrix}\begin{bmatrix}12&-3&3\\ 0&-\frac{3}{2}&\frac{7}{2}\\ 0&0&\frac{11}{3}\end{bmatrix}\]

\[C=\begin{bmatrix}1&0&0\\ \frac{1}{2}&1&0\\ \frac{1}{2}&\frac{1}{3}&1\end{bmatrix}\begin{bmatrix}2&1&1\\ 0&\frac{3}{2}&\frac{1}{2}\\ 0&0&-\frac{2}{3}\end{bmatrix} \quad D=\begin{pmatrix}1&0&0&0\\ 0&1&0&0\\ -1&0&1&0\\ 0&1&0&1\end{pmatrix}\begin{pmatrix}5&3&-1&3\\ 0&1&1&-2\\ 0&0&3&-1\\ 0&0&0&2\end{pmatrix}\]

习题4

利用 LU 分解来求解方程

\[\begin{pmatrix}5&3&-1&3\\ 0&1&1&-2\\ -5&-3&4&-4\\ 0&1&1&0\end{pmatrix}\begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{pmatrix}=\begin{pmatrix}0\\ 2\\ 0\\ 1\end{pmatrix}\]

解由题3已得到方程左边矩阵对应的LU分解,将方程记作 \(LUx=b\) 令 \(y=Ux\),则先求解

\[Ly=b\]

(注,因为L是下三角矩阵,可以对该线性方程自上而下求解) 得到

\[y=\begin{pmatrix}0\\ 2\\ 0\\ -1\end{pmatrix},\]

再求解

\[Ux=y\]

(注,因为U是上三角矩阵,可以对该线性方程自下而上求解) 得到

\[x=\begin{pmatrix}-13/30\\ 7/6\\ -1/6\\ -1/2\end{pmatrix}.\]

习题5 完成以下材料阅读即可

· 为什么需要LU分解?

为什么不直接求解方程组 \(Ax=b\)? 如果了解LU分解所需要的计算量与高斯消去法解方程组所需的计算量,便可知计算复杂度均为 \(O(n^{3})\)。似乎LU分解并没有任何优势。然而,在实际的工程问题中,我们经常会遇到的是这样的问题,需要求解这样一系列的方程组(例如时序的):

\[Ax=b_{1}, Ax=b_{2},\cdot\cdot\cdot Ax=b_{r}.\]

其中的系数矩阵是不变的,只是右边的常数项在改变。这时,如果直接使用高斯消去法求解各个方程组的话,则对应的计算复杂度为 \(O(rn^{3})\)。若使用LU分解,则只需要的运算量级为 \(O(n^{3}+rn^{2})\),这是因为LU 分解在解方程组时只需要 \(O(n^{2})\)。

或许,你会提出直接计算出 \(A^{-1}\),然后再利用它去求解各个方程组。这时所需要的计算量的效果似乎与LU 分解是相似的。事实上,在实际计算中往往不会直接计算矩阵的逆。这里给出其中一个原因:通常实际工程中矩阵A的维度很大,但有一个优点是它是稀疏的,例如一个“带状的”矩阵。使用LU分解,可以保持矩阵的稀疏性(因此,还可以提高运算速度)。然而,直接求解矩阵的逆,则会丢失矩阵的稀疏性。因此,在数据的存储上直接求逆存在明显的劣势。

· Gauss消去与LU分解

假设我们有如下二元一次方程组

\[\begin{cases}2x_{1}+4x_{2}=5\\ 4x_{1}+5x_{2}=3\end{cases}\]

现在我们考虑方程组的求解。在中学时,我们会通过将第一个等式乘以-2加到第二个等式,则得到

\[\begin{cases}2x_{1}+4x_{2}=5\\ 0x_{1}-3x_{2}=-7\end{cases}\]

这个行变换对应的矩阵为 \(\begin{pmatrix}1&0\\ -2&1\end{pmatrix}\) 它的逆矩阵就是 \(\begin{pmatrix}1&0\\ 2&1\end{pmatrix}\)。另外,变换后的系数矩阵为 \(\begin{pmatrix}2&4\\ 0&-3\end{pmatrix}\)。如果我们使用 LU分解,则可得到

\[\begin{pmatrix}2&4\\ 4&5\end{pmatrix}=\begin{pmatrix}1&0\\ 2&1\end{pmatrix}\begin{pmatrix}2&4\\ 0&-3\end{pmatrix}\]

从上可以看出,高斯消去的变换矩阵的逆恰好对应LU分解的L矩阵,变换后的系数矩阵恰好对应U矩阵。

习题6

用Householder 方法求矩阵

\[A=\begin{bmatrix}1&1\\ 2&0\\ 2&1\end{bmatrix}\]

的QR分解。

解令 \(\alpha_{1}=(1,2,2)^{T},a_{1}=||\alpha_{1}||_{2}=3\) 则

\[w_{1}=\frac{\alpha_{1}-a_{1}e_{1}}{||\alpha_{1}-a_{1}e_{1}||_{2}}=\frac{1}{2\sqrt{3}}(-2,2,2)^{T}\]

故有

\[H_{1}=I-2w_{1}w_{1}^{T}=\begin{bmatrix}1/3&2/3&2/3\\ 2/3&1/3&-2/3\\ 2/3&-2/3&1/3\end{bmatrix}\]

此时

\[H_{1}A=\begin{bmatrix}3&1\\ 0&0\\ 0&1\end{bmatrix}\]

再令 \(\beta_{1}=(0,1)^{T}\), \(b_{1}=||\beta_{1}||_{2}=1\) 则

\[w_{2}=\frac{\beta_{1}-b_{1}e_{1}}{||\beta_{1}-b_{1}e_{1}||_{2}}=\frac{1}{\sqrt{2}}(-1,1)^{T}\]

故有

\[\hat{H}_{2}=I-2w_{2}w_{2}^{T}=\begin{bmatrix}0&1\\ 1&0\end{bmatrix}\]

记

\[H_{2}=\begin{bmatrix}1&0&0\\ 0&0&1\\ 0&1&0\end{bmatrix}\]

此时

\[H_{2}H_{1}A=\begin{bmatrix}3&1\\ 0&1\\ 0&0\end{bmatrix}\triangleq R\]

因此 \(A=QR\),其中 \(Q=H_{1}H_{2}=\frac{1}{3}\begin{bmatrix}1&2&2\\ 2&-2&1\\ 2&1&-2\end{bmatrix}\)

习题7

求下列矩阵的正交三角（\(QR\)）分解：

\[ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 1 & \frac{1}{2} & 5 \\ 1 & -\frac{1}{2} & 2 \\ -1 & \frac{1}{2} & -2 \\ 1 & -\frac{3}{2} & 0 \end{bmatrix} \]

解¶

\[ A = \begin{bmatrix} 0 & \frac{\sqrt{6}}{3} & \frac{\sqrt{3}}{3} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{6}}{6} & -\frac{\sqrt{3}}{3} \\ \frac{\sqrt{2}}{2} & -\frac{\sqrt{6}}{6} & \frac{\sqrt{3}}{3} \end{bmatrix} \begin{bmatrix} \sqrt{2} & \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \\ 0 & \frac{\sqrt{6}}{2} & \frac{\sqrt{6}}{6} \\ 0 & 0 & \frac{2\sqrt{3}}{3} \end{bmatrix}, \quad B = \begin{bmatrix} \frac{1}{2} & \frac{\sqrt{2}}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & -\frac{1}{2} & -\frac{\sqrt{2}}{2} \\ -\frac{1}{2} & 0 & \frac{1}{2} & -\frac{\sqrt{2}}{2} \\ \frac{1}{2} & -\frac{\sqrt{2}}{2} & \frac{1}{2} & 0 \end{bmatrix} \begin{bmatrix} 2 & -1 & \frac{9}{2} \\ 0 & \sqrt{2} & \frac{5\sqrt{2}}{2} \\ 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 \end{bmatrix} \]

习题8

求下列对称正定矩阵的Cholesky 分解。

\[A=\begin{bmatrix}5&2&-4\\ 2&1&-2\\ -4&-2&5\end{bmatrix} \quad B=\begin{bmatrix}25&15&-5\\ 15&18&0\\ -5&0&11\end{bmatrix}\]

解 \(g_{11}=\sqrt{a_{11}}=\sqrt{5}\) \(,g_{22}=\sqrt{a_{22}-g_{21}^{2}}=\frac{\sqrt{5}}{5},g_{33}=\sqrt{a_{33}-g_{31}^{2}-g_{32}^{2}}=1\)

\(g_{21}=\frac{a_{21}}{g_{11}}=\frac{2\sqrt{5}}{5}\), \(g_{31}=\frac{a_{31}}{g_{11}}=-\frac{4\sqrt{5}}{5}\) \(g_{32}=\frac{a_{32}-g_{31}g_{21}}{g_{22}}=-\frac{2\sqrt{5}}{5}\)

易求得 \(G=\begin{bmatrix}\sqrt{5}&0&0\\ \frac{2\sqrt{5}}{5}&\frac{\sqrt{5}}{5}&0\\ -\frac{4\sqrt{5}}{5}&-\frac{2\sqrt{5}}{5}&1\end{bmatrix}\) 则有 \(A=GG^{T}\)

\(B\) 有相同的计算过程

\[G=\begin{bmatrix}5&0&0\\ 3&3&0\\ -1&1&3\end{bmatrix}\]

习题9

定义

\[A=\begin{pmatrix}2&-2&1\\ -1&1&-1\\ -3&-1&1\end{pmatrix}\]

(i) 给出矩阵 \(A^{T}A\) 的Cholesky 分解 \(A^{T}A=GG^{T}\) (ii) 试说明 \(||A^{T}A||_{2}=||A||_{2}^{2}=||G||_{2}^{2}\)

解 (i) 记

\[M=A^{T}A=\begin{pmatrix}14&-2&0\\ -2&6&-4\\ 0&-4&3\end{pmatrix}\]

消除M的第一列中的对角线条目

\[L_{1}M=\begin{pmatrix}\sqrt{14}&-\frac{2}{\sqrt{14}}&0\\ 0&\frac{40}{7}&-4\\ 0&-4&3\end{pmatrix}\]

\[L_{1}=\begin{pmatrix}\frac{1}{\sqrt{14}}&0&0\\ \frac{1}{7}&1&0\\ 0&0&1\end{pmatrix}\]

\(L_{1}M\) 右乘 \(L_{1}^{T}\)

\[L_{1}ML_{1}^{T}=\begin{pmatrix}1&0&0\\ 0&\frac{40}{7}&-4\\ 0&-4&3\end{pmatrix}\]

消除 \(L_{1}ML_{1}^{T}\) 的第二列中的对角线条目

\[ L_{2}L_{1}ML_{1}^{T}=\begin{pmatrix} 1 & 0 & 0 \\ 0 & \dfrac{2\sqrt{70}}{7} & -\dfrac{\sqrt{70}}{5} \\ 0 & 0 & \dfrac{1}{5} \end{pmatrix} \]

\[L_{2}=\begin{pmatrix}1&0&0\\ 0&\frac{\sqrt{70}}{20}&0\\ 0&\frac{7}{10}&1\end{pmatrix}\]

\(L_{1}M\) 右乘 \(L_{2}L_{1}ML_{1}^{T}L_{2}^{T}\)

\[L_{2}L_{1}ML_{1}^{T}L_{2}^{T}=\text{diag}_{3\times3}(1,1,\frac{1}{5})\]

令 \(L_{3}:=\text{diag}_{3\times3}(1,1,\sqrt{5})\) 使得 \(L_{3}L_{2}L_{1}ML_{1}^{T}L_{2}^{T}L_{3}^{T}=I_{3}\)。我们有 \(M=A^{T}A=GG^{T}\) 其中

\[G=L_{1}^{-1}L_{2}^{-1}L_{3}^{-1}=\begin{pmatrix}\sqrt{14}&0&0\\ -\frac{\sqrt{14}}{7}&\frac{2\sqrt{70}}{7}&0\\ 0&-\frac{\sqrt{70}}{5}&\frac{\sqrt{5}}{5}\end{pmatrix}\]

(注:或者按题9答案给出分解方式进行分解)

(ii) \(G=U\Sigma V^{T}\),其中 \(U,V\in\mathbb{R}^{n\times n}\) 正交, \(\Sigma=\text{diag}_{n\times n}(\sigma_{1},...,\sigma_{n})\in\mathbb{R}^{n\times n}\) 且 \(\sigma_{1}\ge\sigma_{2}\ge\cdot\cdot\cdot\ge\sigma_{n}\ge0\) 故 \(A^{T}A=GG^{T}=U\Sigma V^{T}V\Sigma U^{T}=U\Sigma^{2}U^{T}\), \(A^{T}A\) 的奇异值为 \(\sigma_{1}^{2},...,\sigma_{n}^{2}\) 因此 \(||A^{T}A||_{2}=\sigma_{1}^{2}=||G||_{2}^{2}\) 同样的,我们可以得出 \(||A^{T}A||_{2}=||A||_{2}^{2}\)

习题10

求下列矩阵的奇异值(SVD) 分解:

\[A=\begin{bmatrix}1&0&0&-1\\ 0&1&0&0\\ 0&1&0&0\end{bmatrix} , B=\begin{bmatrix}1&0\\ 0&1\\ 1&1\end{bmatrix} , C=\begin{bmatrix}2&0&1\\ 1&2&0\end{bmatrix}\]

解

\[A=\begin{bmatrix}1&0&0\\ 0&\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\ 0&\frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2}\end{bmatrix}\begin{bmatrix}\sqrt{2}&0&0&0\\ 0&\sqrt{2}&0&0\\ 0&0&0&0\end{bmatrix}\begin{bmatrix}\frac{\sqrt{2}}{2}&0&0&-\frac{\sqrt{2}}{2}\\ 0&1&0&0 \\ \frac{\sqrt{2}}{2}&0&0&\frac{\sqrt{2}}{2}\\0&0&1&0\end{bmatrix}\]

\[B=\begin{bmatrix}\frac{\sqrt{6}}{6}&\frac{\sqrt{2}}{2}&\frac{\sqrt{3}}{3}\\ \frac{\sqrt{6}}{6}&-\frac{\sqrt{2}}{2}&\frac{\sqrt{3}}{3}\\ \frac{\sqrt{6}}{3}&0&-\frac{\sqrt{3}}{3}\end{bmatrix}\begin{bmatrix}\sqrt{3}&0\\ 0&1\\ 0&0\end{bmatrix}\begin{bmatrix}\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}&-\frac{\sqrt{2}}{2}\end{bmatrix}\]

\[C=\begin{bmatrix}\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}&-\frac{\sqrt{2}}{2}\end{bmatrix}\begin{bmatrix}\sqrt{7}&0&0\\ 0&\sqrt{3}&0\end{bmatrix}\begin{bmatrix}\frac{3\sqrt{14}}{14}&\frac{\sqrt{14}}{7}&\frac{\sqrt{14}}{14}\\ \frac{\sqrt{6}}{6}&-\frac{\sqrt{6}}{6}&\frac{\sqrt{6}}{6}\\ \frac{2\sqrt{21}}{21}&-\frac{\sqrt{21}}{21}&-\frac{4\sqrt{21}}{21}\end{bmatrix}\]

习题11

(i) 假设A可逆,根据A的SVD结果给出 \(A^{-1}\) 的SVD分解(提示: \(Av_{i}=\sigma_{i}u_{i}\forall i\in \{1,...,n\}\))

(ii) 假设Q是正交阵,给出Q的SVD 分解及其奇异值

(iii) 假设 \(A=QBQ^{T}\),其中Q是正交阵,说明A和B有相同奇异值

解 (i) 记A的SVD 分解为

\[A=U\Sigma V^{T}=(u_{1}|\cdot\cdot\cdot|u_{n})[\text{diag}_{n\times n}(\sigma_{1},...,\sigma_{n})](v_{1}|\cdot\cdot\cdot|v_{n})^{T}\]

其中 \(U,V\in\mathbb{R}^{n\times n}\) 正交, \(\sigma_{1}\ge\sigma_{2}\ge\cdot\cdot\cdot\ge\sigma_{n}\ge0\) 因为A可逆,有 \(\text{rank}(A)=n,\sigma_{i}>0,\forall i\in\{1,...,n\}\)。又由 \(A=U\Sigma V^{T}\) 有 \(Av_{i}=\sigma_{i}u_{i}\forall i\in\{1,...,n\}\),因此

\[A^{-1}u_{i}=A^{-1}(\frac{1}{\sigma_{i}}Av_{i})=\frac{1}{\sigma_{i}}v_{i}\]

其中 \(\frac{1}{\sigma_{n}}\ge\cdot\cdot\cdot\ge\frac{1}{\sigma_{2}}\ge\frac{1}{\sigma_{1}}>0\) 故

\[A^{-1}=(v_{n}|\cdot\cdot\cdot|v_{2}|v_{1})[\text{diag}_{n\times n}(\frac{1}{\sigma_{n}},...,\frac{1}{\sigma_{2}},\frac{1}{\sigma_{1}})](u_{n}|\cdot\cdot\cdot|u_{2}|u_{1})^{T}=(VP)(P\Sigma^{-1}P)(UP)^{T}\]

记

\[P:=(e_{n}|\cdot\cdot\cdot|e_{2}|e_{1})\in\mathbb{R}^{n\times n}\]

(由于 \(PP^{T}=P^{2}=I_{n},\) P是正交阵,且 \(VP,UP\) 是正交阵.)

(ii) 由于 \(Q\in\mathbb{R}^{n\times n}\) 正交, \(Q=QI_{n}I_{n}^{T}\) 即Q的SVD分解显然,所有奇异值为1

(iii) 记B的SVD分解为 \(B=U\Sigma V^{T}\),则 \(A=QBQ^{T}=QU\Sigma V^{T}Q^{T}=(QU)\Sigma(QV)^{T}\)

显然A和B有相同奇异值。