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

References

[1]	A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[2]	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
[3]	A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
[4]	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
[5]	E.L. Wachspress, "Iterative solution of elliptic systems and applications to the neutron diffusion equations of reactor physics" , Prentice-Hall (1966)

References

[a1]	I. [I. Babushka] Babuška, M. Práger, E. Vitásek, "Numerical processes in differential equations" , Interscience (1966)