《2022年非线性方程的不动点迭代方法研究 .pdf》由会员分享，可在线阅读，更多相关《2022年非线性方程的不动点迭代方法研究 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、重庆文理学院2011-2012 下学期数值方法课程论文题目：非线性方程的不动点迭代方法研究中国重庆2012 年 06 月学科专业：信息与计算科学指导教师：学生：学号：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 16 页 -摘要通过从现实的一个球体的实际问题引出对非线性方程的不动点迭代研究，在理解迭代规则1()kkpg p的基础上通过对迭代法和不动点迭代法的基本思想即找()0f x的同解变形()xg x，然后运用初值0 x 迭代，求出误差范围内的近似解1kxp。运用函数连续性证明不动点的存在性和运用中值定理和均值定理证明不动点唯一性，进而推导出不动点迭代法的推导步骤。然后又用均
2、值定理和数学归纳法证明出收敛性，并在此基础上引出误差边界。再通过对开题提出的球体问题案例的求解，进一步来加深非线性方程对不动点迭代法实证说明，由此联系到不动点迭代法在其他一些领域如物理和工程等的运用。不动点迭代式（2.2）通常只有线性收敛，有时甚至不收敛，进而在原有的基础上拓展到加速迭代法的收敛性的讨论通常，从而对Steffensen加速迭代和Aitken（埃特金）加速迭代的讨论。关键字不动点迭代；收敛性；Steffensen加速迭代；Aitken加速迭代名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 16 页 -目录1 问题的提出-1 2 算法的思想-1 2.1 迭代法的基本思
3、想-1 2.2 不动点迭代法的基本思想-2 3 算法的推导及步骤-2 3.1 算法的推导-2 3.2 算法的步骤-3 4 算法的分析-4 4.1 收敛性分析-4 4.2 误差性分析-6 4.3 稳定性分析-7 5 算法的实现-7 5.1 案例-7 5.2 求解过程-7 5.3 不动点迭代法代码及输出结果-8 6 运用举例-10 7 知识拓展-10 7.1 Steffensen加速迭代-10 7.2 Aitken（埃特金）加速迭代法-11 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 16 页 -1 1 问题的提出在现实生活当中我们会遇到很多关于诸如像球体的物理和工程问题，例如：
4、球体的半径为 r，并浸入水中，深度为d，假设这个球由由一种密度为=0.638的长叶松构成，且它的半径 r=10cm。当球浸入水中时，它的进水的质量为多少？而这些现实中的问题的解决都要涉及到求解方程的根、线性和非线性方程组以及微分方程的数值解。如上例问题的解决：当一个球以深度 d 浸入水中时，所排开水的质量wM为：2220(3)()3dxwdrdrx rdM（1.1）而球体的质量为：34/3brM（1.2）根据阿基米德定律有：bwMM（1.3）由方程（1.1）、（1.2）、（1.3）联立得：323(34)03dd rr而当 r=10,=0.638 时，方程为：23(2552 30)03dd此时这
5、个物理学中的实际问题就变为了一个3 次非线性方程23255230ydd的根，在根据具体现实情况舍去不合理的根。要解决如上的一些实际问题，就需要求解方程的根、线性和非线性方程组的解以及微分方程的解。计算机科学中的一个基本要素就是迭代，迭代技术用来求解方程的根、线性和非线性方程组的解以及微分方程的解，而不动点迭代法就是迭代法的一种基本方法。在此我们仅对非线性方程的不动点迭代进行研究。2 算法的基本思想2.1 迭代法的基本思想迭代算法是数值计算方法中一种逐次逼近的方法，首先将方程()0f x改写成某种等价的形式，由等价形式构造相应的迭代公式然后选取方程的某个初值近似名师资料总结-精品资料欢迎下载-名
6、师精心整理-第 4 页，共 16 页 -2 根ox代入公式反复校正根的近似值，直到满足精度为止。2.2 不动点迭法代的基本思想将非线性方程()0f x化为等价形式：()xx (2.1)*()()0f xxx称*x为函数()x的一个不动点，给定初始近似值ox，可以得到0()x，如此反复，构造迭代公式：(1)(),0,1,2,3.kkxxk（2.2）此处()x为迭代函数。如果对任何初值0,xa b，由（2.2）得到的序列kx有极限*limkxxx则称迭代公式（2.2）收敛，且*()xx是()x的不不动点，故（2.2）就是不动点迭代法3 算法的推导及步骤3.1 算法的推导3.1.1 不动点的存在性推
7、导及证明设g是一 个 连 续函 数，且0nnp是由 不动 点 迭 代生 成 的序 列。如 果l i mnxpp，则p是()g x的不动点。证明：如果limnxpp，则1limnxpp。根据这个结论，g的连续性和1()nnpg p存在如下关系：1()(lim)lim()limnnnxxxg pgpg ppp（3.1）因此，p是()g x的不动点。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 16 页 -3 3.1.2 不动点的唯一性推导及证明设函数,gC a b。如果对于所有,xa b，映射()yg x的范围满足,ya b，则函数g在,a b 内有一个不动点。（1）此外，设()g
8、x 定义在(,)a b内，且对于所有(,)xa b，存在正常数1K，使得，1()gKx，则函数g在,a b 内有唯一的不动点p。（2）证明：对于命题（1）如果()g aa或()g bb，则断言为真；否则()g a必须满足()(,g aa b，()g b的值必须满足(),)g ba b。表达式()()fxxg x有如下特性：()()0f aag a且()()0f bbg b对()f x应用中值定理，而且由于常量0L，可推断出存在数P,且(,)Pa b，满足()0f P。因此，()Pg P，且P是()g x 的不动点。对于命题（2）必须证明结果是唯一的。采用反证法，设存在两个不动点1P 和2P。根
9、据均值定理，可推断出存在数(,)da b，满足：2121()()()g Pg Pg dPP（3.2）根据假设，有11()gPP且22()gPP，对 3.2 式的右边进行化简可得2121()1PPg dPP但是这与命题（2）中假设在(,)a b内有1()gx矛盾，因此不可能存在两个不动点。所以，在命题（2）的假设条件下，()g x在,a b 内有一个唯一的不动点P。3.2 算法的步骤（1）确定方程()0f x的等价形式()xg x，为确保迭代工程的收敛，要求名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 16 页 -4()g x满足李普希茨条件（或()1g xq）；（2）选取初始值
10、0 x，按公式(1)(),0,1,2,3.kkxg xk进行迭代；（3）若1kkxx，则停止计算1kxx。4 算法分析4.1 收敛性分析设有：g，,gC a b；K是一个正常数；0(,)pa b；对于所有,xa b，有(),g xa b。如果对于所有,xa b，有1()gKx，则迭代1()nnpg p将收敛到唯一的不动点,Pa b。在这种情况下，P称为吸引（attractive）不动点。（3）如果对于所有,xa b，有1()gx，则迭代1()nnpg p将不会收敛到P这种情况下，P称为排斥（repelling）不动点，而且迭代显示出局部发散性。（4）批注：在命题（4）中假设0pP。因为函数g在
11、包含P的一段间隔中是连续的，可在命题（3）和命题（4）中分别利用更简单的判别条件1()gKx和1()gx。证明：对于命题（3）首先要证明点0nP都位于(,)a b内。从0p开始，根据均值定理，可推导出存在一个值0(,)ca b 满足名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 16 页 -5 1000()()()()Ppg Pg pgcPp0000()gPpK PpPpc（3.3）因此，1p 比0p 更接近P，且1(,)pa b 如图 1.一般情况下设1(,)npa b，则：1011()()()()nnPpg Pg pgcPp1111()nnnngPpK PpPpc（3.4）因
12、此，(,)npa b，而且可归纳出所有的点0nnp位于(,)a b内。图 1、P，0p，1p，0Pp 和1Pp 之间的关系为完成命题（3）的证明，需要证明如下表达式成立：lim0nxPp（3.5）首先，用归纳法的证明可建立如下不等式：0nnPpKPp（3.6）当1n时满足关系式 3.3。利用归纳假设10nnPpKPp 和关系式 3.4 的思路，可得到：110nnnnnPpK PpKKPpKPp这样，通过归纳法可以得出，所有的n满足不等式 3.6.由于01K，所以当 n趋于无穷大时，项nK趋近于 0.因此00limlim0nnnnPpKPp（3.7）0Pp 的极限压缩在左右两边的0 之间，所以可
13、得出limnnPP，且根据前面定理 3.1，迭代1()nnpg p收敛到不动点P。因此命题（3）得证。对于命题（4）首先要证明点0nP都位于(,)a b内。从0p 开始，根据均值定理，可推导出存在一个值0(,)ca b 满足：名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 16 页 -6 1000()()()()Ppg Pg pgcPp0000()gPpH PpPpc（3.8）因此，0p 比1p 更接近P，且1(,)pa b，一般情况下设1(,)npa b，则：1011()()()()nnPpg Pg pgcPp1111()nnnngPpH PpPpc（3.9）因此，(,)npa
14、 b，而且可归纳出所有的点0nnp位于(,)a b内。为完成命题（3）的证明，需要证明如下表达式成立：limnxPp（3.10）首先，用归纳法的证明可建立如下不等式：0nnPpHPp（3.11）当1n时满足关系式 3.8。利用归纳假设10nnPpHPp 和关系式 3.9 的思路，可得到：110nnnnnPpH PpHHPpHPp这样，通过归纳法可以得出，所有的 n满足不等式 3.11.由于01K，所以当 n趋于无穷大时，项nK趋近于。因此0limlimnnnnPpHPp（3.12）0Pp 的极限延伸到右边的之外，所以可得出limnnP。因此命题（4）得证。4.2 误差分析设函数g满足：g，,g
15、C a b；K是一个正常数；0(,)pa b；对于所有,xa b，有(),g xa b。当用np 去近似P时，引入误差边界如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 16 页 -7 0nnPpKPp对于所有1n01nnKPpPpK对于所有1n4.3 稳定性分析在原有不动点迭代法的基础上将原有的初始值0 x 修改为0 xx 然后按照迭代规则：(1)(),0,1,2,3.kkxg xk求出迭代通项最后比较其最后的所得值与真实值满足误差范围内内则其算法是稳定的即：1kxx5 算法实现5.1 案例在此案例就已论文开头提出的关于物理球体问题为例：球体的半径为r，并浸入水中，深度为
16、d，假设这个球由由一种密度为=0.638 的长叶松构成，且它的半径 r=10cm。当球浸入水中时，它的进水的质量为多少？5.2 求解过程当一个球以深度 d 浸入水中时，所排开水的质量wM为：2220(3)()3dxwdrdrx rdM（5.1）而球体的质量为：34/3brM（5.2）根据阿基米德定律有：bwMM（5.3）由方程（5.1）、（5.2）、（5.3）联立得：323(34)03dd rr而当 r=10,=0.638 时，方程为：23(2552 30)03dd名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 16 页 -8 此时这个物理学中的实际问题就变为了一个3 次非线性
17、方程23255230ydd的根。对于此方程的求解可以用到不动点迭代法求解。解方程步骤如下：首先有题意可知起0,20d方程2302552 30dd的等价形式为：32552()30ddg d当0,20d时：23()125522030dg dd选取初始值0 x=12然后按公式(1)(),0,1,2,3.kkxg xk进行迭代。若121(0.1)kkdd，则停止计算1kdd。5.3 不动点迭代法代码及输出结果代码：function k,p,err,P=fixpt(g,p0,tol,max1)P(1)=p0;for k=2:max1 P(k)=feval(g,P(k-1);err=abs(P(k)-P(
18、k-1);relerr=err/(abs(P(k)+eps);p=P(k);if(errtol)|(relerrtol),break,end end if k=max1 disp(maximun nuumber of iterations exceeded)end P=P;k,p,err,P=fixpt(gx,12,0.000000000001,200)输出结果：k=45 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 16 页 -9 p=11.86150150813511 err=1.007904870675702e-011 P=12.00000000000000 11.94
19、431524477928 11.91085729014850 11.89085883104665 11.87894290969856 11.87185626654913 11.86764642816162 11.86514723509375 11.86366416540031 11.86278429075393 11.86226235240524 11.86195276626302 11.86176914523977 11.86166023954459 11.86159564865799 11.86155734083855 11.86153462122358 11.86152114671514
20、 11.86151315529503 11.86150841577415 11.86150560487935 11.86150393780662 11.86150294910695 11.86150236273369 11.86150201497027 11.86150180872044 11.86150168639880 11.86150161385288 11.86150157082771 11.86150154531055 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 16 页 -10 11.86150153017696 11.86150152120160 11.861
21、50151587854 11.86150151272156 11.86150151084924 11.86150150973881 11.86150150908025 11.86150150868967 11.86150150845802 11.86150150832064 11.86150150823916 11.86150150819084 11.86150150816218 11.86150150814519 11.86150150813511 6 应用举例不动点迭代法的应用极其广泛，在物理和工程学中都有相应的运用，如：不动点迭代法在齿形系数和应力修正系数计算中的应用利用不动点迭代法求解
22、危险截面齿厚和弯曲力臂为进一步用有限元法求解齿轮的弹性变形带来便利。不动点迭代法求解是机械工程中求齿形系数和应力修正系数精度很高的一种方法，一次计算就可以求出一对相互齿合的齿轮的齿形系数和应力系数及所用迭代次数。方便实用7 知识扩展本节将在原有的不动点迭代法的基础之上进行推展到不动点迭代的加速的一些情况。7.1 Steffensen加速迭代不动点迭代式（2.2）通常只有线性收敛，有时甚至不收敛，为加速迭代法的收敛性通常可以采用Steffensen加速迭代。设*()xx是的不动点，记*kksxx，利用中值定理有：名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 16 页 -11*1
23、1*()()()kkkkkkkksxxxxsxxxx在*x与kx 之间通常()k依赖于k，若()x 变化不大，设()kC于是有：*1*21()()kkkkxxC xxxxC xx从上式消去C,则得*21*1kkkkxxxxxxxx或*221()()()kkkxxxxxx解得22*212121()22kkkkkkkkkkkkxxxxxxxxxxxxx若记2121(),0,1,2.2kkkkkkxxxxkxxx（7.1）用序列kx作为不动点*x的新近似，一般说，它比迭代法（2.2）收敛更快，实际上迭代法式（2.1）（2.2）联立可改为：21(),()(),0,1,2.2kkkkkkkkkkkyxz
24、yyxxxkzyx（7.2）称为 Steffensen迭代法，它是将来原不动点迭代（2.2）计算两次合并成一步得到，可改为另一种不动点迭代法：1(),0,1,2.kkxxk（7.3）其中2()()()2()kxxxxxxx (7.4)并有以下局部收敛定理：若*x为（7.4）定义的函数的不动点，则*x为的不动点。反之，若*x是的不动点，设*()x连续，且*()1x，则*x是的不动点且迭代法（7.3）是二阶收敛的。7.2 Aitken（埃特金）加速迭代法设*()xx是的不动点，利用中值定理有：名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 16 页 -12*101010*21212
25、1()()()()()()()()()()xxxxxxxxxxxxxxxx若()x 变化不大，则可得：12()()可推出：*01*21xxxxxxxx*1201210()2xxxxyxxx即有如下图 2 所示关系关系图 2kx 与ky 的关系进而可以得出其通项：2211221()()2kkkkkkkkkkxxxyxxxxxx然后就有如下的收敛性：*1*0limkkkyxxx超线性收敛01234 .xxxxx123 .yyy名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 16 页 -13 参考文献：1John H.Mathews,Kurtis D.Fink.数值方法（第四版）M.2010.4 2 宜春学院学报 405 期.关于加速迭代的讨论.2009.3 3 Gerald Recktenwald.数值方法和 MATLAB 实现与应用 M.2004 4 金一庆 .数值方法 M.2011 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 16 页 -