Chapter 3: Nonlinear equations in One Variable
A First Course in Numerical Methods (published by SIAM, 2011) Nonlinear equations in one variable Goals
Goals of this chapter
To develop useful methods for a basic, simply stated problem, including such
favourites as xed point iteration and Newton’s method;
to develop and assess several algorithmic concepts that are prevalent
throughout the eld of numerical computing;
to study basic algorithms for minimizing a function in one variable.
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 1 / 32
Nonlinear equations in one variable Outline
Outline
Bisection method
Fixed point iteration
Newton’s method and variants
Minimizing a function in one variable
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 2 / 32
Nonlinear equations in one variable Motivation
Roots of continuous functions
For a given continuous function f = f(x), consider the problem
f(x) = 0,
where x is the independent variable in [a,b].
If x∗ is value of x where f vanishes then x∗ is a root or zero of f.
How many roots? This depends not only on the function but also on the
interval.
Example: f(x) = sin(x) has one root in [−π/2,π/2], two roots in
[−π/4,5π/4], and no roots in [π/4,3π/4].
Why study a nonlinear problem before addressing linear ones?!
One linear equation, e.g. ax = b, is too simple (solution: x = b=a, duh!),
whereas a system of linear equations (Chapter 5 and 7) can have many
complications.
Several important general methods can be described in a simple context.
Several important algorithm properties can be de ned and used in a simple
context.
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 3 / 32
Nonlinear equations in one variable Motivation
Desirable algorithm properties
Generally for a nonlinear problem, must consider an iterative method: starting
with initial iterate (guess) x0, generate sequence of iterates x1, x2, ..., xk,...
that hopefully converge to a root x∗.
Desirable properties of a contemplated iterative method are:
E cient: requires a small number of function evaluations.
Robust: fails rarely, if ever. Announces failure if it does fail.
Requires a minimal amount of additional information such as the derivative
of f.
Requires f to satisfy only minimal smoothness properties.
Generalizes easily and naturally to many equations in many unknowns.
Like many other wish-lists, this one is hard to fully satisfy...
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 4 / 32
Nonlinear equations in one variable Bisection
Outline
Bisection method
Fixed point iteration
Newton’s method and variants
Minimizing a function in one variable
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 5 / 32
Nonlinear equations in one variable Bisection
Bisection method
Simple
Safe, robust
Requires only that f be continuous
Slow
Hard to generalize to systems
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 6 / 32
Nonlinear equations in one variable Bisection
Bisection method development
Given a = b) | (fa*fb >= 0) | (atol 1 so
rate =−log10(ρ) 0.
Newton’s method can be written as a xed point iteration with
g(x) = x− f(x)f′(x).
From this we get g′(x∗) = 0.
In such a situation the xed point iteration may converge faster than linearly:
indeed, Newton’s method converges quadratically under appropriate
conditions.
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 28 / 32
Nonlinear equations in one variable Function Minimization
Outline
Bisection method
Fixed point iteration
Newton’s method and variants
Minimizing a function in one variable
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 29 / 32
Nonlinear equations in one variable Function Minimization
Minimizing a function in one variable
Optimization is a vast subject, only some of which is covered in Chapter 9.
Here, we just consider the simplest situation of minimizing a smooth function
in one variable.
Example: nd x = x∗ that minimizes
ϕ(x) = 10cosh(x/4)−x.
From the gure below, this function has no zeros but does appear to have
one minimizer around x = 1.6.
0 0.5 1 1.5 2 2.5 3 3.5 49
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 30 / 32
Nonlinear equations in one variable Function Minimization
Conditions for optimum and algorithm
Necessary condition for an optimum:
Suppose ϕ∈C2 and denote f(x) = ϕ′(x). Then a zero of f is a critical
point of ϕ, i.e., where
ϕ′(x∗) = 0.
To be a minimizer or a maximizer, it is necessary for x∗ to be a critical point.
Su cient condition for an optimum:
A critical point x∗ is a minimizer if also ϕ′′(x∗) > 0.
Hence, an algorithm for nding a minimizer is obtained by using one of the
methods of this chapter for nding the roots of ϕ′(x), then checking for each
such root x∗ if also ϕ′′(x∗) > 0.
Note: rather than nding all roots of ϕ′ rst and checking for minimum
condition later, can do things more carefully and wisely, e.g. by sticking to
steps that decrease ϕ(x).
Uri Ascher & Chen Greif (UBC Computer Science) A First Course in Numerical Methods September 2, 2014 31 / 32
Nonlinear equations in one variable Function Minimization
Example
To nd a minimizer for
ϕ(x) = 10cosh(x/4)−x,
.1 Calculate gradient
f(x) = ϕ′(x) = 2.5sinh(x/4)−1
.2 Find root of ϕ′(x) = 0 using any of our methods, obtaining
x∗≈1.56014.
.3 Second derivative
ϕ′′(x) = 2.5/4cosh(x/4) > 0 for all x,
so x∗ is a minimizer.