View source for Matrix factorization method

<!--
m0628101.png
$#A+1 = 19 n = 0
$#C+1 = 19 : ~/encyclopedia/old_files/data/M062/M.0602810 Matrix factorization 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}}

''matrix forward-backward substitution method''

A method for solving finite-difference systems that approximate boundary value problems for systems of ordinary differential equations in one-dimensional problems, and for elliptic equations in two-dimensional problems.

The solution of the three-point difference scheme

$$ 
A _ {i} Y _ {i-} 1 - C _ {i} Y _ {i} + B _ {i} Y _ {i+} 1  = \ 
- F _ {i} ,\ \ 
i = 1 \dots N- 1 ,
$$

where  $  Y _ {i} = \{ y _ {1,i} \dots y _ {n,i} \} $
is an unknown grid vector,  $  F _ {i} $
is the right-hand side vector and  $  A _ {i} , B _ {i} , C _ {i} $
are given square matrices, under the boundary conditions

$$ 
- C _ {0} Y _ {0} + B _ {0} Y _ {1}  = \ 
- F _ {0} ,\ \ 
A _ {N} Y _ {N-} 1 - C _ {N} Y _ {N}  =  - F _ {N} ,
$$

is sought for, as in the scalar case, in the form

$$ \tag{* }
Y _ {i}  =  R _ {i+} 1 Y _ {i+} 1 + Q _ {i+} 1 ,\ \ 
i = 0 \dots N- 1.
$$

The coefficients (the matrix  $  R _ {i+} 1 $
and the vector  $  Q _ {i+} 1 $) 
are determined from the recurrence relations ( "forward substitution" )

$$ 
R _ {i+} 1  =  ( C _ {i} - A _ {i} R _ {i} )  ^ {-} 1 B _ {i} ,
$$

$$ 
Q _ {i+} 1  =  ( C _ {i} - A _ {i} R _ {i} )  ^ {-} 1
( A _ {i} Q _ {i} + F _ {i} ),\  i = 1 \dots N- 1,
$$

while  $  R _ {1} $
and  $  Q _ {1} $
are given by the left boundary condition:

$$ 
R _ {1}  =  C _ {0}  ^ {-} 1 B _ {0} ,\ \ 
Q _ {1}  =  C _ {0}  ^ {-} 1 F _ {0} .
$$

The  $  Y _ {i} $
are calculated by formula (*) ( "backward substitution" ), and

$$ 
Y _ {N}  =  ( C _ {N} - A _ {N} R _ {N} )  ^ {-} 1 ( A _ {N} Q _ {N} + F _ {N} ).
$$

There is stability of this method to rounding errors under the conditions

$$ 
\| C _ {0}  ^ {-} 1 B _ {0} \|  <  1,\ \ 
\| C _ {N}  ^ {-} 1 A _ {N} \|  <  1,
$$

$$ 
\| C _ {i}  ^ {-} 1 B _ {i} \| + \| C _ {i}  ^ {-} 1 A _ {i} \|  <  1 ,\  i = 1 \dots N- 1,
$$

which implies that  $  \| R _ {i} \| < 1 $, 
$  i = 1 \dots N $(
see [[#References|[1]]]). A different form of the stability conditions is also available (see [[#References|[2]]], [[#References|[3]]]). The matrix factorization method is applied also to two-point difference schemes (see [[#References|[3]]]). A variant in which inversion of matrices is replaced by orthogonalization is also used (see [[#References|[4]]]).

====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">  V.V. Ogneva,   "The  "sweep"  method for the solution of difference equations"  ''USSR Comp. Math. Math. Phys.'' , '''7''' :  4  (1967)  pp. 113–126  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''7''' :  4  (1967)  pp. 803–812</TD></TR><TR><TD valign="top">[3]</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><TR><TD valign="top">[4]</TD> <TD valign="top">  S.K. Godunov,   "A method of orthogonal successive substitution for the solution of systems of difference equations"  ''USSR Comp. Math. Math. Phys.'' , '''2''' :  6  (1962)  pp. 1151–1165  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''2''' :  6  (1962)  pp. 972–982</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.L. Wachspress,   "Iterative solution of elliptic systems and applications to the neutron diffusion equations of reactor physics" , Prentice-Hall  (1966)</TD></TR></table>

====Comments====

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. [I. Babushka] Babuška,   M. Práger,   E. Vitásek,   "Numerical processes in differential equations" , Interscience  (1966)</TD></TR></table>