LECTURE 23 - Root finding
Introduction
Bisection (internal halving)
Start with an interval [a,b]
containing a single root.
This means the arithmetic
signs of f(a) and f(b) will be different (one positive, one negative).
General idea: Compute the
interval midpoint xm, which then replaces the interval limit with
matching sign. Repeat, stopping when f(xm) is "small",
or when the interval becomes "small" (less than a small
positive constant ).
Note that the size of the
interval is halved at each step.
Bisection - Algorithm
Newton-Raphson method
Pros and Cons of Newton-Raphson
method
Advantages:
Disadvantages:
Secant Method
Derivation of xi+2
Equation of Secant line:
y-yi+1= m*(x-xi+1)
The slope, m, is given by
the two known points:
m = (yi+1 - yi) / (xi+1
- xi)
Also know that point (xi+2
, 0) is on the line:
0-yi+1= {(yi+1 - yi) / (xi+1
- xi)} * (xi+2-xi+1)
xi+2 = xi+1 - {yi+1 * (xi+1
- xi)/ (yi+1 - yi)}
Pros and Cons of Secant
method
Advantages:
Disadvantages:
/* Implementation of the secant method */ #include <math.h> #define TRUE 1 #define FALSE 0 double secant( double (*f)(double), /* function to find root of */ double x1, /* start of interval */ double x2, /* end of interval */ double epsilon, /* tolerance */ int max_tries, /* maximum # of tries */ int *found_flag) /* pointer to flag indicating success */ { int count = 0; /* counter of loops */ double root = x1; /* root value */ *found_flag = TRUE; /* initialize flag to success */ while( fabs(x2-x1)>epsilon) /*check for convergence */ { root = x1 - f(x1)*(x2-x1)/(f(x2)-f(x1)); x1 = x2; x2 = root; count = count + 1; } if( fabs(x2-x1) > epsilon ) /*check for convergence */ *found_flag = FALSE; return(root); /* return root */ }
Go back to lecture menu
Go back to main page