1 Review of Least Squares Solutions to Overdetermined Systems
cs412: introduction to numerical analysis
11/9/10
Lecture 17: Rectangular Systems and Numerical Integration
Instructor: Professor Amos Ron
Scribes: Mark Cowlishaw, Nathanael Fillmore
1 Review of Least Squares Solutions to Overdetermined Systems
Recall that in the last lecture we discussed the solution of overdetermined linear systems using the least squares method. Recall that an overdetermined system is a linear system of equations
Am?nx = b
(1)
where A is a matrix with m rows and n columns with m > n. The picture is
b1
...
x1
... xn
=
...
bn
As we discussed, there is in general no exact solution to an overdetermined system like equation 1. Instead, we look for the solution x with the smallest error vector Ax  b, using some vector norm to determine the size of the error vector. In the least squares method, we look for the error vector with the smallest 2norm. More formally, we find a vector x such that
Ax  b Ax  b
for all vectors x
(2)
2
2
For example, consider the system
2 3
x
=
6 6
Here m = 2, n = 1. If we want to solve the first equation, then x must equal 3. If we want to solve the second equation, then x must equal 2. So obviously we will need to choose as a compromise some number between 2 and 3.
Recall that there is a simple method for solving overdetermined systems using least squares. Given the system Ax = b, with A an m ? n matrix, m > n, we proceed as follows:
Step 1. Multiply both sides of the equation by the transpose A :
Ax = b
1
Step 2. Change parentheses:
(A A)x = A b
(3)
Now we have a standard square system of linear equations, which are called the normal equations. Step 3. Solve this system.
Note that any solution of the normal equations (3) is a correct solution to our least squares problem. Most likely, A A is nonsingular, so there is a unique solution. If A A is singular, still any solution to (3) is a correct solution to our problem. In this case, there will be infinitely many solutions, and all of them are correct solutions to the least squares problem. (In general, if a matrix C is singular then the system Cx = y may not have any solution. However, due to the structure of the least squares problem, in our case A A will always have a solution, even if it is singular.)
Note that the method described above is not precisely how we solve leastsquares problems numerically in practice, since
cond(A A) cond(A2)
so that this new linear system as written may be illconditioned. Instead, numerical analysts have devised algorithms that operate directly on the matrix A. However, it is useful to know that there is an efficient method for solving overdetermined systems using least squares.
We revisit our example from earlier in the lecture. Let us execute our algorithm. We start with.
2 3
x
=
6 6
Step 1: Multiply both sides by
2 3
:
2
3
(
2 3
x )= 2
3
6 6
Step 2: Rearrange parentheses:
(2
3
2 3
)
x
=
2
3
6 6
i.e.,
13 x = 30
Step 3: Solve the system:
x
=
30 13
=
2
4 13
(Why
is
the
solution
not
x
=
2
1 2
?
We
can
compute
2 3
2
1 2

6 6
>
2
2 3
2
4 13

6 6
2
to check.)
2
1.1 Least Squares Fitting of Functions
One important application of least squares solutions to overdetermined systems is in fitting a function to a data set. We can informally state the problem as follows:
Problem 1.1 (Function Fitting). Given an interval [a, b] a function f : [a, b], and a parameter n, find a polynomial p n such that p f .
We have seen how to solve this problem using interpolation, however, there are some important reasons why interpolation might not be a good choice for fitting a function f :
? If we want to fit f at many points, interpolation may be inefficient
? There may be noise in the data, so, rather than fitting each data point exactly, we might get better results by merely following the major trends in the data.
We thus introduce now a new paradigm for fitting a function, namely approximation. Specifically, we here discuss leastsquares approximation by polynomials. Our new problem may be formulated as follows
Problem 1.2 (Leastsquares approximation by polynomials). Given m+1 data points {t0, t1, . . . , tm} and the corresponding perturbed function values {y0, . . . , ym}, where yj = f (tj)+ j for j = 1, . . . , m, the problem is to find a polynomial p n = a1tn + a2tn1 + ? ? ? + an+1 that minimizes error in the 2norm. Here error is defined as error at the given data points:
p(x1)  y1
e
:=
p(x2) ...

y2
p(xm)  ym
An example in which n = 1 is given in Figure 1.
We can model this problem as an overdetermined linear system using the Vandermonde approach:
tn0 t... n1
tnm
tn0 1 t... n1 1 tnm1
... ... ... ...
t00 ...t01 t0m
a1 ... an+1
=
y0
y1 ...
ym
We can solve this system using the least squares method we just outlined. Note that, unlike polynomial interpolation, we have two parameters to help us control the quality of the fit: the number of points m + 1 and the degree of the polynomial n.
In practice, we try to choose the degree n to be "just right". If the degree n = 2 and the data is not in a line, then we will never get a good fit, no matter how many points we have  we need to increase the degree instead. If the degree n is too large, the leastsquares polynomial will follow the jitters too closely, which is also bad. Finding a good value in between these two extremes is an art.
3
Figure 1: Each blue point is a (xj, yj) pair. The line is the leastsquares element of of 1. Image from Wikipedia.
Finally, note that, if we have very noisy data, we will need a large number of points m to get a good fit to the function. The error bound is roughly related to the square root of the number of points, so that increasing the number of points by a factor of 4 would result in a reduction in the error by a factor of 1/2.
We can also use cubic splines to approximate functions. Say we have an interval [a, b]. We partition it into N subintervals as usual. However, we choose N much smaller than the number of points, and again we get an approximant instead of an interpolant. This approach is explored in the homework.
2 Underdetermined Systems
An underdetermined system is a system of linear equations in which there are more unknowns than constraints. That is, an underdetermined system has the form
Am?nxn?1 = bm?1
with m < n. For example, consider the system:
[2 3]
x1 x2
=5
(4)
We can easily see that this system has infinitely many solutions defined by the line in 2space:
2 ? x1 + 3 ? x2 = 5
The question is, how do we select one solution from this infinite set of solutions? Intuitively, we would like the "smallest" solution, that is, the solution nearest the origin. For example, if we are asked to solve the equation:
2 ? x1 + 3 ? x2 = 0 4
we have some intuition that [0 0] is the correct choice. Since the solution is a vector, we will measure its "smallness" using some norm. As before, the least squares solution will select the solution with the smallest 2norm.
2.1 Least Squares Solution to Underdetermined Systems
To reiterate, we would like to solve the linear system
Am?nxn?1 = bm?1 with m < n, and in particular we would like to find a solution x with
x 2 x 2 for all vectors x The solution can be found as follows.
Step 1. Assume that we can write the solution as x = A t for some vector t of m unknowns. Write the system in terms of t as:
A(A t) = b
Step 2. Change parentheses:
(AA )t = b
This step results in a square system of equations, which has a unique solution. Step 3. Solve this system to get the unique solution for t. Step 4. Substitute the value of t into x = A t to get the leastsquares solution x of the original
system.
It is not immediately obvious that the assumption x = A t in Step 1 is legitimate. Fortunately it is indeed the case that the least squares solution can be written as x = A t, and in fact the least squares solution is precisely the unique solution which can be written this way. These points are illustrated in the next example.
In this example, let m = 1, n = 2, A = 1 1 , and b = 2 . Thus we want the least squares solution of
Ax = b i.e.
1
1
x1 x2
=2
Step 1. We substitute x = A t:
11
1 1
t1
=2
Step 2: We change parentheses:
1
1
1 1
t1 = 2
5
i.e.,
2 t1 = 2
Step 3: We solve for t:
t1 = 1
Step 4: We substitute the value of t back into x = A t to find x:
x1 x2
=
1 1
1
i.e.
x1 x2
=
1 1
We are now in a position to understand how the assumption that x = A t in Step 1 helps us. Consider Figure 2. In this figure, the solution space of the original system
11
x1 x2
=
2
is shown as the black line which passes through (2, 0) and (0, 2). The assumption that x = A t, i.e., that
x1 x2
=
1 1
t1
means that the solution must also lie on the magenta line that passes through the origin and is perpendicular to the black line. The unique leastsquares solution to the original system occurs at the intersection of these two lines.
Figure 2: Example of solution space of an underdetermined system. 6
We end our discussion of leastsquares by comparing from an intuitive point of view our approaches to the solution of over and underdetermined systems. In both cases, we did something similar: multiply the coefficient matrix A by A . We chose the side on which we multiplied A (either A A or AA ) in order to get a smaller square matrix, and then we solved the corresponding smaller system. The picture corresponding to the substitution is
=
(i)
(iii)
(ii)
In the case of underdetermined systems, (i) corresponds to A, (ii) corresponds to A and (iii) corresponds to the smaller square matrix AA . In the case of overdetermined systems, (i) corresponds to A , (ii) corresponds to A and (iii) corresponds to the smaller square matrix A A.
Of course, as we have seen, other details of the algorithms also differ, but the above explains the big picture intuitively.
3 Numerical Integration
Recall that the definition of the definite integral of a continuous (and we will assume positive)
function f (t) over the interval [a, b],
b a
f (t)dt
is
the
area
under
the
curve,
as
shown
in
Figure
3.
a
b
Figure 3: The Definite Integral of f (t) over [a, b]
What is the best way to calculate the definite integral? Our experience in math classes suggests that we might use the antiderivative, that is a function F with F = f :
b
f (t)dt = F (b)  F (a)
(5)
a
For example, we can calculate the integral of 1/t between 2 and 3 using antiderivatives:
3 2
1 t
dt
=
log
3

log
2
7
However, how do we actually find the numerical value of log 3  log 2? This brings up two important reasons why antiderivatives are not used (with a few exceptions) in the numerical calculation of definite integrals:
1. There exist many functions that have no antiderivative, or, the antiderivative may exist for a function, but we may not have the notation to express it, for example et2 dt the key point is that this is the common case. We can only find antiderivatives for a very small number of functions, such as those functions that are popular as problems in mathematics textbooks. Outside of math classes, these functions are rare.
2. Even if we can find an antiderivative, calculating its value may be more difficult than calculating the value of the definite integral directly.
In the next few lectures, we shall discuss methods for directly calculating direct integrals by calculating the area under the curve.
8
................
................
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
 lecture 8 least norm solutions of undetermined equations
 1 3 initial conditions initial value problems
 chapter 6 r a x the minimum norm solution and the least
 1 review of least squares solutions to overdetermined systems
 guidelines for the method of undetermined
 second order linear differential equations
 exam 1 review questions and answers part i finding
 1 20 pts a find the solution of the following
 lecture 7 solving ax 0 pivot variables special solutions
 second order linear nonhomogeneous differential equations
Related searches
 how to find a company s annual report
 find a company stock symbol
 find a stock price
 find a song by a few lyrics
 find a quote from a book
 find a quote in a book
 concentration of a solution calculator
 moles in a solution calculator
 find general solution of matrix calculator
 find the solution to system of equations
 find a free address of a person
 find the solution to the equation calculator