Framåtsubstitution

Framåtsubstitution, or forward substitution, is a numerical method for solving systems of linear equations of the form Lx = b, where L is a lower triangular matrix. It is commonly used as part of LU decomposition, where a matrix A is factored into A = LU and the original system is solved by first solving Ly = b and then Ux = y.

The method proceeds from the top row to the bottom. For each i from 1 to n, the value x_i is computed using the previously determined components x_1, ..., x_{i-1} according to the recurrence x_i = (b_i − sum_{j=1}^{i−1} L_{i j} x_j) / L_{i i}. If L has unit diagonal (L_{i i} = 1 for all i), this simplifies to x_i = b_i − sum_{j=1}^{i−1} L_{i j} x_j.

Requirements and efficiency: L must be square, lower triangular, and have nonzero diagonal entries to avoid division by zero. The operation count is O(n^2) and memory usage is O(n). Forward substitution is stable for well-conditioned problems and is the straightforward counterpart to backward substitution for upper triangular systems.

Applications: It is widely used after computing an LU decomposition of a matrix A, solving Ly = b followed by Ux = y to obtain x. Beyond LU, forward substitution is applicable to any lower triangular system encountered in numerical linear algebra, finite element methods, and related computational fields.

Relationship to other methods: Forward substitution is the counterpart to backward substitution, which solves Ux = b for an upper triangular matrix U. Together, they provide a practical workflow for solving linear systems via triangular factorization.