MA332 lecture notes, Fall 1998
Week 8 Tuesday

Homework Notes

Homework 5 (predator-prey and pivoting)
----------

1) Matrix question was supposed to be a gimme, since it is the
   first line of the matrix documentation.

2) Pivoting question: based on the assignment, we can't tell
   whether gausselim is doing partial pivoting or no pivoting!

   Sometimes the right answer is "we don't know!"

   Sometimes the best answer is to do an additional experiment to
   find out.  Only one person in the whole class did.

   Don't guess!!!

3) When you can't read a graph, print some values.  In this
   case, you want to print the end values.  There is an important
   story there -- the prey are making a comeback!!!

4) Always check to make sure you answer is accurate, or at least
   has converged!  Increase n until you have a couple of digits,
   anyway.

5) Animals can't tell time.

Homework 6 hints
----------------

There is no particularly elegant way to do Jacobi and G-S
in Maple, so you might want to do it by hand.

Well, there is an elegant way, but I don't expect you to
do it.  Hint: it involves the map command.

You can mutiply a matrix by a vector:

evalm(T &* x + c);

Also, it is handy to be able to add a new column to a matrix

a:=augment(a,r);

If you want to check the type of an expression, you can try

type(b,vector);
	true
type(A,vector);
	false

Interestingly:

type(A,matrix);
	true
type(A,array);
	true

Keeping track of types in Maple is a pain, but necessary.


New business!
------------

Chapter 9, finding eigenvalues and eigenvectors

The book explains things in n dimensions.  Preparing this lecture,
I found myself translating into 2-D.

This is an example of an important reading technique, which I call
concretization: for every general statement, construct a specific
example.

Often you find that gratuitous math-fu is really saying something
simple.

Think of A as an operator y=Ax.

In R2, two special vectors have the property that Av = lv,

where the vi are the eigenvectors and the li are the eigenvalues.

Weirdness aside, assume that A has linearly independent vi
and largest eigenvalue l1 such that |l1| > |l2|

Since the vi are linearly independent, an vector in R2 can be
written

	x = b1 v1 + b2 v2

So,

	Ax = b1 l1 v2 + b2 l2 v2

Repeated multiplication by A yields powers of l1 and l2

	In the limit, A^k x = l1^k b1 v1

Graphically what we are doing is projecting x onto v1 and v2,
and stretching the projections (unequally) and then adding them
up.

Result: successive multiplications bring x closer to v1

As x->v1,  ||xnew|| / ||xold|| -> l1

For any norm.

Small problem: elements of x probably get big.

Solution: scale as you go

	  xnew = A xold

	  mu = ||xnew|| / ||xold||     (mu approximates l1)

	  xnew = xnew / ||xnew||

Cheap and dirty version uses the infinity norm
(divide through by the largest value).

Nice example of gratuitous math-fu on the bottom of page 373.


Aitken's del2 method
--------------------

Convergence of power method is linear, with ratio of successive
errors = |l2| / |l1|

lim  |mnew - l1| / |mold - l1| = |l2| / |l1| < 1

How do we know it's less than 1?

Ratio of consecutive errors known to be constant:

Given three consecutive estimates, m0 m1 m2, of l...

      m1 - l      m2 - l
      ------  =   ------
      m0 - l      m1 - l

Cross-multiply and solve for l:

               (m1 - m0)^2 
      l = m0 - -----------
               m2 - 2m1 + m0

See pages 50-51 for more details.

Don't confuse Aitken with Richardson.  In Richardson, we _know_ the
ratio of successive estimates, and we only need two consecutive...

      p = p0 + e
      p = p1 + e/k

Solve for p (and e), given p0 p1 AND k


How do we find other eigenvalues (vectors)?

Inverse power method
--------------------

If A has linearly independent vi and li

For q != li, then (A - qI)-1 has eigenvalues

1/(l1-q)  1/(l2-q) ... 1/(ln-q)

Applying power method to (A - qI)-1,

	 xnew = (A - qI)-1 xold

Of course, we don't want to invert (A - qI)-1, so instead
we repeatedly solve

	 (A - qI) xnew = xold

By factoring (A - qI)

Convergence is fast if q is near li

How do we choose initial value of q

1) Gerschgorin circle Theorem

   if d is a diagonal element and r is the sum of |the off-diagonals|

   then there is an eigenvalue in the circle with center d and radius r

2) 1 iteration of power method