Capstone 1: bisection and Newton in a module
The model of the previous lesson gives a method an equation and a tolerance. This lesson adds the two methods that fit it: bisection, which halves a bracket until it is narrower than the tolerance and cannot fail when the bracket is right, and Newton, which follows the tangent and reaches the same root in a tenth of the steps when the start is close. Both return the same derived type, so the report of the next lesson is a loop over a table.
The result type
A method that returns a single real throws away everything a caller needs to judge the answer: how many steps it took, how large the residual is, whether it stopped because it converged or because it ran out of steps. The type below carries all four, with defaults that say "nothing happened" so an early return is still a valid value.
type :: result_t
real(dp) :: x = 0.0_dp
real(dp) :: residual = 0.0_dp
integer :: steps = 0
logical :: converged = .false.
end type result_t
RES = RESULT_T() at the start of each method is a structure constructor with every component defaulted, which is the shortest way to say "empty". The residual is f(x) at the answer, not x minus the true root, because the true root is what the program does not know.
Bisection
Bisection keeps an interval whose ends have opposite signs, evaluates the midpoint, and replaces the end that has the same sign as the midpoint. The width halves at every step, so about log2((b-a)/tol) steps are enough: a bracket of width one and a tolerance of 1.0e-8 need twenty-seven, and the run below takes twenty-eight because the loop tests before it halves.
The sign test is written with two comparisons and .EQV. rather than with sign(f(lo)) /= sign(f(mid)), because gfortran warns about /= on reals under -Wall (lesson 090) and the warning is right: two values that differ in the last bit are not the same question as two values with different signs.
Newton with a numerical derivative
Newton needs the derivative, and the equation type does not carry one. The method takes a central difference instead: (f(x+h) - f(x-h)) / 2h with h = sqrt(epsilon) * max(1, |x|), which is the step that balances the truncation error of the formula against the rounding error of the subtraction. Two extra evaluations per step buy a method that needs no derivative component and converges quadratically.
The convergence test is on the residual, abs(f(x)) <= tol, not on the step, so a method that wanders does not report success because two successive guesses happened to be close. A derivative of zero stops the method with the result as it stands, which is the honest answer: the tangent is flat and there is no next point.
Both methods on both equations
The file methods.f90 holds the module of lesson 126 with the result type and the two methods added, and a program that builds a table of two equations and runs both methods on each:
module solver_model
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
private
public :: equation, result_t, eval, bracket_ok, bisect, newton, cubic, decay
abstract interface
pure function func(x) result(y)
import :: dp
real(dp), intent(in) :: x
real(dp) :: y
end function func
end interface
type :: equation
character(len=32) :: name = ''
procedure(func), pointer, nopass :: f => null()
real(dp) :: a = 0.0_dp
real(dp) :: b = 0.0_dp
real(dp) :: tol = 1.0e-8_dp
end type equation
type :: result_t
real(dp) :: x = 0.0_dp
real(dp) :: residual = 0.0_dp
integer :: steps = 0
logical :: converged = .false.
end type result_t
contains
pure function eval(eq, x) result(y)
type(equation), intent(in) :: eq
real(dp), intent(in) :: x
real(dp) :: y
y = eq%f(x)
end function eval
function bracket_ok(eq) result(ok)
type(equation), intent(in) :: eq
logical :: ok
ok = (eval(eq, eq%a) > 0.0_dp) .neqv. (eval(eq, eq%b) > 0.0_dp)
end function bracket_ok
subroutine bisect(eq, res, max_steps)
type(equation), intent(in) :: eq
type(result_t), intent(out) :: res
integer, intent(in), optional :: max_steps
integer :: limit
real(dp) :: lo, hi, mid
limit = 200
if (present(max_steps)) limit = max_steps
res = result_t()
if (.not. bracket_ok(eq)) return
lo = eq%a
hi = eq%b
do
res%steps = res%steps + 1
mid = 0.5_dp * (lo + hi)
if (abs(hi - lo) <= eq%tol .or. res%steps >= limit) exit
if ((eval(eq, lo) > 0.0_dp) .eqv. (eval(eq, mid) > 0.0_dp)) then
lo = mid
else
hi = mid
end if
end do
res%x = mid
res%residual = eval(eq, mid)
res%converged = abs(hi - lo) <= eq%tol
end subroutine bisect
subroutine newton(eq, res, max_steps)
type(equation), intent(in) :: eq
type(result_t), intent(out) :: res
integer, intent(in), optional :: max_steps
integer :: limit
real(dp) :: x, h, d
limit = 50
if (present(max_steps)) limit = max_steps
res = result_t()
x = eq%a
do
res%steps = res%steps + 1
h = sqrt(epsilon(1.0_dp)) * max(1.0_dp, abs(x))
d = (eval(eq, x + h) - eval(eq, x - h)) / (2.0_dp * h)
if (abs(d) <= tiny(1.0_dp)) return
x = x - eval(eq, x) / d
if (abs(eval(eq, x)) <= eq%tol .or. res%steps >= limit) exit
end do
res%x = x
res%residual = eval(eq, x)
res%converged = abs(res%residual) <= eq%tol
end subroutine newton
pure function cubic(x) result(y)
real(dp), intent(in) :: x
real(dp) :: y
y = x**3 - 2.0_dp * x - 5.0_dp
end function cubic
pure function decay(x) result(y)
real(dp), intent(in) :: x
real(dp) :: y
y = exp(-x) - 0.5_dp
end function decay
end module solver_model
program methods_demo
use solver_model
use, intrinsic :: iso_fortran_env, only: dp => real64
implicit none
type(equation) :: eqs(2)
type(result_t) :: res
integer :: i
eqs(1)%name = 'x**3 - 2x - 5'
eqs(1)%f => cubic
eqs(1)%a = 2.0_dp
eqs(1)%b = 3.0_dp
eqs(2)%name = 'exp(-x) - 0.5'
eqs(2)%f => decay
eqs(2)%a = 0.0_dp
eqs(2)%b = 1.0_dp
do i = 1, size(eqs)
call bisect(eqs(i), res)
print '(a,a,f12.8,a,i3,a,l1)', trim(eqs(i)%name), ' bisection x = ', res%x, ' steps = ', res%steps, &
' converged = ', res%converged
call newton(eqs(i), res)
print '(a,a,f12.8,a,i3,a,l1)', trim(eqs(i)%name), ' newton x = ', res%x, ' steps = ', res%steps, &
' converged = ', res%converged
end do
end program methods_demo
gfortran -Wall -Wextra -std=f2018 methods.f90 -o methods
./methods
x**3 - 2x - 5 bisection x = 2.09455149 steps = 28 converged = T
x**3 - 2x - 5 newton x = 2.09455148 steps = 3 converged = T
exp(-x) - 0.5 bisection x = 0.69314718 steps = 28 converged = T
exp(-x) - 0.5 newton x = 0.69314717 steps = 4 converged = T
What the numbers say
Both methods found the same roots, which are also the values a table gives: the real root of x**3 - 2x - 5 is 2.09455148... and the root of exp(-x) = 0.5 is ln 2 = 0.69314718.... Bisection needed twenty-eight evaluations of the bracket plus one per midpoint for the sign, Newton three or four steps of two evaluations each, which is the whole case for Newton in one line.
The last digit differs between the two methods, and it is not a bug: bisection stops on the width of the interval and Newton on the size of the residual, so the two answers are accurate to different measures. A report that prints eight decimals makes that visible; a report that prints three would hide it.
Newton is also the method that can fail. A start where the derivative is zero returns at once with converged = .false., a start on the other side of a minimum can jump past the root and diverge, and a function that is not smooth breaks the central difference. Bisection needs one bracket and nothing else, which is why a library uses it to find the bracket and Newton to polish the answer.
The report
The program above prints one line per result, which is enough to compare two methods and not enough to hand to a reader who wants the convergence of one run. The next lesson adds the history: an array of steps inside the result type, filled by each method, and a report that prints an aligned table with a header and a line per step.
Exercises
- Change the tolerance of the cubic to 1.0e-12 and run both methods. How many steps does each need, and which one stops improving?
- Start Newton at x = 3 instead of x = 2 by setting eqs(1)%a. Does it still converge, and in how many steps?
- Make the derivative exact for the cubic by adding a df component to the type and passing the true 3x**2 - 2. How many steps does Newton need now?
- Call bisect on an equation whose bracket does not change sign. What does the result contain, and which default value tells the caller that nothing was done?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does bisection need about 28 steps for a tolerance of 1e-8?
Answer
The width halves at every step, and log2(1/1e-8) is about 27
Twenty-seven halvings, plus the test before the last one.
-
What does the result type carry?
Answer
The root, the residual, the number of steps and a flag
A caller can judge the answer.
-
What is
res = result_t()?Answer
A structure constructor with every component defaulted
The shortest way to say "empty".
-
Which step does the central difference use?
Answer
sqrt(epsilon) times max(1, abs(x))
It balances truncation against rounding.
-
How many steps did Newton take on the cubic?
Answer
3
The run is on this page.
-
Why does the two methods' last digit differ?
Answer
They stop on different measures: interval width and residual
Both are converged, by different tests.
-
When does Newton fail here?
Answer
When the derivative is zero or the start is far from the root
A flat tangent has no next point.
-
Why is the sign test written with .EQV. and two comparisons?
Answer
A comparison of two reals with == or /= warns and is not the same question
Lesson 090 on comparing floating-point values.
-
What does
converged = .false.after a bisection call mean?Answer
The bracket did not change sign, or the step limit was reached
Every early return leaves the defaults.
-
What does the next lesson add?
Answer
A history of the steps and a formatted report
One line per result is not a report.
The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev