Namespaces
Variants
Actions

Difference between revisions of "Difference equation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
An equation containing finite differences of an unknown function. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316801.png" /> be a function depending on an integer argument <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316802.png" />; let
+
<!--
 +
d0316801.png
 +
$#A+1 = 90 n = 0
 +
$#C+1 = 90 : ~/encyclopedia/old_files/data/D031/D.0301680 Difference equation
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316803.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316804.png" /></td> </tr></table>
+
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
  
be the finite differences. The expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316805.png" /> contains values of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316806.png" /> at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316807.png" /> points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316808.png" />. The formula
+
$$
 +
\Delta y _ {n}  = \
 +
y _ {n + 1 }  - y _ {n} ,\ \
 +
\Delta ^ {m + 1 } y _ {n}  = \
 +
\Delta ( \Delta  ^ {m} y _ {n} ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d0316809.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$
 +
\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
 
is valid. An equation of the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
F ( n; y _ {n} , \Delta y _ {n} \dots \Delta  ^ {m} y _ {n} )  = 0
 +
$$
  
is called a difference equation, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168011.png" /> is an unknown and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168012.png" /> 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
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
F ( n; y _ {n} ,\
 +
y _ {n + 1 }  \dots
 +
y _ {n + m }  )  = 0.
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168015.png" />, that is, if equation (3) really does contain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168016.png" /> as well as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168017.png" />, then equation (3) is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168019.png" />-th order difference equation.
+
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 [[#References|[1]]]–[[#References|[3]]]). An 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 [[#References|[1]]]–[[#References|[3]]]). An equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168020.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
a _ {m} ( n)
 +
y _ {n + m }  + \dots +
 +
a _ {0} ( n) y _ {n}  =  f _ {n}  $$
  
is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168021.png" />-th order linear difference equation. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168022.png" /> is a given function and the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168024.png" />, are given coefficients, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168026.png" />. Every function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168027.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168028.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168029.png" />, find the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168030.png" /> to equation (4) when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168031.png" />. 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
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>
+
$$ \tag{5 }
 +
a _ {m} ( n)
 +
y _ {n + m }  + \dots +
 +
a _ {0} ( n) y _ {n}  =  0
 +
$$
  
 
is considered.
 
is considered.
Line 31: Line 95:
 
The following assertions are true:
 
The following assertions are true:
  
1) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168033.png" /> be solutions to equation (5) and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168034.png" /> be an arbitrary collection of constants. Then the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168035.png" /> is also a solution to equation (5).
+
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
  
2) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168036.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168037.png" /> solutions to equation (5) and if the determinant
+
$$
 +
\left |
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168038.png" /></td> </tr></table>
+
\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
 
is non-zero, then the general solution to the homogeneous difference equation (5) has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>
+
$$ \tag{6 }
 +
y _ {n}  = \
 +
\sum _ {k = 1 } ^ { m }
 +
c _ {k} y _ {n}  ^ {(} k) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168040.png" /> are arbitrary constants.
+
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).
 
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).
Line 47: Line 131:
 
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, [[#References|[2]]]). In the case of a difference equation with constant coefficients,
 
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, [[#References|[2]]]). In the case of a difference equation with constant coefficients,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168041.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>
+
$$ \tag{7 }
 +
a _ {m} y _ {m + n }  + \dots + a _ {0} y _ {n}  = 0,
 +
$$
  
one can find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168042.png" /> linearly independent particular solutions immediately. Namely, consider the characteristic equation
+
one can find $  m $
 +
linearly independent particular solutions immediately. Namely, consider the characteristic equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168043.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>
+
$$ \tag{8 }
 +
a _ {m} q  ^ {m} +
 +
a _ {m - 1 }
 +
q ^ {m - 1 } + \dots +
 +
a _ {0}  = 0
 +
$$
  
and find its roots <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168044.png" />. If all the roots are simple, then the functions
+
and find its roots $  q _ {1} \dots q _ {m} $.  
 +
If all the roots are simple, then the functions
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168045.png" /></td> </tr></table>
+
$$
 +
y _ {n}  ^ {(} 1)  = \
 +
q _ {1}  ^ {n} \dots \
 +
y _ {n}  ^ {(} m)  = \
 +
q _ {m}  ^ {n}
 +
$$
  
are a linearly independent system of solutions to equation (7). When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168046.png" /> is a root of multiplicity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168047.png" />, the solutions
+
are a linearly independent system of solutions to equation (7). When $  q _ {k} $
 +
is a root of multiplicity $  r $,  
 +
the solutions
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168048.png" /></td> </tr></table>
+
$$
 +
q _ {k}  ^ {n} ,\
 +
nq _ {k}  ^ {n} \dots \
 +
n ^ {r - 1 }
 +
q _ {k}  ^ {n}
 +
$$
  
 
are linearly independent.
 
are linearly independent.
  
If the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168049.png" /> are real and equation (8) has a complex root, for example a simple root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168050.png" />, then instead of the complex solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168051.png" /> one obtains two linearly independent real solutions
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168052.png" /></td> </tr></table>
+
$$
 +
\rho  ^ {n}  \cos  n \phi ,\ \
 +
\rho  ^ {n}  \sin  n \phi .
 +
$$
  
 
Suppose one has a second-order difference equation with constant real coefficients,
 
Suppose one has a second-order difference equation with constant real coefficients,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168053.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>
+
$$ \tag{9 }
 +
a _ {2} y _ {n + 2 }  +
 +
a _ {1} y _ {n + 1 }  +
 +
a _ {0} y _ {n}  = 0.
 +
$$
  
 
The characteristic equation
 
The characteristic equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168054.png" /></td> </tr></table>
+
$$
 +
a _ {2} q  ^ {2} +
 +
a _ {1} q + a _ {0}  = 0
 +
$$
  
 
has the roots
 
has the roots
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168055.png" /></td> </tr></table>
+
$$
 +
q _ {1,2}  = \
  
When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168056.png" /> it is convenient to write the general solution to (9) in the form
+
\frac{- a _ {1} \pm
 +
\sqrt {a _ {1}  ^ {2} - 4a _ {0} a _ {2} } }{2a _ {2} }
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168057.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>
+
When  $  q _ {2} \neq q _ {1} $
 +
it is convenient to write the general solution to (9) in the form
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168059.png" /> are arbitrary constants. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168060.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168061.png" /> are complex conjugate roots:
+
$$ \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} }
 +
,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168062.png" /></td> </tr></table>
+
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
 
then another representation of the general solution is
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168063.png" /></td> <td valign="top" style="width:5%;text-align:right;">(11)</td></tr></table>
+
$$ \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
 
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168064.png" /></td> </tr></table>
+
$$
 +
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
 
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168065.png" /></td> <td valign="top" style="width:5%;text-align:right;">(12)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168066.png" /> is any real number, the solution of (12) is a polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168067.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168068.png" /> (a Chebyshev polynomial of the first kind), defined by
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168069.png" /></td> </tr></table>
+
$$
 +
T _ {n} ( x)  = \
 +
\cos ( n  \mathop{\rm arc}  \cos  x) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168070.png" /></td> </tr></table>
+
$$
 +
= \
 +
{
 +
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168071.png" /> satisfying, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168072.png" />, an equation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168073.png" /></td> <td valign="top" style="width:5%;text-align:right;">(13)</td></tr></table>
+
$$ \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,
 
and two linearly independent boundary conditions. Such boundary conditions can be, for example,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168074.png" /></td> <td valign="top" style="width:5%;text-align:right;">(14)</td></tr></table>
+
$$ \tag{14 }
 +
y _ {0= \
 +
\kappa _ {1} y _ {1} + \mu _ {1} ,\ \
 +
y _ {N}  = \
 +
\kappa _ {2} y _ {N - 1 }  +
 +
\mu _ {2} ,
 +
$$
  
 
or
 
or
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168075.png" /></td> <td valign="top" style="width:5%;text-align:right;">(15)</td></tr></table>
+
$$ \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
 
The following maximum principle is valid for a second-order difference equation. Given the problem (13), (15), let the conditions
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168076.png" /></td> </tr></table>
+
$$
 +
a _ {n}  > 0,\ \
 +
b _ {n}  > 0,\ \
 +
c _ {n}  \geq  \
 +
a _ {n} + b _ {n} ,\ \
 +
n = 1 \dots N - 1,
 +
$$
  
be fulfilled. Now if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168077.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168079.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168080.png" /> cannot have a greatest positive (smallest negative) value when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168081.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168082.png" /> and the right-hand side <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168083.png" />. The [[Shooting method|shooting method]] (see [[#References|[2]]]) can be applied to solve difference boundary value problems (13), (14).
+
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|shooting method]] (see [[#References|[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
 
One has constructed an explicit form of the solution to a non-linear difference equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168084.png" /></td> <td valign="top" style="width:5%;text-align:right;">(16)</td></tr></table>
+
$$ \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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168085.png" />, and a stability theory, which on the whole is analogous to the stability theory for ordinary differential equations, has been developed (see [[#References|[4]]], [[#References|[5]]]).
+
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 [[#References|[4]]], [[#References|[5]]]).
  
 
Multi-dimensional difference equations arise for difference approximations to partial differential equations (see [[#References|[2]]], [[#References|[6]]]). For example, the Poisson equation
 
Multi-dimensional difference equations arise for difference approximations to partial differential equations (see [[#References|[2]]], [[#References|[6]]]). For example, the Poisson equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168086.png" /></td> </tr></table>
+
$$
 +
 
 +
\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
 
can be approximated by the difference equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168087.png" /></td> </tr></table>
+
$$
 +
 
 +
\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
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168088.png" /></td> </tr></table>
+
$$
 +
u _ {i,j}  = \
 +
u ( x _ {1}  ^ {(} i) ,\
 +
x _ {2}  ^ {(} j) ),\ \
 +
x _ {1}  ^ {(} i)  = \
 +
ih _ {1} ,\ \
 +
x _ {2}  ^ {(} j)  = \
 +
jh _ {2} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168089.png" /></td> </tr></table>
+
$$
 +
i, j  = 0, \pm  1, \pm  2 \dots
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031680/d03168091.png" /> are the steps of the grid.
+
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|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|Difference schemes, theory of]]).
 
A system of multi-dimensional difference equations together with additional initial and boundary conditions forms a [[Difference scheme|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|Difference schemes, theory of]]).
Line 151: Line 398:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.O. [A.O. Gel'fond] Gelfond,  "Differenzenrechnung" , Deutsch. Verlag Wissenschaft.  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Samarskii,  E.S. Nikolaev,  "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.A. Samarskii,  Yu.N. Karamzin,  "Difference equations" , Moscow  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D.I. Martynyuk,  "Lectures on the qualitative theory of difference equations" , Kiev  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A. Halanay,  D. Wexler,  "Qualitative theory of impulse systems" , Acad. R.S. Romania  (1968)  (Translated from Rumanian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.A. Samarskii,  "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , '''2''' , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  A.D. Gorbunov,  "Difference equations" , Moscow  (1972)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.O. [A.O. Gel'fond] Gelfond,  "Differenzenrechnung" , Deutsch. Verlag Wissenschaft.  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Samarskii,  E.S. Nikolaev,  "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.A. Samarskii,  Yu.N. Karamzin,  "Difference equations" , Moscow  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D.I. Martynyuk,  "Lectures on the qualitative theory of difference equations" , Kiev  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A. Halanay,  D. Wexler,  "Qualitative theory of impulse systems" , Acad. R.S. Romania  (1968)  (Translated from Rumanian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.A. Samarskii,  "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  I.S. Berezin,  N.P. Zhidkov,  "Computing methods" , '''2''' , Pergamon  (1973)  (Translated from Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  N.S. Bakhvalov,  "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  A.D. Gorbunov,  "Difference equations" , Moscow  (1972)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Revision as of 17:33, 5 June 2020


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)
How to Cite This Entry:
Difference equation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Difference_equation&oldid=46653
This article was adapted from an original article by A.V. GulinA.A. Samarskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article