Transcript No Slide Title

Root Finding
UC Berkeley
Fall 2004, E77
http://jagger.me.berkeley.edu/~pack/e77
Copyright 2005, Andy Packard. This work is licensed under the Creative Commons Attribution-ShareAlike
License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/2.0/ or send a letter to
Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
Solving Algebraic Equations
From linearity, it is easy to solve the equation
3x  7  12
or even the system of equations
2 x  5 y  12
x  6y  3
But what about an equation like
x
tan( x)e  1  0
Solving Algebraic Equations
In general, given a continuous function f, how do you find
the (any, all) solutions to
f ( x)  0
f(x)
Graph of f(x) versus x
x
“roots” of f
Iterative Methods
Iterative methods start with a “guess”, labeled x0 and
through “easy” calculations, generate a sequence
x1, x2, x3, …
Goal is that sequence satisfies
lim xn  x

n
convergence to
a limit, x*
and
 

f x 0
x* is a solution
Rate of Convergence
Suppose {xn} is a sequence, converging to a limit x*. Let
en denote the difference x*-xn
If there is a constant C, and positive exponent  such
that for large n
en 1  C en

then the sequence {xn} converges with order  to x*.
– “linear” convergence is =1
• The sequence 3, 2.5, 2.25, 2.125, 2.0625, … converges linearly
to 2 (here C = ½)
• The sequence 3, 2.1, 2.01, 2.001, 2.0001,… converges linearly to
2 (here C=0.1)
– “quadratic” convergence is =2
• The sequence 3,2 1 2 ,2 1 4 ,2 116 ,2 1 256 ,2 1 65536,... converges
quadratically to 2 (here C=1)
Stopping Criteria
Suppose {xn} is a sequence, converging to a limit x*. The
limit x* has the property f(x*)=0. Let tol be a positive
number
But we don’t know x*
Absolute (in x)
|xn – x*| < tol
“Absolute”
|xn – xn-1| < tol
Relative (in x)
|xn – x*| < tol × |x*|
“Relative”
|xn – xn-1| < tol × |xn|
Absolute in f
|f(xn)| < tol
Sometimes (in bisection, for example)
we can bound this, even without
knowing x*.
Bisection Method, basic idea
Suppose f is continuous,
xM
xL
f  xL 
f xL   0
f xR   0
Intermediate value theorem
f  xR 
xR
There must be a root x* between xL and xR.
•Let xM be the midpoint. |xM-x*|≤0.5|xR-xL|
•Based on sign of f xM  replace either xL or xR with
xM, and repeat.
Simple pseudo-code: Bisection
% Start with xL, xR,
fL = f(xL); fR = f(xR);
while StoppingCriteriaNotMet
xM = 0.5*(xL+xR);
yM = f(xM);
if fL*fM<0
% replace R with M
xR = xM;
else
xL = xM;
end
end
Examples: Bisection
Newton’s Method: motivation
Graph of h(x), the straight-line
approximation to f at x0
graph of f(x)
x
x0
hx0   f x0 
functions are equal at x0
h x   f x0  for all x
'
'
slope of h (everywhere)
equals the slope of f at x0
hx   ax  b for some a, b
graph of h is straight line
hx   f x0   f x0 x  x0 
'
Newton’s Method: motivation
Graph of h(x), the straight-line
approximation to f at x0
graph of f(x)
x
x0
hx   f x0   f x0 x  x0 
'
Approximation to f, near x0
Approximate solving f(x)=0 by solving (easier) h(x)=0
f x0 
hx   0  x  x0  '
f x0 
Newton’s Method: iteration
Graph of h(x), the straight-line
approximation to f at x0
graph of f(x)
*
xapp
x
*
app
x0
f x0 
 x0  '
f x0 
f  xk 
xk 1  xk  '
f  xk 
x
Algorithm: Repeat, using
x*app as the “initial” point.
General form of the iteration
Newton’s Method: iteration
f  xk 
xk 1  xk  '
f  xk 
General form of the iteration
Facts about Newton’s method to solve f(x) = 0
•At each step, need to evaluate the function and its
derivative at a single point
•Not guaranteed to converge. It might “cycle”, and it
might diverge.
•If it does converge, the convergence is quadratic.
•More complicated than bisection, can work better.
•Generalizes to N equations in N unknowns
Function handles and feval
Several Matlab functions solve your problem by repeatedly
calling functions that you supply
New data type: add to
– finding zeros of a function (fzero)
list with double, cell,
– Integrating a function (trapz, quad)
char, struct.
– Integrating a differential equation (ode45)
– minimizing a function (fminbnd, fminsearch)
For example, in calling fzero, you must pass a referenceto-the-function (called a function handle) that you want
fzero to find the zeros of. Use the @ operator to get the
Any function (built-in,
reference.
mfile, etc)
>> shan = @sin;
>> class(shan)
>> feval(shan,linspace(0,pi,5))
Function handles and feval
General syntax for feval is
function handle
[out1,out2,…] = feval(FuncH,arg1,arg2,…)
Output argument list
Input argument list