248
CHAPTER
8.
LAGRANGE
MULTIPLIERS.
NEWTON'S
METHOD.
We assume, for simplicity,
that
the
function
f (x) is differentiable
and
that
f'
(x) is continuous
on
[a,
b].
Then,
there
exists a
constant
C > 0 such
that
If'(x)1
~
C,
V x E
[a,
b].
(8.24) .
From
the
Mean
Value Theorem, we know
that
for
any
two points
XM
and
XL
there
exists a
point
e E
(XL,
XR)
such
that
!'(e)·
Note
that
XL,
XR
E
[a,
b].
From
(8.24)
and
(8.25)
it
follows
that
b-a
xLI
=
C--.
2
n
(8.25)
Since f(XR)
and
f(XL) have different signs,
it
is easy
to
see
that
If(XR) -
f(XL)1
=
IJ(XR)
I + If(XL)I,
and
therefore
b-a
max(IJ(XL)
I,
If(XR)I)
~
If(XR) -
f(XL)1
~
C~.
Then,
for n large enough, max(lf(xL)I, If(XR)I) < toLapprox,
and
the
other
stopping
condition for
the
bisection
method
will
be
satisfied. .
We conclude
that,
for n large enough,
both
conditions required
to
declare
that
a solution for f (
x)
= 0 is found will
be
satisfied,
and
the
bisection
method
will converge.
Example: Use
the
bisection
method
on
the
interval
[-2,3]
to
find a zero
of
the
function
4 2 1
f(
x)
= x
-5x
+4---.
1 + e
x3
Answer: To
make
sure
that
f(
-2)
and
f(3) have different signs, we first
compute
f(
-2)
=
-0.9997
and
f(3) = 40. We use
the
bisection
method
on
the
interval
[-2,
3]
with
tol~nt
=
10-
6
and
toLapprox
=
10-
9
.
After
33
iterations,
the
solution -0.889642 is found.
Note
that
2.000028 E
[-2,3]
is
another
zero for f (
x)
. D
8.2.2
Newton's
Method
Newton's
method
is
the
most
commonly used
method
for solving nonlinear
equations.
While
the
one-dimensional version
of
Newton's
method
is
easy
to
explain,
its
convergence properties (or lack thereof)
are
somewhat subtle.
Unlike
the
bisection
method,
Newton's
method
can
easily
be
extended
to
N-dimensional
problems; see section 8.3.1 for
more
details.
8.2.
NUMERICAL
METHODS
FOR
l-D
NONLINEAR
PROBLEMS
249
One
way
to
derive
the
recursion formula for
Newton's
method
for
one-
dimensional problems is as follows:
Let
Xk
be
the
approximation
of
the
exact
solution
x*
of
f (x) = 0
computed
after
k iterations.
The
next
approximation
point
Xk+l
is
the
x-intercept of
the
tangent
line
to
the
graph
of
f (
x)
at
the
point
(x
k,
f ( X
k)
) .
Mathematically,
this
is equivalent
4
to
the
following recursion formula:
f(Xk)
x
k+
1 = X k -
f'
( X k)' V k 2
O.
(8.27)
A
more
insightful way of deriving (8.27), which
can
easily
be
extended
to
N-dimensional problems, is
to
use
the
Taylor
expansion
of
the
function f(x)
around
the
point
Xk.
From
(5.11) for a =
Xb
we find
that
(8.28)
Let
x =
Xk+l
in
(8.28).
Then,
f(Xk+l)
~
f(Xk) +
(Xk+l
- Xk)!'(Xk).
(8.29)
By
approximating
f(Xk+l)
by
0 (which is
supposed
to
happen
in
the
limit, if
Xk+l
converges
to
a solution for f(x) = 0),
and
replacing
the
approximation
sign by
an
equality
sign
in
(8.29), we find
that
(8.30)
The
recursion formula (8.27) is
obtained
by
solving for
Xk+l
in
(8.30).
Unlike
the
bisection
method,
Newton's
method
does
not
necessarily con-
verge for
any
function
f(x)
and
any
initial guess
Xo.
To
obtain
convergence
in
Newton's
method,
and,
in
particular,
to
obtain
fast
convergence, a good
choice of
the
initial
approximation
Xo
is
important.
In
general, for financial applications, we have a good
idea
about
what
the
relevant zeros
of
the
nonlinear function f
(x)
are. For example,
the
yield
of
a
bond
is positive, usually small,
and
expressed
in
percentage
points. Therefore,
Xo
= 0.1, corresponding
to
an
yield
of
ten
percent, is usually a good initial
approximation
for problems requiring
to
find
the
yield
of
a bond.
On
the
other
hand,
Xo
=
-10
may
not
result
in
a convergent Newton's
method
for
such problems. Similarly, when
computing
implied volatility, a good initial
tangent
line
to
the
graph
of
f(x)
passing
through
the
point
(Xk,
f(Xk))
is
(8.26)
The
x-intercept
of
this line is found by
setting
y = 0 in (8.26)
and
solving for x.
The
solution,
denoted
by
xkH,
is given by (8.27).