The root finding methods

The Root Finding Methods and Dept. Your Section and Serial Number Root Finding Algorithm A root-finding algorithm is a numerical method, or algorithm, for finding a value x such A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f.
Finding a root of f(x) g(x) = 0 is the same as solving the equation f(x) = g(x). Here, x is called the unknown in the equation. Conversely, any equation can take the canonical form f(x) = 0, so equation solving is the same thing as computing (or finding) a root of a function. Numerical root-finding methods use iteration, producing a sequence of numbers that hopefully converge towards a limit (the so called ” fixed point”) which is a root. The first values of this series are initial guesses. The method computes subsequent values based on the old ones and the function f.
The Root Finding Methods
1. Bisection Method :
The bisection method is based on the fact that a function will alter sign when it passes through zero. The bisection method can halve the size of the interval in each iteration and eventually find the root by evaluating the function at the middle of an interval and replacing whichever limit has the same sign.

2. False Position Method:
False position method is an algorithm of the prior estimate for which the function value has opposite sign from the function value at the current best estimate of the root. In this method, the root is bracketed. Similar to the secant method, the false position method also uses a straight line to approximate the function in the local region of interest.

3. The Secant Method :
The secant method is based on the assumption that the function is approximately linear in the local region of interest and uses the zero-crossing of the line connecting the limits of the interval as the new reference point. The next iteration starts from evaluation of the function at the new reference point, and then it forms another line. The process is repeated up to the time of finding root.

4. Newton’s Method:
The Newton-Raphson method finds the slope (the tangent line) of the function at the current point and uses the zero of the tangent line as the next reference point. The process is repeated until the root is found.

5. Fixed Point Iteration:
It is a method of computing fixed points of iterated functions. For example, given that a function f defined on the real numbers having real values and given a point x0 in the domain of f, the fixed point iteration is

which gives rise to the sequence which is hoped to converge to a point x. If f is continuous, then one can prove that the obtained x is a fixed point of f, i. e., f(x) = x.

6. Muller’s Method:
Muller’s method is generalized from the secant method, in the sense that it does not require the derivative of the function. It is an iterative method that needs three starting points, , and . A parabola is constructed that passes through the three points; then the quadratic formula is used to find a root of the quadratic for the next approximation. The following equation generalizes the secant method of root finding by using quadratic 3-point interpolation :
Then the following is defined :

(2)

(3)

(5)
The next iteration is described by this equation:

Source :
Abramowitz, M. and Stegun, I. A. (Eds). Handbook of Mathematical Functions with formulas, Graphs, and Mathematical Tables, 9th Printing.