190
7 Solving Nonlinear Algebraic Equations
print(’Number of function calls: {:d}’.format(2+no_iterations))
print(’A solution is: {:f}’.format(solution))
else:
print(’Solution not found!’)
The number of function calls is now related to no_iterations, i.e., the
number of iterations, as 2 + no_iterations, since we need two function calls
before entering the while loop, and then one function call per loop iteration.
Note that, even though we need two points on the graph to compute each
updated estimate, only a single function call (f(x1)) is required in each iteration since f(x0) becomes the “old” f(x1) and may simply be copied as
f_x0 = f_x1 (the exception is the very first iteration where two function evaluations are needed).
Running secant_method.py, gives the following printout on the screen:
Number of function calls: 19
A solution is: 3.000000
7.4 The Bisection Method
Neither Newton’s method nor the secant method can guarantee that an existing
solution will be found (see Exercises 7.1 and 7.2). The bisection method, however,
does that. However, if there are several solutions present, it finds only one of them,
just as Newton’s method and the secant method. The bisection method is slower
than the other two methods, so reliability comes with a cost of speed (but, again, for
a single equation that is rarely an issue with laptops of today).
To solve x 2 − 9 = 0, x ∈ [0, 1000], with the bisection method, we reason as
follows. The first key idea is that if f (x) = x 2 − 9 is continuous on the interval and
the function values for the interval endpoints (x L = 0, x R = 1000) have opposite
signs, f (x) must cross the x axis at least once on the interval. That is, we know
there is at least one solution.
The second key idea comes from dividing the interval in two equal parts, one
to the left and one to the right of the midpoint x M = 500. By evaluating the sign
of f (x M ), we will immediately know whether a solution must exist to the left or
right of x M . This is so, since if f (x M ) ≥ 0, we know that f (x) has to cross the x
axis between x L and x M at least once (using the same argument as for the original
interval). Likewise, if instead f (x M ) ≤ 0, we know that f (x) has to cross the x axis
between x M and x R at least once.
In any case, we may proceed with half the interval only. The exception is if
f (x M ) ≈ 0, in which case a solution is found. Such interval halving can be
continued until a solution is found. A “solution” in this case, is when |f (x M )| is
sufficiently close to zero, more precisely (as before): |f (x M )| < <, where is a
small number specified by the user.
7 Solving Nonlinear Algebraic Equations
print(’Number of function calls: {:d}’.format(2+no_iterations))
print(’A solution is: {:f}’.format(solution))
else:
print(’Solution not found!’)
The number of function calls is now related to no_iterations, i.e., the
number of iterations, as 2 + no_iterations, since we need two function calls
before entering the while loop, and then one function call per loop iteration.
Note that, even though we need two points on the graph to compute each
updated estimate, only a single function call (f(x1)) is required in each iteration since f(x0) becomes the “old” f(x1) and may simply be copied as
f_x0 = f_x1 (the exception is the very first iteration where two function evaluations are needed).
Running secant_method.py, gives the following printout on the screen:
Number of function calls: 19
A solution is: 3.000000
7.4 The Bisection Method
Neither Newton’s method nor the secant method can guarantee that an existing
solution will be found (see Exercises 7.1 and 7.2). The bisection method, however,
does that. However, if there are several solutions present, it finds only one of them,
just as Newton’s method and the secant method. The bisection method is slower
than the other two methods, so reliability comes with a cost of speed (but, again, for
a single equation that is rarely an issue with laptops of today).
To solve x 2 − 9 = 0, x ∈ [0, 1000], with the bisection method, we reason as
follows. The first key idea is that if f (x) = x 2 − 9 is continuous on the interval and
the function values for the interval endpoints (x L = 0, x R = 1000) have opposite
signs, f (x) must cross the x axis at least once on the interval. That is, we know
there is at least one solution.
The second key idea comes from dividing the interval in two equal parts, one
to the left and one to the right of the midpoint x M = 500. By evaluating the sign
of f (x M ), we will immediately know whether a solution must exist to the left or
right of x M . This is so, since if f (x M ) ≥ 0, we know that f (x) has to cross the x
axis between x L and x M at least once (using the same argument as for the original
interval). Likewise, if instead f (x M ) ≤ 0, we know that f (x) has to cross the x axis
between x M and x R at least once.
In any case, we may proceed with half the interval only. The exception is if
f (x M ) ≈ 0, in which case a solution is found. Such interval halving can be
continued until a solution is found. A “solution” in this case, is when |f (x M )| is
sufficiently close to zero, more precisely (as before): |f (x M )| < <, where is a
small number specified by the user.