Capstone 1: a formatted convergence report

A solver that prints one line per result answers the question "what is the root" and says nothing about how it got there. The report is the other half of a numerical program: a table of the steps with the value and the residual at each, a second table that compares the methods, and a header whose columns line up with the data because both use the same field widths. This lesson closes the first capstone with the report over the solver of the two previous lessons.

The history in the result

The result type grows three arrays and a counter: the value, the residual and a width measure for each step, up to sixty-four of them. A fixed-size array keeps the type simple and the assignment cheap, and sixty-four is more than either method needs here; a method that runs longer stops recording and still returns its answer, which is why the recording is guarded by the counter.

type :: result_t real(dp) :: x = 0.0_dp real(dp) :: residual = 0.0_dp integer :: steps = 0 logical :: converged = .false. integer :: n_hist = 0 real(dp) :: hist_x(64) = 0.0_dp real(dp) :: hist_f(64) = 0.0_dp real(dp) :: hist_w(64) = 0.0_dp end type result_t

Bisection records the midpoint, its residual and the width of the bracket before it was halved; Newton records the current guess, its residual and, in the third array, the size of the residual it is about to use as its convergence measure. The two methods share the arrays and mean slightly different things by the third one, which the report labels per method.

The convergence table

Twenty-eight lines of bisection is more than a page needs, so the program prints every fourth step and the last one, with a rule in the header that says which columns are which. The file is the module of lesson 127 with the three arrays added and this program at the end:

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. integer :: n_hist = 0 real(dp) :: hist_x(64) = 0.0_dp real(dp) :: hist_f(64) = 0.0_dp real(dp) :: hist_w(64) = 0.0_dp 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 (res%n_hist < 64) then res%n_hist = res%n_hist + 1 res%hist_x(res%n_hist) = mid res%hist_f(res%n_hist) = eval(eq, mid) res%hist_w(res%n_hist) = hi - lo end if 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 if (res%n_hist < 64) then res%n_hist = res%n_hist + 1 res%hist_x(res%n_hist) = x res%hist_f(res%n_hist) = eval(eq, x) res%hist_w(res%n_hist) = abs(eval(eq, x)) end if 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 report_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 print '(a)', 'convergence of bisection on x**3 - 2x - 5' print '(a)', ' step x f(x) width' call bisect(eqs(1), res) do i = 1, res%n_hist if (mod(i, 4) == 1 .or. i == res%n_hist) then print '(i5,2x,f14.10,2x,es12.4,2x,es10.3)', i, res%hist_x(i), res%hist_f(i), res%hist_w(i) end if end do print * print '(a)', 'convergence of newton on x**3 - 2x - 5' print '(a)', ' step x f(x)' call newton(eqs(1), res) do i = 1, res%n_hist print '(i5,2x,f14.10,2x,es12.4)', i, res%hist_x(i), res%hist_f(i) end do print * print '(a)', 'summary' print '(a)', 'equation method root residual steps ok' do i = 1, size(eqs) call bisect(eqs(i), res) print '(a18,2x,a9,2x,f12.8,2x,es11.4,2x,i5,2x,l1)', trim(eqs(i)%name), 'bisection', res%x, res%residual, & res%steps, res%converged call newton(eqs(i), res) print '(a18,2x,a9,2x,f12.8,2x,es11.4,2x,i5,2x,l1)', trim(eqs(i)%name), 'newton', res%x, res%residual, & res%steps, res%converged end do end program report_demo

gfortran -Wall -Wextra -std=f2018 report.f90 -o report
./report

convergence of bisection on x**3 - 2x - 5
 step         x                f(x)         width
   1    2.5000000000    5.6250E+00   1.000E+00
   5    2.0937500000   -8.9417E-03   6.250E-02
   9    2.0957031250    1.2862E-02   3.906E-03
  13    2.0946044922    5.9169E-04   2.441E-04
  17    2.0945510864   -4.4101E-06   1.526E-05
  21    2.0945515633    9.1212E-07   9.537E-07
  25    2.0945514739   -8.5791E-08   5.960E-08
  28    2.0945514850    3.8948E-08   7.451E-09

The width column is the story of bisection in one line per four steps: it falls by a factor of sixteen every four rows, which is the halving of the bracket, and the residual does not fall steadily because the midpoint is not the root, only a point nearer to it. The last width is 7.451E-09, below the 1.0e-8 tolerance, and the loop stopped after recording that step.

Newton beside it, and the summary table

Newton records the guess it is about to improve, so its three rows are the three guesses and the third is already the answer to eight digits:

convergence of newton on x**3 - 2x - 5
 step         x                f(x)
   1    2.0000000000   -1.0000E+00
   2    2.1000000000    6.1000E-02
   3    2.0945681211    1.8572E-04

The summary is the table a reader keeps: one line per equation and method, with the root, the residual at it, the number of steps and the convergence flag.

summary
equation           method        root          residual   steps  ok
     x**3 - 2x - 5  bisection    2.09455149   3.8948E-08     28  T
     x**3 - 2x - 5     newton    2.09455148   1.7407E-09      3  T
    exp(-x) - 0.5  bisection    0.69314718   9.1032E-10     28  T
    exp(-x) - 0.5     newton    0.69314717   5.8042E-09      4  T

Eight decimals of the root, four significant digits of the residual, two columns of integers and one logical. The residual is the column that tells a reader how much to trust the root: 3.9e-08 for bisection against the 1.0e-8 it asked for, and 1.7e-09 for Newton, which stopped on the residual and not on the step.

Why the columns line up

Alignment is not a property of the table, it is a property of the format strings. The header is printed with the literal text that has the same widths as the data: (a18,2x,a9,2x,f12.8,2x,es11.4,2x,i5,2x,l1) for the rows and (a) with a hand-written header line for the title. That is why the header above is one character constant with the spaces counted rather than a row of separate labels: a header built from A descriptors of the right widths would be the same thing with more machinery.

Two choices are worth copying. A real that may be large or small is printed with ES, which always gives one digit before the point and an exponent, so 5.6250E+00 and 3.8948E-08 occupy the same width. A count that never exceeds a hundred is printed with I5 and right-aligned, which is what makes the steps column readable. And the logical is L1, which prints a single T or F and needs no legend.

A format that does not match its items is a run-time error, as lesson 097 showed, and the error names the item and the descriptor. The safe habit is to count the items against the descriptors before running the program, and to keep a header next to the format string in the source so that the next change to one is a change to the other.

Rules for a report

Record the history in the result and format it at the edge, not inside the method: a solver that prints cannot be tested, and a result type that carries the steps can be printed by any program. Print the residual beside the root, because the root alone does not say how accurate it is. Use the same widths in the header and the data, and state the units and the method in the header rather than in a footnote. And make the table complete enough that a reader can reproduce the run: the equation, the method, the tolerance and the number of steps are four columns that cost nothing.

The capstone is finished: a model, two methods and a report, in four hundred lines including the comments, with every program on the pages of this part built and run. The next capstone is a matrix library, which replaces the scalar equation with a type that holds storage and the methods of lesson 127 with operations on it.

Exercises

  1. Print every step of the bisection instead of every fourth. How many lines does the section become, and why is the width column the one worth keeping?
  2. Add a column for the derivative that Newton used. Which array does it need, and where is it filled?
  3. Change the root column to F10.6 and the residual to F10.3E3. Which rows become unreadable, and why?
  4. Print the summary in the order of the equations but with bisection and Newton on one line each. Which columns have to change width?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why does the result type carry the history?

    Answer

    A solver that prints cannot be tested, and a caller can format the steps

    Format at the edge, not in the method.

  2. How fast does the width column fall in the bisection table?

    Answer

    By a factor of sixteen every four rows

    The bracket halves at each step.

  3. Why is the residual not monotone in the bisection table?

    Answer

    The midpoint is not the root, only a point nearer to it

    The bracket narrows; the midpoint wanders.

  4. What descriptor prints 5.6250E+00 and 3.8948E-08 in the same width?

    Answer

    ES

    A scientific descriptor with one digit before the point.

  5. What does L1 print?

    Answer

    A single T or F

    The ok column needs no legend.

  6. How is the header aligned with the data?

    Answer

    The header text has the same widths as the format string

    Alignment is a property of the widths.

  7. Why print the residual beside the root?

    Answer

    The root alone does not say how accurate it is

    It is the measure the method stopped on.

  8. What happened to Newton&#39;s third guess in the history?

    Answer

    It is the answer to eight digits

    2.0945681211 against 2.09455148 after the update.

  9. What happens when a format has fewer descriptors than items?

    Answer

    The format reverts and the extra items go on a new record

    Lesson 050 on format reversion.

  10. What does the summary table need to be reproducible?

    Answer

    The equation, the method, the tolerance and the steps

    Four columns that cost nothing.

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