數(shù)值分析課件：第二章 非線性方程求根a

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

*/§1多項(xiàng)式基礎(chǔ)/*Polynomials*/（自習(xí)）§2二分法/*BisectionMethod*/求

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

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

在(a,b)上必有一根?！?BisectionMethodabx1x2abWhentostop?或不能保證

x

的精度x*2xx*§2BisectionMethod誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度

,可估計(jì)二分法所需的步數(shù)k：①簡(jiǎn)單;②對(duì)f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及重根②收斂慢

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

草圖以確定根的大概位置。或用搜索程序，將[a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，且不必要求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)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)思路從一個(gè)初值x0

出發(fā)，計(jì)算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收斂，即存在x*使得

，且g連續(xù)，則由可知x*=g(x*)，即x*是g的不動(dòng)點(diǎn)，也就是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)當(dāng)x[a,b]時(shí)，g(x)[a,b]；(II)0L<1使得

|g’(x)|L<1對(duì)x[a,b]成立。則任取x0[a,b]，由xk+1=g(xk)得到的序列收斂于g(x)在[a,b]上的唯一不動(dòng)點(diǎn)。并且有誤差估計(jì)式：(k=1,2,…)且存在極限k§3Fixed-PointIteration證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？§3Fixed-PointIteration④⑤⑥可用來控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性：若在x*的某領(lǐng)域B={x||xx*|}有g(shù)C1[a,b]且|g’(x*)|<1，則由x0B開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。§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.當(dāng)x很大時(shí)，此處可改為§3Fixed-PointIteration改進(jìn)、加速收斂/*acceleratingconvergence*/

待定參數(shù)法：若

|g’(x)|1，則將x=g(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果用進(jìn)行迭代，則在(1,2)中有現(xiàn)令希望，即