第六章非线性方程求根

第六章非线性方程求根第一页，共六十二页，编辑于2023年，星期五

公元前1700年的古巴比伦人就已有关于一、二次方程的解法。

《九章算术》(公元前50~100年)其中“方程术”有联立一次方程组的一般解法。

1535年意大利数学家尼柯洛冯塔纳找到了一元三次方程一般形式的求根方法。这个成就，使他在几次公开的数学较量中大获全胜，从此名扬欧洲。但是冯塔纳不愿意将他的这个重要发现公之于世.第二页，共六十二页，编辑于2023年，星期五

当时的另一位意大利数学家兼医生卡尔丹诺，对冯塔纳的发现非常感兴趣。他几次诚恳地登门请教，希望获得冯塔纳的求根公式。后来，冯塔纳终于用一种隐晦得如同咒语般的语言，把三次方程的解法“透露”给了卡尔丹诺。冯塔纳认为卡尔丹诺很难破解他的“咒语”，可是卡尔丹诺通过解三次方程的对比实践，很快就彻底破译了冯塔纳的秘密。第三页，共六十二页，编辑于2023年，星期五卡尔丹诺把冯塔纳的三次方程求根公式，写进了自己的学术著作《大法》中，但并未提到冯塔纳的名字。由于第一个发表三次方程求根公式的人确实是卡尔丹诺，因此后人就把这种求解方法称为“卡尔丹诺公式”。第四页，共六十二页，编辑于2023年，星期五

后来，卡尔丹诺的学生弗瑞里(Ferrari)又提出了四次方程的解法。但对于五次方程求根，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。1828年17岁的法国数学家伽罗华(E·Galois1811-1832)写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n次方根，并用类似算法求五次或更高次代数方程的根是不可能的第五页，共六十二页，编辑于2023年，星期五文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1830年伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解”。后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。第六页，共六十二页，编辑于2023年，星期五

十四年后，法国数学家刘维尔(J·Liouville)整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。38年后，即1870年，法国数学家若当(C·Jordan)在专著《论置换与代数方程》中阐发了伽罗华的思想，一门现代数学的分支—群论诞生了。在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。第七页，共六十二页，编辑于2023年，星期五求根问题包括下面三个问题：根的存在性：即f(x)=0有没有根？若有，有几个根？哪儿有根？确定有根区间根的精确化：已知一个根的近似值后，能否将它精确到足够精度？本章假设f

C[a,b]，且f(a)·f(b)<0，则f

在(a,b)上至少有一根，(a,b)即为有根区间。问题1、2得到解决。第八页，共六十二页，编辑于2023年，星期五(1)图解法（利用作图软件如Matlab)(2)扫描法（逐步搜索法）(3)二分法*§2根的搜索第九页，共六十二页，编辑于2023年，星期五

（1）(描)做图法

画出y=f(x)

的草图,由f(x)与横轴交点的大概位置来确定隔根区间;或者利用导函数f(x)的正、负与函数f(x)的单调性的关系确定根的大概位置.

若f(x)比较复杂,还可将方程f(x)=0化为一个等价方程(x)=(x),

则曲线y=(x)与y=(x)之交点A(x*,y*)的横坐标x*即为原方程之根,据此也可通过作图求得x*的隔根区间.第十页，共六十二页，编辑于2023年，星期五如求解方程的近似根

方法1:将方程同解变换成然后画两条曲线第十一页，共六十二页，编辑于2023年，星期五023yx这两条曲线的交点的横座标大致为x=2.5第十二页，共六十二页，编辑于2023年，星期五1.逐步搜索法§2根的搜索

2.逐步搜索法设f(a)<0,f(b)>0，有根区间为(a,b)，从x0=a出发，按某个预定步长(例如h=(b-a)/N)一步一步向右跨，每跨一步进行一次根的搜索，即判别f(xk)=f(a+kh)的符号，若f(xk)>0(而f(xk-1)<0),则有根区间缩小为[xk-1,xk](若f(xk)=0，xk即为所求根),然后从xk-1出发，把搜索步长再缩小，重复上面步骤，直到满足精度：|xk-xk-1|<为止，此时取x*≈(xk+xk-1)/2作为近似根。①无法求复根及偶重根②计算量大，收敛慢①简单;②对f(x)

要求不高

(只要连续即可).x0=abxk-1xkx*第十三页，共六十二页，编辑于2023年，星期五2.BisectionMethod

3.二分法

/*BisectionMethod*/(逐步搜索法的改进)设f(x)的有根区间为[a,b]=[a0,b0],f(a)<0,f(b)>0.将[a0,b0],对分，中点x0=((a0+b0)/2),计算f(x0),

若f(x0)=0,x*=x0

<0,有根区间:[a1,b1]=[x0,b]>0,有根区间:[a1,b1]=[a,x0]对[a1,b1]对分，如此反复进行，得到一系列有根区间：

f(ak)0,f(bk)0,f(x*)=limf(ak)=limf(bk)abx1x2x*第十四页，共六十二页，编辑于2023年，星期五Whentostop?取xk=(ak+bk)/2([ak,bk]的中点)，显然有limxk=x*.——算法和收敛性说明。或不能保证

xk的精度abx1x2x*2xkx*2.BisectionMethod第十五页，共六十二页，编辑于2023年，星期五第1步产生的有误差第k步产生的xk

有误差对于给定的精度

,可估计二分法所需的步数k：①简单，总收敛;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。误差分析2.BisectionMethod第十六页，共六十二页，编辑于2023年，星期五Fixed-PointIterationf(x)=0x=φ(x)，e.g.,φ(x)=f(x)+x等价变换f(x)=0的根

φ

(x)的不动点一、迭代算法的原理f(x*)=0x*=φ(x*)被这个函数映射到其自身一个点！第十七页，共六十二页，编辑于2023年，星期五二、迭代算法的思路

从一个初值x0出发，计算

x1=φ(x0),

x2=φ(x1),

…,

xk+1=φ(xk),

…若收敛，即存在x*使得

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

的根。xk+1=φ(xk)φ(x*)x*φ(x)连续=迭代函数迭代格式第十八页，共六十二页，编辑于2023年，星期五注意x*为的解，即这两个函数图象交点的横坐标。迭代法三、迭代算法的几何意义第十九页，共六十二页，编辑于2023年，星期五xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§3.Fixed-PointIteration第二十页，共六十二页，编辑于2023年，星期五例2用不动点迭代法求方程x4+2x2-x-3=0在[1,1.2]内的实根，取x0=1,精确到小数点后面6位。解迭代格式

发散法一第二十一页，共六十二页，编辑于2023年，星期五解法二迭代格式

收敛第二十二页，共六十二页，编辑于2023年，星期五迭代格式

收敛快解法三第二十三页，共六十二页，编辑于2023年，星期五四、结论可见，f(x)=0的迭代函数（1）不唯一；（2）发散或者收敛；（3）收敛速度有快慢之分。五、问题（1）迭代函数收敛的条件是什么？（2）收敛速度如何评价？第二十四页，共六十二页，编辑于2023年，星期五定理1(迭代收敛条件)考虑方程x=g(x),g(x)C[a,b],若(I)

x[a,b]，g(x)[a,b]；(II)0L<1,s.t.

x[a,b],|g(x)|L.(k=1,2,…)且存在极限k事后误差估计事先误差估计§3.Fixed-PointIteration则任取初值x0[a,b]，由xk+1=g(xk)

得到的序列收敛于g(x)在[a,b]上的唯一不动点，并且有误差估计式：第二十五页，共六十二页，编辑于2023年，星期五§3Fixed-PointIteration证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？第二十六页，共六十二页，编辑于2023年，星期五④⑤⑥可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性§3.Fixed-PointIterationDef1.Ifthereexistsaneighborhoodofx*,e.g.,B

={x||xx*|}，s.t.x0B,

xk+1=g(xk)converges,thenwesaytheiterationconvergeslocallyaroundx*.

第二十七页，共六十二页，编辑于2023年，星期五证明:注：由于事先x*未知，所以无法检验条件|g'(x*)|<1.只能用搜索法初步确定x*所在区间，验证该区间内任一点是否有|g'(x*)|<1.所以Th2实际上没什么应用价值，但在理论上是对g(x)的一个改进。

§3.Fixed-PointIterationTh2.若在x*的某领域B={x||xx*|}有gC1[a,b]且|g'(x*)|<1，则由x0B

开始的迭代收敛。即调整初值可得到收敛的结果。注：局部收敛性定理对迭代函数的要求较弱，但对初始点要求较高，即初始点必须选在精确解的附近第二十八页，共六十二页，编辑于2023年，星期五Algorithm:Fixed-PointIterationFindasolutiontox=g(x)givenaninitialapproximationx0.Input:initialapproximationx0;toleranceTOL;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Seti=1;Step2While(iNmax)dosteps3-6

Step3Setx=g(x0);/*computexi*/

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

Step5Seti++;

Step6Setx0=x;/*updatex0*/Step7Output(ThemethodfailedafterNmaxiterations);/*unsuccessful*/ STOP.当x很大时，此处可改为§3.Fixed-PointIteration第二十九页，共六十二页，编辑于2023年，星期五§3.Fixed-PointIteration改进、加速收敛

/*acceleratingconvergence*/有些迭代过程虽收敛，但速度很慢。为了达到所要求的精度，需要迭代的次数很多，由此必须设法加速迭代过程。1.基本思想上式说明，将预测值x0和校正值x1

作线性组合作为x*的一个新近似值，可能比x1更好。令：

ξ介于x0与x*之间，设变化不大，，则有微分中值定理x0----x*的预测值第三十页，共六十二页，编辑于2023年，星期五一般地，有LinearcombinationUpdateresidual第三十一页，共六十二页，编辑于2023年，星期五

2.Aitken加速：在方法1中含有L，实际应用中不便。下面设法消除L得到一种新的加速方法---Aitken（埃特金）方法。

x0——prediction推广，有下面一般计算公式：

x1=g(x0)——updatingx2=g(x1)——further

updating第三十二页，共六十二页，编辑于2023年，星期五predictionAitken’saccelerationxkupdatingFurtherupdatingimprove第三十三页，共六十二页，编辑于2023年，星期五也称为埃特金(Aitken)外推法.可以证明:为线性收敛,则埃特金法为平方收敛；

这个加速迭代法也可写成下面格式若为p(p>1)阶收敛，导数连续，则埃特金法为2p–1

阶收敛.的

p

阶若第三十四页，共六十二页，编辑于2023年，星期五

例题求方程x=e–x

在x=0.5

附近的根.

解取x0=0.5,迭代格式x25=x26=0.5671433

若对此格式用埃特金法,则

得第三十五页，共六十二页，编辑于2023年，星期五仍取x0=0.5,得由此可见,埃特金法加速收敛效果是相当显著的.第三十六页，共六十二页，编辑于2023年，星期五§3Fixed-PointIterationxyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)Generally,wehave比收敛得略快。3.Steffensen加速：Atkin’smethodfromanotherpointofviewx*x*第三十七页，共六十二页，编辑于2023年，星期五

4.待定参数法：若

|g'(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列。第三十八页，共六十二页，编辑于2023年，星期五§4牛顿迭代法

/*Newton-RaphsonMethod*/Newton’smethodfromthepointofviewofaccelerationpredictupdateM=L-1f'(x)简单牛顿公式Newton’smethod第三十九页，共六十二页，编辑于2023年，星期五牛顿法是解非线性方程（组）的一种常用迭代方法，基本思想是将非线性方程（组）转化为易于求解的线性方程（组）来求解。——

Taylor展开/*Taylor’sexpansion*/设x*有近似解xk

x*，将f(x)在xk

做一阶Taylor展开，将x=

x*代入，有，在x*

和xk

之间。linearequation只要f

C1，每一步迭代都有f(xk)0，而且，则

x*就是f

的根。截取线性项，得xyx*xkTangentmethodNewton’smethodfromthepointofviewoflinearization第四十页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod定理

（牛顿法收敛的充分条件）设f

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

[a,b]使得f(x0)f

(x0)>0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根。有根只有单根，根唯一产生的序列单调有界，保证收敛。定理

（局部收敛性）设f

C2[a,b]，若x*

为f(x)在[a,b]上的根，且f(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足第四十一页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：在单根

/*simpleroot*/

附近收敛快（平方收敛）第四十二页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod注：Newton’sMethod收敛性依赖于x0

的选取。x*x0x0x0第四十三页，共六十二页，编辑于2023年，星期五牛顿法应用举例

第四十四页，共六十二页，编辑于2023年，星期五第四十五页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod改进与推广/*improvementandgeneralization*/

重根/*multipleroot*/

加速收敛法：Q1:

若，Newton’sMethod是否仍收敛？设x*是f

的n

重根，则：且对于牛顿法，A1:

有局部收敛性,但重数n越高,g(x*

)越接近于1,收敛越慢。Q2:

如何加速重根的收敛？A2:

将求

f

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

的重根=

的单根。重根的处理见《矩阵计算与方程求根》－曹志洁等；P.208对f(x)求1,2阶导代入即得第四十六页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod

正割法/*SecantMethod*/

：Newton’sMethod

一步要计算f

和f，相当于2个函数值，比较费时。现用f

的值近似f

，可少算一个函数值。x0x1切线

/*tangentline*/割线

/*secantline*/切线斜率

割线斜率需要2个初值x0

和x1。收敛比Newton’sMethod慢，且对初值要求同样高。第四十七页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod

下山法/*DescentMethod*/

——Newton’sMethod

局部微调：原理若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。第四十八页，共六十二页，编辑于2023年，星期五

抛物线法

/*ParabolaMethod*/

——利用插值将非线性方程转化为低次多项式求根x0x1切线

/*tangentline*/割线

/*secantline*/x2x3第四十九页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethodAlgorithm:Newton’sDescentMethodFindasolutiontof(x)=0givenaninitialapproximationx0.Input:initialapproximationx0;f(x)andf’(x);minimumstepsizeofxmin;

toleranceTOL1forx;toleranceTOL2for

;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-10

Step3Set=1;

Step4Set

;/*computexk*/

Step5If|xx0|<TOL1thenOutput(x);STOP;/*successful*/

Step6Ifthenx0=x;GOTOStep10;/*updatex0*/

Step7Set=/2;/*updatetodescend*/

Step8If>TOL2thenGOTOStep4;/*computeabetterxi*/

Step9Setx0=x0+xmin;/*moveforwardanywaytoavoiddeadlock*/

Step10Setk++;Step11Output(MethodfailedafterNmaxiterations);STOP./*unsuccessful*/计算量未见得减小第五十页，共六十二页，编辑于2023年，星期五§4Newton-RaphsonMethod

求复根/*FindingComplexRoots*/

——

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

为初值，同样有设代入公式，令实、虚部对应相等，可得第五十一页，共六十二页，编辑于2023年，星期五§5迭代法的收敛阶

/*OrderofConvergence*/Def2.

设迭代xk+1=g(xk)收敛到g(x)的不动点x*。设ek=xk

x*，若，则称该迭代为p

阶收敛，其中C

称为渐进误差常数。/*{xk}convergesto

x*oforder

p,withasymptoticerrorconstant

C>0*/

p

=1----线性收敛，

p

>1-----超线性收敛，

p

=2----平方收敛。一种迭代法有效在接近收敛的过程中迭代误差的下降速度。Strictdefinitionisgivenindef2.如何刻画这种关系第五十二页，共六十二页，编辑于2023年，星期五

一般Fixed-PointIteration有，称为线

性收敛

/*linearconvergence*/，这时p=1，0<C<1。注：超线性收敛不一定有p>1。例如xn

=1/nn超线性收敛到0，但对任何p>1都没有

p

阶收敛。Aitken加速有。称为超线性收敛

/*superlinearconvergence*/。第五十三页，共六十二页，编辑于2023年，星期五§5OrderofConvergence

Steffensen加速有p=2，条件是，称为平方收敛

/*quadraticconvergence*/。

Newton’sMethod有，只要，就有p

2。重根是线性收敛的。Q:

如何实际确定收敛阶和渐进误差常数？定理

设x*

为x=g(x)的不动点，若，p2；，且，则xk+1=g(xk)在内p

阶收敛。证明：x*k

CThisisaonelineproof...ifwestartsufficientlyfartotheleft.第五十四页，共六十二页，编辑于2023年，星期五Th3(relationbetweentheconvergencerateandtheiterationfunction)

fortheiterationprocess

xk+1=g(xk),if

g(p)(x)

iscontinuous

aro