第2章非线形方程及其非线性方程组解法.

1第二章方程(组)的迭代解法§1引言§2迭代解法§3迭代公式的改进§4联立方程组的迭代解法§5联立方程组的延拓解法§6联立方程组的牛顿解法2求f(x)=0的根§1引言1.1涉及到的概念f(x)既可以是代数多项式,也可以是超越函数f(x)=a0xn+a1xn-1+…+an-1x+an(a0≠0)如三角函数,指数函数的复合函数等方程的根:满足f(x)=0的x重根和单根:如果f(x)=(x-)mg(x)且g()≠0,则称为f(x)=0的m重根.m=1称为单根,m1称为重根.3§1引言1.2本章重点介绍求方程实根的迭代解法(适用于求解代数方程和超越方程)代数方程:根的个数与其最高次数相同,有成熟的圈定根的方法超越方程:可能有一个,几个根或者无解,无固定的圈定根的方法4§2迭代解法1本节重点（关键问题）根的初值的确定方法；迭代法的求解过程迭代法的收敛性迭代序列的误差估计5§2迭代解法2.1根的初值确定方法求方程根的几何意义:求曲线y=f(x)与x轴交点的横坐标。求根的具体步骤为:确定根的初值x0将x0进一步精确到所需要的精度62.1根的初值确定方法定理2.1设f(x)为区间[a,b]上的单值连续函数如果:f(a)·f(b)0(2.1)则:[a,b]中至少有一个实根。如果:f(x)在[a,b]上还是单调地递增或递减，则:仅有一个实根(有单根的条件)ba72.1根的初值确定方法2.1.1画图法画出y=f(x)的略图,从而看出曲线与x轴交点的大致位置。也可将f(x)=0分解为1(x)=2(x)的形式,1(x)与2(x)两曲线交点的横坐标所在的子区间即为含根区间.1.具体步骤82.1根的初值确定方法2.1.1画图法2.实例已知:f(x)=x㏒x–1=0;求根的初值范围(1)可以改写为:㏒x=1/x(2)画出对数曲线y=㏒x,与双曲线y=1/x,它们交点的横坐标位于区间[2,3]内解:92.1根的初值确定方法2.1.1画图法xy1gxy023yx1102.1根的初值确定方法2.1.2扫描法1.原理对于给定的f(x)，设有根区间为[A,B],从x0=A出发，以步长h=(B-A)/n(n是正整数)，在[A,B]内取定节点：xi=x0＋ih(i=0，1，2，…，n)，从左至右检查f(xi)的符号，如发现xi与端点xi-1的函数值异号，则得到一个缩小的有根子区间［xi-1,xi］。关键是选取步长hh太小，资源耗费大；h过大，可能遗漏根。112.1根的初值确定方法2.1.3对分(二分)法1.具体步骤若f(r)·f(a)0，取a=r；否则取b=r设[xk-1,xk]为含根子区间，初值对于根的误差要求为ε,令a=xk-1,b=xk,计算出f(a),f(b)后,进行如下:取[a,b]的中点r=(a+b)/2,计算f(r)若b-aε,转向Begin;否则结束Begin:122.1根的初值确定方法2.1.3对分(二分)法abx1x2abx*132.1根的初值确定方法2.1.3对分(二分)法14误差分析：第1步产生的21bax有误差21abx*||x第k步产生的xk有误差kkabx*||x2对于给定的精度,可估计二分法所需的步数k：2lnlnln2εabkεabk①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)0。15f(x)=0x=φ(x)等价变换思路:2.2迭代法的求解过程f(x)的根φ(x)的不动点由公式f(x)=0出发将其分解为等价形式x=φ(x)2.2.1建立迭代公式迭代函数例如：f(x)=x3+2x2-4=0可以分解为:x=x+f(x)=x3+2x2+x-4;x=2(1/(2+x))1/2x=x-(x3+2x2-4)/(3x2-4x)162.2迭代法的求解过程2.2.2迭代解法(简单迭代法)由初值x0出发,按迭代函数xn+1=φ(xn)(n=0,1,2,…)进行计算迭代公式x0,x1,x2,…,xn,称为迭代序列；迭代序列的值相应地称为根的0次,1次,2次,…,n次近似值；序列的计算过程称为迭代过程；如果序列x0,x1,x2,…收敛于,即nnxlim则为方程的根.证明：)()lim()(limlim1nnnnnnxxx172.2迭代法的求解过程例2.2：用迭代法求方程f(x)=x3-x-1=0在x=1.5附近的根，要求根的近似值稳定至小数点后5位.解:(1)将方程改写为x=(1+x)1/3(2)按上式建立迭代公式xn+1=(1+xn)1/3x0=1.5(3)取x0=1.5逐次迭代得:x1=1.35721,x2=1.33086,x3=1.32588,x4=1.32494,x5=1.32476,x6=1.32473,x7=1.32472,x8=1.32472(4)最后取稳定至小数后５位的迭代值x8=1.32472为方程的根18xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1192.3迭代法的收敛性1.影响迭代法收敛性的要素迭代函数在根附近的性态初值的选取范围2.迭代法收敛的类型大范围收敛:从任何可取的初值出发都能保证收敛局部收敛:为了保证收敛性必须选取初值充分接近于所要求的根注：这里讨论迭代法的收敛性时，均指的是局部收敛性局部收敛方法比大范围收敛方法收敛得快202.3迭代法的收敛性3.合理的求根算法先用一种大范围收敛方法求得接近于根的近似值(如对分法)再以其作为新的初值使用局部收敛法(如迭代法)4.迭代收敛的条件定理2.2定理2.3定理2.421证明：因α为根,式α=φ(α)恒成立.设x0与α的误差为|x0-α|,则以后各次近似值的误差为:0101)(')()(xxx1212)(')()(xxxnnnnxxx)(')()(11………...01211'''xxnn则条件(1)定理2.2()',[,]xqxab21条件：结论：(1)φ(x)在包含根α的区间[a,b]上可微对任何x0[a,b],迭代过程xn+1=φ(xn)一定收敛k+1kx-aq=max(k=0,1,,n)x-a其中,22证明：011xqxnn根据条件(2)必有0,0,11nnnximqn时当迭代过程收敛得证该定理的条件是充分条件q值等于新旧迭代值之误差比,即对旧误差的缩小率.q愈小,新近似值逼近就愈快一般认为，q1/10,收敛比较快，q1/2,收敛慢在实际应用时,因φ’(x)连续且[a,b]较小,φ’(x)的值变化不大,可用|φ’(x0)|1代替|φ’(x)|123定理2.3)10()()()2(2121LxxLxx条件：结论：(1)φ(x)在区间[a,b]上连续对任何x0[a,b],迭代过程xn+1=φ(xn)一定收敛设迭代序列收敛，如果存在正数r和c，使得cxximnnn1成立，则称该迭代序列是r阶收敛的，或称迭代序列收敛的阶为r，c为渐近误差常数收敛阶数:新近似值的误差与旧近似值误差的r次方成正比24cxximnnn1收敛阶数:r=1线性收敛r=2平方收敛r1超线性收敛2.3迭代法的收敛性r反映了迭代过程的收敛速度,r越大绝对误差缩减得越快,即方法收敛得越快,它是衡量迭代法好坏的重要标志不同的迭代法具有不同的收敛阶数25定理2.4条件：结论：(1)φ(x)在根α附近有r阶连续导数迭代过程xn+1=φ(xn)是r阶收敛的该定理提供了测定收敛阶的方法!(2)φ’(α)=φ’’(α)=…=φ(r-1)(α)=0,及φ(r)(α)≠026上界公式1:2.4迭代序列的误差估计1.迭代终止条件|xn+1-α|ε,xn+1即为所求得的近似值2.引申迭代终止条件(上界公式)nnnxxqqx111证明:)()(1nnxx)()()()(11nnnxxx))(('))(('1211nnnxxx)()()()(11nnnxxx(2.3.1)()xq127))((')()('11112nnnxxxnnnxxx1211)('1)('nnxxqq112.4迭代序列的误差估计讨论nnnnnxxxxqqx1111时当210)(qa11qq,有式(2.3.1)可以简化为:成立能够保证||1nxnnxx1当成立,282.4迭代序列的误差估计讨论可以统一表示为：则，当只能要求时，当),,21(]21,0(11,1121)(11qqqqxxxxqqqqqbnnnn21,210,11qqlxxaxnnn绝对误差限292.4迭代序列的误差估计按相对误差限来控制1111nnnnnxxxxx有的问题中还采用两种误差限并存控制（P36）302.4迭代序列的误差估计讨论的情况时，有可能出现假收敛当1)(qcyx0lxn+1xny2(x)=φ(x)y1(x)=x312.4迭代序列的误差估计总结qqq12121εn1nlxxn1n1qxxlq使用绝对误差限来控制出现假收敛的现象32上界公式2:2.4迭代序列的误差估计证明:011xxqqxnn21121'11nnnnxxqqxxqq2121nnxxqq011xxqqn||11nnnxxqqx(上界公式1)证毕332.4迭代序列的误差估计上界公式2可用来预估迭代次数n当成立,011xxqqn||1nx必成立lnqnnqxx101qxxqnnln)1(01两边取对数可得:342.4迭代序列的误差估计上界公式3:,|'()|,[,]nnfxxmfxxabm0有为精确解，所以,0fnnxffxfnnxfxfmxffxfxnnn证明:证毕由公式3可知:,)(时当mxfn成立就有nx用|f(xn)|ε作为迭代终止的判据352.4迭代序列的误差估计讨论当时,1)(xf当时,1)(xfmxfn)(|f(xn)|ε可以将其作为迭代终止的判据.1mfxfxnn因为ε1ε,所以迭代终止时的xn值的误差不一定能保证小于ε当|f’(xn)|1时,2ffxfxn因为ε2ε,所以迭代终止时的xn值的误差比实际要求的误差要求ε小，因而产生不必要的迭代运算。362.4迭代序列的误差估计例2.3：对下列方程x-sinx=0.25,用迭代法,取三位小数计算其近似根,并估计其误差.方程可变形为x=sinx+0.25由作图法可粗略知α[0.9,1.5]因为φ(x)=sinx+0.25,φ’(x)=cosx当0.9x1.5时有|φ’(x)|≤cos0.9≈0.62=q1所以迭代过程收敛。取x0=1.2、xn+1=sinxn+0.25