MATH566 Lesson 4: Numerical experiments

Overview

• Error functions and truncation error

• Round-off error

• Order, rate of convergence estimation

Error functions

• Standard sequences ${\left\{y_n\right\}}_{n\in \mathbb{N}}$ converge to a scalar, ${lim}_{n\to \infty }{y}_n=y\in ℝ$

• Often, the object of numerical approximation is a function

  ${\displaystyle {\left\{f_n\right\}}_{n\in \mathbb{N}},{lim}_{n\to \infty }{f}_n=f;f,f_n:ℝ\to ℝ.}$

• Example: Taylor polynomial (truncation of Taylor series) of $f:ℝ\to ℝ$

  ${\displaystyle p_n\left(x\right)=f\left(x_0\right)+f^{\text{'}}\left(x_0\right)(x-x_0)+\cdots +\frac{1}{n!}{f}^{\left(n\right)}\left(x_0\right){(x-x_0)}^n.}$

• The goal of numerical analysis in such cases is to detemine an error function

  ${\displaystyle f\left(x\right)=p_n\left(x\right)+r_n\left(x\right),r_n\left(x\right)=\frac{1}{(n+1)!}{f}^{(n+1)}\left(\xi \right){(x-x_0)}^{n+1}}$

• Structure in error function: not converged, truncation error dominates.

• Randomness in error function: converged to machine precision, roundoff error dominates.

Order, rate of convergence estimation

• Typical convergence behavior demonstrated by derivative approximation of

  ${\displaystyle g=f^{\text{'}},f\left(x\right)=e^x-1,x_0=0,g\left(x_0\right)=f^{\text{'}}\left(x_0\right)={lim}_{h\to 0}\frac{f(x_0+h)-f\left(x_0\right)}{h}.}$

  through finite differences

  ${\displaystyle g_n=\frac{f_n-f\left(0\right)}{h_n},f_n=f\left(h_n\right),h_n=2^{-n}.}$

  $\begin{array}{lllll}n& 1& 2& \dots & N\\ h_n=2^{-n}& 1/2& 1/4& \dots & 1/2^N\\ f_n& f_1& f_2& \dots & f_N\\ g_n=\frac{f_n-f\left(0\right)}{h_n}& \frac{f_1-f\left(0\right)}{(1/2)}& \frac{f_n-f\left(0\right)}{(1/4)}& \dots & \frac{f_n-f\left(0\right)}{(1/2^N)}\\ d_{n-1}=|g_n-g_{n-1}|& -& d_1=|g_2-g_1|& \dots & d_{N-1}=|g_N-g_{N-1}|\end{array}$

  Table 1. Calculations to construct approximation of derivative for $f\left(x\right)$, at $x_0=0$.

Convergence order estimation by taking logarithms

• From definition

  ${\displaystyle {lim}_{n\to \infty }\frac{|x_{n+1}-x|}{{|x_n-x|}^p}=r}$

• Assume that for some $n$, $d_n=|x_n-x|$

  ${\displaystyle d_{n+1}\cong r{d}_n^p.}$

• Since $d_n$ is small, take logarithm, $$$c_n=\log d_n$ and obtain

  ${\displaystyle c_{n+1}\cong p{c}_n+\log r.}$

• Subtract successive terms $c_n-c_{n-1}\cong p(c_{n-1}-c_{n-2})$, get average slope

  ${\displaystyle p\cong \frac{1}{N-3}\sum _{n=3}^{N-1}\frac{c_n-c_{n-1}}{c_{n-1}-c_{n-2}}}$

Cauchy sequence convergence, comparison to standard sequences

• Order of convergence definition ${lim}_{n\to \infty }\frac{|x_{n+1}-x|}{{|x_n-x|}^p}=r$ requires knowledge of limit $x$. Replace with

  ${\displaystyle {lim}_{n\to \infty }\frac{|x_{n+1}-x_n|}{{|x_n-x_{n-1}|}^q}=s}$

  $(q,s)$ are estimates of the order, rate of convergence $(p,r)$

• It is useful to compare order of convergence of approximation sequence ${\left\{x_n\right\}}_{n\in \mathbb{N}}$ to some standard sequences, in particular:

  • power function $n^{-p}$

  • exponential function $r^{-n}$

• Sequences that converge like $n^{-p}$ for some $p$ have algebraic convergence

• Sequences that converge like $r^{-n}$ for:

  • some $r>1$ have geometric convergence

  • any $r>1$ have supergeometric convergence