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

  1. 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?
  2. Start Newton at x = 3 instead of x = 2 by setting eqs(1)%a. Does it still converge, and in how many steps?
  3. 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?
  4. 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.

  1. 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.

  2. What does the result type carry?

    Answer

    The root, the residual, the number of steps and a flag

    A caller can judge the answer.

  3. What is res = result_t()?

    Answer

    A structure constructor with every component defaulted

    The shortest way to say "empty".

  4. Which step does the central difference use?

    Answer

    sqrt(epsilon) times max(1, abs(x))

    It balances truncation against rounding.

  5. How many steps did Newton take on the cubic?

    Answer

    3

    The run is on this page.

  6. Why does the two methods&#39; last digit differ?

    Answer

    They stop on different measures: interval width and residual

    Both are converged, by different tests.

  7. 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.

  8. 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.

  9. 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.

  10. 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