第二章,非线性方程的数值解法

本文格式为Word版，下载可任意编辑——第二章,非线性方程的数值解法其次章非线性方程的数值解法NumericalSolutionsofNonlinearEquations本章主要内容1二分法2不动点迭代的构造及其收敛性判定重点3Newton和Steffensen迭代重点4割线法5非线性方程组的迭代解法历史背景求方程几何意义根本定理假设函数在上连续且那么至少有一个数使得若同时的一阶导数在内存在且保持定号即或那么这样的在内唯一1二分法Bisection原理若fCab且fafb0那么f在ab上至少有一实根根本思想逐步将区间分半通过判别区间端点函数值的符号进一步探寻有根区间将有根区间缩小到充分小从而求出得志给定精度的根的近似值以此类推终止法那么x1x2abWhentostop或不能保证x的精度二分法算法给定区间ab求fx0在该区间上的根x输入a和b容许误差TOL最大对分次数Nmax输出近似根xStep1Setk1Step2Computexfab2Step3WhilekNmaxdosteps46Step4IfxTOLSTOPOutputthesolutionxStep5Ifxfa0SetbxElseSetaxStep6Setkk1Computexfab2GoToStep3Step7OutputthesolutionofequationxSTOP3由二分法的过程可知4对分次数的计算公式12令误差分析解例1用二分法求方程在区间上的根误差限为问至少需对分多少次简朴对fx要求不高只要连续即可无法求复根及偶重根收敛慢注用二分法求根最好先给出fx草图以确定根的约莫位置或用探寻程序将ab分为若干小区间对每一个得志fakfbk0的区间调用二分法程序可找出区间ab内的多个根且不必要求fafb02迭代法的理论TheoryofIterationfx0xgx迭代函数思路从一个初值x0启程计算x1gx0x2gx1xk1gxk若收敛即存在x使得且g连续那么由可知xgx即x是g的不动点也就是f的根看起来很简朴令人有点不相信那么问题是什么呢如何判定这种方法是收敛的呢fx的根gx的不动点一不动点迭代FixedPointIteration几何意义下面选取5种迭代格式法1法4法3法2法5Lipschitz条件成立的充分条件证明gx在ab上存在不动点令有根不动点唯一反证若不然设还有那么而当k时xk收敛到xL越收敛越快可用来操纵收敛精度小注条件II可改为在ab得志Lipschitz条件定理结论依旧成立定理23算法不动点迭代给定初始近似值x0求xgx的解输入初始近似值x0容许误差TOL最大迭代次数Nmax输出近似解x或失败信息Step1Seti1Step2WhileiNmaxdosteps36Step3Setxgx0计算xiStep4Ifxx0TOLthenOutputx告成STOPStep5SetiStep6Setx0x更新x0Step7OutputThefailedafterNmaxiterations不告成STOP当x很大时此处可改为二局部收敛性LocalConvergence注解局部收敛性特点假定解存在且断定存在解的一个邻域使得对其中全体初始值由迭代生成的序列收敛于解半局部收敛特点不知道解存在但指出要从得志确定通常很强条件的初始值启程保证收敛于某一邻近解全局整体收敛断定在全空间或至少其中一个很大的片面中无论从何处启程都能保证收敛于一个解证明由于在的某邻域连续存在邻域即对那么由定理23迭代法对收敛即局部收敛注例3已知方程在15邻近有根把方程写成三种不同的等价形式1对应迭代格式2对应迭代格式3对应迭代格式判断迭代格式在的收敛性选一种收敛格式计算精确到小数点后其次位解1迭代格式收敛2迭代格式收敛3迭代格式发散选择2计算01234151481147314691467注1的大小反映了迭代法收敛的快慢是收敛速度的一种度量2设迭代函数得志收敛定理的条件那么产生的序列得志假设在或的邻域有若取必有此时有证明由Taylor公式充分性取极限得必要性设迭代式是阶收敛的那么有即且反证法设结论不成立那么存在最小正整数得志情形一情形二由充分性证明知迭代式是阶收敛的即与阶收敛冲突证明方法与情形一类似自己练习一使用两个迭代值的组合方法3迭代收敛的加速方法Accelerating将xgx等价地改造为当和时有相应的迭代公式为或者选取特殊的有可能使迭代加速如迭代公式为几何意义如图示注1这种迭代对原迭代公式的各近似值在根的两侧往复地趋于时较为有效又如新的迭代函数为根据定理25知迭代法至少是二阶的但由于不知道故也得不到因此可取其的近似值即从而有二Steffensen斯蒂芬森加速迭代法三个迭代值组合或者若令Steffensen迭代法的优点可以提升收敛速度有时也能把不收敛的迭代法提升为收敛的二阶方法艾特肯Aitken加速方法下面选取3种迭代格式显示计算结果证明设斯蒂芬森Steffensen的迭代为其中设那么反之设型洛比塔法那么由Taylor公式那么上式中用替换即证代入上述结果返回4牛顿法NewtonRaphson一牛顿迭代公式的推导1待定参数法不动点迭代的关键是构造得志收敛条件的迭代函数一种自然的选择是令为了加速不动点迭代的收敛过程应尽可能使迭代函数在处有更多阶导数等于零定理25令取因此选取迭代函数NewtonRaphson迭代格式称之为牛顿拉夫森方法简称牛顿法原理将非线性方程线性化取x0x将fx在x0做一阶Taylor开展在x0和x之间2Taylor开展法Taylorsexpansion将xx02看成高阶小量那么有解等价于求方程的正根解法一等价于求方程的正根解法二等价于求方程的正根证明Newtons事实上是一种特殊的不动点迭代其中那么收敛由Taylor开展在单根simpleroot邻近收敛快只要那么令可得结论Th25有根根唯一产生的序列单调有界保证收敛证明由于fC2ab由1和2知fx在ab内有唯一根下面由条件12分4种处境议论仅证明第一种处境其它处境类似议论由中值定理使得由另一方面由Taylor开展得介于之间重复以上过程可得归纳法自己证因此数列单调下降且有下界令由Taylor开展得注Newtons收敛性凭借于x0的选取xTh29中条件3的几何意义证明仿照Th29重根multipleroot加速收敛法Q1若Newtons是否仍收敛设x是f的n重根那么且由于Newtons事实上是一种特殊的不动点迭代其中那么A1有局部收敛性但重数n越高收敛越慢Q2如何加速重根处境时的收敛速度A2将求f的重根转化为求另一函数的单根令那么f的重根的单根求复根FindingComplexRootsNewton公式中的自变量可以是复数记zxiyz0为初值同样有设代入公式令实虚部对应相等可得5弦割法与抛物线法SecantandParabola割线secantline切线斜率割线斜率需要2个初值x0和x1Newtons每一步要计算f和为了制止计算导数值现用f的值近似从而得到弦割法割线法x2一弦割法收敛速度介于NewtonandBisection之间例1证明方程在区间内有唯一根且使得对任意的初始值由割线法产生的序列都收敛于证明令方程存在根方程存在唯一根Muller方法的思想来源于弦割法利用3个已知点构造一条抛物线取其与x轴的交点构造下一次迭代值x二抛物线法Muller几何图示xk1Muller方法的概括实现设已知三个点那么过上述三个点的抛物线方程为取该抛物线与x轴的交点作为下一次迭代值即然后取新的相邻的三次迭代值重复上述过程即为Muller方法Muller方法中抛物线根的计算方法首先要将抛物线化为模范形式引入新的变量将上述变量代入前面的抛物线方程得其中的两个零点为取的两个零点中靠近的那个零点那么有Muller方法的迭代公式为概括计算步骤见教材P39算法Muller方法给定初始近似值x0x1x2求fx0的根输入初值x0x1x2容许误差TOL输出近似解xStep1Seti1Step4Ift4x2x1TOLStep2dosteps37thenOutputxSTOPStep3Computet3x2x1x1x0Step5S