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

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

===== =====

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

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

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


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

Jeżeli tablica ''P[i]'' zawiera wartości w węzłach ''xw[i]'' to 
po wykonaniu algorytmu
<code C>
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])

</code>
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:


| $ \, T \, (^oC) $             |  −250 |  −200 |  −100 |  0 |  100 |  300 |
| $ \, c_p \, (J/kg \cdot K)$ |   16.3 |  318 |  699 |  870 |  941 |  1040 |

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.