Algorytm Neville’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Algorytm Neville'a)
Przejdź do nawigacji Przejdź do wyszukiwania

Algorytm Neville’a – algorytm zaproponowany przez angielskiego matematyka Erica Harolda Neville’a. Jest używany do wyznaczania wartości wielomianu interpolacyjnego (Lagrange’a i Newtona) w danym punkcie Ideą jest wyznaczenie rozwiązania w krokach od pojedynczych węzłów do całego ich zbioru.

Biorąc pod uwagę zbiór danych punktów węzłowych wielomian jest stopnia nie wyższego niż a jego wartości w punktach węzłowych są takie same jak wartości interpolowanej funkcji:

  dla

Definiujemy wielomiany interpolacyjne i ich wartości w ustalonym punkcie

  • – wartość, w punkcie wielomianu stopnia zerowego przechodzącego przez punkt :
  dla
  • – wartość, w punkcie wielomianu stopnia pierwszego przechodzącego przez punkty oraz :
  dla
  • – wartość, w punkcie wielomianu stopnia n-tego przechodzącego przez punktów :
  dla

Wielomiany powyższego typu spełniają następującą własność rekurencyjną:

gdzie: odpowiada stopniowi wielomianu, oraz

Algorytm Neville’a polega na tym, że za pomocą powyższych wzorów konstruujemy tablicę symetryczną, która zawiera wartości wielomianu interpolacyjnego w ustalonym punkcie dla :

Kolejne elementy są obliczane rekurencyjnie na podstawie elementów poprzednich.

W praktyce algorytm Neville’a przedstawiamy w nieco innej wersji. Stosując oznaczenia:

Tablica przyjmuje postać:

Ułatwia to komputerowe zaprogramowanie powyższej tablicy (jako tablicy dwuwymiarowej).

Otrzymujemy również wzór rekurencyjny w prostszej postaci:

gdzie:   dla

Pseudokod:

       for i := 0 to n do
           t[i] = f[i]
       for i := i - 1 downto 0 do
           t[j]= t[j + 1] + (t[j + 1] - t[j]) * (x - x[i]) / (x[i] - x[j])

Szukaną wartość wielomianu interpolacyjnego otrzymujemy jako t[0].

Przykład[edytuj | edytuj kod]

Dane mamy:

      

      

Wyliczymy wartość wielomianu interpolacyjnego w punkcie x=2. Korzystamy ze wzorów i konstruujemy tablicę:

Zatem dla x=2 wartość wielomianu wynosi 3.

Uogólnienie algorytmu Neville’a[edytuj | edytuj kod]

Mając zadane węzły do interpolacji można również użyć funkcji wymiernych:

spełniających warunki:   dla

W przypadku interpolacji funkcjami wymiernymi można wyprowadzić uogólniony wzór Neville’a. Algorytm wygląda wówczas następująco:

Bibliografia[edytuj | edytuj kod]