[指南]抛物线法求多项式方程

[]抛物线法求多项式方程 非线性方程求根问题 教材中，对于非线性方程求根问题，主要考虑迭代法。于是教材中大篇幅介绍了迭代的过程，之后又具体论述了开方法和牛顿法以及牛顿法的改进。 对于迭代过程的描述，首先进行根的隔离。考虑将某个范围划分成若干个子段，然后判断哪个子段有根。即通过在给定区间上，从左端点出发按一定步长一步一步向右跨，每跨一步进行一次根的搜索。采用根的二分搜索使加工规模减半。其次，进行迭代过程的设计。其间运用压缩映像原理和局部收敛性定理来判断迭代过程是否对于迭代初值收敛。第三，由于迭代过程的冗长，考虑迭代加速。对迭代过程论述清楚后，介绍开方法和牛顿法。这两者都是按照迭代函数，到迭代收敛性判定，再到迭代加速的顺序展开论述的。其中对于改进的牛顿法还涉及到了弦截法，此法在之后文章将会有提到。 1a开方法迭代函数:,(x),(x，) 2x f(x)(x),x,,牛顿法迭代函数: 'f(x) f(x)k,牛顿法改进(引入下山因子)迭代公式:xx,,,，k1k'f(x)k f(x),(x),x,(x,x)弦截法迭代函数: 0f(x),f(x)0 接下来讨论一种新的迭代法——抛物线法。 基本原理与算法 抛物线法是求多项式方程的实根和复根的有效方法，也可用来求一般函数方P(x),0 程根。抛物线法是正割法的推广。 f(x),0 设有非线性方程 (1) f(x),0 *xxxf(x)xxx首先给出方程(1)根的三个初始近似值，，过三个点(，)，(，000121 'xf(x)f(x)P(x),0P(x),0)，(，)，可构造二次插值多项式，用它来代替，求f(x)21222 *xxxf(x)的根，记为作为f(x),0根的第3次近似值，这就是抛物线法(设(，)，300xxf(x)f(x)(，)，(，)三点不共线)。 1212 一般情况，设已求得方程根的近似值，，，并用过三点(，)xxxxf(x)kik,2k,1i 构造的二次插值多项式来代替，求的根，并记为P(x)P(x),0(i,k,2,k,1,k)f(x)22 *k，1作为根的第次近似值。 xxf(x),0k，1 显然 (2)P(x),f(x)，f[x,x](x,x)，f[x,x,x](x,x)(x,x)2kkk，1kkk,1k,2kk,1 fx,fx()()k,1k其中，fxx, [,]kk，1x,xk,1k fxx,fxx[,][,]k,1k,2kk,1 fxxx, [,,]kk,1k,2x,xk,2k为了求出根，将(2)式写成更加方便的形式，即 P(x),02 2 (3) P(x),a(x,x)，b(x,x)，ckkkkk2 其中， a,f[x,x,x]kk,2k,1k b,f[x,x]，f[x,x,x](x,x)kk,1kk,2k,1kkk,1 c,f(x)kk 2寻求的绝对值最小的根记为h,x,x，于是x,x，h是最ah，bh，c,0kk，1kk，1kkkkk x接近的方程的根。 P(x),0k2 解此二次方程，得 2bb4ac,,kkkkh,, k2ak xxx于是，初值为，，的抛物线法计算公式为 012 2ckx,x, (k=2,3，„) (4) ，1kk2b,b,4ackkkk abc其中，，，由式(3)求得，根式钱符号应选择使(4)式分母的绝对值或模最kkk bxP(x),0大，即符号应取为与同号，也就是说，在的两个根中选择最接近的作为kk2 f(x),0根的第k+1次近似值。 为了计算上的方便，引入量 x,xx,x2021， p,1，q,q,x,xx,x1010 于是 2,qf,pqf，qf()a012pa,pfxxx,,[,,]222012,x,xx,x()()2121,22,qf,pf，p，qf(())b012pb,, (5),2x,xx,x()()2121, pc,pf,c,22,, 将式(5)代入式(4)得到二次函数的零点为: P(x)2 cxx2(,),21hqxx,,,(,) (6) 2321,2bbac,,4, ,xxqxx,，(,)32321, 2其中， a,qf,pqf，qf012 22 b,qf,pf，(p，q)f012 c,pf2 ,2cq,22b,b,4ac 抛物线法(Muller方法)计算步骤:设方程。 f(x),0 fx(1)选定三个初始近似值，x，x，计算相应的函数值，f，f，f(x),0001212 x,x21q,计算。 x,x10 (2)迭代计算: ; p,1，q hba,b,c,h(按(6)式计算，且分母中“”号与取同号); ,x,x，h(x,x); 3221 f,f(x)计算。 33 (3)如果或(为给定精度)，则迭代终止，即为所求，否则转,,,f,,x,,,132312 (4)。 N(4)如果迭代次数超过指定次数，则认为迭代过程不收敛，计算失败，否则以 分别代替，转(2)继续迭代。(x,x,x,f,f,f,q)(x,x,x,f,f,f,q)1231233012012 注意:这里 ,x,x，当x,1时323, ,,,xx,32，当x,1时3,x3, 实际算例 以下将提供《计算方法》中的快速弦截法和本文引用的抛物线法来求解题目，以获得较 深刻认识。 32【例】求方程在内的根。 (,2,,1.5)f(x),x,3x,x,9,0 弦截法 解:取初值，，代入迭代公式依次求解 x,,2x,,101 f(x)k x,x,(x,x)k，1kkk,1f(x),f(x)kk,1 计算结果见下。 xf(x)k kk 0 -2 -9 1 -1 6 2 -1.4 1.776000 3 -1.499 0.389743 4 -1.526841 -0.026330 5 -1.525079 0.000348 6 -1.525102 0.000000 抛物线法 x,,2f,,9解:取初始近似值，x,,1，x,,1.4，代入原式计算得，，f,600121 。 f,1.7762 (1)计算:q,,0.4p,0.6， a,,0.7104b,,3.2448c,1.0656h,0.30767689 ，，， x,x，h(x,x),,1.5230713221 x,,1.523071(2)计算:由，， x,,1x,,1.4312 ，， f,0.0306984f,6f,1.776312 继续迭代，计算， q,0.30767689p,1.30767689 a,,0.13712260b,,2.41940837c,0.040148374h,0.016578716 ，，， 。 x,x，h(x,x),,1.5251114332 计算 f(x),,0.00013234 上述计算结果与快速弦截法的结果相比较，可知抛物线法收敛较快。 可以证明下述局部收敛定理。 **如果在根x邻近存在连续的三阶导数且初始近似值充分接近x，则抛物线方法迭f(x) 代过程是收敛的，且有 0.42*'''*xx,f(x)k，1'* (设) ,f(x),0lim1.84'**6f(x)k,0xx,k 在抛物线方法中，即使选取，，为实数，但也可能是复数，所以抛物线法可xxxx0312 适用求多项式方程的实根和复根。