An elementary numerical problem is to find the root \(x_0\) of an equation

\[f(x_0) = 0.\]

The applications are manifold. For instance, if the function \(f\) is a derivative of another function \(f(x) = \frac{dg}{dx}\) then finding a root allows us to find extrema (maxima or mimima) or saddle points (depending on the values of the higher derivatives) of the function \(g\).

Trial-and-error root finding methods move along the function graph and, depending on current values, investigate new regions of the function. They continue until they either converge on an answer to a pre-set precision or fail (perhaps after a maximum number of steps). Trial-and-error search is a common technique for cases where analytic solutions are lacking or not practical.

We will study two algorithms: bisection and Newton-Raphson searching.

The Jupyter notebook 12-Root-finding.ipynb contains the lecture notes.1 The derivations of the bisection and the Newton-Raphson algorithms (PDF) can be found in the slides. Skeleton code for in-class problem exercises can be found in the notebook 12-Root-finding-students.ipynb.2

Additional resources:

  • Computational Modelling: Chapter 3.3
  • Computational Physics: Chapter 7

Footnotes

  1. Notebook will be posted after class; in the mean time look at the student notebook. ↩

  2. As usual, git pull the resources repository PHY432-resources to get a local copy of the notebook. Then copy the notebook and all other code into your work directory in order to complete the exercises. ↩