Neville's algorithm

Neville's algorithm

In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation that was derived by the mathematician Eric Harold Neville. Given n + 1 points, there is a unique polynomial of degree ≤ n which goes through the given points. Neville's algorithm evaluates this polynomial.

Neville's algorithm is based on the Newton form of the interpolating polynomial and the recursion relation for the divided differences. It is similar to Aitken's algorithm (named after Alexander Aitken), which is nowadays not used.

The algorithm

Given a set of n+1 data points (xi, yi) where no two xi are the same, the interpolating polynomial is the polynomial p of degree at most n with the property

p(xi) = yi for all i = 0,…,n

This polynomial exists and it is unique. Neville's algorithm evaluates the polynomial at some point x.

Let pi,j denote the polynomial of degree ji which goes through the points (xk, yk) for k = i, i + 1, …, j. The pi,j satisfy the recurrence relation

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

This recurrence can calculate p0,n(x), which is the value being sought. This is Neville's algorithm.

For instance, for n = 4, one can use the recurrence to fill the triangular tableau below from the left to the right.

 p_{0,0}(x) = y_0 \,
 p_{0,1}(x) \,
 p_{1,1}(x) = y_1 \,  p_{0,2}(x) \,
 p_{1,2}(x) \,  p_{0,3}(x) \,
 p_{2,2}(x) = y_2 \,  p_{1,3}(x) \,  p_{0,4}(x) \,
 p_{2,3}(x) \,  p_{1,4}(x) \,
 p_{3,3}(x) = y_3 \,  p_{2,4}(x) \,
 p_{3,4}(x) \,
 p_{4,4}(x) = y_4 \,

This process yields p0,4(x), the value of the polynomial going through the n + 1 data points (xi, yi) at the point x.

This algorithm needs O(n2) floating point operations.

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Neville — is a name that originates from place names in Normandy, from the Old French Néville Néel s estate or Neuville, meaning new village or new town . Neville may refer to: Contents 1 Places 2 Other uses …   Wikipedia

  • Algorithme de Neville — En analyse numérique, l algorithme de Neville[1] est un algorithme d interpolation polynomiale dû à Eric Harold Neville. L algorithme de Neville est une méthode récursive du calcul de la valeur du polynôme d interpolation en un point donné, avec… …   Wikipédia en Français

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Extrapolation de Richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson[1],[2], qui l a introduit au début du XXe siècle. Ce procédé est… …   Wikipédia en Français

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Polynomial interpolation — In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which… …   Wikipedia

  • List of Star Trek characters (N–S) — This article lists characters of Star Trek in their various canonical incarnations. This includes fictional major characters and fictional minor characters created for Star Trek, fictional characters not originally created for Star Trek, and real …   Wikipedia

  • Ornithopter — Cybird radio controlled ornithopter Pa …   Wikipedia

  • Super-logarithm — In mathematics, the super logarithm is one of the two inverse functions of tetration. Just as exponentiation has two inverse functions: roots and logarithms, likewise tetration has two inverse functions: super roots and super logarithms. There… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”