View source for Alternating-direction implicit method

<!--
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.
-->

{{TEX|auto}}
{{TEX|done}}

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]])

$$ 
- ( 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|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 [[#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]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,   "On the numerical integration of $u_{xx}+u_{yy}=u_{y}$ 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>