高代习题选解|最小二乘问题

在开始今天的文章之前，先补充一下关于周三发的那篇高代习题选解|可约矩阵与行/列对角占优的推论和下面那个定理的证明：

定理 The matrix  is nonsingular if  is row-wise strictly (or irreducible) diagonally dominant.

推论 The symmetric matrix  is positive definite if  is row-wise strictly (or irreducible) diagonally dominant and main diagonal entries 

推论之证明 反证法，设不是正定阵，由为实对称阵知必存在非正特征值，设为，考虑，一方面，由特征值性质知奇异，另一方面，当对角占优或不可约对角占优时必然对角占优或不可约对角占优，由前面的定理知非奇异，矛盾，从而推论得证！

定理 Both Jacobi and Gauss-Seidel methods are convergent if  is row-wise strictly (or irreducible) diagonally dominant

定理之证明 考虑Jacobi迭代矩阵和Gauss-Seidel矩阵

采用反证法，假设存在特征值，则奇异，而

易知非奇异，严格对角占优或不可约对角占优，由前面那个定理知必非奇异，从而非奇异，矛盾！

同理可证，这里不再赘述。

今天的小定理

定义 （最小二乘问题） Given a matrix  and a vector , find a vector  such that  is minimized.

从几何上看，求可以看作求到超平面的距离，这里距离用2范数刻画。

定理 The solution of

always exists, and the necessary and sufficient condition for uniquness is 

既然想到了距离，那就不妨进行正交分解，将拆成在上的投影分量和垂直分量。

证明 记为的列向量张成的子空间，为的正交补空间，则存在和，满足

代入得

由于，故总存在满足，因此等号成立。

唯一性的充要条件：

假设存在满足

则

也即

从而，这表明解唯一等价于，定理得证。

定义 Let the solution set of the least square problem be 

定理 The necessary and sufficient condition for  is 

还是采用上面直和分解的思路

证明 由于

且

即

只需证明

即可，而由，上式显然成立，从而命题得证。