Math 472 Lecture 5
Chapter 1 Solving Equations
Zhenhua Wang
U Michigan
1 / 18
1 Solving equations
Problem: solve the equation f (x) = 0 for x.
Definition 1.1
The function f (x) has a root at x = r if f (r) = 0.
Why we study it?
• Shows up in almost any practical application.
• Sometimes the function f is explicit and easy to work with, e.g.,
f (x) = ex sin x. But sometimes not, e.g., f (x) denotes the freezing
temperature of some mineral water under x atmospheres of pressure.
We will learn several methods:
• trade-off between efficiency and the amount of input needed
• more efficient methods may require extra regularity for f , the cost of
evaluating f (x) is an important factor here
2 / 18
1.1 The bisection method
• Main idea of the bisection method:
Bracketing
• Think of how you would look up a word in
a dictionary
• How to make sure that a root exists?
Figure: f (x) = x3 + x 1
Theorem 1.2 (by Intermediate Value Theorem)
Let f be a continuous function on [a, b], satisfying f (a)f (b) < 0. Then, f has
a root in (a, b), i.e. there exists a < r < b such that f (r) = 0.
3 / 18
1.1 The bisection method
The Bisection Method:
• Assume we are given an interval [a, b] where f (a)f (b) < 0.
• Bisection: Let c = (a + b)/2. If f (c) 6= 0, then either
(i) f (c)f (a) < 0 in which case the root must be in [a, c]; or
(ii) f (c)f (b) < 0 in which case the root is in [c, b].
• By repeating the bisection step, we can make the interval containing the
root arbitrarily small.
4 / 18
1.1 The bisection method
Example 1.1
Find the root of x3 + x 1 = 0 on the interval [0, 1]
We conclude from the table that the solution is bracketed between
a9 ⇡ 0.6816 and c9 ⇡ 0.6826. The midpoint of that interval c10 ⇡ 0.6821 is our
best guess for the root, with an error at most c9 2 a9 = 0.0005.
5 / 18
1.1 The bisection method
Example 1.1
Find the root of x3 + x 1 = 0 on the interval [0, 1]
We conclude from the table that the solution is bracketed between
a9 ⇡ 0.6816 and c9 ⇡ 0.6826. The midpoint of that interval c10 ⇡ 0.6821 is our
best guess for the root, with an error at most c9 2 a9 = 0.0005.
5 / 18
1.1 The bisection method
Example 1.1
Find the root of x3 + x 1 = 0 on the interval [0, 1]
We conclude from the table that the solution is bracketed between
a9 ⇡ 0.6816 and c9 ⇡ 0.6826. The midpoint of that interval c10 ⇡ 0.6821 is our
best guess for the root, with an error at most c9 2 a9 = 0.0005.
5 / 18
1.1 The bisection method
Example 1.1
Find the root of x3 + x 1 = 0 on the interval [0, 1]
We conclude from the table that the solution is bracketed between
a9 ⇡ 0.6816 and c9 ⇡ 0.6826. The midpoint of that interval c10 ⇡ 0.6821 is our
best guess for the root, with an error at most c9 2 a9 = 0.0005.
5 / 18
1.1 The bisection method
The Bisection Algorithm:
We are given [a, b] such that f (a)f (b) < 0;
while (b 2 a) > T OL do
c a+b
2
;
if f (c) = 0 then stop, end;
if f (a)f (c) < 0 then
b c;
else
a c;
end
end
The approximate root is (a + b)/2 with error less than T OL
To use bisect.m, first define a Matlab function by:
>> f=@(x) xˆ3+x-1;
This command actually defines a “function handle” f, which can be used as
input for other Matlab functions. Then the command
>> xc=bisect (f,0,1,0.00005)
returns a solution correct to a tolerance of 0.00005.
6 / 18
1.1 The bisection method
Efficiency of the Bisection Method:
• With the initial interval [a, b] and after n bisections, we arrive at some
interval [an , bn ] with length (b a)/2n . Choosing the midpoint
xc = (an + bn )/2 gives a best estimate of the solution r with
b a
Solutions error = |xc r| < (1)
2n+1
and n + 2 function evaluations.
• Each function evaluation cuts the uncertainty in the root by a factor of 2
• Other (better) root–finding algorithms are less predictable and have no
analogue to (1).
• (1) provides the number of steps needed to get a desired precision.
7 / 18
1.1 The bisection method
Definition 1.3
A solution is correct within p decimal places if the error is less than
0.5 ⇥ 10 p .
Example 1.2
How many steps of the Bisection Method is needed to find a root of
f (x) = cos x x in the interval [0, 1] to within six correct places?
.
fo I o flD cost 1 so
b least so
nft.sn
lbz eo 5xIo At step
zine lot
I 3 06 logzhi.zpp
log.ph 8 / 18
og
1.2 Fixed-point iteration
Motivation: input
trap output
• Use a calculator (make sure it is in radian mode) to apply cos(·) function
successively to an arbitrary starting number
• The resulting sequence converges to 0.7390851332
• This is an example of using the Fixed-Point Iteration (FPI) method to get
one solution to the equation
cos(x) = x.
Definition 1.4
The real number r is a fixed point of the function g if g(r) = r.
The number r = 0.7390851332 is (approximately) a fixed point of cos(x).
The function g(x) = x3 has three fixed points, namely, x = ±1, 0.
We used the Bisection Method in Example 1.2 to solve the equation
cos x x = 0. It could be written as cos x = x, and the root is just the fixed
point of the function g(x) = cos x.
9 / 18
1.2 Fixed-point iteration
The Fixed-Point Iteration Algorithm:
x0 initial guess;
for i = 1, 2, . . . , N do
xi g(xi 1 );
end
return xN
That is,
x1 = g(x0 )
x2 = g(x1 )
x3 = g(x2 )
···
FPI may or may not converge.
But, if it does converge and g(·) is continuous, then it must converge to a
fixed point, which could be justified as follows:
why? why?
g(x) = g( lim xn ) = lim g(xn ) = lim xn+1 = x
n!1 n!1 n!1
10 / 18
1.2 Fixed-point iteration
• FPI can solve the fixed-point problem, how about finding a root?
• Can every equation f (x) = 0 be turned into g(x) = x?
Yes, and in many different ways!
• Example: x3 + x 1 = 0 can be transformed into:
1. x = 1 x3 with g(x) = 1 x3
p p
2. x = 1 x with g(x) = 3 1 x
3
1 + 2x3 1 + 2x3
3. x = (add 2x to x + x = 1) with g(x) =
3 3
1 + 3x2 1 + 3x2
• Will FPI have the same performance for all these choices? Or will the
choice matter?
11 / 18
1.2 Fixed-point iteration
• Recall that the bisection algorithm found the approximate root of 0.682
after 9 iteration
.
• FPI for x = g(x) = 1 x3 does not even converge!
12 / 18
1.2 Fixed-point iteration
• Recall that the bisection algorithm found the approximate root of 0.682
after 9 iteration
. p
• FPI for x = g(x) = 3
1 x converges, but slower than the bisection
method
13 / 18
1.2 Fixed-point iteration
• Recall that the bisection algorithm found the approximate root of 0.682
after 9 iteration
. 1 + 2x3
• FPI for x = g(x) = converges very fast!
1 + 3x 2
• Why does FPI performance differ so dramatically between these
equivalent problems?
• It helps to look at the geometry of the FPI method using the cobweb
diagram.
14 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Draw line segments
(i) vertically to the function g(x), which represents xi ! g(xi ),
(ii) horizontally to the diagonal line y = x, which represents xi+1 = g(xi ).
This geometric illustration of a FPI is called the cobweb diagram.
.
Geometry of FPI: x = g(x) = 1 x3
15 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. p
x = g(x) = 3 1 x
16 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. p
x = g(x) = 3 1 x
16 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. p
x = g(x) = 3 1 x
16 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. p
x = g(x) = 3 1 x
16 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. p
x = g(x) = 3 1 x
16 / 18
1.2 Fixed-point iteration
Geometry of FPI:
. 1 + 2x3
x = g(x) =
1 + 3x2
17 / 18
1.2 Fixed-point iteration
• Can you spot the difference?
• What makes the cobweb to “spiral out” or “spiral in”?
• The slope of g near the fixed point!
flat likely toconverge
steep likely to spiralout
18 / 18
