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

• 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)

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 .

Derivation of 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

• Converges very quickly to root

• - 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

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

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

```