7.5 Rate of Convergence
193
A single q in (7.5) is defined in the limit n → ∞. For finite n, and especially
smaller n, q will vary with n. To estimate q, we can compute all the errors e n and
set up (7.5) for three consecutive experiments n − 1, n, and n + 1:
e n = Ce
q
n−1 ,
e n+1 = Ce
q
n .
Dividing, e.g., the latter equation by the former, and solving with respect to q, we
get that
q =
ln(e n+1 /e n )
ln(e n /e n−1 )
.
Since this q will vary somewhat with n, we call it q n . As n grows, we expect q n to
approach a limit (q n → q).
Modifying Our Functions to Return All Approximations To compute all the q n
values, we need all the x n approximations. However, our previous implementations
of Newton’s method, the secant method, and the bisection method returned just the
final approximation.
Therefore, we have modified our solvers 5 accordingly, and placed them in
nonlinear_solvers.py. A user can choose whether the final value or the whole
history of solutions is to be returned. Each of the extended implementations now
takes an extra parameter return_x_list. This parameter is a boolean, set to True
if the function is supposed to return all the root approximations, or False, if the
function should only return the final approximation.
As an example, let us take a closer look at Newton:
def Newton(f, dfdx, x, eps, return_x_list=False):
f_value = f(x)
iteration_counter = 0
if return_x_list:
x_list = []
while abs(f_value) > eps and iteration_counter < 100:
try:
x = x - float(f_value)/dfdx(x)
except ZeroDivisionError:
print(’Error! - derivative zero for x = {:g}’.format(x))
sys.exit(1)
# Abort with error
f_value = f(x)
iteration_counter += 1
if return_x_list:
x_list.append(x)
# Here, either a solution is found, or too many iterations
if abs(f_value) > eps:
iteration_counter = -1 # i.e., lack of convergence
5 An implemented numerical solution algorithm is often called a solver.
193
A single q in (7.5) is defined in the limit n → ∞. For finite n, and especially
smaller n, q will vary with n. To estimate q, we can compute all the errors e n and
set up (7.5) for three consecutive experiments n − 1, n, and n + 1:
e n = Ce
q
n−1 ,
e n+1 = Ce
q
n .
Dividing, e.g., the latter equation by the former, and solving with respect to q, we
get that
q =
ln(e n+1 /e n )
ln(e n /e n−1 )
.
Since this q will vary somewhat with n, we call it q n . As n grows, we expect q n to
approach a limit (q n → q).
Modifying Our Functions to Return All Approximations To compute all the q n
values, we need all the x n approximations. However, our previous implementations
of Newton’s method, the secant method, and the bisection method returned just the
final approximation.
Therefore, we have modified our solvers 5 accordingly, and placed them in
nonlinear_solvers.py. A user can choose whether the final value or the whole
history of solutions is to be returned. Each of the extended implementations now
takes an extra parameter return_x_list. This parameter is a boolean, set to True
if the function is supposed to return all the root approximations, or False, if the
function should only return the final approximation.
As an example, let us take a closer look at Newton:
def Newton(f, dfdx, x, eps, return_x_list=False):
f_value = f(x)
iteration_counter = 0
if return_x_list:
x_list = []
while abs(f_value) > eps and iteration_counter < 100:
try:
x = x - float(f_value)/dfdx(x)
except ZeroDivisionError:
print(’Error! - derivative zero for x = {:g}’.format(x))
sys.exit(1)
# Abort with error
f_value = f(x)
iteration_counter += 1
if return_x_list:
x_list.append(x)
# Here, either a solution is found, or too many iterations
if abs(f_value) > eps:
iteration_counter = -1 # i.e., lack of convergence
5 An implemented numerical solution algorithm is often called a solver.