Algorytm Neville’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Algorytm Neville'a)
Skocz do: nawigacja, szukaj

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 x. 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 i= 1,2,…,n, wielomian jest stopnia nie wyższego niż n, a jego wartości w punktach węzłowych są takie same jak wartości interpolowanej funkcji:

 ; dla i = 1,…,n + 1

Definiujemy wielomiany interpolacyjne i ich wartości w ustalonym punkcie x.

-wartość, w punkcie x, wielomianu stopnia zerowego przechodzącego przez punkt :

dla i =0,…,n

-wartość, w punkcie x, wielomianu stopnia pierwszego przechodzącego przez punkty oraz :

dla i =0,…,n-1

-wartość, w punkcie x, wielomianu stopnia n-tego przechodzącego przez (n+1) punktów dla i=0,…,n

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

gdzie: k odpowiada stopniowi wielomianu, k =1,…,n oraz i =0,…,n

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 x, dla n=3:

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: , i =0,1,…,n

Pseudokod:

  for i =0 to n do

  t[i]= f[i]

  for j = 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]

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]

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

Spełniających warunki:    i=0,1,…,u+v

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

       

Bibliografia[edytuj]