第四章解非线性方程的迭代法.

设线性方程组36225124321321321xxxxxxxxx(1)写出Jacobi法和SOR法的迭代格式(分量形式);(2)讨论这两种迭代法的收敛性.(3)取初值x(0)=(0,0,0)T,若用Jacobi迭代法计算时,预估误差x*-x(10)(取三位有效数字).课堂练习(2)因为A是严格对角占优矩阵,但不是正定矩阵,故Jacobi法收敛,SOR法当01时收敛.解(1)Jacobi法和SOR法的迭代格式分别为216131525151412141)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx)216131()525151()412141()(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx(3)由(1)可见B=3/4,且取x(0)=(0,0,0)T,经计算可得x(1)=(1/4,-2/5,1/2)T,于是x(1)-x(0)=1/2,所以有113.05.075.0175.0110)0()1()10(*xxBBxxk如(x)=3x5-2x4+8x2-7x+1第4章解非线性方程的迭代法本章讨论求非线性方程(x)=0(4.1)的根的问题。其中(x)是高次多项式函数或超越函数。如果存在，使得()＝0，则称是方程(x)=0的根,(x)=e2x+1-xln(sinx)-2等等。或称是函数(x)的零点。如果(x)满足：(x)=(x-)mh(x),其中h(x)在x=处连续且h()0,称是方程(x)=0的m重根。如果方程(x)=0在区间[a,b]上有根,则称[a,b]为方程(x)=0的有根区间。若(x)在处充分可导,则是(x)=0的m重根等价于：()=()=…=(m-1)()=0,(m)()0设(x)在区间[a,b]上连续且(a)(b)0,根据连续函数的介值定理,区间[a,b]上必有方程(x)=0的根。0yxy=(x)ab如果函数(x)在区间[a,b]上又是单调的,则方程(x)=0在区间[a,b]上有唯一根。m=1时,称是方程(x)=0的单根。123§1.1简单迭代法的一般形式§1简单迭代法首先把方程(x)=0改写成等价(同解)形式x=(x)(4.2)得到迭代序列{xk},如果xk,取一个合适的初始值x0，然后作迭代xk+1=(xk),k=0,1,2,…(4.3)这种求方程根的方法称为简单迭代法，或逐次逼近法。则有=(),即是方程(x)=0的根。其中(x)称为迭代函数,式(4.3)称为迭代格式。若迭代序列{xk}收敛,则称简单迭代法是收敛的。,建立迭代格式解改写原方程为等价方程求方程x3-2x-3=0在[1,2]内的根.例1332xx3123,0,1,2,kkxxk如果取初值x0=1.9,计算得：kxkkxk0123451.91.894536471.893521141.893332331.893297221.89329069678910…1.893289471.893289251.893289211.893289201.89328920……由计算结果有|x10－x9|10-8,因此可取x10。方程也可改写成x=(x3-3)/2,建立迭代格式xk+1=(xk3-3)/2,k=0,1,2,…仍取初值x0=1.9,则有x1=1.9295,x2=2.0917,x3=3.0760,x4=13.0529可见,xk,此迭代格式是发散的。§1.2简单迭代法的收敛条件及收敛阶首先，对任意初值x0[a，b]，(x)应使产生的序列{xk}[a,b],即(x)的值域落在定义域内。另外,从几何上看:xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2xoyy=xy=(x)x0x1x2x4x30(x)1-1(x)0(x)1(x)-11.a(x)b,x[a,b];定理4.1设迭代函数(x)C1[a,b],且满足则迭代格式xk+1=(xk),k=0,1,2,…,x0[a,b]都收敛于方程x=(x)在区间[a,b]的唯一根，且11kkkxxLLx011xxLLxkkLxxLkln)1(ln01可见,|xk-xk-1|充分小可保证|xk-|充分小,2.|(x)|L1,x[a,b]而且对任一0,要使|xk-|,只要证记(x)=(x)-x,则(a)=(a)-a0,|xk+1-xk|=|(xk)-(xk-1)||xk-|=|(xk-xk＋1)+(xk+1-)||xk-xk+1|+|xk+1-|L|xk-xk-1|+L|xk-|11kkkLxxxL101kLxxL于是有：(b)=(b)-b0,由(x)的连续性,必存在[a,b]使()=()-=0,即=(),又(x)=(x)-10,所以x=(x)的根唯一。=|()(xk-xk-1)|L|xk-xk-1||xk+1-|=|(xk)-()|=|()(xk-)|L|xk-|求方程xex-1=0在0.5附近的根,精度要求=10-3。解可以验证方程xex-1=0在区间[0.5,0.61]内仅有一个根。例2改写方程为x=e-x,建立迭代格式,2,1,0,1kexkxk由于(x)=e-x,在[0.5,0.61]上有|(x)|e-0.50.61，且(x)[0.5,0.61]，所以迭代法收敛。取x0=0.5,得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065所以,取近似根x10=0.56691满足精度要求。如果精度要求为=10-5,则由LxxLkln)1(ln0195.196.0ln10653.0104.0ln5可知,需要迭代20次。实际上,方程在区间[0.55,0.6]上有唯一根，而在区间[0.55,0.6]上有|(x)|e-0.550.581。若取L=0.58，则有注意：这里迭代次数20是充分的但不是必要的。LxxLkln)1(ln0150.4210lnln0.5818.60.10653可知,只需迭代19次。推论若=(),(x)在附近具有一阶连续导数,且|()|1，则存在0，当x0I=[-，+]时，迭代格式xk+1=(xk),k=0,1,2,…都收敛于方程x=(x)在区间I上的唯一根。实际上，由连续性可知,存在L0，0，使对任何xI=[-，+]都有|(x)|L1.而且，对任何xI=[-，+]，都有|(x)-|=|(x)-()|=|()(x-)|L|x-|即(x)I=[-，+]。由定理4-1可见，结论成立。这时的迭代方法称为局部收敛的。定义4.1设迭代序列xk收敛于,记误差ek=xk-,如果存在正实数p和非零常数C,使得或Ceepkkk1lim|xk+1-|C|xk-|p,k1则称序列xk是p阶收敛的,称p是收敛阶,C是渐近误差常数。p=1称为线性收敛;p1称超线性收敛;p=2称平方收敛。设(x)充分光滑,由于|ek+1|=|xk+1-|=|(xk)-()|=|(k)||ek|所以,当()0时,有0|)(|)(limlim1kkkkkee于是此时,迭代法是m阶收敛的。所以,当()0时,简单迭代法只具有线性收敛。设()=()=…=(m-1)()=0,但(m)()0,由于|ek+1|=|xk+1-|=|(xk)-()|mkkmem)(!1)(0|)(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx))((!1))(()!1(1))((21))(()()()(1)1(2下面介绍Aitken加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。假设(1)(2)，则有由于xk+1-=(1)(xk-)xk+2-=(2)(xk+1-)121kkkkxxxx即(xk+1-)2(xk-)(xk+2-)xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2解得kkkkkkxxxxxx122122kkkkkkxxxxxx12212)(分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根。(=1.585471802)要比序列{xk}更快地收敛于,可构造如下的Aitken加速算法:则,序列注意,如果第k步发生zk-2yk+xk=0,就终止计算,取xk。如果记kkkkkkkxxxxxxx12212)(ˆkxˆ,2,1,0,2)(21kxyzxyxxkkkkkkk)(kkxy)(kkyz例3解用迭代公式：k简单迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078取x0=/2,计算结果如下:xk+1=1.6+0.99cosxk，k＝0，1，2，…Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组。§2Newton迭代法§2.1Newton迭代公式设(x)在有根区间[a,b]上二阶连续可导,x0是根的某个近似值,因为200000)(2)())(()()(xxfxxxfxfxf取(x)(x0)+(x0)(x-x0),方程(x)=0近似为(x0)+(x0)(x-x0)=0若(x0)0,其解为)()(0001xfxfxx得到根的新的近似值x1,一般地,在xk附近线性化方程为(xk)+(xk)(x-xk)=0设(xk)0,其解为)4.4(,2,1,0,)()(1kxfxfxxkkkk迭代格式(4.4)称为Newton迭代法.xyox0y=(x)x1x2直线y=(x0)+(x0)(x-x0)就是y-(x0)=(x0)(x-x0)Newton迭代法也叫切线法.Newton迭代法相当于取迭代函数§2.2Newton迭代法的收敛性)()()(xfxfxx的简单迭代法.因为222)]([)()()]([)()()]([1)(xfxfxfxfxfxfxf