Difference between revisions of "Approximation of a differential boundary value problem by difference boundary value problems"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex done) |
||
Line 1: | Line 1: | ||
+ | {{TEX|done}} | ||
+ | |||
An approximation of a differential equation and its boundary conditions by a system of finite (usually algebraic) equations giving the values of the unknown function on some grid, which is subsequently made more exact by making the parameter of the finite-difference problem (the step of the grid, the mesh) tend to zero. | An approximation of a differential equation and its boundary conditions by a system of finite (usually algebraic) equations giving the values of the unknown function on some grid, which is subsequently made more exact by making the parameter of the finite-difference problem (the step of the grid, the mesh) tend to zero. | ||
− | Consider the computation of a function | + | Consider the computation of a function $ u $ |
+ | which belongs to a linear normed space $ U $ | ||
+ | of functions defined in a given domain $ D _{U} $ | ||
+ | with boundary $ \Gamma $, | ||
+ | and which is the solution of the differential boundary value problem $ Lu = 0 $, | ||
+ | $ lu \mid _ \Gamma = 0 $, | ||
+ | where $ Lu = 0 $ | ||
+ | is a differential equation, while $ lu \mid _ \Gamma = 0 $ | ||
+ | is the set of boundary conditions. Let $ D _{ {hU}} $ | ||
+ | be a grid (cf. [[Approximation of a differential operator by difference operators|Approximation of a differential operator by difference operators]]) and let $ U _{h} $ | ||
+ | be the normed linear space of functions $ u _{h} $ | ||
+ | defined on this grid. Let $ [v] _{h} $ | ||
+ | be a table of values of the function $ v $ | ||
+ | at the points of $ D _{ {hU}} $. | ||
+ | A norm is introduced into $ U _{h} $ | ||
+ | so that the equality | ||
− | + | $$ | |
+ | \lim\limits _ {h \rightarrow 0} \ \| [ v ] _{h} \| _{ {U _ h}} \ = \ \| v \| _{U} $$ | ||
− | is valid for any function | + | is valid for any function $ v \in U $. |
+ | The problem of computing the solution $ u $ | ||
+ | is replaced by a certain problem $ {\mathcal L} _{h} u _{h} = 0 $ | ||
+ | for the approximate computation of the table $ [u] _{h} $ | ||
+ | of values of $ u $ | ||
+ | at the points of $ D _{ {hU}} $. | ||
+ | Here, $ {\mathcal L} _{h} u _{h} $ | ||
+ | is a certain set of (non-differential) equations for the values of the grid function $ u _{h} \in U _{h} $. | ||
− | Let | + | Let $ v _{h} $ |
+ | be an arbitrary function of $ U _{h} $, | ||
+ | let $ {\mathcal L} _{h} v _{h} = \phi _{h} $, | ||
+ | and let $ \Phi _{h} $ | ||
+ | be the normed linear space to which $ \phi _{h} $ | ||
+ | belongs for any $ v _{h} \in U _{h} $. | ||
+ | One says that the problem $ {\mathcal L} _{h} u _{h} $ | ||
+ | is a finite-difference approximation of order $ p $ | ||
+ | of the differential boundary value problem $ Lu = 0 $, | ||
+ | $ lu \mid _ \Gamma =0 $, | ||
+ | on the space of solutions $ u $ | ||
+ | of the latter if | ||
− | + | $$ | |
+ | \| {\mathcal L} _{h} [ u ] _{h} \| _ { \Phi _ h } \ = \ | ||
+ | O ( h^{p} ) . | ||
+ | $$ | ||
− | The actual construction of the system | + | The actual construction of the system $ {\mathcal L} _{h} u _{h} $ |
+ | involves a separate construction of its two subsystems $ L _{h} u _{h} = 0 $ | ||
+ | and $ l _{h} u _{h} \mid _{ {\Gamma _ h}} = 0 $. | ||
+ | For $ L _{h} u _{h} = 0 $ | ||
+ | one uses the difference approximations of a differential equation (cf. [[Approximation of a differential equation by difference equations|Approximation of a differential equation by difference equations]]). The complementary equations $ l _{h} u _{h} \mid _{ {\Gamma _ h}} = 0 $ | ||
+ | are constructed using the boundary conditions $ lu _{h} \mid _ \Gamma = 0 $. | ||
− | An approximation such as has just been described never ensures [[#References|[2]]] that the solution | + | An approximation such as has just been described never ensures [[#References|[2]]] that the solution $ u _{h} $ |
+ | of the finite-difference problem converges to the exact solution $ u $, | ||
+ | i.e. that the equality | ||
− | + | $$ | |
+ | \lim\limits _ {h \rightarrow 0} \ \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ 0 | ||
+ | $$ | ||
− | is valid, no matter how the norms in | + | is valid, no matter how the norms in $ U _{h} $ |
+ | and $ \Phi _{h} $ | ||
+ | have been chosen. | ||
− | The additional condition, the fulfillment of which in fact ensures convergence, is stability [[#References|[3]]], [[#References|[5]]]–[[#References|[8]]], which must be displayed by the finite-difference problem | + | The additional condition, the fulfillment of which in fact ensures convergence, is stability [[#References|[3]]], [[#References|[5]]]–[[#References|[8]]], which must be displayed by the finite-difference problem $ {\mathcal L} _{h} u _{h} = 0 $. |
+ | This problem is called stable if there exist numbers $ \delta > 0 $ | ||
+ | and $ 0 < h _{0} $ | ||
+ | such that the equation $ {\mathcal L} _{h} z _{h} = \phi _{h} $ | ||
+ | has a unique solution $ z _{h} \in U _{h} $ | ||
+ | for any $ \phi _{h} \in \Phi _{h} $, | ||
+ | $ \| \phi _{h} \| < \delta $, | ||
+ | $ h < h _{0} $, | ||
+ | and if this solution satisfies the inequality | ||
− | + | $$ | |
+ | \| z _{h} -u _{h} \| _{ {U _ h}} \ \leq \ C \ \| \phi _{h} \| _{ {\Phi _ h}} , | ||
+ | $$ | ||
− | where | + | where $ C $ |
+ | is a constant not depending on $ h $ | ||
+ | or on the perturbation $ \phi _{h} $ | ||
+ | of the right-hand side, while $ u _{h} $ | ||
+ | is a solution of the unperturbed problem $ {\mathcal L} _{h} u _{h} = 0 $. | ||
+ | If a solution $ u $ | ||
+ | of the differential problem exists, while the finite-difference problem $ {\mathcal L} _{h} u _{h} $ | ||
+ | approximates the differential problem on solutions $ u $ | ||
+ | of order $ p $ | ||
+ | and is stable, then one has convergence of the same order, i.e. | ||
− | + | $$ | |
+ | \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ O ( h^{p} ) . | ||
+ | $$ | ||
For instance, the problem | For instance, the problem | ||
− | + | $$ \tag{1} | |
+ | \left . { { | ||
+ | L (u) \ \equiv \ | ||
+ | \frac{\partial u}{\partial t} | ||
+ | - | ||
+ | \frac{\partial u}{\partial x} | ||
+ | \ = \ | ||
+ | 0,\ \ t > 0,\ \ - \infty < x < \infty ,} \atop { | ||
+ | | lu | _ \Gamma \ = \ u ( 0 ,\ x ) - \psi (x) \ = \ 0,\ \ - \infty | ||
+ | < x < \infty , | ||
+ | }} \right \} | ||
+ | $$ | ||
− | where | + | where $ \psi (x) $ |
+ | is a given function with a bounded second-order derivative, can be approximated, for a natural definition of the norms, by the finite-difference problem | ||
− | + | $$ \tag{2} | |
+ | {\mathcal L} _{h} u _{h} \ = \ | ||
+ | \left \{ { { | ||
+ | L _{h} u _{h} \ = \ | ||
+ | \frac{u _ m^{n+1} -u _{m} ^ n} \tau | ||
+ | - | ||
+ | \frac{u _ m+1^{n} -u _{m} ^ n}{h} | ||
+ | \ = \ 0} \atop {| l _{h} u _{h} | _ { \Gamma _ h } \ \equiv \ | ||
+ | u _ m^{0} - \psi (mh) \ = \ 0}} | ||
+ | \right \}\ = | ||
+ | $$ | ||
− | + | $$ | |
+ | = \ | ||
+ | 0 \ \in \ \Phi _{h} , | ||
+ | $$ | ||
− | where | + | where $ u _ m^{n} $ |
+ | is the value of $ u _{h} $ | ||
+ | at $ ( x _{m} ,\ t _{n} ) = (mh,\ n \tau ) $, | ||
+ | $ \tau = rh $, | ||
+ | $ r = \textrm{ const } $. | ||
+ | If the norm of $ \phi _{n} $ | ||
+ | is taken to be the upper bound of the moduli of the right-hand sides of the equations which constitute the system $ {\mathcal L} _{h} v _{h} = \phi _{h} $, | ||
+ | $ v _{h} \in U _{h} $, | ||
+ | then the approximation of problem (1) by problem (2) on solutions $ u $ | ||
+ | is of the first order. If $ r > 1 $, | ||
+ | there is no convergence, whatever the norm. If $ r \leq 1 $ | ||
+ | and the norm is | ||
− | + | $$ | |
+ | \| u _{h} \| _{ {U _ h}} \ = \ \sup _ { m,n } \ | u _ m^{n} | , | ||
+ | $$ | ||
the problem is stable, so that there is convergence [[#References|[2]]], [[#References|[3]]]: | the problem is stable, so that there is convergence [[#References|[2]]], [[#References|[3]]]: | ||
− | + | $$ | |
+ | \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ O (h) . | ||
+ | $$ | ||
The replacement of differential problems by difference problems is one of the most universal methods for the approximate computation of solutions of differential boundary value problems on a computer [[#References|[7]]]. | The replacement of differential problems by difference problems is one of the most universal methods for the approximate computation of solutions of differential boundary value problems on a computer [[#References|[7]]]. | ||
− | The replacement of differential problems by their difference analogues started in the works [[#References|[1]]], [[#References|[2]]] and [[#References|[4]]], and is sometimes employed to prove that the differential problem is in fact solvable. This is done as follows. It is proved that the set of solutions | + | The replacement of differential problems by their difference analogues started in the works [[#References|[1]]], [[#References|[2]]] and [[#References|[4]]], and is sometimes employed to prove that the differential problem is in fact solvable. This is done as follows. It is proved that the set of solutions $ u _{h} $ |
+ | of the difference analogue of the differential boundary value problem is compact with respect to $ h $, | ||
+ | after which a proof is given that a solution $ u $ | ||
+ | of the differential boundary value problem is the limit of a subsequence $ u _{ {h _ k}} $ | ||
+ | which converges as $ h _{k} \rightarrow 0 $. | ||
+ | If this solution is known to be unique, then not only the subsequence, but also the entire set of $ u _{h} $ | ||
+ | converges to the solution $ u $ | ||
+ | as $ h \rightarrow 0 $. | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> L.A. Lyusternik, "Dirichlet's problem" ''Uspekhi Mat. Nauk'' , '''8''' (1940) pp. 125–124 (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> R. Courant, K. Friedrichs, H. Lewy, "Ueber die partiellen Differenzengleichungen der mathematischen Physik" ''Math. Ann.'' , '''100''' (1928)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> I.G. Petrovskii, "New existence proofs for the solution of the Dirichlet problem by the method of finite differences" ''Uspekhi Mat. Nauk'' , '''8''' (1940) pp. 161–170 (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> V.S. Ryaben'kii, "On the application of the method of finite differences to the solution of the Cauchy problem" ''Dokl. Akad. Nauk SSSR'' , '''86''' : 6 (1952) pp. 1071–1073 (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> V.S. [V.S. Ryaben'kii] Rjabenki, A.F. [A.F. Filippov] Filipov, "Über die stabilität von Differenzgleichungen" , Deutsch. Verlag Wissenschaft. (1960) (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</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">[8]</TD> <TD valign="top"> A.F. Filippov, "On stability of difference equations" ''Dokl. Akad. Nauk SSSR'' , '''100''' : 6 (1955) pp. 1045–1048 (In Russian)</TD></TR></table> | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> L.A. Lyusternik, "Dirichlet's problem" ''Uspekhi Mat. Nauk'' , '''8''' (1940) pp. 125–124 (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> R. Courant, K. Friedrichs, H. Lewy, "Ueber die partiellen Differenzengleichungen der mathematischen Physik" ''Math. Ann.'' , '''100''' (1928)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> I.G. Petrovskii, "New existence proofs for the solution of the Dirichlet problem by the method of finite differences" ''Uspekhi Mat. Nauk'' , '''8''' (1940) pp. 161–170 (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> V.S. Ryaben'kii, "On the application of the method of finite differences to the solution of the Cauchy problem" ''Dokl. Akad. Nauk SSSR'' , '''86''' : 6 (1952) pp. 1071–1073 (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> V.S. [V.S. Ryaben'kii] Rjabenki, A.F. [A.F. Filippov] Filipov, "Über die stabilität von Differenzgleichungen" , Deutsch. Verlag Wissenschaft. (1960) (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</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">[8]</TD> <TD valign="top"> A.F. Filippov, "On stability of difference equations" ''Dokl. Akad. Nauk SSSR'' , '''100''' : 6 (1955) pp. 1045–1048 (In Russian)</TD></TR></table> | ||
− | |||
− | |||
====Comments==== | ====Comments==== | ||
For additional references, see the additional references to [[Approximation of a differential operator by difference operators|Approximation of a differential operator by difference operators]]. | For additional references, see the additional references to [[Approximation of a differential operator by difference operators|Approximation of a differential operator by difference operators]]. |
Latest revision as of 20:44, 29 January 2020
An approximation of a differential equation and its boundary conditions by a system of finite (usually algebraic) equations giving the values of the unknown function on some grid, which is subsequently made more exact by making the parameter of the finite-difference problem (the step of the grid, the mesh) tend to zero.
Consider the computation of a function $ u $ which belongs to a linear normed space $ U $ of functions defined in a given domain $ D _{U} $ with boundary $ \Gamma $, and which is the solution of the differential boundary value problem $ Lu = 0 $, $ lu \mid _ \Gamma = 0 $, where $ Lu = 0 $ is a differential equation, while $ lu \mid _ \Gamma = 0 $ is the set of boundary conditions. Let $ D _{ {hU}} $ be a grid (cf. Approximation of a differential operator by difference operators) and let $ U _{h} $ be the normed linear space of functions $ u _{h} $ defined on this grid. Let $ [v] _{h} $ be a table of values of the function $ v $ at the points of $ D _{ {hU}} $. A norm is introduced into $ U _{h} $ so that the equality
$$ \lim\limits _ {h \rightarrow 0} \ \| [ v ] _{h} \| _{ {U _ h}} \ = \ \| v \| _{U} $$
is valid for any function $ v \in U $. The problem of computing the solution $ u $ is replaced by a certain problem $ {\mathcal L} _{h} u _{h} = 0 $ for the approximate computation of the table $ [u] _{h} $ of values of $ u $ at the points of $ D _{ {hU}} $. Here, $ {\mathcal L} _{h} u _{h} $ is a certain set of (non-differential) equations for the values of the grid function $ u _{h} \in U _{h} $.
Let $ v _{h} $ be an arbitrary function of $ U _{h} $, let $ {\mathcal L} _{h} v _{h} = \phi _{h} $, and let $ \Phi _{h} $ be the normed linear space to which $ \phi _{h} $ belongs for any $ v _{h} \in U _{h} $. One says that the problem $ {\mathcal L} _{h} u _{h} $ is a finite-difference approximation of order $ p $ of the differential boundary value problem $ Lu = 0 $, $ lu \mid _ \Gamma =0 $, on the space of solutions $ u $ of the latter if
$$ \| {\mathcal L} _{h} [ u ] _{h} \| _ { \Phi _ h } \ = \ O ( h^{p} ) . $$
The actual construction of the system $ {\mathcal L} _{h} u _{h} $ involves a separate construction of its two subsystems $ L _{h} u _{h} = 0 $ and $ l _{h} u _{h} \mid _{ {\Gamma _ h}} = 0 $. For $ L _{h} u _{h} = 0 $ one uses the difference approximations of a differential equation (cf. Approximation of a differential equation by difference equations). The complementary equations $ l _{h} u _{h} \mid _{ {\Gamma _ h}} = 0 $ are constructed using the boundary conditions $ lu _{h} \mid _ \Gamma = 0 $.
An approximation such as has just been described never ensures [2] that the solution $ u _{h} $ of the finite-difference problem converges to the exact solution $ u $, i.e. that the equality
$$ \lim\limits _ {h \rightarrow 0} \ \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ 0 $$
is valid, no matter how the norms in $ U _{h} $ and $ \Phi _{h} $ have been chosen.
The additional condition, the fulfillment of which in fact ensures convergence, is stability [3], [5]–[8], which must be displayed by the finite-difference problem $ {\mathcal L} _{h} u _{h} = 0 $. This problem is called stable if there exist numbers $ \delta > 0 $ and $ 0 < h _{0} $ such that the equation $ {\mathcal L} _{h} z _{h} = \phi _{h} $ has a unique solution $ z _{h} \in U _{h} $ for any $ \phi _{h} \in \Phi _{h} $, $ \| \phi _{h} \| < \delta $, $ h < h _{0} $, and if this solution satisfies the inequality
$$ \| z _{h} -u _{h} \| _{ {U _ h}} \ \leq \ C \ \| \phi _{h} \| _{ {\Phi _ h}} , $$
where $ C $ is a constant not depending on $ h $ or on the perturbation $ \phi _{h} $ of the right-hand side, while $ u _{h} $ is a solution of the unperturbed problem $ {\mathcal L} _{h} u _{h} = 0 $. If a solution $ u $ of the differential problem exists, while the finite-difference problem $ {\mathcal L} _{h} u _{h} $ approximates the differential problem on solutions $ u $ of order $ p $ and is stable, then one has convergence of the same order, i.e.
$$ \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ O ( h^{p} ) . $$
For instance, the problem
$$ \tag{1} \left . { { L (u) \ \equiv \ \frac{\partial u}{\partial t} - \frac{\partial u}{\partial x} \ = \ 0,\ \ t > 0,\ \ - \infty < x < \infty ,} \atop { | lu | _ \Gamma \ = \ u ( 0 ,\ x ) - \psi (x) \ = \ 0,\ \ - \infty < x < \infty , }} \right \} $$
where $ \psi (x) $ is a given function with a bounded second-order derivative, can be approximated, for a natural definition of the norms, by the finite-difference problem
$$ \tag{2} {\mathcal L} _{h} u _{h} \ = \ \left \{ { { L _{h} u _{h} \ = \ \frac{u _ m^{n+1} -u _{m} ^ n} \tau - \frac{u _ m+1^{n} -u _{m} ^ n}{h} \ = \ 0} \atop {| l _{h} u _{h} | _ { \Gamma _ h } \ \equiv \ u _ m^{0} - \psi (mh) \ = \ 0}} \right \}\ = $$
$$ = \ 0 \ \in \ \Phi _{h} , $$
where $ u _ m^{n} $ is the value of $ u _{h} $ at $ ( x _{m} ,\ t _{n} ) = (mh,\ n \tau ) $, $ \tau = rh $, $ r = \textrm{ const } $. If the norm of $ \phi _{n} $ is taken to be the upper bound of the moduli of the right-hand sides of the equations which constitute the system $ {\mathcal L} _{h} v _{h} = \phi _{h} $, $ v _{h} \in U _{h} $, then the approximation of problem (1) by problem (2) on solutions $ u $ is of the first order. If $ r > 1 $, there is no convergence, whatever the norm. If $ r \leq 1 $ and the norm is
$$ \| u _{h} \| _{ {U _ h}} \ = \ \sup _ { m,n } \ | u _ m^{n} | , $$
the problem is stable, so that there is convergence [2], [3]:
$$ \| [ u ] _{h} -u _{h} \| _{ {U _ h}} \ = \ O (h) . $$
The replacement of differential problems by difference problems is one of the most universal methods for the approximate computation of solutions of differential boundary value problems on a computer [7].
The replacement of differential problems by their difference analogues started in the works [1], [2] and [4], and is sometimes employed to prove that the differential problem is in fact solvable. This is done as follows. It is proved that the set of solutions $ u _{h} $ of the difference analogue of the differential boundary value problem is compact with respect to $ h $, after which a proof is given that a solution $ u $ of the differential boundary value problem is the limit of a subsequence $ u _{ {h _ k}} $ which converges as $ h _{k} \rightarrow 0 $. If this solution is known to be unique, then not only the subsequence, but also the entire set of $ u _{h} $ converges to the solution $ u $ as $ h \rightarrow 0 $.
References
[1] | L.A. Lyusternik, "Dirichlet's problem" Uspekhi Mat. Nauk , 8 (1940) pp. 125–124 (In Russian) |
[2] | R. Courant, K. Friedrichs, H. Lewy, "Ueber die partiellen Differenzengleichungen der mathematischen Physik" Math. Ann. , 100 (1928) |
[3] | S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian) |
[4] | I.G. Petrovskii, "New existence proofs for the solution of the Dirichlet problem by the method of finite differences" Uspekhi Mat. Nauk , 8 (1940) pp. 161–170 (In Russian) |
[5] | V.S. Ryaben'kii, "On the application of the method of finite differences to the solution of the Cauchy problem" Dokl. Akad. Nauk SSSR , 86 : 6 (1952) pp. 1071–1073 (In Russian) |
[6] | V.S. [V.S. Ryaben'kii] Rjabenki, A.F. [A.F. Filippov] Filipov, "Über die stabilität von Differenzgleichungen" , Deutsch. Verlag Wissenschaft. (1960) (Translated from Russian) |
[7] | A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian) |
[8] | A.F. Filippov, "On stability of difference equations" Dokl. Akad. Nauk SSSR , 100 : 6 (1955) pp. 1045–1048 (In Russian) |
Comments
For additional references, see the additional references to Approximation of a differential operator by difference operators.
Approximation of a differential boundary value problem by difference boundary value problems. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Approximation_of_a_differential_boundary_value_problem_by_difference_boundary_value_problems&oldid=13955