Use of LU decomposition - Tutorial 2 ~ UTeM BMFR - Technical and Vocational Education

Use of LU decomposition - Tutorial 2

Posted by BMFRGuru at 7:58 PM

Procedure

Suppose we have to solve a linear system Ax = b, and that we can express the coefficient matrix A in the form of the socalled LU decomposition A = LU.

Then we may solve the linear system by the following procedure:

Stage l: Write Ax = LUx = b.

Stage 2: Set y = Ux, so that Ax = Ly = b. Use forward substitution on Ly = b to find y₁, y₂, . . , y_n in that order, i.e., suppose the augmented matrix for the system Ly = b is:

Then forward substitution yields y₁ = b₁/l₁₁, and, subsequently,

Note that the value of y_i depends on the values y₁, y₂, . . , y_i-1, which have already been calculated.

Stage 3: Finally, use back-substitution on Ux = y to find x_n, . . . , x₁x in that order.

Later on we shall outline a general method for finding LU decompositions of square matrices. The following example shows this method in action, involving the matrix A = L₁U₁ above. If we wish to solve Ax = b for a number of different bs, then this method is more efficient than Gauss elimination. Once we have found an LU decomposition of A, we need only do forward and backward substitutions to solve the system for any b.