Namespaces
Variants
Actions

Difference between revisions of "Alternating-direction implicit method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A method introduced in 1955 by D.W. Peaceman and H.H. Rachford [[#References|[a3]]] and J. Douglas [[#References|[a1]]] as a technique for the numerical solution of elliptic and parabolic differential equations (cf. [[Elliptic partial differential equation|Elliptic partial differential equation]]; [[Parabolic partial differential equation|Parabolic partial differential equation]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105401.png" /> be a bounded region and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105402.png" /> continuous functions with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105403.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105404.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105405.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105406.png" />. The discretization of the elliptic boundary value problem (cf. [[Boundary value problem, elliptic equations|Boundary value problem, elliptic equations]])
+
<!--
 +
a1105401.png
 +
$#A+1 = 31 n = 1
 +
$#C+1 = 31 : ~/encyclopedia/old_files/data/A110/A.1100540 Alternating\AAhdirection implicit method
 +
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/a/a110/a110540/a1105407.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/a/a110/a110540/a1105408.png" /></td> </tr></table>
+
A method introduced in 1955 by D.W. Peaceman and H.H. Rachford [[#References|[a3]]] and J. Douglas [[#References|[a1]]] as a technique for the numerical solution of elliptic and parabolic differential equations (cf. [[Elliptic partial differential equation|Elliptic partial differential equation]]; [[Parabolic partial differential equation|Parabolic partial differential equation]]). Let  $  \Omega \in \mathbf R  ^ {2} $
 +
be a bounded region and  $  K _ {1} ,K _ {2} , K _ {0} $
 +
continuous functions with  $  K _ {1} ( x,y ) > 0 $,
 +
$  K _ {2} ( x,y ) > 0 $,
 +
$  K _ {0} ( x,y ) \geq  0 $
 +
in  $  \Omega $.  
 +
The discretization of the elliptic boundary value problem (cf. [[Boundary value problem, elliptic equations|Boundary value problem, elliptic equations]])
  
in a bounded region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a1105409.png" /> by finite differences leads to a system of linear equations of the form
+
$$
 +
- ( K _ {1} u _ {x} ) _ {x} - ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f  \textrm{ in  }  \Omega,
 +
$$
  
<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/a/a110/a110540/a11054010.png" /></td> </tr></table>
+
$$
 +
u = g  \textrm{ on  }  \partial  \Omega,
 +
$$
  
Here, the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054012.png" /> stand for the discretization of the differential operators in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054013.png" /> (horizontal) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054014.png" /> (vertical) direction, respectively, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054015.png" /> is a diagonal matrix representing multiplication by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054016.png" />. The alternating-direction implicit method attempts to solve this linear system by the iteration
+
in a bounded region  $  \Omega \subset  \mathbf R  ^ {2} $
 +
by finite differences leads to a system of linear equations 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/a/a110/a110540/a11054017.png" /></td> </tr></table>
+
$$
 +
( H + V + S ) \mathbf u = \mathbf f .
 +
$$
  
<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/a/a110/a110540/a11054018.png" /></td> </tr></table>
+
Here, the matrices  $  H $
 +
and  $  V $
 +
stand for the discretization of the differential operators in the  $  x $ (horizontal) and  $  y $ (vertical) direction, respectively, and  $  S $
 +
is a diagonal matrix representing multiplication by  $  K _ {0} $.  
 +
The alternating-direction implicit method attempts to solve this linear system by the iteration
  
with some parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054019.png" />. On a uniform mesh, each of the two half-steps in the above iteration scheme requires the solution of a number of tri-diagonal systems arising from one-dimensional difference operators, a task which is relatively inexpensive. On an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054020.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054021.png" /> rectangular mesh, the appropriate choice of a set of parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054022.png" /> (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054023.png" />) in the above iteration allows one to solve the [[Poisson equation|Poisson equation]] (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054025.png" />) with an operation count of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054026.png" />, which is almost optimal. (Optimal methods with an operation count proportional to the number of unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054027.png" /> have later been developed using multi-grid methods.)
+
$$
 +
\left ( H + {
 +
\frac{1}{2}
 +
} S + \rho _ {k} I \right ) \mathbf u _ {k - {1 / 2 }  } = \left ( \rho _ {k} I - V - {
 +
\frac{1}{2}
 +
} S \right ) \mathbf u _ {k - 1 }  + \mathbf f,
 +
$$
 +
 
 +
$$
 +
\left ( V + {
 +
\frac{1}{2}
 +
} S + \rho _ {k} I \right ) \mathbf u _ {k} = \left ( \rho _ {k} I - H - {
 +
\frac{1}{2}
 +
} S \right ) \mathbf u _ {k - {1 / 2 }  } + \mathbf f, k = 1, 2, \dots,
 +
$$
 +
 
 +
with some parameters $  \rho _ {k} > 0 $.  
 +
On a uniform mesh, each of the two half-steps in the above iteration scheme requires the solution of a number of tri-diagonal systems arising from one-dimensional difference operators, a task which is relatively inexpensive. On an $  n $
 +
by $  n $
 +
rectangular mesh, the appropriate choice of a set of parameters $  \rho _ {1} \dots \rho _ {l} $ (with $  l = { \mathop{\rm log} } n $)  
 +
in the above iteration allows one to solve the [[Poisson equation|Poisson equation]] ( $  K _ {1} = K _ {2} \equiv 1 $,
 +
$  K _ {0} = 0 $)  
 +
with an operation count of $  O ( n  ^ {2} { \mathop{\rm log} } n ) $,  
 +
which is almost optimal. (Optimal methods with an operation count proportional to the number of unknowns $  n  ^ {2} $
 +
have later been developed using multi-grid methods.)
  
 
For the parabolic initial-boundary value problem
 
For the parabolic initial-boundary value 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/a/a110/a110540/a11054028.png" /></td> </tr></table>
+
$$
 +
u _ {t} = ( K _ {1} u _ {x} ) _ {x} + ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f  \textrm{ in  }  ( 0,T ) \times \Omega,
 +
$$
  
<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/a/a110/a110540/a11054029.png" /></td> </tr></table>
+
$$
 +
u = g  \textrm{ on  }  ( 0,T ) \times \partial  \Omega, u = u _ {0}  \textrm{ for  }  t = 0,
 +
$$
  
implicit discretization in time requires the solution of an elliptic boundary value problem of the type above in each time-step. The alternating-direction implicit method advances in time by inverting only the one-dimensional difference operators in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054030.png" />- and in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054031.png" />-direction. Each time step is therefore much less expensive. It can be shown to be unconditionally stable. The classical reference is [[#References|[a4]]], Chapts. 7, 8.
+
implicit discretization in time requires the solution of an elliptic boundary value problem of the type above in each time-step. The alternating-direction implicit method advances in time by inverting only the one-dimensional difference operators in $  x $- and in $  y $-direction. Each time step is therefore much less expensive. It can be shown to be unconditionally stable. The classical reference is [[#References|[a4]]], Chapts. 7, 8.
  
 
In the 1980{}s, the apparent potential for parallelism in the alternating-direction implicit method led to research on the appropriate implementation on parallel computers [[#References|[a2]]].
 
In the 1980{}s, the apparent potential for parallelism in the alternating-direction implicit method led to research on the appropriate implementation on parallel computers [[#References|[a2]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,  "On the numerical integration of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a110/a110540/a11054032.png" /> by implicit methods"  ''SIAM J.'' , '''3'''  (1962)  pp. 42–65</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Lennart Johnsson,  Y. Saad,  M.H. Schultz,  "Alternating direction methods on multiprocessors"  ''SIAM J. Sci. Statist. Comput.'' , '''8'''  (1987)  pp. 686–700</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.W. Peaceman,  H.H. Rachford,  "The numerical solution of parabolic and elliptic differential equations"  ''SIAM J.'' , '''3'''  (1955)  pp. 28–41</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.S. Varga,  "Matrix iterative analysis" , Prentice-Hall  (1962)</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,  "On the numerical integration of $u_{xx}+u_{yy}=u_{t}$ by implicit methods"  ''SIAM J.'' , '''3'''  (1962)  pp. 42–65</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Lennart Johnsson,  Y. Saad,  M.H. Schultz,  "Alternating direction methods on multiprocessors"  ''SIAM J. Sci. Statist. Comput.'' , '''8'''  (1987)  pp. 686–700</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.W. Peaceman,  H.H. Rachford,  "The numerical solution of parabolic and elliptic differential equations"  ''SIAM J.'' , '''3'''  (1955)  pp. 28–41</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.S. Varga,  "Matrix iterative analysis" , Prentice-Hall  (1962)</TD></TR></table>

Latest revision as of 01:55, 21 January 2022


A method introduced in 1955 by D.W. Peaceman and H.H. Rachford [a3] and J. Douglas [a1] as a technique for the numerical solution of elliptic and parabolic differential equations (cf. Elliptic partial differential equation; Parabolic partial differential equation). Let $ \Omega \in \mathbf R ^ {2} $ be a bounded region and $ K _ {1} ,K _ {2} , K _ {0} $ continuous functions with $ K _ {1} ( x,y ) > 0 $, $ K _ {2} ( x,y ) > 0 $, $ K _ {0} ( x,y ) \geq 0 $ in $ \Omega $. The discretization of the elliptic boundary value problem (cf. Boundary value problem, elliptic equations)

$$ - ( K _ {1} u _ {x} ) _ {x} - ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f \textrm{ in } \Omega, $$

$$ u = g \textrm{ on } \partial \Omega, $$

in a bounded region $ \Omega \subset \mathbf R ^ {2} $ by finite differences leads to a system of linear equations of the form

$$ ( H + V + S ) \mathbf u = \mathbf f . $$

Here, the matrices $ H $ and $ V $ stand for the discretization of the differential operators in the $ x $ (horizontal) and $ y $ (vertical) direction, respectively, and $ S $ is a diagonal matrix representing multiplication by $ K _ {0} $. The alternating-direction implicit method attempts to solve this linear system by the iteration

$$ \left ( H + { \frac{1}{2} } S + \rho _ {k} I \right ) \mathbf u _ {k - {1 / 2 } } = \left ( \rho _ {k} I - V - { \frac{1}{2} } S \right ) \mathbf u _ {k - 1 } + \mathbf f, $$

$$ \left ( V + { \frac{1}{2} } S + \rho _ {k} I \right ) \mathbf u _ {k} = \left ( \rho _ {k} I - H - { \frac{1}{2} } S \right ) \mathbf u _ {k - {1 / 2 } } + \mathbf f, k = 1, 2, \dots, $$

with some parameters $ \rho _ {k} > 0 $. On a uniform mesh, each of the two half-steps in the above iteration scheme requires the solution of a number of tri-diagonal systems arising from one-dimensional difference operators, a task which is relatively inexpensive. On an $ n $ by $ n $ rectangular mesh, the appropriate choice of a set of parameters $ \rho _ {1} \dots \rho _ {l} $ (with $ l = { \mathop{\rm log} } n $) in the above iteration allows one to solve the Poisson equation ( $ K _ {1} = K _ {2} \equiv 1 $, $ K _ {0} = 0 $) with an operation count of $ O ( n ^ {2} { \mathop{\rm log} } n ) $, which is almost optimal. (Optimal methods with an operation count proportional to the number of unknowns $ n ^ {2} $ have later been developed using multi-grid methods.)

For the parabolic initial-boundary value problem

$$ u _ {t} = ( K _ {1} u _ {x} ) _ {x} + ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f \textrm{ in } ( 0,T ) \times \Omega, $$

$$ u = g \textrm{ on } ( 0,T ) \times \partial \Omega, u = u _ {0} \textrm{ for } t = 0, $$

implicit discretization in time requires the solution of an elliptic boundary value problem of the type above in each time-step. The alternating-direction implicit method advances in time by inverting only the one-dimensional difference operators in $ x $- and in $ y $-direction. Each time step is therefore much less expensive. It can be shown to be unconditionally stable. The classical reference is [a4], Chapts. 7, 8.

In the 1980{}s, the apparent potential for parallelism in the alternating-direction implicit method led to research on the appropriate implementation on parallel computers [a2].

References

[a1] J. Douglas, "On the numerical integration of $u_{xx}+u_{yy}=u_{t}$ by implicit methods" SIAM J. , 3 (1962) pp. 42–65
[a2] S. Lennart Johnsson, Y. Saad, M.H. Schultz, "Alternating direction methods on multiprocessors" SIAM J. Sci. Statist. Comput. , 8 (1987) pp. 686–700
[a3] D.W. Peaceman, H.H. Rachford, "The numerical solution of parabolic and elliptic differential equations" SIAM J. , 3 (1955) pp. 28–41
[a4] R.S. Varga, "Matrix iterative analysis" , Prentice-Hall (1962)
How to Cite This Entry:
Alternating-direction implicit method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Alternating-direction_implicit_method&oldid=14574
This article was adapted from an original article by G. Starke (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article