Algorytm Neville’a

Algorytm Neville’a

Algorytm Neville’a to metoda stworzona przez angielskiego matematyka Erica Harolda Neville’a, która służy do obliczania wartości wielomianu interpolacyjnego, takiego jak wielomiany Lagrange’a i Newtona, w określonym punkcie x.

Głównym celem algorytmu jest wyznaczenie rozwiązania, przechodząc krok po kroku od pojedynczych węzłów do pełnego zbioru danych.

Rozważając zbiór punktów węzłowych (xi, yi), gdzie i = 1, 2, …, n, wielomian P jest stopnia nieprzekraczającego n, a jego wartości w punktach węzłowych są zgodne z wartościami funkcji, którą chcemy interpolować:

P(xi) = f(xi) = yi, dla i = 1, …, n + 1.

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

  • pi – wartość wielomianu stopnia zerowego w punkcie x, przechodzącego przez punkt (xi, yi): pi = yi = Pi(x), dla i = 0, …, n.
  • pi(i+1) – wartość wielomianu stopnia pierwszego w punkcie x, przechodzącego przez punkty (xi, yi) oraz (xi+1, yi+1): pi(i+1) = Pi(i+1)(x), dla i = 0, …, n – 1.
  • p0…n – wartość wielomianu stopnia n w punkcie x, przechodzącego przez (n + 1) punktów (xi, yi): p0…n = P0…n(x), dla i = 0, …, n.

Wielomiany te spełniają następującą własność rekurencyjną:

pi(i+1…i+k) = (x – xi+k) pi(i+1…i+k-1) + (xi – x) p(i+1)(i+2…i+k), gdzie k odpowiada stopniowi wielomianu, k = 1, …, n, a i = 0, …, n.

Algorytm Neville’a polega na budowie symetrycznej tablicy, która zawiera wartości wielomianu interpolacyjnego w ustalonym punkcie x dla n = 3. Kolejne elementy są obliczane rekurencyjnie na podstawie wcześniejszych wartości.

W praktyce algorytm ten przedstawiamy w inny sposób. Używając oznaczeń:

t(i+k), k = pi(i+1…(i+k)), otrzymujemy tablicę, co ułatwia implementację w postaci tablicy dwuwymiarowej.

Otrzymujemy również uproszczony wzór rekurencyjny:

tik = (x – xi-k) ti,k-1 – (x – xi) ti-1,k-1 / (xi – xi-k), dla 1 ≤ k ≤ i, i = 0, 1, …, n.

Pseudokod algorytmu jest następujący:

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

Wartość wielomianu interpolacyjnego uzyskujemy jako t[0].

Przykład

Rozważmy dane:

  • i = 0, 1, 2, 3
  • x0 = 0, x1 = 1, x2 = 3, x3 = 4
  • f(x0) = 1, f(x1) = 3, f(x2) = 2, f(x3) = 1

Obliczamy wartość wielomianu interpolacyjnego w punkcie x=2, konstruując tablicę. Dla x=2 wartość wielomianu wynosi 3.

Uogólnienie algorytmu Neville’a

W przypadku węzłów (xi, fi) można również zastosować funkcje wymierne do interpolacji:

Zu,v = Pu,v / Qu,v = (a0 + a1x + … + auxu) / (b0 + b1x + … + bvxv), które spełniają warunki: Zu,v(xi) = fi, dla i = 0, 1, …, u + v.

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

Ti0 = fi, Ti,k-1 = 0, Tik = Ti,k-1 + (Ti,k-1 – Ti-1,k-1) / [(x – xi-k)(1 – (Ti,k-1 – Ti-1,k-1)/(Ti,k-1 – Ti-1,k-2))].

Bibliografia

J. Stoer, R. Bulirsch, Wstęp do analizy numerycznej, PWN, 1987.

J.N. Lyness, C.B. Moler, Van Der Monde Systems and Numerical Differentiation, „Numerishe Mathematik” 8 (1966), s. 458–464.

Przeczytaj u przyjaciół: