MATH566

MATH566 Lesson 5: Polynomial interpolation

Overview

Function approximation criteria: interpolation, least squares, min-max
Bases for polynomial interpolation
Polynomial interpolant forms
- Lagrange
- Barycentric Lagrange

Function approximation criteria

Consider $f : ℝ \to ℝ$ , “difficult” to compute, and known through a sample

𝒟 = {(x_{i}, y_{i}), i = 0, 1, 2, \dots, m}, y_{i} = f (x_{i}), i \neq j \Rightarrow x_{i} \neq x_{j} .

Introduce approximant $g : ℝ \to ℝ$ , “easy” to compute, $z_{i} = g (x_{i})$

Introduce vectors: $𝒙 = {[\begin{array}{lll} x_{0} & \dots & x_{m} \end{array}]}^{T}$ , $𝒚 = {[\begin{array}{lll} y_{0} & \dots & y_{m} \end{array}]}^{T}$ , $𝒛 = {[\begin{array}{lll} z_{0} & \dots & z_{m} \end{array}]}^{T}$

Assess accuracy of approximation through norm of error vector $δ = || 𝒛 - 𝒚 ||$

Various types of norms and error bounds can be considered:
- $δ = 0 \Rightarrow 𝒛 = 𝒚 \Rightarrow g (x_{i}) = y_{i}, i = 0, \dots, m$ is known as interpolation
- Assume $g$ is defined by $n + 1$ parameters, $𝒄 = {[\begin{array}{lll} c_{0} & \dots & c_{n} \end{array}]}^{T}$ , $z_{i} = g (x_{i}, 𝒄)$ . The approximant obtained by minimization of the two-norm is known as the least squares approximant
  ${min}_{𝒄} {|| 𝒛 - 𝒚 ||}_{2} \Leftrightarrow {min}_{𝒄} Σ_{i = 0}^{m} {(z_{i} - y_{i})}^{2}$
- The approximant obtained by the minimization of the inf-norm is known as the minmax approximant
  ${min}_{𝒄} {|| 𝒛 - 𝒚 ||}_{\infty} \Leftrightarrow {min}_{𝒄} {max}_{0 ⩽ i ⩽ m} | z_{i} - y_{i} |, i \in ℕ .$

Linear combination approach to approximation

Consider a set of linearly independent functions ${g_{0} (t), g_{1} (t), \dots, g_{n} (t)}$
$g (t) = c_{0} g_{0} (t) + c_{1} g_{1} (t) + \dots + c_{n} g_{n} (t) = 0 \Rightarrow c_{0} = c_{1} = \dots = c_{n} = 0_{}$
Construct approximation of $f (t)$ by
$f (t) ≅ g (t) = c_{0} g_{0} (t) + c_{1} g_{1} (t) + \dots + c_{n} g_{n} (t) = \sum_{j = 0}^{n} c_{j} g_{j} (t)$
Even though $f (t), g_{0} (t), \dots, g_{n} (t)$ might be nonlinear the above expresses $f$ as a linear combination of ${g_{0} (t), g_{1} (t), \dots, g_{n} (t)}$
Various choices can be made for the basis functions ${g_{0} (t), g_{1} (t), \dots, g_{n} (t)}$

Lagrange form of polynomial interpolant

The interpolation conditions $g (x_{i}) = y_{i}$ can be achieved if
- $n = m$
- $g_{i} (x_{j}) = δ_{i j} = {\begin{cases} 1 & if i = j \\ 0 & if i \neq j \end{cases} .$
In this case the linear combination coefficients $a_{i}$ are simply the function values
$g (x_{j}) = \sum_{i = 0}^{m} c_{i} g_{i} (x_{j}) = \sum_{i = 0}^{m} c_{i} δ_{i j} = c_{i} = y_{i}, i = 0, 1, \dots, m$
Construct polynomial of degree $m$ to satisfy above conditions
$l_{i} (t) = \prod_{j = 0, j \neq i}^{m} (t - x_{j}) \equiv \prod_{j = 0}^{m}^{'} (t - x_{j}), ℓ_{i} (t) = \frac{\prod_{j = 0}^{m}^{'} (t - x_{j})}{\prod_{j = 0}^{m}^{'} (x_{i} - x_{j})}$ $l_{i} (x_{i}) = \prod_{j = 0, j \neq i}^{m} (x_{i} - x_{j}), ℓ_{i} (t) = \frac{l_{i} (t)}{l_{i} (x_{i})}, ℓ_{i} (x_{j}) = δ_{i j}$
$ℓ_{i} (t)$ are the Lagrange basis polynomials, $l_{i} (t)$ are the unnormalized version

Shape of the Lagrange basis

Figure 1. Lagrange basis for $n = 6$ equidistant subintervals over interval $[- π, π]$

Note that at each $x_{j} = - π + 2 π j / n$ all polynomials except one evaluate as 0. The remaining polynomial evaluates as 1.
The polynomials can reach values greater or less than 1

Evaluation of the Lagrange polynomial interpolant

Algorithm (Lagrange evaluation)

Input: $𝒙, 𝒚 \in ℝ^{n + 1}, t \in ℝ$

Output: $p (t) = \sum_{i = 0}^{n} y_{i} \prod_{j = 0}^{n}^{'} (t - x_{j}) / (x_{i} - x_{j})$

$p = 0$

for $i = 0$ to n

$w = 1$

for $j = 0$ to $n$

if $j \neq i$ then $w = w (t - x_{j}) / (x_{i} - x_{j})$

end

$p = p + w \cdot y_{i}$

end

return $p$

Operation count: for each $i$ from 0 to $n$ , for each $j$ from 0 to $n$ skipping one index, carry out 2 FLOPS (1 FLOP = 1 addition and 1 multiplication)
$2 n (n - 1) = 𝒪 (2 n^{2}) FLOPs$

Barycentric form of Lagrange interpolant

The $𝒪 (2 n^{2})$ operation count for evaluating the Lagrange interpolant can be reduced to $𝒪 (2 n)$ by using a different form, the barycentric form.

Let $w (t) = \prod_{k = 0}^{n} (t - x_{k})$ and rewrite $ℓ_{i} (t)$ as

ℓ_{i} (t) = \prod_{j = 0}^{n}^{'} \frac{t - x_{j}}{x_{i} - x_{j}} = w (t) \frac{w_{i}}{t - x_{i}}, w_{i} = \prod_{j = 0}^{n}^{'} \frac{1}{x_{i} - x_{j}} .

The interpolating polynomial is now

p (t) = \sum_{i = 0}^{n} y_{i} ℓ_{i} (t) = w (t) \sum_{i = 0}^{n} y_{i} \frac{w_{i}}{t - x_{i}} .

Interpolation of the function $g (t) = 1$ gives $1 = w (t) \sum_{i = 0}^{n} \frac{w_{i}}{t - x_{i}}$ .

Take ratio to obtain barycentric form

p (t) =,

Evaluation of barycentric Lagrange polynomial

$\circ$

Algorithm (Barycentric Lagrange evaluation)

Input: $𝒙, 𝒚 \in ℝ^{n + 1}, t \in ℝ$

Output: $p (t) = (\sum_{i = 0}^{n} y_{i}) / (\sum_{i = 0}^{n})$

for $i = 0$ to $n$

$w_{i} = 1$

for $j = 0$ to $n$

if $j \neq i$ $w_{i} = w_{i} / (x_{i} - x_{j})$

end

$q = r = 0$

for $i = 0$ to n

$s = w_{i} / (t - x_{i})$ ; $q = q + y_{i} s$ ; $r = r + s$

end

$p = q / r$

return $p$

∴

function BaryLagrange(t,x,y)
  n=length(x)-1; w=ones(size(x));
  for i=1:n+1
    w[i]=1
    for j=1:n+1
      if (i!=j) w[i]=w[i]/(x[i]-x[j]); end
    end
  end
  q=r=0
  for i=1:n+1
    d=t-x[i]
    if d≈0 return y[i]; end
    s=w[i]/d; q=q+y[i]*s; r=r+s
  end
  return q/r
end;

∴	p2(t)=3t^2-2t+1;

∴	x=[-2 0 2]; y=p2.(x);

∴	t=-3:3; [p2.(t) BaryLagrange.(t,Ref(x),Ref(y))]

$[\begin{array}{cc} 34 & 33.99999999999999 \\ 17 & 17 \\ 6 & 6.0 \\ 1 & 1 \\ 2 & 2.0 \\ 9 & 9 \\ 22 & 21.999999999999996 \end{array}]$ (1)

∴

Precompute $w_{i}$ , $𝒪 (n^{2})$ FLOPs. Evaluation for given $t$ costs only $𝒪 (2 n)$ FLOPs