第7章非线性方程求根

第7章非线性方程求根方程是在科学研究中不可缺少的工具方程求解是科学计算中一个重要的研究对象几百年前就已经找到了代数方程中二次至五次方程的求解公式但是,对于更高次数的代数方程目前仍无有效的精确解法对于无规律的非代数方程的求解也无精确解法因此,研究非线性方程的数值解法成为必然设非线性方程--------(1)本节主要研究单根区间上的求解方法一、简单迭代法(基本迭代法)--------(2)将非线性方程(1)化为一个同解方程继续--------(3)称(3)式为求解非线性方程(2)的简单迭代法则称迭代法(3)收敛,否则称为发散--------(4)如果将(2)式表示为与方程(2)同解收敛例1.解:(1)将原方程化为等价方程发散显然迭代法发散(2)如果将原方程化为等价方程仍取初值x2=0.9644x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000依此类推,得已经收敛,故原方程的解为同样的方程不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?迭代函数的构造有关定理1.--------(5)--------(6)--------(7)(局部收敛性)证:由条件(1)由根的存在定理,由由微分中值定理证毕.定理1指出,由(6)式,只要因此,当迭代就可以终止,只要构造的迭代函数满足此时虽收敛但不一定是唯一根--------(8)例2.用迭代法求方程的近似解,精确到小数点后6位解:本题迭代函数有两种构造形式因此采用迭代函数d1=0.1000000d2=-0.0105171d3=0.1156e-002d4=-0.1265e-003d5=0.1390e-004d6=-0.1500e-005d7=0.1000e-006由于|d7|=0.1000e-006<1e-6因此原方程的解为x7=0.090525x1=0.1000000x2=0.0894829x3=0.0906391x4=0.0905126x5=0.0905265x6=0.0905250x7=0.0905251由定理1的(7)式出,迭代法收敛就越快定义1.--------(9)不可能直接确定定理2.

例3.为线性收敛证明:所以例4.至少是平方收敛的由定义1注意例4与例3的迭代法是相同的,两例有何区别?证明:令则所以由定理2该迭代法至少是平方收敛的二、Newton迭代法如果将非线性方程令化为等价方程如果令即则于是取--------(10)--------(11)--------(12)(12)式称为Newton迭代法参见例4，可知Newton迭代法至少平方收敛局部收敛性例5.用Newton迭代法求方程的根:解:由Newton迭代法x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553迭代四次精度达10-8

Newtonddf.mNewton迭代法需要求每个迭代点处的导数复杂！--------(12)--------(13)这种格式称为简化Newton迭代法精度稍低三、Newton迭代法的变形则Newton迭代法变为--------(14)这种格式称为弦截法收敛阶约为1.618几何意义例6.用简化Newton法和弦截法解例(5)中方程的根，解:由简化Newton法并和Newton迭代法比较由弦截法x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化Newton法由弦截法要达到精度10-8

简化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次无论前面哪种迭代法：Newton迭代法简化Newton法弦截法Newton迭代法x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关如x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010x5=0收敛发散--------(15)这种方法称为Newton下山法，例7.解:1.先用Newton迭代法x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205迭代13次才达到精度要求2.用Newton下山法,结果如下k=0x0=-0.99fx0=0.666567k=1x1=32.505829f(x)=11416.4w=0.5x1=15.757915f(x)=1288.5w=0.25x1=7.383958f(x)=126.8w=0.125x1=3.196979f(x)=7.69w=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1w=0.5x2=2.60928f(x)=3.31w=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000四、多根区间上的逐次逼近法有唯一根有多根所有根均为单根有重根用迭代法求解然后在每个区间上判断是否有根若成立统计根的个数则所有的有根区间均为单根区间则继续对分区间,并重新判断直到找到所有根的所在区间然后在每个有根区间进行求根可得一系列的小区间和中点小区间中点显然每个小区间都有单根搜索法—二分法例8.解:由于可知方程的解在区间[0,10]内将区间[0,10]等分成三等份[0,3.33][3.33,6.67][6.67,10][0,3.33]内至少有一个根[5,6.67][3.33,5]将[3.33,6.67]再分成两个区间[5,6.67]内至少有一个根[3.33,5]内至少有一个根[0,3.33][5,6.67][3.33,5]因此找到了三个有单根的区间依此类推结果为对分故有且由例3.对于Newton迭代法趋于零Newton迭代法也只是线性收敛此时Newton迭代法可能不收敛考察函数而应该用定义求导Tailor展开所以由定理2，迭代法至少是二阶收敛二、非线性方程迭代法的加速对于迭代法上式的迭代函数令迭代改变量即求导并令----(9)得因此有松弛迭代法:--------(10)从后面的例子可以看出,加速效果是明显的甚至一些不收敛的迭代法经过松弛加速后也能收敛不方便中值定理差商近似代替导数即于是可以得到迭代格式:其中-------(11)上组公式称为Altken公式或Altken加速将(11)式综合后可得一个解析式表示的迭代法:----(12)上式称为Steffensen迭代法Altken公式与Steffensen公式是等价的加速效果也是很明显的例2中将比较不同加速方法例2.对迭代格式进行加速解方程组解:x0=0.5x1=0.375x2=0.3509115x3=0.3477369x4=0.3473496x5=0.3473028x6=0.3472971x7=0.3472964(1)直接使用迭代格式迭代7次,得到满足精度的解(2)对迭代格式进行松弛加速x0=0.5x1=0.3333333x2=0.3472222x3=0.3472964x4=0.3472964迭代4次,得到满足精度的解(3)对迭代格式进行Altken加速(11)式x0=0.5x1=0.3451613x2=0.3472961x3=0.3472964迭代3次,得到满足精度的解从以上3种结果可见,迭代法加速技术效果比较明显迭代格式显然不收敛x0=1.5x1=1.5350706x2=1.5321124x3=1.5320889x4=1.5320889迭代4次,得到满足精度的解对迭代格式进行松弛加速x=1.5x=1.5333333x=1.5320906x=1.5320889x=1.5320889迭代4次,得到满足精度的解对迭代格式进行Altken加速可见加速技术可能将不收敛的迭代法加速为收敛§3Fixed-PointIteration改进、加速收敛/*acceleratingconvergence*/

待定参数法：若

|g’(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果