数值分析.ppt

数值分析1294353.ppt初等变分原理
最速下降法
共轭梯度法
数值试验算例
《数值分析》 12




( x, y ) = ( y, x );
( tx, y ) = t ( x, y);
( x+ y, z ) = ( x, z ) + ( y, z );
( x, x) ≥ 0, 且( x, x) = 0  x = 0;
I 方程组问题: Ax = b
设A是 n 阶对称正定阵
( Ax, y ) = ( x, Ay ) ;
( Ax,x ) ≥0, 且( Ax, x) = 0  x = 0
2/16
——初等变分原理——
II 极值问题:
设, 记( x , y) = xT y
设A =( aij )n×n为实对称正定矩阵,
则 x 使二次函数
取极小值 x 是线性方程组 Ax = b 的解。
证明: 必要性. 设 u 是 Ax = b的解
 Au = b 
对任意 x∈R n , 只须证明 f (x) – f (u) ≥ 0
3/16
证充分性. 设 u 使 f(x) 取极小值. 取非零向量 x∈R n,
对任意 t∈R , 有
令 g(t) = f( u + tx), 当 t=0 时, g(0)= f(u)达到极小值, 所以 g’(0) =0 ,即
( Au – b , x ) = 0 
Au – b = 0
所以, u 是方程组 Ax = b 的解.
4/16
——最速下降法——
从初值点 x(0) 出发,以负梯度方向 r 为搜索方向
在 x 处,梯度方向是 f(x) 增长最快方向
负梯度方向是 f(x) 下降最快方向
梯度: f = gradf(x) =[ fx1, fx2, ····, fxn ]T
选择步长 t0, 使 x(1) = x(0) + t0r 为 f(x) 极小值点
f = Ax – b
5/16
方向l : l = [ v1, v2 ,···, vn ]T , g(t) = f( x + t l )
方向导数: g’(0) = fx1v1+ fx2v2+ ····,+fxn vn
l 与f 方向一致时, 方向导数取得最大值
f 是 f(x) 增长最快方向
–f 是 f(x) 下降最快方向
其中, || l || = 1, x = [x1, x2 ,···, xn ]T
l 与f 方向相反时, 方向导数取得最小值
6/16
分别取 l = e1, e2, ···, en (单位矩阵 I 的列向量),
g’(0) = fx1v1+ fx2v2+ ····,+fxn vn
g’(0)=( Ax – b , l )
最速下降方向: r = –f = b – Ax
f =Ax – b
n 个方向的方向导数按次序排列成梯度f
7/16
求解, 得 t0 = ( r0 , r0) / (Ar0 , r0)
为选取最佳步长 t0 ,令
取初值点 x(0), 取负梯度方向 r0 = b – A x(0)
求点: x(1) = x(0) + t0r0 使得
记
8/16
解对称正定方程组Ax = b 的最速下降算法:
第一步: 取初值 x(0)∈R(n) , >0,计算
r0 = b – Ax(0) , k  0;
第二步: 计算 tk = (rk ,rk ) / (Ark , rk)
x(k+1) = x(k) + tk rk ; rk+1 = b – Ax(k+1) ;
第三步: k  k+ 1, 如果||rk|| ≥,转第二步;
否则,输出: x(k) , 结束.
9/16
——共轭梯度法——
A是 n 阶对称正定矩阵,非零向量 p1, p2∈Rn
(Ap1, p2)=0
n 个向量 p1, p2 ,···, pm 共轭:
(Api , pj )=0
(i≠j; i, j = 1,2,···,m )
非零向量 p1, p2 ,···, pm ∈Rn
p1, p2 ,···, pm 关于 A 共轭
 p1, p2 ,···, pm 线性无关
两个向量 p1, p2 共轭:
10/16