Graphics Programs Reference
In-Depth Information
which can be solved for
y
by forward substitution. Then
Ux
=
y
will yield
x
by the back substitutionprocess.
The advantageofLU decomposition over the Gauss eliminationmethodisthat
once
A
is decomposed, wecan solve
Ax
b
foras many constant vectors
b
as we
please. The cost of each additional solutionis relatively small, since the forward and
back substitution operations are much less timeconsuming than the decomposition
process.
=
Doolittle's Decomposition Method
Decomposition phase
Doolittle's decompositionis closelyrelated to Gauss elim-
ination. In order to illustrate the relationship,considera3
×
3matrix
A
and assume
that thereexist triangular matrices
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
1
00
U
11
U
12
U
13
0
U
22
U
23
00
U
33
L
=
U
=
L
21
1
0
L
31
L
32
1
such that
A
=
LU
.After completing the multiplication on the right hand side, we get
⎡
⎣
⎤
⎦
U
11
U
12
U
13
A
=
(2.12)
U
11
L
21
U
12
L
21
+
U
22
U
13
L
21
+
U
23
U
11
L
31
U
12
L
31
+
U
22
L
32
U
13
L
31
+
U
23
L
32
+
U
33
Let us now apply Gauss elimination to Eq. (2.12). The first pass of the elimina-
tionprocedureconsists of choosing the first rowas the pivot row and applying the
elementary operations
row2
←
row2
−
L
21
×
row1(eliminates
A
21
)
row3
←
row3
−
L
31
×
row1(eliminates
A
31
)
The result is
⎡
⎣
⎤
⎦
U
11
U
12
U
13
0
U
22
U
23
0
U
22
L
32
U
23
L
32
A
=
+
U
33
In the next pass wetake the second rowas the pivot row, and utilize the operation
row3
←
row3
−
L
32
×
row2(eliminates
A
32
)
Search WWH ::
Custom Search