The Algebraic Structure of an Implicit Runge-Kutta Type Method

Abstract

In this paper, the theory of linear transformation (Homomorphism) and monomorphism is applied to a first-order Runge-Kutta Type Method illustrated in a Butcher Table and the extended second order Runge- Runge-Kutta type Method to substantiate their uniform order and error constants obtained. A homomorphism is a mapping from one group to another group which preserves the group operations. It’s sometimes called the operation preserving function. The methods which initially are Linear Multistep were reformulated into Runge-Kutta (R-K) Type to establish the advantages the R-K has over Linear Multistep. The first-order Linear multistep was reformulated into first-order R-K type which was further extended to second order. This extension can be made to higher order. For this study, the extension was limited to the second order.

Introduction

I. INTRODUCTION

 A function  T  between two vector spaces T:V→W  that preserves the operations of addition if v1  and v2 ? V  then

Tv1+v2=Tv1+T(v2)                                                                                              (1)

And scalar multiplication if v ? V  and r ? R , then

Trv=rT(v)                                                                                                                       (2)

is a homomorphism or linear Transformation, Agam (2013).

A homomorphism that is one-to-one or a mono is called a monomorphism. The monomorphism transformation preserves its algebraic structure and the order of the domain in its Range.

Reference [2,4] extended the general Linear method to the case in which the second derivative, as well as the first derivative, can be calculated. They constructed methods of third and fourth order which are A-stable, possess the Runge-Kutta stability property, and have a diagonally implicit structure for efficient implementation. However, they concentrated on only linear problems for which it is possible to compute accurate starting methods, the general-purpose starting methods for non-linear problems were not developed. Reference [5-7,10] presented a direct integration of second-order Ordinary Differential Equation using only the Explicit Runge-Kutta Nystrom (RKN) method with a higher derivative. They derived and tested various numerical schemes on standard problems. Due to the limitations of Explicit Runge-Kutta (ERK) in handling stiff problems, the extension to higher order Explicit Runge-Kutta Nystrom (RKN) was considered and results obtained showed an improvement over conventional Explicit Runge-Kutta schemes. The Implicit Runge-Kutta scheme was however not considered. [8] derived an implicit 6-stage block Runge-Kutta Type Method for direct integration of second-order (special or general), third-order (special or general) as well as first-order initial value problems and boundary value problems. The theory of Nystrom was adopted in the reformulation of the methods [6].

The convergence and stability analysis of the method were conducted, and the region of absolute stability was plotted. The method was A-stable, possessed the Runge-Kutta stability property, had an implicit structure for efficient implementation, and produced simultaneous approximation of the solution of both linear and nonlinear initial value problems.

A. Consistency of Runge Kutta Methods

The first and second-order Ordinary Differential Equation (ODE) methods are said to be consistent if

φx,yx,0≡f(x,y(x))                                                                                        (3)

φx,yx,y'x,0≡f(x,yx,y'x)                                                                   (4)

holds respectively.

Note that consistency demands that 1sbs=1                                                        (5)

 and

 1sbs=12                                                                                                                                                               (6)

 for first and second order respectively. Also  1sbs  is as shown in the butcher array table.

A=aij=β2                        A=aij=β               β=βe  

B. Convergence of Runge –Kutta Methods

If y'=fx,yx;   y''=fx,yx,y'x  represents first and second order respectively, then for such method consistency is necessary and sufficient for convergence. Hence the methods are said to be convergent if and only if they are consistent [1].

II. METHODOLOGY

 Proposition: Let T  be a linear transformation that is continuously differentiable on a set of ordered three-tuple vector in R3  as follows.

Vi=(x+cih, y+j=1saij Tvj, y'+j=1saijT'(vj))∈ R3                                   (7)                                  

TVi=h(y'+j=1saijT'(vj))                                                                                                          (8)                                                                                                        

and                                                                                                                                                                                              

T'vi=hfx+cih,y+j=1saij Tvj, y'+j=1saijT'vj=hmi                                    (9)                                                           

i:e  mi=fx+cih,y+j=1saij Tvj, y'+j=1sai??T'vj                                  (10)                                                                                        

Then the Transformation T:R3→R  is a well-defined monomorphism:

Proof:

 Let u,v ? R  be defined by

U=(x+cih, y1+j=1saij Tuj, y1'+j=1saijT'(uj))                                                             (11)                       

V=(x+cih, y2+j=1saij Tvj, y2'+j=1saijT'(vj))                                                               (12)                                                       

TU+V=h(y1'+y2'+j=1saij (T'(uj)+T'(vj))                                                    (13)                                                                                                                          

By the definition of T on R3

TU+V=hy1'+j=1saijT'uj+h(y2'+j=1saijT'(vj))                                                 (14)                                        

TU+V=TU+T(V)                                                                                           (15)

Tk.U=k.T(U)                                                                                                       (16)  

Hence T  is a homomorphism

Now we show that T  is 1-1

Let u,v ?R3  with

Tu=Tv                                                                                                                                                            (17)

By definition of T                                                                                                             

⇒h(y1'+j=1saij T'uj)=h(y2'+j=1saij T'vj)                                                                  (18)                                                                                           

Since

Tu=Tv  then Tuj=T(vj)  and T'uj=T'vj                                                               (19)                                                                                                           

y1=y2  and x1+cih= x2+cih  i:e  x1=x2                                                                             (20)

Hence U=V                                                                                                                                         (21)

 Thus, T is 1-1⇔  a monomorphism from R3→R

Remark: The necessity for the above proposition is to ensure that the algebraic structure and the order do not change during the transformation. We consider the case k=1 . The Runge-Kutta type method is obtained from the Reformulation of a Linear Multistep Method of the same step number and is given as:

yn+12  =yn+h(34k2-14k3)yn+1= yn+hk2                                                                                               (22)                                                                                            

Where

k1=f(xn,yn )

  k2=f(xn+12h,yn+h0k1+34k2-14k3)

k3=f(xn+h,yn+h{0k1+k2+0k3)

Putting the coefficients of (22) in the Butcher Table we obtained Table 1

Table I: The Butcher Table for k=1

Extending the method (22) with the coefficients as characterized in the butcher array for second order as

A=aij=β2                        A=aij=β
              β=βe   gives

Table II: The Butcher Table for Second Order for K=1

The Table I satisfies the Runge-Kutta conditions for the solution of first-order ODE since

i     j=1saij=ci                                                                                                                               (23)                                                                                                                

ii    j=1sbj=1                                                                                                                                  (24)                                                                                                                              

We consider the general second-order differential equation in the form

y''=f(x,y,y') , yx0=y0    y'(x0)  =    y0'                                                                                 (25)                                                                                                                      

y''=fv,           v=(x, y,y')                                                                                                          (26)                                                                                         

TVi=Tx+cih, y+j=13aijTVj ,y'+j=13aijT'Vj                                   (27)                                                  

          = h (y'+j=13aij T'(Vj))                                                                                          (28)

=h (y'+j=13aij hmj)                                                                                         (29)      

TV1=hy'+0hm1+0hm2+0hm3 ⇒TV1=hy'                                      (30)                                                                                                                    

TV2=hy'+0hm1+34hm2-14hm3

⇒TV2=h(y'+34hm2-14hm3)                                                                               (31)                                                                             

TV3=hy'+0hm1+hm2+0hm3

⇒TV3=hy'+hm2                                                                                                   (32)                                                                                                

Also

mi=T'Vj=fx+cih, y+j=1saijTVj, y'+j=1saijT'Vj   (33)                                                            

m1=fx+0h, y+0+0+0=  m1=f(x,y)                                                                       (34)                                                                                                                                                                         

m2=f(x+12h, y+12hy'+516h2m2-316h2m3, y'+34hm2-14hm3)                    (35)                   

m3=f(x+h, y+hy'+34h2m2-14h2m3,y'+hm2 )                                            (36)           

The direct method for solving y''=f(x,y,y')  is now

yn+1=yn+b1TV1+b2TV2+b3T(V3)                                                                       (37)      

yn+1=yn+0TV1+TV2+0T(V3)                                                                               (38)         

yn+1=yn+TV2                                                                                                                 (39)

yn+1=yn+hyn'+34hm2-14hm3                                                                          (40)

yn+1=yn+hyn'+h243m2-m3                                                                               (41)        

yn+1'=yn'+b1T'V1+b2T'V2+b3T'V3                                                                                (42)                                                       

yn+1'=yn'+0hm1+hm2+0hm3                                                                                                      (43)                                                                   

yn+1'=yn'+hm2                                                                                                          (44)

III. RESULTS AND DISCUSSION

We made use of the coefficients of the Butcher table of the first-order RKTM to prove the second-order RKTM. Equations (40) and (44) satisfy the Runge-Kutta consistency conditions of second and first order respectively. This further shows that it is a monomorphism.

Conclusion

This research work established the reason behind the uniform order and error constant of the first-order Runge-kutta type method and the extended second-order Runge-kutta type method. Also why the algebraic structure and the order of the two methods are preserved and not changed during the transformation. Data Availability: The article includes the information necessary to understand the results of this investigation.

References

[1] Adegboye, Z.A (2013), Construction and implementation of some reformulated block implicit linear multistep method into Runge-Kutta type method for initial value problems of general second and third order ordinary differential equations. Unpublished doctoral dissertation, Nigerian Defence Academy, Kaduna . [2] Agam, A.S (2012), A sixth order multiply implicit Runge-Kutta method for the solution of first and second order ordinary differential equations. Unpublished doctoral dissertation, Nigerian Defence Academy, Kaduna . [3] Butcher, J.C & Hojjati, G. (2005). Second derivative methods with Runge-Kutta stability. Numerical Algorithms, Vol.40, 415-429. [4] Chollom J.P.,Olatun-bosun I.O, & Omagu S. (2012). A class of A-stable block explicit methods for the solutions of ordinary differential equations. Research Journal of Mathematics and Statistics, Vol. 4(2),52-56. [5] Kendall, E. A (1989). An introduction to numerical analysis, (2nd ed), John Wiley & Sons.367. [6] Okunuga, S.A, Sofulowe, A.B, Ehigie, J.O, & Akanbi, M.A. (2012). Fifth order 2-stage explicit runge kutta nystrom (erkn) method for the direct integration of second order ode. Scientific Research and Essays, Vol. 7(2), 134-144. [7] Yahaya Y.A. and Adegboye Z.A. (2013). Derivation of an implicit six-stage block Runge- Kutta type method for direct integration of boundary value problems in second order ode using the Quade type multistep method. Abacus, Vol.40(2), 123-132. [8] Yahaya, Y.A. & Badmus, A.M. (2009). A class of collocation methods for general second-order ordinary differential equations. African Journal of Mathematics and Computer Science Research 2(4), 69-72.

Copyright

Copyright © 2024 Raihanatu Muhammad, Abdulmalik Oyedeji. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.