1.1 Review of calculus
The theorems below are proved in a first course in real analysis. They are restated here in the form in which numerical analysis uses them: each one guarantees that some point exists, and the analysis then uses that point to bound an error.
Theorem 1.1.1 (Intermediate Value Theorem). If \(f\) is continuous on \([a,b]\) and \(K\) is any number between \(f(a)\) and \(f(b)\), then there is a number \(c\in (a,b)\) with \(f(c) = K\).
In particular, if \(f(a)\) and \(f(b)\) have opposite signs, \(f\) has a zero in \((a,b)\). This is the basis of the bisection method in Section 2.1.
Theorem 1.1.2 (Extreme Value Theorem). If \(f\) is continuous on \([a,b]\), there are points \(c_1,c_2\in [a,b]\) with \(f(c_1)\leq f(x)\leq f(c_2)\) for all \(x\in [a,b]\). If in addition \(f\) is differentiable on \((a,b)\), each of \(c_1, c_2\) is either an end point of \([a,b]\) or a point where \(f' = 0\).
The second sentence is how maxima are found in practice: compare the values of \(f\) at the end points and at the critical points.
Theorem 1.1.3 (Rolle’s Theorem and the Mean Value Theorem). Let \(f\) be continuous on \([a,b]\) and differentiable on \((a,b)\).
- (a)
- If \(f(a) = f(b)\), there is \(c\in (a,b)\) with \(f'(c) = 0\).
- (b)
- In general there is \(c\in (a,b)\) with \(f(b) - f(a) = f'(c)(b-a)\).
Theorem 1.1.4 (Generalized Rolle’s Theorem). Let \(f\in C[a,b]\) be \(n\) times differentiable on \((a,b)\). If \(f\) vanishes at \(n+1\) distinct points \(x_0<x_1<\dots <x_n\) of \([a,b]\), then \(f^{(n)}(c) = 0\) for some \(c\in (x_0,x_n)\).
Proof. By Rolle’s Theorem, \(f'\) vanishes at a point of each of the \(n\) intervals \((x_{i-1},x_i)\), so \(f'\) has \(n\) distinct zeros. Applying Rolle’s Theorem to \(f'\) between consecutive zeros gives \(n-1\) distinct zeros of \(f''\), and so on; after \(n\) steps \(f^{(n)}\) has at least one zero, lying in \((x_0,x_n)\). □
This theorem is the key to the error formula for polynomial interpolation (Theorem 6.1.3).
Theorem 1.1.5 (Weighted Mean Value Theorem for Integrals). If \(f\) is continuous on \([a,b]\), \(g\) is integrable on \([a,b]\) and \(g\) does not change sign there, then for some \(c\in [a,b]\) \[\int _a^b f(x)g(x)\,dx = f(c)\int _a^bg(x)\,dx .\]
Proof. Suppose \(g\geq 0\) (otherwise use \(-g\)). Let \(m\) and \(M\) be the minimum and maximum of \(f\). Then \(mg\leq fg\leq Mg\), and integrating, \(m\int g\leq \int fg\leq M\int g\). If \(\int g = 0\) any \(c\) works. Otherwise \(\int fg/\int g\) lies between \(m\) and \(M\), and by the Intermediate Value Theorem it equals \(f(c)\) for some \(c\). □
This is the tool that turns an error integral into the closed error terms of the quadrature rules in Section 8.2.
Theorem 1.1.6 (Taylor’s Theorem). Suppose \(f\in C^n[a,b]\), \(f^{(n+1)}\) exists on \([a,b]\), and \(x_0\in [a,b]\). Then for every \(x\in [a,b]\) there is a number \(\xi (x)\) between \(x_0\) and \(x\) such that \[f(x) = P_n(x) + R_n(x),\] where \begin {gather*} P_n(x) = \sum _{k=0}^n\frac {f^{(k)}(x_0)}{k!}(x-x_0)^k ,\\ R_n(x) = \frac {f^{(n+1)}(\xi (x))}{(n+1)!}(x-x_0)^{n+1}. \end {gather*}
\(P_n\) is the \(n\)th Taylor polynomial of \(f\) about \(x_0\) and \(R_n\) is the remainder or truncation error. When \(x_0 = 0\) the polynomial is also called a Maclaurin polynomial.
Proof. Fix \(x\neq x_0\) and choose the number \(K\) so that \[f(x) = P_n(x) + K(x-x_0)^{n+1}.\] Define, for \(t\) between \(x_0\) and \(x\), \[g(t) = f(x) - \sum _{k=0}^n\frac {f^{(k)}(t)}{k!}(x-t)^k - K(x-t)^{n+1}.\] Then \(g(x) = f(x) - f(x) - 0 = 0\) and \(g(x_0) = 0\) by the choice of \(K\). By Rolle’s Theorem, \(g'(\xi ) = 0\) for some \(\xi \) strictly between \(x_0\) and \(x\). Differentiating the sum, the terms telescope: \[\frac {d}{dt}\sum _{k=0}^n\frac {f^{(k)}(t)}{k!}(x-t)^k = \sum _{k=0}^n\frac {f^{(k+1)}(t)}{k!}(x-t)^k - \sum _{k=1}^n\frac {f^{(k)}(t)}{(k-1)!}(x-t)^{k-1} = \frac {f^{(n+1)}(t)}{n!}(x-t)^n .\] So \[0 = g'(\xi ) = -\frac {f^{(n+1)}(\xi )}{n!}(x-\xi )^n + (n+1)K(x-\xi )^n ,\] and since \(x-\xi \neq 0\), \(K = \dfrac {f^{(n+1)}(\xi )}{(n+1)!}\). □
Note. The point \(\xi (x)\) is not known; the theorem only says that it lies between \(x_0\) and \(x\). Error bounds are obtained by replacing \(|f^{(n+1)}(\xi )|\) by its largest possible value on that interval. This pattern (an exact error formula with an unknown point, followed by a bound) recurs throughout the course.
Example 1.1.7. Let \(f(x) = \cos x\) and \(x_0 = 0\).
- (a)
- Find the second Taylor polynomial \(P_2\) and use it to approximate \(\cos 0.01\). Bound the error.
- (b)
- Use \(P_3\) instead and bound the error.
- (c)
- Use \(P_2\) to approximate \(\int _0^{0.1}\cos x\,dx\) and bound the error.
Solution. The derivatives of \(\cos \) at \(0\) are \(1, 0, -1, 0, 1,\dots \), so \[\cos x = 1 - \frac {x^2}{2} + \frac {x^3}{6}\sin \xi (x)\] with \(\xi (x)\) between \(0\) and \(x\).
(a) \(P_2(0.01) = 1 - 0.00005 = 0.99995\). The error is \(\frac {(0.01)^3}{6}|\sin \xi |\) with \(0<\xi <0.01\). Using only \(|\sin \xi |\leq 1\) gives the bound \(1.\overline {6}\times 10^{-7}\). Using \(|\sin \xi |\leq |\xi |<0.01\) gives the sharper bound \[|\cos 0.01 - 0.99995|\leq \frac {(0.01)^3}{6}(0.01)\approx 1.67\times 10^{-9}.\] The actual error is \(4.17\times 10^{-10}\).
(b) Since the cubic term of the Maclaurin series of \(\cos \) is zero, \(P_3 = P_2\), but the remainder now has the form \(R_3(x) = \frac {x^4}{24}\cos \xi \), so \[|\cos 0.01 - 0.99995|\leq \frac {(0.01)^4}{24}\approx 4.17\times 10^{-10}.\] The same approximation, analysed with one more term, gets a bound that is almost exactly the true error.
(c) Integrating the identity term by term, \[\int _0^{0.1}\cos x\,dx = \left [x - \frac {x^3}{6}\right ]_0^{0.1} + \int _0^{0.1}\frac {x^3}{6}\sin \xi (x)\,dx = 0.0998\overline {3} + E,\] with \(|E|\leq \int _0^{0.1}\frac {x^3}{6}\,x\,dx = \frac {(0.1)^5}{30}\approx 3.3\times 10^{-7}\). In fact \(\int _0^{0.1}\cos x\,dx = \sin 0.1 = 0.09983341665\), so the error is \(8.33\times 10^{-8}\).
Example 1.1.8. How many terms of the series \(e = \sum _{k=0}^\infty \frac {1}{k!}\) are needed to compute \(e\) with an error less than \(10^{-6}\)?
Solution. Taylor’s Theorem for \(e^x\) about \(0\), evaluated at \(x=1\), gives \[e = \sum _{k=0}^n\frac {1}{k!} + \frac {e^{\xi }}{(n+1)!}, \qquad 0<\xi <1.\] The error is less than \(\frac {3}{(n+1)!}\), since \(e^\xi <e<3\). We need \((n+1)!>3\times 10^6\). Since \(9! = 362880\) and \(10! = 3628800\), \(n = 9\) suffices: ten terms, \(k = 0,\dots ,9\), give \(e = 2.7182815\ldots \) with error below \(8.3\times 10^{-7}\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.