数值分析（陈延梅）2线性方程组的数值解法.pptVIP

单变量t的二次函数 令??(t)=t(Apk, pk)-(r(k), pk)=0得 且这时有???(t)=(Apk, pk)?0, 从而得极小f(x(k+1)). 其中 考察直线x= x(k) +tpk与椭球面f(x)=C的交点， 二次方程?(t)= f(x(k) +tpk)=C，当C=f(x(k+1) 时只有 一个重根?k，因此pk与椭球面f(x)=f(x(k+1)相切于 x(k+1). 另外， r(k+1)=b-Ax(k+1)=b-A(x(k)+?kpk)=r(k)-?kApk (r(k+1), pk)= (r(k), pk)- ?k(Apk, pk)=0 r(k+1)与 pk正交. 最速下降法 在n维空间定义的二次函数f(x)在点x(k)的改变率 最大的方向是f(x)在点x(k)的梯度 gradf(x)|x= x(k)=-r(k) ， 因此沿方向r(k)函数f(x)瞬时下降的最快，所以取 这个方向为pk而得到新的近似x(k+1)的方法就叫最 速下降法. 只要r(k)?0,最速下降法就继续下去,这里有(r(k+1), r(k) )=0. 共轭梯度法 求解Ax=b的最速下降法的最速下降方向,即 r(k)=-gradf(x(k))具有局部性质,在x(k) 附近f(x)沿r(k) 下降最快. 但总体看,这个方向未必是函数下降最理想的方向.下面介绍更合理地选择方向pk的方法,这种方法只要经过有限步(? n)就能找到n维椭球面簇的公共中心x*的一种迭代法，即共轭梯度法，它是具有迭代形式的精确解法. 定义 A?Rn?n为对称正定矩阵, p,l?Rn，如果 (p, Al)=0,则称p与l为A-正交或A-共轭. 先考察二维情形 共轭梯度法的具体步骤 第1步（采用最速下降法） 对于初始向量x(0)，r(0)=b-Ax(0)?0，取p0=r(0), 从x(0)出发沿方向p0寻找新的近似(f(x)的极小点)x(1). 计算r(1)=b-Ax(1)=r(0) - ?0Ap0，且有(r(1), p0)=0，若 r(1)?0 第2步 选择方向向量p1,满足条件 ⅰ) p1=r(1) +?0p0 ； ⅱ) p1与p0为A-正交或A-共轭(称p1为p0的共轭方向). 即选择?0满足0=(p1, Ap0)= (r(1), Ap0)+?0 (p0, Ap0) 从而 ，p1=r(1) +?0p0 有了p1，沿方向p1，在直线x=x(1) +tp1 (t为参数)上找使 f(x)为极小的点x(2)， 计算r(2)=b-Ax(2)=r(1) - ?1Ap1，且有(r(2), p1)=0，若r(2)?0 ? ? 重复上述过程，设已求得x(k)，且假设r(0), r(1),?, r(k)都非零， p0 ,p1 ,?,pk-1都非零, (r(k), pk-1)=0, 第k+1步 (从第2步开始，以后各步统一按如下原则)选择方向向量pk ,满足： ⅰ) pk= r(k) +?k-1pk-1 ⅱ) pk与pk-1为A-正交或A-共轭. 即选择?k-1满足0=(pk, Apk-1)=(r(k), Apk-1)+?k-1(pk-1, Apk-1) pk= r(k) +?k-1pk-1 沿方向pk,在直线x=x(k)+tpk (t为参数)上找使f(x)为 极小的点x(k+1) 计算r(k+1) =b-Ax(k+1)= r(k) -?kApk 且有(r(k+1) , pk)= (r(k), pk)- ?k(Apk, pk)=0 , pk? 0 若r(k+1) ? 0 ，，继续下一步. 共轭梯度法推算步骤公式(算法) (1)任取初值x(0) ?Rn； (2) p0=r(0)=b-Ax(0) (3)对于 k=0,1,2,?,N x(k+1)=x(k) +?kpk r(k+1)=b-Ax(k+1)=r(k) -?kApk pk+1= r(k+1)+?kpk 定理 设{r(k)},{pk}分别为由共轭梯度法产生的剩余向量序列和共轭方向序列，则{r(k)}构成一个正交系,{pk}构成一个A-正交系，即 (ri, rj)=0, 当i?j (pi, Apj)=0, 当i?j 定理 定理 共轭梯度法cg最多迭代n次就能得到方程组Ax=b 的精确