Graphics Reference
In-Depth Information
2
4
3
5
A
11
A
12
A
13
A
14
A
21
A
22
A
23
A
24
A ¼
A
31
A
32
A
33
A
34
A
41
A
42
A
43
A
44
2
4
3
5
2
4
3
5
(B.9)
L
11
000
L
21
U
11
U
12
U
13
U
14
0
U
22
U
23
U
24
00
U
33
U
34
000
U
44
L
22
00
¼ LU ¼
L
31
L
32
L
33
0
L
41
L
42
L
43
L
44
The decomposition of a matrix
A
into the
L
and
U
matrices can be used to easily solve a system of
linear equations. For example, consider the case of four unknowns (
x
) and four equations shown in
Equation B.10
.
Use of the decomposition permits the system of equations to be solved by forming
A
11
x
1
þ A
12
x
2
þ A
13
x
3
þ A
14
x
4
¼ b
1
A
21
x
1
þ A
22
x
2
þ A
23
x
3
þ A
24
x
4
¼ b
2
A
31
x
1
þ A
32
x
2
þ A
33
x
3
þ A
34
x
4
¼ b
3
A
41
x
1
þ A
42
x
2
þ A
43
x
3
þ A
44
x
4
¼ b
4
A
11
(B.10)
2
3
2
3
2
3
A
12
A
13
A
14
x
1
x
2
x
3
x
4
b
1
b
2
b
3
b
4
4
5
4
5
4
5
A
21
A
22
A
23
A
24
¼
A
31
A
32
A
33
A
34
A
41
A
42
A
43
A
44
Ax ¼ b
Ax ¼ b
ðLUÞx ¼ b
LðUxÞ¼b
Ux ¼ y
Ly ¼ b
(B.11)
This solves the original set of equations. The advantage of doing it this way is that both of the last
two equations resulting from the decomposition involve triangular matrices and therefore can be
solved trivially with simple substitution methods. For example,
Equation B.12
shows the solution
to
Ly ¼ b.
Notice that by solving the equations in a top to bottom fashion, the results from the equa-
tions of previous rows are used so that there is only one unknown in any equation being considered.
Once the solution for
y
has been determined, it can be used to solve for
x
in
Ux ¼ y
using a
similar approach. Once the
LU
decomposition of
A
is formed, it can be used repeatedly to solve sets
of linear equations that differ only in right-hand sides, such as those for computing the inverse of a
matrix. This is one of the advantages of
LU
decomposition over methods such as Gauss-Jordan
elimination.
Search WWH ::
Custom Search