数值分析第四章学习小结

第四章学习小结本章为非线性方程与非线性方程组的迭代解法，由此可分为两大节4.1非线性方程的迭代解法和4.2非线性方程组的迭代解法。本章以人口增长模型为引言，由于在实际应用中只有很少类型的非线性方程能解出根的解析表达式，对于大多数非线性方程，只能用数值法求出它的根的近似值，本章将要介绍几种常用的有效的数值求根方法，它们都属于迭代法，因而还要讨论这些方法的收敛性和收敛速度。4.1.1对分法（1）基本思想：①确定方程有根的区间；②将区间逐次分半缩小，得到一个区间长度以1/2的比例减小的含根区间序列kx，在给定根的误差界时，利用长度趋于零的特点，可得到在某个区间中满足要求的近似根。收敛速度与公比为12的等比数列的收敛速度相同。(2)迭代终止条件或者(3)二分法的优缺点：优点：程序简单，总能求出近似根，对()fx要求不高。缺点：收敛速度慢，只能求单根和奇数重根，不能求偶重根，复根。二分法一般用于对根求近似根。4.1.2简单迭代法及其收敛性迭代法的基本思想:迭代法是一种逐次逼近法，用某个固定公式反复校正根的近似值，使12abx()kfx2kkba2kkkbaxs0)(xf)(xx1(),0,1,2,kkxxk之逐步精确化，最后得到满足精度要求的解。迭代法的基本思想是将隐式方程()xx的求根问题归结为计算一组显式公式1()kkxx，逐步过程实际上是一个逐步显示化的过程。收敛性：若由迭代公式1().1,2,3...kkxxk产生的序列kx收敛于x，则x是原方程的根。收敛条件：a．非局部收敛性定理：设函数()[,]xCab，在（a，b）内可导，且满足两个条件：（1）当[,]xab时，()[,]xab；（2）当[,]xab时，'()1xL，其中L为一常数。则有如下结论：（1）方程()xx在[,]ab上有唯一的根s；（2）对任取的0[,]xab，简单迭代法1()kkxx产生的序列[,]kxab且收敛于s；（3）成立误差估计式101kkLsxxxL或11kkkLsxxxL这种形式的收敛定理称为大范围收敛性定理，但当条件不够充分时，预先指定一个区间常常是不可能的。b．局部收敛性定理设'(),()ssx在包含s的某个开区间内连续。如果'()1s，则存在0当0[,]xss时，由简单迭代法1()kkxx产生的序列[,]kxss且收敛于s。4.1.3简单迭代法的收敛速度当kK（某个正整数）时，1krkece成立，则称序列kx收敛于s具有r阶收敛速度，简称kx是r阶收敛的。r的大小反映了序列kx收敛的快慢程度，r越大收敛越快。r=1时称序列线性收敛的，r=2时，为平方收敛的。线性收敛的条件：设函数()[,]xCab，'()(,)xCab，且满足如下条件：（1）当[,]xab时，()[,]xab；（2）当[,]xab时，'()1xL，其中L为一常数。则对任取的0[,]xab，简单迭代法1()kkxx产生的序列[,]kxab收敛于方程()xx在[,]ab内的唯一的根s，并且当0xs时kx是线性收敛的。m阶收敛的条件：设()(),()mssx在包含s的某个开区间内连续（2m）。如果()()()0(1,2,,1),()0imsims则存在0，当0[,]xss但0xs时，简单迭代法1()kkxx产生的序列[,]kxab以m阶收敛速度收敛于s。4.1.4迭代的加速过程1.加权迭代法:或者缺点：L值的确定需要函数的迭代信息，不便于实际应用。2．Aitken加速法：设序列kx线性收敛于s，则3.Steffensen迭代法迭代公式：,2,1,0,2)()(),(21kxyzxyxxyzxykkkkkkkkkkk),(1kkxx迭代：kkkxLLxLx11111改进：])([111kkkLxxLx121,kkkkxsxsLLxsxs121kkkkxsxsxsxskkkkkkxxxxxxs1221222)(1kx无论迭代法是否收敛于s，Steffensen迭代法都能以不低于二阶的收敛速度收敛于s。4.1.5Newton法基本思想：（1）构造法推导→，→推出迭代公式Newton法可求方程的实数根和复数根，求实数根时有明显的几何意义。当获得kx之后，过曲线()yfx上的点(,())kkxfx作该曲线的切线，此曲线与X轴相交的交点的横坐标就是Newton法迭代序列的第k+1个元素1kx，因此Newton法又称为切线法。局部收敛性定理：设s是方程()xx的根，在包含s的某个开区间内''()fx连续且'()0fx，则存在0，当0[,]xss时，由Newton法产生的序列kx收敛于s；若''()0fs且0xs，则序列kx是平方收敛的。非局部收敛性定理：设函数()fx在区间[,]ab上存在二阶连续导数，且满足条件：（1）()()0fafb；（2）''()fx在区间[,]ab上不变号；（3）当[,]xab时，'()0fx；（4）''000[,],()()0xabfxfx。则有Newton法产生的序列kx单调收敛于方程()xx在[,]ab内唯一的根s，并且至少是平方收敛的。4.1.6求方程m重根的Newton法设s是方程()xx的m重根（m2），()fx在s的某邻域内有m阶连续导数，这时()0s0)(xf0)()(xfxh()0hsxxxfxh)()(,2,1,0,)(')(1kxfxfxxkkkk(1)()()()()0,()0mmfsfsfsfs()()'()fxxxfx结论线性收敛。（2）变形的Newton法令则至少平方收敛，缺点是不知道重根的重数m。（3）若s是方程()xx的m重根，则s为的单根。迭代函数：迭代公式：优点：至少二阶收敛；缺点：计算''()fx工作量大。4.1.7割线法基本思想：用割线代替切线，用增量割线斜率11()()kkkkfxfxxx替换导数'()kfx。迭代公式几何意义：收敛性：设()0fs，在s的某邻域内''()fx连续且'()0fx，则存在0，当10,xxI时，由割线法产生的序列kx收敛于s，且收敛速度的阶至少为1.618.1(),()1sssm()()'()mfxxxfx(),()0sss()()'()fxuxfx2()()()()'()[()]()()uxfxfxgxxxuxfxfxfx12()(),0,1,2,[()]()()kkkkkkkfxfxxxkfxfxfx111()(),0,1,2,()()kkkkkkkfxxxxxkfxfx4.1.8单点割线法1.基本思想：用固定点00(,())xfx代替11(,())kkxfx，也就是点00(,())xfx永远是割线上的一点。2.迭代公式：3.几何意义：4收敛性：设函数()fx在区间[,]ab上存在二阶连续导数，且满足条件：（1）()()0fafb；（2）''()fx在区间[,]ab上不变号；（3）当[,]xab时，'()0fx；（4）01,[,]xxab且''0001()()0,()()0fxfxfxfx。则由单点割线法产生的序列kx单调收敛于方程在[,]ab内唯一的根s，并且收敛速度是一阶的。4.2非线性方程组的迭代解法4.2.1一般概念:1.非线性方程组的一般形式：向量形式2.非线性方程组的一般解法：①简单迭代法②线性化方法③求函数极小值的方法。010()(),0,1,2,()()kkkkkfxxxxxkfxfx12112212(,,,)0(,,,)0(,,,)0nnnnfxxxfxxxfxxx)()()()(21xfxfxfxFn()0Fxnxxxx21nininxxxfxxx122121)],,,([),,,(4.2.2简单迭代法设方程组：(x)=0F1.迭代公式：xG（）—迭代函数2.收敛性：非局部收敛性定理设nn:GDRR在闭区域0DD上满足两个条件：（1）G把0D映入它自身，即00G（D）D；（2）G在0D上压缩映射，即存在常数L（0,1），使对任意的0x,yD有()()GxGyLxy则有下列结论：（1）对任取的(0)0xD，由迭代公式产生的序列()0kxD，且收敛于方程内的唯一解x；（2）成立误差估计式()(1)(0)1kkLxxxxL或()()(1)1kkkLxxxxL实际计算时，可预先给定精度水平0，当迭代序列满足()(1)()kkkxxx时停止迭代，取当前的()kx作为方程组的近似解。4.2.3Newton1.基本思想将非线性方程组线性化，构造迭代格式。设00(,)xy为方程组解的一组初始近似解。11110000(,)(,)()()fffxyfxyxxyyxy22220000(,)(,)()()fffxyfxyxxyyxy2()()xFx2min()min()xFx():nnFxRR()0()FxxGx(1)()(),0,1,2,kkxGxk0),(0),(21yxyxff2.迭代公式：3.收敛性：条件：()Fx连续可微，'()Fx非奇异；结论：①kx超线性收敛于x②若()Fx二次连续可微，则kx平方收敛于x4.Newton算法5.Newton法的优缺点：优点：收敛快，一般都能达到平方收敛；缺点：对初值要求较苛刻，且要求()ifx的各个偏导数存在。4.2.4离散Newton法1.基本思想：用差商代替导数。()()()()()()()()kkkkijjiikjjfxhefxfxxh2.迭代公式：3.()kh的选取(1)保证:(2)Newton-Steffensen方法，取()()()kkjjhcFx（jc为非零常数；j=1,2，…n）（3）()kjh也可取与k无关的常数。(1)()()1()()(),0,1,2,kkkkxxFxFxk)()1()(kkkxxx)()()(1)()(kkkxFxFx)()()1(kkkxxx)()()()()(kkkxFxxF()()()()()()111111()()1()()()()()()()()()11()()1()()()()()(,)()()()()kkkkkknnkknkkkkkkkkknnnnnnkknfxhefxfxhefxhhFxJxhfxhefxfxhefxhh(1)()()()1()[(,)](),0,1,2,kkkkkxxJxhFxk()0,kjh()(),1,2,,kkjjxheDjn思考题8.设s是方程()0fx的根，4()fx在s的某个邻域内连续，并且'()0fx。令2''()()()()[]()()fxfxxxhxfxfx为使迭代法1()(0,1,)kkxxk能够至少以三阶收敛速度收敛于s，则应如何选取函数()hx？解：由定理4.4可知，至少三阶收敛速度于s。则(1)()0s，(2)()0s，(3)()0s。令'()()()fxuxfx，于是2()()()[()]xxuxhxux。通过求导可得：(2)''''(2)''''''''''2'''''''