« previous | Thursday, March 27, 2014 | next »
Quiz on Tuesday over Chapter 5 (diff eqs)
Linear Algebra
Matrices
Component-wise addition, subtraction, and scalar multiplication
Gaussian-Jordan Elimination
(Sections 6.1 and 6.2
Row echelon form:
Find solution to
- If
, find another row
such that
and switch
- Divide row
by 
- Add row 1 scaled by
to remaining rows 
- Recur on submatrices to get upper triangular matrirx
- Jordan steps perform similar operations to upper half of matrix (starting from bottom) to get identity matrix.
Gaussian and Jordan's steps each take
operations. Hence solving system of equations is
In Matlab, x = A \ b
is a fast matrix equation solver. Don't use x = A^(-1) * b
Instability
Example
Let
Performing gaussian elimination gives solutions
for very small
, we get
, which is actually a pretty good estimation, but substituting it back into
, whereas the exact solution for
is
.
In reality, we are not solving for
, we are actually solving for
. We really care how close
is to
given
and
are small values.
Matlab Exercise
Generate random matrix
and compute
Solve for
.
This usually works only 1 out of 10 times, so Gaussian elimination is unstable
Gaussian Elimination with Partial Pivoting
Added stability
At step
, we are operating on row
with current diagonal entry
.
If
, find
such that
and swap rows
and
.
Now whenever we multiply remaining rows
by
, we have
Example
Applying this to our example above gives
The solutions match with exact solutions:
and
Gaussian Elimination with Full Pivoting
When looking at
,
- find
such that
(largest entry in entire matrix)
- Interchange rows
and
and columns
and 
- Change
to
(bookkeeping headache)
This is better, but still not perfect: there are still matrices that might cause it to fail.
(this method is what Matlab uses)
Eigenvalues and Eigenvectors
is an eigenvalue of
if there exists
such that
.
This implies
, which further implies
.
Computing this determinant gives a polynomial of
of degree
(for
\times
matrix) that has roots
(i.e.
).
Example
Gives equation
and solutions
As
, we get
. Therefore Gaussian elimination will be stable.