Neville’s Method of Polynomial Interpolation

[This article was first published on R – Aaron Schlegel, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Part 1 of 5 in the series Numerical Analysis

Neville’s method evaluates a polynomial that passes through a given set of [latex]x[/latex] and [latex]y[/latex] points for a particular [latex]x[/latex] value using the Newton polynomial form. Neville’s method is similar to a now-defunct procedure named Aitken’s algorithm and is based on the divided differences recursion relation (“Neville’s Algorithm”, n.d).

It was stated before in a previous post on Lagrangian polynomial interpolation that there exists a Lagrange polynomial that passes through points [latex]y_1, y_2, \cdots, y_k[/latex] where each is a distinct integer and [latex]0 \leq y_i \leq n[/latex] at corresponding x values [latex]x_0, x_1, x_2, \cdots, x_n[/latex]. The [latex]k[/latex] points [latex]y_1, y_2, \cdots, y_k[/latex] are denoted [latex]P_{y_1, y_2, \cdots, y_k}(x)[/latex].

Neville’s Method

Neville’s method can be stated as follows:

Let a function [latex]f[/latex] be defined at points [latex]x_0, x_1, \cdots, x_k[/latex] where [latex]x_j[/latex] and [latex]x_i[/latex] are two distinct members. For each [latex]k[/latex], there exists a Lagrange polynomial [latex]P[/latex] that interpolates the function [latex]f[/latex] at the [latex]k + 1[/latex] points [latex]x_0, x_1, \cdots, x_k[/latex]. The [latex]k[/latex]th Lagrange polynomial is defined as:

[latex display=”true”] \large{P(x) = \frac{(x – x_j) P_{0,1,\cdots,j-1,j+1,\cdots,k}(x) – (x – x_i) P_{0,1,\cdots,i-1,i+1,\cdots,k}(x)}{(x_i – x_j)}} [/latex]

The [latex]P_{0,1,\cdots,j-1,j+1,\cdots,k}[/latex] and [latex]P_{0,1,\cdots,i-1,i+1,\cdots,k}[/latex] are often denoted [latex]\hat{Q}[/latex] and [latex]Q[/latex], respectively, for ease of notation.

[latex display=”true”] \large{P(x) = \frac{(x – x_j) \hat{Q}(x) – (x – x_i) Q(x)}{(x_i – x_j)}} [/latex]

The interpolating polynomials can thus be generated recursively, which we will see in the following example:

Neville’s Method Example

Consider the following table of [latex]x[/latex] and corresponding [latex]y[/latex] values.

x y
8.1 16.9446
8.3 17.56492
8.6 18.50515
8.7 18.82091

Suppose we are interested in interpolating a polynomial that passes through these points to approximate the resulting [latex]y[/latex] value from an [latex]x[/latex] value of 8.4.

We can construct the interpolating polynomial approximations using the function above:

[latex display=”true”] Q_{1,1} = \frac{(8.4 – x_0)Q_{1,0} – (8.4 – x_1) Q_{0,0}}{x_1 – x_0} = \frac{(8.4 – 8.1)(17.56492) – (8.4 – 8.3)(16.9446)}{8.3 – 8.1} = 17.87508 [/latex]
[latex display=”true”] Q_{2,1} = \frac{(8.4 – x_1)Q_{2,0} – (8.4 – x_2)Q_{1,0}}{(x_2 – x_1)} = \frac{(8.4 – 8.3)(18.50515) – (8.4 – 8.6)(17.56492)}{(8.6 – 8.3)} = 17.87833 [/latex]
[latex display=”true”] Q_{3,1} = \frac{(8.4 – x_2)Q_{3,0} – (8.4 – x_3)Q_{2,0}}{(x_3 – x_2)} = \frac{(8.4 – 8.6)(18.82091) – (8.4 – 8.7)(18.50515)}{(8.7 – 8.6)} = 17.87363 [/latex]

The approximated values [latex]Q_{1,1} = 17.87508, Q_{2,1} = 17.87833, Q_{3,1} = 17.87363[/latex] are then used in the next iteration.

[latex display=”true”] Q_{2,2} = \frac{(8.4 – x_0)Q_{2,1} – (8.4 – x_2)Q_{1,1}}{(x_2 – x_0)} = \frac{(8.4 – 8.1)(17.87833) – (8.4 – 8.6)(17.87508)}{(8.6 – 8.1)} = 17.87703 [/latex]
[latex display=”true”] Q_{3,2} = \frac{(8.4 – x_1)Q_{3,1} – (8.4 – x_3)Q_{2,1}}{(x_3 – x_1)} = \frac{(8.4 – 8.3)(17.87363) – (8.4 – 8.7)(17.87833)}{(8.7 – 8.3)} = 17.877155 [/latex]

Then the final iteration yields the approximated [latex]y[/latex] value for the given [latex]x[/latex] value.

[latex display=”true”] Q_{3,3} = \frac{(8.4 – x_0)Q_{3,2} – (8.4 – x_3)Q_{2,2}}{(x_3 – x_0)} = \frac{(8.4 – 8.1)(17.877155) – (8.4 – 8.7)(17.87703)}{(8.7 – 8.1)} = 17.8770925 [/latex]

Therefore [latex]17.8770925[/latex] is the approximated value at the point [latex]8.4[/latex].

Neville’s Method in R

The following function is an implementation of Neville’s method for interpolating and evaluating a polynomial.

poly.neville <- function(x, y, x0) {
  
  n <- length(x)
  q <- matrix(data = 0, n, n)
  q[,1] <- y
  
  for (i in 2:n) {
    for (j in i:n) {
      q[j,i] <- ((x0 - x[j-i+1]) * q[j,i-1] - (x0 - x[j]) * q[j-1,i-1]) / (x[j] - x[j-i+1])
    }
  }
  
  res <- list('Approximated value'=q[n,n], 'Neville iterations table'=q)
  return(res)
}

Let’s test this function to see if it reports the same result as what we found earlier.

x <- c(8.1, 8.3, 8.6, 8.7)
y <- c(16.9446, 17.56492, 18.50515, 18.82091)

poly.neville(x, y, 8.4)
## $`Approximated value`
## [1] 17.87709
## 
## $`Neville iterations table`
##          [,1]     [,2]     [,3]     [,4]
## [1,] 16.94460  0.00000  0.00000  0.00000
## [2,] 17.56492 17.87508  0.00000  0.00000
## [3,] 18.50515 17.87833 17.87703  0.00000
## [4,] 18.82091 17.87363 17.87716 17.87709

The approximated value is reported as [latex]17.87709[/latex], the same value we calculated previously (minus a few decimal places). The function also outputs the iteration table that stores the intermediate results.

The pracma package contains the neville() function which also performs Neville’s method of polynomial interpolation and evaluation.

library(pracma)


neville(x, y, 8.4)
## [1] 17.87709

The neville() function reports the same approximated value that we found with our manual calculations and function.

References

Burden, R. L., & Faires, J. D. (2011). Numerical analysis (9th ed.). Boston, MA: Brooks/Cole, Cengage Learning.

Cheney, E. W., & Kincaid, D. (2013). Numerical mathematics and computing (6th ed.). Boston, MA: Brooks/Cole, Cengage Learning.

Neville’s algorithm. (2016, January 2). In Wikipedia, The Free Encyclopedia. From https://en.wikipedia.org/w/index.php?title=Neville%27s_algorithm&oldid=697870140

The post Neville’s Method of Polynomial Interpolation appeared first on Aaron Schlegel.

To leave a comment for the author, please follow the link and comment on their blog: R – Aaron Schlegel.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)