设 p1 , p2 , , pk 是 Rn 中一组非零向量，如果它们两两关于A
共轭，即 piT Apj 0, i j ,i , j 1,2, ,k。 则称这组方向是关于A共轭的，也称它们是一组A共轭方向。
注：如 果A是 单 位 矩 阵 ， 则
p1T I p2 0 p1T p2 0
p1 p2
§2.5 共轭梯度法
预备知识 最速下降法 共轭梯度法 数值试验算例
21:26
预备知识：内积的定义
I II
方程组问题: 极值问题:
Ax =
min
b
f
(x)
1
xT Ax
bT
x
xRn
设 x, y Rn , 记 ( x , y) = xT y
2
▪( x, y ) = ( y, x ); ▪( tx, y ) = t ( x, y); ▪( x+ y, z ) = ( x, z ) + ( y, z ); ▪( x, x) ≥ 0, 且( x, x) = 0 x = 0;
p(k 1) r (k 1) k p(k )
进行下一次迭代
例：用CG迭代法求解下列方程组: x(0) (0 0 0)T
2 0 1 x1
3
0 1 0 x2 1
1 0 2 x3
3
解： 易验证系数矩阵是对称正定的.
Step1 计算 p(0) r(0) b Ax(0) (3 1 3)T
0
x2 x1
x*
x3
注 最速下降方向反映了目 标函数的一种局部性质。它只是 局部目标函数值下降最快的方向。 最速下降法是线性收敛的算法。
f(x1,x2)=100x12+x22
最速下降法
21:26
f(x1,x2)=100x12+x22
21:26
Barzilai-Borwein方法
局部思想: 最速下降法思想简单,但是收敛速度慢。本
➢几何意义：
等值线
x
(
0)
•
•x
思
最速下降法是指每次沿着函数值
想
下降最快的方向寻找最小值点。
而函数值下降最快的方向是函数的负梯度方向
➢最速下降法实现过程： 选取初始向量 x(0)，由二次函数 H ( x)的基本性质
H ( x(0) ) b Ax(0) r (0) 如果 r (0) 0 ，则 x(0)就是方程组的解； 如果 r (0) 0 ，则沿 r (0)方向进行一维极小搜索：
0
(r(0), r(0) ) ( Ar (0) , r (0) )
19 55
x(1) x(0) 0r (0)
19 (3 1 3)T 55
最好 + 最好 = 最好 ?
• 方向(最速下降) (best rk)
• 步长(精确搜索) (best k)
• x(k1) x(k) k r(k) 是否最好 ?
由极值的必要条件得
r (1)T Ar (1) r (1)T Ap(0) r(1)T r(1)
0
r (1)T Ap(0) p(0)T Ap(0)
0
x% x(1) 0r (1) 0 p(0) 其中 0 ,满0足
00rr((11))TT
Ar (1) Ap(0)
0r (1)T Ap(0) r (1)T 0 p(0)T Ap(0) 0
i 1 j 1
j 1
定理(初等变分原理) 设A =(aij )n×n为实对称正定矩 阵, x, b ，R则n x是二次函数
nn
n
H(x) xT Ax 2bT x
aij xi x j 2 bj x j
i 1 j 1
j 1
的极小值点 x 是线性方程组 Ax = b 的解。
21:26
若 H ( x ) min H ( x), 则由极值的必要条件得 xRn H ( x ) 2Ax 2b 0. Ax b
0
(r(0), r(0) ) ( Ar (0) , r (0) )
注意到
d2
d 2
( x(0)
r(0)
)
2( Ar (0) , r(0) )
0
min
(
x(0)
r(0)
)
(
x(0)
r(0)
0
)
令 x(1) x(0) 0r (0)，从而完成第一次迭代。
下面以 x (1)为新的初值，重复上述过程。
x ( x1,L , xn )T , b (b1,L , bn )T ; x* A1b.
思 共轭梯度法将求解方程组问题等价转化为一个 想 二次 泛函的极值问题。
一、与方程组等价的二次泛函问题
定义二次函数 : Rn R
nn
n
H(x) xT Ax 2bT x
aij xi x j 2 bj x j
共轭是正交的推广！！
共轭梯度法
选取初始向量 x(0)，
p(0)
r(0),
0
(r(0) , p(0) ) ( Ap(0) , p(0) )
x(1) x(0) 0 p(0) , r (1) b Ax(1)
如何确定下一个搜索方向呢？
➢共轭梯度法的实现过程
选取初始向量
x(0) ，p(0) r (0)
求 0 使得 H ( x(0) r (0) ) 达到最小值, 则
x(1) x(0) 0r (0) .
H ( x(0) r(0) )=
1 ( x(0) r(0) )T A( x(0) r(0) ) bT ( x(0) r(0) )
2
d H(x(0) r(0) ) 0 d
(r(0), r(0) ) ( Ap(0) , p(0) )
19 55
x(1) x(0) 0 p(0)
19 (3 1 3)T 55
Step2 计算
r (1)
r(0)
0 Ap(0)
6 (1 55
6
1)T
0
(r(1) , r(1) ) (r(0), r(0) )
21:26
Th 设 A的特征值为 0 1 ,L n
则由前述最速下降算法产生的序列 x(满k) 足
k
x(k) x
A
n n
1 1
其中 x A。1b
x(0) x A
上述定理说明，当 1 =时最n速下降法收敛非常慢。
锯齿现象
在极小点附近，目标函数可以用二次函数近似，其等值面近似 椭球面。
f x2
L
Hessf M O
2 f
xnx1
L
2 f
x1xn
M
2 f
xn2
预备知识
f ( x) 1 ( Ax, x) (b, x) 2
n
n
=
1 2
aij xi x j bi xi
i, j1
i 1
gradf Ax b
2 f
x12
2 f
该性质说明：求解方程组的解等价于求上述 二次函数的最小值。
迭代法构造思想：构造 { x(k使) }得
H ( x(0) ) H ( x(1) ) L H ( x(k1) ) H ( x(k) ) L H ( x* ),
且 lim H( x(k) ) H( x* )， lim x(k) x*。
设A是 n 阶对称正定阵
▪( Ax, y ) = ( x, Ay ) ; ▪( Ax，x ) ≥0, 且( Ax, x) = 0 x = 0
2/16
预备知识
梯度:
f ( x) gradf ( x)
, ,L , f f
x1 x2
f T xn
Hessian矩阵:
21:26
f
x1
f
(
x)
For k=0 , 1 , 2 , … , n
计算k
(r(k), r(k) ) ( Ap(k) , p(k) )
x(k1) x(k ) k p(k )
r (k 1) r (k ) k Ap(k )
如果 r(k1) 0 ，停止
否则，计算
k
(r(k1) , r(k1) ) (r(k),r(k) )
r (k1) b Ax(k1)
b
A(
x(k)
r(k)
k
)
r (k ) k Ar (k )
收敛速度？？？？？
缺陷：收敛速度慢！
例：用最速下降法求解方程组: x(0) (0 0 0)T
2 0 1 x1
3
0 1 0 x2 1
1 0 2 x3
3
解： 易验证系数矩阵是对称正定的.
Step1 计算 r(0) b Ax(0) (3 1 3)T
r (k 1) r (k ) k Ap(k )
如果 r(k1) 0 ，停止
否则，计算
k
p(k )T Ar (k1) p(k )T Ap(k )
p(k 1) r (k 1) k p(k )
进行下一次迭代
➢共轭梯度法的算法
选取初值 x(0) Rn
计算 r(0) b Ax(0) p(0) r(0)
p(1)、 p(和0) r(1的) 几何意义
2
xg p(1) r(1) x g(1)
p(0)
此时 ( 在x) 上可2 表示为
H x(1) r(1) p(0)
( ,)
1
x(1) r(1) p(0)
T
A
x(1) r(1) p(0)
2
bT x(1) r(1) p(0)
共轭梯度法的关键是构造一组两两共 轭的方向(即一组线性无关向量)。巧妙的是, 共轭方向可以由上次搜索方向和当前的梯 度方向之组合来产生。
pk+1 := rk+1 + tau*pk