Course review

Things to remember for the final.

1Taylor expansions¶

Am I the only one who is constantly forgetting how these work? Please tell me I'm not?

$$f(x + a) = f(x) + af'(x) + \frac{a^2}{2}f''(x) + \frac{a^3}{6}f'''(x) + \ldots$$

2Fixed-point theorem¶

Theorem: if $g$ is continuous and differentiable over an interval $[a, b]$ such that $\forall x \in [a, b]$, $g(x) \in [a, b]$, and the first derivative satisfies $|g'(x)| < 1$ for all $x \in (a, b)$. Then, for any $x_0 \in [a, b]$, the sequence defined by $x_{n+1} = g(x_n)$ will converge to a unique fixed point $x^* \in [a, b]$ such that $g(x^*) = x^*$.

To prove it from first principles without the derivative assumption, define $h(x) = g(x) - x$ and use IVT to show that a fixed point exists, then get a contradiction with the $< \gamma$ assumption. The convergence proof probably involves a limit, I'm not sure.

3Interpolating polynomials¶

$$l_j = \frac{x-x_0}{x_j-x_0} \cdots \frac{x-x_{j-1}}{x_j-x_{j-1}} \cdot \frac{x-x_{j+1}}{x_j-x_{j+1}} \cdots \frac{x-x_n}{x_j-x_n}$$

In Newton form, we have

$$p_n(x) = \sum_{j=0}^n c_jw_j(x)$$

where $w_0(x) = 1$, $\displaystyle w_i(x) = \prod_{j=0}^{i-1} (x-x_j)$ for all other $i$, and $c_i = f[x_0, \ldots, x_i]$.

4Degree of accuracy (quadrature)¶

The largest $n$ such that all polys $p$ of deg $\leq n$ satisfy $I(p) = I_h(p)$

5Local truncation error (Runge-Kutta)¶

$$\tau_{i+1} = y(t_{i+1}) - w_{i+1}$$

6Order of a method (Runge-Kutta)¶

If the error is $O(h^n)$ the order is $n-1$

7Error bound for trapezoidal rule¶

$$\frac{(b-a)^3}{12} f''(\xi)$$

8Bisection method¶

$$\text{number of steps} = \log_2\left ( \frac{b-a}{\text{max error}} \right )$$

9Composite Simpson's rule¶

$$I_h(f) = \sum_{j=0}^{n/2-1} \frac{h}{3} (f_{2_j} + 4f_{2j+1} + f_{2j+2}) = \frac{h}{3}[f_0+f_n] +\frac{2h}{3} \sum_{j=1}^{n/2-1} f_{2j} + \frac{4h}{3}\sum_{j=0}^{n/2-1} f_{2j+1}$$