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

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 .

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

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