Open access peer-reviewed chapter

Relationship between Interpolation and Differential Equations: A Class of Collocation Methods

Written By

Francesco Aldo Costabile, Maria Italia Gualtieri and Anna Napoli

Submitted: May 15th, 2016 Reviewed: November 21st, 2016 Published: March 15th, 2017

DOI: 10.5772/66995

Chapter metrics overview

1,600 Chapter Downloads

View Full Metrics


In this chapter, the connection between general linear interpolation and initial, boundary and multipoint value problems is explained. First, a result of a theoretical nature is given, which highlights the relationship between the interpolation problem and the Fredholm integral equation for high-order differential problems. After observing that the given problem is equivalent to a Fredholm integral equation, this relation is used in order to determine a general procedure for the numerical solution of high-order differential problems by means of appropriate collocation methods based on the integration of the Fredholm integral equation. The classical analysis of the class of the obtained methods is carried out. Some particular cases are illustrated. Numerical examples are given in order to illustrate the efficiency of the method.


  • boundary value problem
  • initial value problem
  • collocation methods
  • interpolation
  • Birkhoff
  • Lagrange
  • Peano
  • Fredholm

1. Introduction

The relationship between interpolation and differential equations theories has already been considered. In Ref. ([1], p. 72), Davis observed that the Peano kernel in the interpolation problem


is the Green’s function of the differential problem


where φ(x)=y(x)P1[y](x), being P1[y](x)the unique interpolatory polynomial for Eq. (1).

He observed that “these remarks indicate the close relationship between Peano kernels and Green’s functions, and hence between interpolation theory and the theory of linear differential equations. Unfortunately, we shall not be able to pursue this relationship” [1].

Later, Agarwal ([2], p. 2), Agarwal and Wong ([3], pp. 21, 151, 186) considered some separate boundary value problems and the related Fredholm integral equation, using only polynomial interpolation, without taking into account the related Peano kernel. They used Fredholm integral equation in order to obtain existence and uniqueness results for the solution of the considered boundary value problems.

Linear interpolation has an important role also in the numerical solution of differential problems. For example, finite difference methods (see, for instance, [46] and references therein) approximate the solution y(x)of a boundary value problem by a sequence of overlapping polynomials which interpolate y(x)in a set of grid points. This is obtained by replacing the differential equation with finite difference equations on a mesh of points that covers the range of integration. The resultant algebraic system of equations is often solved with iterative processes, such as relaxation methods.

Many authors (see [710] and references therein) used linear interpolation with spline functions for the numerical solution of boundary value problems.

Here, we take into account a more general nonlinear initial/boundary/multipoint value problems for high-order differential equations


where y(x)=(y(x),y(x),,y(q)(x)), 0q<r, yCr(I), and Liare rlinearly independent functionals on Cr(I). Moreover, we suppose that the function f:[a,b]×Rq+1Ris continuous at least in the interior of the domain of interest, and it satisfies a uniform Lipschitz condition in y, which means that there exists a nonnegative constant Λ, such that, whenever (x,y0,y1,,yq)and (x,y¯0,y¯1,,y¯q)are in the domain of f, the following inequality holds


If Li[y]=Φ(y(a)),i=0,,r1, then (2) is an initial value problem (IVP); if Li[y]=Φ(y(a),y(b)),i=0,,r1, then (2) is a boundary value problem (BVP); if Li[y]=Φ(y(xj)),i=0,,r1, j=0,,m2, then (2) is a multipoint value problem (MVP).

In this chapter,

  1. - we assume that the conditions for the existence and uniqueness of solution of problem (2) in a certain appropriate domain of [a,b]×Rq+1are satisfied and that the solution y(x)is differentiable with continuity up to what is necessary;

  2. - we get the Fredholm integral equation related to problem (2), by polynomial interpolation and the Peano kernel of the linear interpolation problem Li[y](x)=wi,i=0,,r1. In this way, we point out the close relationship between Green’s function and Peano kernel;

  3. - then, we construct a class of spectral collocation (pseudospectral) methods which are derived by a linear interpolation process.

The reason for which we prefer collocation methods is their superior accuracy for problems whose solutions are sufficiently smooth functions. Recently, Boyd ([11], p. 8) observed that “When many decimal places of accuracy are needed, the contest between pseudospectral algorithms and finite difference and finite element methods is not an even battle but a rout: pseudospectral methods win hands-down.”


2. The Fredholm integral equation for problem (2)

We consider the general differential problem (2), and we prove that it is equivalent to a Fredholm integral equation.

Proposition 1[1, p. 35] The linear interpolation problem


withLi, i=0,,r1, linearly independent functionals onCr(I), has the unique solution


Proof. Since the Li, i=0,,r1are linearly independent, the result follows from the general linear interpolation theory.

Proposition 2IfyCr(I)andLi[y](x)=wi,i=0,,r1,xI, then


with Li[y]=Li[Pr1], i=0,,r1, Pr1[y](x)=Pr1(x), and


where indexxmeans thatKrx(x,t)is considered as a function ofx.

Proof. It follows by observing that Pr1[(x)+j](t)=(t)+j,j=0,,r1and from Peano kernel Theorem [1].

Theorem 1With the above notations and under the mentioned hypothesis, problem (2) is equivalent to the Fredholm integral equation


Proof. The result follows from the uniqueness of the Peano kernel and from Propositions 1 and 2.

Corollary 1It resultsLi[Krx]=0,i=0,,r1.

From Theorem 1, general results on the existence and uniqueness of solution of problem (2) by standard techniques [2, 3] can be obtained. In the following, we will not linger over them, but we will outline the close relationship between interpolation and differential equations. Particularly, we will use linear interpolation in order to determine a class of collocation methods for the numerical solution of problem (2).


3. A class of Birkhoff-Lagrange collocation methods

Integral Eq. (8) allows to determine a very wide class of numerical methods for Eq. (2), which we call methods of collocation for integration.

Let {xi}i=1mbe mdistinct points in [a,b]and denoted by li(t), i=1,,m,the fundamental Lagrange polynomials on the nodes xi, that is

li(t)=ωm(t)(txi)ωm(xi),where ωm(t)=k=1m(txk).E9

Theorem 2If the solutiony(x)of Eq. (8) is inCr+m(I), then




and the remainder termTr,m(y,x)is given by:


beingξxa suitable point of the smallest interval containingxand allxi, i=1,,m.

Proof. From Lagrange interpolation




is the remainder term. From (2), f(x,y(x))=i=1mli(x)y(r)(xi)+R¯m(y,x). Then, from Theorem 1, inserting Eq. (13) into (8), we obtain Eq. (10).

Theorem 2 suggests to consider the implicitly defined polynomial


For polynomial (15), the following theorem holds.

Theorem 3 (The main Theorem).Polynomial (15), of degreer+m1, satisfies the relations


that is, yr,m(x)is a collocation polynomial for Eq. (2) at nodesxj, j=1,,m.

Proof. From (15), Corollary 1 and the linearity of operators Li, we get Li[yr,m](x)=wi,i=0,,r1. By Theorems 1 and 2, we obtain y(r)(xi)=yr,m(r)(xi), and from Eq. (11), pr,i,m(r)(x)=li(x). Hence, relations (16) follow.

Remark 1(Hermite-Birkhoff-type interpolation). Theorem 3 is equivalent to the general Hermite-Birkhoff interpolation problem [12]: givenwiR,i=0,,r1, andαjR,j=1,,m, determine, if there exists, the polynomialQ(x)Pm+r1such that


Remark 2In the case of IVPs, for each method (15), we can derive the corresponding implicit Runge-Kutta method. For example, forr=2, letb=x0+handxi=x0+cihwithci[0,1]. With the change of coordinatesx=x0+th,t[0,1], we can write


Puttingf(xi,yr,m(xi))=yr,m(xi)Ki,ai,j=pr,j(xi)=h20ci(cis)lj(s)ds,we have




Eqs. (19) and (20) are the well-known continuous Runge-Kutta method for second-order differential equations. Particularly, fort=1, we have the implicit Runge-Kutta-Nystrom method.

3.1. A-priori estimation of error

In what follows, we consider the norm


Moreover, we define


where R¯m(y,t)is defined as in (14).

Theorem 4With the previous notations, ifΛQm<1, then


Proof. By deriving Eqs. (10) and (15), stimes, s=0,,q, we get


It follows that


From this, we obtain inequality (23).


4. Algorithms and implementation

To calculate the approximate solution of problem (2) by polynomial yr,m(x)at xI, we need the values yr,m(s)(xk), k=1,,m, s=0,,q. In order to get these values, we propose the following algorithm:

- Put yk(s)=yr,m(s)(xk), k=1,,m, s=0,,qand consider the following system


k=1,,m, s=0,,q, where yi=(yi,yi,,yi(q)).

System (26) can be written in the form






From Eq. (27), we get


or, putting G(Y)=AF(Y)+C,


For the existence and uniqueness of solution of system (34), we can prove, with standard technique, the following theorem.

Theorem 5IfT=ΛA<1, system (34) has a unique solution which can be calculated by an iterative method


with a fixed(Ym)0Rm(q+1)andG(Ym)=AF(Ym)+C.

Moreover, ifYis the exact solution,


Remark 3If f is linear, then system (27) is a linear system which can be solved by a more suitable method.

Remark 4System (27) can be considered as a discrete method for the numerical solution of (2).

Remark 5Method (15) can generate the polynomial sequence


which is equivalent to the discretization of Picard method for differential equations.

4.1. Numerical computation of the entries of matrix A

To calculate the elements a˜i,k(s)of the matrix Ain Eq. (27), we have to compute the integrals


for x=xi. Integrating by parts, it remains to solve the problem of the computation of


i,j=1,m. To this aim, it suffices to compute


where c=aor c=b, r0,0(t)=1,


For the computation of the integral (41), we use the recursive algorithm introduced in Ref. [13]: for each i=1,,m, let us consider the new points zj(i)=xjif j<i, and zj(i)=xj+1if ji. Moreover, let us define g0,1,c(i)(x)=xcand for s=1,,m1


We can easily compute g0,j,c(i)(x)=(xc)jj!.For the computation of Eq. (43), the following recurrence formula [13] holds


Thus, if Wi=k=1,kim(xixk), then


Remark 6An alternative approach for the exact computation of integrals (39) and (40) is to use a quadrature formula with a suitable degree of precision.

4.2. Outline of the method

Summarizing the proposed method consists of the following steps:

  1. determine the interpolation polynomial Pr1[y](x)satisfying the boundary conditions and compute the Peano remainder;

  2. approximate y(r)(x)by Lagrange interpolation on a set of fixed nodal point;

  3. compute the elements of matrix A (28) and solve system (26);

  4. obtain polynomial (15).


5. Some particular cases

Now we consider some special cases of problem (2), and for each case, we determine Pr1[y](x)and Krx(x,t). We also show how the proposed class of methods includes the methods presented in previous works [1224].

5.1. Initial value problems

In the case of initial value problems, in Refs. [13, 17, 25], problem


has been considered, while in Ref. [23], the authors introduced the more general equation


In both cases




If {xi}i=1mare the zeros of Chebyshev polynomials of first and second kind, the explicit expression for polynomials pr,i,m(x)can be obtained [13, 17, 25] for some values of r.

Particularly, for r=1and r=2, in the case of zeros of Chebyshev polynomials of first kind, we get


where Tk1(x)and Tk+1(x)are the Chebyshev polynomials of the first kind and degree k1and k+1, respectively, and


In the case of zeros of Chebyshev polynomials of second kind




In Refs. [13, 25], the authors presented the corresponding implicit Runge-Kutta methods too.

In Ref. [26], Coleman and Booth used also a polynomial interpolant of degree nfor y, but they started from an identity different to Eq. (8) and derived a collocation method for which the nodes {xi}i=1mare the zeros of Chebyshev polynomials of second kind.

5.2. Boundary value problems

5.2.1. Case r=2n

For n=1, for the exact solution y(x)of the second-order BVP


x[1,1], it is known that




By applying method (15), we get [16]


with pr,i,m(x)=11K2x(x,t)li(t)dt.

If xi=cosπim+1, i=1,,m, we obtain explicitly the expression of pr,i,m(x)[18]




The same method has been presented in Ref. [24], where also stability has been studied.

Now assume [a,b]=[0,1]and r>2. Several types of boundary conditions can be considered.

-Hermite boundary conditions [22]:


with αh,βh, h=0,,n1real constants.

In this case, Pr1is the Hermite polynomial of degree 2n1




The kernel is


-Lidstone boundary conditions [19]:


where αh,βh, h=0,,nare real constants.

In this case, Pr1is the Lidstone interpolating polynomial [3] of degree 2n1


where Λk(x)are the Lidstone polynomials of degree 2k+1[3], and the function K2nx(x,t)is


5.2.2. Case r=2n+1

If we consider the following boundary conditions


with α0,αh,βh, h=1,,nreal constants, then Pr1is the complementary Lidstone interpolating polynomial [27] of degree 2n[3, 24, 27, 28].


where vk(x)are the complementary Lidstone polynomials of degree k[27]. The kernel is


In Ref. [19], the proposed method applied to problem (2) with conditions (64) and (67), respectively, has been examined in detail.

5.2.3. Other special boundary conditions

If r=n1and [a,b]=[0,1], we can consider Bernoulliboundary conditions [21]


with βk, k=0,,n1real constants. The method has been examined in [14].

5.3. Multipoint boundary value problems

Let us now consider [15] the following conditions in I=[1,1]


In this case




and lk(t)are the fundamental Lagrange polynomials on the points xj,j=1,,rs. Pr1(x)is the unique polynomial of degree r1which satisfies the Birkhoff interpolation problem


with 1<x1<<xrs1. Hence, the solution of problem (2), with multipoint conditions (71), is


with Pr1[y](x)given in Eq. (72) and


Observe that Eq. (74) is a special type of Birkhoff interpolation problem with incidence matrix E=(eij)defined by e1j=eis=1,j=0,,s1,i=2,,rs+1,eij=0otherwise and r1.

In Ref. [23], Pr1[y](x)is presented in a little different form:


where Es(x,lk(x))=1x1xslk(t)dtdt.

Let us now consider the following conditions [12, 20]


The solution to the Birkhoff interpolation problem


with 1<x1<<xr2<1is [12]






Hence, the solution of problem (2) is


with Pr1[y](x)given in Eq. (80) and


6. Numerical examples

In this section, we present some numerical results obtained by applying method (15), which we call CGN method, to find numerical approximations yr,m(x)to the solution of some test problems. In order to solve the nonlinear system (19), we use the so-called modified Newton method [29] (the same Jacobian matrix is used for more than one iteration) and we use algorithm (44) for the computation of the entries of the matrix, when polynomials pr,i,m(x)are not explicitly known. Since the true solutions of the analyzed problems are known, we consider the error function em(x)=|y(x)yr,m(x)|.

The maximum values of em(x)over the interval [a,b]have also been calculated by using Matlab, particularly the built-in solvers

  • ode15s, a variable-step, variable-order multistep solver based on the numerical differentiation formulas of orders 1–5;

  • ode45, a single-step solver, based on an explicit Runge-Kutta (4, 5) formula, the Dormand-Prince pair

for initial value problems, and the finite difference codes;

  • bvp4c(with an optional mesh of 200 points) that implements the three-stage Lobatto IIIa formula;

  • bvp5cthat implements the four-stage Lobatto IIIa formula.

for boundary value problems.

All solvers have been used with optional parameters RelTol=AbsTol=1e−17.

Moreover, the powerful tool Chebfun[30] has been used.

Example 1Consider the following linear ninth-order BVP [28]


with exact solution y(x)=(1x)ex.

The unique polynomialP8(x)=P8[y](x)of degree 8 satisfying the boundary conditionsP8(j)(0)=1jforj=0,,4,andP8(j)(1)=j ej=0,,3is


From Eq. (7), we get


Now we calculate the values of the integrals (39) by using Eq. (45), and we solve system (26). Thus, we obtain the approximate solution (15) to problem (85).

Table 1shows the numerical results. The absolute errors are compared with those obtained in Ref. [28], where a modified decomposition method is applied for the solution of problem (85). The second and third columns ofTable 1show the error, respectively, in the method in Ref. [28] and in the CGN method, using in both cases polynomials of degree 12. The last column contains the error in the approximation by a polynomial of degree 14 using CGN method. As collocation points, equidistant nodes in[0,1]are chosen. Analogous results are obtained by using Chebyshev nodes of first and second kind, and Legendre-Gauss-Lobatto points.

xMethod in [28]CGNm=4CGNm=6

Table 1.

Absolute error em(x)in MDMand CGNmethods for problem (85).

The maximum absolute errormax{em(x)}on[0,1]has also been calculated by using Matlab( Table 2 ).


Table 2.

Maximum absolute error in problem (85) using Matlab built-in functions.

Example 2Consider the fifth-order initial value problem [13]


with solutiony(x)=ex2.

Table 3shows the absolute error in some points of the interval[0,1]for CGN method in the case, respectively, of Chebyshev nodes of first kind(Cheb I), of second kind(Cheb II) and in the case of equidistant nodes(EqPts).

xCheb ICheb IIEqPts

Table 3.

Problem (88)—example 2.

The maximum absolute errors calculated by using Matlab are displayed inTable 4.


Table 4.

Maximum absolute error in problem (88) using Matlab built-in functions.

Example 3Consider now the following nonlinear problem [31]


with exact solutiony(x)=sin(x).

This kind of problems models several nonlinear phenomena such as traveling waves in suspension bridges [32] or the bending of an elastic beam [33].

Suspension bridges are generally susceptible to visible oscillations, due to the forces acting on the bridge (including the force due to the cables which are considered as a spring with a one-sided restoring, the gravitation force and the external force due to the wind or other external sources).frepresents the forcing term, whileyrepresents the vertical displacement when the bridge is bending.

In the case of elastic beam, frepresents the force exerted on the beam by the supports.xmeasures the position along the beam(x=0is the left-hand endpoint of the beam), yand yindicate, respectively, the height and the slope of the beam atx. ymeasures the curvature of the graph ofy, and, in physical terms, it measures the bending moment of the beam atx, that is, the torque that the load places on the beam atx.

The considered boundary conditions state that the beam has both endpoints simply supported. Moreover, the derivative of the deflection function is not zero at those points, and it indicates that the beam at the wall is not horizontal.

Table 5shows the comparison between the NMD method presented in Ref. [31] and the CGN method withm=5and m=9, respectively. The approximating polynomial of NMD method has degree 11, while the polynomial considered in CGN method form=5has degree 8.


Table 5.

Error of NMDand CGNmethods—problem (89).

The maximum absolute errors calculated by using Matlab are displayed inTable 6.


Table 6.

Maximum absolute error in problem (89) using Matlab build-in functions.


  1. 1. Davis P.Interpolation and approximation. Dover, New York. 1975.
  2. 2. Agarwal R.Boundary value problems for higher order differential equations. World Scientific Publishing Co., Inc., Teaneck, NJ. 1986.
  3. 3. Agarwal R, Wong P.Lidstone polynomials and boundary value problems. Computers and Mathematics with Applications. 1989;17(10): 1397–1421.
  4. 4. Hairer E, Nørsett S, Wanner G.Solving ordinary differential equations I. Nonstiff problems. Berlin: Springer-Verlag. 1987.
  5. 5. Henrici P.Discrete variable methods in ordinary differential equations. Wiley, New York. 1962.
  6. 6. Strikwerda J.Finite difference schemes and partial differential equations. SIAM., Philadelphia, PA. 2004.
  7. 7. Caglar H, Caglar N, Elfaituri K.B-spline interpolation compared with finite difference, finite element and finite volume methods which applied to two-point boundary value problems. Applied Mathematics and Computation. 2006;175(1): 72–79.
  8. 8. Chang J, Yang Q, Zhao L.Comparison of b-spline method and finite difference method to solve bvp of linear odes. Journal of Computers. 2011;6(10): 2149–2155.
  9. 9. Costabile F, Gualtieri MI, Serafini G.Cubic Lidstone-Spline for numerical solution of BVPs. submitted.
  10. 10. Khan A.Parametric cubic spline solution of two point boundary value problems. Applied Mathematics and Computation. 2004;154(1): 175–182.
  11. 11. Boyd J.Chebyshev and Fourier spectral methods. 2nd edition, Dover, Mineola, NY. 2000.
  12. 12. Costabile F, Longo E.A Birkhoff interpolation problem and application. Calcolo. 2010;47(1): 49–63.
  13. 13. Costabile F, Napoli A.A class of collocation methods for numerical integration of initial value problems. Computers and Mathematics with Applications. 2011;62(8): 3221–3235.
  14. 14. Costabile F, Napoli A.Numerical solution of high order Bernoulli boundary value problems. Journal of Applied Mathematics. 2014, Article ID 276585. doi: 10.1155/2014/276585.
  15. 15. Costabile F, Napoli A.A method for high-order multipoint boundary value problems with Birkhoff-type conditions. International Journal of Computer Mathematics. 2015;92(1): 192–200.
  16. 16. Costabile F, Longo E.A new collocation method for a BVP. Applied and Industrial Mathematics in Italy III, 289–297. 2009;3: 289–297. (Ser. Adv. Math. Appl. Sci., 82, World Sci. Publ., Hackensack, NJ. 2010)
  17. 17. Costabile F, Napoli A.A method for global approximation of the solution of second order IVPs. Rendiconti del Circolo Matematico, Ser. II. 2004;24: 239–260.
  18. 18. Costabile F, Napoli A.A method for polynomial approximation of the solution of general second order BVPs. Far East Journal of Applied Mathematics. 2006;25(3): 289–305.
  19. 19. Costabile F, Napoli A.Collocation for high-order differential equations with Lidstone boundary conditions. Journal of Applied Mathematics. 2012, Article ID 120792. doi: 10.1155/2012/120792.
  20. 20. Costabile F, Napoli A.A multipoint Birkhoff type boundary value problem. Journal of Numerical Mathematics. 2015;23(1): 1–11.
  21. 21. Costabile F, Serpe A, Bruzio A.No classic boundary conditions. In: Proceedings of World Congress on Engineering 2007; July 2–4, 2007, London 918–921.
  22. 22. Costabile F, Napoli A.Collocation for high order differential equations with two-points Hermite boundary conditions. Applied Numerical Mathematics. 2015;87: 157–167.
  23. 23. Dehghan M, Aryanmehr S, Eslahchi M.A technique for the numerical solution of initial-value problems based on a class of Birkhoff-type interpolation method. Journal of Computational and Applied Mathematics. 2013;244: 125–139.
  24. 24. Wang L, Samson M, Zhao X.A well-conditioned collocation method using a pseudospectral integration matrix. SIAM Journal on Scientific Computing. 2014;36(3): 907–929.
  25. 25. Costabile F, Napoli A.A method for global approximation of the initial value problem. Numerical Algorithms. 2001;27(2): 119–130.
  26. 26. Coleman J, Booth A.The Chebyshev methods of Panovsky and Richardson as Runge-Kutta-Nyström methods. Journal of Computational and Applied Mathematics. 1995;61(3): 245–261.
  27. 27. Costabile F, DellAccio F, Luceri R.Explicit polynomial expansions of regular real functions by means of even order Bernoulli polynomials and boundary values. Journal of Computational and Applied Mathematics. 2005;176(1): 77–90.
  28. 28. Wazwaz AM.Approximate solutions to boundary value problems of higher order by the modified decomposition method. Computers and Mathematics with Applications. 2000;40(6): 679–691.
  29. 29. Quarteroni A, Sacco R, Saleri F.Numerical mathematics. Second edition. Texts in Applied Mathematics, 37. Springer-Verlag: Berlin. 2007.
  30. 30. Driscoll TA, Hale N, Trefethen NL.Chebfun guide. Pafnuty Publications: Oxford. 2014.
  31. 31. Noor MA, Mohyud-Din ST.An efficient method for fourth-order boundary value problems. Computers and Mathematics with Applications. 2007;54(7): 1101–1111.
  32. 32. Lazer A, McKenna P.Large-amplitude periodic oscillations in suspension bridges: some new connections with nonlinear analysis. Siam Review. 1990;32(4): 537–578.
  33. 33. Yang B.Estimates of positive solutions to a boundary value problem for the beam equation. Communications in Mathematical Analysis. 2007;2(1): 13–21.

Written By

Francesco Aldo Costabile, Maria Italia Gualtieri and Anna Napoli

Submitted: May 15th, 2016 Reviewed: November 21st, 2016 Published: March 15th, 2017