Fully Implicit Four Point Block Backward Difference Formulae for Solving First Order Initial Value Problems
Umaru MOHAMMED and Yusuph Amuda YAHAYA
Maths/Computer Science Department, Federal University of Technology, Minna, Nigeria.
E-mails: digitalumar@yahoo.com, yusuphyahaya@yahoo.com
(^{* }Corresponding author)
Abstract
The four steps Backward Differentiation Formulae (BDF) were reformulated for applications in the continuous form. The process produces some schemes which are combined in order to form an accurate and efficient block method for parallel or sequential solution of ordinary differential equations (ODE’s). The suggested approach eliminates requirement for a starting value and its speed proved to be up when computations with the Block Discrete schemes were used.
Keywords
Backward Differentiation Formulae (BDF); Block Method; Parallelism; Sequential.
Introduction
Consider the initial value problems for the system/scalar ordinary differential equations (ODEs).
(1)
In the literature, conventional linear multistep methods including hybrid ones have been made continuous through the idea of multistep collocation (MC) [1-5]. The Continuous Multistep Method (CMM) method produces piece-wise polynomial solutions over K-steps [X_{n}, X_{n+k}] for the first order systems/scalar ODEs. Of note, is that the implicit [CMM] interpolant (12) is not to be directly use as the numerical integrator, but the resulting discrete multistep Schemes which is derived from it, which will now be self- starting and can be applied for parallel or sequential solutions of both the initial and boundary value problems.
In this paper is part of research effort to reformulate for efficient and accurate use, the linear multistep methods and four step block differentiation formulae (BDF) is considered here.
Derivation of proposed approximate solution
Def 1.1 A-Stable (Dahlqquist [6])
A numerical method is said to be A-stable if its region of absolute stability contains, the whole of the left-hand half-plane
Definition 1.2:A(α) stable (Widluid [7])
A numerical method is said to be , if its region of absolute stability contains the infinite wedge; it is said to be A (0) - stable if it is stable for some (sufficiently small)
Definition 1.3
A block method is zero-stable provided the roof s of the first characteristics polynomial specified as satisfies and for those roots with the multiplicity must not exceed two. The principal root of is denoted by
General multistep collocation (MC) Linked to Continuous Multistep Method (CMM)
Let us first give a general description for the method of multistep collocation (MC) and its link to Continuous Multistep Method (CMM) for (1). In the equation (1), f is given and y is sought as
(2)
where
x_{n} ≤x≤x_{n+k}, where n = 0, k, … n-k, T = “Transpose of”
Equation (2) can be re-written as
(3)
The unknown coefficients a_{1}, a_{2}, … a_{p} are determined using respectively the r (0<r<=k) interpolation conditions and the s>0 distinct collocation conditions, p=r+s as follows
(4)
This is a system of p linear equations from which we can compute values for the unknown coefficients provided (4) is assumed non-singular, for the distinct points x_{i} and c_{i} the non-singular system is guaranteed (see proof in Yusuph and Onumanyi 2002). We can write (4) as a single set of linear equations of the form
(5)
Where (6)
Substituting the vector a, given by (5) and F by (6) into (3) gives
(7)
Equation (7) is the continuous MC Interpolant C^{T} known explicitly in the form
(8)
Or
(9)
Where from (8)
(10)
Therefore,
(11)
where are given by (10). Hence (11) with (10) is the CMM interpolant with uniform or variable step-size.
We propose an approximate solution to (1) in the form
(12)
with m = 0, t = 4 and p = m+t -1 also are the parameters to be determined where p is the degree of the polynomial interpolant of our choice. Specifically, we interpolate equation (12) at using the method described in this paper; we obtain a continuous form for the solution from the system of the equation in the matrix below.
The general form of the new method is expressed a
The matrix D of the new method expressed as:
Matrix D in the equation above, which when solved either by matrix inversion techniques or Gaussian elimination method to obtain the values of the parameters j = 0,1,(m+t-1) and then substituting them into equation (12) give a scheme expressed in the form.
If we now let k=4, after some manipulation we obtain a continuous form of solution.
(13)
Differentiating equation (13) once, yielded
(14)
Evaluating (14) at x=x_{n+4}, we obtain
(15)
This is the existing method of (BDF) (see Lambert [8], [9]) of order four (4) with error constant E = 12h^{5}y^{5}/125.
Evaluating equation (14) at point x = x_{n+3}, x = x_{n+2}, and x = x_{n+1}we obtain respectively
(16)
Equation (15) and (16) constitute the member of a zero-stable block integrators of order (4,4,4,4)^{T} with the application of the block integrators with n=0 give the accurate values of along with as shown in table (1-2 )
To start the IVP integration on the sub-interval [x_{0}, x_{4}]. We combine (15) and (16), when n=0 i.e the 1-block 4 point method as given in equation (17) produces its unknown simultaneously without recourse to any starting method(predictor) to generate before computing using equation (15) in the main method (see Lambert [6,7] . Hence this is an improvement over this reported works. Though, this does not becloud the contribution of these authors.
Results and Discussion
Recall, that, it is a desirable property for a numerical integrator to produce solution that behave similar to the theoretical solution to a problem at all times. Thus several definitions, which call for the method to possess some “adequate” region of absolute stability, can be found in several literatures. See Lambert [8], Fatunla [10,11]etc. following Funtula [10], the four integrator proposed in this report in equations (15) and (16) are put in the matrix-equation form and for easy analysis the result was normalized to obtain;
(17)
The first characteristic polynomial of the proposed 1-block 4 step method is
(18)
This implies, R_{1} = R_{2} = R_{3} = 0, R_{4} = 1
From definition (1.3) and equation (18), the 1 block 4-point is zero stable and is also consistent as its order (4,4,4,4)^{ T} >1, thus, it is convergent, following Henrici [12]
Remarks 4.1
Using the matlab package, we were able to plot the stability region of the proposed block method. This is done by reformulating a block method as general linear method to obtain the values of the matrices A,B,U,V which are then substituted into stability matrix and stability function. Then the utilized maple package yield the stability polynomial of the block method. Using a matlab program we plot the absolute stability region of proposed four step block backward differentiation formulae (BDF).
Figure 1. Region of Absolute Stability
From definition (1.2) and figure (1) above the proposed four point block (BDF) method (17) is stable.
Numerical Experiment
To illustrate the potentials of the new formulas constructed in this paper, we will compare their performance on the same problem when (BDF) scheme is used singly. (Note that is not self starting) we shall use other (BDF) for k=1, 2, 3 to get it started (ie to obtain y_{1,} y_{2,} y_{3}). While the proposed four points block (BDF) type method is self starting on its own.
Consider the initial value problem
Table 1. Proposed (BDF) block method
N |
X |
Approx value |
Exact value |
Error |
0 |
1 |
1.0000000000 |
1.0000000000 |
0 |
1 |
0.1 |
0.9048399472 |
0.9048374180 |
2.5292000001E-06 |
2 |
0.2 |
0.8187328468 |
0.8187307531 |
2.0937000000E-06 |
3 |
0.3 |
0.7408202286 |
0.7408182207 |
2.0078999999E-06 |
4 |
0.4 |
0.6703216658 |
0.6703200460 |
1.6198000000E-06 |
5 |
0.5 |
0.6065338205 |
0.6065306597 |
3.1608000001E-06 |
6 |
0.6 |
0.5488143655 |
0.5488116361 |
2.7293999999E-06 |
7 |
0.7 |
0.4965878495 |
0.4965853038 |
2.5457000000E-06 |
8 |
0.8 |
0.4493311354 |
0.4493289641 |
2.1713000000E-06 |
9 |
0.9 |
0.4065727605 |
0.4065696597 |
3.1008000000E-06 |
10 |
1.0 |
0.3678821594 |
0.3678794412 |
2.7182000000E-06 |
Table 2. k=4 (BDF) schemes only, using a starting value (y_{1,} y_{2,} y_{3}) computed from other(BDF)for k=1, 2,3
N |
X |
Approx value |
Exact value |
Error |
0 |
1 |
1.0000000000 |
1.0000000000 |
0 |
1 |
0.1 |
0.9090909091 |
0.9048374180 |
4.2534911000E-03 |
2 |
0.2 |
0.8238636362 |
0.8187307531 |
5.1328831000E-03 |
3 |
0.3 |
0.7454937301 |
0.7408182207 |
4.6755094000E-03 |
4 |
0.4 |
0.6744298736 |
0.6703200460 |
4.1098276000E-03 |
5 |
0.5 |
0.6102826374 |
0.6065306597 |
3.7519777000E-03 |
6 |
0.6 |
0.5523053404 |
0.5488116361 |
3.4937043000E-03 |
7 |
0.7 |
0.4908308572 |
0.4965853038 |
5.7544466000E-03 |
8 |
0.8 |
0.4276690805 |
0.4493289641 |
2.1659883600E-02 |
9 |
0.9 |
0.3691527030 |
0.4065696597 |
3.7416956700E-02 |
10 |
1.0 |
0.3185377346 |
0.3678794412 |
4.9341706600E-02 |
In this paper one block method was proposed and to test for their efficiency. One test example was solved with a derived block method. Their results were presented in tables 4.1-4.2. It will be observed that four step block backward differentiation method gives better result than when four step BDF scheme is using single. As it gives the smallest error.
However, the block method (BM) produces very accurate result, when compared with exact solution.
Conclusion
We have converted to continuous form the well known BDF. The continuous formulae are immediately employed as block method for direct solution of four point ivps. The direct solutions are in discrete form which can be substitution into the continuous formula for dense output. The proposed method is self starting, convergent and A(α) stable as shown by the plotted region of absolute stability. The method has been tested on simple ODEs and shown to perform satisfactory, without recourse to any other method to provide a starting value.
References
1. Lie I., Norset S.P., Supper Convergence for Multistep Collocation, Math. Comp, 1989, 52, p. 65- 79.
2. Onumanyi P., Awoyemi D.O., Jator S.N and Sirisena U.W., New linear Multistep with Continuous Coefficients for First Order Initial Value Problems, J. Nig. Math. Soc., 1994, 13, p. 37- 51
3. Onumanyi P., Jator S.N and Sirisena U.W., Continous Finite difference Approximate for Solving Differential Equations, J. Nig. Math. Soc., 1999, 1, p. 15- 27
4. Yusuph Y.A. and Onumayi p., New Multiple FDMS through multi step collocation for y^{”} = f(x, y), Abacus, 2002, 29(2), p. 92- 100
5. Yahaya Y.A., some theory and application of continous linear multi-step methods for ordinary differential equation, ph.D thesis (unpublished) university of jos, Nigeria,2004
6. Dahlquist, G., A special stability problem for linear multi step methods , BIT 3, 1963, p. 27-43
7. Widlund, O. B., note on unconditionally stable linear multistep methods BIT 7, 1967, p. 65-70.
8. Lambert J.D., Computational Methods in Ordinary Differential Equations, New York, John Wiley and Sons, 1973.
9. Lambert J.D., Numerical Method for Ordinary Systems, New York, John Wiley and Sons, 1991.
10. Fatunla S.O., Parallel methods for second order ODE`s computational ordinary differential equations, proceeding of computer conference (eds),1992, p. 87-99.
11. Fatunla S.O., Higher order parallel methods for second order ode`s, proceeding of fifth international conference on scientific computing (eds fatunla), 1994, p. 61-67.
12. Henrici P., Discrete variable methods for ode`s, New York USA, John Wiley and sons, 1962.