Absolute error in MDM and CGN methods for problem (85).
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
The relationship between interpolation and differential equations theories has already been considered. In Ref. (, p. 72), Davis observed that the Peano kernel in the interpolation problem
is the Green’s function of the differential problem
where , being 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” .
Later, Agarwal (, p. 2), Agarwal and Wong (, 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, [4–6] and references therein) approximate the solution of a boundary value problem by a sequence of overlapping polynomials which interpolate 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.
Here, we take into account a more general nonlinear initial/boundary/multipoint value problems for high-order differential equations
where , , , and are linearly independent functionals on . Moreover, we suppose that the function is continuous at least in the interior of the domain of interest, and it satisfies a uniform Lipschitz condition in , which means that there exists a nonnegative constant , such that, whenever and are in the domain of , the following inequality holds
If , then (2) is an initial value problem (IVP); if , then (2) is a boundary value problem (BVP); if , , then (2) is a multipoint value problem (MVP).
In this chapter,
- we assume that the conditions for the existence and uniqueness of solution of problem (2) in a certain appropriate domain of are satisfied and that the solution is differentiable with continuity up to what is necessary;
- we get the Fredholm integral equation related to problem (2), by polynomial interpolation and the Peano kernel of the linear interpolation problem . In this way, we point out the close relationship between Green’s function and Peano kernel;
- 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 (, 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
with , , linearly independent functionals on , has the unique solution
Proof. Since the , are linearly independent, the result follows from the general linear interpolation theory.
Proposition 2 If y ∈ C r ( I ) and L i [ y ] ( x ) = w i , i = 0, … , r − 1 , x ∈ I , then
with , , , and
where index means that is considered as a function of .
Proof. It follows by observing that and from Peano kernel Theorem .
Theorem 1 With 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 1 It results
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
Let be distinct points in and denoted by , the fundamental Lagrange polynomials on the nodes , that is
Theorem 2 If the solution of Eq. (8) is in , then
and the remainder term is given by:
being a suitable point of the smallest interval containing and all , .
Proof. From Lagrange interpolation
Theorem 2 suggests to consider the implicitly defined polynomial
For polynomial (15), the following theorem holds.
Theorem 3 (The main Theorem). Polynomial (15), of degree r + m − 1 , satisfies the relations
that is, is a collocation polynomial for Eq. (2) at nodes , .
Proof. From (15), Corollary 1 and the linearity of operators , we get . By Theorems 1 and 2, we obtain , and from Eq. (11), . Hence, relations (16) follow.
Remark 1 (Hermite-Birkhoff-type interpolation). Theorem 3 is equivalent to the general Hermite-Birkhoff interpolation problem : given w i ∈ R , i = 0, … , r − 1 , and α j ∈ R , j = 1, … , m , determine, if there exists, the polynomial Q ( x ) ∈ P m + r − 1 such that
Remark 2 In the case of IVPs, for each method (15), we can derive the corresponding implicit Runge-Kutta method. For example, for r = 2 , let b = x 0 + h and x i = x 0 + c i h with c i ∈ [ 0,1 ] . With the change of coordinates x = x 0 + t h , t ∈ [ 0,1 ] , we can write
Putting we have
Eqs. (19) and (20) are the well-known continuous Runge-Kutta method for second-order differential equations. Particularly, for , we have the implicit Runge-Kutta-Nystrom method.
4. Algorithms and implementation
To calculate the approximate solution of problem (2) by polynomial at , we need the values , , . In order to get these values, we propose the following algorithm:
- Put , , and consider the following system
, , where .
System (26) can be written in the form
From Eq. (27), we get
or, putting ,
For the existence and uniqueness of solution of system (34), we can prove, with standard technique, the following theorem.
Theorem 5 If , system (34) has a unique solution which can be calculated by an iterative method
with a fixed and
Moreover, if Y is the exact solution,
Remark 3 If f is linear, then system (27) is a linear system which can be solved by a more suitable method.
Remark 4 System (27) can be considered as a discrete method for the numerical solution of (2).
Remark 5 Method (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 of the matrix A in Eq. (27), we have to compute the integrals
for . Integrating by parts, it remains to solve the problem of the computation of
. To this aim, it suffices to compute
where or , ,
For the computation of the integral (41), we use the recursive algorithm introduced in Ref. : for each , let us consider the new points if , and if . Moreover, let us define and for
Thus, if , then
Remark 6 An 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:
determine the interpolation polynomial satisfying the boundary conditions and compute the Peano remainder;
approximate by Lagrange interpolation on a set of fixed nodal point;
compute the elements of matrix A (28) and solve system (26);
obtain polynomial (15).
5. Some particular cases
5.1. Initial value problems
has been considered, while in Ref. , the authors introduced the more general equation
In both cases
Particularly, for and , in the case of zeros of Chebyshev polynomials of first kind, we get
where and are the Chebyshev polynomials of the first kind and degree and , respectively, and
In the case of zeros of Chebyshev polynomials of second kind
In Ref. , Coleman and Booth used also a polynomial interpolant of degree for , but they started from an identity different to Eq. (8) and derived a collocation method for which the nodes are the zeros of Chebyshev polynomials of second kind.
5.2. Boundary value problems
For , for the exact solution of the second-order BVP
, it is known that
By applying method (15), we get 
If , , we obtain explicitly the expression of 
The same method has been presented in Ref. , where also stability has been studied.
Now assume and . Several types of boundary conditions can be considered.
-Hermite boundary conditions :
with , real constants.
In this case, is the Hermite polynomial of degree
The kernel is
-Lidstone boundary conditions :
where , are real constants.
In this case, is the Lidstone interpolating polynomial  of degree
where are the Lidstone polynomials of degree , and the function is
If we consider the following boundary conditions
where are the complementary Lidstone polynomials of degree k . The kernel is
In Ref. , the proposed method applied to problem (2) with conditions (64) and (67), respectively, has been examined in detail.
5.3. Multipoint boundary value problems
Let us now consider  the following conditions in
In this case
and are the fundamental Lagrange polynomials on the points . is the unique polynomial of degree which satisfies the Birkhoff interpolation problem
with . Hence, the solution of problem (2), with multipoint conditions (71), is
with given in Eq. (72) and
Observe that Eq. (74) is a special type of Birkhoff interpolation problem with incidence matrix defined by otherwise and .
In Ref. , is presented in a little different form:
The solution to the Birkhoff interpolation problem
with is 
Hence, the solution of problem (2) is
with 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 to the solution of some test problems. In order to solve the nonlinear system (19), we use the so-called modified Newton method  (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 are not explicitly known. Since the true solutions of the analyzed problems are known, we consider the error function .
The maximum values of over the interval 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;
bvp5c that 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  has been used.
Example 1 Consider the following linear ninth-order BVP 
with exact solution .
The unique polynomial P 8 ( x ) = P 8 [ y ] ( x ) of degree 8 satisfying the boundary conditions P 8 ( j ) ( 0 ) = 1 − j for j = 0, … ,4, and P 8 ( j ) ( 1 ) = − j e j = 0, … ,3 is
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 1 shows the numerical results. The absolute errors are compared with those obtained in Ref. , where a modified decomposition method is applied for the solution of problem (85). The second and third columns of Table 1 show the error, respectively, in the method in Ref.  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 are chosen. Analogous results are obtained by using Chebyshev nodes of first and second kind, and Legendre-Gauss-Lobatto points.
|x||Method in ||CGN||CGN|
The maximum absolute error on has also been calculated by using Matlab ( Table 2 ) .
Example 2 Consider the fifth-order initial value problem 
with solution .
Table 3 shows the absolute error in some points of the interval 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).
|x||Cheb I||Cheb II||EqPts|
The maximum absolute errors calculated by using Matlab are displayed in Table 4 .
Example 3 Consider now the following nonlinear problem 
with exact solution .
This kind of problems models several nonlinear phenomena such as traveling waves in suspension bridges  or the bending of an elastic beam .
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). represents the forcing term, while represents the vertical displacement when the bridge is bending.
In the case of elastic beam, represents the force exerted on the beam by the supports. measures the position along the beam (is the left-hand endpoint of the beam), and indicate, respectively, the height and the slope of the beam at . measures the curvature of the graph of , and, in physical terms, it measures the bending moment of the beam at , that is, the torque that the load places on the beam at x .
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 5 shows the comparison between the NMD method presented in Ref.  and the CGN method with and , respectively. The approximating polynomial of NMD method has degree 11, while the polynomial considered in CGN method for has degree 8.
The maximum absolute errors calculated by using Matlab are displayed in Table 6 .