algorytm.org

Interpolacja odwrotna

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Interpolacja odwrotna
Ocena użytkowników:***** / 6
SłabyŚwietny 
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:
x1x2...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)
x1x2...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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał ŁadanowskiJava
.java
.java
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 02 października 2012 17:30
Komentarze
photo
-1 # Juzef 2013-01-07 17:43
dobre to
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz