LU Decomposition
Part 3: Solving Equations
In practice, LU decompositions are often used to solve a sequence of matrix equations, all with the same coefficient matrix:
Ax = b1, Ax = b2, ... , Ax = bn.
For this situation, using the LU decomposition for A is generally more efficient than solving directly by row reduction. In this part, we explore the reason why.
The efficiency of a numerical algorithm is generally measured by counting the number of floating point operations, or flops, needed to complete the algorithm. [Any single arithmetic opertion (addition, subtraction, multiplication, or division) on two real floating point numbers is a flop.]
- Using pencil and paper, calculate the reduced row echelon form of the augmented matrix [A|b], for the matrix A and the vector b defined in your worksheet. Count the number of flops required to solve the equation Ax = b. How many flops would be required for a general system of 3 equations in 3 unknowns?
- Based on your row-reduction, write down an LU decomposition for the matrix A.
- Now we will solve the matrix equation using the LU decomposition for A. The trick is to think of the equation Ax = b as L(Ux) = b.
- Solve the equation Ly = b. Count the number of flops required.
- Solve the equation Ux = y. Count the number of flops required.
How does the total number of flops needed to find x compare with the number needed when you solved as in Step 1?
Of course, the increased efficiency you achieved by using the LU decomposition depended on knowing L and U, which required additional flops. But if you needed to solve other matrix equations with the same coefficient matrix, using the LU decomposition would be more efficient because you need to compute L and U only once!
- Use your LU decomposition for A to solve the equation Ax = c, where c is the vector defined in your worksheet.
modules at math.duke.edu
