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

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

Interpolacja wielomianowa, dla węzłów budujemy wielomian stopnia

Dla dwóch punktów otrzymujemy równanie prostej

Dla przybliżenie parabolą, itd.

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

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

Wielomian interpolacyjny

Wartość może być wyznaczona efektywnie w sposób rekurencyjny

Wprowadźmy oznaczenia (dla algorytmu wprzód)

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

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

Niech zawiera wartości funkcji w węzłach

Dla każdego wykonaj

Dla każdego wykonaj

Dla każdego wykonaj

Zwróć wynik

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 Newtona ma 2 kroki:

wyznaczenie współczynników ,

wyznaczenie wartości wielomianu .

Umożliwia szybkie wyznaczenie kolejnych wartości dla tych samych węzłów.

Metoda Neville'a: modyfikacja metody Newtona, przyśpiesza wyznaczenie wartości bez konieczności zapamiętywania wszystkich współczynników

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

gdzie

Niech zawiera wartości funkcji w węzłach

Dla każdego wykonaj

Dla każdego wykonaj

Zwróć wynik

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

Ćw. 1

Oblicz analitycznie wartość za pomocą wzoru interpolacyjnego Lagrange'a dla funkcji i węzłów interpolacyjnych . Napisz program, który korzystając z tych węzłów pozwoli wyznaczyć wartość dla 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.