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
- 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?
- Add a column for the derivative that Newton used. Which array does it need, and where is it filled?
- Change the root column to F10.6 and the residual to F10.3E3. Which rows become unreadable, and why?
- 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.
-
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.
-
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.
-
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.
-
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.
-
What does L1 print?
Answer
A single T or F
The ok column needs no legend.
-
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.
-
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.
-
What happened to Newton's third guess in the history?
Answer
It is the answer to eight digits
2.0945681211 against 2.09455148 after the update.
-
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.
-
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