Graphics Programs Reference
In-Depth Information
⎡
⎣
⎤
⎦
···
···
···
A
11
A
12
A
13
A
1
k
A
1
j
A
1
n
b
1
0
A
22
A
23
···
A
2
k
···
A
2
j
···
A
2
n
b
2
00
A
33
···
A
3
k
···
A
3
j
···
A
3
n
b
3
.
.
.
.
.
.
.
000
···
A
kk
···
A
kj
···
A
kn
b
k
←
pivot row
.
.
.
.
.
.
.
←
rowbeing
transformed
000
···
A
ik
···
A
i j
···
A
in
b
i
.
.
.
.
.
.
.
000
···
A
nk
···
A
nj
···
A
nn
b
n
Let the
i
th rowbe a typical rowbelow the pivot equation that istobetransformed,
meaning that the element
A
ik
istobeeliminated. Wecan achievethis by multiplying
the pivot rowby
A
kk
and subtracting itfrom the
i
th row. The corresponding
changes in the
i
th roware
λ
=
A
ik
/
←
A
i j
−
λ
=
,
+
,...,
A
i j
A
kj
,
j
k
k
1
n
(2.8a)
b
i
←
b
i
−
λ
b
k
(2.8b)
To t ransformthe entire coefficientmatrix to upper triangular form,
k
and
i
inEqs. (2.8)
must have the ranges
k
n
(chooses the row to betransformed). The algorithm for the eliminationphase now
almost writes itself:
=
1
,
2
,...,
n
−
1 (chooses the pivot row),
i
=
k
+
1
,
k
+
2
...,
fork=1:n-1
for i= k+1:n
if A(i,k) ˜= 0
lambda = A(i,k)/A(k,k);
A(i,k+1:n) = A(i,k+1:n) - lambda*A(k,k+1:n);
b(i)= b(i) - lambda*b(k);
end
end
end
In order to avoid unnecessary operations, the above algorithmdeparts slightly
fromEqs. (2.8) in the following ways:
If
A
ik
happenstobezero, the transformation of row
i
isskipped.
+
The index
j
in Eq. (2.8a)starts with
k
1rather than
k
. Therefore,
A
ik
is not re-
placedbyzero, but retains its original value.As the solutionphase neveraccesses
Search WWH ::
Custom Search