(k ) (0) (k) (0) (0) k (0)
定理7.3表明：向量组 r
( 0)
, r ,, r
(1)
(k )
和
p , p ,, p
( 0)
(1)
(k)
分别是Krylov子空间的正交基和共轭正交基。因此，共轭
梯度法最多用n步便可得到方程组的精确解。
Th5.4
由共轭梯度法计算得到的
x
(k )
( k 1)
p
( k 1)
r
( k 1)
x
( k 1)
x
(k )
k p
(k )
k p
(k )
进行下一次迭代
r
0, 0 i j k r , r 0, i j , 0 i , j k Ap , p 0, i j , 0 i , j k
二、最速下降法/*Steepest Descent Method*/
思 想
最速下降法是指每次沿着函数值 下降最快的方向寻找最小值点。
而函数值下降最快的方向是函数的负梯度方向
几何意义：
等值线
x
(0)


x

最速下降法的实现过程 (0) 选取初始向量 x ，由二次函数 ( x ) 的基本性质
(1)
r r
(1)
x
(1)
(1)
2bT x (1)
p A x r p
p
(0) (0) T (1) (0)
( , )
(1)
r
(1)
p
(0)

由极值的必要条件得
(1)T (1) (1)T (0) (1)T (1) 2 r Ar r Ap r r 0 2 r (1)T Ap(0) p(0)T Ap(0) 0
( k )T (k )
终止条件：
r
( k 1)
0
同时注意到
(r , p ) (b Ax ,p ) (k ) (k ) (k ) (k ) (r , p ) k ( Ap , p ) 0
(k ) (k )
( k 1)
( k 1)
(r , p ) ( r , r
(k ) (k ) (k )
(r
( k 1)
,r
(k )
)0
( k 1)
(k )
b Ax (k ) (k ) (r , r ) k (k ) (k ) ( Ar , r ) r
r
(k )
( k 1)
b Ax
(k )
b A( x k r )
x
( k 1)
x
(k )
(k )
k r
设
nn
(0) (1) (l ) (i ) ( j) p , p , , p 满足 ( Ap , p ) 0 i j
Def
设 A R
n n
为对称正定矩阵，若 R 中向量组
n
则称它是 R n 中的一个A 共轭（A 正交）向量组。
思 想
利用一维极小搜索方法确定一组 A 共轭方向 代替最速下降法中的正交方向来进行迭代。
设 A 对称正定，则 x 为

xR
证明： 必要性由上述性质易知，下证充分性： 如果 ( x


) min ( x ) n
xR
则由极值的必要条件得

( x ) 2( Ax b) 0 Ax b 2 ( x) A 0

定理7.1说明：求解方程组的解等价于求上述 二次函数的最小值。常用方法：迭代解法
设
( x) x Ax 2 x b aij xi x j 2 b j x j
T T
n
n
n
i 1 j 1
j 1
二次函数 ( x )的基本性质： 对 x R , ( x) 2( Ax b)
n
设 x A b 为 Ax b 的解，则

1
(0)
r
(0)
)
( x r ) A( x r ) 2b ( x r )
( 0) T ( 0) ( 0)
(r , r ) 0 ( 0) ( 0) ( Ar , r )
d (0) (0) (0) (0) 注意到 2 ( x r ) ( Ar , r ) 0 d
T
2
0
0
1
1
0
计算
( 0)
0
x1 x2
3

( 0)
1
1
Step1
2
( 0)
x3
3
解： 易验证系数矩阵是对称正定的.
p r
( 0)
b Ax
(1)
( 0)
(3 1 3)
( 0)
T
(r , r ) 0 ( 0) (0) ( Ap , p ) 55
x 19
x
0 p
( 0)
19 T (3 1 3) 55
r
(k )
k Ar
(k )
如果
r

，停止
缺陷：收敛速度慢
否则，进行下一次循环
(k ) x 则由前述最速下降算法产生的序列 满足
Th7.2
设
A 的特征值为 0 1 n ,
x
其中
(k )

x
A
x A b。
1
n 1 n 1
(1 )
和
所张成的下列二维平
面内找出函数值下降最快的方向作为搜索方向
p
(1)
2 x x
(1)
r
(1)
p : , R
(0)
p 、p
(1)
(0)
和
r
(1 )
的几何意义
2
x p
(1)
r
(1)
x
(1)
p
(0)
此时 ( x ) 在 2 上可表示为
x
p
( 0)
b Ax ( 0) r
(k )
k Ap
(k )
如果 r
( k 1)
0 ，停止
( k 1)
否则，计算
For k=0 , 1 , 2 , … , n
(r , r ) 计算 k (k ) (k) ( Ap , p )
(k )
(r , r ) k (k ) (k ) (r , r )
2
( 0)
( 0)
min ( x

(0)
r ) (x
(0)
(0)
0r )
(0)
令 x(1)
下面以
x
x
(1 )
( 0)
0r
( 0)
，从而完成第一次迭代。
为新的初值，重复上述过程。
最速下降法的算法
选取初值
(k )
x
( 0)
R
(k )
n
搜索方向是正交的：
For k=0,1,2,…
Step2 计算
(1)
r
(1)
r
( 0)
0 Ap
( 0)
6 T (1 6 1) 55
(1) (1)
(r , r ) 72 (r , r ) 55 0 ( 0) ( 0) 1 (1) (1) ( r , r ) 3025 ( Ap , p ) 57
p r 0 p
r ( x ) b Ax (0) ( 0) 如果 r 0 ，则 x 就是方程组的解； ( 0) (0) 如果 r 0 ，则沿 r 方向进行一维极小搜索：
( 0) ( 0)
(0)
求步长
d (0) (0) (x r ) 0 d
( 0) ( 0) T ( 0)
(x ，使得 min
(1) (1) ( 0)
(1)
114 T ( 1 18 1) 3025
(1) TΒιβλιοθήκη xr( 2)
x 1 p (1 1 1)
(1)
( 2)
b Ax
( 2)
(0 0 0)
T
迭代结束
( j)
Th7.3
由共轭梯度法得到的 r

(i )
,p
(i )
满足性质：
,p
(i)
( j)
(i )
( j)
(i)

Krylov (克雷洛夫)子空间
(0)
span r , , r
(0)
A, r
span p , , p , k 1 span r , Ar ,, A r
共轭梯度法的实现过程
选取初始向量
x
(0)
，p
( 0)
( 0)
r
(1)
( 0)
，
( 0)
x x
(1)
( 0)
0 p , r
b Ax
p
(0)
(r , r ) ( 0) ( 0) ( Ap , p )
(1)
( 0)
( 0)
如何确定下一个搜索方向呢？ 在过点
x
(1 )
的由向量 r
( x ) ( Ax , x )

，且对 x R 有
n
( x) ( x ) ( Ax, x) 2( Ax , x)

( Ax , x ) ( A( x x ), x x )