《计算机数值方法教学课件》第一章线性代数方程组数值解法-pa

1、1.3 解线性方程组的迭代法(Iterative Methods for Linear Equations),2,求如下线性代数方程的解,解为,3,4,精确解为,5,定义1：对于任一向量 ,按照一定规则确定一个实数与之对应，该实数记为 ，若 满足下面三性质： （1） 当且仅当X=0时， ； （2）对任意实数a, ； （3）对任意向量 ，满足 那么，称该实数 为向量X的范数。,一、 向量范数(Norm of Vector),1.3.1范数及有关性质,6,设,，则,是否为向量X的范数？,常用的三种向量范数有,(I)、 2范数,(II)、 1范数,(III)、 范数,7,解：,8,二、矩阵的范数,定

2、义2 设XRn，ARnn，则定义,为矩阵A的范数（算子范数）。,9,二、矩阵的范数,矩阵范数的性质：,性质： 向量范数的性质（1，2，3）,4、对与矩阵A具有相同维数的向量X， 恒有,5、对于同阶矩阵A，B有,(相容性),10,由此可以得到与前面三种向量范数对应的矩阵范数是,(I)、 2范数,(II)、 列范数,(III)、 行范数,11,解：,12,如Rn中的 Rn 1和 Rn ，就存在如下关系：, Rn Rn 1 n Rn ,1/n Rn 1 Rn Rn 1,13,三、向量及矩阵序列的收敛问题,14,从上面范数的等价性可以推出，在某一种范数意义下向量序列收敛，则在任何一种范数意义下该向量序

3、列收敛。因此，一般按计算的需要采用不同的范数，而不特别强调在那种范数意义下收敛。而且把向量序列X(k)收敛于向量X记为：,同样,15,16,四、谱半径,设nn阶矩阵A的特征值为i(i=1,2,n) ，则称,为矩阵A的谱半径。, 矩阵范数和谱半径的关系,17,18,五、扰动方程组的误差分析,定义4 如果线性方程组AX=b中A或b的元素的微小变化，就会引起方程组解的巨大变化，则称该方程组为“病态”方程组，矩阵为“病态”矩阵；否则称方程组为“良态”方程组，矩阵为“良态”矩阵。,AX=b,A为非奇异阵,19,右端项扰动,解的相对误差可能达到右端项相对误差的AA-1倍,20,系数矩阵的扰动,设：,由,2

4、1,可见，右端项和系数矩阵的扰动对解的影响都与AA1有关。 A为非奇异阵，定义： cond(A)=AA1 为矩阵A的条件数。则有：,条件数cond(A)的值刻划了方程组“病态”的程度。,22,条件数与所用范数有关。常用的矩阵条件数有：,23,方程病态的判断方法,1.用主元素消去法求解时出现小主元； 2.某些行或某些列几乎线性相关； 3.矩阵A的元素间数量级相差很大，且无规律； 4.当r=b-AXk的|r|很小时，Xk作为解的精度仍然很差或不符合要求。,24,一、简单迭代法（Jacobi迭代）,AX=b,方程组可改写成多种迭代格式。,1.3.2 解线性代数方程组的迭代法,25,假设,令,迭代格式

5、：,26,令,27,当k时,若序列X(k)收敛到X*，则X*就是就是原方程的解。因为X*适合方程,以上计算过程称简单迭代法，矩阵B称为简单迭代法的迭代矩阵 。, k=0, 1, 2,.,28,X(0)，,X(1) X(0),X(1) ，,否,. . .,X(m)，,实际迭代求解过程：,29,二、Seidel(Gauss-Seidel,G-S) 迭代法, k=0, 1, 2,.,简单迭代法,30,二、Seidel(G-S) 迭代法,31,二、Seidel(G-S) 迭代法,令：,32,k=0,1,2, ., n,迭代格式,注 意:交换方程和未知数的次序都会影响Seidel迭代法的计算结果，但这种

6、交换对简单迭代法是没有影响的。,33,简单迭代法,Seidel迭代法,它们有一个共同的特点，就是新的近似解X(k+1)是已知近似解X(k)的线性函数，并且X(k+1) 只与X(k)有关, 这类迭代叫做单点线性迭代。,34,例 1 方程组,从任意选取的初始向量X(0)出发，利用迭代格式（a）构造向量序列X(k) ，该向量序列是否一定收敛呢？,35,1.3.3 迭代法的收敛性及误差估计,例 2,36,定理5 对任何初始向量X(0)和常数项f，由迭代式,产生的向量序列X(k)收敛的充分必要条件是,其中：(M)是矩阵M的谱半径。,证明： 1必要性,假设,令,37,2 充分性,结论：,条件：,收敛,有唯

7、一解，记为X*,设：,38,该定理说明：迭代是否收敛只与迭代矩阵的谱半径有关，而迭代矩阵M是由系数矩阵A 演变过来的。所以迭代是否收敛与系数矩阵A以及演变方式有关，与常数项和初始迭代向量的选择无关。,39,对例1来说，迭代矩阵,对例2来说，迭代矩阵,具体问题中，(M)1很难计算。但由于(M) |M|，所以，可以用|M|来作为(M)的一种估计，当|M|1，迭代一定收敛，不过这只是收敛的充分条件。,40,定理 6 若|M|1,则迭代序列X(k)的第k次近似值X(k)和准确解X*有估计式,根据这一定理，在实际计算中，若允许误差是，则只要相邻两次迭代向量的差满足关系式 就停止迭代,41,证明：,42,

8、定理 7 若迭代矩阵M的范数|M|=q1,则迭代格式,的第k次迭代X(k) 对于准确解X*的误差有估计式,根据这一定理，可以粗略估计达到要求精度所需的迭代次数。,43,证明：,由于,所以,44,(1) 如果方程组Ax=b的系数矩阵A(aij)Rnxn为严格对角占优矩阵，则对任意的初始向量，Jacobi迭代法和Gauss-Seidel迭代法收敛。 (2) 如果系数矩阵A是对称正定矩阵，则Gauss-Seidel迭代法收敛。,45,例3 已知方程组,1) 证明用雅可比迭代法和高斯赛德尔迭代法求解均收敛。 2)写出Jacobi法迭代的计算公式，取,3)写出Gauss-Seidel法的计算公式,202

9、0/7/15,求方程的根：,4次以上的一元n次方程没有一般公式解法！,由公式求解：,1.4 非线性方程（组）的解法,2020/7/15,1，方程可能有实根或者复根，本章学习求实根。,2，在有根的区间内，方程可能有单根、多根和重根，本章主要求单根。,本章主要内容是：求某一区间内的单实根。,2020/7/15,1.4.1 求实根的对分区间法,设f(x)=0在a,b内仅有一个实根 ,且有,a1 , b1,2020/7/15,a , b, a1 , b1, a2 , b2 , an , bn ,依此类推，可构造得到有根区间序列：,后一区间为前一区间的一半，所以称该方法为对分区间法或二分法。若取,为方程

10、根的近似值*，则有,2020/7/15,对分区间法计算过程归纳：,1、找出有根区间a, b，计算f(a)，f(b)； 2、计算f(a+b)/2f ； 3、判断： 若f =0，停止； 若f * f(a)0， (a+b)/2, b a1, b1； 4、重复2, 3，直到停止或区间缩小到误差范围内。,特点：简单，对于简单问题常用，对f(x)的要求不高，收敛速度与比值为的等比级数相同。不能求偶重根。,2020/7/15, 1.4.2 迭代法,构造迭代格式：,得到序列：,初值x0,2020/7/15,解：方程改写成等价的迭代形式,真实根,2020/7/15,则将x0=1代入后可得 x1=-6， x2=-

11、230， x3=-12063750,但是，若将方程改写成如下的等价迭代形式,明显不收敛。Why？,收敛,2020/7/15,定理1.4.1 设迭代函数(x)满足：,当xa, b时，a (x) b； 存在正数L1，对任意xa, b，均有,2020/7/15,证明：,1、作函数H(x)= (x)-x，可证明a, b必存在根,2、反证法，可证明a, b的根是唯一的。,2020/7/15,3、证明收敛性,(c),2020/7/15,反复使用(b)式，结合(c)式得,(d),2020/7/15,(1),(2),1、 L越小，收敛越快，因此，称L为渐进收敛因子。 2、由(1)式，可给出迭代终止条件； 3、

12、由(2)式，可计算所需的迭代次数； 4、定理中的条件是充分的，但不是必要的。,2020/7/15,定义1.4.1 对方程x =(x) ，若存在根的某个邻域Q : |x- |，且具有性质：对任意的初值x0 Q ， xk+1 =(xk) (k=0,1,2,)收敛，则称xk+1 =(xk)在的邻域Q内具有局部收敛性。,定理1.4.2 设为方程x =(x)的根， (x) 在的某邻域内Q一阶导连续，且|()|1，则迭代法xk+1 =(xk) 具有局部收敛性。,由于求根时，根并不是已知的，因此，此定理的意义在于：适当的调整初值，有可能使迭代法收敛。,2020/7/15,设迭代格式xk1(xk)收敛, 若记

13、ek=xk-.定义1.4.2 若存在实数p1和c0满足,则称该迭代格式p阶收敛。当p1时，称为线性收敛，当p1时称为超线性收敛，当p2时称为平方收敛。,2020/7/15,定理1.4.3 如果x(x) 中的迭代函数(x) 在根附近满足：1、 (x) 存在连续的p阶导数；2、,则迭代法 xk1(xk) 为 p 阶收敛。,证明：,2020/7/15,由于,所以,2020/7/15,例3：求方程x=e-x在0.5, 0.7内的根，并使近似根的误差小于10-3（取x0 = 0.5进行计算）。,解：,迭代收敛,迭代格式,说明0.5, 0.7为有根区间。,2020/7/15,迭代法的优点是简单，但对收敛性

14、的要求较高，收敛速度与(x)有密切关系，且有些迭代格式 x =(x) 不收敛。,0.00057 10-3,2020/7/15, 1.4.3 牛顿法(Newton法),一、基本算法,解非线性方程的牛顿法是把非线性方程f(x)=0线性化的一种近似方法。,2020/7/15,牛顿法的迭代序列：,牛顿法的几何意义：(切线法),n=0,1,2,2020/7/15,例5：用牛顿法求下面方程的根(x0=1),解：,迭代公式：,取x0=1,2020/7/15,二、收敛性估计,此式表明牛顿法具有平方收敛速度。,如果f(x)在一重零点附近存在连续的二阶微商，且初始值x0充分接近于 ，那么牛顿迭代法是收敛的，其收敛

15、速度为,2020/7/15,将f()在xn处作Taylor级数展开，得,略去高阶小量，然后两边同除以f(xn)，整理得,即,2020/7/15,再化简，得,两边取极限，得,所以，Newton法是二阶收敛的。,2020/7/15,1、收敛速度快，可以求重根和复根；（优点） 2、需计算导数值； （缺点）,简化牛顿法：,计算量小，但收敛速度相对较慢。,牛顿法特点：,2020/7/15, 1.4.4 Newton下山法,Newton法收敛速度快，但初值不易确定，而且往往由于初值取得不当而使迭代不收敛。,2020/7/15,但若能保证 | f (xn) | | f (xn+1) | （1）下山条件 则有可能防止迭代发散。为此先用牛顿法计算,然后引入,n=0,1,2,2020/7/15,加权平均：,合并后：,其中，为下山因子，上式称为Newton下山法。,一般由试算决定，分别取 11/2 1/22 1/23直到满足下山条件。若对于一个初值取不到满足下山条件的，则称“下山失败”，需另取初值。 |f (xn+1