Numerical Methods For Engineering: Root Of A Polynomial

Muller's Method

Muller's Method is a generalization of the secant method, in the sense that it does not require the derivate of the function. It is an iterative method that requires 3 starting points (xo, f(xo)) , (x1, f(x1)) , (x2, f(x2)). A parabola is constructed that passes through the three points; the quadratic formula is used to find a root of the quadratic for the next approximation. It has been proved that near a simple root Muller´s Method converges faster than the secant method and almost as fast as Newton's method. The method can be used to find real or complex zeros of a function and can be programed to use complex arithmetic.

The fact that this method can be used to find complex roots is one of the main advantages of Müller's method.

Comparison With Secant Method:

Procedure:
Consider $P(x)=a(x-x_2)^2+b(x-x_2)+c$
Once

x₃

is determined, let

x_o = x₁ , x₁ = x₂ , x₂ = x₃

and repeat.
Example:
Suppose we wish to find a root of the polynomial X7 + 3X6 + 7X5 + X4 + 5X3 + 2X2 + 5X + 5.
We will use Xo=0, X1=-0.1 and x2=-0.2 as our three numerical approximations. Tolerance = 0.0001
Results are shown in the next table:

Thus the last step, the tolerance is met, and therefore, after six iterations, our approximationto the root is -0.706826.

References:

http://math.arizona.edu/~restrepo/475A/Notes/sourcea/node25.html

http://math.fullerton.edu/mathews/n2003/MullersMethodMod.html

http://www.ece.uwaterloo.ca/~dwharder/NumericalAnalysis/10RootFinding/mueller/

Bairstow's Method

Bairstow Method is an iterative method used to find both the real and complex roots of a polynomial. It is based on the idea of synthetic division of the given polynomial by a quadratic function and can be used to find all the roots of a polynomial. Given a polynomial say

Bairstow's method divides the polynomial by a quadratic function: $\displaystyle x^{2}-rx-s.$

Now the quotient will be a polynomial: $\displaystyle f_{n-2}(x)=b_{2}+b_{3}x+b_{4}x^{2}+...+b_{n-1}x^{n-3}+b_{n}x^{n-2}$

and the remainder is a linear function: $\displaystyle R(x)=b_{1}(x-r)+b_{0}$

Since the quotient $f_{n-2}(x)$ and the remainder are obtained by standard synthetic division the co-efficients can be obtained by the following recurrence relation.

$\displaystyle b_{n}=a_{n}$ | $\displaystyle b_{n-1}=a_{n-1}+rb_{n}$ | $\displaystyle b_{i}=a_{i}+rb_{i+1}+sb_{i+2}$ for i = n-2 to 0

It may be noted that $x^{2}-rx-s$ is considered based on some guess values for . So Bairstow's method reduces to determining the values of r and s such that is zero.