numerical analysis brief overview

Contents

Interpolation

Lagrange polynomial

Given a set of $k + 1$ data points

(x_{0}, y_{0}), \dots, (x_{j}, y_{j}), \dots, (x_{k}, y_{k})

$(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})$

where no two $x_{j}$ are the same, the interpolation polynomial in the Lagrange form is a linear combination

L (x) := \sum_{j = 0}^{k} y_{j} ℓ_{j} (x)

$L(x):=\sum _{j=0}^{k}y_{j}\ell _{j}(x)$

of Lagrange basis polynomials

ℓ_{j} (x) := \prod_{\begin{matrix} 0 \leq m \leq k \\ m \neq j \end{matrix}} \frac{x - x_{m}}{x_{j} - x_{m}} = \frac{(x - x_{0})}{(x_{j} - x_{0})} \dots \frac{(x - x_{j - 1})}{(x_{j} - x_{j - 1})} \frac{(x - x_{j + 1})}{(x_{j} - x_{j + 1})} \dots \frac{(x - x_{k})}{(x_{j} - x_{k})},

$\ell _{j}(x):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\frac {x-x_{m}}{x_{j}-x_{m}}}={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}},$

Remainder in Lagrange interpolation formula

R (x) = f (x) - L (x)

$R(x)=f(x)-L(x)$

ℓ (x) = (x - x_{0}) (x - x_{1}) \dots (x - x_{k}) R (x) = f [x_{0}, \dots, x_{k}, x] ℓ (x) = ℓ (x) \frac{f^{(k + 1)} (ξ)}{(k + 1)!}, x_{0} < ξ < x_{k},

$\ell (x)=(x-x_{0})(x-x_{1})\cdots (x-x_{k}) \\ {\displaystyle R(x)=f[x_{0},\ldots ,x_{k},x]\ell (x)=\ell (x){\frac {f^{(k+1)}(\xi )}{(k+1)!}},\quad \quad x_{0}<\xi <x_{k},}$

The remainder can be bound as

\frac{ℓ (x)}{(k + 1)!} min_{x_{0} \leq ξ \leq x_{k}} f^{(k + 1)} (ξ) \leq R (x) \leq \frac{ℓ (x)}{(k + 1)!} max_{x_{0} \leq ξ \leq x_{k}} f^{(k + 1)} (ξ)

${\frac {\ell(x)}{(k+1)!}}\min _{x_{0}\leq \xi \leq x_{k}}f^{(k+1)}(\xi ) \leq R(x)\leq {\frac {\ell(x)}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}f^{(k+1)}(\xi )$

Newton polynomial

divided differences

[y_{ν}] := y_{ν}, ν \in {0, \dots, k} [y_{ν}, \dots, y_{ν + j}] := \frac{[y_{ν}, \dots, y_{ν + j - 1}] - [y_{ν + 1}, \dots, y_{ν + j}]}{x_{ν} - x_{ν + j}}, ν \in {0, \dots, k - j}, j \in {1, \dots, k}

$[y_{\nu }]:=y_{\nu },\qquad \nu \in \{0,\ldots ,k\} \\ [y_{\nu },\ldots ,y_{{\nu +j}}]:={\frac {[y_{{\nu }},\ldots ,y_{{\nu +j-1}}]-[y_{{\nu +1}},\ldots ,y_{{\nu +j}}]}{x_{\nu }-x_{{\nu +j}}}},\qquad \nu \in \{0,\ldots ,k-j\},\ j\in \{1,\ldots ,k\}$

\begin{matrix} x_{0} & f (x_{0}) \\ \frac{f (x_{1}) - f (x_{0})}{x_{1} - x_{0}} \\ x_{1} & f (x_{1}) & \frac{\frac{f (x_{2}) - f (x_{1})}{x_{2} - x_{1}} - \frac{f (x_{1}) - f (x_{0})}{x_{1} - x_{0}}}{x_{2} - x_{0}} \\ \frac{f (x_{2}) - f (x_{1})}{x_{2} - x_{1}} \\ x_{2} & f (x_{2}) & ⋮ \\ ⋮ \\ ⋮ & ⋮ \\ ⋮ \\ x_{n} & f (x_{n}) \end{matrix}

${\begin{matrix}x_{0}&f(x_{0})&&\\&&{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}}&\\x_{1}&f(x_{1})&&{{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}-{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}&\\x_{2}&f(x_{2})&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&f(x_{n})&&\\\end{matrix}}$

(\begin{matrix} f [x_{0}] & f [x_{0}, x_{1}] & f [x_{0}, x_{1}, x_{2}] & \dots & f [x_{0}, \dots, x_{n}] \\ 0 & f [x_{1}] & f [x_{1}, x_{2}] & \dots & f [x_{1}, \dots, x_{n}] \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & f [x_{n}] \end{matrix})

${\begin{pmatrix}f[x_{0}]&f[x_{0},x_{1}]&f[x_{0},x_{1},x_{2}]&\ldots &f[x_{0},\dots ,x_{n}]\\0&f[x_{1}]&f[x_{1},x_{2}]&\ldots &f[x_{1},\dots ,x_{n}]\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}$

Given a set of $k + 1$ data points

(x_{0}, y_{0}), \dots, (x_{j}, y_{j}), \dots, (x_{k}, y_{k})

$(x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})$

where no two $x_{j}$ are the same, the Newton interpolation polynomial is a linear combination of Newton basis polynomials

N (x) := \sum_{j = 0}^{k} a_{j} n_{j} (x)

$N(x):=\sum _{{j=0}}^{{k}}a_{{j}}n_{{j}}(x)$

with the Newton basis polynomials defined as

n_{j} (x) := \prod_{i = 0}^{j - 1} (x - x_{i})

$n_{j}(x):=\prod _{{i=0}}^{{j-1}}(x-x_{i})$

for $j > 0$ and $n_{0}(x)= 1$ .

The coefficients are defined as

a_{j} := [y_{0}, \dots, y_{j}]

$a_{j}:=[y_{0},\ldots ,y_{j}]$

where

[y_{0}, \dots, y_{j}]

$[y_{0},\ldots ,y_{j}]$

is the notation for divided differences.

Thus the Newton polynomial can be written as

N (x) = [y_{0}] + [y_{0}, y_{1}] (x - x_{0}) + \dots + [y_{0}, \dots, y_{k}] (x - x_{0}) (x - x_{1}) \dots (x - x_{k - 1}) .

$N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{{k-1}}).$

The remainder can be bound as

\frac{ℓ (x)}{(k + 1)!} min_{x_{0} \leq ξ \leq x_{k}} f^{(k + 1)} (ξ) \leq R (x) \leq \frac{ℓ (x)}{(k + 1)!} max_{x_{0} \leq ξ \leq x_{k}} f^{(k + 1)} (ξ)

${\frac {\ell(x)}{(k+1)!}}\min _{x_{0}\leq \xi \leq x_{k}}f^{(k+1)}(\xi ) \leq R(x)\leq {\frac {\ell(x)}{(k+1)!}}\max _{x_{0}\leq \xi \leq x_{k}}f^{(k+1)}(\xi )$

Hermite interpolation

Repeat points divided differences:

R e p e a t p o i n t s : f (x_{0}) = a, f^{'} (x_{0}) = b, f^{″} (x_{0}) = c, \dots f [x_{0}, x_{0}] = lim_{x_{1} \to x_{0}} f [x_{0}, x_{1}] = lim_{x_{1} \to x_{0}} \frac{f (x_{1}) - f (x_{0})}{x_{1} - x_{0}} = f^{'} (x_{0}) f [x_{0}, x_{0}, x_{0}] = lim_{\begin{aligned} x_{1} \to x_{0} \\ x_{2} \to x_{0} \end{aligned}} f [x_{0}, x_{1}, x_{2}] = \frac{1}{2!} f^{″} (x_{0}) \dots f [x_{0}, \dots, x_{0}] = lim_{x_{i} \to x_{0}} f [x_{0}, x_{1}, \dots, x_{n}] = \frac{1}{n!} f^{(n)} (x_{0})

$Repeat\ points: \quad f(x_{0}) = a,\ f'(x_{0}) = b, \ f''(x_{0})=c,\ \dots\\ f\left[ x_{0},x_{0} \right] = \lim\limits_{x_{1}\rightarrow x_{0}} f \left[ x_{0},x_{1} \right] = \lim\limits_{x_{1}\rightarrow x_{0}}\frac{f(x_{1}) - f(x_{0})}{x_{1} - x_{0}} = f'(x_{0}) \\ f\left[ x_{0},x_{0},x_{0} \right] = \lim\limits_{\begin{align} x_{1}\rightarrow x_{0} \\ x_{2} \rightarrow x_{0} \end{align}}f\left[ x_{0},x_{1},x_{2} \right] = \frac{1}{2!}f''(x_{0}) \\ \cdots \\ f\left[ x_{0}, \dots,x_{0} \right] = \lim\limits_{x_{i}\rightarrow x_{0}} f \left[ x_{0},x_{1},\dots,x_{n} \right] = \frac{1}{n!}f^{(n)}(x_{0})$

Runge's phenomenon

In the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation points. The discovery was important because it shows that going to higher degrees does not always improve accuracy.

Linear interpolation

If the two known points are given by the coordinates $(x_0, y_0)$ and $(x_1, y_1)$ , the linear interpolant is the straight line between these points. For a value $x$ in the interval $(x_0, x_1)$ , the value $y$ along the straight line is given from the equation of slopes

\frac{y - y_{0}}{x - x_{0}} = \frac{y_{1} - y_{0}}{x_{1} - x_{0}}

$\frac{y-y_0}{x-x_0} = \frac{y_1 - y_0}{x_1 - x_0}$

Interpolation remainder

Polynomial remainder

$x$	0	1	2
$f(x)$	0	1	1
$f'(x)$	0	1

P (x) = \frac{9}{4} x^{2} - \frac{3}{2} x^{3} + \frac{1}{4} x^{3}

$P(x) = \frac{9}{4}x^{2} - \frac{3}{2}x^{3} + \frac{1}{4}x^{3}$

Remainder:

R (x) = f (x) - P (x) R (0) = R (1) = R (2) = 0, R^{'} (0) = R^{'} (1) = 0

$R(x) = f(x) - P(x) \\ R(0)=R(1)=R(2) = 0,\ R'(0) = R'(1) = 0$

Assume:

R (x) = k (x) x^{2} (x - 1)^{2} (x - 2) φ (t) = R (t) - k (x) t^{2} (t - 2)^{2} (t - 2)

$R(x) = k(x)x^{2}(x-1)^{2}(x-2) \\ \varphi(t) = R(t)-k(x)t^{2}(t-2)^{2}(t-2)$

It follows that,

φ (t) = 0, t = x, 0, 1, 2 φ^{'} (t) = 0, t = 0, 1

$\varphi(t)=0,\ t=x,0,1,2 \\ \varphi '(t)=0,\ t=0, 1$

There are $5$ points that

φ^{'} (x) = 0

$\varphi'(x) = 0$

, as can be seen from Roller's Theorem.

So:

\exists ξ_{x} \in [min {x, 0, 1, 2}, max {x, 0, 1, 2}] φ^{(5)} (ξ_{x}) = 0

$\exists\ \xi_{x} \in \left[ \min{\{ x,0,1,2 \}}, \max{\{ x,0,1,2 \}}\right] \\ \varphi^{(5)}(\xi_{x}) = 0$

then

\begin{aligned} φ^{(5)} (t) & = R^{(5)} (t) - k (x) [t^{2} (t - 1)^{2} (t - 2)]^{(5)} \\ = f^{(5)} (t) - P^{(5)} (t) - k (x) \cdot 5! \\ = f^{(5)} (t) - k (x) \cdot 5! \end{aligned}

$\begin{align} \varphi^{(5)}(t) & = R^{(5)}(t) - k(x) [t^{2}(t-1)^{2}(t-2)]^{(5)} \\ & = f^{(5)}(t) - P^{(5)}(t)-k(x)\cdot5! \\ & = f^{(5)}(t) - k(x)\cdot 5! \end{align}$

substitute

φ^{(5)} (ξ_{x}) = f^{(5)} (ξ_{x}) - k (x) \cdot 5! = 0 ⇓ k (x) = \frac{f^{(5)} (ξ_{x})}{5!}

$\varphi^{(5)}(\xi_{x}) = f^{(5)}(\xi_{x})-k(x)\cdot 5!=0 \\ \Downarrow \\ k(x) = \frac{f^{(5)}(\xi_{x})}{5!}$

At the end,

R (x) = \frac{f^{(5)} (ξ_{x})}{5!} x^{2} (x - 1)^{2} (x - 2), ξ_{x} \in [min {x, 0, 1, 2}, max {x, 0, 1, 2}]

$R(x) =\frac{f^{(5)}(\xi_{x})}{5!}x^{2}(x-1)^{2}(x-2) , \ \xi_{x} \in \left[ \min{\{ x,0,1,2 \}}, \max{\{ x,0,1,2 \}}\right]$

Linear remainder

$f(x)$ is primal function, $I(x)$ is linear interpolation polynomial.

a = x_{0} < x_{1} < \dots < x_{n} = b f (x_{i}) = I (x_{i}) = y_{i}, i = 0, 1, \dots, n

$a=x_0 < x_1 < \dots < x_n = b \\ f(x_i) = I(x_i) = y_i,\ i = 0,1,\dots, n$

Theorem:

h = sup_{0 \leq k \leq n - 1} (x_{k + 1} - x_{k}) max_{a \leq x \leq b} | f (x) - I (x) | \leq \frac{h^{2}}{8} max_{a \leq x \leq b} | f^{(2)} (x) |

$h = \sup\limits_{0 \leq k \leq n-1}(x_{k+1}-x_{k}) \\ \max\limits_{a \leq x \leq b} |f(x) - I(x)| \leq \frac{h^{2}}{8}\max\limits_{a \leq x \leq b} |f^{(2)}(x)|$

Prove:

According to polynomial remainder, we can get:

\exists ξ \in [min {x, x_{k}, x_{k + 1}}, max {x, x_{k}, x_{k + 1}}] max_{x_{k} \leq x \leq x_{k + 1}} | f (x) - I (x) | = max_{x_{k} \leq x \leq x_{k + 1}} | \frac{f^{(2)} (ξ)}{2!} | \cdot | (x - x_{k}) (x - x_{k + 1}) |

$\exists \ \xi \in \left[ \min{\{ x,x_k,x_{k+1} \}},\ \max{\{ x,x_k,x_{k+1} \}}\right] \\ \max\limits_{x_{k} \leq x \leq x_{k+1}} | f(x) - I(x) | = \max\limits_{x_{k} \leq x \leq x_{k+1}} \Big| \frac{f^{(2)}(\xi)}{2!} \Big|\cdot |(x-x_{k})(x-x_{k+1})| \\$

\begin{aligned} max_{x_{k} \leq x \leq x_{k + 1}} | \frac{f^{(2)} (ξ)}{2!} | \cdot | (x - x_{k}) (x - x_{k + 1}) | \\ = max_{x_{k} \leq x \leq x_{k + 1}} | \frac{(x - x_{k}) (x - x_{k + 1})}{2} | \cdot max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (ξ) | \end{aligned}

$\begin{align} & \max\limits_{x_{k} \leq x \leq x_{k+1}} \Big| \frac{f^{(2)}(\xi)}{2!} \Big|\cdot |(x-x_{k})(x-x_{k+1})| \\ & = \max\limits_{x_{k} \leq x \leq x_{k+1}} \Big| \frac{(x-x_{k})(x-x_{k+1})}{2} \Big|\cdot \max\limits_{x_{k} \leq x \leq x_{k+1}} |f^{(2)}(\xi)| \end{align}$

On one hand,

{\frac{(x - x_{k}) (x - x_{k + 1})}{2}}^{'} = 0 ⇓ x = \frac{x_{k} + x_{k + 1}}{2} h_{k + 1} = x_{k + 1} - x_{k} max_{x_{k} \leq x \leq x_{k + 1}} | \frac{(x - x_{k}) (x - x_{k + 1})}{2} | \leq \frac{h_{k + 1}^{2}}{8}

$\left\{\frac{(x-x_{k})(x-x_{k+1})}{2} \right\}' = 0 \\ \Downarrow \\ x=\frac{x_k + x_{k+1}}{2}\\ h_{k+1} = x_{k+1}-x_{k} \\ \max\limits_{x_{k} \leq x \leq x_{k+1}} \Big| \frac{(x-x_{k})(x-x_{k+1})}{2} \Big| \leq \frac{h_{k+1}^{2}}{8}$

On the other hand,

max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (ξ) | = | f^{(2)} (ξ) | \leq max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (x) |

$\max\limits_{x_{k} \leq x \leq x_{k+1}} |f^{(2)}(\xi)| = |f^{(2)}(\xi)| \leq \max\limits_{x_{k} \leq x \leq x_{k+1}} | f^{(2)}(x) |$

It follows that,

max_{x_{k} \leq x \leq x_{k + 1}} | \frac{(x - x_{k}) (x - x_{k + 1})}{2} | \cdot max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (ξ) | \leq \frac{h_{k + 1}^{2}}{8} max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (x) |

$\max\limits_{x_{k} \leq x \leq x_{k+1}} \Big| \frac{(x-x_{k})(x-x_{k+1})}{2} \Big|\cdot \max\limits_{x_{k} \leq x \leq x_{k+1}} |f^{(2)}(\xi)|\ \leq\ \frac{h_{k+1}^{2}}{8}\max\limits_{x_{k} \leq x \leq x_{k+1}} | f^{(2)}(x) |$

max_{x_{k} \leq x \leq x_{k + 1}} | f (x) - I (x) | \leq \frac{h_{k + 1}^{2}}{8} max_{x_{k} \leq x \leq x_{k + 1}} | f^{(2)} (x) | \exists j, max_{a \leq x \leq b} | f (x) - I (x) | = max_{x_{j} \leq x \leq x_{j + 1}} | f (x) - I (x) | \leq \frac{h_{j + 1}^{2}}{8} max_{x_{j} \leq x \leq x_{j + 1}} | f^{(2)} (x) | \leq \frac{h_{j + 1}^{2}}{8} max_{a \leq x \leq b} | f^{(2)} (x) | ∵ h_{j + 1} \leq sup_{0 \leq k \leq n - 1} (x_{k + 1} - x_{k}) ⇓ h = sup_{0 \leq k \leq n - 1} (x_{k + 1} - x_{k}), max_{a \leq x \leq b} | f (x) - I (x) | \leq \frac{h^{2}}{8} max_{a \leq x \leq b} | f^{(2)} (x) |

$\max\limits_{x_{k} \leq x \leq x_{k+1}} | f(x) - I(x) | \leq \frac{h_{k+1}^{2}}{8}\max\limits_{x_{k} \leq x \leq x_{k+1}} | f^{(2)}(x) | \\ \exists\ j, \ \max\limits_{a \leq x \leq b} |f(x) - I(x)| = \max\limits_{x_{j} \leq x \leq x_{j+1}} | f(x) - I(x) | \leq \frac{h_{j+1}^{2}}{8}\max\limits_{x_{j} \leq x \leq x_{j+1}} | f^{(2)}(x) | \leq \frac{h_{j+1}^{2}}{8}\max\limits_{a \leq x \leq b} | f^{(2)}(x) | \\ \because h_{j+1} \leq \sup\limits_{0 \leq k \leq n-1}(x_{k+1}-x_{k}) \\ \Downarrow \\ h = \sup\limits_{0 \leq k \leq n-1}(x_{k+1}-x_{k}), \quad \max\limits_{a \leq x \leq b} |f(x) - I(x)| \leq \frac{h^{2}}{8}\max\limits_{a \leq x \leq b} |f^{(2)}(x)|$

Approximation theory

Theorem

minimax Approximation

‖ f (x) - y (x) ‖_{\infty} = max_{a \leq x \leq b} | f (x) - y (x) |

$\| f(x) - y(x) \|_{\infty} = \max\limits_{a \leq x \leq b}|f(x) - y(x) |$

Least-Squares Approximation

‖ f (y) - y (x) ‖_{2}^{2} = \int_{a}^{b} ρ (x) [f (x) - y (x)]^{2} d

$\|f(y) - y(x)\|_2^2 = \int_{a}^{b}\rho(x)[f(x) - y(x)]^{2}d$

Inner product space

weight function

\exists \int_{a}^{b} | x |^{n} ρ (x) d x, n = 0, 1, \dots g (x) \geq 0, \int_{a}^{b} g (x) ρ (x) = 0 i f g (x) \equiv 0, t h e n ρ (x) i s w e i g h t f u n c t i o n i n (a, b)

$\exists \ \int_{a}^{b}|x|^{n}\rho (x) dx, \ n=0,1,\dots \\ g(x) \geq 0, \ \int_{a}^{b}g(x) \rho (x) = 0 \\ if \ g(x) \equiv 0,\ then \ \rho (x) \ is\ weight\ function\ in\ (a, b)$

Inner product between $f(x)$ and $g(x)$

(f, g) = \int_{a}^{b} ρ (x) f (x) g (x) d x

$(f,g) = \int_{a}^{b} \rho(x) f(x) g(x) dx$

Cauchy-Schwarz

| (f, g) | \leq ‖ f ‖_{2} ‖ g ‖_{2}

$|(f,g)| \leq \|f\|_{2}\|g\|_{2}$

triangle inequality

‖ f + g ‖_{2} \leq ‖ f ‖_{2} + ‖ g ‖_{2}

$\|f+g\|_{2} \leq \|f\|_{2} + \|g\|_{2}$

Parallelogram theorem

‖ f + g ‖_{2}^{2} + ‖ f - g ‖_{2}^{2} = 2 (‖ f ‖_{2}^{2} + ‖ g ‖_{2}^{)}

$\|f+g\|_{2}^{2} + \|f-g\|_{2}^{2} = 2(\|f\|_{2}^{2}+\|g\|_{2}^)$

Linearly independent

{φ_{1} (x), φ_{1} (x), \dots, φ_{n} (x)} a_{1} φ_{1} (x) + a_{2} φ_{2} (x) + \dots + a_{n} φ_{n} (x) = 0 ⟺ a_{1} = a_{2} = \dots = a_{n} = 0

$\{\varphi_1(x),\varphi_1(x),\cdots,\varphi_n(x) \}\\ a_1\varphi_1(x)+a_2\varphi_2(x)+\cdots + a_n\varphi_n(x) = 0 \iff a_1=a_2=\cdots=a_n=0$