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.