1020 共轭梯度法（精选）.ppt

文档介绍：§ 共轭梯度法
基本思想
利用目标函数在当前迭代点处的负梯度方向与上一步的搜索方向的适当线性组合,逐步产生一系列共轭方向,分别作为下一步的搜索方向.
由Taylor公式知,一个函数在一点附近的性态与二次函数是很接近的,因此,为了建立有效算法,往往先考虑二次模型,即现针对正定二次函数建立有效的算法,然后再推广到一般函数上去。
一、共轭方向及其性质
注:
若
则是正交的,因此共轭是
正交的推广.
定义1:
如果:
则称
是关于
共轭的.
设
是
中任一组
非零向量,
是n阶实正定矩阵,
定理1:
设
为
阶正定阵,
非零向量组
关于
共轭,
则必线性无关.
推论1:
设
为
阶正定阵,
非零向量组
关于
共轭,
则它们构成
的一组基.
则
定理2:
设
为
阶正定阵,
非零向量组
关于
共轭.
若向量
与
均正交,
定理1:
设
为
阶正定阵,
非零向量组
关于
共轭,
则必线性无关.
证明:
定理1和定理2 的证明
设有一组数
满足
用
左乘上式两边,
得
而
由于A是正定阵,
所以
结合上式,则
因此
线性无关。
证明:
向量
可由它们线性表示,
于是
则
定理2:
设
为
阶正定阵,
非零向量组
关于
共轭.
若向量
与
均正交,
由于
关于
共轭,
所以
线性无关,
因此它们是
的一组基。
设表示式为:
注意到
即
与
均正交,
则
所以
是零向量,
证毕。
定理3:
设
为
阶正定阵,
向量组
关于
共轭,
对正定二次函数
由任意点
出发,
依次沿
进行精确
则:
(1)
(2)
当
时,
为f(x)在
上的极小点.
一维精确得
最多经n次迭代便可求得极小点.
启发:
用迭代法求解正定二次函数极小:
转化为构造关于Q共轭的n个方向问题.
如何构造n个关于Q共轭的方向?
一种做法是借助迭代点处的负梯度方向来构造
共轭梯度法
二、求解正定二次函数的共轭梯度法
令
左乘
并使
得:
1. 构造共轭方向—借助待定系数法
取:
令
然后