Namespaces
Variants
Actions

Difference between revisions of "Difference scheme"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
A system of difference equations (cf. [[Difference equation|Difference equation]]) approximating a differential equation and subsidiary (initial, boundary and other) conditions. Approximating an original differential problem by a difference scheme is one of the methods of approximating the original problem by a discrete problem. For this the given region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317201.png" /> of independent variables is replaced by a discrete set of points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317202.png" /> — the grid, and the derivatives entering into the differential equation are replaced by difference relations on the grid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317203.png" />. As a result of such a change one obtains a closed system of a large number of algebraic equations (linear or non-linear, depending on the original differential equation) which makes up the difference scheme. In essence a difference scheme is a family of difference equations depending on the steps of the grid. The solution of a difference scheme also depends parametrically on the steps of the grid. A difference scheme is a multi-parameter and complicated object. Besides the coefficients of the original differential equation it contains also its own characteristic parameters, such as the steps with respect to time and space, weight factors, and others. The influence of these parameters can substantially distort the representation of the behaviour of the original differential problem.
+
<!--
 +
d0317201.png
 +
$#A+1 = 15 n = 0
 +
$#C+1 = 15 : ~/encyclopedia/old_files/data/D031/D.0301720 Difference scheme
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
A system of difference equations (cf. [[Difference equation|Difference equation]]) approximating a differential equation and subsidiary (initial, boundary and other) conditions. Approximating an original differential problem by a difference scheme is one of the methods of approximating the original problem by a discrete problem. For this the given region $  G $
 +
of independent variables is replaced by a discrete set of points $  G _ {h} $—  
 +
the grid, and the derivatives entering into the differential equation are replaced by difference relations on the grid $  G _ {h} $.  
 +
As a result of such a change one obtains a closed system of a large number of algebraic equations (linear or non-linear, depending on the original differential equation) which makes up the difference scheme. In essence a difference scheme is a family of difference equations depending on the steps of the grid. The solution of a difference scheme also depends parametrically on the steps of the grid. A difference scheme is a multi-parameter and complicated object. Besides the coefficients of the original differential equation it contains also its own characteristic parameters, such as the steps with respect to time and space, weight factors, and others. The influence of these parameters can substantially distort the representation of the behaviour of the original differential problem.
  
 
The following questions are being studied in connection with the approximation by difference schemes of differential equations: means of constructing a difference scheme; the convergence under grid refinement of the solution of the difference problem to the solution of the original differential equation; and methods for solving systems of difference equations. All the questions listed are considered in the theory of difference schemes (cf. [[Difference schemes, theory of|Difference schemes, theory of]]). Effective numerical methods for solving typical difference schemes for ordinary and partial differential equations, assuming the use of a high-speed computer, have been developed.
 
The following questions are being studied in connection with the approximation by difference schemes of differential equations: means of constructing a difference scheme; the convergence under grid refinement of the solution of the difference problem to the solution of the original differential equation; and methods for solving systems of difference equations. All the questions listed are considered in the theory of difference schemes (cf. [[Difference schemes, theory of|Difference schemes, theory of]]). Effective numerical methods for solving typical difference schemes for ordinary and partial differential equations, assuming the use of a high-speed computer, have been developed.
Line 5: Line 20:
 
A simple example of a difference scheme is given below. Suppose one is given the differential equation
 
A simple example of a difference scheme is given below. Suppose one is given the differential 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/d031720/d0317204.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\left .
  
The domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317205.png" /> is replaced by the grid
+
\begin{array}{c}
 +
u  ^ {\prime\prime} ( x) - q ( x) u ( x)  =  - f ( x),\ \
 +
q ( x)  \geq  0,\ \
 +
0 < x < 1,  \\
 +
u  ^  \prime  ( 0)  = \
 +
\sigma u ( 0) -
 +
\mu _ {1} ,\ \
 +
u ( 1)  = \
 +
\mu _ {2} ,\ \
 +
\sigma > 0. \\
 +
\end{array}
  
<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/d031720/d0317206.png" /></td> </tr></table>
+
\right \}
 +
$$
 +
 
 +
The domain  $  G = \{ 0 < x < 1 \} $
 +
is replaced by the grid
 +
 
 +
$$
 +
G _ {h}  = \
 +
\{ {x _ {i} = ih } : {
 +
i = 0 \dots N;  hN = 1 } \}
 +
.
 +
$$
  
 
A difference scheme for problem (1) has the form
 
A difference scheme for problem (1) 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/d031720/d0317207.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
\left .
 +
 
 +
\begin{array}{c}
 +
 
 +
\frac{y _ {i + 1 }  - 2y _ {i} + y _ {i - 1 }  }{h  ^ {2} }
 +
-
 +
q _ {i} y _ {i}  = - f _ {i} ,\ \
 +
i = 1 \dots N - 1,  \\
 +
{
 +
\frac{y _ {1} - y _ {0} }{h}
 +
= \
 +
( \sigma + 0.5hq _ {0} ) y _ {0} -
 +
( \mu _ {1} + 0.5hf _ {0} )
 +
y _ {N}  = \mu _ {2} ,  \\
 +
\end{array}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317208.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d0317209.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d03172010.png" />. It can be shown that, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d03172011.png" />, the solution to the difference problem (2) converges to the solution of the original problem (1) for sufficiently smooth functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d03172012.png" />.
+
\right \}
 +
$$
 +
 
 +
where $  y _ {i} = y ( x _ {i} ) $,  
 +
$  q _ {i} = q ( x _ {i} ) $,  
 +
$  x _ {i} \in G _ {h} $.  
 +
It can be shown that, as $  h \rightarrow 0 $,  
 +
the solution to the difference problem (2) converges to the solution of the original problem (1) for sufficiently smooth functions $  q , f $.
  
 
The difference scheme (2) has second-order accuracy, that is,
 
The difference scheme (2) has second-order accuracy, that 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/d031720/d03172013.png" /></td> </tr></table>
+
$$
 +
\max _ {0 \leq  i \leq  N } \
 +
| y _ {i} - u ( x _ {i} ) |  \leq  \
 +
Mh  ^ {2} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d03172014.png" /> is a constant that does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031720/d03172015.png" />. The solution to the difference scheme (2) can be found by the [[Shooting method|shooting method]].
+
where $  M $
 +
is a constant that does not depend on $  h $.  
 +
The solution to the difference scheme (2) can be found by the [[Shooting method|shooting method]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</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">[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></table>
 
<table><TR><TD valign="top">[1]</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">[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></table>
 
 
  
 
====Comments====
 
====Comments====
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.E. Forsythe,  W.R. Wasow,  "Finite difference methods for partial differential equations" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.R. Garabedian,  "Partial differential equations" , Wiley  (1964)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I. Gladwell (ed.)  R. Wait (ed.) , ''A survey of numerical methods for partial differential equations'' , Clarendon Press  (1979)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Mitchell,  D.F. Griffiths,  "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.D. Richtmeyer,  K.W. Morton,  "Difference methods for initial value problems" , Wiley  (1967)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G.D. Smith,  "Numerical solution of partial differential equations" , Oxford Univ. Press  (1977)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  N.N. Yanenko,  "The method of fractional steps: solution of problems of mathematical physics in several variables" , Springer  (1971)  (Translated from Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.E. Forsythe,  W.R. Wasow,  "Finite difference methods for partial differential equations" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.R. Garabedian,  "Partial differential equations" , Wiley  (1964)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I. Gladwell (ed.)  R. Wait (ed.) , ''A survey of numerical methods for partial differential equations'' , Clarendon Press  (1979)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Mitchell,  D.F. Griffiths,  "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.D. Richtmeyer,  K.W. Morton,  "Difference methods for initial value problems" , Wiley  (1967)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G.D. Smith,  "Numerical solution of partial differential equations" , Oxford Univ. Press  (1977)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  N.N. Yanenko,  "The method of fractional steps: solution of problems of mathematical physics in several variables" , Springer  (1971)  (Translated from Russian)</TD></TR></table>

Revision as of 17:33, 5 June 2020


A system of difference equations (cf. Difference equation) approximating a differential equation and subsidiary (initial, boundary and other) conditions. Approximating an original differential problem by a difference scheme is one of the methods of approximating the original problem by a discrete problem. For this the given region $ G $ of independent variables is replaced by a discrete set of points $ G _ {h} $— the grid, and the derivatives entering into the differential equation are replaced by difference relations on the grid $ G _ {h} $. As a result of such a change one obtains a closed system of a large number of algebraic equations (linear or non-linear, depending on the original differential equation) which makes up the difference scheme. In essence a difference scheme is a family of difference equations depending on the steps of the grid. The solution of a difference scheme also depends parametrically on the steps of the grid. A difference scheme is a multi-parameter and complicated object. Besides the coefficients of the original differential equation it contains also its own characteristic parameters, such as the steps with respect to time and space, weight factors, and others. The influence of these parameters can substantially distort the representation of the behaviour of the original differential problem.

The following questions are being studied in connection with the approximation by difference schemes of differential equations: means of constructing a difference scheme; the convergence under grid refinement of the solution of the difference problem to the solution of the original differential equation; and methods for solving systems of difference equations. All the questions listed are considered in the theory of difference schemes (cf. Difference schemes, theory of). Effective numerical methods for solving typical difference schemes for ordinary and partial differential equations, assuming the use of a high-speed computer, have been developed.

A simple example of a difference scheme is given below. Suppose one is given the differential equation

$$ \tag{1 } \left . \begin{array}{c} u ^ {\prime\prime} ( x) - q ( x) u ( x) = - f ( x),\ \ q ( x) \geq 0,\ \ 0 < x < 1, \\ u ^ \prime ( 0) = \ \sigma u ( 0) - \mu _ {1} ,\ \ u ( 1) = \ \mu _ {2} ,\ \ \sigma > 0. \\ \end{array} \right \} $$

The domain $ G = \{ 0 < x < 1 \} $ is replaced by the grid

$$ G _ {h} = \ \{ {x _ {i} = ih } : { i = 0 \dots N; hN = 1 } \} . $$

A difference scheme for problem (1) has the form

$$ \tag{2 } \left . \begin{array}{c} \frac{y _ {i + 1 } - 2y _ {i} + y _ {i - 1 } }{h ^ {2} } - q _ {i} y _ {i} = - f _ {i} ,\ \ i = 1 \dots N - 1, \\ { \frac{y _ {1} - y _ {0} }{h} } = \ ( \sigma + 0.5hq _ {0} ) y _ {0} - ( \mu _ {1} + 0.5hf _ {0} ) y _ {N} = \mu _ {2} , \\ \end{array} \right \} $$

where $ y _ {i} = y ( x _ {i} ) $, $ q _ {i} = q ( x _ {i} ) $, $ x _ {i} \in G _ {h} $. It can be shown that, as $ h \rightarrow 0 $, the solution to the difference problem (2) converges to the solution of the original problem (1) for sufficiently smooth functions $ q , f $.

The difference scheme (2) has second-order accuracy, that is,

$$ \max _ {0 \leq i \leq N } \ | y _ {i} - u ( x _ {i} ) | \leq \ Mh ^ {2} , $$

where $ M $ is a constant that does not depend on $ h $. The solution to the difference scheme (2) can be found by the shooting method.

References

[1] A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[2] A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)

Comments

References

[a1] G.E. Forsythe, W.R. Wasow, "Finite difference methods for partial differential equations" , Wiley (1960)
[a2] P.R. Garabedian, "Partial differential equations" , Wiley (1964)
[a3] I. Gladwell (ed.) R. Wait (ed.) , A survey of numerical methods for partial differential equations , Clarendon Press (1979)
[a4] A.R. Mitchell, D.F. Griffiths, "The finite difference method in partial differential equations" , Wiley (1980)
[a5] R.D. Richtmeyer, K.W. Morton, "Difference methods for initial value problems" , Wiley (1967)
[a6] G.D. Smith, "Numerical solution of partial differential equations" , Oxford Univ. Press (1977)
[a7] N.N. Yanenko, "The method of fractional steps: solution of problems of mathematical physics in several variables" , Springer (1971) (Translated from Russian)
How to Cite This Entry:
Difference scheme. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Difference_scheme&oldid=46655
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