These are the first set of questions. See homepage for more practice problems. Here is a description of various approximation algorithms. 

The notes are taken from Chapra, Steven. Numerical Methods for engineers with Software and Programming Applications 4th ed. Mcgraw Hill, New York, NY, 2002

Taken from Table PT2.3 pg. 212, Chapra

 

Method	Initial guess	convergence rate	stability	Accuracy	Breadth of Applications	Prog. effort	Comments
direct	--	--	--	--	limited
graph	--	--	--	Poor	real roots	-	May take more time than num. Method
Bisection	2	slow	always	good	real roots	easy
false position	2	Slow/medium	always	good	real roots	easy
modify FP	2	medium	always	good	real roots	easy
Fixed point iter	1	slow	possible divergent	good	general	easy
Newton-Raphson	1	fast	Possible divergent	good	general	easy	needs f'(x)
Modify N-R	1	fast for multi roots; medium single root	Possible divergent	good	general	easy	requires f'(x) & f''(x)
Secant	2	Medium to fast	Possible divergent	good	general	easy	Initial guess need not bracket root
Modified Secant	1	Medium to fast	Possible divergent	good	general	easy
Muller	2	Medium to fast	Possible divergent	good	Polynomials	Moderate
Bairstow	2	fast	Possible divergent	good	polynomials	Moderate

These methods are for approximating the zero crossing of functions, which is useful for complex function when algebraic techniques are too tedious. Also a computer can uniformly apply these methods to the functions without being programmed to solve the problem algebraically. 

 

Graphical Method

Plot a graph of the function and narrow down where the function crosses zero. The following methods use similar methods 

Bisection (Bolzano) method
 

Based on the idea that the zero crossing is lies between points between points where f(x1)>0 and f(x2)<0. The method then uses a binary search to identify the zero-crossing that is between x1 and x2. You can imagine the problems this method with multiple peaks and troughs or max/min that lie on y=0, such as x^2
 

The false position method & modified version

This method improves on Bisection by taking into account a line between two guesses. The zero intersect of the line is the input for the next iteration along with the other x such that the zero cross is between the two points. Converges slowly when curve bends sharply between the two guesses, such as for f(x)=x^10-1. The solution is to divide on of the slowly converging bound (such as in a binary search). 

Fixed Point iteration 
 

Unlike the previous methods, this method only uses one initial guess as opposed to two. However, this means the method could divergent from approaching the real answer. The concept is to manipulate a function to be solved into the form of x=g(x) this can be achieved algebraically or by adding x to both sides. The new value of x is xnew = g(x). The final convergence is when x = g(x). Convergence is ensured if |g’(x)| <1.
 

Newton-Raphson method
 

A popular root locating formula. This method approximates the curve as the line tangent to the curve being solved. The Taylor series can be used to derive the formula. In addition, the derivation shows that this method converges quadratically. 

The Newton-Raphson method can be modified (Ralston & Rabinowitz) to solve polynomials with multiple roots with quadratic convergence as opposed to linear convergence. 

The Newton-Raphson method can be used to solve system of nonlinear equation. This involved multivariable Taylor series and the Jacobian. The Jacobian is also used in Kalman filter, which is an important method in tracking systems (I am still in the process of learning this).
 

Secant Method & Modified

This method approximates the derivate of f(x) and therefore is useful when it is difficult to solve for f’(x). Two initial guesses are used. This method is very similar to the False-point method, however the secant method converges faster. 

The modified version eliminates one of the initial guesses and uses a small delta offset from the iterated x.

The secant method can also be used to solve two nonlinear simultaneous equations. The two equations are set equal and algebraically rearranged into the form x = g(x).
 

Muller Method 

This method is used to find the roots of polynomials. Other methods extrapolate the tangent at the guessed x value. The Muller method interpolates a parabola between three points. The resulting parabola can be solved for its zero crossing, which is the next input into the iteration. The method should converge fast as the next x will be a closer estimate than the secant’s straight-line estimate.

Bairstow’s Mehtod

This is another method to find roots of polynomials. It works by dividing the polynomial by x-t, where x=t is the initial guess. No remainder means that x is the root. Otherwise a root is not found and the iteration happens with a new guess of x. Looks complicated.