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 (dla algorytmu wprzód)

$$\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}$$

Uwaga: na wykładzie podana jest metoda Newtona różniąca się definicją różnic

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$$

Algorytm (w przód)

1. Niech $a_0, a_1, \ldots, a_n$ zawiera wartości funkcji $y_i$ w węzłach $x_i$
2. Dla każdego $i=1, \ldots, n$ wykonaj
3. Dla każdego $k = i, \ldots, n$ wykonaj
   $$a_i \leftarrow \frac{a_k - a_{i-1}}{x_k-x_{i-1}}$$
4. $y=a_n$
5. Dla każdego $i=n-1, \ldots, 0$ wykonaj
   $$y \leftarrow y \cdot (x - x_i) + a_i$$
6. Zwróć wynik $y$

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 wartości $P_n(x)$ bez konieczności zapamiętywania wszystkich 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

1. Niech $P_0, P_1, \ldots, P_n$ zawiera wartości funkcji $y_i$ w węzłach $x_i$
2. Dla każdego $k = 1, \ldots, n$ wykonaj
3. Dla każdego $i = 0, \ldots, n-k$ wykonaj
   $$P_i \leftarrow \frac{(x - x_{i+k}) \cdot P_i - (x - x_{i}) \cdot P_{i+1} }{x_i - x_{i+k}} $$
4. Zwróć wynik $P_0$

Zadanie 8

Treść zadania znajduje się w Moodle pod adresem Zadanie 8

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.