# Matrix factorization method

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 ). A different form of the stability conditions is also available (see , ). The matrix factorization method is applied also to two-point difference schemes (see ). A variant in which inversion of matrices is replaced by orthogonalization is also used (see ).

How to Cite This Entry:
Matrix factorization method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matrix_factorization_method&oldid=47794
This article was adapted from an original article by T.A. Germogenova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article