非线性方程的数值解法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4,牛顿法,一、牛顿迭代公式的推导,(,Taylor,展开法,),思想：,非线性方程线性化,（以直代曲）,取,x,0,x*,，,将,f,(,x,),在,x,0,做一阶,Taylor,展开,:,，,在,x,0,和,x,之间,将,(,x*,x,0,),2,看成,高阶小量,，则有：,令,注：牛顿法是一种特殊的迭代法。,Newton Raphson,迭代格式,称之为,牛顿,拉夫森,方法，简称,牛顿法,.,x,y,x*,x,0,与,x,轴交点的横坐标,无开方运算，又无除法运算。,例,1,：,写出求 的,Newton,迭代格式；,写出求 的,Newton,迭代格式,要求公式中既,解：,等价于求方程 的正根,解法一：,等价于求方程 的正根,解法二：,等价于求方程 的正根,Th2.7,（,局部收敛性,）,设,x,*,为方程,f,(,x,)=0,的根，在包含,x,*,的某个开区间内 连续，且 ，则存在,x,*,的邻域 ，使得任取初值 ，由,Newtons Method,产生的序列 以,不低于二阶,的收敛速度收敛于,x,*,，且,证明：,Newtons Method,事实上是一种,特殊的不动点迭代,其中 ，则,收敛,由,Taylor,展开：,只要,，则令,可得结论。,Th2.5,有根,根唯一,产生的序列,单调有界,保证收敛,证明省略。,Th2.8,（,收敛的充分条件,）,设,f,(,x,),=0,且,f,C,2,a,b,，若,(1),f,(,a,),f,(,b,)0,；,(2),在整个,a,b,上 不变号且,；,(3),选取,x,0,a,b,使得 ；,则,Newtons Method,产生的序列,x,k,收敛于方程的根,.,Th2.9,（,收敛的另一充分条件,）,设,在,a,b,上连续，,(1),f,(,a,),f,(,b,)0,；,(2),在整个,a,b,上 且,；,(3),，,则对 ，,Newtons Method,产生的序列,x,k,收敛于方,程 在,a,b,内,的唯一实根 。,且,证明省略。,注：,Newtons Method,收敛性依赖于,x,0,的选取。,x,*,x,0,x,0,x,0,改进与推广（,补充,）,重根,加速收敛法：,Q1:,若 ，,Newtons Method,是否仍收敛？,设,x,*,是,f,的,n,重根，则：且 。,因为,Newtons Method,事实上是一种特殊的不动点迭代,其,中 ，则,A1:,有局部收敛性，但重数,n,越高,，收敛,越慢,。,Q2:,如何,加速,重根情况时的收敛速度？,A2:,将求,f,的,重根转化,为求另一函数的,单根,。,令，则,f,的重根,=,的单根。,求复根,Newton,公式中的自变量可以是,复数,记,z,=,x,+,i y,z,0,为初值，同样有,设,代入公式，令,实、虚部对应相等,，可得,5,弦割法与抛物线法,x,0,x,1,割线,切线斜率,割线斜率,需要,2,个初值,x,0,和,x,1,。,Newtons Method,每一步要计算 ，为了避免计算导数值，现用 的近似，得到,弦割法,（,割线法,）。,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,*,。,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,法和,弦割法,宽,但计算量比弦割法大。进一步研究可知,Muller,法可求复根。,