Interpolation and Approximation

\[ φ_i(x)=x^i \quad⇒\quad \mathsf A= \begin{pmatrix} 1 & x_0 & \dots & x_0^n \\ 1 & x_1 & \dots & x_1^n \\ \vdots & \vdots & & \vdots \\ 1 & x_n & \dots & x_n^n \end{pmatrix} \]

Code

pl = Plots.plot(size=(450,300), bottom_margin=4Plots.mm)
for d in 0:10
    p(x) = x^d
    Plots.plot!(p, 0, 1, )
end
Plots.plot!(xlims=(0, 1), xlabel="x",
    legend=false)

\[ φ_{i}(x) = \prod_{\substack{j = 0\\ j ≠ i}}^{n} \frac {x - x_j} {x_i - x_j} \quad⇒\quad \mathsf A=\mathsf I \]

Code

xs = LinRange(0, 1, 11)
pl = Plots.plot(size=(450,300), bottom_margin=4Plots.mm)
for d in eachindex(xs)
    p(x) = prod(x .- xs[1:end .!= d]) / prod(xs[d] .- xs[1:end .!= d])
    Plots.plot!(p, extrema(xs)...)
end
Plots.scatter!(xs, 0*xs .+ 1, )
Plots.plot!(xlims=(0, 1), xlabel="x",
    title="$(length(xs)) equally spaced nodes",
    legend=false)

\[ φ_{i}(x) = (x-x_0) (x-x_1) (x-x_2) \dots (x-x_{i-1}) \]

\(\quad⇒\quad \mathsf A\) lower triangular

Code

xs = LinRange(0, 1, 11)
pl = Plots.plot(size=(450,300), bottom_margin=4Plots.mm)
for d in eachindex(xs)
    p(x) = prod(x .- xs[1:d-1])
    Plots.plot!(p, extrema(xs)...)
end
Plots.scatter!(xs, zero(xs), )
Plots.plot!(xlims=(0, 1), xlabel="x",
    title="$(length(xs)) equally spaced nodes",
    legend=false)

• \(u\colon [a, b] \to {\mathbb{{R}}}\) is a function in \(\mathcal{C}^{n+1}([a, b])\)

• \(a=x_0< x_1< \dotsc < x_n=b\) are \(n+1\) distinct nodes

• \(\widehat u\) is a polynomial of degree at most \(n\), interpolating \(u\) at the points \(x_0, x_1, \dotsc, x_n\), i.e. \(\widehat u(x_i) = u(x_i)\) for all \(i ∈ \{0,\dotsc,n\}\)

Then \(\quad∀\, x ∈ [a,b],\quad ∃\, ξ=ξ(x) ∈ [a,b]\) \[ \fcolorbox{bleu_C}{bleu_light_C}{$ e_n(x) := u(x) - \widehat u(x) = \frac{u^{(n+1)}(\xi)}{(n+1)!} (x-x_0) \dotsc (x - x_n) $} \]

\[ \fcolorbox{bleu_C}{bleu_light_C}{$ e_n(x) := u(x) - \widehat u(x) = \frac{u^{(n+1)}(\xi)}{(n+1)!} (x-x_0) \dotsc (x - x_n) $} \]

• Increasing the number of nodes \(n+1\) changes \(u^{(n+1)}\) ⇒ difficult to control

• Idea: for given \(n\), choose nodes to minimize \(\sup_{x∈[a,b]} \lvert(x-x_0) \dotsc (x - x_n)\rvert\)

• For any monic polynomial \(p\) of degree \(n\), one shows that \(\sup_{x∈[-1,1]} \lvert p(x)\rvert ≥ \frac{1}{2^{n-1}}\)

• The bound \(\frac{1}{2^{n-1}}\) is achieved by \(\frac{T_{n}(x)}{2^{n-1}}\) where \(T_n(x)=\cos(n\arccos x)\) (Chebyshev polynomial)

• The zeros of \(T_n\) are therefore \(x_k=-\cos (\pi \frac{k + \frac{1}{2}}{n} ) \; (0 ≤ k < n)\) (minus sign for ordering)

• Hence \(x_k=-\cos (\pi \frac{k + \frac{1}{2}}{n+1} ) \; (0 ≤ k ≤ n)\) for \(n+1\) points

• In the case \([a,b]\), for \(n\) points \[ \fcolorbox{pistache_C}{pistache_light_C}{$ x_k=a + (b-a) \frac{1 - \cos (\pi \frac{k + \frac{1}{2}}{n} )}{2} \quad (0 ≤ k < n) $} \]

• Application to the Runge function \(u(x)=\frac{1}{1+25x^2}\)

\[ \fcolorbox{bleu_C}{bleu_light_C}{$ e_n(x) := u(x) - \widehat u(x) = \frac{u^{(n+1)}(\xi)}{(n+1)!} (x-x_0) \dotsc (x - x_n) $} \]

\[ \fcolorbox{bleu_C}{bleu_light_C}{$ \begin{align} &E_n := \sup_{x ∈ [a, b]} \bigl\lvert e_n(x) \bigr\rvert \leqslant\frac{C_{n+1}}{4(n+1)} h^{n+1}\\ &\text{with } C_{n+1} = \sup_{x ∈ [a, b]} \left\lvert u^{(n+1)}(x) \right\rvert \text{ and } h = \max_{i ∈ \{0, \dotsc, n-1\}} \lvert x_{i+1} - x_i\rvert \end{align} $} \]

Idea to control the bound:

• split the interval \([a,b]\) with \(n+1\) nodes, for example \(h=\frac{b-a}{n}\)

• interpolate with a polynomial of degree \(m\) on \([x_{i},x_{i+1}]\)

  #| echo: false
  #| eval: true
  #| code-fold: false
  #| code-line-numbers: false
  
  δ = 0.2
  pl = Plots.plot(size = (700,100), ylim =(-δ,δ))
  xs = LinRange(-1, 1, 37)
  Plots.plot!(xs, zero(xs),)
  Plots.scatter!(xs, zero(xs), markersize=6, markershape=:diamond,)
  xs = LinRange(-1, 1, 13)
  Plots.scatter!(xs, zero(xs), markersize=8,)
  Plots.plot!(axis = false, grid = false, legend = false, ticks = false)

  \[ \fcolorbox{bleu_C}{bleu_light_C}{$ \sup_{x ∈ [x_{i},x_{i+1}]} \bigl\lvert e_n(x) \bigr\rvert \leqslant\frac{C_{m+1}}{4(m+1)} \left(\frac{h}{m}\right)^{m+1} $} \]

• \(m\) is kept small, so the error is uniformly bounded by \(C h^{m+1}\)

• \(n+1\) distinct nodes \(a=x_0< x_1< \dotsc < x_n=b\)

• \(n+1\) values \(u_0, u_1, \dotsc, u_n\)

• a subspace \(\mathop{\mathrm{Vect}}(φ_0,φ_1,\dotsc,φ_m)\) of the vector space of continuous functions on \([a,b]\) (usually polynomials) but here \(\color{red}{m<n}\)

We look for an element of \(\mathop{\mathrm{Vect}}(φ_0,φ_1,\dotsc,φ_m)\), i.e. \[ \fcolorbox{bleu_C}{bleu_light_C}{$ \widehat u(x) = α_0 φ_0(x) + \dotsb + α_m φ_m(x) $} \] such that \[ \fcolorbox{bleu_C}{bleu_light_C}{$ \forall i \in \{0, \dotsc, n\}, \qquad \widehat u(x_i) \, {\color{red}{\approx}} \, u_i $} \] \[ \fcolorbox{bleu_C}{bleu_light_C}{$ \mathsf A \mathbf{\boldsymbol{\alpha }}:= \begin{pmatrix} \varphi_0(x_0) & \varphi_1(x_0) & \dots & \varphi_m(x_0) \\ \varphi_0(x_1) & \varphi_1(x_1) & \dots & \varphi_m(x_1) \\ \varphi_0(x_2) & \varphi_1(x_2) & \dots & \varphi_m(x_2) \\ \vdots & \vdots & & \vdots \\ \varphi_0(x_{n-2}) & \varphi_1(x_{n-2}) & \dots & \varphi_m(x_{n-2}) \\ \varphi_0(x_{n-1}) & \varphi_1(x_{n-1}) & \dots & \varphi_m(x_{n-1}) \\ \varphi_0(x_n) & \varphi_1(x_n) & \dots & \varphi_m(x_n) \end{pmatrix} \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \vdots \\ \alpha_m \end{pmatrix} {\color{red}{\approx}} \begin{pmatrix} u_0 \\ u_1 \\ u_2 \\ \vdots \\ u_{n-2} \\ u_{n-1} \\ u_n \end{pmatrix} =: \mathbf{\boldsymbol{b}} $} \]