EPODE

Nonlinear and multivalue methods

A numerical step-by-step method is a linear one if applying it to the equation y'=Ay, with A an arbitrary matrix, we get a linear equation in the discrete variable y_n.

A linear multistep formula with matrix coefficients has the form:

S_j=0^k[a_j⁽⁰⁾ I+S_i=1^sa_j⁽ⁱ⁾ hⁱQ_nⁱ ]y_n+j-k =hS_j=0^k[b_j⁽⁰⁾ I+S_i=1 ^s-1b_j⁽ⁱ⁾ hⁱQ_nⁱ]f_n+j-k, where Q_n is a variable matrix chosen so that ||Q(n)|| is bounded and the matrix coefficient of y_n is nonsingular. If b_k^(j) =0, j=0, ... ,s-1 the new approximation can be directly computed at each step with an unique matrix inversion. Practically, the -Q_n matrix is an approximation of the Jacobian 's matrix. The advantage of these formulae is due to the fact that we can build-up some explicit A-stable formulae. The behaviour of the classical linear multistep formulae at the scalar test equation is a prevision model of its behaviour when we integrate a linear system. This fact is not valid also for the formulae with matrix coefficients. A linear multistep formula with variable matrix coefficients is A'-stable if all the solutions of the difference equation produced applying the method with Q_n=-A to the problem y'=Ay, with max_iRel_i< 0, y(t₀)=y₀, converge to zero when n goes to infinity, for any stepsize h. The maximum order of an / line / line A -stable formulae is 2s.

A nonlinear formulae can be constructed as follows. Note that the Euler 's explicit rule is the result of the interpolation process with

I(t)=At+B, y_n=I(t_n), y_n-1 =I(t_n-1 ), f_n-1=I'(t_n-1) We get the iterative formula by the elimination of the parameters A and B. Lambert proposes the replacement of the polynomial I with a rational function. For example, we mention some conditions:

I(t)= A / (t+B) , y_n=I(t_n), y_n-1 =I(t_n-1 ), f_n-1 =I'(t_n-1) The resulting formula is the following one:

y_n-y_n-1 = hy_n-1 f_n-1 / (y_n-1 -hf_n-1) , (L1) These formulae are applied at each component of the solution. For example, for the problem y'=f(y), f=(f¹, ... ,f^N), y(t₀)=y₀

y_nⁱ-y_n-1 ⁱ= hy_n-1 ⁱf_n-1 ⁱ / ( y_n-1 ⁱ-hf_n-1 ⁱ ), i=1, ... ,N, n>= 1. A disadvantage of a such formula is the locally unconsistency, i.e. the order of the method is not a constant (it is a variable function on the iterative values). This inconvenient can be avoid applying some linear multistep formula in a neighbourhood of an inconsistent point. In the case of the above formula, the order

p >= 1, if y_n-1 # 0 and p=0, otherwise The formula is L-stable and its characteristic function is identically to the one of Euler 's implicit rule.

A multistep exponential formulae is an iterative process of the form

S_i=0^ka_ie^Ah(k-i) y_n+i-k=hS_i=0^kF_ki(Ah)g_n+i-k, a_k# 0, where a_i are some constants independent on h, and F_ki (Ah) are dependent on h and A. The formula is a nonlinear one, since the difference equation produced applying the method to a linear system is nonlinear in h. Practically, the exponentials are numerical approximated, for example by Pade 's rational function. The advantage of such method is the possibility to use a reasonable stepsize, since the stability condition is ||F_kk(Ah)||h||g_y||< 1.

The (A,B)-methods are also referred to as general linear methods, Butcher 's methods , or multivalues methods . These formula generalizes both the linear multistep formula and the Runge-Kutta 's process. A general linear formula is an iterative process of the following form

y_i⁽ⁿ⁾ =S_j=1^ra_ij⁽²⁾ y_j^(n-1) +hS_j=1 ^sb_ij ⁽²⁾ f(t_n-1 +hc_j,Y_j), i=1, ... ,r,

Y_i=S_j=1^ra_ij ⁽¹⁾ y_j^(n-1) +hS_j=1^sb_ij⁽¹⁾ f(t_n-1 +hc_j,Y_j), i=1, ... ,s, where y_i⁽ⁿ⁾ are the external stages, and Y_i, the internal stages. As usual, r=s inserting some zeros. Note u=r+s. The matrix equation is y^{(n) =A₂y^(n-1) +hB₂f(Y), Y=A₁y^(n-1) +hB₁f(Y),} or Y⁽ⁿ⁾ =AY^(n-1) +hBF(Y⁽ⁿ⁾ ), where Y⁽ⁿ⁾ =(y⁽ⁿ⁾ ,Y). We can rewrite the process in a symbolic form

`c`	`A₁`	`B₁`
	`A₂`	`B₂`

An equivalent written form is that of an (A,B,C)-method. In the autonomous case, such a method can be described by the difference equation

y_i⁽ⁿ⁾ =S_j=1^ua_ij y_j^(n-1) +hS_j=1 ^ub_ijf(y_j⁽ⁿ⁾ )+hS_j=1^uc_ij f(y_j^(n-1) ). The two forms are equivalents. The (A,B)-method is explicit when B is an inferior triangular matrix, else the method is implicit. The Runge-Kutta 's process with q stages is an (A,B) method with u=q+1. We must mention that there are some generalizations of the classical Runge-Kutta 's process which are also examples of (A,B)-methods, like the multistep Runge-Kutta methods, or the pseudo Runge-Kutta methods. The (A,B,C)-method is preconsistent if Ae=e and consistent if it is preconsistent and, for some vector v (consistency vector) Av+(B+C)e=v+e holds, where e=(1, ... ,1)^T. The matrix A is stable if there is a norm produced by a scalar product for which ||A||<=1. The (A,B)-method is stable if the matrix A is stable. An (A,B)-method is convergent iff it is consistent and stable.

The class of A-methods include all the above mentioned formulae and schemes, both linear and nonlinear methods. The matrix formula is

Y_n+1 =AY_n +hF(t_n ,Y_n ,h) , n>= 0, Y₀ =F(h) where F is the starting procedure, and A is a matrix which is independently on the solved problem. An A-method consist in (1) a starting procedure, (2) the advance formula, (3) a correct validation Z(t_n,h) of the approximate values Y_n : the global error is the difference Y_n-Z(t_n,h).