---
tag: 58AM5FK67J
kind: concept
name: Neville's algorithm
msc: [65D05, 41A05]
sources:
  - url: https://en.wikipedia.org/wiki/Neville%27s_algorithm
same_as:
  wikidata: Q7884545
  wikipedia: Neville's algorithm
---

## Summary

Neville's algorithm computes the value at one point $x$ of the [[interpolation polynomial|SS1YMS2NPC]] through given data, without computing its coefficients.
It builds a triangular table.
Each entry is the value at $x$ of the interpolation polynomial through a block of consecutive nodes.
It is computed from two entries for shorter blocks.
It costs $O(n^2)$ operations for $n + 1$ nodes.
It is often used for extrapolation, for example to the limit $h \to 0$ in Richardson-type methods.

## Explanations

### L1 human

Through each single point there is a constant, through each pair a line, through each triple a parabola, and so on.
Neville's idea is to get the value of the curve through a block of points by blending two shorter curves.
One goes through the block without its last point, the other through the block without its first point.
The blend is a weighted average whose weights depend on how far $x$ is from the two end nodes.
For the points $(0, 1)$ and $(1, 3)$, the line has value $1 \cdot (1 - x) + 3 \cdot x$, and at $x = 2$ this gives $5$.
The [[definition|KVZ7D84541]] gives the recursion.