Numerical Method Test number 1

Numerical methods involve approximating roots of equations. So all of these methods are toward that goal.

1.Bracketting Method

This is the genral idea of graphical, bisection and false-position method.

We start with two value x1 and x2 that are approximation of the real root xr where f(x1) * f(x2) < 0. Since the function usually changes sign in the vincinity of a root. We then through calculations reduce the size of this bracket. If all things works out (let’s hope it should?) we will be closing in on the real root.

a. Graphical Method:

Graph the function and zoom in to where it intercepts the x-axis (obvious, but not literally)

b. Bisection method: this is better than the last one.

We start with x1 and x2 as our bracket. Then we calculate x3 = (x1+x2)/2. Then our next bracket Would be xi, xj with i,j in {1,2,3} where f(xi) * f(xj) < 0. (since we already have f(x1) and f(x2) of opposite sign, anything between it can only evaluate to the same size with EITHER f(x1) and f(x2) not both. We just reduce our search region in half. We keep doing this until xn and x_n-1 is within a desired error margin.

Error margin = |[x_n - x_(n-1) ] / x_n| * 100%

(absolute value of: newest estimation minus the one prior divided by the newest times 100%. This should yield something like 10% or 1% etc. If it’s 1% we know that we are getting there.)

c. False-position method

The idea of this method is we treat the function over the interval [x1, x2] as a straight line. and wherever this line intercepts the x-axis is our new estimation for the root x. 7th grade mathematic (thank you co Tu’) yields this function for the x-intercept of a line passing thru x1 and x2 of function f(x):

                 f(x2)*(x1-x2)
xr = x2 - __________
                 f(x1) - f(x2)

of course through several iteration we will be closing on the real roots.

2. Open Methods

Open methods differs from Bracketting method because it does not involve two estimation around the roots. For Open Method we start with 1 value and make our way toward the real roots. We just need to have a very good starting point (guess work based on knowledge of the physical system and stuff, perhaps graphical method)

 a. Simple fixed-point iteration

For this method we simple rearrange our equation

f(x) = 0

into:

g(x) = x

Then our next guess for x_n is g(x_(n-1));

It’s very mind boggling simple

Example:

f(x) = e^(-x) - x

we rearrange:

x = e^(-x);

Starting with x0 = 0 we evaluate e^(-0) and this will be our x1 (for the next iteration).. (e^0 = 1 so x1 = 1)
For the 2nd iteration to evaluate x2 = we do g(x1) or  1/e = 0.36787 so x2 = .36787

and so forth and so on. each round we evaluate the estimated error and the true error

b. Newton-Raphson

This one of the open method, that is we start out with a single approximated value x_0. We will then find the tangient of the graph at x0. This line intercepts x-axis at our new approximation x1. We repeat this by finding the tangient at x1 which intercepts x-axis at our new approximation x2. Ideally as we progress our approximated error declines because we are approaching the true value of the root.

formula:

                       f(x_i) 
x_(i+1) =     ——-
                       f’(x_i)
c. The Secant method

Like Newton Raphson, but with a twist. When the derivative is hard to evaluate we estimate the derivative at x_i by:

                      f(x_(i-1)) - f(xi)
f ‘(xi)=         —————-
                       x_(i-1) - xi

and just plug this back to the original Newton-Raphson formula above. Pretty straightforward.

3. Müller’s Method

This is a method to find roots of polynomials. We start with 3 values x0, x1 and x2. We then find the corresponding 3 points on the graph. We then We “approximate” a parabola passing through these 3 points and find where this parabola intercepts the x-axis. That would be our x4 and we repeat the process with x_1-thru-4 (dropping x0 out).

 for parabola is in the form:
ax^2 + bx + c = 0

(lots of formula, but simple for values of a, b and c).

After we have the forumla we solve the quadratic equation for the new estimation x_new and repeat the whole process.