第二章方程求解

第二章：解方程的数值方法§1.迭代法的一般概念§2.区间分半法§3.不动点迭代§4.Newton-Raphson方法§5.割线法§6.多项式求根1在这一章中，我们将讨论求实函数方程f(x)=0的解的数值方法．方程f(x)=0的解，通常称为方程的（实）根或函数f(x)的零点．求非线性方程的根，除了一些特殊方程，如二次三项式方程，一般需要应用迭代法．所谓迭代法是从给定的一个或几个初始近似值（以后简称初始值）出发，按某种方法产生一个序列（1．2）称为谨代序列，使得此序列收敛于方程f(x)=0的一个根户，即这样，当k足够大时，取作为户的一个近似值．例如，求的问题可以化为求方程的一个根．在第一章中提到，给定才了的一个初始值。（＞0），我们可以由公式§1.迭代法的一般概念2rxxx,.....,,10,.....,......,,,....,,110krrxxxxxpxkklimkx3032x0x产生一个序列对于选代法，一般需要讨论的基本问题是，迭代法的构造，迭代序列的收敛性和收敛速度以及误差估计．解方程f(x)=0的一个迭代法产生的选代序列是否收敛于f(x)=0的一个根，通常与初始近似值选取范围有关，若从任何可取的初始值出发都能保证收敛，则称之为大范围收敛．但若为了保证收敛性，必须选取初始值充分接近于所要求的根（解），则称它为局部收敛．为了讨论收敛速度，我们先给出一种衡量它的标准——收敛阶数．假设一个选代法收敛（局部或者大范围），,是方程f(x)=0的一个解．令若存在实数人和非零常数C，使得§1.迭代法的一般概念32/)3(11kkkxxx,....,.....,,10rxxx}{kxkkxlimkkxe(1.3)则称该选代法为人阶收敛，或者说它的收敛阶数为,若为整数，则可将（1．3）式改写成的大小反映了收敛速度的快慢．若=1，则说该选代法是线性收敛的；若＞1，则说该迭代法为超线性收敛．通常，局部收敛方法比大范围收敛方法收敛得更快．因此，一个合理的算法是先用一种大范围收敛方法求得接近于根的近似值，再以其作为新的初始值使用局部收敛方法．§1.迭代法的一般概念4Ceekkk1limCeekkk1lim解非线性方程f(x)=0（2．1）的一种直观而又简单的迭代法是建立在介值定理上，称之为二分法或区间分半法．设函数f(x)在区间上连续，且f(a)f(b)0．据介值定理知，方程f(x)=0在区间内至少有一个根．记=，设为区间的中点：若，是予先给定的足够小的量，则是所要求的方程f(x)=0的一个根的近似值．若，且f(a)f(b)0则区间内至少有方程f(x)=0的一个根，令；若则区间内至少有f(x)=0的一个根，令。因此，可继续将区间分半，即将或分半，得中点§2.区间分半法5ba,ba,ba,11,ba1p2111bap)(1pf1p)(1pf11,bp1212,bbpa0)()(11bfpf11,pa1212,pbaa22,ba11,pa11,bp11,ba即或如此继续，可得到序列当区间中点的函数值的绝对值小于误差容限或区间长度小于容限时，过程终止．最后区间的中点便作为方程f(x)=0的一个根的近似。下面给出区间分半法求方程f(x)=0的近似根的一种算法．算法2．1假设f(x)是区间上的连续函数，f(a)f(b)＜0，求f(x)=0的一个解．输人端点a，b；容限TOL1，TOL2；最大迭代次数m．输出近似解或失败信息．stepl对n=1，…，m做step2—4．step2step3若，则输出（P），停机．step4若f(p)f(b)0，则，否则·step5输出（‘Methodfailed’）；停机．§2.区间分半法62222bap2112bpp2112pap,....,.....,2,1npppba,p2/)(bap22/)(1)(TOLbaTOLpf或papb假设函数f(x)在区间[a,b]上连续，且两个端点处函数值f(a)，f(b)异号．不难看出，区间分半法产生的序列必收敛于方程f(x)=0的一个根．因此，它是大范围收敛的．并且，得到的序列有误差估计式(2.2)这是一个先验的绝对误差界．若令表示预先给定的绝对误差容限，要求，则只要则两边取对数得（2.3）§2.区间分半法7p,...,.....,,21nppp)(21abppnnppn)(21abnabn22lg/)(lgabn于是，可取n为大于的最小整数．这就给我们提供了一个迭代终止准则．我们可以在第n步终止迭代．在算法2．1的第3步的终止准则的缺点是，有可能出现很接近于零，但却与根相差很大．例如，的一个根为。令则当n＞l时，但要则必须n＞1000．另一个较好的终止准则是，考虑到本身的大小，令表示相对误差容限，一直迭代到时，终止迭代过程．§2.区间分半法82lg/)(lgabn1)(TOLpf)(npfp10)1()(xxf1pnpn/11310)(npf310ppnpnnnppp1例设由于f(x)连续，且,因此f(x)在区间[1，2]内至少有一个根．又因从而f(x)在（1，2）中单调增加，故f(x)在（1，2）内有唯一根．我们用区间分半法来求根的近似值，要求根的近似值的绝对误差不超过．由于因此要使，只要即两边取对数得因此，取时，可使.用区间分半法迭代14次得结果见表2.1§2.区间分半法9p1)(3xxxf051)2()1(ff)2,1(,013)(2xxxfpp410nnnnabpp2/12/)12(2/)(4102/1n4102/1n4102n3.132lg10lgn14n410ppn表2.1§2.区间分半法101234567891011121314111.251.251.31251.31251.31251.32031251.324218751.324218751.324218751.3247070311.3247070311.32470703121.51.51.3751.3751.343751.3281251.3281251.3281251.3261718751.3251953121.3251953121.3249511711.3248291011.51.251.3751.31251.343751.3281251.32031251.324218751.3261718751.3251953121.3249511711.3249517711.3248291011.3247680660.875-0.2970.2246-0.05150.08260.01458-0.0187-0.023nbnanp)(npfn3102.631004.25107.441095.941074.44105.1使用区间分半法求方程的根时，从其误差估计式看出，近似解的误差下降速度不快．但此方法比较简单，且安全可靠．在实际应用中，这个方法可以用来求根的初始近似值．§2.区间分半法11解非线性方程f(x)=0（3．1）的问题，常常将它化为解等价方程x＝g(x)．（3．2）方程（3．2）的根又称为函数g的不动点．例1方程在区间中有唯一根．我们可以用不同方法将它化为方程：(1)(2)(3)(4)(5)等等。§3.不动点迭代12042)(23xxxf2,142)(231xxxxgx2/12)/2()()(xxxgxg2/1332/2)(xxgx2/14)21(2)(xxgxxxxxxxgx4342)(2235为了求g的不动点，我们选取一个初始近似值，令（3．4）以产生序列，这一类选代法称为不动点迭代法，或Picard迭代，g(x)又称为迭代函数。显然，若g(x)连续，且g的一个不动点。因此，P必为方程（3．1）的一个解．算法2．2用不动点迭代求方程x=g(x)的一个解．输人初始值；误差容限TOL；最大迭代次数m．输出近似解或失败信息．stepl对k=1，2，…，m做step2—3．step2step3若，则输出（）；停机，否则．step4输出（‘Methodfailed’）；停机．在第3步中，迭代终止准则可用§3.不动点迭代130x,......2,1),(1kxgxkkkx是则ppxkk,limp0x)(0xgpTOLxp0ppx0TOLpxp0例2就方程（3．3），取初始值，对g(x)的五种选择应用迭代公式（3．4）计算得结果见表2．2．§3.不动点迭代145.10x1234567891011121329-2.375-72.560.5590169941.3829872000.8230505931.3119556820.9332270691.2623867540.9970543661.2265420691.0379748141.2003529761.0654751741.1811927851.0844308331.1272225841.0690449681.1416378781.1283710451.1307611191.1303294161.1304073551.1303932831.1303958231.1303953651.1303954471.1303954321.1960784321.1330205311.1303954351.130395435k)(11kkxgx)(12kkxgx)(13kkxgx)(14kkxgx)(15kkxgx5107.35101.52/1333.0续表2.2从表2．2看到，选取迭代函数为，分别迭代12次和4次得到方程的近似根1．130395435．若选取作为迭代函数，则在为奇数时迭代子序列§3.不动点迭代1530313233495089901091101191201.1330746491.1281163211.1323221241.1287580221.1302789221.1304942001.1303952771.1303955691.1303954291.130394401.1303954341.130395436k)(11kkxgx)(12kkxgx)(13kkxgx)(14kkxgx)(15kkxgx)(4xg)(5xg)(3xg单调增加，k为偶数时迭代子序列单调减小，迭代120次方能得到近似根1·130395436。若选取作为迭代函数，则迭代序列不收敛。选取为迭代函数，出现负数开方，因而无法继续进行迭代。这个例子说明，我们选择迭代函数的基本原则是，首先必须保证Picard迭代产生的迭代序列在g（x）的定义域中，以使迭代过程不致于中断；其次要求迭代序列收敛且尽可能收敛得快。定理1假设g(x)为定义在[a,b]上的一个实函数，它满足下列条件：(1)(2)Lipschitz条件，且Lipschitz常数L＜1，即存在正常数L,使得(3.5)§3.不动点迭代16)(1xg)(2xg,....,.....,,10kxxxkxbaxbaxg,,,)(bayxyxLygxg,,,)()(那么，对任意的初始值由Picard迭代（3.4）产生的序列都收敛于g的唯一不动点，并且有误差估计式(3.6)其中证明首先证明g的不动点存在且唯一。令据条件（1）知又据条件（2）知，g（x）在[a,b]上连续，从而h(x)在[a,b]上也连续·因此，方程h(x)=0在[a,b]上至少有一个根，而且，方程h(x)=0在[a,b]上只能有一个根.。否则，假设存在两个根,则因§3.不动点迭代17bax,0p011xxLLekkpxekk)()(xgxxh0)()(0)()(b