数值分析第四章学习小结.doc

第四章学习小结本章为非线性方程与非线性方程组的迭代解法，由此可分为两大节4.1非线性方程的迭代解法和4.2非线性方程组的迭代解法。本章以人口增长模型为引言，由于在实际应用中只有很少类型的非线性方程能解出根的解析表达式，对于大多数非线性方程，只能用数值法求出它的根的近似值，本章将要介绍几种常用的有效的数值求根方法，它们都属于迭代法，因而还要讨论这些方法的收敛性和收敛速度。4.1.1对分法（1）基本思想：确定方程有根的区间；将区间逐次分半缩小，得到一个区间长度以1/2的比例减小的含根区间序列，在给定根的误差界时，利用长度趋于零的特点，可得到在某个区间中满足要求的近似根。收敛速度与公比为的等比数列的收敛速度相同。(2)迭代终止条件 或者 (3)二分法的优缺点：优点：程序简单，总能求出近似根，对要求不高。缺点：收敛速度慢，只能求单根和奇数重根，不能求偶重根，复根。二分法一般用于对根求近似根。4.1.2简单迭代法及其收敛性迭代法的基本思想:迭代法是一种逐次逼近法，用某个固定公式反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的解。 迭代法的基本思想是将隐式方程的求根问题归结为计算一组显式公式，逐步过程实际上是一个逐步显示化的过程。收敛性：若由迭代公式产生的序列收敛于，则是原方程的根。收敛条件：a非局部收敛性定理：设函数，在（a，b）内可导，且满足两个条件：（1）当时，；（2）当时，其中L为一常数。则有如下结论：（1）方程在上有唯一的根s；（2）对任取的，简单迭代法产生的序列且收敛于s；（3）成立误差估计式或这种形式的收敛定理称为大范围收敛性定理，但当条件不够充分时，预先指定一个区间常常是不可能的。b局部收敛性定理设在包含s的某个开区间内连续。如果，则存在当时，由简单迭代法产生的序列且收敛于s。4.1.3简单迭代法的收敛速度当（某个正整数）时，成立，则称序列收敛于s具有r阶收敛速度，简称是r阶收敛的。r的大小反映了序列收敛的快慢程度，r越大收敛越快。r=1时称序列线性收敛的，r=2时，为平方收敛的。线性收敛的条件：设函数，且满足如下条件：（1）当时，；（2）当时，其中L为一常数。则对任取的，简单迭代法产生的序列收敛于方程在内的唯一的根s，并且当时是线性收敛的。m阶收敛的条件：设在包含s的某个开区间内连续（）。如果则存在，当但时，简单迭代法产生的序列以m阶收敛速度收敛于s。4.1.4 迭代的加速过程1.加权迭代法: 或者缺点：L值的确定需要函数的迭代信息，不便于实际应用。2Aitken加速法：设序列线性收敛于s，则 3.Steffensen迭代法迭代公式：无论迭代法是否收敛于s， Steffensen迭代法都能以不低于二阶的收敛速度收敛于s。4.1.5 Newton法基本思想：（1）构造法 推导 ， 推出迭代公式 Newton法可求方程的实数根和复数根，求实数根时有明显的几何意义。当获得之后，过曲线上的点作该曲线的切线，此曲线与X轴相交的交点的横坐标就是Newton法迭代序列的第k+1个元素，因此Newton法又称为切线法。局部收敛性定理：设s是方程的根，在包含s的某个开区间内连续且，则存在，当时，由Newton法产生的序列收敛于s；若且，则序列是平方收敛的。非局部收敛性定理：设函数在区间上存在二阶连续导数，且满足条件：（1）；（2）在区间上不变号；（3）当时，；（4）。则有Newton法产生的序列单调收敛于方程在内唯一的根s，并且至少是平方收敛的。 4.1.6求方程m重根的Newton法设s是方程的m重根（），在s的某邻域内有m阶连续导数，这时结论 线性收敛。（2）变形的Newton法令 则 至少平方收敛，缺点是不知道重根的重数m。（3）若s是方程的m重根，则s为 的单根。迭代函数：迭代公式：优点：至少二阶收敛；缺点：计算工作量大。4.1.7割线法基本思想：用割线代替切线，用增量割线斜率替换导数。迭代公式几何意义：收敛性：设，在s的某邻域内连续且，则存在，当时，由割线法产生的序列收敛于s，且收敛速度的阶至少为1.618.4.1.8单点割线法1.基本思想：用固定点代替，也就是点永远是割线上的一点。2.迭代公式：3.几何意义：4收敛性：设函数在区间上存在二阶连续导数，且满足条件：（1）；（2）在区间上不变号；（3）当时，；（4）且。则由单点割线法产生的序列单调收敛于方程在内唯一的根s，并且收敛速度是一阶的。4.2非线性方程组的迭代解法4.2.1一般概念:1.非线性方程组的一般形式： 向量形式2.非线性方程组的一般解法：简单迭代法线性化方法求函数极小值的方法。 4.2.2简单迭代法 设 方程组： 1.迭代公式： 2.收敛性：非局部收敛性定理设在闭区域上满足两个条件：（1）G把映入它自身，即；（2）G在上压缩映射，即存在常数，使对任意的有则有下列结论：（1）对任取的，由迭代公式产生的序列，且收敛于方程内的唯一解；（2）成立误差估计式或实际计算时，可预先给定精度水平，当迭代序列满足时停止迭代，取当前的作为方程组的近似解。4.2.3 Newton1.基本思想将非线性方程组线性化，构造迭代格式。设 为方程组解的一组初始近似解。2.迭代公式：3.收敛性：条件：连续可微，非奇异；结论：超线性收敛于若二次连续可微，则平方收敛于4.Newton算法 5.Newton法的优缺点：优点：收敛快，一般都能达到平方收敛；缺点：对初值要求较苛刻，且要求的各个偏导数存在。4.2.4离散Newton法1.基本思想：用差商代替导数。2.迭代公式：3.的选取(1)保证:(2)Newton-Steffensen方法，取（为非零常数；j=1,2，n）（3）也可取与k无关的常数。思考题8.设s是方程的根，在s的某个邻域内连续，并且。令为使迭代法能够至少以三阶收敛速度收敛于s，则应如何选取函数？解：由定理4.4可知，至少三阶收敛速度于s。则，。令，于是。通过求导可得：9.试分别用割线法和单点割线法求方程的根，要求。解：令，所以。（1）割线法：迭代公式由于，在只有一个根。取，则算到即可。（2）单点割线法，满足定理4.9的4个条件：（1）； （2）当；（3）；（4）且取，由单点割线法产生的迭代公式由单点割线法产生的序列单调收敛于方程在内唯一的根。结果为2.查阅其他参考书，寻找用牛顿法求解多项式方程根的特殊方法，再找一种加权法。解: (1)Newton法1.基本思想将非线性方程组线性化，构造迭代格式。设 为方程组解的一组初始近似解。2.迭代公式：3.收敛性：条件：连续可微，非奇异；结论：超线性收敛于若二次连续可微，则平方收敛于4.Newton算法 5.Newton法的优缺点：优点：收敛快，一般都能达到平方收敛；缺点：对初值要求较苛刻，且要求的各个偏导数存在。(2)离散Newton法1.基本思想：用差商代替导数。2.迭代公式：3.的选取(1)保证:(2)Newton-Steffensen方法，取（为非零常数；j=1,2，n）（3）也可取与k无关的常数。(3)简化牛顿法:简化牛顿法，也称平行弦法. 其迭代公式为:迭代函数:若在根附近成立，即取,则迭代法局部收敛. 在中取，则称为简化牛顿法，这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与X轴交点作为的近似值. (4)牛顿下山法牛顿法收敛性依赖初值的选取,如果偏离所求根较远，则牛顿法可能发散.为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性: 满足这项要求的算法称下山法. 将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果 与前一步的近似值适当加权平均作为新的改进值, 其中 称为下山因子,即称为牛顿下山法. 选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件成立为止. 任玉杰习题2.81.用抛物线法求方程的一个实根的近似值，使精确到。解：（1）用作图法确定初始值在MATLAB工作窗口输入x=-2:0.001:2;y=2.*x.3-5.*x-1;plot(x,y);grid,gtext(y=2x3-5x-1)运行后得出图形1-1，可知区间内有一个实根，故取初值（2）建立名为fnq.m的M文件function y=fnq(x) y=2.*x.3-5.*x-1;图1-1（3）保存名为paowu.m的M文件(4)在MATLAB工作窗口输入k,piancha,xdpiancha,xk,yk=paowu(-0.25,0,-0.5,1e-6,1e-6,100)（5）运行后输出结果为提示：根的判别式值为正数.ans=1.0000 0.2500 0.5000 -0.2022 -0.0058提示：根的判别式值为正数.ans=2.0000 0.0478 0.2367 -0.2034 0.0000提示：根的判别式值为正数.ans=3.0000 0.0012 0.0060 -0.2034 -0.0000提示：根的判别式值为正数.ans=4.0000 0.0000 0.0000 -0.2034 0提示：根的判别式值为正数.ans=5.0000 0.0000 0.0000 -0.2034 0k=5piancha=1.1558e-010xdpiancha=5.6836e-010xk=-0.2034yk=0即，迭代k =5次，得到精度为的根的近似值xk=-0.2034，其函数值为yk=0，xk的相邻最小偏差为piancha=1.1558e-010，其相对误差为xdpiancha=5.6836e-010.表1-11.00000.25000.5000-0.2022-0.00582.00000.04780.2367-0.20340.00003.00000.00120.0060-0.2034-0.00004.00000.00000.0000-0.203405.00000.00000.0000-0.203402.用抛物线法求方程的全部实根，精确到。解：（1）用作图法确定初始值在MATLAB工作窗口输入x=-5:0.0001:5;y=x.3-x+5;plot(x,y);grid,gtext(y=x3-x+5)运行后得出图形2-1，可知区间内有一个实根，故取初值（2）建立名为fnq.m的M文件function y=fnq(x) y=x.3-x+5;图2-1（3）保存名为paowu.m的M文件(4)在MATLAB工作窗口输入k,piancha,xdpiancha,xk,yk=paowu(-2,-1,-3,1e-9,1e-9,100)（5）运行后输出结果为提示：根的判别式值为正数.ans=1.0000 1.0000 0.3333 -1.9129 -0.0865提示：根的判别式值为正数.ans=2.0000 0.0871 0.0455 -1.9042 -0.0007提示：根的判别式值为正数.ans=3.0000 0.0086 0.0045 -1.9042 0.0000提示：根的判别式值为正数.ans=4.0000 0.0001 0.0000 -1.9042 -0.0000提示：根的判别式值为正数.ans=5.0000 0.0000 0.0000 -1.9042 0提示：根的判别式值为正数.ans=6.0000 0.0000 0.0000 -1.9042 0k=6piancha=4.4409e-016xdpiancha=2.3322e-016xk=-1.9042yk=0即，迭代k =6次，得到精度为的根的近似值xk=-1.9042，其函数值为yk=0，xk的相邻最小偏差为piancha=4.4409e-016，其相对误差为xdpiancha=2.3322e-016.表2-11.0000 1.00000.3333-1.9129-0.08652.0000 0.08710.0455-1.9042-0.00073.0000 0.00860.0045-1.90420.00004.0000 0.00010.0000-1.9042-0.00005.0000 0.00000.0000-1.904206.0000 0.00000.0000-1.904203.求曲线与曲线之间的最小垂直距离处的x值，精确到小数点后10位。解：令，距离最小处即求的最小值，故处即可能为最小值点。（1）用作图法确定初始值在MATLAB工作窗口输入x=-5:0.0001:5;y=cos(x)-2.*x-1/5;plot(x,y);grid,gtext(y=cos(x)+2x-1/5)运行后得出图形3-1，可知区间内有一个实根，故取初值（2）建立名为fnq.m的M文件function y=fnq(x) y=cos(x)+2*x-0.2;（3）保存名为paowu.m的M文件(4)在MATLAB工作窗口输入k,piancha,xdpiancha,xk,yk=paowu(0.5,1,0,1e-9,1e-9,100)（5）运行后输出结果为提示：根的判别式值为正数.ans=1.0e+015 * 0.0000 0.0000 2.2518 -0.0000 -0.0000提示：根的判别式值为正数.ans=2.0000 0.3754 1.0000 -0.3668 -0.0000提示：根的判别式值为正数.ans=3.0000 0.0086 0.0234 -0.3667 0.0000提示：根的判别式值为正数.ans=4.0000 0.0000 0.0000 -0.3667 0.0000提示：根的判别式值为正数.ans=5.0000 0.0000 0.0000 -0.3667 0.0000k=5 piancha=7.0561e-010xdpiancha=1.9240e-009xk=-0.