马勒法

Muller方法是线性插值的进一步伸展，采用经过三个已知点所确定的抛物线与x轴的交点作为下一个近似解。Muller方法的算法原理如图所示，对于求

y=f(x)的零点x''来说，假设已经得到互异的三个点x0,x1,x2处的函数值f(x0),f(x1),f(x2),那么可以 经过平面上的三个点（x0，f(x0)),(x1,f(x1))以及(x2,f(x2))作为抛物线，记为y=p(x)(图中较粗的那条曲线），并把抛物线y=p(x)与x轴的交点x3作为f(x)=0的近似解。接下来再经过（x1，f(x1)),(x2,f(x2))以及

(x3,f(x3))作为抛物线……从而形成一个算法，算法的关键是求抛物线与x轴的交点。

假设过（x0，f(x0)), (x1,f(x1))以及(x2,f(x2))这三个点的抛物线方程为

y=a(x-x2) ^2+b(x-x2)+c ************************************ (1)

依次用（x0，f(x0)),(x1,f(x1))以及(x2,f(x2))分别代入（1）式，得

f(x0)= a(x0-x2) ^2+b(x0-x2)+c ****************************(2)

f(x1)= a(x1-x2) ^2+b(x1-x2)+c *************************** (3)

f(x2)= a(x2-x2) ^2+b(x2-x2)+c *****************************(4)

由(4)式可得c=f(x2),分别代入到(2)(3)中，整理后得

a(x0-x2) ^2+b(x0-x2)+c=f(x0)-f(x2)********************** (5)

a(x1-x2) ^2+b(x1-x2)+c=f(x1)-f(x2)********************** (6)

为了把上面的方程组（5）（6）的解更有规律性，令

h0= x1-x0

h1= x2-x1

q0=[f(x1)-f(x0)]/h0 *************************************(7)

q1=[f(x2)-f(x1)]/h1

把上面的定义的方程组分别代入（5）（6）中，整理后可得

a=(q1-q0)/(h1+h0)

b=q1+ah1 ***********************************************(8)

再在（1）式中令y=0，利用求根公式解关于x-x2的方程可以得到

x1-x2=[(-b)+√（b ^2-4ac）]/2a************************* (9)

x1= x2 +[(-b)+√（b ^2-4ac）]/2a************************ (10)

由图可以看出，如果得到了插值抛物线的两个零点，应该取与x2更靠近的哪一个最为问题的近似解。利用一元二次方程的求根的计算方法，可以得到

x= x2 – 2c/[(b+sign(b)+ √（b ^2-4ac）] **************(11)

上面的（11）式可以用来求下一个迭代点，其中a，b,c可以利用（7）式和（9）式得到，从而利用Muller方法求函数零点的关键问题得到解决。