Least Square
1 Description and Objectives
In this (our final) lab, you will put together many of the matrix operations
that you have
learned to produce an application that can solve Least Squares problems from
scratch.
This is a farily involved lab. (Sorry.) But on the bright side, you will have a
good while to
finish it.
Lab Objectives
1. Understand DenseMatrix class operations from previous lab.
2. Implement a Cholesky Factorization routine for solving (dense) symmetric
positive definite
linear systems
3. Understand how to use the Cholesky Factorization to solve a linear system
4. Learn how to create the normal equations that are required for a least
squares curve
fitting, including operations for matrix transpose
5. Solve the linear system(s) necessary to perform a least-squares curve fitting
2 Cholesky Decomposition
Our first step towards our goal of having a least squares solver is to build a
class that can
factorize a symmetric positive definite matrix into lower and upper triangular
parts: A =
LLT . All of the operations today will use (and extend) the DenseMatrix classes
you wrote
for Lab 11.
2.1 Problem
Implement the constructor for the CholeskyDecomposition class I gave you. You
may wish
to use the matrix in the file C1.txt, which has a decomposition:
3 Solving Linear Systems
3.1 Problem
Write a solve method for the CholeskyDecomposition class that takes a
DenseMatrix
as input and outputs a DenseMatrix as the solution to the matrix system
AX = B
The pseudocode TriangularSolve given in class today should come in quite handy.
You can
use the file RHS.txt, which has b = [32, 26, 38, 30]T You can (if you wish)
assume that B has
only one column (and then so would the matrix returned by your method) Note
however, that
this is not necessary...
4 Useful Code
4.1 Problem
Write a (simple) method for your DenseMatrix class that returns a copy of the
transpose of
the matrix
5 Least Squares
You are a master brewmaker, and you would like to form a functional relationship
to help you
predict the “yummyness” of a beer y as a function of the amount of hops x you
put in the beer.
Your experiments yielded the measures given in Table 1, as well as hours of
enjoyment:
Table 1: Measurements of Yummyness
| Hops | Yummyness |
 |
|
5.1 Problem
Using the codes you have developed, compute a best linear fit for these
measurements: y =
. What are the coefficients
? Plot the data as well as your (linear)
approximation
to it.
5.2 Problem
Using the codes you have developed, compute a best quadratic fit for these
measurements: y =
. What are the coefficients
? Plot the data as well as your (quadratic)
approximation to it.
6 Bonus Problem
6.1 Problem
Let e(n) be the total error in the approximation (
)
if a basis of polynomials up to degree
n − 1 is used. Plot e(n) as a function of n for the data in Table 1
7 Lab Deliverables
• Three files: Lab12.java, DenseMatrix.java, CholeskyDecomposition.java. You
should not have to change (too much) the code in Lab12.java, though you may find
it
useful to comment parts out while you do the code development. Also, your
estimates
and plots for the problems in Section 5.
8 Problem Set (In addition to those from Lab11)
8.1 Problem
CLRS 28.5-6
8.2 Problem
For the following two matrices, provide a Cholesky decomposition, or prove that
the matrix is
not SPD
8.3 Problem
28-1 (a), (b), (c).
8.1 Extra Credit
8.4 Problem
28-1 (d) (e)