Implicit methods List of Runge–Kutta methods

1 implicit methods

1.1 backward euler
1.2 implicit midpoint
1.3 gauss–legendre methods
1.4 lobatto methods

1.4.1 lobatto iiia methods
1.4.2 lobatto iiib methods
1.4.3 lobatto iiic methods
1.4.4 lobatto iiic* methods
1.4.5 generalized lobatto methods


1.5 radau methods

1.5.1 radau ia methods
1.5.2 radau iia methods

implicit methods
backward euler

the backward euler method first order. unconditionally stable , non-oscillatory linear diffusion problems.

1


1





1






{\displaystyle {\begin{array}{c|c}1&1\\\hline &1\\\end{array}}}



implicit midpoint

the implicit midpoint method of second order. simplest method in class of collocation methods known gauss methods. symplectic integrator.

1

/

2


1

/

2





1






{\displaystyle {\begin{array}{c|c}1/2&1/2\\\hline &1\end{array}}}



gauss–legendre methods

these methods based on points of gauss–legendre quadrature. gauss–legendre method of order 4 has butcher tableau:

1
2


−



3

6






1
4






1
4


−



3

6








1
2


+



3

6






1
4


+



3

6






1
4









1
2






1
2









1
2


+


1
2




3






1
2


−


1
2




3








{\displaystyle {\begin{array}{c|cc}{\frac {1}{2}}-{\frac {\sqrt {3}}{6}}&{\frac {1}{4}}&{\frac {1}{4}}-{\frac {\sqrt {3}}{6}}\\{\frac {1}{2}}+{\frac {\sqrt {3}}{6}}&{\frac {1}{4}}+{\frac {\sqrt {3}}{6}}&{\frac {1}{4}}\\\hline &{\frac {1}{2}}&{\frac {1}{2}}\\&{\frac {1}{2}}+{\frac {1}{2}}{\sqrt {3}}&{\frac {1}{2}}-{\frac {1}{2}}{\sqrt {3}}\\\end{array}}}

the gauss–legendre method of order 6 has butcher tableau:

1
2


−



15

10






5
36






2
9


−



15

15






5
36


−



15

30








1
2






5
36


+



15

24






2
9






5
36


−



15

24








1
2


+



15

10






5
36


+



15

30






2
9


+



15

15






5
36









5
18






4
9






5
18







−


5
6






8
3




−


5
6








{\displaystyle {\begin{array}{c|ccc}{\frac {1}{2}}-{\frac {\sqrt {15}}{10}}&{\frac {5}{36}}&{\frac {2}{9}}-{\frac {\sqrt {15}}{15}}&{\frac {5}{36}}-{\frac {\sqrt {15}}{30}}\\{\frac {1}{2}}&{\frac {5}{36}}+{\frac {\sqrt {15}}{24}}&{\frac {2}{9}}&{\frac {5}{36}}-{\frac {\sqrt {15}}{24}}\\{\frac {1}{2}}+{\frac {\sqrt {15}}{10}}&{\frac {5}{36}}+{\frac {\sqrt {15}}{30}}&{\frac {2}{9}}+{\frac {\sqrt {15}}{15}}&{\frac {5}{36}}\\\hline &{\frac {5}{18}}&{\frac {4}{9}}&{\frac {5}{18}}\\&-{\frac {5}{6}}&{\frac {8}{3}}&-{\frac {5}{6}}\end{array}}}



lobatto methods

there 3 main families of lobatto methods, called iiia, iiib , iiic (in classial mathematical literature, symbols , ii reserved 2 types of radau methods). these named after rehuel lobatto. implicit methods, have order 2s − 2 , have c1 = 0 , cs = 1. unlike explicit method, s possible these methods have order greater number of stages. lobatto lived before classic fourth-order method popularized runge , kutta.

lobatto iiia methods

the lobatto iiia methods collocation methods. second-order method known trapezoidal rule:

0


0


0




1


1

/

2


1

/

2





1

/

2


1

/

2





1


0






{\displaystyle {\begin{array}{c|cc}0&0&0\\1&1/2&1/2\\\hline &1/2&1/2\\&1&0\\\end{array}}}

the fourth-order method given by

0


0


0


0




1

/

2


5

/

24


1

/

3


−
1

/

24




1


1

/

6


2

/

3


1

/

6





1

/

6


2

/

3


1

/

6





−


1
2




2


−


1
2








{\displaystyle {\begin{array}{c|ccc}0&0&0&0\\1/2&5/24&1/3&-1/24\\1&1/6&2/3&1/6\\\hline &1/6&2/3&1/6\\&-{\frac {1}{2}}&2&-{\frac {1}{2}}\\\end{array}}}

this methods a-stable, not l-stable , b-stable.

lobatto iiib methods

the lobatto iiib methods not collocation methods, can viewed discontinuous collocation methods (hairer, lubich & wanner 2006, §ii.1.4). second-order method given by

0


1

/

2


0




1


1

/

2


0





1

/

2


1

/

2





1


0






{\displaystyle {\begin{array}{c|cc}0&1/2&0\\1&1/2&0\\\hline &1/2&1/2\\&1&0\\\end{array}}}

the fourth-order method given by

0


1

/

6


−
1

/

6


0




1

/

2


1

/

6


1

/

3


0




1


1

/

6


5

/

6


0





1

/

6


2

/

3


1

/

6





−


1
2




2


−


1
2








{\displaystyle {\begin{array}{c|ccc}0&1/6&-1/6&0\\1/2&1/6&1/3&0\\1&1/6&5/6&0\\\hline &1/6&2/3&1/6\\&-{\frac {1}{2}}&2&-{\frac {1}{2}}\\\end{array}}}

lobatto iiib methods a-stable, not l-stable , b-stable.

lobatto iiic methods

the lobatto iiic methods discontinuous collocation methods. second-order method given by

0


1

/

2


−
1

/

2




1


1

/

2


1

/

2





1

/

2


1

/

2





1


0






{\displaystyle {\begin{array}{c|cc}0&1/2&-1/2\\1&1/2&1/2\\\hline &1/2&1/2\\&1&0\\\end{array}}}

the fourth-order method given by

0


1

/

6


−
1

/

3


1

/

6




1

/

2


1

/

6


5

/

12


−
1

/

12




1


1

/

6


2

/

3


1

/

6





1

/

6


2

/

3


1

/

6





−


1
2




2


−


1
2








{\displaystyle {\begin{array}{c|ccc}0&1/6&-1/3&1/6\\1/2&1/6&5/12&-1/12\\1&1/6&2/3&1/6\\\hline &1/6&2/3&1/6\\&-{\frac {1}{2}}&2&-{\frac {1}{2}}\\\end{array}}}

they l-stable. algebraically stable , b-stable, makes them suitable stiff problems.

lobatto iiic* methods

the lobatto iiic* methods known lobatto iii methods (butcher, 2008), butcher’s lobatto methods (hairer et al, 1993), , lobatto iiic methods (sun, 2000) in literature. second-order method given by

0


0


0




1


1


0





1

/

2


1

/

2






{\displaystyle {\begin{array}{c|cc}0&0&0\\1&1&0\\\hline &1/2&1/2\\\end{array}}}

the fourth-order method given by

0


0


0


0




1

/

2


1

/

4


1

/

4


0




1


0


1


0





1

/

6


2

/

3


1

/

6






{\displaystyle {\begin{array}{c|ccc}0&0&0&0\\1/2&1/4&1/4&0\\1&0&1&0\\\hline &1/6&2/3&1/6\\\end{array}}}

these methods not a-stable, b-stable or l-stable. lobatto iiic* method



s
=
2


{\displaystyle s=2}

called explicit trapezoidal rule.

generalized lobatto methods

one can consider general family of methods 3 real parameters



(

α

a


,

α

b


,

α

c


)


{\displaystyle (\alpha _{a},\alpha _{b},\alpha _{c})}

considering lobatto coefficients of form

a

i
,
j


(

α

a


,

α

b


,

α

c


)
=

α

a



a

i
,
j


a


+

α

b



a

i
,
j


b


+

α

c



a

i
,
j


c


+

α

c
∗



a

i
,
j


c
∗




{\displaystyle a_{i,j}(\alpha _{a},\alpha _{b},\alpha _{c})=\alpha _{a}a_{i,j}^{a}+\alpha _{b}a_{i,j}^{b}+\alpha _{c}a_{i,j}^{c}+\alpha _{c*}a_{i,j}^{c*}}

,

where

α

c
∗


=
1
−

α

a


−

α

b


−

α

c




{\displaystyle \alpha _{c*}=1-\alpha _{a}-\alpha _{b}-\alpha _{c}}

.

for example, lobatto iiid family introduced in (nørsett , wanner, 1981), called lobatto iiinw, given by

0


1

/

2


1

/

2




1


−
1

/

2


1

/

2





1

/

2


1

/

2






{\displaystyle {\begin{array}{c|cc}0&1/2&1/2\\1&-1/2&1/2\\\hline &1/2&1/2\\\end{array}}}

and

0


1

/

6


0


−
1

/

6




1

/

2


1

/

12


5

/

12


0




1


1

/

2


1

/

3


1

/

6





1

/

6


2

/

3


1

/

6






{\displaystyle {\begin{array}{c|ccc}0&1/6&0&-1/6\\1/2&1/12&5/12&0\\1&1/2&1/3&1/6\\\hline &1/6&2/3&1/6\\\end{array}}}

these methods correspond




α

a


=
2


{\displaystyle \alpha _{a}=2}

,




α

b


=
2


{\displaystyle \alpha _{b}=2}

,




α

c


=
−
1


{\displaystyle \alpha _{c}=-1}

, ,




α

c
∗


=
−
2


{\displaystyle \alpha _{c*}=-2}

. methods l-stable. algebraically stable , b-stable.

radau methods

radau methods implicit methods (matrix of such methods can have structure). radau methods attain order 2s − 1 s stages. radau methods a-stable, expensive implement. can suffer order reduction. first order radau method similar backward euler method.

radau ia methods

the third-order method given by

0


1

/

4


−
1

/

4




2

/

3


1

/

4


5

/

12





1

/

4


3

/

4






{\displaystyle {\begin{array}{c|cc}0&1/4&-1/4\\2/3&1/4&5/12\\\hline &1/4&3/4\\\end{array}}}

the fifth-order method given by

0




1
9







−
1
−


6



18







−
1
+


6



18








3
5


−



6

10






1
9






11
45


+



7


6



360






11
45


−



43


6



360








3
5


+



6

10






1
9






11
45


+



43


6



360






11
45


−



7


6



360









1
9






4
9


+



6

36






4
9


−



6

36








{\displaystyle {\begin{array}{c|ccc}0&{\frac {1}{9}}&{\frac {-1-{\sqrt {6}}}{18}}&{\frac {-1+{\sqrt {6}}}{18}}\\{\frac {3}{5}}-{\frac {\sqrt {6}}{10}}&{\frac {1}{9}}&{\frac {11}{45}}+{\frac {7{\sqrt {6}}}{360}}&{\frac {11}{45}}-{\frac {43{\sqrt {6}}}{360}}\\{\frac {3}{5}}+{\frac {\sqrt {6}}{10}}&{\frac {1}{9}}&{\frac {11}{45}}+{\frac {43{\sqrt {6}}}{360}}&{\frac {11}{45}}-{\frac {7{\sqrt {6}}}{360}}\\\hline &{\frac {1}{9}}&{\frac {4}{9}}+{\frac {\sqrt {6}}{36}}&{\frac {4}{9}}-{\frac {\sqrt {6}}{36}}\\\end{array}}}



radau iia methods

the ci of method zeros of

p

s


(
2
x
−
1
)
−

p

s
−
1


(
2
x
−
1
)
=
0
,


{\displaystyle p_{s}(2x-1)-p_{s-1}(2x-1)=0,}

where




p

s




{\displaystyle p_{s}}

legendre polynomial of degree s. third-order method given by

1

/

3


5

/

12


−
1

/

12




1


3

/

4


1

/

4





3

/

4


1

/

4






{\displaystyle {\begin{array}{c|cc}1/3&5/12&-1/12\\1&3/4&1/4\\\hline &3/4&1/4\\\end{array}}}

the fifth-order method given by

2
5


−



6

10






11
45


−



7


6



360






37
225


−



169


6



1800




−


2
225


+



6

75








2
5


+



6

10






37
225


+



169


6



1800






11
45


+



7


6



360




−


2
225


−



6

75






1




4
9


−



6

36






4
9


+



6

36






1
9









4
9


−



6

36






4
9


+



6

36






1
9








{\displaystyle {\begin{array}{c|ccc}{\frac {2}{5}}-{\frac {\sqrt {6}}{10}}&{\frac {11}{45}}-{\frac {7{\sqrt {6}}}{360}}&{\frac {37}{225}}-{\frac {169{\sqrt {6}}}{1800}}&-{\frac {2}{225}}+{\frac {\sqrt {6}}{75}}\\{\frac {2}{5}}+{\frac {\sqrt {6}}{10}}&{\frac {37}{225}}+{\frac {169{\sqrt {6}}}{1800}}&{\frac {11}{45}}+{\frac {7{\sqrt {6}}}{360}}&-{\frac {2}{225}}-{\frac {\sqrt {6}}{75}}\\1&{\frac {4}{9}}-{\frac {\sqrt {6}}{36}}&{\frac {4}{9}}+{\frac {\sqrt {6}}{36}}&{\frac {1}{9}}\\\hline &{\frac {4}{9}}-{\frac {\sqrt {6}}{36}}&{\frac {4}{9}}+{\frac {\sqrt {6}}{36}}&{\frac {1}{9}}\\\end{array}}}






^ http://homepage.math.uiowa.edu/~ljay/publications.dir/lobatto.pdf