06-线性方程组的迭代法--共轭梯度法(CG)

CG 方法 -线性方程组与极值问题 -最速下降法 -CG 方法(共轭梯度法)
展开查看详情

1.第六章 线性方程组的迭代法 — 共轭梯度法 ( CG )

2.2 线性方程组与极值问题 最速下降法 CG 方法(共轭梯度法) CG 方法

3.2 线性方程组与极值问题 最速下降法 CG 方法(共轭梯度法) CG 方法

4.4 梯度下降法 基本思想: 选取 一 个初始向量 x (0) (2) 确定一个下降方向 p (0) ,从 x (0) 出发,沿方向 p (0) 找极小点 x (1) (3) 以 x (1 ) 点为新的出发点,确定一个新的下降方向 p (1) ,从 x (1) 出发 , 沿 p (1) 找极小点 x (2) (4) 以此类推,不断寻找新的点 x ( k ) ,直到找出最小值点 x  求解线性方程组 Ax = b 求  ( x ) 的最小值点 ( 极小值点 )

5.5 两个基本问题 问题一 :如何确定 下降方向 ? 问题二 :如何确定 步长 ?

6.6 最速下降法 基本思想: 任取一个迭代初始向量 x (0) ,构造迭代序列 x (0) , x (1) , x (2 ) , . . . , 使得  ( x (0) ) >  ( x (1) ) >  ( x (2) ) > . . . ,且每一步都 以 最快 的 速度 下降 到  ( x ) 的极小值。 具体作法: 设 x ( k ) 已经求得,计算 x ( k +1) :  ( x ) 沿 x ( k ) 处的 最速下降 方向,即 负梯度方向 r ( k ) = -( Ax ( k ) - b ) 的 最小值点,即

7.7 最速下降法 计算  的值

8.8 最速下降法 算法 : (最速下降法) (3) 对 k = 0, 1, 2, ... , 计算 若 ,则输出 x   x ( k +1) ,停止 计算。 给定初值 x (0 ) 和精度要求  计算

9.9 最速下降法的收敛性 定理 : 设 A 对称正定 ,其特征值为 则由最速下降法产生的序列满足 且有 缺点 : (1) 若  1 >> n ,则收敛很 慢,并可能出现不稳定现象 ( 舍入误差 ) (2) 每次的下降方向为 局部下降最快 ,并非全局最快

10.10 举例

11.11 举例

12.12 举例 等高线  ’ ( x )  ( x )

13.13 举例 最 速 下 降 法

14.14 共轭梯度法 出发点 : 在确定 x ( k +1) 时,不沿负梯度方向取极小,而是寻找一个更好的方向 p ( k ) ,使得  ( x ) 下降得更快! 定义 : 设 A 对称正定 ,若 ( x , Ay ) =0 ,则称 x , y 关于 A 正交 ( A- 正交 ) 或 A - 共轭 ,若 z 1 , z 2 , . . . , z n 相互 A - 共轭,则称 z 1 , z 2 , . . . , z n 构成 A - 正交向量组或 A - 共轭向量 组 。

15.15 共轭梯度法 具体作法 : 令 p (0) = r (0) ,设 x ( k ) 已经求得,则 x ( k +1) 由下面的公式确定: 其中

16.16 共轭梯度法 定理: 设 A 对称正定 ,则由 CG 算法产生的序列满足 (1) 当 i  j 时, ( r ( i ) , r ( j ) ) =0 ,即 r (0) , r (1) , r (2) , . . . 相互正交 (2) 当 i  j 时, ( p ( i ) , Ap ( j ) ) =0 ,即 p (0) , p (1) , p (2) , . . . 相互 A- 共轭 证明 :略 参数的新计算公式:

17.17 共轭梯度法 算法 : (共轭梯度法) (3) 对 k = 0, 1, 2, ... , 计算 给定初值 x (0 ) 和精度要求  计算 ,令 若 ,则输出 x  = x ( k +1) ,停止 计算 。

18.18 共轭梯度 法 的收敛性 定理 : 设 A 对称正定 ,则共轭梯度法至多 n 步就能找到精确解。 定理 : 设 A 对称正定 , x  为精确解, x ( k ) 为共轭梯度法的数值解,则有 其中