Graphics Programs Reference
In-Depth Information
Diagonal Dominance
An n
n matrix A issaid to be diagonally dominant ifeach diagonal element islarger
than the sumof the other elements in the same row (we aretalking here about absolute
values). Thus diagonal dominance requires that
×
n
A i j ( i
|
A ii | >
=
1
,
2
,...,
n )
(2.30)
j
=
1
j
=
i
For example, the matrix
2
4
1
1
13
4
21
is not diagonallydominant, but if we rearrange the rows in the following manner
4
21
2
4
1
1
13
thenwehave diagonal dominance.
It canbe shown that if the coefficientmatrix A of the equations Ax
b is diagonally
dominant, then the solutiondoes not benefitfrompivoting; that is, the equations are
already arrangedinthe optimalorder. It followsthat the strategy of pivoting shouldbe
to reorder the equationssothat the coefficientmatrix is as close todiagonaldominance
as possible. This is the principle behind scaledrow pivoting, discussednext.
=
Gauss Elimination with Scaled Row Pivoting
Consider the solution of Ax
b by Gauss eliminationwith row pivoting. Recall that
pivoting aims at improving diagonal dominance of the coefficient matrix, i.e., making
the pivot element aslarge as possible in comparison to other elements in the pivot
row. The comparisonis madeeasierif we establish an array s , with the elements
=
A i j ,
s i
=
max
j
i
=
1
,
2
,...,
n
(2.31)
Thus s i ,called the scale factor of row i ,contains the absolute value of the largest
element in the i th row of A . The vector s can beobtainedwith the following algorithm:
fori=1:n
s(i) = max (abs(A(i,1:n)))
end
Search WWH ::




Custom Search