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

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

/*NumericalSolutionsofNonlinearEquations*/本章主要内容：1、二分法2、不动点迭代的构造及其收敛性判定（重点）3、Newton和Steffensen迭代（重点）4、割线法5、非线性方程组的迭代解法历史背景

代数方程的求根问题是一个古老的数学问题。理论上，次代数方程在复数域内一定有个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。

求方程几何意义基本定理如果函数在上连续，且则至少有一个数使得，若同时的一阶导数在内存在且保持定号，即(或)则这样的在内唯一。

abx*§1二分法

/*BisectionMethod*/原理：若f

C[a,b]，且f(a)·f(b)<0，则f在(a,b)上至少有一实根。基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。以此类推终止法则？abx1x2abWhentostop?或不能保证

x

的精度x*2xx*二分法算法给定区间[a,b]

，求f(x)=0

在该区间上的根x.输入:

a和b;容许误差

TOL;最大对分次数

Nmax.输出:近似根x.Step1Setk=1;Step2Computex=f((a+b)/2);Step3While(kNmax)dosteps4-6Step4If|x|

<TOL

,STOP;Outputthesolutionx.Step5Ifx*f(a)<0,Setb=x;

ElseSet

a=x;Step6Setk=k+1;Computex=f((a+b)/2);GoTo

Step3;Step7Outputthesolutionofequation:

x;STOP.3、由二分法的过程可知：4、对分次数的计算公式：1、2、令误差

分析解：例1：用二分法求方程在区间上的根，误差限为，问至少需对分多少次？①简单;②

对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢

注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。优点缺点§2迭代法的理论

/*TheoryofIteration

Method*/f(x)=0x=g(x)（迭代函数）等价变换思路从一个初值x0出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得

，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。看起来很简单，令人有点不相信，那么问题是什么呢？如何判定这种方法是收敛的呢？f(x)的根g(x)的不动点一、不动点迭代

/*Fixed-PointIteration*/xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1几何意义例2：已知方程在上有一个根（正根）下面选取5种迭代格式：1、即2、即3、即4、即5、即取计算结果如下：法1法4法3法2法5Lipschitz条件成立的充分条件考虑方程x=g(x),若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得

对x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：(k=1,2,…)且存在极限连续时证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？L越收敛越快可用来控制收敛精度④⑤⑥小注：条件(II)可改为在[a,b]满足Lipschitz条件,定理结论仍然成立(定理2.3’)。

算法:不动点迭代给定初始近似值

x0

，求x=g(x)

的解.输入:

初始近似值

x0;容许误差

TOL;最大迭代次数

Nmax.输出:近似解x或失败信息.Step1Seti=1;Step2While(iNmax)dosteps3-6

Step3Setx=g(x0);/*计算xi*/

Step4If|xx0|<TOLthenOutput(x);/*成功*/ STOP;

Step5Seti++;

Step6Setx0=x;/*更新x0*/Step7Output(Themethodfailedafter

Nmax

iterations);/*不成功*/ STOP.当x很大时，此处可改为二、局部收敛性/*LocalConvergence*/（局部收敛性

）若存在的不动点的一个闭邻域对任意的，由迭代法产生的序列均收敛于，则称该迭代法局部收敛。

注解:局部收敛性特点：假定解存在，且肯定存在解的一个邻域，使得对其中所有初始值，由迭代生成的序列收敛于解。半局部收敛特点：不知道解存在，但指出要从满足一定（通常很强）条件的初始值出发，保证收敛于某一（临近）解。全局（整体）收敛：肯定在全空间或至少其中一个很大的部分中，无论从何处出发，都能保证收敛于一个解。设为的不动点，在的某邻域连续，且，则迭代法(*)局部收敛。证明：因为在的某邻域连续，存在邻域即对则由定理2.3’，迭代法(*)对收敛，即局部收敛.注

例3：已知方程在1.5附近有根，把方程写成三种不同的等价形式(1)对应迭代格式；(2)对应迭代格式；(3)对应迭代格式;判断迭代格式在的收敛性，选一种收敛格式计算，精确到小数点后第二位。解：（1），，迭代格式收敛；（2），，迭代格式收敛；（3），，迭代格式发散。选择(2)计算

012341.51.4811.4731.4691.467（收敛阶/*theorderofConvergence*/)设序列收敛到，，若存在实数及常数，使,则称序列是阶收敛的，称为渐近误差常数。当且时，称为线性收敛，为超线性收敛，时为平方或二次收敛.注:（1）的大小反映了迭代法收敛的快慢，是收敛速度的一种度量;

（2）设迭代函数满足收敛定理的条件，则产生的序列满足，如果在或的邻域有若取，必有，此时有设迭代法的迭代函数的高阶导数在不动点的邻域里连续，则式（*）是阶收敛的充要条件是且证明：由Taylor公式：充分性取极限得必要性设迭代式（*）是阶收敛的，则有即且（反证法）设结论不成立则存在最小正整数满足情形一情形二由充分性证明知，迭代式（*）是阶收敛的即而的极限不存在与阶收敛矛盾证明方法与情形一类似（自己练习）一、使用两个迭代值的组合方法：§3迭代收敛的加速方法

/*Accelerating

Method*/本节讨论迭代法加速收敛问题，常用于线性收敛迭代法

将x=g(x)

等价地改造为当和时，有相应的迭代公式为或者选取特殊的，有可能使迭代加速。

xyy=xy=g(x)x*如：迭代公式为几何意义如图示注：(1)这种迭代对原迭代公式(*)的各近似值在根的两侧往复地趋于时较为有效；中点(2)只有且较大时，加速效果才明显。又如：新的迭代函数为当时根据定理2.5知，迭代法至少是二阶的.

但由于不知道，故也得不到，因此可取其的近似值，即从而有二、Steffensen(斯蒂芬森)加速迭代法：（三个迭代值组合）xyy=xy=g(x)x*x0从初值出发，计算出在曲线上得到两个点用直线连接、两点它与的交点设为点的坐标为将视为新的初值，重复上述步骤

一般地，由组合得到迭代式或者这个方法称为斯蒂芬森(Steffensen)迭代方法

若令则得到斯蒂芬森(Steffensen)迭代法的另一种形式：Steffensen迭代法的优点：可以改进收敛速度，有时也能把不收敛的迭代法改进为收敛的二阶方法.艾特肯（Aitken）加速方法：例4：已知方程在上有一个根（正根）下面选取3种迭代格式：1、即2、即3、即显示计算结果设不动点迭代的迭代函数在其不动点的某邻域内具有二阶连续导数，则斯蒂芬森(Steffensen)的迭代技术是二阶收敛的，而且其极限仍为。证明：设斯蒂芬森(Steffensen)的迭代为其中首先证明有相同的不动点设则反之，设型洛比塔法则其次证明Steffensen迭代是二阶收敛的由Taylor公式：在处展开则上式中用替换即证代入上述结果：注意：对本来就是P(>1)阶收敛的方法，改用Stefensen迭代方法优点不多。取计算结果如下：法2原迭代次数29法3原来不收敛法1原来不收敛返回§4牛顿法

/*Newton-RaphsonMethod*/一、牛顿迭代公式的推导1、待定参数法不动点迭代的关键是构造满足收敛条件的迭代函数

一种自然的选择是令为了加速不动点迭代的收敛过程，应尽可能使迭代函数在处有更多阶导数等于零（定理2.5）。令现设取满足因此，选取迭代函数Newton–Raphson迭代格式称之为牛顿—拉夫森方法，简称牛顿法原理：将非线性方程线性化取x0

x*，将f(x)在x0

做一阶Taylor展开:，在x0和x之间2、Taylor展开法/*Taylor’sexpansionMethod*/将(x*

x0)2看成高阶小量，则有：xyx*x0只要f

C1，每一步迭代都有而且，则

x*就是f的根。与x轴交点的横坐标无开方运算，又无除法运算。例1：写出求的Newton迭代格式；写出求的Newton迭代格式,要求公式中既解：等价于求方程的正根解法一：等价于求方程的正根解法二：等价于求方程的正根Th2.7

（局部收敛性）设x*

为方程f(x)=0的根，在包含x*的某个开区间内连续，且，则存在x*的邻域，使得任取初值，由Newton’sMethod产生的序列以不低于二阶的收敛速度收敛于x*，且证明：Newton’sMethod

事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：在单根

/*simpleroot*/附近收敛快只要，则令可得结论。Th2.5有根根唯一产生的序列单调有界保证收敛证明：因为f

C2[a,b]，由（1）和（2）知f(x)在[a,b]内有唯一根下面由条件（1）、（2）分4种情况讨论：仅证明第一种情况，其它情况类似讨论Th2.8

（收敛的充分条件）设f(x)=0且f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整个[a,b]上不变号且

；(3)选取x0

[a,b]使得；则Newton’sMethod产生的序列{xk}收敛于方程的根,且由中值定理，使得因此即在上单调递增由另一方面，由Taylor展开得介于、之间重复以上过程，可得（归纳法）（自己证）因此，数列单调下降且有下界令由Taylor展开得注：Newton’sMethod收敛性依赖于x0

的选取。x*x0x0x0Th2.9

（收敛的另一充分条件）设

在[a,b]上连续，(1)

f(a)f(b)<0；(2)在整个[a,b]上且

；(3)

，则对，Newton’sMethod产生的序列{xk}收敛于方程在[a,b]内的唯一实根。且Th2.9中条件（3）的几何意义保证数列单调递增且有上界证明仿照Th2.9改进与推广（补充）

/*improvementandgeneralization*/重根

/*multipleroot*/加速收敛法：Q1:若，Newton’sMethod

是否仍收敛？设x*是f的n重根，则：且。因为Newton’sMethod

事实上是一种特殊的不动点迭代，其中，则A1:

有局部收敛性，但重数n

越高，收敛越慢。Q2:如何加速重根情况时的收敛速度？A2:

将求

f

的重根转化为求另一函数的单根。令，则f的重根=

的单根。求复根

/*FindingComplexRoots*/——Newton

公式中的自变量可以是复数记z=x+iy,z0

为初值，同样有设代入公式，令实、虚部对应相等，可得§5弦割法与抛物线法

/*SecantMethodandParabolaMethod

*/x0x1割线

/*secantline*/切线斜率

割线斜率需要2个初值x0和x1。Newton’sMethod每一步要计算f和，为了避免计算导数值，现用f的值近似，从而得到弦割法（割线法）。x2一、弦割法Th2.10

局部收敛性设表示区间，x*为方程f(x)=0的根，函数f(x)在

中有足够阶连续导数，且满足则对，由割线法产生的序列都收敛于x*，且(i)(ii)(iii)

其中收敛速度介于NewtonandBisection

之间

Corollary(推论)设x*

为方程f(x)=0的一个根，，且在x*的附近连续，则使得由Secant

Method产生的序列都收敛于x*。例1

证明方程在区间内有唯一根，且使得对任意的初始值，由割线法产生的序列都收敛于。

证明：令方程存在根方程存在唯一根且在附近连续由推论知，由割线法产生的序列都收敛于。

xk-2Muller方法的思想来源于弦割法:利用3个已知点构造一条抛物线,取其与x轴的交点构造下一次迭代值.x*二、抛物线法(Muller)几何图示xkxk-1xk+1

Muller方法的具体实现:设已知三个点则过上述三个点的抛物线方程为:取该抛物线与x轴的交点作为下一次迭代值,即然后取新的相邻的三次迭代值重复上述过程,即为Muller方法.

Muller方法中抛物线根的计算方法:首先要将抛物线化为规范形式:引入新的变量将上述变量代入前面的抛物线方程,得其中的两个零点为:取的两个零点中靠近的那个零点,则有

Muller方法的迭代公式为:具体计算步骤见教材P39.

算法:Muller方法给定初始近似值

x0

，x1

，

x2,求f(x