高代习题选解|最速下降法的收敛速度

问题背景

解线性方程组

在  （其中  表示矩阵  的第  列向量）时，整个问题可以看作求解最小二乘问题

当  对称正定时，该最小二乘问题的解恰为优化问题

的解

记号约定：

其中  为优化问题的最优解

下面的讨论全部针对优化问题的求解

在这个意义下， 

关于最速下降收敛速度证明

定理 Denote the eigenvalues of  be  , then the error inequality of sequence  generated by the steepest descent method holds

where  , 

证明 先证明一个引理：

引理 Denote the eigenvalues of  be  , and  be polynomial, then

引理之证明 由于  对称正定，存在正定阵  ，对角阵 满足 ，记 

已知等式等价于

即

（上式用到了多项式中  ）

代入  有

整理得

即

由  的定义   知  ，又由  正定知  ，上式显然成立，从而引理得证！

回到原定理，只需证明

由最速下降法迭代式

其中

则

即原不等式等价于

由  得

从而

令  由引理

考察直线  的图像，当直线过  时取 

从而

进而命题得证！

注 由于

代入  并取最小值得

注 由条件数的定义

原定理还能写成

参考资料

本文整理自数值线性代数课程笔记，感谢老师的答疑。