---
tag: KVZ7D84541
kind: definition
name: Neville's algorithm
msc: [65D05, 41A05]
defines: 58AM5FK67J
uses: [SS1YMS2NPC, 04C5ZBG1WT]
sources:
  - url: https://en.wikipedia.org/wiki/Neville%27s_algorithm
---

## Definition

Let $K$ be a [[field|04C5ZBG1WT]], let $n \ge 0$, let $x_0, \dots, x_n \in K$ be pairwise distinct, let $y_0, \dots, y_n \in K$, and let $x \in K$.
*Neville's algorithm* computes the numbers $p_{i,j}$ for $0 \le i \le j \le n$ by the recursion

1. $p_{i,i} = y_i$ for $0 \le i \le n$;
2. for $i < j$,
$$p_{i,j} = \frac{(x - x_i) \, p_{i+1,j} - (x - x_j) \, p_{i,j-1}}{x_j - x_i},$$

in order of increasing $j - i$, and returns $p_{0,n}$.

## Remarks

By induction on $j - i$, the number $p_{i,j}$ is the value at $x$ of the [[interpolation polynomial|SS1YMS2NPC]] of degree at most $j - i$ through $(x_i, y_i), \dots, (x_j, y_j)$.
Indeed, the same recursion with $x$ as a variable gives a polynomial of degree at most $j - i$.
At $x = x_i$ it gives $p_{i,j-1}(x_i) = y_i$, and at $x = x_j$ it gives $p_{i+1,j}(x_j) = y_j$.
At an inner node $x_k$ both terms give $y_k$.
So the output $p_{0,n}$ is the value at $x$ of the interpolation polynomial of all the data.

Example: data $(0, 1)$, $(1, 3)$, $(2, 7)$ and $x = 3$.
Then $p_{0,1} = \frac{3 \cdot 3 - 2 \cdot 1}{1} = 7$, $p_{1,2} = \frac{2 \cdot 7 - 1 \cdot 3}{1} = 11$ and $p_{0,2} = \frac{3 \cdot 11 - 1 \cdot 7}{2} = 13$.
This agrees with the interpolation polynomial $x^2 + x + 1$ at $3$.

Non-example: if two nodes coincide, $x_i = x_j$ with $i < j$, the recursion divides by $x_j - x_i = 0$, so the algorithm is not defined.