Lab. 9 Interpolacja

Definicja

Interpolacja – poszukuje funkcji interpolacyjnej, która przyjmuje określone wartości $f(x_i)$ w ustalonych punktach (węzłach) $x_i$

Aproksymacja punktowa, regresja, dopasowanie krzywej - przybliżenie zbioru punktów funkcją ciągłą.

Wielomian Lagrange'a

Interpolacja wielomianowa, dla $n+1$ węzłów budujemy wielomian stopnia $n$

$$W_n(x) =\sum_{j=0}^{n} y_{j} \prod_{k=0 \atop k \neq j}^{n} \frac{\left(x-x_{k}\right)}{\left(x_{j}-x_{k}\right)}$$

Dla dwóch punktów $n=1$ otrzymujemy równanie prostej $$W_{1}(x)=\frac{x-x_{0}}{x_{1}-x_{0}} y_{1}+\frac{x-x_{1}}{x_{0}-x_{1}} y_{0}$$

Dla $n=2$ przybliżenie parabolą, itd.

Przykład

double lagrange(double x, double xw[], double yw[], int n)
{
   double y = 0.0, l, m, xi;
   int i, j;

   for (i = 0; i <= n; i++)
   {
      l = 1.0;
      m = 1.0;
      xi = xw[i];
      for (j = 0; j <= n; j++)
      {
         if (i == j) continue;
         l *= x - xw[j];
         m *= xi - xw[j];
      }
      y += yw[i] * l / m;
   }
   return y;
}

Przykładowy program: lagrange.c

Zjawisko Rungego

Pogarszanie się przybliżenia na krańcach przedziału dla wielomianów wysokiego stopnia

Metoda Newtona

Wielomian interpolacyjny

$$P_{n}(x)=a_{0}+\left(x-x_{0}\right) a_{1}+\left(x-x_{0}\right)\left(x-x_{1}\right) a_{2}+\cdots \\ +\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots \left(x-x_{n-1}\right) a_{n}$$

Wartość $P_k(x)$ może być wyznaczona efektywnie w sposób rekurencyjny

$$P_{0}(x)=a_{n}, \quad P_{k}(x)=a_{n-k}+\left(x-x_{n-k}\right) P_{k-1}(x), \quad k=1,2, \ldots, n$$

Wprowadźmy oznaczenia

$$\begin{aligned} \nabla y_{i}=& \frac{y_{i}-y_{0}}{x_{i}-x_{0}}, \quad i=1,2, \ldots, n \\ \nabla^{2} y_{i}=& \frac{\nabla y_{i}-\nabla y_{1}}{x_{i}-x_{1}}, \quad i=2,3, \ldots, n \\ \nabla^{3} y_{i}=& \frac{\nabla^{2} y_{i}-\nabla^{2} y_{2}}{x_{i}-x_{2}}, \quad i=3,4, \ldots n \\ & \vdots \\ \nabla^{n} y_{n}=& \frac{\nabla^{n-1} y_{n}-\nabla^{n-1} y_{n-1}}{x_{n}-x_{n-1}} \end{aligned}$$

Rozwiązanie przechodzące przez węzły daje

$$a_{0}=y_{0} \quad a_{1}=\nabla y_{1} \quad a_{2}=\nabla^{2} y_{2} \quad \cdots \quad a_{n}=\nabla^{n} y_{n}$$

$$P_{0}(x)=a_{n}, \quad P_{k}(x)=a_{n-k}+\left(x-x_{n-k}\right) P_{k-1}(x), \quad k=1,2, \ldots, n$$

Przykład

double newton(double x, double xw[], double yw[], int n)
{
   double y, a[MAX];
   int i, k;
   
   for (i = 0; i <= n; i++) a[i] = yw[i];

   for (i = 1; i <= n; i++)
      for (k = i; k <= n; k++)
         a[k] = (a[k] - a[i-1]) / (xw[k] - xw[i-1]);

   y = a[n];
   for (k = n-1; k >= 0; k--)
         y = y *(x-xw[k]) + a[k];

   return y;
}

Metoda Neville'a

Metoda Newtona ma 2 kroki:

1. wyznaczenie współczynników $a_i$,
2. wyznaczenie wartości wielomianu $P_n(x)$.

Umożliwia szybkie wyznaczenie kolejnych wartości $P_n(x)$ dla tych samych węzłów.

Metoda Neville'a: modyfikacja metody Newtona, przyśpiesza wyznaczenie pojedynczej wartości $P_n(x)$ bez zapamiętywania współczynników $a_i$

Zależność rekurencyjna na wielomian stopnia $k$ przechodzący przez $k+1$ punktów

$$\begin{array}{l} P_{k}\left[x_{i}, x_{i+1}, \ldots, x_{i+k}\right] = \frac{\left(x-x_{i+k}\right) \cdot P_{k-1}\left[x_{i,} x_{i+1}, \ldots, x_{i+k-1}\right]-\left(x - x_{i}\right) \cdot P_{k-1}\left[x_{i+1}, x_{i+2}, \ldots, x_{i+k}\right]}{x_{i}-x_{i+k}} \end{array}$$

gdzie $$P_{0}\left[x_{i}\right]=y_{i}$$

Algorytm Neville'a

Jeżeli tablica P[i] zawiera wartości w węzłach xw[i] to po wykonaniu algorytmu

for k in 1..n-1
   for i in 0..n-k
      P[i] = ((x-xw[i+k])*P[i] - (x-xw[i])*P[i+1]) / (xw[i]-xw[i+k])

wartość interpolowana dla puntu x zawarta będzie w P[0]

Zadanie

Ciepło właściwe $c_p$ aluminium zależy od temperatury $T$ w nastepujący sosób:

Napisz program, który za pomocą metody Neville'a wyznaczy wartość ciepła właściwego $c_p$ dla dowolnej (podanej przez użytkownika) wartości temperatury $T$ w zakresie od $-250^oC$ do $300^oC$.

Dodatkowe ćwiczenia

Ćw. 1

Oblicz analitycznie wartość $\sqrt{117}$ za pomocą wzoru interpolacyjnego Lagrange'a dla funkcji $y = \sqrt{x}$ i węzłów interpolacyjnych $x_0 = 100, x_1 = 121, x_2 = 144$. Napisz program, który korzystając z tych węzłów pozwoli wyznaczyć wartość $\sqrt{x}$ dla $x$ z zakresu od 100 do 144. Porównaj wynik z wartością dokładną wyznaczoną za pomocą funkcji sqrt() i wyznacz błąd względny.