Algorytm Neville'a

Algorytm Neville’a – algorytm zaproponowany przez angielskiego matematyka . 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].