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

  1. Change the starting point of Newton from 2.0 to 0.0. What happens, and why is the derivative the problem?
  2. 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]?
  3. Replace the residual test of Newton with a test on the step. Does the iteration count change for this function?
  4. 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.

  1. What does bisection need to start?

    Answer

    A bracket in which the function changes sign

    The sign change is the only condition.

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

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

    Answer

    0.125

    The interval is halved three times: an eighth.

  4. What is the Newton step?

    Answer

    r - f(r) / f&#39;(r)

    It follows the tangent to zero.

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

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

  7. What is the usually best production arrangement?

    Answer

    Bisection for safety, then Newton or secant to finish

    Safeguarded methods are what the libraries implement.

  8. Why print the iteration count with the root?

    Answer

    A run that used the maximum did not converge

    The count is the convergence check.

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

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