Math 128A: Numerical Analysis
Week 1
1.1 Calculus
Why numerical analysis?
Root finding, integrals, differential equations, etc.
Introductory Concepts
Consider a function, $G(s, x)$, where $s$ is a source position and $x$ is a spatial variable. ($x \in \mathbb{R}^2$ or $x \in \mathbb{R}^3$.) I might care about this definite integral:
\[f(x) = \int_{0}^{2\pi} G(s, x)\text{d}s\]Suppose $s$ parameterizes a curve (a circle), $y(s) = (\cos(s), \sin(s))$.
What is the Mean Value Theorem?
Theorem (Mean Value Theorem).
Let $f : [a,b] \rightarrow \mathbb{R}$ be a function such that:
- $f$ is continuous on the closed interval $[a,b]$, and
- $f$ is differentiable on the open interval $(a,b)$.
Then there exists some $c \in (a,b)$ such that
\[f'(c) = \frac{f(b) - f(a)}{b - a}.\]In other words, at some point $c$ between $a$ and $b$, the instantaneous rate of change (the derivative) equals the average rate of change over the interval.
Theorem (Generalized Mean Value Theorem).
\[f(a) = f'(a) = f''(a) = \cdots = f^{(n-1)}(a) = 0.\]
Let $f : [a,b] \rightarrow \mathbb{R}$ be $n$-times differentiable on $(a,b)$ and continuous on $[a,b]$.
Suppose thatThen there exists some $c \in (a,b)$ such that
\[f(b) = \frac{f^{(n)}(c)}{n!}(b-a)^n .\]This result is a higher-order extension of the Mean Value Theorem and forms the basis for the remainder term in Taylor’s theorem.
Theorem (Generalized Rolle’s Theorem).
\[f(x_0) = f(x_1) = \cdots = f(x_n)\]
Let $f : [a,b] \rightarrow \mathbb{R}$ be $n$-times differentiable on $(a,b)$ and continuous on $[a,b]$.
Suppose thatwhere
\[a = x_0 < x_1 < \cdots < x_n = b.\]Then there exists some $c \in (a,b)$ such that
\[f^{(n)}(c) = 0.\]
1.2 Convergence
Definition (Convergence). Consider a sequence, $(x_n)$ in $\mathbb{R}$. $\lim_{n \to \infty}x_n = x$ if, for every $\epsilon > 0$, there exists $r \in \mathbb{R}$ such that for all $n > r$, $\vert x_n - x\vert < \epsilon$.
Types of Convergence
Definition (At Least Linear Convergence). $(x_n)$ converges to $x$ at least linearly if there exists $c \in \mathbb{R}$ such that, for sufficiently large $n$, $\vert x_{n+1} - x\vert \leq c\vert x_{n} - x \vert$.
Definition (Superlinear Convergence). $(x_n)$ converges to $x$ superlinearly if there exists some sequence $(\epsilon_n) \in \mathbb{R}$ such that $(\epsilon_n)$ converges to 0 and, for sufficiently large $n$, $\vert x_{n+1} - x\vert \leq \epsilon_n\vert x_{n} - x \vert$.
Definition (Quadratic Convergence). $(x_n)$ converges to $x$ at least quadratically if there exists $c \gt 0$ such that, for sufficiently large $n$, $\lvert x_{n+1} - x\rvert \leq c\lvert x_{n} - x \rvert^2$.
What is the definition of Convergence of Order $\alpha$?
Definition (Convergence of Order $\alpha$). $(x_n)$ converges to $x$ at with order $\alpha$ if there exists $c \gt 0$ such that, for sufficiently large $n$, $\vert x_{n+1} - x\vert \leq c\vert x_{n} - x \vert^{\alpha}$.
Order $\alpha$ convergence is often not practical to consider. Finally, a really weak notion of convergence is sublinear convergence ($\alpha = 1$ and $c = 1$).
Definition (Sublinear Convergence). $(x_n)$ converges to $x$ at sublinearly if, for sufficiently large $n$, $\vert x_{n+1} - x\vert \leq \vert x_{n} - x \vert$.
Examples
- $x_n = \frac{1}{2^n}$ converges linearly to 0. (Check with something similar to the ratio test!)
- $y_n = \frac{1}{n!}$ converges at least superlinearly to 0, but not quadratically!
- $z_n = \frac{1}{n^{2^n}}$ converges at least quadratically.
Notation
Formally, how are Big-$\mathcal O$ and Little-$\mathcal o$ defined?
Definition (Big-$\mathcal{O}$ Notation for Functions). If $f,g$ are real-valued functions over real-valued inputs, then, for $c \in \mathbb{R}$, $f(x) = \mathcal{O}(g(x))$ as $x \to c$ if $\vert f(x) \vert \leq M \vert g(x) \vert$ for all $x$ near (but not equal to) $c$.
Definition (Little-$\mathcal{o}$ Notation). $x_n = \mathcal{o}(\alpha_n)$ if there exists $(\epsilon_n) \in \mathbb{R}_{\geq0}$ such that $(\epsilon_n)$ converges to 0 and $\vert x_n \vert \leq \epsilon_n \vert \alpha_n \vert$.
It can be said that $\frac{n}{3n^2 + 1} = \mathcal{O}(\frac{1}{n})$. Also, if $x_n = \mathcal{O}(\alpha_n)$ and $y_n = \mathcal{O}(\alpha_n)$, then $x_n + y_n = \mathcal{O}(\alpha_n)$.
As an example, $\arctan(x) = x + \mathcal{O}(x^3)$.
Also, recall that $\frac{1}{1 + x} = 1 - x + x^2 - \ldots$, so $\frac{1}{1 + \mathcal{O}(x)} = 1 + \mathcal{O}(x)$.
Week 2
2.1 Floating Point
Polynomials
Horner’s method for evaluating polynomials: nest the multiplications! In other words, to evaluate a polynomial, use $p(x) = a_0 + x(a_1 + x(a_2 + \ldots))$. How many multiplications and how many additions is this?
Rounding and Chopping
Rounding and chopping are means of reducing the precision of a real-valued number. If only allowed $n$ digits, formally let $\tilde x$ be $x$ rounded to $n$ digits and let $\hat x$ be $x$ chopped to $n$ digits.
Lemma (Error of Rounding). $\vert x - \tilde x \vert < \frac{1}{2} \cdot 10^{-n}$.
Lemma (Error of Chopping). $\vert x - \hat x \vert < 10^{-n}$.
Provide proof of the error lemmas above.
Proof. Consider $n = 0$. $x \in [x_0, x_0 + 1]$, so $\hat x$ is either $x_0$ or $x_0 + 1$. $\vert \hat x - x \vert < 1$. Also, $\vert \tilde x - x \vert \leq \frac{1}{2}$. For $n > 0$, can reduce to $n=0$ case by multiplying by 10. (More formally write this out later.)
Scientific Notation
In base-2, a number $x$ can be represented as $\pm q \cdot 2^m$, where $q \in [\frac{1}{2}, 1)$ and $m$ is an integer.
Floating Point
A computer has specific ways of representing floating points. One bit is allocated to store the sign of the number. Some bits are allocated to store the biased exponent of the number. Finally, some more bits are allocated to store the mantissa of the floating point.
For example,
| s | e | f |
|---|---|---|
| 1 bit | 8 bits (with bias 127) | 23 bits |
Specifically, $m = e - 127$ and $q = 1.f$ (the mantissa always assumes a leading 1).
What are the parameters for IEEE 64-bit floating point? What is $(\frac{1}{5})_2$ stored as?
TODO.
Machine numbers are representable by the given machine. In general, if $x_-$ is the largest machine number less than $x$, and $x_+$ is the smallest machine number greater than $x$, then $\text{fl}(x)$ is the machine number that is closest.
What is $\text{fl}(\frac{1}{5})$?
$x_+$.
Definition (Machine Epsilon). The smallest $\epsilon$ such that $1 + \epsilon \neq 1$.
2.2 Errors
How are absolute and relative error defined?
If $x$ is approximated by $x^\ast$, the absolute error is $\vert x - x^\ast \vert$. The relative error is $\vert \frac{x - x^\ast}{x} \vert$.
Subtraction Issues
Subtracting two nearly equal terms tends to result in loss of precision.
How to avoid loss of precision when calculating the roots of $x^2 + 62x + 1$?
Calculate $x = \frac{-2c}{-b - \sqrt{b^2 - 4ac}}$ instead of $x = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$.
How to avoid loss of precision when calculating $x - \sin x$ where $x$ is near 0?
Reformulate $\sin$ as a truncated Taylor series.
Checking for Equality
Never use == unless certain that numbers are constructed to be identical. In general, abs(a - b) < tolerance is a safer bet.
For example, because $\text{fl}(\pi)$ is only an approximation of $\pi$, $\sin \pi \approx \epsilon$, so $\sin \pi == 0$ will not be true. Machine errors cause the graph of the nested form to be bumpy. Compare the plots of $(x - 1)^3$ and $-1 + x(3 + x(-3 + x))$.
Week 3
2.3 Stability
A process is unstable if small errors made at one stage are magnified in subsequent stages.
What is the conditioning number of a differentiable function, $f: (a, b) \to \mathbb R$?
If $x \in (a, b)$, $x \frac{f’(x)}{f(x)}$. Larger the magnitude, the more sensitive to errors.
By MVT, $f(x + h) - f(x) = f’(\xi)h$. Approximately, $f(x + h) - f(x) \approx f’(x)h$, and $\frac{f(x + h) - f(x)}{f(x)} \approx \frac{f’(x)h}{f(x)}$. Suppose we are examining truncation error, and $x + h = \text{fl}(x)$. Then,
\[x \frac{f'(x)}{f(x)} \frac{h}{x}\]is large when:
- $x$ is large.
- $\frac{f’(x)}{f(x)}$ is large.
- $\frac{h}{x}$ is large (large relative error).
Suppose $f(x) = \pi^x$, $x = 20$, and $h = 0.1$. What is the relative error of $f$?
0.11, or 11 percent. Unstable!
Is the recursive definition of the sequence $x_n = \frac{10}{3}x_{n - 1} - x_{n - 2}$ stable?
No.
3.1 Bisection Method
What is true of the roots of $f$ if $f(a)f(b) < 0$?
There is a root $r \in (a, b)$.
Specifically, the bisection method, given $f$ and a starting interval $[a_0, b_0]$:
- $c = (a + b) / 2$.
- If $0 < b - c$ is small, $c$ is root.
- If the sign of $f(a)$ is not equal to the sign of $f(c)$, then $b = c$. Otherwise, $a = c$.
The Bisection Method converges as $n \to \infty$, so it is an exact algorithm.
Prove that the Bisection Method is an exact algorithm, with roughly linear convergence.
What is the error at iteration $n$?
Slow, can’t find roots without sign change.
3.2 Newton’s Method
Update $x_{n + 1} = x_n + \frac{f(x_n)}{f’(x_n)}$ until within error bound. Need $f’$, but much faster than Bisection Method.
Error Analysis
Theorem (Quadratic Convergence of Newton’s Method).
\[f(r) = 0, \quad f'(r) \ne 0.\]
Let $f$ be twice continuously differentiable on an interval containing a root $r$, and supposeIf the initial guess $x_0$ is sufficiently close to $r$, then the Newton iteration
\[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\]converges to $r$ with second-order (quadratic) convergence, i.e. there exists a constant $C>0$ such that
\[|x_{n+1}-r| \le C |x_n-r|^2\]for all sufficiently large $n$.
Derive the error convergence for Newton’s method.
3.3 Secant Method
Week 4
3.4 Fixed-Point Methods
Theorem (Fixed Point Existence and Uniqueness).
Let $g:[a,b] \to [a,b]$ be a function such that
- $g$ is continuous on $[a,b]$.
Then there exists at least one fixed point $x^\ast \in [a,b]$ such that
\[g(x^\ast) = x^\ast.\]If in addition
\[|g'(x)| \le k < 1 \quad \text{for all } x \in [a,b],\]then
\[x_{n+1} = g(x_n)\]
- the fixed point is unique, and
- the fixed-point iteration
converges to $x^\ast$ for any initial $x_0 \in [a,b]$.