《埃特金牛顿》PPT课件.ppt

思路：构造新的迭代函数，提高收敛阶.,寻找新的迭代公式,由前面性质（定理2.1）知：,当k很大时，有,2.3.4埃特金加速法（Aitken）,原来迭代函数,解出,该式可作为一个迭代公式.令 ,则,可以证明：,具体可利用洛必塔法则（ 型）得到：,（然后将 代入得）,还可以证明：若原来 是线性收敛，则 是平方收敛；,若 是p阶( )收敛 ，则新的迭代函数 是（ 2p-1） 阶收敛。,（证明略）,2.4 牛顿法与割线法 2.4.1 牛顿法,特点： .将非线性方程转为线性方程处理； .可计算重根； .可推广到n维空间求根。,思路：设 是 的近似根,将 在 点作一阶泰勒展开,（转为线性方程）,可得迭代公式:,几何意义：迭代公式可看成 与 轴,( )的交点.（令左式中 ，即得式）,两个公式联合，可得几何意义： 表示曲线过 的切线方程与x轴,的交点作为下一个迭代点。,牛顿法也称为切线法。,只要初值点足够靠近 ，牛顿法局部收敛。,初值可通过别的方法求出。,2.4.3 收敛速度,利用前面定理判断，需计算 各阶导数及在 点处的值。,对 ，先计算各阶导数：,2.4.2 收敛性,对单根情况，设,为 的单根，可写成,(其中 ),且：,(一般地， ),由前面定理知：p=2，即2阶局部收敛，,且有：,对m重根（m2），可类似知收敛阶为1：,设 为 的m重根，即有,利用 及迭代法性质,，得,由前面定理知，对重根（m 2）是一阶局部收敛,总结：牛顿法特点：局部收敛，收敛速度快，可处理重根。,例：使用牛顿法求,在x=0.4附近根，,迭代,具体可通过,判断迭代是否结束。,要求达到4位有效数字。,2.4.4 大范围收敛性,牛顿法对初值 要求比较苛刻，要充分靠近,（可与别的方法结合）。要对初值在较大范围内收敛，,需对 附加的一些条件（充分条件）。,定理：设,在区间a,b上存在二阶连续导数，且满足,则牛顿法二阶收敛。,简要说明：和保证a,b内有唯一根，,因为在a,b内 切线不再同一侧，有可能不收敛于,，如图所示，,具体证明可见参考文献。,若保证在区间内收敛， 也可改用牛顿下山法。,保证 在a,b上是凹或凸曲线，,保证当 时, .,牛顿下山法介绍： 为防止迭代发散，可对迭代附加条件:,（1）,这样可保证收敛，称为下山法。 具体的，可将前后两次迭代计算作加权平均， 构造新的迭代公式，即,设 为迭代x+1次的结果,新迭代公式,为权因子（下山因子）,对于权因子迭取，可采用类似二分法，先取 =1， 若不能保证(1),对 减半迭取，如果仍不能保证(1) ， 则需要更换初值。,2.4.5割线法（弦截法，弦切法）,牛顿法每迭代一次需计算 ,计算量大。,可使用差商代替,，用,表示 即,所以迭代公式：,几何意义：可看成直线,（该直线斜率）与x轴（y=0）交点。,当 较复杂时，,特点：迭代需2个初值 （可取有根区间端点）；,( 可求出，不必重新计算).,不需计算导数； 计算中，每迭代1次只需求1次,收敛速度与牛顿法相比稍慢，但还是较快.,该方法也称为抛物线法（Muller法）,该方法还可推广，利用三个点构成迭代公式， 三个点可构造二次抛物线方程，,例：使用割线法求,在x=0.4附近的根，,要求达到4位有效数字（上机作业）,2.5代数方程求根的劈因子法,以上方法可计算单根、重根，都为实数根； 该方法可用来求复根。,思路：设方程 从,中分离出一个二次多项式，,( 二次方程有求根公式，可求重根和复根),为 n-2次多项式,这样可转为对,求根，关键问题是如何找 ,可使用迭代法。,即 ,可事先构造初始函数,，通过迭代，,逐步逼近 ,即对系数u,v精确化，从而得到 .,用 ，可得余式,（1）,其中,p(x),r0,r1都依赖于w(x),即与u,v有关.,可记r0=r0(u,v), r1=r1(u,v),若（r0,r1),(0,0)，,则 为满足一定精度的二次多项式.,迭代过程就是对u,v修正,令,希望：,（2）,对（2）式在（u,v）处二元函数一阶泰勒展开，得,（3）,需求解（3）式中的未知数 ,此时r0,r1已知,（用 所得余项即是）,对式两边关于v求偏导得,(此时f(x)不依赖于v, p(x),w(x),r0,r1都与v有关,p(x)= w(x)+ x +,p(x)/w(x),所得余项即为 ,同理对式两边关于u求偏导得,需求 , , , , 计算如下:,0=p(x)+ w(x)+ x+,0=xp(x)+ w(x)+ x+,用xp(x)/w(x),所得余项即为 ,利用上面系数对求,得到修正值,若u,v精度不够，可继续迭代下去，直至满足精度。,第1章 复习 作业 ：上机练习，要求二分法，牛顿法求解例子。,即xp(x)= w(x)+ x +,第三章 线性方程组数值解 3.1 问题 ：工程领域、应用问题都涉及到，,a11x1+a12x2+a1nxn=b1 an1x1+an2x2+annxn=bn,其中aij 、bi为系数，xi为未知数. 可写成矩阵形式,表示方法,方程组为,也可以写成增广矩阵,若矩阵A的行列式detA0，由克莱姆法则得xi=,其中 D=detA，Di=表示用b代替A中第i列元素的行列式值。,一般求解方法 ：,对n阶方程组：需计算n+1个n阶行列式， 而n阶行列式计算至少n！乘法 共需乘法（n+1）！,当n=20时，需5.109 次乘法，,若计算机执行速度为1010乘法/秒，也需要162年。 对大型方程组，克莱姆法则是不实用的。,其他方法求解：可分为两类 直接法. 如通过矩阵初等变换，高斯消去法,迭代法. 给定初始值，通过迭代计算，雅可比迭代法,算法分析：,3.2 消去法 3.2.1三角方程组解法,三角方程形式：,u11x1+u12x2+ +u1nxn=y1 u22x2+ +u2nxn=y2 un-1,n-1xn-1+un-1,nxn=yn-1 un,nxn =yn,写成矩阵形式： ux=y,u11 u12 u1n u22 u2n un-1,n-1 un-1,n un,n,求解 首先需 det u0 ,即uii0 (i=1,2,3,n),由最后一行往上求解：xn= yn/un,n,xn-1=( yn-1un-1,nxn)/ un-1,n-1 ,xi=(yi )/ui,i (i=n1,n2,1),此过程称为回代过程.,称为上三角矩阵,u=,乘除法：1234n=,加减法：01234n1=,3.2.2高斯消去法 利用上面回代过程求解， 利用矩阵初等变换将其转为上三角矩阵。,举例,求解方程组：,12x13x2+3x3=15 18x13x2+ x3=15 x12x2+ x3=6,运算次数：,可解得x1=1 x2=2 x3=3,高斯消去法一般过程： 记增广矩阵,=,其中,第一步消元： 将,第一列对角线一下元素消为0,设,将,的第1行乘上,（,