非线性方程数值法.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第二章 非线性方程的数值解法,,,/*,Numerical Solutions of Nonlinear Equations,*/,本章主要内容：,,1,、二分法,,2,、不动点迭代的构造及其收敛性判定,（重点）,,3,、,Newton,和,Steffensen,迭代,（重点）,,4,、割线法,,5,、非线性方程组的迭代解法,,历史背景,,代数方程的求根问题是一个古老的数学问题理论上， 次代数方程在复数域内一定有 个根,(,考虑重数,),早在,16,世纪就找到了三次、四次方程的求根公式，但直到,19,世纪才证明大于等于,5,次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个一般也不存在根的解析表达式因此需要研究数值方法求得满足一定精度要求的根的近似解求方程 几何意义,基本定理,如果函数 在 上连续，且,,则至少有一个数 使得 ，若同时 的一阶导数 在 内存在且保持定号，即,(,或,),则这样的 在 内唯一。

a,b,x*,,§1,二分法,,/* Bisection Method */,原理：,若,f,,C[,a,,,b,],，,且,f,(,a,) ·,f,(,b,) < 0,，,则,f,,在,(,a,,,b,),上至少有一实根基本思想：,逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求,,出满足给定精度的根 的近似值以此类推,,终止法则？,a,b,x,1,x,2,a,b,When to stop?,或,不能保证,,x,,的精度,x*,,2,x,x*,,二分法算法,,给定区间,[,a,,,b,],,，求,f,(,x,)=0,,在该区间上的根,x,.,,输入,:,,a,和,b,;,容许误差,,TOL,;,最大对分次数,,N,max,.,,输出,:,,近似根,x,.,,Step 1,Set,k,= 1,;,,Step 2 Compute,x=f,(,(a+b)/2,),;,,Step 3,While (,k,,N,max,) do steps 4-6,,Step 4 If,|,x|,,<,TOL,,,,STOP,;,Output,the solution,x,.,,Step 5,If,x,*,f,(,a,),<0,,,Set,b=x,;,,,Else,Set,,a=x,;,,Step 6,Set,k=k+,1,;,Compute,x=f,(,(a+b)/2,),;,Go To,,Step 3 ;,,Step 7,Output,the,solution,of equation,:,,x,;,STOP,.,,3,、,由二分法的过程可知：,4,、,对分次数的计算公式：,1,、,2,、,令,误差,,分析,,,解,：,例,1,：,用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？,,①,简单,;,,②,,对,f,(,x,),,要求不高,(,只要连续即可,) .,①,无法求复根及,偶重根,,②,收敛慢,,注：,用二分法求根，最好先给出,f,(,x,),,草图以确定根的大概位置。

或用搜索程序，将,[,a,,,b,],分为若干小区间，对每一个满足,f,(,a,k,)·,f,(,b,k,) < 0,的区间调用二分法程序，可找出区间,[,a,,,b,],内的多个根，且不必要求,f,(,a,)·,f,(,b,) < 0,优点,缺点,,§2,迭代法的理论,,/* Theory of Iteration,,Method,*/,f,(,x,) = 0,x,=,g,(,x,),（,迭代函数）,等价变换,思路,从一个初值,x,0,出发，计算,x,1,=,g,(,x,0,),,x,2,=,g,(,x,1,), …,,x,k,+1,=,g,(,x,k,),, …,若 收敛，即存在,x,*,使得,,,，且,g,连续，则由 可知,x,* =,g,(,x,* ),，即,x,*,是,g,的,不动点，也就是,f,,的根看起来很简单，令人有点不相信，那么问题是什么呢？,如何判定这种方法是收敛的呢？,f,(,x,),的根,g,(,x,),的不动点,一、不动点迭代,,/*,Fixed-Point Iteration*/,,x,y,y = x,x,y,y = x,x,y,y = x,x,y,y = x,x*,x*,x*,x*,y=g,(,x,),y=g,(,x,),y=g,(,x,),y=g,(,x,),x,0,p,0,x,1,p,1,,x,0,p,0,x,1,p,1,,x,0,p,0,x,1,p,1,,x,0,p,0,x,1,p,1,,几何意义,,例,2,：,已知方程 在 上有一个根（正根）,下面选取,5,种迭代格式：,1,、,即,2,、,即,3,、,即,4,、,即,5,、,即,,取,计算结果如下：,法1,法4,法3,法2,法5,,Lipschitz,条件成立的充分条件,,,,,,,,,考虑方程,x,=,g,(,x,),,若,( I ),当,x,[,a,,,b,],时，,g,(,x,),[,a,,,b,],；,,( II ), 0 ,L,< 1,使得,,对,,x,[,a,,,b,],成立。

则任取,x,0,[,a,,,b,],，,由,x,k,+1,=,g,(,x,k,),得到的序列 收敛于,g,(,x,),在,[,a,,,b,],上的,唯一不动点并且有误差估计式：,,,(,k,= 1, 2, … ),且,存在极限,连续时,,证明：,①,g,(,x,),在,[,a,,,b,],上存在不动点？,令,有根,②,不动点唯一？,反证：若不然，设还有 ，则,在,和,之间而,③ 当,k,, ,时，,,x,k,收敛到,x,*,？,,,,,L,越 收敛越快,可用 来控制收敛精度,,④,,⑤,,⑥,,小,注：,条件,( II ),可改为,在,[,a,,,b,],满足,Lipschitz,条件,,,定理结论仍然成立,(,定理,2.3,’,),算法,:,不动点迭代,,给定初始近似值,,x,0,,，求,x,=,g,(,x,),,的解,.,,输入,:,,初始近似值,,x,0,;,容许误差,,TOL,;,最大迭代次数,,N,max,.,,输出,:,,近似解,x,,或,失败信息,.,,Step 1,Set,i,= 1;,,Step 2,While (,i,,N,max,) do steps 3-6,,,Step 3,Set,x,=,g,(,x,0,);,/*,计算,x,i,*/,,,Step 4,If |,x,,x,0,| <,TOL,then Output (,x,);,/*,成功*,/,,STOP;,,,Step 5,Set,i,++;,,,Step 6,Set,x,0,=,x,;,/*,更新,x,0,*/,,Step 7,Output (,The method failed after,,N,max,,iterations,);,/*,不成功 *,/,,STOP.,当,x,很大时，此处可改为,,,二、局部收敛性,/*,Local Convergence*/,（,局部收敛性,,）,若存在 的不动点 的一个闭邻域,,对任意的 ，由迭代法 产生的序列 均收敛于 ，则称该迭代法局部收敛。

注解,:,,局部收敛性特点：,假定解存在，且肯定存在解的一个邻域，使得对其中所有初始值，由迭代生成的序列收敛于解半局部收敛特点：,不知道解存在，但指出要从满足一定（通常很强）条件的初始值出发，保证收敛于某一（临近）解全局（整体）收敛：,肯定在全空间或至少其中一个很大的部分中，无论从何处出发，都能保证收敛于一个解设 为 的不动点， 在 的某邻域连续，,,且 ，则迭代法,(*),局部收敛证明：,因为 在 的某邻域连续，,存在邻域,即对,则由,定理,2.3,’,，迭代法,(*),对 收敛，即局部收敛,.,注,,,例,3,：,已知方程 在,1.5,附近有根，把方程写成三,,,种不同的等价形式,(1),对应迭代格式 ；,,,(2),对应迭代格式 ；,(3),对应,,,迭代格式,;,判断迭代格式在 的收敛性，选,,,一种,收敛格式,计算，精确到小数点后,第二位,解：,（,1,） ， ，迭代格式收敛；,（,2,） ， ，迭代格式收敛；,（,3,） ， ，迭代格式发散。

选择,(2),计算,,,0 1 2 3 4,,1.5 1.481 1.473 1.469 1.467,,（,收敛阶,/*the order of Convergence*/,),设序列 收敛到 ， ，若存在实数 及常,,,数,，,使,,,则称序列 是 阶收敛的，,,,称为渐近误差常数当 且 时， 称为线,,,性收敛， 为超线性收敛， 时为平方或二次收敛,.,注,:,（,1,）,的大小反映了迭代法收敛的快慢，是收敛速度,,的一 种度量,;,,,（,2,）,设,迭代函数 满足收敛定理的条件，则产生的序列满足 ，如果在 或 的邻域有,,若取 ，必有 ，此时有,,,,,设迭代法的迭代函数 的高阶导数 在不,,动点 的邻域里连续，则式（*）是 阶收敛的充要条件,,,是,,,且,证明：,由,Taylor,公式：,充分性,取极限得,,必要性,设迭代式（*）是 阶收敛的，则有,即,且,（,反证法,）设结论不成立,则,存在最小正整数,满足,情形一,情形二,由,充分性证明知,，迭代式（*）是 阶收敛的,即,而,的,极限不存在,与 阶收敛矛盾,证明方法与情形一类似,（自己练习）,,一、,使用两个迭代值的组合方法：,§3,迭代收敛的加速方法,,/*,A,ccelerating,,Method,*/,本节讨论,迭代法加速收敛问题，常用于,线性收敛,迭代法,,将,x,=,g,(,x,),,等价地改造为,当 和 时，有,相应的迭代公式为,或者,选取特殊的 ，有,可能,使迭代,加速,。

x,y,y = x,y,=,g,(,x,),x,*,如：,迭代公式为,几何意义,如图示,注：,,(1),这种迭代对,原迭代公式,(*),的各近似值在根 的,两侧往复,地趋于 时较为有效,；,中点,(2),只有,且 较大时，加速效果才明显又如：,新的迭代函数为,当,时,根据,定理,2.5,知，迭代法至少是,二,阶的,.,,但由于,不知道,，故 也,得不到,，因此可取其 的,近似值,，即,从而有,,二、,Steffensen,(,斯蒂芬森,),加速迭代法,：（,三个,迭代值组合）,x,y,y = x,y,=,g,(,x,),x,*,,x,0,从初值 出发，计算出,在曲线 上得到,,两个点,用直线连接 、 两点它与 的交点设为,点的坐标为,将 视为,新的初值,，重复上述步骤,,,一般地,，,由 组合得到迭代式,或者,这个方法称为斯蒂芬森,(,Steffensen,),迭代方法,,,若令,则得到斯蒂芬森,(,Steffensen,),迭代法的另一种形式：,,Steffensen,迭代法的优点：可以改进收敛速度，有时也能把,不收敛,的迭代法改进为,收敛,的二阶方法,.,艾特肯（,Aitken,）加速方法：,,例,4,：,已知方程 在 上有一个根（正根）,下面选取,3,种迭代格式：,1,、,即,2,、,即,3,、,即,显示计算结果,,,设不动点迭代 的迭代函数 在其不动点,,的某邻域内具有二阶连续导数，,,则斯蒂芬森,(,Steffensen,),的迭代技术是二阶收敛的，而,,且其极限仍为 。

证明：,设斯蒂芬森,(,Steffensen,),的迭代为,其中,首先证明有 相同的不动点,设,则,,,反之,，设,型,洛比塔法则,,,其次证明,Steffensen,迭代是,二阶,收敛的,由,Taylor,公式：,在 处展开,则,上式,中用 替换,即证,,代入上述结果：,,注意：,对本来就是,P,(>1),阶收敛的方法，,,改用,Stefensen,迭代方法优点不多取,计算结果如下：,法2,原迭代次数,29,法3,原来,不收敛,法1,原来,不收敛,返回,,,§4,牛顿法,,/* Newton - Raphson Method */,一、牛顿迭代公式的推导,1,、,待定参数法,不动点迭代的,关键,是构造满足,收敛条件,的,迭代函数,,一种,自然的选择,是令,为了加速不动点迭代的收敛过程，应尽可能使迭代函数 在 处有,更多阶导数等于零,（定理,2.5,）令,现设,,,取,满足,,因此，选取迭代函数,Newton –,Raphson,迭代格式,称之为,牛顿,—,拉夫森,方法，简称,牛顿法,原理：,将非线性方程,线性化,取,x,0,,,x*,，,将,f,(,x,),在,x,0,,做一阶,Taylor,展开,:,，,,在,x,0,,和,x,,之间,2,、,Taylor,展开法,/* Taylor’s expansion Method */,,将,(,x*,,,x,0,),2,,看成,高阶小量,，则有：,x,y,x*,x,0,,只要,f,,,C,1,，,每一步迭代都有,,,而且 ，则,,x,*,就是,f,,的根。

与,x,轴交点的横坐标,,无开方运算，又无除法运算例,1,：,写出求 的,Newton,迭代格式；,,写出求 的,Newton,迭代格式,,,要求公式中既,解：,,等价于求方程 的正根,,解法一：,等价于求方程 的正根,,,解法二：,等价于求方程 的正根,,Th2.7,,（,局部收敛性,）,,设,x,*,,为方程,f,(,x,) =0,的根，在包含,x,*,的某个开区间内 连续， 且,，则,存在,x,*,的,邻域 ，使得任取初值 ，由,Newton’s Method,产生的序列 以不低于,二阶,的收敛速度收敛于,x,*,，且,,证明：,Newton’s Method,,事实上是一种,特殊的不动点迭代,,其中 ，则,收敛,由,Taylor,展开：,在,单,根,,/*simple root */,,附近收敛快,,只要,，则,令,,可得结论。

Th2.5,,有根,根,唯一,产生的序列,单调有界,保证收敛,证明：,因为,f,,,C,2,[,a,,,b,],，,由（,1,）和（,2,）知,f,(,x,),在,[,a,,,b,],内有,唯一,根,下面由条件（,1,）、（,2,）分,4,种情况讨论：,,,,,仅证明,第一种,情况，其它情况类似讨论,Th2.8,,（,收敛的充分条件,）,设,f,(,x,),=0,,且,f,,,C,2,[,a,,,b,],，,若,,(1),f,(,a,),f,(,b,) < 0,；,(2),在整个,[,a,,,b,],上 不变号且,,；,,(3),选取,x,0,,,[,a,,,b,],,使得,；,,则,Newton’s Method,产生的序列,{,x,k,},,收敛于方程的根,,,且,,由,中值定理， 使得,因此,即 在 上单调递增,由,另一方面，由,Taylor,展开得,介于 、 之间,,重复以上过程，可得（,归纳法,）,（自己证）,因此，数列 单调下降且有下界,令,由,Taylor,展开得,,注：,Newton’s Method,,收敛性依赖于,x,0,,的选取。

x,*,x,0,,x,0,,x,0,Th2.9,,（,收敛的另一充分条件,）,设,,,在,[,a,,,b,],上连续，,,(1),,f,(,a,),f,(,b,) < 0,；,(2),,在整个,[,a,,,b,],上 且,,；,,(3),,，,,则对 ，,Newton’s Method,产生的序列,{,x,k,},,收敛于方,,程 在,[,a,,,b,],内,的唯一实根 且,,Th2.9,中条件,（,3,）,的,几何意义,,保证数列 单调递增且有上界,证明仿照,Th2.9,,改进与推广（,补充,）,,/* improvement and generalization */,,重根,,/* multiple root */,,加速收敛法：,Q1:,,若　　　 ，,Newton’s Method,,是否仍收敛？,设,x,*,是,f,,的,n,,重根，则： 且 因为,Newton’s Method,,事实上是一种特殊的不动点迭代，,,其中 ，则,A1:,,有局部收敛性，但重数,n,,越高,，收敛,越慢,。

Q2:,,如何,加速,重根情况时的收敛速度？,A2:,,将求,,f,,的,重根转化,为求另一函数的,单根,,令　　　　　，则,f,,的重根,=,,,,的单根,求复根,,/* Finding Complex Roots */,,——,Newton,,公式中的自变量可以是,复数,记,z,=,x,+,i y,,,z,0,,为初值，同样有,设,代入公式，令,实、虚部对应相等,，可得,,,§5,弦割法与抛物线法,,,/* Secant Method and,Parabola Method,,*/,x,0,x,1,割线,,,/* secant line */,切线斜率,,,,割线斜率,需要,2,个初值,x,0,,和,x,1,Newton’s Method,,每一步要计算,f,,和 ，为了避免计算导数值，现用,f,,的值近似 ，从而得到,弦割法,（,割线法,）x,2,一、弦割法,,Th2.10,,,局部收敛性,,设,表示区间 ，,x,*,为方程,f,(,x,) =0,的根， 函数,f,(,x,),在,,中有,足够阶连续导数,， 且 满足,则对 ，由割线法产生的序列 都收敛于,x,*,，且,(i),,(ii),,(iii),,其中,收敛速度介于,Newton,and,Bisection,,之间,,,Corollary,(,推论,),设,x,*,,为方程,f,(,x,) =0,的,一个根， ， 且 在,x,*,,的,附近连续，则 使得 由,Secant,,,Method,产生的序列 都收敛于,x,*,。

例,1,,证明方程 在区间 内有,唯一,根 ，且,,,使得对任意的初始值 ，由,割线法,产生的序列 都收敛于 证明：,令,方程,存在,根,方程存在,唯一,根,且,在 附近连续,由,推论,知，由,割线法,产生的序列 都收敛于 ,,x,k-2,Muller,方法的思想来源于,弦割法,:,利用,3,个已知点构造一条抛物,,线,,,取其与,x,轴的交点构造下一次迭代值,.,x,*,二、抛物线法,(,Muller,),几何图示,x,k,x,k-1,x,k+1,,,,Muller,方法的具体实现,:,设已知三个点,则过上述三个点的,抛物线方程,为,:,取该抛物线与,x,轴的交点作为下一次迭代值,,,即,然后取新的相邻的三次迭代值重复上述过程,,,即为,Muller,方法,.,,,,Muller,方法中抛物线根的计算方法,:,首先要将抛物线化为,规范形式,:,引入新的变量,,将上述变量代入前面的抛物线方程,,,得,其中,的两个零点为,:,,取 的两个零点中靠近 的那个零点,,,则有,,Muller,方法的迭代公式为,:,具体计算步骤见教材,P,39.,,,,算法,:,Muller,方法,,给定初始近似值,,x,0,,，,x,1,,，,,x,2,,,求,f,(,x,),,=0,的根,.,,输入,:,,初值,,x,0,，,x,1,，,,x,2,;,容许误差,,TOL,.,,输出,:,,近似解,x,.,,Step 1,Set,i,= 1;,Step 4,If |t,4,(,x,2,-,x,1,) | <,TOL,,Step 2,,do steps 3-7,,then Output (,x,);,,STOP,;,,,Step 3,,Compute,,,t,3,= (,x,2,,x,1,)/ (,x,1,,x,0,);,Step 5,Set,i,++;,,,d,3,= 1+t,3,;,Step 6,Set,x,0,=,x,1,, x,1,=x,2,, x,2,=x,;,,a=,f,(,x,0,)t,3,2,-,f,(,x,1,)t,3,d,3,+,f,(,x,2,)t,3,;,Step 7,,goto,Step 2.,,b=,f,(,x,0,)t,3,2,-,f,(,x,1,)d,3,2,+,f,(,x,2,)(t,3,+d,3,),;,,,c=,f,(,x,2,)d,3,;,,,t,4,=-2c/[b+sign(b)sqrt(b,2,-4ac)],;,,,x= x,2,+,t,4,(,x,2,-x,1,);,,Th,2.5.2,,（,局部收敛性,）,,设,， 在,x,*,的某邻域内连续，则存,,在,x,*,的一个邻域 ，当,,时,,,由,抛物线法,产生的序列 收敛于,x,*,，且,其中,,,是方程 的根,.,,Muller,法,的优点：初值的选取范围比,Newton,法和,弦割法,宽,,,,,而且可以一次求得方程的,一对复根,.,,。