MA332 lecture notes, Fall 1998
Week 6, Tuesday

Reading: F&B Chapter 6.1 -- 6.4


Systems of linear equations.

Matrix notation.

Operations you can perform on the augmented matrix without changing
the solution:

1) Multiply a row by a scalar

2) Add any multiple of one row to another

3) Swap rows 

These operations do not change the solution if we are using real
arithmetic.  In FP arithmetic, they do, especially 3

Book contains good explanation of where this augmented matrix
idea comes from.

Number of mult/div is n^3/3 + n^2 - n/3
Number of add/sub is n^3/3 + n^2/2 - 5n/6

where n is the number of equations.

FP addition typically one cycle, mult 5-10, div 10 (very approximate).

We seldom measure performance this accurately, rather, just report
that the run time is proportional to n^3, which is kinda bad news.

Basic GE:

1) Find the pivot

2) Calculate the multiplier m

3) perform E2 - mE1 -> E2

In-class exercise:

   .003x + 59.14y = 59.17
   5.291x - 6.13y = 46.78

   Correct answer: x=10, y=1

Use 4-digit rounding arithmetic.


Partial pivoting (maximal column pivoting)

Step 1) find the largest value in the current column and swap
        it into the pivot position


Repeat exercise.

Scaled partial pivoting

1) Each row gets a scale factor associated with it at the beginning,
   that stick with it all the way through.  It's the largest value
   in the row.

2) Every time we go looking for a pivot, we compare values RELATIVE
   to the scale factor for the rows.

Scaled partial pivoting usual as far as anyone goes in practice.

Online documentation of matrices and arrays is better than the book.


Review of linear algebra
------------------------

Nonsingular (invertible) matrixes:

1) Ax=0 true only for x=0
2) Ax=b has unique solution for any b
3) A is nonsingular, A inverse exists
4) det A != 0

What does it mean if two rows are equal?

How do we know if a FP number is equal or just approximately equal?

If GE fails, can we conclude that the matrix is singular?

   Maybe not, but it's at least ill-conditioned.

A-1b is the solution to Ax=b

How do we find A-1?  Augment the matrix with the identity matrix
    (see book for nice derivation)

Why don't we, usually?  More expensive than GE.

When might we?  If we had to solve the same matrix for many right-hand
sides.  Actually, in this case, factorization makes for sense.

Factorization
-------------

If A=LU, then Ax=b -> LUx=b

if y = Ux, then solve Ly=b    O(n^2)

           then solve Ux=b    O(n^2)

Of course, it still takes O(n^3) to do the factorization, and it's
not possible for all matrices, even some invertible ones.