Page 96 - Applied Numerical Methods Using MATLAB

SOLVING A SYSTEM OF LINEAR EQUATIONS 85
(cf) The number of floating-point multiplications required in this routine ‘gauss()’is

NA NA−1

{(NA − k + 1)(NA + NB − k) + NA − k + 1}+ (NA − k)NB
k=1 k=1
NA NA NA

= k(k + NB − 1) − NB k + NA · NB
k=1 k=1 k=1
1 1
2
= (NA + 1)NA(2NA + 1) − NA(NA + 1) + NA NB
6 2
1 2
= NA(NA + 1)(NA − 1) + NA NB
3
1 3
≈ NA for NA NB (2.2.18)
3
where NA is the size of the matrix A,and NB is the column dimension of the RHS
matrix B.

Here are several things to note.

Remark 2.2. Partial Pivoting and Undetermined/Inconsistent Case

1. In Gauss or Gauss–Jordan elimination, some row switching is performed
to avoid the zero division. Even without that purpose, it may be helpful
for reducing the round-off error to fix

Max{|a mk |,k ≤ m ≤ M} (2.2.19)

as the pivot element in the kth iteration through some row switching, which
is called ‘partial pivoting.’ Actually, it might be better off to fix

|a mk |
Max ,k ≤ m ≤ M (2.2.20)
Max{|a mn |,k ≤ n ≤ M}
as the pivot element in the kth iteration, which is called ‘scaled partial
pivoting’ or to do column switching as well as row switching for choosing
the best (largest) pivot element, which is called ‘full pivoting.’ Note that
if the columns are switched, the order of the unknown variables should be
interchanged accordingly.
2. What if some diagonal element a kk and all the elements below it in the
same column are zero and, besides, all the elements in the row including
a kk are also zero except the RHS element? It implies that some or all
rows of the coefficient matrix A are dependent on others, corresponding
to the case of redundancy (infinitely many solutions) or inconsistency (no