埃特金牛顿

kkkkkk121222,1kkxkkk12解出kkkkkk22该式可作为一个迭代公式.令,则kkx122lim可以证明：具体可利用洛必塔法则（型）得到：00122limlim*k（然后将代入得）12212212222还可以证明：若原来是线性收敛，则是平方收敛；2若是p阶()收敛，则新的迭代函数是（2p-1）阶收敛。（证明略）2.4牛顿法与割线法2.4.1牛顿法特点：①.将非线性方程转为线性方程处理；②.可计算重根；③.可推广到n维空间求根。kffk0kkkfff思路：设是的近似根,将在点作一阶泰勒展开（转为线性方程）kkkff①可得迭代公式:kkkkff1kkkffy0y0y几何意义：迭代公式可看成与轴()的交点.（令左式中，即得①式）kkf,0yk1k2kf0两个公式联合，可得几何意义：表示曲线过的切线方程与x轴的交点作为下一个迭代点。牛顿法也称为切线法。只要初值点足够靠近，牛顿法局部收敛。初值可通过别的方法求出。p2.4.3收敛速度利用前面定理判断，需计算各阶导数及在点处的值。ff对，先计算各阶导数：2211ffffffffff222fffffffffff2.4.2收敛性*x0)(xf)()()(*xgxxxf对单根情况，设为的单根，可写成'*'()()()()fxgxxxgx0)(*xg∴(其中)'*(*)()0fxgx)0)((0)('**xfx∵∴且：0)(')('')(''***xfxfx0)(''*xf(一般地，)∴由前面定理知：p=2，即2阶局部收敛，且有：)(')(''21)(''21!)(lim**)(12xfxfxpxeepkkk对m重根（m≥2），可类似知收敛阶为1：*x0)(xf()()(),mfxxxgx()0gx设为的m重根，即有∴)(')()()()('1xgxxxgxxmxfmm)(')()()()()(')()()()()()(')()(1xgxxxmgxgxxxxgxxxgxxmxgxxxxfxfxxmmmxx)(()()'()limxxxxxxx利用及迭代法性质，得'()x()()()()'()limxxxxgxxxmgxxxgxxxmxgxxxmgxgxx11)(')()()(1lim∴由前面定理知，对重根（m≥2）是一阶局部收敛总结：牛顿法特点：局部收敛，收敛速度快，可处理重根。01)1()(2xxxf例：使用牛顿法求在x=0.4附近根，)13)(1()('xxxf)13)(1(1)1()(')(21kkkkkkkkkxxxxxxfxfxx4.00x4656.0x∴迭代具体可通过411021kkxx判断迭代是否结束。要求达到4位有效数字。0xxxf2.4.4大范围收敛性牛顿法对初值要求比较苛刻，要充分靠近（可与别的方法结合）。要对初值在较大范围内收敛，需对附加的一些条件（充分条件）。xf0fafb定理：设在区间[a,b]上存在二阶连续导数，且满足①②0,xfbax时，③保号时，xfbax,④abfbfbbafafa,则牛顿法二阶收敛。xfxfxbaxk,baxk,1简要说明：①和②保证[a,b]内有唯一根，因为在[a,b]内切线不再同一侧，有可能不收敛于，如图所示，具体证明可见参考文献。若保证在区间内收敛，也可改用牛顿下山法。③保证在[a,b]上是凹或凸曲线，④保证当时,.牛顿下山法介绍：为防止迭代发散，可对迭代附加条件:)(1kxf|()|kfx（1）这样可保证收敛，称为下山法。具体的，可将前后两次迭代计算作加权平均，构造新的迭代公式，即1kx1kx)()(/kkkxfxfx设为迭代x+1次的结果kkkxxx)1(111,0,新迭代公式为权因子（下山因子）对于权因子迭取，可采用类似二分法，先取=1，若不能保证(1),对减半迭取，如果仍不能保证(1)，则需要更换初值。2.4.5割线法（弦截法，弦切法）kxfxfxf牛顿法每迭代一次需计算,计算量大。xf11,,,kkkkxxxfxfkxfkkkkkxfxxxfxf11可使用差商代替，用表示即所以迭代公式：111kkkkkkkxfxfxxxfxxkkxxxfy)(11)()(kkkkxxxfxf几何意义：可看成直线（该直线斜率）与x轴（y=0）交点。当较复杂时，21,xx)(xf)(1kxf特点：迭代需2个初值（可取有根区间端点）；(可求出，不必重新计算).不需计算导数；计算中，每迭代1次只需求1次xy0x1x2x*x收敛速度与牛顿法相比稍慢，但还是较快.该方法也称为抛物线法（Muller法）该方法还可推广，利用三个点构成迭代公式，三个点可构造二次抛物线方程，011)(2xxxf例：使用割线法求在x=0.4附近的根，要求达到4位有效数字（上机作业）2.5代数方程求根的劈因子法以上方法可计算单根、重根，都为实数根；该方法可用来求复根。0.......)(110nnnaxaxaxf)(xf**2*vxuxxw思路：设方程从中分离出一个二次多项式，)()(**xpxwxfxp*(二次方程有求根公式，可求重根和复根)为n-2次多项式xw*xw*这样可转为对求根，关键问题是如何找,可使用迭代法。即,vuxxxw2xw*xw*可事先构造初始函数，通过迭代，逐步逼近,即对系数u,v精确化，从而得到.)(/)(xwxf10rxrr10)(rxrxwxpxf用，可得余式（1）其中,p(x),r0,r1都依赖于w(x),即与u,v有关.可记r0=r0(u,v),r1=r1(u,v),xw若（r0,r1)(0,0)，则为满足一定精度的二次多项式.,uuuvvv迭代过程就是对u,v修正,令希望：0,0,10vvuurvvuur（2）对（2）式在（u,v）处二元函数一阶泰勒展开，得ovvruurrovvruurr111000（3）vu,需求解（3）式中的未知数,xwxf此时r0,r1已知,（用所得余项即是）()pxvvr0vr1对①式两边关于v求偏导得(此时f(x)不依赖于v,p(x),w(x),r0,r1都与v有关()pxvvr0vr1∴－p(x)=w(x)+x+vr0vr1∴－p(x)/w(x),所得余项即为,同理对①式两边关于u求偏导得ur0vr0ur1vr1需求,,,,计算如下:0=p(x)+w(x)+x+()pxuur0ur10=xp(x)+w(x)+x+()pxuur0ur1ur0ur1∴用－xp(x)/w(x),所得余项即为,vu,利用上面系数对③求,得到修正值,若u,v精度不够，可继续迭代下去，直至满足精度。第1章复习作业：上机练习，要求二分法，牛顿法求解例子。即－xp(x)=w(x)+x+第三章线性方程组数值解3.1问题：工程领域、应用问题都涉及到，a11x1+a12x2+…+a1nxn=b1………………………an1x1+an2x2+…+annxn=bn其中aij、bi为系数，xi为未知数.可写成矩阵形式nnnnnnnnbbbbxxxxaaaaaaaaaA2121212222111211,,表示方法∴方程组为Axb也可以写成增广矩阵bAAnnnnnnnbbbaaaaaaaaa21212222111211若矩阵A的行列式detA≠0，由克莱姆法则得xi=DDi其中D=detA，Di=表示用b代替A中第i列元素的行列式值。一般求解方法：对n阶方程组：需计算n+1个n阶行列式，而n阶行列式计算至少n！乘法∴共需乘法（n+1）！当n=20时，需5.109次乘法，1910若计算机执行速度为1010乘法/秒，也需要162年。∴对大型方程组，克莱姆法则是不实用的。其他方法求解：可分为两类①直接法.如通过矩阵初等变换，高斯消去法②迭代法.给定初始值，通过迭代计算，雅可比迭代法算法分析：3.2消去法3.2.1三角方程组解法三角方程形式：u11x1+u12x2+…+u1nxn=y1u22x2+…+u2nxn=y2………………un-1,n-1xn-1+un-1,nxn=yn-1un,nxn=yn写成矩阵形式：u·x=yu11u12…u1nu22…u2nun-1,n-1un-1,nun,n求解①首先需detu≠0,即uii≠0(i=1,2,3…,n)②由最后一行往上求解：xn=yn/un,nxn-1=(yn-1－un-1,nxn)/un-1,n-1…………………nijjijxu1xi=(yi－)/ui,i(i=n－1,n－2,…,1)此过程称为回代过程.称为上三角矩阵u=2)1(nn2)1(nn乘除法：1＋2＋3＋4＋…＋n=加减法：0＋1＋2＋3＋4＋…＋n－1=3.2.2高斯消去法利用上面回代过程求解，利用矩阵初等变换将其转为上三角矩阵。举例,求解方程组：12x1－3x2+3x3=1518x1－3x2+x3=15－x1－2x2+x3=6运算次数：)67()23()121(23121342945470215272301533126121151318153312rrrrrr6121151318153312可解得x1=1x2=2x3=3高斯消去法一般过程：记增广矩阵)1(A)1(1n)1(n(1)2(1)1)1(1n2)1(n2)1(22)1(21)1(1n1)1(n1)1(12)1(11nnnnaaaaaaaaaaaaiiiji