Difference equation

An equation containing finite differences of an unknown function. Let $ y ( n) = y _ {n} $ be a function depending on an integer argument $ n = 0, \pm 1, \pm 2 , . . . $; let

$$ \Delta y _ {n} = \ y _ {n + 1 } - y _ {n} ,\ \ \Delta ^ {m + 1 } y _ {n} = \ \Delta ( \Delta ^ {m} y _ {n} ), $$

$$ \Delta ^ {1} y _ {n} = \Delta y _ {n} ,\ m = 1, 2 \dots $$

be the finite differences. The expression $ \Delta ^ {m} y _ {n} $ contains values of the function $ y $ at the $ m + 1 $ points $ n \dots n + m $. The formula

$$ \tag{1 } \Delta ^ {m} y _ {n} = \ \sum _ { k= } 0 ^ { m } (- 1) ^ {m - k } \left ( \begin{array}{c} m \\ k \end{array} \right ) y _ {n + k } $$

is valid. An equation of the form

$$ \tag{2 } F ( n; y _ {n} , \Delta y _ {n} \dots \Delta ^ {m} y _ {n} ) = 0 $$

is called a difference equation, where $ y $ is an unknown and $ F $ is a given function. Replacing the finite differences in (2) by their expressions in the values of the desired function according to (1), it reduces to an equation of the form

$$ \tag{3 } F ( n; y _ {n} ,\ y _ {n + 1 } \dots y _ {n + m } ) = 0. $$

If $ \partial F/ \partial y _ {n} \neq 0 $, $ \partial F/ \partial y _ {n + m } \neq 0 $, that is, if equation (3) really does contain $ y _ {n} $ as well as $ y _ {n + m } $, then equation (3) is called an $ m $- th order difference equation.

The most developed theory is that of linear difference equations, which has much in common with the theory of linear ordinary differential equations (see [1]–[3]). An equation

$$ \tag{4 } a _ {m} ( n) y _ {n + m } + \dots + a _ {0} ( n) y _ {n} = f _ {n} $$

is an $ m $- th order linear difference equation. Here $ f _ {n} = f ( n) $ is a given function and the $ a _ {k} ( n) $, $ k = 0 \dots m $, are given coefficients, $ a _ {m} ( n) \neq 0 $, $ a _ {0} ( n) \neq 0 $. Every function $ y _ {n} = y ( n) $ satisfying equation (4) is called a solution to the difference equation. As in the case of differential equations one distinguishes particular and general solutions of the difference equation (4). A general solution to the difference equation (4) is a solution, depending on $ m $ arbitrary parameters, such that each particular solution can be obtained from it by giving a certain value to the parameters. Usually the actual values of the parameters are found from supplementary conditions. The Cauchy problem is typical: Given $ y _ {0} \dots y _ {m - 1 } , f _ {n} $, find the solution $ y _ {n} $ to equation (4) when $ n = m, m + 1 , . . . $. The existence of and a method for constructing a solution to the difference equation (4) are established according to the following scheme. Along with (4) the homogeneous difference equation

$$ \tag{5 } a _ {m} ( n) y _ {n + m } + \dots + a _ {0} ( n) y _ {n} = 0 $$

is considered.

The following assertions are true:

1) Let $ y _ {n} ^ {(} 1) \dots y _ {n} ^ {(} k) $ be solutions to equation (5) and let $ c _ {1} \dots c _ {k} $ be an arbitrary collection of constants. Then the function $ c _ {1} y _ {n} ^ {(} 1) + \dots + c _ {k} y _ {n} ^ {(} k) $ is also a solution to equation (5).

2) If $ y _ {n} ^ {(} 1) \dots y _ {n} ^ {(} m) $ are $ m $ solutions to equation (5) and if the determinant

$$ \left | \begin{array}{ccc} y _ {0} ^ {(} 1) &\dots &y _ {0} ^ {(} m) \\ \dots &\dots &\dots \\ y _ {m - 1 } ^ {(} 1) &\dots &y _ {m - 1 } ^ {(} m) \\ \end{array} \ \right | $$

is non-zero, then the general solution to the homogeneous difference equation (5) has the form

$$ \tag{6 } y _ {n} = \ \sum _ {k = 1 } ^ { m } c _ {k} y _ {n} ^ {(} k) , $$

where $ c _ {k} $ are arbitrary constants.

3) The general solution to the non-homogeneous difference equation (4) is the sum of any one of its particular solutions and the general solution of the homogeneous difference equation (5).

A particular solution to the non-homogeneous equation (5) can be constructed by starting from the general solution (6) of the homogeneous equation by the method of variation of parameters (see, for example, [2]). In the case of a difference equation with constant coefficients,

$$ \tag{7 } a _ {m} y _ {m + n } + \dots + a _ {0} y _ {n} = 0, $$

one can find $ m $ linearly independent particular solutions immediately. Namely, consider the characteristic equation

$$ \tag{8 } a _ {m} q ^ {m} + a _ {m - 1 } q ^ {m - 1 } + \dots + a _ {0} = 0 $$

and find its roots $ q _ {1} \dots q _ {m} $. If all the roots are simple, then the functions

$$ y _ {n} ^ {(} 1) = \ q _ {1} ^ {n} \dots \ y _ {n} ^ {(} m) = \ q _ {m} ^ {n} $$

are a linearly independent system of solutions to equation (7). When $ q _ {k} $ is a root of multiplicity $ r $, the solutions

$$ q _ {k} ^ {n} ,\ nq _ {k} ^ {n} \dots \ n ^ {r - 1 } q _ {k} ^ {n} $$

are linearly independent.

If the coefficients $ a _ {0} \dots a _ {m} $ are real and equation (8) has a complex root, for example a simple root $ q _ {k} = \rho ( \cos \phi + i \sin \phi ) $, then instead of the complex solutions $ q _ {k} ^ {n} , \overline{q}\; {} _ {k} ^ {n} $ one obtains two linearly independent real solutions

$$ \rho ^ {n} \cos n \phi ,\ \ \rho ^ {n} \sin n \phi . $$

Suppose one has a second-order difference equation with constant real coefficients,

$$ \tag{9 } a _ {2} y _ {n + 2 } + a _ {1} y _ {n + 1 } + a _ {0} y _ {n} = 0. $$

The characteristic equation

$$ a _ {2} q ^ {2} + a _ {1} q + a _ {0} = 0 $$

has the roots

$$ q _ {1,2} = \ \frac{- a _ {1} \pm \sqrt {a _ {1} ^ {2} - 4a _ {0} a _ {2} } }{2a _ {2} } . $$

When $ q _ {2} \neq q _ {1} $ it is convenient to write the general solution to (9) in the form

$$ \tag{10 } y _ {n} = c _ {1} \frac{q _ {2} q _ {1} ^ {n} - q _ {1} q _ {2} ^ {n} }{q _ {2} - q _ {1} } + c _ {2} \frac{q _ {2} ^ {n} - q _ {1} ^ {n} }{q _ {2} - q _ {1} } , $$

where $ c _ {1} $ and $ c _ {2} $ are arbitrary constants. If $ q _ {1} $ and $ q _ {2} $ are complex conjugate roots:

$$ q _ {1,2} = \ \rho ( \cos \phi \pm i \sin \phi ), $$

then another representation of the general solution is

$$ \tag{11 } y _ {n} = \ - c _ {1} \rho ^ {n} \frac{\sin ( n - 1) \phi }{\sin \phi } + c _ {2} \rho ^ {n - 1 } \frac{\sin n \phi }{\sin \phi } . $$

In the case of a multiple root the general solution can be obtained by taking limits in (10) or (11). It will have the form

$$ y _ {n} = \ - c _ {1} ( n - 1) q _ {1} ^ {n} + c _ {2} nq _ {1} ^ {n - 1 } . $$

One can consider the Cauchy problem or various boundary value problems for second-order difference equations in the same way as for equations of arbitrary order. For example, for the Cauchy problem

$$ \tag{12 } \left . \begin{array}{c} T _ {n + 2 } ( x) - 2xT _ {n + 1 } ( x) + T _ {n} ( x) = 0,\ \ n = 0, 1 \dots \\ T _ {0} ( x) = 1,\ \ T _ {1} ( x) = x, \\ \end{array} \right \} $$

where $ x $ is any real number, the solution of (12) is a polynomial $ T _ {n} ( x) $ of degree $ n $( a Chebyshev polynomial of the first kind), defined by

$$ T _ {n} ( x) = \ \cos ( n \mathop{\rm arc} \cos x) = $$

$$ = \ { \frac{1}{2} } [( x + \sqrt {x ^ {2} - 1 } ) ^ {n} + ( x + \sqrt {x ^ {2} - 1 } ) ^ {-} n ]. $$

A boundary value problem for a second-order difference equation is to find a function $ y _ {n} $ satisfying, when $ n = 1 \dots N - 1 $, an equation

$$ \tag{13 } Ly _ {n} = \ a _ {n} y _ {n - 1 } - c _ {n} y _ {n} + b _ {n} y _ {n + 1 } = \ - f _ {n} $$

and two linearly independent boundary conditions. Such boundary conditions can be, for example,

$$ \tag{14 } y _ {0} = \ \kappa _ {1} y _ {1} + \mu _ {1} ,\ \ y _ {N} = \ \kappa _ {2} y _ {N - 1 } + \mu _ {2} , $$

or

$$ \tag{15 } y _ {0} = \ \mu _ {1} ,\ \ y _ {N} = \ \mu _ {2} . $$

The following maximum principle is valid for a second-order difference equation. Given the problem (13), (15), let the conditions

$$ a _ {n} > 0,\ \ b _ {n} > 0,\ \ c _ {n} \geq \ a _ {n} + b _ {n} ,\ \ n = 1 \dots N - 1, $$

be fulfilled. Now if $ Ly _ {n} \geq 0 $ $ ( Ly _ {n} \leq 0) $, $ n = 1 \dots N - 1 $, then $ y _ {n} \not\equiv \textrm{ const } $ cannot have a greatest positive (smallest negative) value when $ n = 1 \dots N - 1 $. The maximum principle implies that the boundary value problem (13), (15) is uniquely solvable and that its solution is stable under a change of the boundary conditions $ \mu _ {1} , \mu _ {2} $ and the right-hand side $ f _ {n} $. The shooting method (see [2]) can be applied to solve difference boundary value problems (13), (14).

One has constructed an explicit form of the solution to a non-linear difference equation

$$ \tag{16 } y _ {n + 1 } = \ f _ {n} ( y _ {n} ),\ \ n = 0, 1 \dots $$

only in isolated, very special cases. For equations of the type (16) one studies qualitative questions on the behaviour of the solutions as $ n \rightarrow \infty $, and a stability theory, which on the whole is analogous to the stability theory for ordinary differential equations, has been developed (see [4], [5]).

Multi-dimensional difference equations arise for difference approximations to partial differential equations (see [2], [6]). For example, the Poisson equation

$$ \frac{\partial ^ {2} u }{\partial x _ {1} ^ {2} } + \frac{\partial ^ {2} u }{\partial x _ {2} ^ {2} } = \ - f ( x _ {1} , x _ {2} ) $$

can be approximated by the difference equation

$$ \frac{u _ {i + 1, j } - 2u _ {i,j} + u _ {i - 1, j } }{h _ {1} ^ {2} } + \frac{u _ {i, j + 1 } - 2u _ {i,j} + u _ {i, j + 1 } }{h _ {2} ^ {2} } = \ - f _ {i,j} , $$

where

$$ u _ {i,j} = \ u ( x _ {1} ^ {(} i) ,\ x _ {2} ^ {(} j) ),\ \ x _ {1} ^ {(} i) = \ ih _ {1} ,\ \ x _ {2} ^ {(} j) = \ jh _ {2} , $$

$$ i, j = 0, \pm 1, \pm 2 \dots $$

and $ h _ {1} $ and $ h _ {2} $ are the steps of the grid.

A system of multi-dimensional difference equations together with additional initial and boundary conditions forms a difference scheme. Such questions as the correctness of difference problems, methods for solving them, convergence under grid refinement to the solutions of the original differential equations, are all studied in connection with multi-dimensional difference equations (see Difference schemes, theory of).

Although various mathematical and technical models leading to difference equations exist (see, for example, [4], [5]) the basic field of their application is in approximation methods for solving differential equations (see [6] and [9]).

References

[1]	A.O. [A.O. Gel'fond] Gelfond, "Differenzenrechnung" , Deutsch. Verlag Wissenschaft. (1958) (Translated from Russian)
[2]	A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
[3]	A.A. Samarskii, Yu.N. Karamzin, "Difference equations" , Moscow (1978) (In Russian)
[4]	D.I. Martynyuk, "Lectures on the qualitative theory of difference equations" , Kiev (1972) (In Russian)
[5]	A. Halanay, D. Wexler, "Qualitative theory of impulse systems" , Acad. R.S. Romania (1968) (Translated from Rumanian)
[6]	A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[7]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , 2 , Pergamon (1973) (Translated from Russian)
[8]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[9]	A.D. Gorbunov, "Difference equations" , Moscow (1972) (In Russian)

Comments

For references see also Difference scheme. In addition, [a1], [a2] below give a more general treatment of difference equations and difference operators (cf. Difference operator), as well as applications of these to differential equations.

References

[a1]	P. Henrici, "Discrete variable methods in ordinary differential equations" , Wiley (1962)
[a2]	F.B. Hildebrand, "Finite-difference equations and simulations" , Prentice-Hall (1968)
[a3]	M.R. Spiegel, "Calculus of finite differences and difference equations" , McGraw-Hill (1971)
[a4]	L.M. Milne-Thomson, "The calculus of finite differences" , Chelsea, reprint (1981)
[a5]	N.E. Nörlund, "Volesungen über Differenzenrechnung" , Springer (1924)