Burden & Faires, 9th Ed. - §1.1–1.4
Chapter 1: Error Analysis
Calculus foundations · Types of error · Floating-point arithmetic & round-off · Algorithms, stability & rates of convergence
Every numerical method in this course does the same trade: it swaps an equation we cannot solve exactly for one we can solve approximately, on a machine that cannot even store most real numbers exactly. This chapter is about making that trade honestly - knowing where the error comes from, how big it can get, and how fast it shrinks. Every later chapter leans on the vocabulary built here: the Taylor remainder that bounds interpolation and integration error, the machine epsilon that limits how small a step size can usefully be, and the order of convergence that tells you whether an iterative method is worth running.
Section 1.1
Calculus Foundations
Continuity and the Intermediate Value Theorem
Definition - Continuity
A function $f$ is continuous at $x_0$ if $\displaystyle\lim_{x\to x_0} f(x) = f(x_0)$. $f\in C[a,b]$ means $f$ is continuous at every point of $[a,b]$; $f\in C^n[a,b]$ means $f, f', \ldots, f^{(n)}$ are all continuous on $[a,b]$.
Theorem 1.1.1 - Intermediate Value Theorem
If $f\in C[a,b]$ and $K$ is any number between $f(a)$ and $f(b)$, then there exists $c\in(a,b)$ with $f(c)=K$.
A special case - if $f(a)$ and $f(b)$ have opposite signs, some $c\in(a,b)$ satisfies $f(c)=0$ - is the entire justification for the Bisection Method in the next chapter: it is what guarantees a root exists inside the bracket before we ever start halving it.
Rolle's Theorem and the Mean Value Theorem
Theorem 1.1.2 - Rolle's Theorem
If $f\in C[a,b]$, $f$ is differentiable on $(a,b)$, and $f(a)=f(b)$, then there exists $c\in(a,b)$ with $f'(c)=0$.
Theorem 1.1.3 - Mean Value Theorem
If $f\in C[a,b]$ and $f$ is differentiable on $(a,b)$, then there exists $c\in(a,b)$ with
$$f'(c) = \frac{f(b)-f(a)}{b-a}$$
The Mean Value Theorem is the workhorse behind nearly every error bound in this course - it is how we convert a statement about function values into a statement about a derivative evaluated at some unknown but bounded point $c$.
Taylor's Theorem
Theorem 1.1.4 - Taylor's Theorem with Lagrange Remainder
Suppose $f\in C^n[a,b]$ and $f^{(n+1)}$ exists on $(a,b)$. For $x_0\in[a,b]$, the $n$th Taylor polynomial for $f$ about $x_0$ is
$$P_n(x) = \sum_{k=0}^{n} \frac{f^{(k)}(x_0)}{k!}(x-x_0)^k$$
and for every $x\in[a,b]$ there exists $\xi(x)$ strictly between $x_0$ and $x$ such that
$$f(x) = P_n(x) + R_n(x), \qquad R_n(x) = \frac{f^{(n+1)}(\xi(x))}{(n+1)!}(x-x_0)^{n+1}$$
$R_n(x)$ is the truncation error - the exact price of stopping the infinite Taylor series after $n+1$ terms.
$f(x)=\sin(x)$ (gray) against its Taylor polynomial $P_n(x)$ about $x_0=0$ (blue). Raise $n$ and watch the interval of good agreement widen - but the polynomial always eventually diverges outside it, exactly as $R_n(x)$ predicts.
📘 Example 1.1 - How Many Terms Does $e^{0.5}$ Need?
Use the Taylor polynomial for $f(x)=e^x$ about $x_0=0$ to approximate $e^{0.5}$ to within $10^{-6}$. How many terms are required?
Solution
Every derivative of $f$ is $f^{(k)}(x)=e^x$, so $P_n(x) = \sum_{k=0}^n \dfrac{x^k}{k!}$ and
$$R_n(0.5) = \frac{e^{\xi}}{(n+1)!}(0.5)^{n+1}, \qquad \xi\in(0,0.5)$$
Since $\xi<0.5$, we bound $e^\xi < e^{0.5} < 2$ (a crude but safe bound that avoids circularity - we don't yet know $e^{0.5}$, so we use $e^{0.5}<\sqrt{4}=2$). So
$$|R_n(0.5)| < \frac{2\,(0.5)^{n+1}}{(n+1)!}$$
We need the right side below $10^{-6}$. Tabulate:
$n=7$ is the first value below $10^{-6}$.
$n=7$ terms ($P_7$) guarantee error $<10^{-6}$. Direct computation gives $P_7(0.5)=1.6487212\ldots$ against the true value $e^{0.5}=1.6487213\ldots$ - error $\approx 4\times10^{-8}$, comfortably inside the bound, since Lagrange remainder bounds are always conservative.
| $n$ | $2(0.5)^{n+1}/(n+1)!$ |
|---|---|
| 4 | $2(0.5)^5/120 = 5.2\times10^{-4}$ |
| 5 | $2(0.5)^6/720 = 4.3\times10^{-5}$ |
| 6 | $2(0.5)^7/5040 = 3.1\times10^{-6}$ |
| 7 | $2(0.5)^8/40320 = 1.9\times10^{-7}$ |
📘 Example 1.2 - Finding the MVT Point $c$
For $f(x) = x^3 - 2x$ on $[0,2]$, find the point(s) $c$ guaranteed by the Mean Value Theorem.
Solution
$$\frac{f(2)-f(0)}{2-0} = \frac{(8-4)-0}{2} = 2$$
We need $f'(c) = 3c^2 - 2 = 2 \;\Rightarrow\; c^2 = \tfrac{4}{3} \;\Rightarrow\; c = \tfrac{2}{\sqrt3} \approx 1.1547$.
$c = 2/\sqrt3 \approx 1.1547 \in (0,2)$ ✓. The negative root $-2/\sqrt3$ is discarded - it lies outside $(0,2)$.
Section 1.2
Types of Error
Absolute and Relative Error
Definition - Absolute & Relative Error
If $p^*$ approximates $p$, the absolute error is $|p-p^*|$ and, provided $p\neq0$, the relative error is
$$\frac{|p-p^*|}{|p|}$$
Relative error is almost always the more meaningful quantity - an absolute error of $0.1$ is disastrous for $p=0.001$ but irrelevant for $p=10^8$.
Significant Digits
$p^*$ agrees with $p$ to $t$ significant digits if $t$ is the largest nonnegative integer with $\dfrac{|p-p^*|}{|p|} \le 5\times10^{-t}$. This is the precise version of "accurate to $t$ digits."
Truncation Error vs. Round-off Error
The Two Sources of Numerical Error
- Truncation error - the error from replacing an infinite/exact process with a finite one: stopping a Taylor series, replacing a derivative with a finite difference, replacing an integral with a finite sum. It is a property of the method, and it is still there even on a perfect, infinite-precision machine.
- Round-off error - the error from the computer's inability to store most real numbers exactly, and from the finite arithmetic performed on those stored approximations. It is a property of the machine, and it is still there even for a method with zero truncation error.
Section 1.3
Floating-Point Arithmetic & Round-off Error
Binary Representation and Machine Epsilon
A normalized binary floating-point number has the form
$$x = \pm(1.b_1b_2b_3\cdots b_t)_2 \times 2^{e}, \qquad b_i\in\{0,1\}$$
with $t$ stored bits after the binary point (the double-precision IEEE 754 standard used by MATLAB, Python, and virtually every numerical library sets $t=52$). Only finitely many real numbers can be represented exactly this way - every other real number is rounded to the nearest representable one, called fl$(x)$.
Definition - Machine Epsilon
The machine epsilon $\varepsilon_{\text{mach}} = 2^{-t}$ is the distance from $1$ to the next larger representable number. It bounds the relative round-off error of storing any number:
$$\left|\frac{\text{fl}(x) - x}{x}\right| \le \varepsilon_{\text{mach}}$$
For IEEE double precision, $\varepsilon_{\text{mach}} = 2^{-52}\approx 2.22\times10^{-16}$ - roughly 15–16 correct decimal digits, no matter what $x$ is.
Loss of Significance (Catastrophic Cancellation)
The Danger: Subtracting Nearly-Equal Numbers
When two floating-point numbers that are close in value are subtracted, the leading (correct) digits cancel and what remains is dominated by whatever round-off error was already present in the operands. The relative error of the result can be enormous even though each operand was individually accurate to full machine precision. This single fact drives the design of half the formulas in this course - you will see it again when Chapter 4 rewrites the forward-difference derivative formula, and when the quadratic formula needs a "stable" version.
x = 10^4
Computing $g(x)=\sqrt{x+1}-\sqrt{x}$ two mathematically equivalent ways in real IEEE double precision: the naive subtraction (red) vs. the algebraically rationalized form $\dfrac{1}{\sqrt{x+1}+\sqrt{x}}$ (blue), which never subtracts two close numbers. Drag to increase $x$ and watch the naive method's relative error climb while the stable one stays flat.
📘 Example 1.3 - Rationalizing to Avoid Cancellation
Explain why $g(x) = \sqrt{x+1}-\sqrt{x}$ is numerically dangerous for large $x$, and find an equivalent, stable formula.
Solution
For large $x$, $\sqrt{x+1}\approx\sqrt{x}$ - we are subtracting two nearly identical floating-point numbers, each already carrying round-off error of relative size $\sim\varepsilon_{\text{mach}}$. Rationalizing the numerator:
$$g(x) = \sqrt{x+1}-\sqrt{x} = \frac{(\sqrt{x+1}-\sqrt{x})(\sqrt{x+1}+\sqrt{x})}{\sqrt{x+1}+\sqrt{x}} = \frac{1}{\sqrt{x+1}+\sqrt{x}}$$
This version only adds positive numbers and divides - no cancellation is possible at any $x$.
Stable form: $g(x) = \dfrac{1}{\sqrt{x+1}+\sqrt{x}}$. At $x=10^{10}$, double precision gives the naive formula a relative error near $10^{-6}$ (it should be exact to $\sim10^{-16}$) while the stable formula stays accurate to full machine precision - a loss of roughly 10 significant digits from cancellation alone.
📘 Example 1.4 - The Stable Quadratic Formula
Solve $x^2 + 62.10x + 1 = 0$ using 4-digit rounding arithmetic, and show why the standard quadratic formula fails for one root.
Solution
$\sqrt{b^2-4ac} = \sqrt{62.10^2-4} = \sqrt{3856-4.000} = \sqrt{3852} = 62.06$ (4 digits).
$$x_1 = \frac{-62.10+62.06}{2} = \frac{-0.04000}{2} = -0.02000, \qquad x_2 = \frac{-62.10-62.06}{2}=-62.08$$
The true roots (to 6 digits) are $x_1=-0.0161070$ and $x_2=-62.0839$. The large root $x_2$ is fine (error $\approx0.04\%$), but $x_1$ is off by nearly $25\%$ - the subtraction $-62.10+62.06$ cancelled almost all the significant digits of the numerator. The fix: compute the "safe" root normally, then get the other root from $x_1 x_2 = c/a$:
$$x_1 = \frac{c}{a\,x_2} = \frac{1}{(1)(-62.08)} = -0.01611$$
Stable roots: $x_1\approx-0.01611$, $x_2\approx-62.08$ - the product trick recovers the small root to full precision without ever subtracting nearby numbers.
Section 1.4
Algorithms, Stability & Rates of Convergence
Stable vs. Unstable Algorithms
Definition - Stability
Denote by $E_0$ a small initial error (from round-off or data uncertainty) and by $E_n$ the corresponding error after $n$ subsequent operations. An algorithm is
- stable if $E_n$ grows no faster than $\propto n$ (linearly) as $n$ increases,
- unstable if $E_n$ grows exponentially, e.g. $E_n \propto C^n$ for some $C>1$.
Rate of Convergence and Big-O Notation
Definition - Big-O for Sequences and Functions
Suppose $\{\beta_n\}\to0$ and $\{\alpha_n\}\to\alpha$. We say $\{\alpha_n\}$ converges to $\alpha$ with rate of convergence $O(\beta_n)$, written $\alpha_n = \alpha + O(\beta_n)$, if there exists a constant $K>0$ with
$$|\alpha_n - \alpha| \le K|\beta_n| \quad\text{for } n \text{ sufficiently large}$$
The same definition applies to functions as $h\to0$: $F(h)=L+O(h^p)$ means the error shrinks at least as fast as $h^p$.
Definition - Order of Convergence of an Iterative Method
If a sequence $p_n\to p$ with error $e_n = p_n - p$, and constants $\lambda>0$, $\alpha>0$ exist such that
$$\lim_{n\to\infty} \frac{|e_{n+1}|}{|e_n|^\alpha} = \lambda$$
then $\{p_n\}$ converges to $p$ of order $\alpha$ with asymptotic error constant $\lambda$. $\alpha=1$ (with $\lambda<1$) is linear convergence; $\alpha=2$ is quadratic. This single number is what separates the Bisection Method ($\alpha=1$) from Newton's Method ($\alpha=2$) in the next two chapters - and the difference is not cosmetic.
Iterations to reach error < 10⁻¹⁰: -
Starting from the same initial error $e_0=0.5$ and asymptotic constant $\lambda=0.5$, each curve applies $e_{n+1}=\lambda\,e_n^{\alpha}$. Switch order to see why quadratic convergence (Newton's Method, Ch. 4) reaches machine precision in a handful of steps while linear convergence (Bisection, Ch. 2) crawls.
📘 Example 1.5 - Estimating Order of Convergence from Data
An iterative method produces the errors below. Estimate its order of convergence $\alpha$.
Solution
Assume $|e_{n+1}| \approx \lambda|e_n|^\alpha$. Taking logs of two consecutive ratios and solving for $\alpha$:
$$\alpha \approx \frac{\ln(|e_{n+1}|/|e_n|)}{\ln(|e_n|/|e_{n-1}|)}$$
Using $n=1,2,3$: $\ln(|e_2|/|e_1|) = \ln(0.0625) = -2.7726$, and $\ln(|e_1|/|e_0|)=\ln(0.25)=-1.3863$, giving $\alpha\approx1.9999\approx2$. Checking with $n=2,3$: $\ln(|e_3|/|e_2|)=\ln(0.0039063)=-5.5452$ and $\ln(|e_2|/|e_1|)=-2.7726$, giving $\alpha\approx 2.0000$.
$\alpha=2$ - this data is quadratically convergent, consistent with $e_n \sim (0.5)^{2^n-1}\cdot 0.5$, the signature footprint of Newton's Method near a simple root (Chapter 4).
| $n$ | $e_n = |p_n-p|$ |
|---|---|
| 0 | $5.0\times10^{-1}$ |
| 1 | $1.25\times10^{-1}$ |
| 2 | $7.8125\times10^{-3}$ |
| 3 | $3.0518\times10^{-5}$ |
Practice
Practice Problem
Try this problem yourself before expanding the solution below.
✏️ Practice Problem 1.1 - Taylor Polynomial Error for $\ln(1.4)$
Let $f(x)=\ln(1+x)$. Use the third-degree Taylor polynomial $P_3(x)$ expanded about $x_0=0$ to approximate $\ln(1.4)$. Then find an upper bound on the truncation error using the Lagrange remainder $R_3(x)$, and compare that bound to the actual error.
Solution
Differentiating: $f'(x)=\frac{1}{1+x}$, $f''(x)=\frac{-1}{(1+x)^2}$, $f'''(x)=\frac{2}{(1+x)^3}$, $f''''(x)=\frac{-6}{(1+x)^4}$. So
$$P_3(x) = x - \frac{x^2}{2} + \frac{x^3}{3}.$$
At $x=0.4$: $P_3(0.4) = 0.4 - 0.08 + 0.021333 = 0.341333$.
The true value is $\ln(1.4) = 0.336472$, giving an actual error of $|0.341333-0.336472| = 0.004861$.
For the bound, $R_3(x) = \frac{f''''(\xi)}{4!}x^4$ for some $\xi \in (0,0.4)$. Since $|f''''(\xi)| = \frac{6}{(1+\xi)^4}$ is largest at $\xi=0$ (where it equals $6$), $$|R_3(0.4)| \le \frac{6}{24}(0.4)^4 = 0.25 \times 0.0256 = 0.0064.$$ $P_3(0.4)=0.341333$, actual error $\approx 0.004861$, theoretical bound $0.0064$ - the bound safely covers the true error, as it must.
The true value is $\ln(1.4) = 0.336472$, giving an actual error of $|0.341333-0.336472| = 0.004861$.
For the bound, $R_3(x) = \frac{f''''(\xi)}{4!}x^4$ for some $\xi \in (0,0.4)$. Since $|f''''(\xi)| = \frac{6}{(1+\xi)^4}$ is largest at $\xi=0$ (where it equals $6$), $$|R_3(0.4)| \le \frac{6}{24}(0.4)^4 = 0.25 \times 0.0256 = 0.0064.$$ $P_3(0.4)=0.341333$, actual error $\approx 0.004861$, theoretical bound $0.0064$ - the bound safely covers the true error, as it must.
Connections Across the Course
- The Taylor remainder $R_n(x)$ reappears as the exact error term for every interpolation formula in Chapter 5 and every finite-difference formula in Chapter 8.
- Machine epsilon sets a hard floor on how small a step size $h$ can usefully be - shrink $h$ past it in Chapter 8 and round-off error, not truncation error, starts dominating.
- Order of convergence $\alpha$ is computed by exactly Example 1.5's method to compare the Bisection Method, Fixed-Point Iteration, and Newton's Method head-to-head in Chapters 2–4.