Chapter 18: Approximation and Error
Beginner
18.1 Linear Approximation
If $f$ is differentiable near $a$, then for values of $x$ close to $a$:
$$f(x) \approx f(a) + f'(a)(x-a)$$Define $\Delta x=x-a$ and $\Delta f=f(a+\Delta x)-f(a)$. Then:
$$\Delta f \approx f'(a)\,\Delta x$$As $\Delta x$ approaches $0$, the error of this approximation approaches $0$ much faster than $\Delta x$ itself (even the error divided by $\Delta x$ approaches $0$).
$f(x) = \sqrt{x}$, $a = 4$, $x = 4.1$
$f(4) = 2$, $f'(x) = \dfrac{1}{2\sqrt{x}}$, $f'(4) = \dfrac{1}{4}$
$\sqrt{4.1} \approx 2 + \dfrac{1}{4}(0.1) = 2.025$
(Actual value: 2.02485...)
18.2 Error Estimation
If $f$ can be differentiated twice between $a$ and $x$, Taylor's theorem lets us write the error using some point $c$ between $a$ and $x$:
$$f(x)-L(x)=\dfrac{f''(c)}{2}(x-a)^2$$Therefore, if we know a constant $M$ such that $|f''(t)|\le M$ throughout the interval, an upper bound for the error is:
$$|f(x)-L(x)|\le\dfrac{M}{2}(x-a)^2$$The first equation expresses the error itself in terms of the second derivative at some point $c$. The equation involving $M$ gives an upper bound that can be estimated in advance.
18.3 Newton's Method
An iterative method for finding a solution to the equation $f(x)=0$:
$$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$However, $f'(x_n)\ne0$ is required at every iteration. Depending on the choice of the initial value, the method may fail to converge. Convergence is not guaranteed by the iteration formula alone.
Find the zero of $f(x) = x^2 - 2$.
$f'(x) = 2x$
Iteration formula: $x_{n+1} = x_n - \dfrac{x_n^2 - 2}{2x_n} = \dfrac{x_n^2 + 2}{2x_n} = \dfrac{x_n + \dfrac{2}{x_n}}{2}$
Start with $x_0 = 1$:
- $x_1 = \dfrac{1 + 2}{2} = 1.5$
- $x_2 = \dfrac{1.5 + 1.333...}{2} = 1.4167$
- $x_3 = 1.41422...$
The sequence quickly converges to $\sqrt{2} \approx 1.41421...$.
Frequently Asked Questions
How large is the error in a linear approximation?
If $f$ can be differentiated twice, the error can be written as $\left|f''(c)\right|h^2/2$ using some point $c$ between $a$ and $a+h$ (Taylor's theorem). Furthermore, if $|f''(t)|\le M$ throughout the interval, the error is at most $Mh^2/2$. The smaller $h$ is, the smaller the error. The larger $|f''|$ is, the larger the error.
When should higher-order approximations be used?
When a linear (first-order) approximation is not accurate enough, second- or third-order approximations can be used. For example, near $x=0$, $\sin x \approx x - \dfrac{x^3}{6}$ (a third-order approximation), which is more accurate than the first-order approximation when $x$ is sufficiently small. However, a Taylor approximation is useful only near its expansion point, and its range of accuracy should be evaluated using the error term. Higher-order expansions are needed in numerical computation and perturbation theory in physics.
What is the difference between truncation error and rounding error?
Truncation error is the error caused by stopping a Taylor expansion after a finite number of terms (a mathematical error). Rounding error is the error caused by a computer's limited number of digits (an implementation-related error). Balancing these two types of error is important in numerical computation.
Exercises
Use linear approximation to estimate $\ln(1.1)$.
Use Newton's method to approximate $\sqrt[3]{5}$, starting from $x_0 = 2$ and performing two iterations.
Show Answers
Answer to Exercise 1
$f(x) = \ln x$, $a = 1$
$f(1) = 0$, $f'(1) = 1$
$\ln(1.1) \approx 0 + 1 \times 0.1 = 0.1$
(Actual value: 0.0953...)
Answer to Exercise 2
$f(x) = x^3 - 5$, $f'(x) = 3x^2$
$x_{n+1} = x_n - \dfrac{x_n^3 - 5}{3x_n^2}$
$x_0 = 2$: $x_1 = 2 - \dfrac{8-5}{12} = 2 - 0.25 = 1.75$
$x_1 = 1.75$: $x_2 = 1.75 - \dfrac{5.359-5}{9.1875} \approx 1.711$
($\sqrt[3]{5} \approx 1.71$)