Alternating-direction implicit method: Difference between revisions

Revision as of 17:49, 19 June 2018

Revision as of 15:39, 5 July 2018

Line 9:

=== When to use ADI ===

If <math>A \in \mathbb{C}^{m \times m}</math> and <math>B \in \mathbb{C}^{n \times n}</math>, then <math> AX - XB = C</math> can be solved directly in <math> \mathcal{O}(m^3 + n^3)</math> using the Bartels-Stewart method.<ref>{{Cite book|url=https://www.worldcat.org/oclc/824733531|title=Matrix computations|last=Golub, G.|publisher=Johns Hopkins University|others=Van Loan, C|year=1989|isbn=1421407949|edition=Fourth edition|___location=Baltimore|pages=|oclc=824733531}}</ref> It is therefore only beneficial to use ADI when matrix-vector multiplication and linear solves involving <math>A</math> and <math>B</math> can be applied cheaply.

The equation <math> AX-XB=C</math> has a unique solution if and only if <math> \sigma(A) \cap \sigma(B) = \emptyset</math>, where <math> \sigma(M) </math> is the [[Spectrum of a matrix|spectrum]] of <math>M</math>.<ref name=":1" /> However, the ADI method performs especially well when <math>\sigma(A)</math> and <math>\sigma(B)</math> are well-separated, and <math>A</math> and <math>B</math> are [[Normal matrix|normal matrices]]. These assumptions are met, for example, by the Lyapunov equation <math>AX + XA^* = C</math> when <math>A</math> is [[Positive-definite matrix|positive definite]]. Under these assumptions, near-optimal shift parameters are known for several choices of <math>A</math> and <math>B</math>.<ref name=":4" /><ref name=":5" /> Additionally, a priori error bounds can be computed, thereby eliminating the need to monitor the residual error in implementation.

Line 74:

and <math>\delta_p^2</math> is the central second difference operator for the ''p''-th coordinate

: <math>\delta_p^2 u_{ij}=u_{ij+e_p}-2u_{ij}+u_{ij-e_p}</math>

with <math>e_p=10</math> or <math>01</math> for <math>p=x</math> or <math>y</math> respectively (and <math>ij</math> a shorthand for lattice points <math>(i,j)</math>).

After performing a [[Von Neumann stability analysis|stability analysis]], it can be shown that this method will be stable for any <math>\Delta t</math>.