3-6最速下降法和共轭梯度法

§3.6

最速下降法与共轭梯度法

考虑线性方程组：

Ax b

其中A为对称正定。定义二次泛函 其梯度

有唯一的极小点

( x) Ax b *

1 T T ( x) x Ax b x 2

1 x A b

线性方程组的求解问题转化为优化问题： * Ax b ( x ) min ( x) (3 32) nx R

求 的极小点的最简单而有效的方法是 最速下降法。具体方法：

从某个初始点x 出发，沿 ( x)在 x 的 负梯度方向(0)

( 0)

( 0)

r

求得 x 的极小点 x

x

(0)

b Ax (搜索方向) (1)(())

,

即

(1) (2) 然后从 x 出发，重复上述过程，求得 x .

(1) (0) (0) x min x r 0

如此继续下去，由 ( k 1) (k ) ( k ) x min x r

(k ) 得到序列 x , 满足(k ) ( k 1) x x

0

k 1, 2,

k 1,2,

现令 易知 由

(k ) (k ) f ( ) x r , R

(k ) f ( ) r

T

(k ) (k ) r Ar

(k ) Ar

f 0

可得f 的唯一极小点

(k ) k 1 r

T

(k ) r

(k ) r

T

这样，得到了最速下降法的迭代公式：

( k 1) k r

x

T

( k 1) r

( k 1) r( k 1)

T

( k 1) Ar

x

(k )

( k 1)

k r(k )

r

(k )

b Ax

(k 1,2, ).

算法3.1 (最速下降法) (0) 1. 输入A, b, x 和精度 . (0) (0) 2. r : b Ax , x : x . T T 3. : r r / r Ar , (0) x : x x , r : b Ax. 4. 如果 r , 则输出x, 停;否则, 转3.

结论：

(k ) x

(0) 从任一 x 出发，用最速下降法产生的序列 均收敛于方程组Ax b的解。其收敛速度

取决于 n 1 n 1 , 其中 1, n分别是A的最大、 最小特征值.优点： 计算简单，能充分利用矩阵的稀疏性。 缺点：

当 《 1 n时，收敛速度很慢。

为解决这一问题，需引入 共轭梯度法

3.6.2共轭梯度法基本思想：

搜索方向在负梯度方向基础上加以修正。 ( k 1) ( k 1) 要求第k次搜索方向 与前次搜索方向d k d (k 1) 关于A共轭，即：d , Ad 0 (0) 计算过程： 取初始向量x (0) (0) (0) (0) 第1步： d r ( x ) b Ax (0) (0) ( k 1) ( k 1) 0 r , d d , Ad

(1) (0) (0) x x 0 d

第k步(k 1, 2,...) (k )

(k ) (k ) r ( x ) b Ax ( k ) ( k 1) ( k 1) ( k 1) k 1 r , Ad d , Ad

(k ) (k ) ( k 1) d r k 1 d k (k ) (k ) (k ) k r , d d , Ad ( k 1) ( k ) (k ) x x k d

优点： 1. 共轭梯度法具有有限步终止性，即如果 计算过程中无舍入误差产生，用共轭梯 度法求解问题(3-32)至多进行n步就 可以得到准确解。 2. 具有超线性的收敛速度。

3. 存储量小，计算简便，对病态方程可得 到较准确的解缺点: 如果系数矩阵A的特征值较均匀地分布在一 个很长的区间内,共轭梯度法可能收敛得很慢.

本章小结1.Jacobi迭代法

2.Gauss-Seidel迭代法3.松弛法

4.迭代的收敛条件

作业

P72 3题，4题用松弛法

上机作业

实验一

编程实现Jacobi, G-S, 松弛迭代法

线性方程组数值解法总结

直接三角分解法A LU Ax b Ly b Ux y

y1 b1 k 1 y b l y k k kj j j 1 x n y n u nn n x k ( y k u kj x j ) u kk j k 1

k 2,3, , n

k n 1, n 2, ,1

追赶法--三对角方程组Ax=d的求解公式 u1 b1 li ai ui 1 i u b c l i i 1 i i u1 l2 u2 l3 u3

2,3, , n

y1 d1 追 : Ly d yk dk lk yk 1

k 2,3, , n

xn yn / un k n 1, n 2, 1 赶 : Ux y xk ( yk ck xk 1 ) / uk追赶法的运算量为5n 4.

平方根法

Ax b

Ly b,

L x yT

y1 b1 / l11 k 1 y ( b l y ) l k k kj j kk j 1

k 2,3, , n

xn yn / lnn n x ( y l x ) l k k jk j kk j k 1

k n 1, n 2, ,1

改进的平方根法

A LDL ,T

Ax b Ly b,设

L x D yT

1

1 l 1 21 L l 31 l 32 1 l n1 l n 2 l n 3 1

D diag(d1 , , d n ) di 0

计算公式

2 d a l kk kj d j k j 1 k 1 l (a l d l ) d ik ik ij j kj k j 1

k 1

k 1,2, , n i k 1, , n

记 uik lik d k

k 1,2, , n,

i k 1, , n

k 1 d k a kk u kj l kl j 1 k 1 u ik aik u ij l kj j 1 l u d ik ik k

k 1,2, , n

i k 1, , n