~~NOCACHE~~
~~REVEAL theme=simple&size=1024x800~~

====== Lab. 9 Interpolacja ======

===== Definicja ====

{{ zajecia:mn1_2021_2:interpolation_aproximation.png?500  |}}

**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 =====


<code C>
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;
}
</code>

Przykładowy program: {{zajecia:mn1_2021_2:lagrange.c|}}

===== Zjawisko Rungego =====

{{ zajecia:mn1_2021_2:interpolation_error.png?600  |}}

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

===== =====

{{ zajecia:mn1_2021_2:newton_coeff_tab.png?600  |}}

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) ====

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


<code C>
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;
}
</code>

===== Metoda Neville'a =====

  * Metoda Newtona ma 2 kroki: 
    - wyznaczenie współczynników $a_i$, 
    - 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}$$

{{ zajecia:mn1_2021_2:neville_tab.png?600  |}}


===== Algorytm Neville'a =====

  - Niech $P_0, P_1, \ldots, P_n$ zawiera wartości funkcji $y_i$ w węzłach $x_i$
  - Dla każdego $k = 1, \ldots, n$ wykonaj
  - 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}} $$ 
  - Zwróć wynik $P_0$  


=====  Zadanie 8 =====

Treść zadania znajduje się w Moodle pod adresem [[https://moodle.umk.pl/WFAIIS/mod/assign/view.php?id=4796|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.