<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/nevilles-method-of-polynomial-interpolation/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.aaronschlegel.com/nevilles-method-polynomial-interpolation/"> R – Aaron Schlegel</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div>Part 1 of 5 in the series <a rel="nofollow" href="http://www.aaronschlegel.com/series/numerical-analysis/" title="Numerical Analysis" target="_blank">Numerical Analysis</a></div>
<p>Neville’s method evaluates a polynomial that passes through a given set of <img alt="x" title="x" src="https://s0.wp.com/latex.php?latex=x&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="y" title="y" src="https://s0.wp.com/latex.php?latex=y&bg=ffffff&fg=000&s=0" class="latex"> points for a particular <img alt="x" title="x" src="https://s0.wp.com/latex.php?latex=x&bg=ffffff&fg=000&s=0" class="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).</p>
<p>It was stated before in a previous post on <a rel="nofollow" href="http://wp.me/p4aZEo-5RJ" target="_blank">Lagrangian polynomial interpolation</a> that there exists a Lagrange polynomial that passes through points <img alt="y_1, y_2, \cdots, y_k" title="y_1, y_2, \cdots, y_k" src="https://s0.wp.com/latex.php?latex=y_1%2C+y_2%2C+%5Ccdots%2C+y_k&bg=ffffff&fg=000&s=0" class="latex"> where each is a distinct integer and <img alt="0 \leq y_i \leq n" title="0 \leq y_i \leq n" src="https://s0.wp.com/latex.php?latex=0+%5Cleq+y_i+%5Cleq+n&bg=ffffff&fg=000&s=0" class="latex"> at corresponding x values <img alt="x_0, x_1, x_2, \cdots, x_n" title="x_0, x_1, x_2, \cdots, x_n" src="https://s0.wp.com/latex.php?latex=x_0%2C+x_1%2C+x_2%2C+%5Ccdots%2C+x_n&bg=ffffff&fg=000&s=0" class="latex">. The <img alt="k" title="k" src="https://s0.wp.com/latex.php?latex=k&bg=ffffff&fg=000&s=0" class="latex"> points <img alt="y_1, y_2, \cdots, y_k" title="y_1, y_2, \cdots, y_k" src="https://s0.wp.com/latex.php?latex=y_1%2C+y_2%2C+%5Ccdots%2C+y_k&bg=ffffff&fg=000&s=0" class="latex"> are denoted <img alt="P_{y_1, y_2, \cdots, y_k}(x)" title="P_{y_1, y_2, \cdots, y_k}(x)" src="https://s0.wp.com/latex.php?latex=P_%7By_1%2C+y_2%2C+%5Ccdots%2C+y_k%7D%28x%29&bg=ffffff&fg=000&s=0" class="latex">.</p>
<h6>Neville’s Method</h6>
<p>Neville’s method can be stated as follows:</p>
<p>Let a function <img alt="f" title="f" src="https://s0.wp.com/latex.php?latex=f&bg=ffffff&fg=000&s=0" class="latex"> be defined at points <img alt="x_0, x_1, \cdots, x_k" title="x_0, x_1, \cdots, x_k" src="https://s0.wp.com/latex.php?latex=x_0%2C+x_1%2C+%5Ccdots%2C+x_k&bg=ffffff&fg=000&s=0" class="latex"> where <img alt="x_j" title="x_j" src="https://s0.wp.com/latex.php?latex=x_j&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="x_i" title="x_i" src="https://s0.wp.com/latex.php?latex=x_i&bg=ffffff&fg=000&s=0" class="latex"> are two distinct members. For each <img alt="k" title="k" src="https://s0.wp.com/latex.php?latex=k&bg=ffffff&fg=000&s=0" class="latex">, there exists a Lagrange polynomial <img alt="P" title="P" src="https://s0.wp.com/latex.php?latex=P&bg=ffffff&fg=000&s=0" class="latex"> that interpolates the function <img alt="f" title="f" src="https://s0.wp.com/latex.php?latex=f&bg=ffffff&fg=000&s=0" class="latex"> at the <img alt="k + 1" title="k + 1" src="https://s0.wp.com/latex.php?latex=k+%2B+1&bg=ffffff&fg=000&s=0" class="latex"> points <img alt="x_0, x_1, \cdots, x_k" title="x_0, x_1, \cdots, x_k" src="https://s0.wp.com/latex.php?latex=x_0%2C+x_1%2C+%5Ccdots%2C+x_k&bg=ffffff&fg=000&s=0" class="latex">. The <img alt="k" title="k" src="https://s0.wp.com/latex.php?latex=k&bg=ffffff&fg=000&s=0" class="latex">th Lagrange polynomial is defined as:</p>
<img alt=" \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)}} " title=" \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)}} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7BP%28x%29+%3D+%5Cfrac%7B%28x+-+x_j%29+P_%7B0%2C1%2C%5Ccdots%2Cj-1%2Cj%2B1%2C%5Ccdots%2Ck%7D%28x%29+-+%28x+-+x_i%29+P_%7B0%2C1%2C%5Ccdots%2Ci-1%2Ci%2B1%2C%5Ccdots%2Ck%7D%28x%29%7D%7B%28x_i+-+x_j%29%7D%7D+&bg=ffffff&fg=000&s=0" class="latex">
<p>The <img alt="P_{0,1,\cdots,j-1,j+1,\cdots,k}" title="P_{0,1,\cdots,j-1,j+1,\cdots,k}" src="https://s0.wp.com/latex.php?latex=P_%7B0%2C1%2C%5Ccdots%2Cj-1%2Cj%2B1%2C%5Ccdots%2Ck%7D&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="P_{0,1,\cdots,i-1,i+1,\cdots,k}" title="P_{0,1,\cdots,i-1,i+1,\cdots,k}" src="https://s0.wp.com/latex.php?latex=P_%7B0%2C1%2C%5Ccdots%2Ci-1%2Ci%2B1%2C%5Ccdots%2Ck%7D&bg=ffffff&fg=000&s=0" class="latex"> are often denoted <img alt="\hat{Q}" title="\hat{Q}" src="https://s0.wp.com/latex.php?latex=%5Chat%7BQ%7D&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="Q" title="Q" src="https://s0.wp.com/latex.php?latex=Q&bg=ffffff&fg=000&s=0" class="latex">, respectively, for ease of notation.</p>
<img alt=" \large{P(x) = \frac{(x - x_j) \hat{Q}(x) - (x - x_i) Q(x)}{(x_i - x_j)}} " title=" \large{P(x) = \frac{(x - x_j) \hat{Q}(x) - (x - x_i) Q(x)}{(x_i - x_j)}} " src="https://s0.wp.com/latex.php?latex=+%5Clarge%7BP%28x%29+%3D+%5Cfrac%7B%28x+-+x_j%29+%5Chat%7BQ%7D%28x%29+-+%28x+-+x_i%29+Q%28x%29%7D%7B%28x_i+-+x_j%29%7D%7D+&bg=ffffff&fg=000&s=0" class="latex">
<p>The interpolating polynomials can thus be generated recursively, which we will see in the following example:</p>
<h6>Neville’s Method Example</h6>
<p>Consider the following table of <img alt="x" title="x" src="https://s0.wp.com/latex.php?latex=x&bg=ffffff&fg=000&s=0" class="latex"> and corresponding <img alt="y" title="y" src="https://s0.wp.com/latex.php?latex=y&bg=ffffff&fg=000&s=0" class="latex"> values.</p>
<table>
<thead>
<tr>
<th>x</th>
<th>y</th>
</tr>
</thead>
<tbody>
<tr>
<td>8.1</td>
<td>16.9446</td>
</tr>
<tr>
<td>8.3</td>
<td>17.56492</td>
</tr>
<tr>
<td>8.6</td>
<td>18.50515</td>
</tr>
<tr>
<td>8.7</td>
<td>18.82091</td>
</tr>
</tbody>
</table>
<p>Suppose we are interested in interpolating a polynomial that passes through these points to approximate the resulting <img alt="y" title="y" src="https://s0.wp.com/latex.php?latex=y&bg=ffffff&fg=000&s=0" class="latex"> value from an <img alt="x" title="x" src="https://s0.wp.com/latex.php?latex=x&bg=ffffff&fg=000&s=0" class="latex"> value of 8.4.</p>
<p>We can construct the interpolating polynomial approximations using the function above:</p>
<p><img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B1%2C1%7D+%3D+%5Cfrac%7B%288.4+-+x_0%29Q_%7B1%2C0%7D+-+%288.4+-+x_1%29+Q_%7B0%2C0%7D%7D%7Bx_1+-+x_0%7D+%3D+%5Cfrac%7B%288.4+-+8.1%29%2817.56492%29+-+%288.4+-+8.3%29%2816.9446%29%7D%7B8.3+-+8.1%7D+%3D+17.87508+&bg=ffffff&fg=000&s=0" class="latex"><br>
<img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B2%2C1%7D+%3D+%5Cfrac%7B%288.4+-+x_1%29Q_%7B2%2C0%7D+-+%288.4+-+x_2%29Q_%7B1%2C0%7D%7D%7B%28x_2+-+x_1%29%7D+%3D+%5Cfrac%7B%288.4+-+8.3%29%2818.50515%29+-+%288.4+-+8.6%29%2817.56492%29%7D%7B%288.6+-+8.3%29%7D+%3D+17.87833+&bg=ffffff&fg=000&s=0" class="latex"><br>
<img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B3%2C1%7D+%3D+%5Cfrac%7B%288.4+-+x_2%29Q_%7B3%2C0%7D+-+%288.4+-+x_3%29Q_%7B2%2C0%7D%7D%7B%28x_3+-+x_2%29%7D+%3D+%5Cfrac%7B%288.4+-+8.6%29%2818.82091%29+-+%288.4+-+8.7%29%2818.50515%29%7D%7B%288.7+-+8.6%29%7D+%3D+17.87363+&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>The approximated values <img alt="Q_{1,1} = 17.87508, Q_{2,1} = 17.87833, Q_{3,1} = 17.87363" title="Q_{1,1} = 17.87508, Q_{2,1} = 17.87833, Q_{3,1} = 17.87363" src="https://s0.wp.com/latex.php?latex=Q_%7B1%2C1%7D+%3D+17.87508%2C+Q_%7B2%2C1%7D+%3D+17.87833%2C+Q_%7B3%2C1%7D+%3D+17.87363&bg=ffffff&fg=000&s=0" class="latex"> are then used in the next iteration.</p>
<p><img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B2%2C2%7D+%3D+%5Cfrac%7B%288.4+-+x_0%29Q_%7B2%2C1%7D+-+%288.4+-+x_2%29Q_%7B1%2C1%7D%7D%7B%28x_2+-+x_0%29%7D+%3D+%5Cfrac%7B%288.4+-+8.1%29%2817.87833%29+-+%288.4+-+8.6%29%2817.87508%29%7D%7B%288.6+-+8.1%29%7D+%3D+17.87703+&bg=ffffff&fg=000&s=0" class="latex"><br>
<img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B3%2C2%7D+%3D+%5Cfrac%7B%288.4+-+x_1%29Q_%7B3%2C1%7D+-+%288.4+-+x_3%29Q_%7B2%2C1%7D%7D%7B%28x_3+-+x_1%29%7D+%3D+%5Cfrac%7B%288.4+-+8.3%29%2817.87363%29+-+%288.4+-+8.7%29%2817.87833%29%7D%7B%288.7+-+8.3%29%7D+%3D+17.877155+&bg=ffffff&fg=000&s=0" class="latex"></p>
<p>Then the final iteration yields the approximated <img alt="y" title="y" src="https://s0.wp.com/latex.php?latex=y&bg=ffffff&fg=000&s=0" class="latex"> value for the given <img alt="x" title="x" src="https://s0.wp.com/latex.php?latex=x&bg=ffffff&fg=000&s=0" class="latex"> value.</p>
<img alt=" 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 " title=" 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 " src="https://s0.wp.com/latex.php?latex=+Q_%7B3%2C3%7D+%3D+%5Cfrac%7B%288.4+-+x_0%29Q_%7B3%2C2%7D+-+%288.4+-+x_3%29Q_%7B2%2C2%7D%7D%7B%28x_3+-+x_0%29%7D+%3D+%5Cfrac%7B%288.4+-+8.1%29%2817.877155%29+-+%288.4+-+8.7%29%2817.87703%29%7D%7B%288.7+-+8.1%29%7D+%3D+17.8770925+&bg=ffffff&fg=000&s=0" class="latex">
<p>Therefore <img alt="17.8770925" title="17.8770925" src="https://s0.wp.com/latex.php?latex=17.8770925&bg=ffffff&fg=000&s=0" class="latex"> is the approximated value at the point <img alt="8.4" title="8.4" src="https://s0.wp.com/latex.php?latex=8.4&bg=ffffff&fg=000&s=0" class="latex">.</p>
<h6>Neville’s Method in R</h6>
<p>The following function is an implementation of Neville’s method for interpolating and evaluating a polynomial.</p>
<pre>
poly.neville &lt;- function(x, y, x0) {
  
  n &lt;- length(x)
  q &lt;- matrix(data = 0, n, n)
  q[,1] &lt;- y
  
  for (i in 2:n) {
    for (j in i:n) {
      q[j,i] &lt;- ((x0 - x[j-i+1]) * q[j,i-1] - (x0 - x[j]) * q[j-1,i-1]) / (x[j] - x[j-i+1])
    }
  }
  
  res &lt;- list('Approximated value'=q[n,n], 'Neville iterations table'=q)
  return(res)
}
</pre>
<p>Let’s test this function to see if it reports the same result as what we found earlier.</p>
<pre>
x &lt;- c(8.1, 8.3, 8.6, 8.7)
y &lt;- 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
</pre>
<p>The approximated value is reported as <img alt="17.87709" title="17.87709" src="https://s0.wp.com/latex.php?latex=17.87709&bg=ffffff&fg=000&s=0" class="latex">, the same value we calculated previously (minus a few decimal places). The function also outputs the iteration table that stores the intermediate results.</p>
<p>The <a rel="nofollow" href="https://cran.r-project.org/web/packages/pracma/index.html" target="_blank">pracma package</a> contains the <code>neville()</code> function which also performs Neville’s method of polynomial interpolation and evaluation.</p>
<pre>
library(pracma)
</pre>
<pre>
neville(x, y, 8.4)
## [1] 17.87709
</pre>
<p>The <code>neville()</code> function reports the same approximated value that we found with our manual calculations and function.</p>
<h6>References</h6>
<p>Burden, R. L., &amp; Faires, J. D. (2011). Numerical analysis (9th ed.). Boston, MA: Brooks/Cole, Cengage Learning.</p>
<p>Cheney, E. W., &amp; Kincaid, D. (2013). Numerical mathematics and computing (6th ed.). Boston, MA: Brooks/Cole, Cengage Learning.</p>
<p>Neville’s algorithm. (2016, January 2). In Wikipedia, The Free Encyclopedia. From <a rel="nofollow" href="https://en.wikipedia.org/w/index.php?title=Neville%27s_algorithm&oldid=697870140" target="_blank">https://en.wikipedia.org/w/index.php?title=Neville%27s_algorithm&amp;oldid=697870140</a></p>
<p>The post <a rel="nofollow" href="http://www.aaronschlegel.com/nevilles-method-polynomial-interpolation/" target="_blank">Neville’s Method of Polynomial Interpolation</a> appeared first on <a rel="nofollow" href="http://www.aaronschlegel.com/" target="_blank">Aaron Schlegel</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://www.aaronschlegel.com/nevilles-method-polynomial-interpolation/"> R – Aaron Schlegel</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/ThWzwaKuv-0" height="1"></a></div>