Graphics Programs Reference
In-Depth Information
in place. The eliminationwould thenproceedas follows (for the sake of brevity, we
skip repeating the details of choosing the pivot equation):
⎡
⎣
⎤
⎦ ←
−
2
26 16
A
b
=
−
2
4 3
0
−
184
−
1
⎡
⎣
⎤
⎦
0 29 16
A
b
=
−
2 4
3
0
0 65
/
2
−
1
←
⎡
⎣
⎤
⎦
0049
/
6
49
/
3
A
b
=
−
2 4
3
0
0 65
/
2
−
1
But now the back substitutionphase is a little more involved,since the orderinwhich
the equations must be solved has becomescrambled. In hand computationsthis is
not aproblem, because wecan determine the orderbyinspection. Unfortunately,
“by inspection” does not workonacomputer. To overcomethis difficulty, wehave
to maintain an integer array
p
that keepstrack of the rowpermutations during the
eliminationphase. The contents of
p
indicate the orderinwhich the pivot rows were
chosen. In thisexample, we would have at the end of Gauss elimination
⎡
⎣
⎤
⎦
2
3
1
p
=
showing that row2was the pivot rowinthe first eliminationpass, followedbyrow3in
the second pass. The equations are solvedbyback substitutioninthe reverse order:
equation1is solvedfirst for
x
3
, then equation3is solved for
x
2
, and finally equation
2yields
x
1
.
By dispensing with swapping of equations, the schemeoutlinedabove would
probablyresult in a faster (and morecomplex) algorithm than
gaussPiv
, but the
number of equations would havetobequite large before the difference becomes
noticeable.
PROBLEM SET 2.2
=
1. Solve the equations
Ax
b
by utilizing Doolittle's decomposition, where
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
3
−
33
9
A
=
−
351
315
b
=
−
7
12
Search WWH ::
Custom Search