B9 - numerical differentiation

finite difference numerical integrator

for a given function, its derivative can be written as:

\frac{d f}{d t} \approx \frac{f (t + Δ t) - f (t)}{Δ t}

this is called the finite difference approximation
if $\frac{d x}{d t} = f (x) :$

\begin{matrix} \frac{x (t + Δ t) - x (t)}{Δ t} \approx f (x) \\ ⟹ x (t + Δ t) \approx x (t) + Δ t f (x) \end{matrix}

this is a numerical integrator

different schemes and errors

image: Tristanevanslee

the taylor approximations:

f (t \pm Δ t) \approx f (t) \pm \frac{d f}{d t} Δ t + \frac{Δ t^{2}}{2!} \frac{d^{2} f}{d t^{2}} \pm \frac{Δ t^{3}}{3!} \frac{d^{3} f}{d t^{3}} + \dots + O (Δ t^{4})

the forward difference scheme:

\frac{d f}{d t} \approx \frac{f (t + Δ t) - f (t)}{Δ t} = \frac{d f}{d t} + \underset{error}{\underset{⏟}{\frac{d^{2} f}{d t^{2}} \frac{Δ t}{2!} + \frac{d^{3} f}{d t^{3}} \frac{Δ t^{2}}{3!} + \dots}}

the leading order error term is: $\frac{d^{2} f}{d t^{2}} \frac{Δ t}{2!}$ , and is in the order, $O (Δ t)$
the backward difference scheme:

\frac{d f}{d t} \approx \frac{f (t + Δ t) - f (t)}{Δ t} = \frac{d f}{d t} - \underset{error}{\underset{⏟}{\frac{d^{2} f}{d t^{2}} \frac{Δ t}{2!} + \frac{d^{3} f}{d t^{3}} \frac{Δ t^{2}}{3!} + \dots}}

the error has the exact same form, but is negative
the central difference scheme:

\begin{matrix} f (t + Δ t) - f (t - Δ t) = 2 [\frac{d f}{d t} Δ t + \frac{Δ t^{3}}{3!} \frac{d^{3} f}{d t^{3}} + \dots + O (Δ t^{5})] \\ \frac{d f}{d t} \approx \frac{f (t + Δ t) - f (t - Δ t)}{2 Δ t} = \frac{d f}{d t} + \frac{Δ t^{2}}{3!} \frac{d^{3} f}{d t^{3}} + \dots + O (Δ t^{5}) \end{matrix}

this reduces the error to the order $O (Δ t^{2})$ , ie. if $Δ t$ is reduced by a factor of $10$ , the error is reduced by a factor of $100$ , and not just $10$ as it is for the previous schemes
note: the error can be further reduced by using taylor expansions for $f (t \pm 2 Δ t)$ , and so on

x1 - code for difference schemes comparison

second derivative

the finite difference approximation of the second derivative is:

\frac{d^{2} f}{d t^{2}} = \frac{f^{'} (t + Δ t) - f^{'} (t)}{Δ t}

using the taylor expansions of $f (t \pm Δ t) :$

\begin{matrix} f (t + Δ t) + f (t - Δ t) = 2 f (t) + Δ t^{2} f^{″} (x) + O (t^{4}) \\ ⟹ f^{″} (t) \approx \frac{f (t + Δ t) - 2 f (t) + f (t - Δ t)}{Δ t^{2}} + O (Δ t^{2}) \end{matrix}

this is the central difference second derivative approximation with error in the order, $O (t^{2})$
note: considering $f_{n} = f (x_{n}) = f (n Δ x)$ , for $x_{n} \in [x_{1}, x_{N}]$

\frac{d f}{d x} = {\begin{cases} forward difference fpr x_{1} \\ central difference for m i d d l e \\ backward difference for x_{N} \end{cases}

taking the step to zero

theoretically, taking the step, $Δ t$ , to zero should make the error arbitrarily small, but this is not possible due to numerical truncation error
computers can only store a finite precision of bits and and decimals smaller than this get truncated by rounding it off
for double precision, the round off error, $e_{r} \sim 10^{- 16}$
eg: $(\sqrt{2} + 10^{- 16} / 2)$ will be stored as $\sqrt{2}$

\begin{aligned} \frac{d f}{d t} & = \frac{f (t + Δ t) - f (t - Δ t) + 2 e_{r}}{2 Δ t} + O (t^{2}) \\ = \frac{f (t + Δ t) - f (t - Δ t)}{2 Δ t} + \frac{e_{r}}{Δ t} + O (t^{2}) \end{aligned}

therefore, as $Δ t \to 0$ , the round off error $\to \infty$

\begin{matrix} | error | \leq \frac{e_{r}}{Δ t} + \frac{Δ t^{2} m}{3!} = E_{m a x} (Δ t) \\ m = max (f^{‴}) for (t - Δ t) to (t + Δ t) \end{matrix}

the taylor series error: $O (Δ t^{2}) \sim Δ t^{2}$ , ie. $\to 0$ as $Δ t \to 0$ and $\to \infty$ as $Δ t \to \infty$
$e_{r} / Δ t \to \infty$ as $Δ t \to 0$ and $\to 0$ as $Δ t \to \infty$
to minimise the error:

\frac{\partial E_{m a x}}{\partial (Δ t)} = 0 ⟹ Δ t = 3 \sqrt{\frac{3 e_{r}}{m}}

assuming a constant $m \sim 1 : Δ t \sim 10^{- 5}$

numerical intefr

numerical integration of ODEs