LECTURE 23 - Root finding

Introduction

• Given a function y=f(x)

• Want to find a root or zero of f(x) on an interval [a,b], i.e. a xroot b such that f(xroot) = 0.

• Although the formula for f(x) is known, algebraic techniques for solving f(x)=0 may not work (e.g. arbitrary quintic or polynomial of degree 5; trancendental functions such as f(x) = tan x - e^x).

• A number of iterative techniques allow us to obtain successively better approximations of the root, xroot.
  
  

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

• xlow=a , xhigh=b
  
• xmiddle (xlow + xhigh) /2
  
• if f(xmiddle) < or xlow - xhigh < then xroot xmiddle , STOP.
  
• if f(xmiddle) * f(xroot) < 0 then xlow xmiddle , else xroot xmiddle
  
• go to step 2
  
  

Newton-Raphson method

• Have a guess, xi ,at the root.
  

• An improved guess, xi+1, is a point at which the line tangent to the curve at (xi, f(xi)) intersects the x axis.
  

• Repeat iteration, stopping when f(xi+1) < , or xi+1 - xi < , concluding that xroot xi+1 .
  

• Equation of line tangent to curve y=f(x) at the point (xi , yi) is
  
• y-yi= m*(x-xi)
  
• The slope, m, is given by the value of the derivative of y, evaluated at the point (xi , yi)
  
• m=f'(xi)
  
• Also know that point (xi+1, 0) is on the line:
  
• 0 - yi = f'(xi) * (xi+1 - xi)
  
• xi+1 = xi - f(xi)/f'(xi)

Pros and Cons of Newton-Raphson method

Advantages:

• Converges very quickly to root
  

Disadvantages:

• - Must compute the derivative f'(x), which may be hard, costly.
• - Possible oscillatory behaviour (e.g. f(x)=sin x)
  

Secant Method

• Start with two guesses at the root: xi and xi+1, with
  

• f(xi+1) < f(xi)
  

• Approximate the tangent to the curve at (xi, f(xi)) by the secant.
  

• The secant is the line through (xi , f(xi)) and (xi+1, f(xi+1)).
  

• An improved guess, xi+2 , is the point at which the secant line intersects the x-axis.
  

• Repeat iteration, stopping when f(xi+2) < , or xi+2 - xi+1 < , concluding that xroot xi+2 .
  

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:

• Converges quickly to root (almost as quickly as Newton-Raphson method)
• Does not require computation of y'.
  

Disadvantages:

• -Possible oscillatory behaviour (e.g. f(x) = sin x)
  

/* 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