超定线性方程组的最小二乘法解

贡献者： addis

预备知识　最小二乘法

　　¹令 $ \boldsymbol{\mathbf{A}} $ 为 $M\times N$ 的复数矩阵，$ \boldsymbol{\mathbf{x}} $ 和 $ \boldsymbol{\mathbf{y}} $ 为复数列矢量，当 $M > N$ 时，以下线性方程组称为超定方程组（overdetermined system）

\begin{equation} \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} ~. \end{equation}

　　我们把 $ \boldsymbol{\mathbf{y}} $ 和 $ \boldsymbol{\mathbf{A}} $ 拼接成一个 $M\times(N+1)$ 的矩阵，当这个矩阵的 $M$ 个行矢量中只有小于或等于 $N$ 个线性无关时，我们只需取所有线性无关的行即可得到非超定的线性方程组。举一个简单的例子，如果第 2 条方程（第 2 行）是第 1 条方程（第 1 行）乘以常数，那么这两条方程中我们只需保留一条即可。

　　如果有大于 $N$ 个线性无关的行（由于每行只有 $N+1$ 个元，那么最多只可能有 $N+1$ 个线性无关的行），那么超定方程无解。

未完成：为什么？

未完成：以下似乎应该移动到最小二乘法中

但我们仍然可以寻找一个最优的 $ \boldsymbol{\mathbf{x}} $，使以下误差函数取最小值

\begin{equation} \left\lVert \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} - \boldsymbol{\mathbf{y}} \right\rVert ^2 = \sum_k \left\lvert \sum_j A_{kj} x_j - y_k \right\rvert ^2~, \end{equation}

　　所以这是一个最小二乘法问题。令误差函数分别对每个 $x_i$ 的实部和虚部分别求导等于 0，得

\begin{equation} \sum_j \left(\sum_i A ^\dagger _{ik} A_{kj} \right) x_j = \sum_k A ^\dagger _{ik} y_k~. \end{equation}

即

\begin{equation} ( \boldsymbol{\mathbf{A}} ^\dagger \boldsymbol{\mathbf{A}} ) \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{A}} ^\dagger \boldsymbol{\mathbf{y}} ~. \end{equation}

定理 1　

　　当 $ \boldsymbol{\mathbf{A}} $ 的各列线性无关时，式 4 必有唯一解。

　　证明：对 $ \boldsymbol{\mathbf{A}} $ 做列变换不会改变行列式 $ \left\lvert \boldsymbol{\mathbf{A}} ^\dagger \boldsymbol{\mathbf{A}} \right\rvert $ 的值（对 $ \boldsymbol{\mathbf{A}} $ 做行变换或对 $ \boldsymbol{\mathbf{B}} $ 做列变换分别相当于对 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{B}} $ 做相同的行变换或列变换）。所以可以通过列变换使 $ \boldsymbol{\mathbf{A}} $ 的各列正交且非零，于是 $ \boldsymbol{\mathbf{A}} ^\dagger \boldsymbol{\mathbf{A}} $ 变为对角矩阵，且对角元都大于零，所以行列式也大于零。证毕。

　　对比式 1 可以发现式 4 只是在左右两侧同时乘以 $ \boldsymbol{\mathbf{A}} $ 的厄米共轭。所以任何能满足式 1 的解也可以通过式 4 解得。

1. ^ 参考 Wikipedia 相关页面。