数值分析课件：第二章 非线性方程求根a

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

*/§1多项式基础/*Polynomials*/（自习）§2二分法/*BisectionMethod*/求

f(x)=0的根原理：若f

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

在(a,b)上必有一根。§2BisectionMethodabx1x2abWhentostop?或不能保证

x

的精度x*2xx*§2BisectionMethod误差分析：第1步产生的有误差第k步产生的xk

有误差对于给定的精度

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

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

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

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

n

m,.InputThereareseveralsetsofinputs.Foreachset: The1stlinecontainsanintegernwhichisthedegreeofapolynomial.n=1signalstheendoffile. The2ndlinecontainsn+1realnumberswhicharethecoefficientsofthepolynomial.Thenumbersareseparatedbyspaces. The3rdlinecontainsanintegerMaxandtworealnumberseps1andeps2,whereMaxisthemaximumnumberofiterations,eps1istheaccuracyboundforxandeps2istheaccuracyboundforp(x). The4thlinecontainsanintegerm(n

m

0),followedbympairsofrealnumbersa1

b1…ambmwhicharetheendpointsoftheintervals[a1,b1]…[am

,bm].Output

EachrootistobeprintedasintheCfprintf:fprintf(outfile,"%12.7f",root);/*hererepresentsaspace*/Ifthereisnorootfoundinaninterval,simplyprint“noroot”.Theoutputofthenextsetmustbeprintedinanewline.SampleInput(representsaspace)210110000.000000010.00000001220.50.523100110000.000000010.00000001210021SampleOutput(representsaspace)1.00000001.0000000noroot1.0000000§2BisectionMethod

试位法

/*RegulaFalsiMethod*/ab(a+b)/2x*(a,f(a))(b,f(b))IsitreallybetterthanBisectionMethod?注：试位法每次迭代比二分法多算一次乘法，而且不保证收敛。§2BisectionMethod§3迭代法/*Fixed-PointIteration

*/f(x)=0x=g(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?§3Fixed-PointIterationxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§3Fixed-PointIteration定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得

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

时，

xk收敛到x*？§3Fixed-PointIteration④⑤⑥可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*的某领域B={x||xx*|}有gC1[a,b]且|g’(x*)|<1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果。§3Fixed-PointIterationAlgorithm: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很大时，此处可改为§3Fixed-PointIteration改进、加速收敛/*acceleratingconvergence*/

待定参数法：若

|g’(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即