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


Copyright © 1996 McGill University. All rights reserved.