These notes are based on Chapter 10 of Jones, O., Maillardet, R., & Robinson, A. (2009). Introduction to scientific programming and simulation using R. CRC Press.


A root is a solution of \(f(x)=0\). Visually, a root is a point where the graph \(y=f(x)\) crosses the x-axis. For example, in the interval \([0,10]\), there are two roots of the following \(f\):

plot(c(1,7), c(0,0), pch = 19,
     xlim=c(0,10), ylim=c(-1050,1050),
     xlab="x", ylab="y",
curve((x-1)*(x-7)*(x-13)*(x-16), from=0, to=10, add=TRUE)
text(1, 100, "root at x = 1", pos=4)
text(7, -100, "root at x = 7", pos=4)

Root finding is important because:

  • Factorisation of a polynomial, one of the most popular classes of functions (e.g., Taylor series approximation). For example, \[\begin{align} f(x) &= x^4-37x^3+447x^2-1867x+1456\\ &= (x-1)(x-7)(x-13)(x-16) \end{align}\]
  • Many problems can be modelled as root finding of suitable functions. Remember that finding a root of \(f(x)\) is equivalent to solving an equation \(g(x)=h(x)\) where \(f(x) = g(x)-h(x)\).

Loan repayments

Let’s suppose:

  • \(P_n\) : Remaining amount of loan after \(n\) months
  • \(P_0\) : Initial amount of loan
  • \(N\) : Duration of repayments
  • \(A\) : Monthly repayment amount
  • \(r\) : Monthly interest rate

Given \(P_{n-1}\), we know: \[P_n = (1+r)P_{n-1} - A\] That is, each month, interest based on \(P_{n-1}\) is added and then you repay \(A\). The solution of the difference equation (i.e., the expression of \(P_n\) as a function of \(n\)) is:

\[ P_n = (1+r)^nP_0 - \frac{A}{r}\left((1+r)^n-1\right) .\]

To see this, for each \(k\in\{1,\dots,n\}\), multiply both sides of \(P_k = (1+r)P_{k-1} - A\) by \((1+r)^{n-k}\) and get a telescoping sum.

We negotiate with a bank on the interest rate. A question is under what \(r\), can we repay the loan after \(N\) months?

We could get the answer by solving \(P_N=0\) for \(r\): \[\begin{alignat}{2} && P_N &= 0\\ &\Leftrightarrow \quad & (1+r)^NP &= \frac{A}{r}\left((1+r)^N-1\right)\\ &\Leftrightarrow \quad & (1+r)^N &= \frac{A}{A-rP}\\ &&&\vdots \end{alignat}\] Well, this is hard (at least for me). Instead, we may use numerical root-finding methods for \(f(r):=P_N\).

Fixed-point iteration

Fixed point

Let \(g: \mathbb{R}\to\mathbb{R}\) be a continuous function. Then, a fixed point of \(g\) is a solution of \(g(x)=x\). Visually, a fixed point is a point where the graph \(y=g(x)\) crosses the 45-degree line. For example, a hyperbolic tangent \[g(x) = 2\tanh(x) = 2\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}\] has three fixed points: \(x = -1.915, 0, 1.915\).

x <- c(-1.915,0,1.915)
y <- c(-1.915,0,1.915)
plot(x, y, pch = 19, xlim=c(-2,2), ylim=c(-2,2))
curve(2*tanh(x), from=-3, to=3, add=TRUE)
curve(x*1, from=-3, to=3, add=TRUE)
text(-1.55, -.8, "fixed point at -1.915")
text(0, -.2, "fixed point at 0", pos=4)
text(1.55, .8, "fixed point at 1.915")
arrows(-1.8, -1, -1.9, -1.8, length=0.1)
arrows(1.8, 1, 1.9, 1.8, length=0.1)