CS323 LECTURE NOTES - LECTURE 12

Neville’s Method

From the algorithmic point of view, if we want to compute P(r) for many values of r ∈ R, the method described before is not very ecient since we must compute the complete polynomial for each one of them. The other option is to use (2)and(3) substituting all the values to nd P(4). In this case each L requires O(n) operations, and since there are n Ls to compute, the method will take O(n2) time to compute.

We will now discuss a dierent method to obtain the value of the interpolating polynomial for a given x = r. with this method we do not nd the coecients of the polynomial, we just nd the value of P(r). Algorithmically speaking, this method uses the Dynamic

Programming technique which is used in recursive algorithms to avoid the use of recursion by storing temporary results on a table.

Let us dene Pi,j(x) to be the polynomial that goes exactly through points (xi,yi), (xi+1,yi+1), . . . , (xj  1,yj  1), (xj ,yj)

Suppose that we are given Pi,j  1(x) and Pi+1,j(x), i.e. those polynomials that go through the points i, . . . ,j  1andi + 1, . . .,j respectively. Using these two polynomial we will build Pi,j(x).

Notice that Pi+1,j(x) does not correctly compute yi when x = xi , so if we multiply it by (x  xi), it will be 0 when x = xi, but since it correctly computes the value of yj  when x = xj, we divide it by (xj  xi).

(x  xi)

Pi+1,j (x)

On the other hand, Pi,j  1(x) does not correctly compute yj when x = xj, so if whe multiply it by (x  xj), it will be 0 when x = xj , but since it correctly computes that value of yi  when x = xi, we divide it by (xi  xj)

(x  xj)

Pi,j  1(x)(x)

We claim that we can just add the previous two polynomials to obtain Pi,j

Pi,j(x) =

=

(x  xi)         (x  xj)

(xj  xi)        (xi  xj )

Pi+1,j (x)(x  xi)  Pi,j  1(x)(x  xj)

xj  xi

We just have to verify

 yi Pi,j (x) =  yj

case x = xi

that

if

if

if x = xk ,

x = xi

x = xj

i + 1  k  j  1

Pi,j(xi) =

=

=

Pi+1,j (xi)(xi  xi)  Pi,j  1(xi)(xi  xj )

xj  xi

Pi,j  1(xi)

yi

case x = xj

Pi,j(xj) =

=

Pi+1,j (xj )(xj  xi)  Pi,j  1(xj )(xj  xj )

xj  xi

Pi+1,j (xj)

= yj

case x = xk   i + 1  k  j  1

Pi,j(xk) =

=

Pi+1,j (xk)(xk  xi)  Pi,j  1(xk)(xk  xj) xj  xi

ykxk  ykxi  ykxk + ykxj xj  xi

yk (xj  xi)

=                         xj  x + i

= yk

Hence we have the following formula

Pi+1,j (x)(x  xi)  Pi,j  1(x)(x  xj)

xj  xi

which is known as Neville’s formula.

Notice that Neville’s formula is recursive since to compute it we need to compute itself on dierent values. In the case of interpolat- ing polynomials the objective is to nd the one that goes through each one of the points from the rst one to the last one.

For the sake of simplicity of the algorithm assume that we are given n+ 1 points (x0,y0), (x1,y1), . . . , (xn,yn) and that we want to compute the polynomial of degree n that goes through the points. This means that we need to nd P0,n(x).

Using Neville’s formula we noticethat in orderto compute P0,n(x) we need to compute P0,n  1(x) and P1,n(x). We can put all those polynomials in a n  n matrix, where polynomial Pi,j(x) would be stored in row i column j:

Since Pk,k is the polynomial of degree 0 that goes through point (xk,yk), we have that:

Pk,k(x) = yk    ∀k = 0, . . . ,n

i.e. we have all the values of the main diagonal. The remaining values can be computed diagonally, since according the Neville’s formula, to compute the value of an entry Pi,j  we need only to compute the entry to its right (Pi,j  1), and the one immediately below it (Pi+1,j).