Perpframes, Aligners and Hangers
Linear Systems, Pseudo-Inverse
Matrix Norm, Rank One
Round off error,
"Shoot!", says Bill.
"We've got four equations and only three unknowns.
Everyone knows you only need three equations to solve for three unknowns.
Let's just delete the last equation."
Ted agreed with Bill and so they decided to solve the system:
"Hold on", says Ted. "We can only solve this equation if the coefficient matrix is invertible."
After a lot of work Ted computes
Seeing that the determinant is non-zero, Bill and Ted feel confident in computing
Bill and Ted were pleased with their results, but they realized that the numbers they recorded on the right hand side of their equations, , were only accurate to the nearest tenth.
They decided to round their numbers and try the calculation again:
"Noooooooooo!", screamed Bill, "how could this happen?"
"We've changed our matrix equation only a little but now we get a wildly different answer."
Explain to Bill and Ted what went wrong.Start by finding an SVD for the coefficient matrix .
An SVD for A is .
Since A has three non-zero stretch factors, the rank of A is three and A is invertible.
But that smallest singular value is so small that A is nearly a rank two matrix.
This spells trouble.
Using the SVD method you can compute
Now let y be the original right hand side and let y' be the rounded right hand side.
You need to explain why is so big.
Now the matrix stretches vectors parallel to by a factor of 5000.
So if is parallel to , then .
This says that changes in the right hand side can get magnified up to 5000 times when you solve for x.
Explain to Bill and Ted how to fix their problem.First, explain to Bill that only mathematicians are silly enough to think that three equations are good enough to solve for three unknowns.
In the real world you want all the data you can get.
Here's the original system with the fourth equation returned.
Now a reduced SVD for the coefficient matrix is
This matrix is a fully robust rank 3 matrix.
Since the singular values of A are each roughly 100, the singular values of the pseudo-inverse, , will each be roughly .
This tells you that if
is the original right hand side
So the theory tells you that rounding y to y' won't affect the solution to the system.
That's the theory, now here are the facts:
Value for a,b,c using the original right hand side.
Value for a,b,c using the rounded right hand side.
The theory holds up!
Then the fundamental equations tell you .
is an orthonormal basis, then
Comment: You can use this theorem to give an upper bound on the difference between the solution to and
and then solved for .
Give an upper bound on .
2. If A has singular values , then the condition number of A is .
Compute the condition number for
A matrix with a large condition number is called ill-conditioned
and often displays extreme sensitivity to rounded like Ted and Bill