3.9 课后习题

练习3.1 设 $A \in \mathbb{R}^{m \times n}$ , 其中 $m \leq n$ . 试证明: 矩阵 $\left[ \begin{array}{cc} I & A^{\mathsf{T}} \\ A & 0 \end{array} \right]$ 非奇异的充要条件是 $\operatorname{rank}(A) = m$ .

练习3.2设 $B\in \mathbb{R}^{m\times m}$ 对称半正定, $A\in \mathbb{R}^{m\times n}$ , 其中 $m\geq n$ . 试证明: 矩阵 $\left[ \begin{array}{cc}B & A\\ A^{\mathsf{T}} & 0 \end{array} \right]$ 非奇异的充要条件是 $A$ 列满秩且矩阵 $[B,A]$ 行满秩 (即 $A$ 列满秩且 $\mathrm{Ker}(B)\cap \mathrm{Ker}(A^{\mathsf{T}}) = \{0\}$ ).

练习3.3设 $\tau \neq 0$ ，向量 $u,v\in \mathbb{R}^n$ 均不为零,求矩阵 $E(u,v,\tau) = I - \tau uv^{\top}$ 的特征值

练习3.4 (Sylverster 降幂公式(3.4))设 $A\in \mathbb{C}^{m\times n}$ ， $B\in \mathbb{C}^{n\times m}$ ,其中 $m\geq n$ ，则有

(因此 $AB$ 和 $BA$ 具有相同的非零特征值)

练习3.5 设 $A \in \mathbb{R}^{n \times n}$ 是正交矩阵, 则 $A$ 可表示成不超过 $n$ 个Householder变换的乘积

练习3.6设 $G = \left[ \begin{array}{cc}c & s\\ -s & c \end{array} \right]\in \mathbb{R}^{2\times 2}$ 是Givens变换,由练习3.5可知， $G$ 可以表示为2个Householder变换的乘积，试给出这两个Householder变换所对应的Householder向量.

练习3.7设 $x = [x_{1},x_{2},\ldots ,x_{n}]^{\mathsf{T}}\in \mathbb{R}^{n}$ 是一个非零向量, $H$ 是Householder矩阵,满足 $Hx = \alpha e_{1}$ 证明： $H$ 的第一列与 $x$ 平行.

(注: 该结论提供了一种构造指定第一列的正交矩阵或酉矩阵的实用方法)

练习3.8设 $H_{k} = I - \beta_{k}v_{k}v_{k}^{\top}\in \mathbb{R}^{k\times k}$ 是Householder变换,其中 $k < n$

证明: $H_{n} = \left[ \begin{array}{cc}I_{n - k} & 0\\ 0 & H_{k} \end{array} \right]$ 是 $n$ 阶Householder变换,并写出对应的Householder向量.

练习3.9 设 $R = \left[ \begin{array}{cc}r_{11} & r_{12}\\ 0 & r_{22} \end{array} \right]\in \mathbb{R}^{2\times 2}$ ，求一个Givens变换 $G$ ，使得 $G^{\mathsf{T}}RG = \left[ \begin{array}{cc}r_{22} & r_{12}\\ 0 & r_{11} \end{array} \right].$

练习3.10 设 $R \in \mathbb{R}^{n \times n}$ 是一个上三角矩阵, 且对角线元素互不相同. 证明: 存在正交矩阵 $Q$ , 使得 $Q^{\mathrm{T}} R Q$ 为上三角矩阵, 且对角线元素为 $R$ 的对角线元素的降序排列.

(注: 该结论可以看作是练习 3.9 的推广)

练习3.11 利用数学归纳法证明QR分解的存在性

练习3.12 设 $A \in \mathbb{R}^{n \times n}$ , 证明: $\| A \|_2 = \max_{x \neq 0, y \neq 0} \frac{y^\top A x}{\| x \|_2 \| y \|_2}$ .

练习 $3.13^{*}$ 设 $A$ 的奇异值分解为 $A = U_{n}\Sigma V^{*} = \sum_{i = 1}^{n}\sigma_{i}u_{i}v_{i}^{*}\in \mathbb{C}^{m\times n}$ , 证明

其中 $A_{k} = \sum_{i = 1}^{k}\sigma_{i}u_{i}v_{i}^{*}$ .(提示：利用定理3.17)

练习3.14设 $A\in \mathbb{C}^{n\times n}$ 有 $n$ 个互不相同的非零特征值,其Schur分解为 $A = URU^{*}$ ,其中 $U$ 为酉矩阵， $R$ 为上三角矩阵.设矩阵 $B\in \mathbb{C}^{n\times n}$ 满足 $AB = BA.$ 证明： $U^{*}BU$ 是上三角矩阵.

练习3.15 用Householder变换计算矩阵 $A = \begin{bmatrix} 1 & 1 & 1\\ 2 & -1 & -1\\ 2 & -4 & 10 \end{bmatrix}$ 的QR分解.

练习3.16 求解最小二乘问题: $\min \| Ax - b\| _2$ ，其中 $A = \begin{bmatrix} 2 & 0\\ -2 & 3\\ 0 & -1\\ 1 & -2 \end{bmatrix}, b = \begin{bmatrix} 2\\ 0\\ 2\\ 2 \end{bmatrix} .$

练习 $3.17^{*}$ 设 $A\in \mathbb{R}^{m\times n}$ ( $m\geq n$ ) 且 $\operatorname {rank}(A) = n$ 计算矩阵 $\left[ \begin{array}{cc}I & A\\ A^{\mathsf{T}} & 0 \end{array} \right]$ 的谱条件数.(用 $A$ 的奇异值表示)

以下为可选题

练习3.18设 $A = [a_{1},a_{2},\ldots ,a_{n}]\in \mathbb{R}^{m\times n}$ ，下面是另外一种修正Gram-Schmidt正交化过程[57]，试指出与Gram-Schmidt正交化过程的区别.

1: for $i = 1$ to $n$ do
2: $r_{ii} = \| a_i\| _2$
3: $q_{i} = a_{i} / r_{ii}$
4: for $j = i + 1$ to $n$ do
5: $r_{ij} = q_i^\top a_j, \quad a_j = a_j - r_{ij}q_i$
6: end for
7: end for

练习3.19 (Cholesky QR分解)设 $A \in \mathbb{R}^{m \times n}$ ( $m \geq n$ ) 是满秩矩阵, $A^* A$ 的Cholesky分解为 $A^* A = R^\top R$ , 其中 $R \in \mathbb{R}^{n \times n}$ 是对角线元素为正的上三角矩阵. 令 $Q = A R^{-1}$ , 证明: $A = Q R$ 是 $A$ 的QR分解. (试比较Cholesky QR与MGS QR分解的运算量)

练习3.20 设 $A \in \mathbb{R}^{m \times n}$ , 证明: $\operatorname{Ran}(A^{\mathsf{T}}) = \operatorname{Ran}(A^{\mathsf{T}}A)$ .
练习3.21 试证明三类初等矩阵都可以写成(3.3)中的形式.(以第75页上的 $E_{1}, E_{2}, E_{3}$ 为例)
练习3.22 证明定理3.1中的结论(3)，即：

对任意非零向量 $x, y \in \mathbb{C}^n$ , 存在 $u, v \in \mathbb{C}^n$ 和 $\tau \in \mathbb{C}$ , 使得

练习3.23设 $A\in \mathbb{R}^{n\times n}$ 是正交矩阵,则 $A$ 可表示成至多 $\frac{1}{2} n(n - 1)$ 个Givens变换和1个对角线为 $\pm 1$ 的对角矩阵的乘积.(更进一步，该对角矩阵除了最后一个对角线元素是 $\pm 1$ 外，其他对角线元素都是1)

练习 $3.24^{*}$ 试给出定理3.5在复数空间上的相对应的结论, 并证明

练习3.25 证明定理3.13和定理3.14.(奇异值的相关性质)

练习 $3.26^{*}$ 证明奇异值的最小最大定理, 即定理3.18

练习3.27 证明奇异值的扰动性质，即定理3.22.

练习3.28 试给出加权正则化问题(3.31)存在唯一解的充要条件.

练习 $3.29^{*}$ 设 $A \in \mathbb{R}^{n \times n}$ 是一个对角加边矩阵

试给出用Givens变换计算 $A$ 的QR分解的详细算法,使得运算量为 $\mathcal{O}(n^2)$

练习 $3.30^{*}$ 设 $A\in \mathbb{R}^{m\times n}$ $(m\geq n)$ ，如何求解下面的数据拟合问题

练习 $3.31^{*}$ 设 $x = [x_{1}, x_{2}, \ldots, x_{n}]^{\mathsf{T}} \in \mathbb{C}^{n}$ 是一个非零复向量，问：是否存在 Householder 矩阵 $H(v)$ 使得 $H(v)x = \alpha e_{1}$ ？若存在，如何计算 $v$ ？（提示：这里 $\alpha$ 可以是复数）

练习 $3.32^{*}$ 如果矩阵在内存中是按行排列的, 怎么实现 QR 分解比较高效?

练习 $3.33^{*}$ 设 $A \in \mathbb{R}^{m \times n}$ ( $m \geq n$ ), 如果 $A$ 不是满秩的, 如何求解相应的最小二乘问题?

以下为实践题

练习3.34 编写Householder变换函数：对任意给定的变量 $x \in \mathbb{R}^n$ ，输出 $v$ 使得 $H(v)x = \| x\|_2e_1$ 其中 $H(v) = I - 2vv^{\top}$ ，函数原型： $v = \text{House2}(x)$

练习3.35 编写Householder变换函数：对任意给定的变量 $x \in \mathbb{R}^n$ ，输出 $\beta$ 和 $v$ 使得 $H(v)x = \| x\|_2e_1$ ，其中 $H(v) = I - \beta vv^\top$ 且 $v$ 的第一个分量为1. 函数原型：[beta,v] = House3(x)

练习3.36 编写基于Householder变换的QR分解，函数原型：[Q,R]=QR_Householder(A)

练习3.37 设 $A = \begin{bmatrix} R \\ S \end{bmatrix}$ , 其中 $R \in \mathbb{R}^{n \times n}$ 是上三角矩阵, $S \in \mathbb{R}^{m \times n}$ 是稠密矩阵, 试描述 $A$ 的基于Householder变换的QR算法. 要求算法过程中始终保持 $R$ 中的零元.

练习3.38 设 $A = R + uv^{\mathsf{T}}$ , 其中 $R \in \mathbb{R}^{n \times n}$ 是上三角矩阵, $u, v \in \mathbb{R}^n$ 为非零列向量, 试给出计算 $A$ 的QR分解的有效算法. (提示: 使用Givens变换, 算法总运算量大约为 $\mathcal{O}(n^2)$ )

练习3.39 设 $B = A + uv^{\mathsf{T}}$ , 其中 $A \in \mathbb{R}^{n \times n}$ , $u, v \in \mathbb{R}^n$ . 假定 $A$ 的QR分解已知, 试给出计算 $A$ 的QR分解算法.

练习3.40构造并实现列主元QR分解的算法.(选列主元过程中，在计算 $R_{22}^{(k - 1)}$ 各列的范数时，可利用前一步选主元时所计算的范数，这样能减少计算量，可参见[57])

练习3.41构造并实现矩阵的LQ分解算法,即 $A = LQ$ ,其中 $L$ 为下三角矩阵， $Q$ 为正交矩阵