Wpisany przez Michał Ładanowski,
02 marca 2011 19:53
Interpolacja odwrotna jest algorytmem poszukiwania rozwiązań nieliniowych równań algebraicznych. Idea algorytmu jest prosta. Skroro znamy funkcję to stwórzmy tabelę zawierającą kilka węzłów oraz odpowiadające im wartości w n miejscach:
Jeśli stabelaryzowane wartości są ściśle monotoniczne oznacza to dla nas, że funkcja jest odwracalna, czyli możemy zamienić miejscami wartości oraz węzły.
Interpolujmy więc funkcję odwrotną, znajdźmy jej wartość w 0, a wartość ta będzie szukanym przez nas miejscem zerowym.
Możliwa implementacja takiego algorytmu:
x - miejsce zerowe
wybieramy 3 początkowe węzły: a, b, c
while (|f(x)| > zadana dokładność)
x = lagrangeInterpolation(f(a), f(b), f(c), a, b, c, 0)
a = b
b = c
c = x
end
lagrangeInterpolation - interpolacja Lagrange’a, pobiera węzły i odpowiadające im wartości. W algorytmie podajemy w odwrotnej kolejności czyli interpolujemy funkcje odwrotną.
Uwagi końcowe:
Poszukajmy miejsca zerowego dla funkcji: x3-1
Początkowe 3 punkty a, b, c niech będą wynosić odpowiednio -2, -1, 4.
Wartość funkcji w tych punktach to: -9, -2, 63. Jak widać wartości są monotoniczne, zatem możemy użyć algorytmu interpolacji odwrotnej.
Obliczamy wartość funkcji odwrotnej w punkcie 0, używając interpolacji Largrange dla punktów a, b, c i przypisujemy wynik do zmiennej x.
x = -0.7307692307692308
Wykonujemy podstawienia a = b; b = c; c = x.
a = -1.0, b = 4.0, c = -0.7307692307692308.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = -1.3902480655439238.
Nie jest to dla nas satysfakcjonujące przybliżenie miejsca zerowego, więc obliczamy nową wartość x dla nowych punktów.
x = -0.1326619792331245.
Wykonujemy podstawienia a = b; b = c; c = x.
a = 4.0, b = -0.7307692307692308, c = -0.1326619792331245.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = -1.0023347448023001.
Nadal nie jest to dla nas satysfakcjonujące przybliżenie miejsca zerowego, więc obliczamy nową wartość x dla nowych punktów.
x = 1.3808253091589175.
Wykonujemy podstawienia a = b; b = c; c = x.
a = -0.7307692307692308, b = -0.1326619792331245, c = 1.3808253091589175.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = 1.6327899767486351.
...
Obliczenia kontynuujemy aż obliczone miejsce zerowe uzyskamy z zadaną dokładnością.
x1 | x2 | ... | xn |
f(x1) | f(x2) | ... | f(xn) |
Jeśli stabelaryzowane wartości są ściśle monotoniczne oznacza to dla nas, że funkcja jest odwracalna, czyli możemy zamienić miejscami wartości oraz węzły.
f(x1) | f(x2) | ... | f(xn) |
x1 | x2 | ... | xn |
Interpolujmy więc funkcję odwrotną, znajdźmy jej wartość w 0, a wartość ta będzie szukanym przez nas miejscem zerowym.
Możliwa implementacja takiego algorytmu:
x - miejsce zerowe
wybieramy 3 początkowe węzły: a, b, c
while (|f(x)| > zadana dokładność)
x = lagrangeInterpolation(f(a), f(b), f(c), a, b, c, 0)
a = b
b = c
c = x
end
lagrangeInterpolation - interpolacja Lagrange’a, pobiera węzły i odpowiadające im wartości. W algorytmie podajemy w odwrotnej kolejności czyli interpolujemy funkcje odwrotną.
Uwagi końcowe:
- W praktyce stosuje się dla niewielkiej ilości węzłów,
- jeden krok interpolacji odwrotnej opartej o 2 punkty, jest równy jednemu krokowi metody siecznych.
Przykład:
Poszukajmy miejsca zerowego dla funkcji: x3-1
Początkowe 3 punkty a, b, c niech będą wynosić odpowiednio -2, -1, 4.
Wartość funkcji w tych punktach to: -9, -2, 63. Jak widać wartości są monotoniczne, zatem możemy użyć algorytmu interpolacji odwrotnej.
Obliczamy wartość funkcji odwrotnej w punkcie 0, używając interpolacji Largrange dla punktów a, b, c i przypisujemy wynik do zmiennej x.
x = -0.7307692307692308
Wykonujemy podstawienia a = b; b = c; c = x.
a = -1.0, b = 4.0, c = -0.7307692307692308.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = -1.3902480655439238.
Nie jest to dla nas satysfakcjonujące przybliżenie miejsca zerowego, więc obliczamy nową wartość x dla nowych punktów.
x = -0.1326619792331245.
Wykonujemy podstawienia a = b; b = c; c = x.
a = 4.0, b = -0.7307692307692308, c = -0.1326619792331245.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = -1.0023347448023001.
Nadal nie jest to dla nas satysfakcjonujące przybliżenie miejsca zerowego, więc obliczamy nową wartość x dla nowych punktów.
x = 1.3808253091589175.
Wykonujemy podstawienia a = b; b = c; c = x.
a = -0.7307692307692308, b = -0.1326619792331245, c = 1.3808253091589175.
Wartość funkcji w obliczonym punkcie wynosi: f(x) = 1.6327899767486351.
...
Obliczenia kontynuujemy aż obliczone miejsce zerowe uzyskamy z zadaną dokładnością.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Michał Ładanowski | Java | .java | .java | ***** / 1 |
Poprawiony: 02 października 2012 17:30