作业6¶

提交截至时间：2022/11/14 周一 12:00（中午）

习题 1. 设 $A = \left[ \begin{array}{c c} {1} & 2 \\ 3 & 4 \\ 5 & 6 \end{array} \right],b={ \left[ \begin{array} { l } { 1 } \\ { 1 } \\ { 1 } \end{array} \right] }$ 用正规化方法求对应的 LS 问题的解。

解. 该 $L S$ 问题的解就是下列正规化方程组的解：

\[ \boldsymbol {A} ^ {T} \boldsymbol {A} \boldsymbol {x} = \boldsymbol {A} ^ {T} \boldsymbol {b} \]

即

\[ \left[ \begin{array}{l l} 3 5 & 4 4 \\ 4 4 & 5 6 \end{array} \right] \left[ \begin{array}{l} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \end{array} \right] = \left[ \begin{array}{l} 9 \\ 1 2 \end{array} \right] \]

解得： $\pmb { x } = ( - 1 , 1 ) ^ { T }$ 对于非满秩的 $A$ ，也可以先行变换后消去多余行再对 $L S$ 问题求解。

习题 2. 设 $A = { \left[ \begin{array} { l l l l } { 1 } & { 3 } & { 1 } & { 1 } \\ { 2 } & { 0 } & { 0 } & { 0 } \\ { 1 } & { 0 } & { 0 } & { 0 } \end{array} \right] } , \ b = { \left[ \begin{array} { l } { 1 } \\ { 1 } \\ { 1 } \end{array} \right] }$ 用任意一种方法求对应的 $L S$ 问题的全部解。

解. 该 $L S$ 问题的解就是下列正规化方程组的解:

\[ \left[ \begin{array}{l l l l} 6 & 3 & 1 & 1 \\ 3 & 9 & 3 & 3 \\ 1 & 3 & 1 & 1 \\ 1 & 3 & 1 & 1 \end{array} \right] \left[ \begin{array}{l} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \\ \boldsymbol {x} _ {3} \\ \boldsymbol {x} _ {4} \end{array} \right] = \left[ \begin{array}{l} 4 \\ 3 \\ 1 \\ 1 \end{array} \right] \]

初等行变换得到同解方程组

\[ \left[ \begin{array}{c c c c} 1 & 3 & 1 & 1 \\ 0 & 1 5 & 5 & 5 \end{array} \right] \left[ \begin{array}{l} x _ {1} \\ x _ {2} \\ x _ {3} \\ x _ {4} \end{array} \right] = \left[ \begin{array}{l} 1 \\ 2 \end{array} \right] \]

从而

\[ \left[ \begin{array}{c c} 1 & 3 \\ 0 & 1 5 \end{array} \right] \left[ \begin{array}{l} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \end{array} \right] = \left[ \begin{array}{c} 1 - \boldsymbol {x} _ {3} - \boldsymbol {x} _ {4} \\ 2 - 5 \boldsymbol {x} _ {3} - 5 \boldsymbol {x} _ {5} \end{array} \right] \]

即

\[ \left[ \begin{array}{c} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \end{array} \right] = \left[ \begin{array}{c} \frac {3}{5} \\ \frac {2}{1 5} - \frac {1}{3} \boldsymbol {x} _ {3} - \frac {1}{3} \boldsymbol {x} _ {4} \end{array} \right] \]

其中 $\mathbf { { x } } _ { 3 } , \mathbf { { x } } _ { 4 } \in R$

习题 3. 设 $ { A } \in \mathbb { R } ^ { m \times n }$ 且存在 $\pmb { X } \in \mathbb { R } ^ { n \times m }$ 使得对每一个 $\pmb { b } \in \mathbb { R } ^ { m } , \pmb { x } = \pmb { X } \pmb { b }$ 均极小化 $\| { \boldsymbol { A } } { \boldsymbol { x } } - { \boldsymbol { b } } \| _ { 2 }$ .证明 $A X A = A$ 和 $( A X ) ^ { T } = A X .$

证明. 由 $\pmb { b }$ 的任意性，取 $\pmb { b }$ 分别为 $\pmb { A }$ 的每一列 $\pmb { a } _ { 1 } , \pmb { a } _ { 2 } , \cdots , \pmb { a } _ { n }$ ，则显然，若 $x$ 极小化 $\| A x - \pmb { a } _ { i } \| _ { 2 }$ ，$\boldsymbol { x }$ 可以取第 $i$ 个元素为 1，其余元素为 0 的向量, 因此 $X$ 使得 $\mathbf { \pmb { x } } = \pmb { X } \pmb { a } _ { i }$ 最小化的 $\| A X \pmb { a } _ { i } - \pmb { a } _ { i } \| _ { 2 } = 0$ ，这样 $A X \pmb { a } _ { i } = \pmb { a } _ { i }$ ，即 $A X A = A$

因为对每一个 $\pmb { b } \in \mathbb { R } ^ { m } , \pmb { x } = \pmb { X } \pmb { b }$ 均极小化 $\| { \pmb { A } } { \pmb { x } } - { \pmb { b } } \| _ { 2 }$ 。有 $\pmb { A } ^ { \mathrm { T } } \pmb { A } \pmb { X } \pmb { b } = \pmb { A } ^ { \mathrm { T } } \pmb { b }$ 。

由于 $\pmb { b }$ 的任意性，有 $\pmb { A } ^ { \mathrm { T } } \pmb { A } \pmb { X } = \pmb { A } ^ { \mathrm { T } }$ ，等式两边同时乘以 $X ^ { \mathrm { { T } } }$ ，有

\[ \boldsymbol {X} ^ {\mathrm {T}} \boldsymbol {A} ^ {\mathrm {T}} \boldsymbol {A} \boldsymbol {X} = \boldsymbol {X} ^ {\mathrm {T}} \boldsymbol {A} ^ {\mathrm {T}} \]

即

\[ (\boldsymbol {A} \boldsymbol {X}) ^ {\mathrm {T}} (\boldsymbol {A} \boldsymbol {X}) = (\boldsymbol {A} \boldsymbol {X}) ^ {\mathrm {T}} \]

所以

\[ \boldsymbol {A} \boldsymbol {X} = (\boldsymbol {A} \boldsymbol {X}) ^ {\mathrm {T}} (\boldsymbol {A} \boldsymbol {X}) = (\boldsymbol {A} \boldsymbol {X}) ^ {\mathrm {T}} \]

证毕。

习题 4. 利用等式

\[ \left\| \boldsymbol {A} (\boldsymbol {x} + \alpha \boldsymbol {w}) - \boldsymbol {b} \right\| _ {2} ^ {2} = \left\| \boldsymbol {A x} - \boldsymbol {b} \right\| _ {2} ^ {2} + 2 \alpha \boldsymbol {w} ^ {T} \boldsymbol {A} ^ {T} (\boldsymbol {A x} - \boldsymbol {b}) + \alpha^ {2} \| \boldsymbol {A w} \| _ {2} ^ {2} \]

证明：如果 $\pmb { x } \in { \pmb X } _ { L S }$ ,那么 $\pmb { A } ^ { T } \pmb { A } \pmb { x } = \pmb { A } ^ { T } \pmb { b }$

解. 设 $f ( \alpha ) = \| A ( \pmb { x } + \alpha \pmb { w } ) - \pmb { b } \| _ { 2 } ^ { 2 }$ ，由于 $\pmb { x } \in { \pmb { X } } _ { L S }$ ，说明当 $\alpha = 0$ 时，函数取极小点。由于 $f$ 是关于 $\alpha$ 的二次函数，故在 $\begin{array} { r } { \alpha = - \frac { 2 w ^ { T } A ^ { T } ( A x - b ) } { 2 \alpha ^ { 2 }\| \left. A w \|\right. _ { 2 } ^ { 2 } } } \end{array}$ 取得极值点。代入 $\alpha = 0$ ，有

\[ \boldsymbol {w} ^ {T} \boldsymbol {A} ^ {T} (\boldsymbol {A} \boldsymbol {x} - \boldsymbol {b}) = 0 \]

又由于 $\pmb { w }$ 的任意性，有

$$ \boldsymbol {A} ^ {T} \boldsymbol {A} \boldsymbol {x} = \boldsymbol {A} ^ {T} \boldsymbol {b} $$ 习题 5.

\[ A := \left( \begin{array}{c c c} 5 & - 1 & 1 \\ - 1 & 2 & 0 \\ 1 & 0 & 3 \end{array} \right) \]

记 $\Lambda ( A ) = \{ \lambda _ { 1 } , \lambda _ { 2 } , \lambda _ { 3 } \} \subseteq \mathbb { C }$ with $| \lambda _ { 1 } | \geq | \lambda _ { 2 } | \geq | \lambda _ { 3 } | .$

(i) 使用 Gerschgorin 圆盘定理, 证明 ${ \frac { \left| \lambda _ { 1 } \right| } { \left| \lambda _ { 3 } \right| } } \leq 7 .$（注：由于 $A$ 为对称矩阵， $\frac { \left| \lambda _ { 1 } \right| } { \left| \lambda _ { 3 } \right| }$ 为 $A$ 的条件数）

(ii)（编程题，提交代码）使用幂法与反幂法计算 $\frac { \left| \lambda _ { 1 } \right| } { \left| \lambda _ { 3 } \right| }$

解. $( i )$ 令 $a \in \mathbb { C }$ , $r \in \mathbb { R }$ , $r > 0$ , 记 $D ( a , r ) : = \{ z \in \mathbb { C } : | z - a | \leq r \} \subseteq \mathbb { C } .$ . 对 $A$ 和 $A ^ { \mathrm { T } }$ 使用 Gerschgorin 圆盘定理，有 $\Lambda ( A ) = \Lambda \left( A ^ { \mathrm { T } } \right) \subseteq { \tilde { G } } _ { 1 } \cup { \tilde { G } } _ { 2 } \cup { \tilde { G } } _ { 3 }$ ，其中

\[ \tilde {G} _ {1} := D (5, 2), \tilde {G} _ {2} := D (2, 1), \tilde {G} _ {3} := D (3, 1) \]

可得 $| \lambda _ { 1 } | \le 7$ , $| \lambda _ { 3 } | \geq 1 .$ . 故 $\frac { \left| \lambda _ { 1 } \right| } { \left| \lambda _ { 3 } \right| } \le 7$ .

$(i i) \frac {| \lambda_ {1} |}{| \lambda_ {3} |} \approx 3. 4 8 2 3$