Lesson 23 - Learning Goals
23.1 Learn why Root finding is useful
23.2 Learn several different root finding Techniques
23.3 Learn how to compare different root finding algorithms
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
Derivation of xi+1
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