310梯度法与共轭梯度法解析课件

§3.10共轭梯度法一、与方程组等价的二次泛函问题思想共轭梯度法将求解方程组问题等价转化为一个二次泛函的极值问题。

定义二次函数设为对称正定矩阵，其中§3.10共轭梯度法一、与方程组等价的二次泛函问题思想共1二次函数的基本性质：对对有为的解的充要条件是证明：必要性:二次函数的基本性质：对对2该性质说明：求解方程组的解等价于求上述二次函数的最小值。如果则由极值的必要条件得充分性:迭代法构造思想：构造使得该性质说明：求解方程组的解等价于求上述如果则由极值的必要条件3二、最速下降法几何意义：等值线思想最速下降法是指每次沿着函数值下降最快的方向寻找最小值点。

而函数值下降最快的方向是函数的负梯度方向二、最速下降法几何意义：等值线思想最速下降法是指每次沿着函4最速下降法实现过程：选取初始向量，由二次函数的基本性质如果，则就是方程组的解；如果，则沿方向进行一维极小搜索：求使得达到最小值,则最速下降法实现过程：选取初始向量，由二次函5注意到令，从而完成第一次迭代。下面以为新的初值，重复上述过程。注意到令6最速下降法的算法:选取初值Fork=0,1,2,…如果，停止否则，进行下一次循环搜索方向是正交的：缺陷：收敛速度慢！收敛速度？？？？？最速下降法的算法:选取初值Fork=0,1,2,…如果7设的特征值为,则由前述最速下降算法产生的序列满足其中。上述定理说明，当时最速下降法收敛非常慢。设的特征值为,则由83、共轭梯度法/*Conjugate-GradientMethod*/共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中，已经成为求解大型稀疏线性方程组最受欢迎的一类方法。

3、共轭梯度法/*Conjugate-GradientMe9设为对称正定矩阵，其中思想设为对称正定矩阵，若中向量组满足则称它是中的一个共轭（正交）向量组。利用一维极小搜索方法确定一组共轭方向代替最速下降法中的正交方向来进行迭代。设10选取初始向量，共轭梯度法如何确定下一个搜索方向呢？选取初始向量，11共轭梯度法的实现过程选取初始向量，，如何确定下一个搜索方向呢？由过点向量和所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向共轭梯度法的实现过程选取初始向量，12、和的几何意义此时在上可表示为、和的几何意义此时在13由极值的必要条件得其中满足由极值的必要条件得其中满足14取下一个搜索方向为沿该方向进行一维搜索得步长为记下面以为新的迭代值，重复上述过程即可取下一个搜索方向为沿该方向进行一维搜索得步长为记下面以15一般地，设已经得到，则第k+1步迭代的计算公式为终止条件：一般地，设已经得到，则第k+1步迭代的计算公式为16算法简化：算法简化：17310梯度法与共轭梯度法解析课件18共轭梯度法的算法选取初值Fork=0,1,2,…,n计算计算如果，停止否则，计算进行下一次迭代共轭梯度法的算法选取初值Fork=0,1,2,19由共轭梯度法得到的满足性质：Krylov(克雷洛夫)子空间由共轭梯度法得到的满足性质：Kr20由共轭梯度法计算得到的近似解满足或由共轭梯度法计算得到的近似解满足或21解：易验证系数矩阵是对称正定的.例：用CG迭代法求解下列方程组:3xStep1计算解：易验证系数矩阵是对称正定的.例：用CG迭代法求解下列方程22Step2计算迭代结束Step2计算迭代结束23§3.10共轭梯度法一、与方程组等价的二次泛函问题思想共轭梯度法将求解方程组问题等价转化为一个二次泛函的极值问题。

定义二次函数设为对称正定矩阵，其中§3.10共轭梯度法一、与方程组等价的二次泛函问题思想共24二次函数的基本性质：对对有为的解的充要条件是证明：必要性:二次函数的基本性质：对对25该性质说明：求解方程组的解等价于求上述二次函数的最小值。如果则由极值的必要条件得充分性:迭代法构造思想：构造使得该性质说明：求解方程组的解等价于求上述如果则由极值的必要条件26二、最速下降法几何意义：等值线思想最速下降法是指每次沿着函数值下降最快的方向寻找最小值点。

而函数值下降最快的方向是函数的负梯度方向二、最速下降法几何意义：等值线思想最速下降法是指每次沿着函27最速下降法实现过程：选取初始向量，由二次函数的基本性质如果，则就是方程组的解；如果，则沿方向进行一维极小搜索：求使得达到最小值,则最速下降法实现过程：选取初始向量，由二次函28注意到令，从而完成第一次迭代。下面以为新的初值，重复上述过程。注意到令29最速下降法的算法:选取初值Fork=0,1,2,…如果，停止否则，进行下一次循环搜索方向是正交的：缺陷：收敛速度慢！收敛速度？？？？？最速下降法的算法:选取初值Fork=0,1,2,…如果30设的特征值为,则由前述最速下降算法产生的序列满足其中。上述定理说明，当时最速下降法收敛非常慢。设的特征值为,则由313、共轭梯度法/*Conjugate-GradientMethod*/共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中，已经成为求解大型稀疏线性方程组最受欢迎的一类方法。

3、共轭梯度法/*Conjugate-GradientMe32设为对称正定矩阵，其中思想设为对称正定矩阵，若中向量组满足则称它是中的一个共轭（正交）向量组。利用一维极小搜索方法确定一组共轭方向代替最速下降法中的正交方向来进行迭代。设33选取初始向量，共轭梯度法如何确定下一个搜索方向呢？选取初始向量，34共轭梯度法的实现过程选取初始向量，，如何确定下一个搜索方向呢？由过点向量和所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向共轭梯度法的实现过程选取初始向量，35、和的几何意义此时在上可表示为、和的几何意义此时在36由极值的必要条件得其中满足由极值的必要条件得其中满足37取下一个搜索方向为沿该方向进行一维搜索得步长为记下面以为新的迭代值，重复上述过程即可取下一个搜索方向为沿该方向进行一维搜索得步长为记下面以38一般地，设已经得到，则第k+1步迭代的计算公式为终止条件：一般地，设已经得到，则第k+1步迭代的计算公式为39算法简化：算法简化：40310梯度法与共轭梯度法解析课件41共轭梯度法的算法选取初值Fork=0,1,2,…,n计算计算如果，停止否则，计算进行下一次迭代共轭梯度法的算法选取初值Fork=0,1,2,42