200
7 Solving Nonlinear Algebraic Equations
a) Implement Halley’s method as a function Halley. Place the function in a module
that has a test block, and test the function by solving x 2 −9 = 0, using x 0 = 1000
as your initial guess.
b) Compared to Newton’s method, more computations per iteration are needed
with Halley’s method, but a convergence rate of 3 may be achieved close
to the root. You are now supposed to extend your module with a function
compute_rates_decimal, which computes the convergence rates achieved
with your implementation of Halley (for the given problem).
The implementation of compute_rates_decimal should involve the
decimal module (you search for the right documentation!), to better handle
very small errors that may enter the rate computations. For comparison, you
should also compute the rates without using the decimal module. Test and
compare with several parameter values.
Hint The logarithms in the rate calculation might require some extra consideration
when you use the decimal module.
Filename: Halleys_method.py.
Exercise 7.7: Fixed Point Iteration
A nonlinear algebraic equation f (x) = 0 may be solved in many different ways, and
we have met some of these in this chapter. Another, very useful, solution approach
is to first re-write the equation into x = φ(x) (this re-write is not unique), and then
formulate the iteration
x n+1 = φ(x n ), n = 0, 1, . . . ,
with some starting value x 0 . If φ(x) is continuous, and if φ(x n ) approaches α as x n
approaches α (i.e., we get α = φ(α) as n → ∞), the iteration is called a fixed point
iteration and α is referred to as a fixed point of the mapping x → φ(x). Clearly, if
a fixed point α is found, α will also be a solution to the original equation f (x) = 0.
In this exercise, we will briefly explore the fixed point iteration method by
solving
x
3
+ 2x = e
−x , x ∈ [−2, 2] .
For comparison, however, you will first be asked to solve the equation by
Newton’s method (which, in fact, can be seen as fixed point iteration 8 ).
a) Write a program that solves this equation by Newton’s method. Use x = 1
as your starting value. To better judge the printed answer found by Newton’s
method, let the code also plot the relevant function on the given interval.
b) The given equation may be rewritten as x =
e −x −x 3
2
. Extend your program with
a function fixed_point_iteration, which takes appropriate parameters, and
uses fixed point iteration to find and return a solution (if found), as well as the
number of iterations required. Use x = 1 as starting value.
8 Check out https://en.wikipedia.org/wiki/Fixed_point_iteration.
7 Solving Nonlinear Algebraic Equations
a) Implement Halley’s method as a function Halley. Place the function in a module
that has a test block, and test the function by solving x 2 −9 = 0, using x 0 = 1000
as your initial guess.
b) Compared to Newton’s method, more computations per iteration are needed
with Halley’s method, but a convergence rate of 3 may be achieved close
to the root. You are now supposed to extend your module with a function
compute_rates_decimal, which computes the convergence rates achieved
with your implementation of Halley (for the given problem).
The implementation of compute_rates_decimal should involve the
decimal module (you search for the right documentation!), to better handle
very small errors that may enter the rate computations. For comparison, you
should also compute the rates without using the decimal module. Test and
compare with several parameter values.
Hint The logarithms in the rate calculation might require some extra consideration
when you use the decimal module.
Filename: Halleys_method.py.
Exercise 7.7: Fixed Point Iteration
A nonlinear algebraic equation f (x) = 0 may be solved in many different ways, and
we have met some of these in this chapter. Another, very useful, solution approach
is to first re-write the equation into x = φ(x) (this re-write is not unique), and then
formulate the iteration
x n+1 = φ(x n ), n = 0, 1, . . . ,
with some starting value x 0 . If φ(x) is continuous, and if φ(x n ) approaches α as x n
approaches α (i.e., we get α = φ(α) as n → ∞), the iteration is called a fixed point
iteration and α is referred to as a fixed point of the mapping x → φ(x). Clearly, if
a fixed point α is found, α will also be a solution to the original equation f (x) = 0.
In this exercise, we will briefly explore the fixed point iteration method by
solving
x
3
+ 2x = e
−x , x ∈ [−2, 2] .
For comparison, however, you will first be asked to solve the equation by
Newton’s method (which, in fact, can be seen as fixed point iteration 8 ).
a) Write a program that solves this equation by Newton’s method. Use x = 1
as your starting value. To better judge the printed answer found by Newton’s
method, let the code also plot the relevant function on the given interval.
b) The given equation may be rewritten as x =
e −x −x 3
2
. Extend your program with
a function fixed_point_iteration, which takes appropriate parameters, and
uses fixed point iteration to find and return a solution (if found), as well as the
number of iterations required. Use x = 1 as starting value.
8 Check out https://en.wikipedia.org/wiki/Fixed_point_iteration.