MATHEMATICS

A. D. GORBUNOV and B. M. BUDAK

ON THE CONVERGENCE OF CERTAIN FINITE-DIFFERENCE PROCESSES FOR THE EQUATIONS \(y'=f(x,y)\) AND \(y'(x)=f(x,y(x),y(x-\tau(x)))\)

(Presented by Academician S. L. Sobolev on 22 XI 1957)

An extensive literature is devoted to the description and study of finite-difference methods for solving the Cauchy problem for the equations indicated in the title (see, for example, \((^{1-6})\)). In the present article the convergence of certain finite-difference processes for solving the Cauchy problem for such equations is investigated, and some estimates are obtained.

\(1^\circ\). Suppose the equation

\[ y'=f(x,y), \tag{1} \]

is given, whose right-hand side is defined and continuous in a certain bounded closed domain \(\overline G\) of the \((x,y)\)-plane; it is required to find its solution satisfying the condition

\[ y(x_0)=y_0,\qquad (x_0,y_0)\in G. \tag{2} \]

By \(y=y(x)\) we shall denote any exact solution of problem (1), (2) \((^7)\).

We shall seek approximate values \(y_i\) of the ordinates \(y(x_i)\) of the exact solution \(y=y(x)\) at the points \(x_i=x_0+ih,\ i=0,\pm1,\pm2,\ldots;\ h>0\), by means of the finite-difference equation:

\[ \sum_{i=0}^{m}\alpha_i y_{k-i} = h\sum_{i=0}^{n}\beta_i f_{k+l-i}, \qquad f_j=f(x_j,y_j), \tag{3} \]

where \(l,m\), and \(n\) are given integers; \(\alpha_i\) and \(\beta_i\) are specified real numbers; \(m>0;\ n\ge 0;\ \alpha_0,\alpha_m,\beta_0,\beta_n\) are nonzero \((^6)\).

Noting that the order of equation (3) is equal to \(p-q\), where \(p=\max(k,k+l)\) and \(q=\min(k-m,k+l-n)\), we prescribe the initial conditions in the form

\[ y_i=g(x_i),\qquad i=0,-1,\ldots,-(p-q-1),\qquad g(x_0)=y_0, \tag{4} \]

where \(g(x)\) is a certain continuously differentiable function, given on the interval \(x^*\le x\le x_0\) and called the initial function; here the interval \([x^*,x_0]\) constitutes part of the projection of the intersection of the straight line \(y=y_0\) with the domain \(G\) onto the \(x\)-axis, and \((x,g(x))\in G\); the possibility is allowed that the initial function may change when the step \(h\) is changed, which must satisfy the condition \(h(p-q-1)\le x^*-x_0\).

Suppose that problem (3), (4) has been solved on some interval of values of \(x\). Join each pair of points \((x_j,y_j)\) and \((x_{j+1},y_{j+1})\) by a line segment, and let the equation of the polygonal line thus obtained be \(y=\widetilde y_h(x)\). Suppose, further, that the numbers \(\overline x\) and \(h_0\) are chosen so that the mentioned polygonal line is defined, in any case, on the interval \(x_0\le x\le \overline x\) for every \(h,\ 0<h\le h_0\). If from every sequence of steps converging to zero one can extract a subsequence \(h_\nu,\ \nu=1,2,\ldots,\) such that the corresponding sequence יק0

of the corresponding broken lines \(y=\widetilde y_{h_\nu}(x)\) converges uniformly on the interval \([x_0,\bar x]\) to some solution of problem (1), (2), then we shall say that the finite-difference process defined by equation (3) converges.

Theorem 1. If the finite-difference process defined by equation (3) converges, then the conditions

\[ \sum_{i=0}^{m}\alpha_i=0,\qquad \sum_{i=0}^{m-1}\sum_{j=0}^{i}\alpha_j = \sum_{i=0}^{n}\beta_i\ne 0 \tag{5} \]

are satisfied.

\(2^\circ\). Denote by \(C_h[x_0,\bar x]\) the space of finite functions \(\psi(x_k)\), given at the points \(x_k\), \(k=0,1,\ldots,N_h=\left[\dfrac{\bar x-x_0}{h}\right]\), with norm
\[ \|\psi\|=\max_{0\le k\le N_h}|\psi(x_k)|, \]
and by \(C[x_0,\bar x]\) the space of bounded functions \(\psi(x)\), given on the interval \(x_0\le x\le \bar x\), with norm
\[ \|\psi\|=\sup_{x_0\le x\le \bar x}|\psi(x)|. \]
The space \(C_h[x_0,\bar x]\) can be embedded in \(C[x_0,\bar x]\), identifying elements of \(C_h[x_0,\bar x]\) with the corresponding piecewise constant functions from \(C[x_0,\bar x]\).

Consider the finite-difference equation

\[ \sum_{i=0}^{m-1}\sum_{j=0}^{i}\alpha_j\varphi_{k-i}=h\psi_k, \tag{6} \]

where \(\varphi_j=\varphi(x_j)\), \(\psi_j=\psi(x_j)\). Under zero initial conditions its solution can be written in the form

\[ \varphi_k=hB_h\psi_k,\qquad \psi\in C_h[x_0,\bar x], \tag{7} \]

where, for every fixed \(h\), \(B_h\) is a linear bounded operator with norm
\[ \|B_h\|=\max_{0\le k\le N_h}\sum_{i=0}^{k-1}|\gamma_{ki}|, \]
where the \(\gamma_{ki}\) are completely determined by some fundamental system of solutions of the homogeneous equation corresponding to equation (6).

Analogously, the finite-difference equation

\[ \sum_{i=0}^{m-1}\sum_{j=0}^{i}\alpha_j\varphi(x-ih)=h\psi(x) \tag{7'} \]

under zero initial conditions determines the function

\[ \varphi(x)=h\widetilde B_h\psi(x),\qquad \psi\in C[x_0,\bar x], \tag{8'} \]

where the operator \(\widetilde B_h\), for every fixed \(h\), is linear and bounded, \(\|\widetilde B_h\|=\|B_h\|\).

Let \(f\) range over the set of all continuous functions in \(\bar G\); then the function \(\psi_h\), defined by the relation

\[ \psi_k=\sum_{i=0}^{n}\beta_i f_{k+l+1-i},\qquad 0\le k\le N_h=\left[\frac{\bar x-x_0}{h}\right], \tag{9} \]

ranges over the whole space \(C_h[x_0,\bar x]\).

Denote by \(K(C)\) the class of all functions \(\psi\) belonging to
\[ \sum_{0<h<h_0} C_h[x_0,\bar x], \]
for which \(\|\psi\|\le C\), \(C>0\), and by \(R(C')\) the class

all continuously differentiable functions \(g(x)\), \(x^* \leq x \leq x_0\), for which \(M_{g'} \leq C'\), \(C' > 0\), \(g(x_0)=y_0\).*

The finite-difference process defined by equation (3) will be called uniformly convergent if it converges and if, whatever \(C>0\) and \(C'>0\) may be, there exists a constant \(A_{CC'}\), depending only on \(C\) and \(C'\), such that the inequality

\[ |\Delta y_k/h|<A_{CC'} \tag{10} \]

is satisfied uniformly with respect to \(h\), \(0 \leq h \leq h_0\), with respect to \(k=0,1,\ldots,N_h\), with respect to \(\psi \in K(C)\), and with respect to \(g \in R(C')\); \(\Delta y_k=y_{k+1}-y_k\) is found by means of equation (3) and the initial conditions (4). The equation

\[ \sum_{i=0}^{m-1}\sum_{j=0}^{i}\alpha_j\lambda^{m-1-i}=0 \tag{11} \]

will, as usual, be called the characteristic equation of the difference equation (6).

Theorem 2. Suppose that the coefficients of equation (3) satisfy conditions (5). Then, for the uniform convergence of the finite-difference process defined by this equation, it is necessary and sufficient that the norm of the operator \(B_h\) be uniformly bounded with respect to \(h\), \(0<h\leq h_0\), that the moduli of the simple roots of the characteristic equation (11) not exceed unity, and that the moduli of its multiple roots be less than unity.

Let us consider some special cases.

A. For the finite-difference process defined by the equation
\[ \alpha_0 y_k+\alpha_1 y_{k-1} = h(\beta_0 f_{k+1}+\cdots+\beta_n f_{k+1-n}), \]
the necessary conditions (5) take the form
\[ \alpha_0+\alpha_1=0,\qquad \alpha_0=\beta_0+\cdots+\beta_n\ne 0, \]
and are also sufficient conditions for convergence.

B. The finite-difference process generated by the equation
\[ \alpha_0 y_k+\alpha_1 y_{k-1}+\alpha_2 y_{k-2} = h(\beta_0 f_{k+1}+\cdots+\beta_n f_{k+1-n}) \]
converges uniformly only when the conditions
\[ \alpha_0+\alpha_1+\alpha_2=0,\qquad 2\alpha_0+\alpha_1=\beta_0+\cdots+\beta_n\ne 0, \]
\[ -1<-\frac{\alpha_0+\alpha_1}{\alpha_1}<1 \]
are fulfilled.

3°. Suppose that \(f(x,y)\) satisfies the Lipschitz condition in \(y\) with constant \(L\).

Then the integral
\[ u=\int_{x_0}^{x}|\widetilde y_h(\xi)-y(\xi)|\,d\xi \]
satisfies the inequality

\[ du/dx\leq Lu+A+B(x-x_0), \tag{12} \]

where

\[ A=h\rho(h)\left[ C^{**}\sum_{i=0}^{m-1}\left|\sum_{j=0}^{i}\alpha_j\right|\,i + C^*(m-1) \right], \qquad B=C^{**}\varepsilon(h), \]

\[ \rho(h)= \max_{x_0-(m-1)h\leq x\leq x_0} \left| \frac{\Delta g_{i-1}}{h} - f\bigl(x,\widetilde y_h(x)\bigr) \right|, \qquad \|\widetilde B_h\|\leq C^{**}, \]

\[ \varepsilon(h)=\max_{x_0\leq x\leq \bar x}|Q_h(x)|, \tag{13} \]

\[ Q_h(x)= \sum_{i=0}^{n}\beta_i f_{k+1-i} - \sum_{j=0}^{m-1}\sum_{j=0}^{i}\alpha_j f\bigl(x-ih,\widetilde y_h(x-ih)\bigr), \qquad x_{k-1}<x\leq x_k, \]

\[ C^*= \max_{0\leq k<+\infty} \sum_{i=1}^{m-1}\sum_{j=1}^{m-1} |C_{ij}|\,|\zeta_i(k)|, \]

where \(\zeta_1(k),\ldots,\zeta_{m-1}(k)\) denote the functions, arranged in a certain order,
\[ \lambda_1^k,\ k\lambda_1^k,\ldots,\ k^{\omega_1-1}\lambda_1^k,\ldots, \lambda_s^k,\ k\lambda_s^k,\ldots,\ k^{\omega_s-1}\lambda_s^k, \]
constructed

* By \(M_f\) and \(m_f\), \(M_\psi\) and \(m_\psi\), etc., we shall denote the upper and lower bounds of the moduli of the functions \(f\), \(\psi\), etc., in the region under consideration.

by means of the roots of equation (11) \(\left(\lambda_i\right.\) has multiplicity \(\omega_i;\ \left.\sum_{i=0}^{s}\omega_i=m-1\right)\), and the constants \(C_{ij}\) do not depend on \(h\). From (12) one obtains the estimate

\[ \left|\widetilde{y}_h(x)-y(x)\right|\leq A e^{L(x-x_0)}+\frac{B}{L}\left[e^{L(x-x_0)}-1\right]. \tag{14} \]

If \(f(x,y)\) satisfies the Lipschitz condition
\[ |f(x,y)-f(x',y')|\leq L_1|x-x'|+L_2|y-y'| \]
with constants \(L_1\) and \(L_2\), then estimate (14) can be given a more effective form:

\[ \left|\widetilde{y}_h(x)-y(x)\right|\leq h\left\{P e^{L_2(x-x_0)}+\frac{C^{**}S}{L_2}\left[e^{L_2(x-x_0)}-1\right]\right\}, \tag{15} \]

where

\[ P=\rho(h)\left[C^*\sum_{i=0}^{m-1}\left|\sum_{j=0}^{i}\alpha_j\right|\,i+C^*(m-1)\right], \qquad \rho(h)\leq M_{g'}+M_f, \]

\[ S=\left[L_1+L_2\left(C^*M_{g'}+C^{**}M_f\right)\sum_{i=0}^{n}|\beta_i|\right] \left[\sum_{i=0}^{n}|\beta_i|(|i-l|+1)+\sum_{i=0}^{m-1}\left|\sum_{j=0}^{i}\alpha_j\right|\,i\right]. \]

\(4^\circ\). Let, for the equation

\[ y'(x)=f(x,y(x)),y(x-\tau(x)),\qquad m_\tau>0, \tag{16} \]

where \(f(x,y,z)\) is given and continuous in the closed domain \(\overline{G}\) of the space \((x,y,z)\), and \(\tau(x)\) is also a given continuous function, it be required to find a solution satisfying the condition

\[ y(x)=\varphi(x)\quad \text{for } \widetilde{x}\leq x\leq x_0, \tag{17} \]

where
\[ \widetilde{x}=\min_{x_0\leq x\leq X}[x-\tau(x)]; \]
\(\varphi(x)\) is a given continuous function.

The definitions, propositions, and estimates established in paragraphs \(1^\circ,2^\circ,3^\circ\) extend, with slight modifications, to the finite-difference method for solving problem (16), (17), defined as follows. Consider the points \(x_i,\ i=0,\pm1,\pm2,\ldots,\) and use the finite-difference equation

\[ \sum_{i=0}^{m}\alpha_i y_{k-i} = h\sum_{i=0}^{n}\beta_i f_{k+l-i} \tag{18} \]

of order \(p-q\). Put

\[ y_i=g(x_i),\qquad i=0,-1,\ldots,-(p-q-1), \tag{19} \]

where \(g(x)\) is a continuously differentiable function defined on the interval \(x^*\leq x\leq x_0,\ g(x_0)=\varphi(x_0)\); the step \(h\) must satisfy the conditions
\[ 0<h\leq m_\tau,\qquad h(p-q-1)\leq x^*-x_0. \]
Next we shall solve equation (18) step by step under the initial conditions (19), putting \(\widetilde{y}_h(x)=\varphi(x)\), \(\widetilde{x}\leq x\leq x_0\),
\[ f_j=f\left(x_j,y_j,\widetilde{y}_h(x_j-\tau(x_j))\right), \]
and continue, step by step, the function \(y=\widetilde{y}_h^\circ(x)\), applying linear interpolation of the neighboring values \(y_j\) and \(y_{j+}\). This will lead to the construction of an approximate solution of problem (16), (17).

Moscow State University
named after M. V. Lomonosov

Received
28 X 1957

CITED LITERATURE

1. Mathematics in the USSR for Thirty Years, 1948.
2. L. Collatz, Numerical Methods for Solving Differential Equations, IL, 1955.
3. V. E. Milne, Numerical Solution of Differential Equations, IL, 1955.
4. M. R. Shura-Bura, Prikl. matem. i mekh., 16, 5 (1942).
5. N. S. Bakhvalov, DAN, 104, No. 5 (1955).
6. Dahlquist, Math. Skand., 4, No. 1 (1956).
7. I. G. Petrovsky, Lectures on the Theory of Ordinary Differential Equations, 1952.
8. A. O. Gelfond, Calculus of Finite Differences, 1952.
9. B. M. Budak, A. D. Gorbunov, DAN, 117, No. 4 (1957).