Optimisation, dynamics and computation

15.1 Numerical analysis

1. Theorem · A Existence and uniqueness of the interpolating polynomial For distinct nodes there is exactly one polynomial of degree at most $n$ through the given $n+1$ points, and it is $p(x) = \sum_j y_j\,\ell_j(x)$.
2. Theorem · A The Vandermonde determinant $\det V = \prod_{0 \le i < j \le n} (x_j - x_i)$. So $V$ is invertible exactly when the nodes are distinct.
3. Theorem · A Interpolation error formula If $f$ has $n+1$ continuous derivatives on $[a, b]$ and $p_n$ interpolates it at distinct nodes in $[a, b]$, then for each $x$ in $[a, b]$ there is a point $\xi$ in $(a, b)$ with $f(x) - p_n(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{j=0}^{n}(x - x_j)$.
4. Corollary · A Error bound for equally spaced nodes With nodes $x_j = a + jh$, $h = (b-a)/n$, we have $|w(x)| \le \tfrac14 h^{n+1} n!$ on $[a, b]$, so $|f(x) - p_n(x)| \le \dfrac{M_{n+1}\,h^{n+1}}{4(n+1)}$.
5. Theorem · A Properties of the Chebyshev polynomials $T_n(\cos\theta) = \cos n\theta$; $T_n$ has degree $n$ and leading coefficient $2^{n-1}$ (for $n \ge 1$); it has $n$ distinct roots $\cos\frac{(2k+1)\pi}{2n}$ in $(-1, 1)$; $|T_n| \le 1$ on $[-1, 1]$ and $T_n(\cos\frac{k\pi}n) = (-1)^k$.
6. Theorem · A Chebyshev's minimal property Among all monic polynomials of degree $m \ge 1$, none has a smaller largest absolute value on $[-1, 1]$ than $2^{1-m}$, and $T_m/2^{m-1}$ achieves it.
7. Corollary · A Error bound for Chebyshev nodes With the Chebyshev nodes on $[-1, 1]$, $|f(x) - p_n(x)| \le \dfrac{M_{n+1}}{2^n\,(n+1)!}$, and no choice of $n+1$ nodes makes the factor $\max|w|$ smaller than $2^{-n}$.
8. Theorem · A Newton's divided-difference formula With $p_k$ the interpolant through the first $k+1$ nodes, $p_n(x) = \sum_{k=0}^{n} f[x_0, \dots, x_k]\,(x - x_0)\cdots(x - x_{k-1})$, and the divided differences satisfy the quotient recursion in the definition.
9. Lemma · A Cauchy's mean value theorem If $g, k$ are continuous on $[0, h]$, differentiable on $(0, h)$ and $k' \ne 0$ there, then $\dfrac{g(h) - g(0)}{k(h) - k(0)} = \dfrac{g'(\tau)}{k'(\tau)}$ for some $\tau \in (0, h)$.
10. Theorem · A Error of the trapezoidal and Simpson rules On an interval of width $b - a$, $\int_a^b f - T = -\dfrac{(b-a)^3}{12}f''(\eta)$ and $\int_a^b f - S = -\dfrac{(b-a)^5}{2880}f^{(4)}(\eta)$ for some $\eta \in (a, b)$ (a different $\eta$ in each).
11. Theorem · A Composite trapezoidal and Simpson rules With $N$ pieces of width $h$: $T_N = h\big(\tfrac12 f_0 + f_1 + \cdots + f_{N-1} + \tfrac12 f_N\big)$ has error at most $\dfrac{(b-a)h^2}{12}M_2$, and (for $N$ even) $S_N = \dfrac h3\big(f_0 + 4f_1 + 2f_2 + 4f_3 + \cdots + 4f_{N-1} + f_N\big)$ has error at most $\dfrac{(b-a)h^4}{180}M_4$.
12. Theorem · A Newton's method converges quadratically If $f(r) = 0$, $f'(x_k) \ne 0$ and $f$ is twice differentiable, then $x_{k+1} - r = \dfrac{f''(\xi_k)}{2f'(x_k)}\,(x_k - r)^2$ for some $\xi_k$ between $x_k$ and $r$.