MAT1001 Differential Calculus: Lecture Notes
Chapter 6 Numerical Methods
6.1 Solving equations numerically
It frequently happens that when confronted with a problem you end up with a mathematical problem or expression that cannot be evaluated analytically. This may be a differential equation that we cannot solve, an integral that has no closed form solution, or even an
algebraic equation which does not yield an explicit solution. This is where we have to turn to computer packages or follow a numerical method. Nowadays many computer programs can implement these approaches as standard. However, it is a good idea to understand
how to implement a few of these approaches by hand as you may end up writing one of your own at some stage.
Chapter 27 of [Riley et al., 2006] contains a lot of information about this topic and is a good place to go for more details than we will discuss here.
Before moving on to numerical differentiation and integration we will first discuss how to solve algebraic equations numerically. This is all about finding the real roots of an equation \(f(x)=0\). This equation can either be algebraic, with \(f(x)\) being a polynomial, or
transcendental, if \(f(x)\) includes trig, log, or exponential terms. We will be using iterative schemes to solve the equations, where we make successive approximations to the true solution, which converge to the true solution. For a method to be successful we need both
that the approximations converge to the true solution, and also that we only have a finite number of solutions.
It is important to note that different iteration methods will be better at solving certain kinds of problems, in practice some combination of methods is likely to be used. We will see four methods, Rearrangement, Linear interpolation, and Bisection, before discussing Newton’s method, which is the most important method to know in this module.
Rearrangement
To explain what we mean by an iterative scheme it is useful to consider the first example method, recasting our equation \(f(x)=0\) as
\(\seteqnumber{0}{6.}{0}\)\begin{equation*} x=\phi (x), \end{equation*}
for some slowly varying function \(\phi (x)\). Our iteration scheme starts from a guess, \(x_{0}\) which will not solve \(f(x_{0})=0\) but should be picked so that it is close to zero1. We then have that \(x_{1}=\phi (x_{0})\) and can keep repeating this
process, i.e. \(x_{n+1}=\phi (x_{n})\). The solution we are looking for will be a value of \(x\) that is left unchanged by applying \(\phi \).
The different methods are different ways of building \(\phi (x)\) so that we can start the iteration scheme.
As an example of how to use the rearrangement iteration consider
\(\seteqnumber{0}{6.}{0}\)\begin{equation} f(x)=x^{5}-3x^3+2x-4=0. \label {eq: equation for iterating} \end{equation}
By rearranging this equation we have that
\(\seteqnumber{0}{6.}{1}\)\begin{equation*} x=\left (3x^{3}-2x+4\right )^{\frac {1}{5}}. \end{equation*}
From the plot we in fig. 6.1 we see that the root is between \(x=1.5\) and \(x=2\) and to see how the method works we will not attempt to start from that close to the true root. Here we take \(x_{0}=1.8\) and then iterate using
\(\seteqnumber{0}{6.}{1}\)\begin{equation*} x_{n+1}=\left (3x_{n}^{3}-2x_{n}+4\right )^{\frac {1}{5}}. \end{equation*}
The successive values of \(x_{n}\) and \(f(x_{n})\) are shown in table 6.1 and they are closing in on
\(\seteqnumber{0}{6.}{1}\)\begin{equation} x=1.757632748, \label {eq: precise root} \end{equation}
which is the value of the root to \(9\) decimal places. We see from the table that once we got to \(x_{5}\) we were only differing from the precise answer in the third decimal places, so are within two parts in \(10^{3}\). We can also see that lots of iterations are needed
to get an accurate answer. The precise number will depend on the specific problem.
| \(n\) | \(x_{n}\) | \(f(x_{n})\) |
| \(0\) | \(1.8\) | \(0.99968\) |
| \(1\) | \(1.7805378\) | \(0.52247969\) |
| \(2\) | \(1.7700175\) | \(0.27736234\) |
| \(3\) | \(1.7643295\) | \(0.14849136\) |
| \(4\) | \(1.761254\) | \(0.07986324\) |
| \(5\) | \(1.7595909\) | \(0.043059716\) |
| \(12\) | \(1.75765592\) | \(0.00058017842\) |
| \(18\) | \(1.7576331\) | \(7.8434818\times 10^{-6}\) |
1 It is useful to plot or roughly sketch the function \(f(x)\) as then it can be easier to pick a starting point.
-
Exercise 6.1. Implement this iteration method numerically for eq. (6.1) using a programming language or computer program of your choice. I would suggest trying Python or Matlab, but you can use whatever you feel most comfortable with.
Linear interpolation
The next method to look at is linear interpolation. The idea here is to pick two points \(A_{1},B_{1}\) on the graph \(y=f(x)\) that lie on either side of the root, i.e. so that \(f(A_{1})\) and \(f(B_{1})\) have opposite signs. We can then think about the
straight line2 joining these points \((A_{1},f(A_{1}))\) to \((B_{1},f(B_{1}))\). An example of this is shown in fig. 6.2 where \(A_{1}=1.5\) and \(B_{1}=1.8\).
The intersection of this straight line with the \(x\)-axis is given by
\(\seteqnumber{0}{6.}{2}\)\begin{equation*} x_{1}=\frac {A_{1}f(B_{1})-B_{1}f(A_{1})}{f(B_{1})-f(A_{1})}, \end{equation*}
We then replace \(A_{1}\) or \(B_{1}\) by \(x_{1}\), find the point on the curve corresponding to \(x=x_{1}\) and then iterate this process using the interpolation formula
\(\seteqnumber{0}{6.}{2}\)\begin{equation} x_{n}=\frac {A_{n}f(B_{n})-B_{n}f(A_{n})}{f(B_{n})-f(A_{n})}. \label {eq: linear interpolation formula} \end{equation}
With each iteration the chord will become shorter and the end points will move until the value of \(x_{n}\) converges to the precise value of the root. The first few steps of this interpolation starting from \(A_{1}=1.5\) and \(B_{1}=1.8\) are shown in table 6.2.
| \(n\) | \(A_{n}\) | \(f(A_{n})\) | \(B_{n}\) | \(f(B_{n})\) | \(x_{n}\) | \(f(x_{n})\) |
| \(1\) | \(1.5\) | \(-3.5315\) | \(1.8\) | \(0.99968\) | \(1.50003\) | \(-3.5310\) |
| \(2\) | \(1.50003\) | \(-3.5310\) | \(1.8\) | \(0.99968\) | \(1.50006\) | \(-3.53082\) |
| \(3\) | ||||||
| \(4\) | ||||||
| \(5\) |
We can see from this example that the linear interpolation method is much slower than rearrangement method, this will not always be true, but is your first hint that you should play around with several approaches before settling on the one that works the best. If you are writing code for these problems, then it is a good idea to have code that can implement any of the iteration schemes that we are discussing here.
Bisection method
Newton’s method
The main numerical method that is needed in this module is Newton’s method, sometimes called the Newton-Raphson method. Newton’s method finds the root by constructing the tangent to a curve through the initial point \(x_{0}\), and then
taking the next point \(x_{1}\) to be where the tangent line intersects the \(x\)-axis.
| \(n\) | \(x_{n}\) | \(f(x_{n})\) |
| \(0\) | \(1.8\) | \(0.99968\) |
| \(1\) | \(1.760530638\) | \(0.06382986248\) |
| \(2\) | \(1.757647406\) | \(0.00032122929\) |
| \(3\) | \(1.757632748\) | \(8.267167839\times 10^{-9}\) |
| \(4\) | \(1.757632748\) | \(-8.881784197\times 10^{-16}\) |
| \(5\) | \(1.757632748\) | \(-8.881784197\times 10^{-16}\) |
In other words we start from a guess, \(x_{0}\), then construct the tangent line
\(\seteqnumber{0}{6.}{3}\)\begin{equation*} y(x)=\left (x-x_{0}\right )f'(x_{0})+f(x_{0}). \end{equation*}
Once we have the tangent we find the value of \(x\) such that \(y(x)=0\) and call this \(x_{1}\). Doing this for a general point in the iteration \(x_{n}\) the iteration scheme is
\(\seteqnumber{0}{6.}{3}\)\begin{equation} x_{n+1}=x_{n}-\frac {f(x_{n})}{f'(x_{n})}. \label {eq: Newton iteration scheme} \end{equation}
An important observation here is that if the points \(x_{n}\) get close to a critical point of \(f(x)\) then the scheme will break down as then \(f'(x_{n})\) will be approaching zero. This means that we need to be very careful about picking our starting point, if we
pick one that is on the opposite side of a critical point from a root then we may not be able to get to the root. Figure 6.3 shows what the first step in Newton’s method looks like graphically.
For the specific equation in eq. (6.1) we have that
\(\seteqnumber{0}{6.}{4}\)\begin{equation} x_{n+1}=x_{n}-\frac {x_{n}^{5}-3x_{n}^3+2x_{n}-4}{5x_{n}^{4}-9x_{n}^{2}+2}. \end{equation}
Starting from \(x_{0}=1.8\) we get the sequence in table 6.3. This iteration scheme converges to the precise answer of eq. (6.2) much quicker than the other methods.
Newton’s method is the approach that you need to be able to use during this module so we will treat a couple more examples using it. There are a couple more examples on [Dawkins, 2025a] if you want to see more.
-
Example 6.2. Use Newton’s method to determine an approximation to the solution to \(\sin {x} = -x\) that lie in the interval \([-1,1]\). Find the approximation to \(6\) decimal places.
First we need to pick a starting point \(x_{0}\). Here we will take \(x_{0}=0.5\), you can get an idea of what value to pick by plotting the function. For this example we have that
\(\seteqnumber{0}{6.}{5}\)\begin{equation} f(x)=\sin (x)+x=0, \label {eq: sin +x roots} \end{equation}
so the iteration equation for Newton’s method eq. (6.4) becomes
\(\seteqnumber{0}{6.}{6}\)\begin{equation*} x_{n+1}=x_{n}-\frac {\sin {x_{n}}+x_{n}}{\cos {x_{n}}+1}. \end{equation*}
The first approximation is then
\(\seteqnumber{0}{6.}{6}\)\begin{equation*} x_{1}=\frac {1}{2}-\frac {\sin {\frac {1}{2}}+\frac {1}{2}}{\cos {\frac {1}{2}}+1}=-0.0216418 \end{equation*}
Table 6.4: Successive approximations to the root of eq. (6.6) using Newton’s method.\(n\) \(x_{n}\) \(f(x_{n})\) \(0\) \(0.5\) \(0.979426\) \(1\) \(-0.021642\) \(-0.043282\) \(2\) \(2\times 10^{-6}\) \(3.\times 10^{-6}\) \(3\) \(0\) \(0\) The further iteration steps are shown in table 6.4, and we see that to 6 decimal places, it only takes \(4\) iterative steps to find that the root is at \(x=0\). If we did any more steps we would see that these remain at \(x=0\).
Now we can consider one of the examples from [Dawkins, 2025a] which shows when Newton’s method does not work.
-
Example 6.3. Starting from \(x_{0}=1\) we will apply Newton’s method to \(\sqrt [3]{x}\).
Intuitively it is clear that the root is \(x=0\). However, Newton’s method will not find this root. For this example eq. (6.4) becomes
\(\seteqnumber{0}{6.}{6}\)\begin{equation*} x_{n+1}=x_{n}-\frac {\sqrt [3]{x}}{\frac {1}{3}x^{-\frac {2}{3}}}=x_{n}-3x_{n}=-2x_{n}. \end{equation*}
This already tells us that instead of converging to \(x=0\), Newton’s method will diverge with \(x_{1}=-2\), \(x_{2}=4\), \(x_{3}=-8\), \(x_{4}=16\), …. This is the opposite of what we want. Fortunately, it became obvious quite quickly that the method was not working and we did not have to waste much time before discovering that we needed to used a different model.
Secant method
A variant of Newton’s method is the Secant method, where we start with two estimates of the root, \(x_{0}\) and \(x_{1}\) and estimate the derivative as being the Newton quotient
\(\seteqnumber{0}{6.}{6}\)\begin{equation*} Q(x_{0},x_{1})=\frac {f(x_{1})-f(x_{1})}{x_{1}-x_{0}}, \end{equation*}
so that
\(\seteqnumber{0}{6.}{6}\)\begin{equation*} x_{2}=x_{1}-\frac {f(x_{1})}{Q(x_{0},x_{1})}=x_{1}-\frac {f(x_{1})}{\frac {f(x_{1})-f(x_{1})}{x_{1}-x_{0}}}. \end{equation*}
This means that the iteration scheme is given by
\(\seteqnumber{0}{6.}{6}\)\begin{equation} x_{n+1}=x_{n}-\frac {f(x_{n})}{Q(x_{n-1},x_{n})}=x_{n}-\frac {f(x_{n})}{\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}} \label {eq: secant method} \end{equation}
Geometrically, the secant method can also be viewed as constructing a line nearby our function and moving to the point where this line cuts the \(x\)-axis. However, this line is no longer a tangent line, but is a secant.
-
\(\seteqnumber{0}{6.}{7}\)
\begin{equation*} f(x)=x^{2}-10, \end{equation*}
and taking \(x_{0}=2\), \(x_{1}=3\) we find \(x_{2}\) using the secant method as follows:
\(\seteqnumber{0}{6.}{7}\)\begin{align*} x_{2}&=x_{1}-\frac {f(x_{1})}{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}\\ &=3-\frac {-1}{\frac {-1-(-6)}{3-2}}\\ &=3+\frac {1}{7}\\ &=3.14286. \end{align*} This is an equation that we can solve directly by the rearrangement method since \(f(x)=0\) corresponds to \(x^{2}=10\) so the exact answers are \(x=-\sqrt {10}\simeq -3.16228\) and \(x=\sqrt {10}\simeq 3.16228\). We can see that \(x_{2}\) is already approaching this exact answer.
Convergence and errors
The absolute error of a numerical method is the difference between the true solution \(x\) and the approximate solution \(\xi \), \(\epsilon =\vert x-\xi \vert \). It can be hard to estimate the absolute error unless we already know the exact solution.
We say that an iteration scheme converges when it subsequent iterations do not change the value of \(x_{n}\), at least to the accuracy that we are looking for. Not every method will converge for a given problem, We have already seen that Newton’s method does not converge for the cube root, \(\sqrt [3]{x}\). You will gain experience of which methods works best for which type of of problem. In this module, you will mainly be using Newton’s method so you need to remember that it can fail.