Chapter 2 Solutions of Equations: Root-finding#
Arya and the mystery of the Rhind papyrus#
College life is full of adventures, some hopefully of intellectual nature, and Arya is doing her part by taking a history of science class. She learns about the Rhind papyrus; an ancient Egyptian papyrus purchased by an antiquarian named Henry Rhind in Luxor, Egypt, in 1858.
Fig. 1 Rhind Mathematical Papyrus. (British Museum Image under a Creative Commons license.)#
The papyrus has a collection of mathematical problems and their solutions; a translation is given by Chace and Manning [1927]. The following is Problem 26, taken from [Chace and Manning, 1927]:
A quantity and its \(1/4\) added together become 15. What is the quantity?
Assume 4.
As many times as 5 must be multiplied to give 15, so many times 4 must be multiplied to give the required number. Multiply 5 so as to get 15.
Multiply 3 by 4.
The quantity is
Arya’s instructor knows she has taken math classes and asks her if she could decipher this solution. Although Arya’s initial reaction to this assignment can be best described using the word “despair”, she quickly realizes it is not as bad as she thought. Here is her thought process: the question, in our modern notation is, find \(x\) if \(x+x/4=15\). The solution starts with an initial guess \(p=4\). It then evaluates \(x+x/4\) when \(x=p\), and finds the result to be 5: however, what we need is 15, not 5, and if we multiply both sides of \(p+p/4=5\) by 3, we get \((3p)+(3p)/4=15\). Therefore, the solution is \(3p=12\).
Here is a more general analysis of this solution technique. Suppose we want to solve the equation \(g(x)=a\), and that \(g\) is a linear map, that is, \(g(\lambda x)=\lambda g(x)\) for any constant \(\lambda\). Then, the solution is \(x=ap/b\) where \(p\) is an initial guess with \(g(p)=b\). To see this, simply observe
The general problem#
How can we solve equations that are far complicated than the ancient Egyptians solved? For example, how can we solve \(x^{2}+5\cos x=0\)? Stated differently, how can we find the root \(p\) such that \(f(p)=0\), where \(f(x)=x^{2}+5\cos x\)? In this chapter we will learn some iterative methods to solve equations. An iterative method produces a sequence of numbers \(p_{1},p_{2},...\) such that \(\lim_{n\rightarrow\infty}p_{n}=p,\) and \(p\) is the root we seek. Of course, we cannot compute the exact limit, so we stop the iteration at some large \(N\), and use \(p_{N}\) as an approximation to \(p\).
The stopping criteria#
With any iterative method, a key question is how to decide when to stop the iteration. How well does \(p_{N}\) approximate \(p\)?
Let \(\epsilon>0\) be a small tolerance picked ahead of time. Here are some stopping criteria: stop when
\(|p_{N}-p_{N-1}|<\epsilon\),
\(\left|\frac{p_{N}-p_{N-1}}{p_{N}}\right|<\epsilon,p_{N}\neq0\), or
\(|f(p_{N})|<\epsilon.\)
However, difficulties can arise with any of these criteria:
It is possible to have a sequence \(\{p_{n}\}\) such that \(p_{n}-p_{n-1}\rightarrow0\) but \(\{p_{n}\}\) diverges.
It is possible to have \(|f(p_{N})|\) small (called residual) but \(p_{N}\) not close to \(p\).
In our numerical results, we will experiment with various stopping criteria. However, the second criterion is usually preferred over the others.
Exercise 2.1 Solve the following problems and discuss their relevance to the stopping criteria.
a. Consider the sequence \({p_n}\) where \(p_n=\sum_{i=1}^n \frac{1}{i}\). Argue that \({p_n}\) diverges, but \(\lim_{n\rightarrow\infty} (p_n-p_{n-1})=0\).
b. Let \(f(x)=x^{10}\). Clearly, \(p=0\) is a root of \(f\), and the sequence \(p_n=\frac{1}{n}\) converges to \(p\). Show that \(f(p_n)<10^{-3}\) if \(n>1\), but to obtain \(|p-p_n|<10^{-3}\), \(n\) must be greater than \(10^3\).