1 Linear Systems
Systems of equations that are linear in the unknowns are said to be linear
systems
For instance
gives 2 equations and 2 unknowns.
More generally we have
This can be written in matrix re presentation as
Ax = b 
(1)
where
and
The solution is given by multiplying boths sides by A-1.
A-1Ax = Ix = x = A-1b 
(4)
This is the same answer you would get if you isolated one variable at a time and
then
substituted back into the other equation. We will be concerned with solving
linear equations
with uknowns x under the conditions
• When M < N or M = N and the equations are degenerate or
singular.
Degeneracy happens when the equations are not linearly independent. The
determinant
of a square matrix is zero if and only if it’s singular. The number of linearly
independent equations is called the rank of A. If the rank is less than the
size, the
matrix is said to be not of full rank. Because of this, there is a set of
nonzero vectors
that produce zero output. These vectors can be added to any solution, and it’s
still a
solution. Therefore the solution is not unique.
The space spanned by the set of vectors that produce zero is called the nullity
of A.
We would like to know a single solution and the characterize the nullity of A.
• When M = N and A is of full rank. We would like to find the unique solution x
in a
way that is efficient and accurate. In some cases the matrix A can be nearly
singular.
In such cases it can be impossible to compute the solution (even though it
exists)
because of numerical errors .
• When M > N, the system is over determined. In this case we would like to find
the best
compromise solution. Often, the best solution is defined in the sense of least
squares.
That is, minimize:
(Ax − b)2(5)
There are many ways to do this. One way is to convert the equations into another
linear N × N problem that solves this least squares. This is
ATAx = ATb 
(6)
These are called the normal equations of the initial problem. The solution is
x = (ATA)-1ATb
(7)
The matrix
x = (ATA)-1AT is called the psuedo inverse. Notice, sometimes (ATA)-1 can
be solved with a method for well -posed linear systems, but can be singular or
nearly
so. Therefore, the normal equations for overconstrained systems should be used
with
caution.
• In some cases we would like to solve
for many different 
2 Mechanisms for Solving Linear Systems
For well-posed systems (i.e. square matrix of full rank) there are several
mechanisms for
solving. Note that explicitly computing the inverse A-1, is generally not
recommended.
Gaussian Elimination: Somewhat robust. Can detect singularities. Not very
efficient.
LU Decomposition: Somewhat robust. Efficient. Can solve
for many b’s. Gives the
determinant directly.
Iterative techniques: Can be slow. Are very accurate. Often use to clean up the
accumulated
round-off error associated with these other methods.
3 Singular Value Decomposition
A very powerful tool in numerical linear algrebra is singular value
decomposition.
Where the matrices U and V are orthogonal in their columns (V in rows as well).
The singular
values and their associated columns are defined to within a scalar factor, and
therefore
we usually as sume the column vectors of U and V are normalized.
Such a decompostion is always possible, regardless of the matrix, and there are
stable
numerical algorithms given in “Numerical Recipes”. The decomposition is unique,
up to a
swapping of rows in all matrices.
Why would we want to do a SVD?
3.1 SVD of Square Matrix
If A is square (say N × N) then U V and W are all the same size.
Because U and V are orthogonal, inverses are the transpose.
Because W is diagonal, inverse is reciprical of diagonal elements.
So the inverse of A is
This won’t work if one of the 
is zero, or even if one is very small (so
small that it’s
value is dominated by roundoff error). If more than one
is zero, then the
number of zero
gives the nullity of A.
SVD gives a mechanism for finding the inverse, and some clear indications of
what’s
wrong when it fails. We can see this as follows. Any x that is composed of
columns of V
with corresponding 
that are zero gives Ax = 0. We
know this because if multiply A by
column of V , call it 
, we get
where is zero when 
= 0. Thus the null space is spanned by the vectors
(columns of VT )
associated with zero 
is the null space. Any point in this space when
multiplied by A
returns 0. The space spanned by the vectors associate with the nonzero elements
of W is
called the range of A. The dimensionality of that space is the rank. The rank
plus the nullity
is equal to the size of A, which is N. Therefore, the nullity of A is the
dimension of its null
space.
Solving Singular Problems
If A is singular, one might want to single out a solution that is somehow better
than the
others. In this case want might want the smallest solution, i.e. the smallest
length x2.
One way to do that is to use the diagonals, but replace 1/
by zero where
is
zero.
I.e. use zero whereever 1/ b lows up .
The solution is then
This gives the shortest solution to the problem.
Proof
Consider a solution that is modified by a vector x' could it be shorter by some
other solution?
What happens when we add a vector x' that is in the null space.
But, the first term has nonzero elements only in those places where the
≠ 0.
The
second term, because it’s in the null space, has nonzero elements only in those
places where
= 0. Therefore the two terms are orthogonal vectors, and their sum must be
greater
length than either part.
Solving Overconstrained Problems
We can solve over constrained problems and get the least squared solution.
The solution strategy is the same
but it is quaranteed to minimize the square of the residual
Proof
Consider the solution given above, and modify it by adding some arbitrary vector
x'. Let
b' = Ax'. Clearly b' is in the range of A.
However (WW-1 − 1) is a diagonal matrix with nonzero element only where
= 0.
Because b' lies in the range of A, UT has nonzero elements only where
≠ 0.
Therefore
these terms are orthongal vectors, and the minimum of their sum is obtained when
b' = 0.
3.2 Solving Homogeneous Problems
Consider a homogeneous problem of the form
Ax = 0. 
(16)
If it is overconstrained, we would like to solve the associated least squares
problem, which
minimizes
The solution of such systems is not unique—it is defined up to a scalar value.
Therefore,
we usually look for the solution to the constrained problem, i.e. ||x|| = 1.
I.e. we look for
the unit length solution that produces the smallest residual.
The solution is given by SVD to be the column vector of V which corresponds to
the
singular value in W which has the smallest magnitude. How do we know this?
Proof
Consider the input s which is this vector, and assume it is position i. The
output is
Notice that 
is a column of U, and it has length 1. This is the shortest
output possible
from this matrix, because any other unit length input would include weighted
sums of 
with weights that must be larger than
, because it is the smallest singular
value.
