Root finding: bisection and Newton
Two methods find the same root with the same code and differ by a factor of seven in the number of steps. Bisection only needs a bracket in which the function changes sign, and it gains one binary digit per step. Newton needs the derivative and converges so fast that three steps beat twenty-one. This lesson writes both for the same cubic, prints the iterations each one needs for four tolerances, and measures the difference.
Bisection
The method keeps an interval [lo, hi] in which the function changes sign, evaluates the middle, and replaces the half that has the same sign as the middle. The root is in the remaining half, the interval halves every step, and after k steps its width is the starting width divided by 2^k. Nothing about the function needs to be smooth, only continuous and of two signs at the ends.
The file roots.f90:
module roots
implicit none
private
public :: f, df, bisection, newton
contains
pure function f(x) result(y)
real, intent(in) :: x
real :: y
y = x ** 3 - 2.0 * x - 5.0
end function f
pure function df(x) result(y)
real, intent(in) :: x
real :: y
y = 3.0 * x * x - 2.0
end function df
function bisection(a, b, tol, maxit, iters) result(r)
real, intent(in) :: a, b, tol
integer, intent(in) :: maxit
integer, intent(out) :: iters
real :: r, lo, hi, mid
lo = a
hi = b
iters = 0
do while (hi - lo > tol .and. iters < maxit)
mid = 0.5 * (lo + hi)
if (f(lo) * f(mid) <= 0.0) then
hi = mid
else
lo = mid
end if
iters = iters + 1
end do
r = 0.5 * (lo + hi)
end function bisection
function newton(x0, tol, maxit, iters) result(r)
real, intent(in) :: x0, tol
integer, intent(in) :: maxit
integer, intent(out) :: iters
real :: r
r = x0
iters = 0
do while (abs(f(r)) > tol .and. iters < maxit)
r = r - f(r) / df(r)
iters = iters + 1
end do
end function newton
end module roots
program rootdemo
use roots
implicit none
integer :: it, k, ib, in
real :: r, tol, tols(4)
r = bisection(1.0, 3.0, 1.0e-6, 100, it)
print '(a,f10.7,a,i0)', 'bisection: root = ', r, ' iterations = ', it
print '(a,es12.4)', 'residual = ', abs(f(r))
r = newton(2.0, 1.0e-6, 100, it)
print '(a,f10.7,a,i0)', 'newton: root = ', r, ' iterations = ', it
print '(a,es12.4)', 'residual = ', abs(f(r))
tols = [1.0e-1, 1.0e-2, 1.0e-4, 1.0e-6]
print '(a)', ' tol bisection newton'
do k = 1, size(tols)
tol = tols(k)
r = bisection(1.0, 3.0, tol, 100, ib)
r = newton(2.0, tol, 100, in)
print '(es9.1,i10,i9)', tol, ib, in
end do
end program rootdemo
gfortran -Wall -Wextra -std=f2018 roots.f90 -o roots
./roots
bisection: root = 2.0945516 iterations = 21
residual = 9.5367E-07
newton: root = 2.0945516 iterations = 3
residual = 9.5367E-07
tol bisection newton
1.0E-01 5 1
1.0E-02 8 2
1.0E-04 15 3
1.0E-06 21 3
Newton's method
Newton follows the tangent line: from the current point it steps to where the tangent crosses zero, r - f(r)/f'(r). Near a simple root the step is squared in the error, so the number of correct digits doubles with every iteration, which is why three steps reach the same residual that bisection reaches in twenty-one.
The price is the derivative. It is written by hand here, and the module makes it one more function of the same shape. A production program rarely differentiates by hand: it takes a finite difference, which is one more function evaluation per step and a loss of the quadratic rate near the roundoff floor, or it uses a secant method that skips the derivative entirely. Both are the same loop with a different expression for the step.
The measured table
The table is the interesting part of the page, because the two columns are the two orders in numbers. Bisection needs 5, 8, 15 and 21 iterations for tolerances 1e-1 down to 1e-6; each extra decimal digit costs about 3.3 steps, which is log2(10), the number of bisections that divide an interval by ten. Newton needs 1, 2, 3 and 3: the count grows by one per digit at first and then stops growing, because at 1e-6 it has already reached the accuracy a single-precision real can hold near 2.1.
Both residuals are 9.5e-07, which is just under the 1e-6 demanded. That is the tolerance test written on the residual, abs(f(r)) > tol, not on the step or on the error in x: a program that wants a bound on the error in the root has to divide the residual by the derivative, or test the step as well.
Reading the columns
A linear method costs one iteration per binary digit of accuracy, which for a tolerance range of five decimal digits is seventeen steps. A quadratic method costs one iteration per doubling of the digits, so the same range is about five. For a single function call the difference does not matter; for a root that is found inside another loop, or for a problem with a thousand roots, it is the whole cost of the program.
The same counting argument explains why a hybrid is the usual production choice: bisection to get into the neighbourhood of a root, where it cannot fail, then Newton or the secant method to finish it in three steps. The numerical libraries are full of that arrangement, and the two halves are the two functions of this lesson.
Where each method fails
Bisection fails when the bracket does not contain a sign change, which is a user error, and when the function has a pole inside the bracket, where it changes sign without a root. It never diverges, and its worst case is a slow answer. Newton fails in three ways that matter: a starting point where the derivative is zero divides by zero, a starting point far from the root can diverge or cycle, and a function with several roots converges to whichever one is nearest in the sense of its basins, which nobody can see from the code.
A program that uses Newton and nothing else should check what it got: a residual that is small, a step that is small, and an iteration count below the maximum. The maxit argument of both functions is the guard that keeps a divergent run from looping for ever, and the program above passes a hundred.
A value instead of a procedure
A function passed as an argument is named without its parentheses; with them it is the value of a call, and the compiler says what it expected:
module roots
implicit none
abstract interface
pure function fun_iface(x) result(y)
real, intent(in) :: x
real :: y
end function fun_iface
end interface
type :: bracket
real :: lo = 0.0
real :: hi = 1.0
end type bracket
contains
pure function f(x) result(y)
real, intent(in) :: x
real :: y
y = x ** 3 - 2.0 * x - 5.0
end function f
function midpoint_of(fn, b) result(r)
procedure(fun_iface) :: fn
type(bracket), intent(in) :: b
real :: r
r = 0.5 * (b%lo + b%hi)
if (fn(r) > 0.0) r = r
end function midpoint_of
end module roots
program badproc
use roots
implicit none
type(bracket) :: b
b = bracket(1.0, 3.0)
print *, midpoint_of(f(1.0), b)
end program badproc
gfortran -Wall -Wextra -std=f2018 badproc.f90 -o badproc
badproc.f90:39:23:
39 | print *, midpoint_of(f(1.0), b)
| 1
Error: Expected a procedure for argument 'fn' at (1)
The fix is midpoint_of(f, b). The error is short because the interface is explicit: a dummy procedure of a module has one, and the compiler compares the actual argument with it rather than guessing.
Rules for a root finder
Bracket when the function allows it, and solve inside the bracket. Test the residual and the step, not only the iteration count. Keep the derivative next to the function in the same module, so that a change to one is visible when the other is edited. And print the iteration count with the answer: a run that needed the maximum is a run that did not converge, whatever the root looks like.
The capstone of part 14 builds exactly this as a module with a report, and the two functions of this lesson are its methods. Nothing in it is special to Fortran except the module boundary, which is what keeps the function and its derivative together.
Exercises
- Change the starting point of Newton from 2.0 to 0.0. What happens, and why is the derivative the problem?
- Use x*x - 2.0 as the function and find the square root of two. How many bisections does 1e-6 need from the bracket [1, 2]?
- Replace the residual test of Newton with a test on the step. Does the iteration count change for this function?
- Run bisection with a bracket that does not change sign, [3, 4], and print the iteration count. What did the function return, and why is the count the maximum?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does bisection need to start?
Answer
A bracket in which the function changes sign
The sign change is the only condition.
-
Why does bisection need about 3.3 steps per decimal digit?
Answer
It gains one binary digit per step and ten is 2 to the 3.3
The table shows 5 to 21 for five digits.
-
What does this program print?
program p implicit none real :: lo, hi, mid integer :: i lo = 0.0 hi = 1.0 do i = 1, 3 mid = 0.5 * (lo + hi) hi = mid end do print *, hi end program pAnswer
0.125
The interval is halved three times: an eighth.
-
What is the Newton step?
Answer
r - f(r) / f'(r)
It follows the tangent to zero.
-
Why does the Newton column stop growing at 1e-6?
Answer
It has reached the accuracy a single-precision real can hold near the root
The same reason the Simpson column flattened in lesson 093.
-
What happens when Newton starts where the derivative is zero?
Answer
The step divides by zero and the run is not a root at all
The tangent is horizontal and never crosses zero.
-
What is the usually best production arrangement?
Answer
Bisection for safety, then Newton or secant to finish
Safeguarded methods are what the libraries implement.
-
Why print the iteration count with the root?
Answer
A run that used the maximum did not converge
The count is the convergence check.
-
What does gfortran report for
midpoint_of(f(1.0), b)?Answer
Error: expected a procedure for argument
The parentheses call the function instead of naming it.
-
Which method can never diverge?
Answer
Bisection, given a valid bracket
The interval shrinks whatever the function does.
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