跳转至

作业13

提交截至时间：暂定 2022/04/23 下周五 20: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} \]