数值分析课件非线性方程组的求解

数值分析课件非线性方程组的求解第一页，共六十四页，2022年，8月28日预备知识

满足函数方程f(x)=0的x称为方程(1)的根，或称为函数f(x)的零点。如果函数(x)可分解为

(x)=(xs)mg(x)且g(s)0,则称s是(x)的m重零点或(x)=0的m重根。当m=1时，称s是(x)的单根或单零点。定理假设函数y=f(x)在x=s的某一邻域内充分可微，则s是方程f(x)=0的m重根的充分必要条件是第二页，共六十四页，2022年，8月28日求解非线性方程的根的问题可分为下面几个方面：

根的存在性根的隔离根的精确化

非线性方程根的存在性非常复杂。

对于代数方程即多项式方程，其根的个数与代数方程的次数相同。而且理论上已证明，对于次数n<=4的多项式方程,它的根可以用公式表示,而次数大于5的多项式方程,它的根一般不能用解析表达式表达。示.

对于超越方程或其他非线性方程，可能没有零点，也可能有一个或若干个零点，甚至无穷多个零点。第三页，共六十四页，2022年，8月28日根的存在性定理

定理1.(根的存在定理)假设函数y=f(x)Ca,b,且f(a)·f(b)<0,则至少存在一点x(a,b)使得f(x)=0.

(并称区间(a,b)为有根区间).

定理2.（根的唯一性）

假设函数y=f(x)在a,b上单调连续,且

f(a)·f(b)<0,则恰好只存在一点x(a,b)使得

f(x)=0

第四页，共六十四页，2022年，8月28日根的隔离求根的隔离区间的两种方法

画图法

画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0分解为1(x)=2(x)的形式，1(x)与2(x)两曲线交点的横坐标所在的子区间即为含根区间。

例如xlgx–1=0可以改写为lgx=1/x画出对数曲线y=lgx,与双曲线y=1/x,它们交点的横坐标位于区间[2,3]内第五页，共六十四页，2022年，8月28日023yx画图法第六页，共六十四页，2022年，8月28日逐步搜索法

对于给定的f(x)，设有根区间为[A,B]，从x0=A

出发，以步长h=(B-A)/n(n是正整数)，在[A,B]内取定节点：xi=x0＋ih(i=0，1，2，…，n)，从左至右检查f(xi)的符号，如发现xi与端点x0

的函数值异号，则得到一个缩小的有根子区间［xi-1,xi］。用逐步搜索法进行实根隔离的关键是选取步长h要选择适当h，使之既能把根隔离开来，工作量又不太大。

逐步搜索法第七页，共六十四页，2022年，8月28日二分法Bisection

在方程求根的方法中，最直观、最简单的方法就是二分法。

给定方程f(x)=0,设f(x)在区间[a,b]连续,且f(a)f(b)<0,则方程f(x)在(a,b)内至少有一根,为便于讨论,不妨设方程f(x)=0在(a,b)内只有一个(重根视为一个)实根。

二分法的基本思想

用对分区间的方法，通过判别函数f(x)在每个对分区间中点的符号，逐步将有根区间缩小，最终求得一个具有相当精确程度的近似根第八页，共六十四页，2022年，8月28日二分法详细步骤

第九页，共六十四页，2022年，8月28日第十页，共六十四页，2022年，8月28日二分法终止的条件如下条件终止，可否？这不能保证精确值的精度！xx*第十一页，共六十四页，2022年，8月28日有如下估计因此终止的条件为

二分法终止的条件对于给定的精度,可估计二分法所需的步数k：第十二页，共六十四页，2022年，8月28日二分法的优缺点

优点

计算简单，方法可靠，并保证收敛

对函数要求不高，只要连续即可。

缺点

无法求复根和偶重根收敛慢调用一次求解一个[a,b]间的多个根无法求得

一般求方程的近似根，不大单独使用，常用来为其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法。第十三页，共六十四页，2022年，8月28日functiony=erfen(fun,a,b,esp)Matlabprogramiffeval(fun,a)*feval(fun,b)<0n=1;c=(a+b)/2;while(b-a)>espiffeval(fun,a)*feval(fun,c)<0b=c;c=(a+b)/2;elseiffeval(fun,c)*feval(fun,b)<0a=c;c=(a+b)/2;elsey=c;endn=n+1;endy=c;elseiffeval(fun,a)==0y=a;elseiffeval(fun,b)==0y=b;end第十四页，共六十四页，2022年，8月28日第十五页，共六十四页，2022年，8月28日不动点迭代法

迭代法的基本思想是一种逐次逼近的方法，首先给定一个粗糙的初值，然后用同一个迭代公式，反复校正这个初值，直到满足预先给出的精度要求。迭代法的基本步骤f(x)=0等价变换f(x)的根x=(x)(x)的不动点第十六页，共六十四页，2022年，8月28日从一个初值

x0出发，计算

x1=

(x0),x2=(x1),…,xk+1=(xk),…

若收敛，即存在x*使得

，且连续，则由可知

x*=(x*)，即x*是的不动点，也就是f

的根。不动点迭代法定义：迭代公式xk+1=

(xk)(k=0,1,…)被称为求解方程f(x)=0的不动点迭代法，其中

(x)称为迭代函数。

第十七页，共六十四页，2022年，8月28日迭代法的几何含义yxyy=xsy=g(x)x0p0x1p1第十八页，共六十四页，2022年，8月28日需要讨论的问题

首先期望每个xk都在(x)的定义域上,保持有界而且收敛到精确解;如何选取适合的迭代函数(x);迭代函数(x)迭代满足什么条件,迭代序列收敛到精确解,收敛速度如何;

H

第十九页，共六十四页，2022年，8月28日

设将原方程改写成下列形式据此建立迭代公式

但若采用方程另一种等价形式建立迭代公式第二十页，共六十四页，2022年，8月28日第二种方法仍取迭代初值，则有结果会越来越大，不可能趋于某个极限.第二十一页，共六十四页，2022年，8月28日

迭代法的收敛条件定理第二十二页，共六十四页，2022年，8月28日

注

条件(2)可用更强更便于应用的条件代替:

由误差估计可以得到迭代终止的条件

由误差估计可以知道L越小，收敛越快以及迭代最少次数

第二十三页，共六十四页，2022年，8月28日

局部收敛性

前述定理条件为充分条件，非必要条件。在实际应用当中条件并不易检验。

定义（局部收敛性）设有不动点，如果存在的某个邻域对任意，迭代产生的序列且收敛到，则称迭代法局部收敛.定理设s为(x)的不动点,'(x)在s的某个邻域内连续,且|'(x*)|<1,则迭代法是局部收敛的.

本定理给出的就是局部收敛性条件。具体解题时，虽然无法判别隔根区间是否为以x*为中心的邻域，但只要它足够小，且在邻域中满足：第二十四页，共六十四页，2022年，8月28日xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1xyy=xsy=g(x)x0p0x1p1

收敛性图像说明第二十五页，共六十四页，2022年，8月28日用不同方法求方程的根

例这里其不动点为由此构造不同的迭代法：可改写为各种不同的等价形式第二十六页，共六十四页，2022年，8月28日

从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.

迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.第二十七页，共六十四页，2022年，8月28日functiony=iterate(x)x1=g(x);n=1;while(abs(x1–x)>=1.0e–6)&(n<=1000)x=x1;x1=g(x);

n=n+1;endx1nmatlabprogram

第二十八页，共六十四页，2022年，8月28日收敛阶(描述收敛速度)

收敛速度（收敛速度的阶）

设迭代过程收敛于方程

的根

，如果迭代误差当时成立下列渐近关系式则称{xn}是p阶收敛若p=1

,称{xk}为线性收敛,这时0<C≤1。

p>1,称{xk}为超线性收敛;

p=2,称其为平方收敛.第二十九页，共六十四页，2022年，8月28日收敛阶定理

数p的大小反映了迭代法的收敛速度的快慢，P越大，收敛越快，所以说收敛阶是对迭代法收敛速度的一种度量。

（收敛阶定理）

对于迭代过程，如果在所求根的邻近连续，并且:则该迭代过程在点邻近是P阶收敛的。

上述定理说明，迭代过程的收敛速度依赖于迭代函数的选取.第三十页，共六十四页，2022年，8月28日Newton迭代法

Newton法的基本思想

将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解

具体而言：

设xk是非线性方程f(x)=0的一个近似根，把f(x)在xk处作一阶泰勒展开，即用前两项近似代替则近似方程转化为

设，上式解为第三十一页，共六十四页，2022年，8月28日Newton迭代法

于是方程f(x)=0的新的近似根xk+1，可得牛顿迭代公式

牛顿迭代公式为特殊的不动点迭代。

其迭代函数为

第三十二页，共六十四页，2022年，8月28日Newton迭代法几何解释

设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与轴的交点的横坐标作为的新的近似值.

注意到切线方程为

第三十三页，共六十四页，2022年，8月28日牛顿法的收敛性

定理设f(x*)=0,,且在x*的邻域上存在,连续,则可得(1)Newton迭代公式在单根情况下至少2阶局部收敛.(2)

定理表明，当初值x0充分接近x*时，Newton法的收敛速度较快，但当初值不够好时，可能会不收敛或收敛于别的根，这可从Newton法的几何意义看到：

第三十四页，共六十四页，2022年，8月28日牛顿法的计算步骤：

步骤1准备选定初始近似值，计算步骤2迭代按公式迭代一次，得新的近似值

，计算步骤3控制如果满足或，则终止迭代，以作为所求的根；否则转步骤4.

此处是允许误差，而

第三十五页，共六十四页，2022年，8月28日牛顿法的计算步骤：

其中是取绝对误差或相对误差的控制常数，步骤4修改或者，则方法失败；

否则以代替转步骤2继续迭代.如果迭代次数达到预先指定的次数，第三十六页，共六十四页，2022年，8月28日functiony=newton(x0)x1=x0–fc(x0)/df(x0);n=1;while(abs(x1–x0)>=1.0e–6)&(n<=100000000)x0=x1;x1=x0–fc(x0)/df(x0);n=n+1;endx1nmatlabprogram

第三十七页，共六十四页，2022年，8月28日计算重根的牛顿迭代法

Newton法在重根情形下的收敛阶为线性阶

若是方程的重根，即此时有第三十八页，共六十四页，2022年，8月28日牛顿法应用举例可导出求开方值的计算程序

：开方公式对于任意给定的正初值均为平方收敛。求无理数的近似值可导出求开方值的计算程序

第三十九页，共六十四页，2022年，8月28日求.取初值，对

按公式迭代3次便得到精度为的结果第四十页，共六十四页，2022年，8月28日牛顿迭代法的优缺点

优点在单根附近,牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。而且能计算复根。缺点

重根情形下为局部线性收敛;

牛顿迭代法计算量比较大:因每次迭代除计算函数值外还要计算导数值;选定的初值要接近方程的解，否则有可能得不到收敛的结果;第四十一页，共六十四页，2022年，8月28日牛顿迭代法的改进

重根情形下为局部线性收敛--------

改进公式或加速每步都要计算导数值-----------简化Newton迭代法或弦截法初值近似问题-------二分法求初值或”下山算法”重根情形的加速提速方案1:

迭代函数使用重数.将迭代函数改为则迭代法为可以证明它是求m重根x*的具平方收敛的迭代格式。

第四十二页，共六十四页，2022年，8月28日牛顿迭代法的改进问题是一般情况下并未知重数m.如何确定m?

令则因此可用下式估计m

第四十三页，共六十四页，2022年，8月28日提速方案2:将求f的重根转化为求另一函数的单根。

构造函数牛顿迭代法的改进对它用牛顿法，其迭代函数为第四十四页，共六十四页，2022年，8月28日避免导数值的计算牛顿迭代法的改进

简化Newton迭代法第四十五页，共六十四页，2022年，8月28日

弦截法牛顿迭代法的改进导数用差商取代，则：导数用差商取代，则1弦截法与牛顿法都是线性化方法，但两者有本质的区别.

2弦截法具有超线性的收敛性.第四十六页，共六十四页，2022年，8月28日

牛顿下山法牛顿迭代法的改进

如果偏离所求根较远，则牛顿法可能发散.

为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：满足这项要求的算法称下山法.

将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.

第四十七页，共六十四页，2022年，8月28日牛顿迭代法的改进牛顿下山法采用以下迭代公式：其中称为下山因子，

选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件成立为止.

牛顿下山法只有线性收敛第四十八页，共六十四页，2022年，8月28日迭代过程的加速

对于收敛的迭代过程，从理论上说，只要迭代足够多次，总可得到满意的精度，但有时迭代过程过于缓慢，计算量极大，实际上得不到满意的结果。因此，迭代过程的加速便成了一个重要的研究课题.加速方案一

当迭代函数

(x)在不动点x*处导数不为零,迭代

xk+1=

(xk)仅是线性收敛.

设由迭代公式计算出迭代值，若x在x*附近变化,'(x)连续,则'(x)变化不大,近似地记为常数L，则用微分中值定理，可以得到第四十九页，共六十四页，2022年，8月28日迭代过程的加速解出x*：

具体算法如下：把它作为xk的一种补偿第五十页，共六十四页，2022年，8月28日加速方案二：Atiken加速法迭代过程的加速

设由基本迭代公式计算出3个迭代值xk,xk+1,xk+2

,则把它作为xk的一种补偿第五十一页，共六十四页，2022年，8月28日迭代过程的加速定理

设序列线性收敛于x*,则的Aitken序列存在,且即比更快收敛于x*.

Atiken加速法与基本迭代公式结合，即为Steffensen迭代法第五十二页，共六十四页，2022年，8月28日迭代过程的加速

Steffensen迭代法具体算法如下：或写成不动点迭代形式第五十三页，共六十四页，2022年，8月28日几何解释xyy=xy=g(x)sx0P(x0,x1)x1x2P(x1,x2)比x2更接近s!第五十四页，共六十四页，2022年，8月28日例

求方程x3

-x-1=0在区间(1,2)内的根s.发散第五十五页，共六十四页，2022年，8月28日kykzkxk01.512.3750012.39651.4162921.840925.238881.3556531.491402.317281.3289541.347101.444351.3248051.325181.327141.32472计算结果

Steffensen迭代法将原不收敛的迭代法变成收敛第五十六页，共六十四页，2022年，8月28日解非线性方程组的牛顿迭代法

考虑方程组其中均为的多元函数.令第五十七页，共六十四页，2022年，8月28日解非线性方程组的牛顿迭代法方程组可以表示为向量形式

F(x)=0.

只要把前面介绍的单变量函数看成向量函数

则可将单变量方程求根方法推广到方程组.

将函数的分量在用多元函数泰勒展开，并取其线性部分，则可表示为第五十八页，共六十四页，2022年，8月28日解非线性方程组的牛顿迭代法令上式右端为零，得到线性方程组其中

求解线性方程组，并记解为，则得这就是解非线性方程组的牛顿迭代法.

第五十九页，共六十四页，2022年，