MATH566 Lesson 2: Approximation assessment

Overview

• Mathematical problems: condition number

• Mathematical algorithms: absolute, relative errors and residuals

• Rate of convergence

Mathematical problem

• A mathematical problem is a mapping from input set $X$ to output set $Y$

• Often the mapping is a function: a single output $y\in Y$ for given input $x\in X$

  ${\displaystyle f:X\to Y,y=f\left(x\right),x\stackrel{f}{\to }y}$

• Examples:

  • Compute the square of a real: $X=ℝ,Y=ℝ,y=f\left(x\right)=x^2.$

  • Find $x$solution of $ax+b=c$ for given $a,b,c\in ℝ$, $a\ne 0$.

    ${\displaystyle X=ℝ\backslash \left\{0\right\}\times ℝ\times ℝ,Y=ℝ,f(a,b,c)=(c-b)/a.}$

  • Compute the innner product of two vectors $𝒖,𝒗\in {ℝ}^n$:

    ${\displaystyle X={ℝ}^n\times {ℝ}^n,Y=ℝ,y=f(𝒖,𝒗)=\sum _{i=1}^n{u}_i{v}_i}$

Mathematical problem: more examples

• For $u,v$ continuous functions $u,v\in C^{\left(0\right)}\left([a,b]\right)$, compute definite integral

  ${\displaystyle f(u,v)=(u,v)=\underset{a}{\overset{b}{\int }}u\left(x\right)v\left(x\right)dx,X=C^{\left(0\right)}\left([a,b]\right)\times C^{\left(0\right)}\left([a,b]\right),Y=ℝ.}$

• Compute the derivative of a function $g\in C^{\left(1\right)}\left(ℝ\right)$

  ${\displaystyle X=C^{\left(1\right)}\left(ℝ\right),Y=C^{\left(0\right)}\left(ℝ\right),f=d/dx(\mathrm{an}\mathrm{operator}).}$

• Find roots of polynomial $p_n\left(x\right)=a_n{x}^n+\dots +a_{1}x+a_0$. Input: polynomial coefficients $𝒂\in {ℝ}^{n+1}$, $a_n\ne 0$. Output: $𝒙\in {ℝ}^n$, $p_n\left(x_i\right)=0$. $f:{ℝ}^{n+1}\to {ℝ}^n$. The function $f:X\to Y$ cannot be written explicitly (corollary of Abel-Ruffini theorem), but there are approximations $\stackrel{\sim }{f}$ of the root-finding function that can be implemented such $\stackrel{\sim }{f}\cong f$.

Mathematical problems: formalism for assessing intrinsic difficulty

• How hard is it to solve a mathematical problem? Idea: a problem is difficult to solve if small changes in inputs produce large changes in output. “Small” and “large” require definition of a way to measure mathematical objects including numbers, vectors, functions.

• Organize mathematical objects as a vector space $𝒱=(V,S,+,\cdot )$

  Addition rules for	$\forall 𝒂,𝒃,𝒄\in V$
  $𝒂+𝒃\in V$	Closure
  $𝒂+(𝒃+𝒄)=(𝒂+𝒃)+𝒄$	Associativity
  $𝒂+𝒃=𝒃+𝒂$	Commutativity
  $𝟎+𝒂=𝒂$	Zero vector
  $𝒂+(-{𝒂}_{})=𝟎$	Additive inverse
  Scaling rules for	$\forall 𝒂,𝒃\in V$, $\forall x,y\in S$
  $x𝒂\in V$	Closure
  $x(𝒂+𝒃)=x𝒂+x𝒃$	Distributivity
  $(x+y)𝒂=x𝒂+y𝒂$	Distributivity
  $x(y𝒂)=(xy)𝒂$	Composition
  $1𝒂=𝒂$	Scalar identity

• Examples: $(ℝ,ℝ,+,\cdot ),({ℝ}^n,ℝ,+,\cdot ),(C^0[a,b],ℝ,+,\cdot )$

Mathematical problems: norms

Definition. A norm on vector space $𝒳$ is a function $||||:X\to {ℝ}_{+}$, that for any $x,y,z\in X$, $\alpha \in ℝ$ satisfies the properties:

• In $(ℝ,ℝ,+,\cdot )$, $x\in ℝ,||x||=\left|x\right|$

• In $({ℝ}^m,ℝ,+,\cdot )$, $𝒙\in {ℝ}^n$, ${||𝒙||}_p={\left({\sum }_{i=1}^m{\left|x_i\right|}^p\right)}^{1/p}$

• In $(C[a,b],ℝ,+,\cdot )$, $g\in C[a,b]$, ${||g||}_{\infty }={max}_{a⩽x⩽b}\left|g\left(x\right)\right|$

• In $(C[a,b],ℝ,+,\cdot )$, $g\in C[a,b]$, ${||g||}_2={({\int }_a^b{\left[g\left(x\right)\right]}^{2}dx)}^{1/2}$

• In $(C[a,b],ℝ,+,\cdot )$, $g\in C(a,b)$, ${||g||}_{\infty }={sup}_{a<x<b}\left|g\left(x\right)\right|$

Condition number of a mathematical problem

• With an appropriate formalism now defined (vector space, norm), quantify the idea of “large output change for small input change”

Definition. The problem $f:X\to Y$ has absolute condition number

For $f$ differentiable, the absolute condition number is norm of the Jacobian

Definition. The problem $f:X\to Y$ has relative condition number

Condition number examples

• Condition number of the identity mapping, $f:X\to X$, $f\left(x\right)=x$

  ${\displaystyle \hat{\kappa }=||f^{\text{'}}||=1}$

  Change in output is as large as that in input: the problem is well conditioned.

• Condition number of subtraction: $f:{ℝ}^2\to ℝ$, $f(x_1,x_2)=x_1-x_2$

  ${\displaystyle \hat{\kappa }=||𝑱||,𝑱=\left[\begin{array}{ll}\frac{\partial f}{\partial x_1}& \frac{\partial f}{\partial x_2}\end{array}\right]=\left[\begin{array}{ll}1& -1\end{array}\right],\hat{\kappa }={||𝑱||}_{\infty }=2}$ ${\displaystyle \kappa =\frac{{||𝑱||}_{\infty }}{||f||/||𝒙||}=\frac{2}{|x_1-x_2|/max(x_1,x_2)}}$

  Problem is well conditioned in absolute terms, ill conditioned in relative terms for $x_1\cong x_2$.

Approximation sequence convergence

• Let ${\left\{y_n\right\}}_{n\in \mathbb{N}}$ be a sequence of approximations of $y$, ${lim}_{n\to \infty }{y}_n=y$

• Recall definition of limit: $\forall \epsilon >0$, $\exists N_{\epsilon }$ such that for $n>N_{\epsilon }$, $|y_n-y|<\epsilon$

• Difficulty: $y$ is not known! (that's the whole point of a numerical algorithm that constructs approximations of $y$)

• Two approaches:

  1. Adopt Cauchy sequence criterion: $\forall \epsilon >0$, $\exists N_{\epsilon }$ such that for $n>N_{\epsilon }$, $p\in {\mathbb{N}}^{\ast },|y_{n+p}-y|<\epsilon$. This means successive terms are getting closer to one another. Most often $p=1$. In complete metric spaces ($ℝ$, ${ℝ}^m$) Cauchy sequences converge.

  2. Estimate approximation convergence through residual. For mathematical problem $y=f\left(x\right)$, formulate $F(x,y)=y-f\left(x\right)=0$. The residual at step $n$ of the approximation sequence is $r_n=F(x,y_n)$. Estimate convergence in terms of ${\left\{r_n\right\}}_{n\in \mathbb{N}}$, ${lim}_{n\to \infty }{r}_n=0$.

Rate of convergence

• Practical computation is concerned not only with accuracy, but also with minimizing computational effort.

Definition. ${\left\{y_n\right\}}_{n\in \mathbb{N}}$ converges to $y$ with rate $r\in (0,1)$ and order $p$ if

• The above definition requires knowledge of the exact solution $y$. Replace with a Cauchy-type definition

  ${\displaystyle {lim}_{n\to \infty }\frac{|y_{n+2}-y_{n+1}|}{{|y_{n+1}-y_n|}^p}=r.}$

• $p=1,2,3$ are known as linear, quadratic, cubic convergence, respectively.