Chemistry Reference
In-Depth Information
Figure 3.6
Convergence analysis for the bisection method and Newton's method calculations
described in the text.
long run get closer and closer to a solution. How do we know when to stop? In
a real application, we do not know the exact solution, so we cannot use
1
i
¼jx
i
xj
as our measure of how accurate our current estimate is. Instead,
we have to define a stopping criteria that depends only on the series of approxi-
mations we have calculated. A typical choice is to continue iterating until the
difference between successive iterates is smaller than some tolerance, that is,
jx
iþ
1
x
i
j
,
d
. If we chose
d
0.01 for the examples above, we would stop
after 6 iterations of the bisection method, concluding that
x
2.34375, or
after 3 iterations of Newton's method, concluding that
x
2.355628. If we
chose a smaller tolerance,
d
0.001, we would stop after 11 (4) iterations
of the bisection method (Newton's method) with the approximation that
x
2.3554688 (
x
2.3561942).
The examples above demonstrate several general properties of numerical
optimization that are extremely important to appreciate. They include:
1. The algorithms are iterative, so they do not provide an exact solution;
instead, they provide a series of approximations to the exact solution.
2. An initial estimate for the solution must be provided to use the algor-
ithms. The algorithms provide no guidance on how to choose this initial
estimate.
3. The number of iterations performed is controlled by a tolerance par-
ameter that estimates how close the current solution is to the exact
solution.
