第4章非线性方程求根

第4章非线性方程求根/*SolutionsofNonlinearEquations

*/§1Introduction

科学技术中常遇到高次代数方程或超越方程的求根问题。大于4次的代数方程无求根公式。因此需要研究函数方程求根问题的数值方法。求f(x)=0的根或零点x*求根问题包括下面三个问题：根的存在性：即f(x)=0有没有根？若有，有几个根？哪儿有根？确定有根区间根的精确化：已知一个根的近似值后，能否将它精确到足够精度？本章假设f

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

在(a,b)上至少有一根，(a,b)即为有根区间。问题1、2得到解决。1.逐步搜索法§2根的搜索

1.逐步搜索法设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*2.BisectionMethod

2.二分法

/*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*Whentostop?取xk=(ak+bk)/2([ak,bk]的中点)，显然有limxk=x*.——算法和收敛性说明。或不能保证

xk的精度abx1x2x*2xkx*2.BisectionMethod第1步产生的有误差第k步产生的xk

有误差对于给定的精度

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

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

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

3.比例法（试位法

/*RegulaFalsiMethod*/）一般地，设

[ak,bk]为有根区间，过(ak,f(ak))、(bk,f(bk))作直线，与x轴交于一点xk,(a+b)/23.RegulaFalsiMethod

abx*(a,f(a))(b,f(b))(x,f(x))x那么用什么来逼近解呢？定理设f(a)f(b)<0,且f(x),f(x)在[a,b]内保号，则按比例求根法确定的序列{xk}必收敛到根x*.3.RegulaFalsiMethod

证明：不妨设f(a)<0,f(b)>0,f(x)>0,曲线如下图用比例求根法，一切有根区间的右端点均为b,即ak=xk-1,bk=b,k=1,2,…abxkx*xk+1上式两端取极限，有即{xk}收敛到f(x)=0的根x*.#注:x*b,因为f(xk-1)<0,所以f(x*)0,而f(b)>03.RegulaFalsiMethod

注：1.试位法每次迭代比二分法多算一次乘法，而且不保证收敛。

2.比例法不是通过使求根区间缩小到0来求根，而是在一定条件下直接构造出一个点列（递推公式），使该点列收敛到方程的根。——这正是迭代法的基本思想。3.RegulaFalsiMethod

xk=(ak+bk)/2§3迭代法

/*Fixed-PointIteration

*/f(x)=0x=g(x)，e.g.,g(x)=f(x)+x等价变换f(x)的根g(x)的不动点思路从一个初值x0出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得

，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f

的根。Sobasicallywearedone!Ican’tbelieveit’ssosimple!What’stheproblem?Ohyeah?Whotellsyouthatthemethodisconvergent?可用§1中的方法迭代函数§3.Fixed-PointIterationxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§3.Fixed-PointIteration说明：①迭代函数不唯一，②迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。

§3.Fixed-PointIteration定理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]上的唯一不动点，并且有误差估计式：§3Fixed-PointIteration证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？④⑤⑥可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性§3.Fixed-PointIterationDef1.Ifthereexistsaneighborhoodofx*,e.g.,B

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

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

证明:注：由于事先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

开始的迭代收敛。即调整初值可得到收敛的结果。注：局部收敛性定理对迭代函数的要求较弱，但对初始点要求较高，即初始点必须选在精确解的附近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§3.Fixed-PointIteration改进、加速收敛

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

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

ξ介于x0与x*之间，设变化不大，，则有微分中值定理x0----x*的预测值一般地，有LinearcombinationUpdateresidual

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

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

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

updatingpredictionAitken’saccelerationxkupdatingFurtherupdatingimprove§3Fixed-PointIterationxyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)Generally,wehave比收敛得略快。3.Steffensen加速：Atkin’smethodfromanotherpointofviewx*x*

4.待定参数法：若

|g'(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列。§4牛顿迭代法

/*Newton-RaphsonMethod*/Newton’smethodfromthepointofviewofaccelerationpredictupdateM=L-1f'(x)简单牛顿公式Newton’smethod牛顿法是解非线性方程（组）的一种常用迭代方法，基本思想是将非线性方程（组）转化为易于求解的线性方程（组）来求解。——

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§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*，且满足§4Newton-RaphsonMethod证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：在单根

/*simpleroot*/

附近收敛快（平方收敛）§4Newton-RaphsonMethod注：Newton’sMethod收敛性依赖于x0

的选取。x*x0x0x0牛顿法应用举例

§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阶导代入即得§4Newton-RaphsonMethod

正割法/*SecantMethod*/

：Newton’sMethod

一步要计算f

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

的值近似f

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

/*tangentline*/割线

/*secantline*/切线斜率

割线斜率需要2个初值x0

和x1。收敛比Newton’sMethod慢，且对初值要求同样高。§4Newton-RaphsonMethod

下山法/*DescentMethod*/

——Newton’sMethod

局部微调：原理若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。

抛物线法

/*ParabolaMethod*/

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

/*tangentline*/割线

/*secantline*/x2x3§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*/计算量未见得减小§4Newton-RaphsonMethod

求复根/*FindingComplexRoots*/

——

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

为初值，同样有设代入公式，令实、虚部对应相等，可得§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.如何刻画这种关系

一般Fixed-PointIteration有，称为线

性收敛

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

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

p

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

/*superlinearconvergence*/。§5OrderofConvergence

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

/*quadraticconvergence*/。

Newton’sMethod有，只要，就有p

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

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

设x*

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

阶收敛。证明：x*k

CThisisaonelineproof...ifwestartsufficientlyfartotheleft.Th3(relationbetweentheconvergencerateandtheiterationfunction)

fortheiterationprocess

xk+1=g(xk),if

g(p)(x)

iscontinuous

aroundtheroot

x*,and

g(l)(x*)=0,l=1,2,…,p,g(p)(x*)0,thentheiterationis

p-convergent

around

x*.Note:1.Th3说明,收敛速度完全取决于迭代函数2.若x[a,b],g(x)0,迭代只可能是线性收敛。3.对牛顿公式，若x*是单根,则f(x*)=0,f(x*)0

g(x*)=0在x*附近平方收敛4.对简单牛顿公式,当Ｍ＝f(x*)时，g(x*)=0，在x*附近平方收敛.一般地，当简单牛顿法收敛，但收敛阶较低

乘法次数n(n+1)/2§6代数多项式的根多项式求值的秦九韶算法

(Horner’sRule)前面讨论的算法都要用到f(x)在某点之值f(x0),甚至导数值f(x0).对于多项式当然可以直接求,但用宋秦九韶算法计算多项式值和导数值,计算量少,结构紧凑。

多项式值f(x0)n次乘法,结构紧凑，程序通用多项式导数值f(x0)f(x)isapolynomialofordern从f(x)中分离出一个2次因子。即：通过可解出一对共轭复根。思路从一对初值(u,v)出发，则有其中(r,s)取决于u

和v，可以看作是(u,v)的函数，即

r=r(u,v)，s=s(u,v)。目标：r=r(u*,v*)=0，s=s(u*,v*)=0。多项式求根的劈因子法

/*SplittingMethod*/§6SplittingMethod将r和s

在初值点(u,v)做一阶Taylor展开，并代入(u*,v*)：从中解出，以更新u和v再迭代，直到r和s充分接近0。每步迭代须计算§6SplittingMethod计算r和s：可记为

bn1若令，则§6SplittingMethod计算

：n2阶多项式n4阶多项式与前一步同理，可导出和的公式。§6SplittingMethod计算

：而前一步得到可见iterationmethodsforthesolutionofnonlinearsystemsNonlinearsystem:f1,f2,…,fn--nonlinearfunctionsBasicideaofiterationforthesolutionof1-dimnonlinearfunctionf(x)=0:Conditionforconvergence:RealrootInitialpointIterationfornonlinearsystem:Conditionforconvergence:Sufficient(notnecessary)conditionfortheiterationconverging

Example6Solution:Converges!Newton’smethod(Newton-Raphsonmethod)—rootfindingfornonlinearfunctiony=f(x)Basicideafor1-dnonlinearfunctions(x0,f(x0))(x1,f(x1))y=f(x)rootx*f(x*)=0xyInthevicinityofx*Checkiff(x0)<:Yes,halt;ElsedrawtangentlineofthecurveGeometrically:usesthetangentlinetothecurveofthenonlinearfunctiontoapproximatethecurveandusetherootofthetangentlinefunctiontoapproximatetherootofthenonlinearfunctionTangentlinetothecurvey=f(x):y=f(x0)+f'(x0)(x-x0),rootThefirsttwotermsofTaylorseriesoffunctiony=f(x)atx0Taylorseriesoff(x)atxkUsethefirsttwoterms(linearfunction—tangentline)toapproximatenonlinearfunctionf(x)mathematicallyNewtoniterationformulaJacobimatrixofF(x)Newton’smethodfornonlinearsystemsF(x)=0VectorfunctionVectorformNewtoniterationformula—vectorform,linearsystem(supposeF´(x(k))isnotsingular).wearefacedwithfindinganinversematrix,somethingwewouldliketoavoid.rather,onecansolveandthenupdate

Advantage:convergesfastDisadvantages:needsalotofcalculationsofderivativesandtheinverseofJacobimatrixateachapproximateroot.

SimplifiedNewton’smethod—reducesthecomputationcostwhileslowsdowntheconvergenceConditionforconvergenceF(x)iscontinuouslydifferential(fi(x1,x2,…,xn)(i=1,2,…,n)andtheirfirstpartialderivativesareallcontinuous)inanopenconvexsetD,andthereexistsx*s.t.F(x*)=0andF´(x)isnotsingular,thentheremustexistaclosedsphere(overlinearlyconverges).IfF´(x)satisfiesLipschitzconditionnearx*,orthereexistsapositiveconstantk,s.t.thenx(k)quadraticallyconvergestox*.SimplifiedNewton’smethodfornonlinearsystemsiff(x0)>,findanotherapproximaterootx1

usingbisection,newton’smethod,etc.Secantmethod—rootfindingfornonlinearfunctiony=f(x)Basicideafor1-dnonlinearfunctionsGeometrically:usesthesecantlinetothecurveofthenonlinearfunctiontoapproximatethecurveandusetherootofthesecantlinefunctiontoapproximatetherootofthenonlinearfunction.Avoidcomputationofderivativeswhileslowdownconvergence.