\documentclass[12pt]{article}
%
\usepackage[noTS1]{mathtime} % Comment out when using TtH
\input TS1avoid.tex % Comment out when using TtH
\usepackage{epsfig} % Comment out when using TtH
%
\def\copyright{\protect\pcopyright}
\def\pcopyright{\textrm{\ooalign{\hfil
     \raise.07ex\hbox{c}\hfil\crcr\mathhexbox20D}}}
%
\newcommand{\real}{\mbox{${\rm I\!R}$}}
\newcommand{\complex}{\mbox{$\,{\rm l\!\!\!C}\,$}}
\newcommand{\rn}[1]{\mbox{${\real}^{#1}$}}
\newcommand{\rmn}[2]{\mbox{${\real}^{{#1} \times {#2}}$}}
\newcommand{\cmn}[2]{\mbox{${\complex}^{{#1} \times {#2}}$}}
%
\title{Linear Algebra}
\author{William F. Moss\thanks{Department of Mathematical Sciences, Clemson
University, Clemson, SC 29634--1907, U.S.A.
(\texttt{bmoss@math.clemson.edu}).
Copyright \copyright 1995,1996 William F. Moss. All rights reserved.
}}

\begin{document}
\date{}
\bibliographystyle{unsrt}
\maketitle

\section{Least Squares Linear Models}
Suppose we are given a set of $m$ data points
\[
(t_{1},y_{1}),(t_{2},y_{2}),\ldots,(t_m,y_m)
\]
which we believe to be samples from some underlying function. Our
problem is to approximate the underlying function using
all available information.
In general, this is a difficult problem because we may know very
little about the underlying function
and the data may be corrupted with noise.
There are two common approaches to approximation of the underlying
function: interpolation and curve fitting.
In interpolation a function, called an interpolant, is constructed
whose graph passes through the data points. In curve fitting
a function is constructed which passes "close to" the data points but
not necessarily through them. This function is said to "fit" the
data. When a significant amount of noise
is present in the data, an interpolant may not provide a
satisfactory approximation of the underlying function
because the interpolant may oscillate rapidly. In this case, a slowly
varying function that "fits" the data may provide
a better approximation of the underlying function.

A linear model of the form
\begin{equation}
\label{rep}
f(t;\mathbf{c}) = \sum_{j=1}^{n} c_{j} \phi_{j}(t)
\end{equation}
is often used to interpolate or fit data. It is a linear combination of
"basis" functions,
$\phi_{1}(t), \cdots, \phi_{n}(t)$,
which are selected based on practical considerations, visual inspection
of the data, and knowledge of the processes giving rise to the data.
The linear model depends on an independent variable $t$ and on a set
of $n$ coefficients, $c_1,\ldots,c_n$. The
$\mathbf{c}$ in $f(t;\mathbf{c})$
denotes a column vector containing these coefficients.
In interpolation, the number of basis functions, $n$, is chosen to be
equal to the number of data points, $m$, while for curve fitting
$n$ is typically much smaller than $m$. We will assume that
$n \leq m$.

As an example, suppose a straight line is to be used to fit $m \geq 2$
data points. We set $n=2$ and
$\phi_{1}(t) = 1$ and $\phi_{2}(t) = t$.  Then $f$ has the form
$f(t;\mathbf{c}) = c_{1} + c_{2}t$.
Generally, this line will be an interpolant only in case $m=2$.
A straight line fit is often used in statistics where this line is
called the regression line.

If the linear model is constructed so that it changes much more
slowly than an interpolant, then curve fitting
can be used as a noise filter. This approach is illustrated in the first
problem of this project. Here, samples taken from a straight line are corrupted
with noise generated randomly, and then a straight line is fit to the data.
The original line is very nearly recovered.

In the mathematical discussion below, we will
use the following matrix notation which was introduced in the
Orthogonal Methods course outline. Let
\[
\mathbf{y}=[y_1,\ldots,y_m]^T,\;\;
\mathbf{c} = [c_1,\ldots,c_n]^T\;\;,
A = (a_{ij}) = (\phi_j(t_i)).
\]
The $m \times n$ matrix $A$ is often called the design matrix.

The interpolation problem is to find $\mathbf{c}$ so that the
interpolation equations
\begin{equation}
\label{int}
f(t_i;\mathbf{c}) = y_i,\;\;i=1,\ldots,m,
\end{equation}
have a solution.
Substituting equation~(\ref{rep}) into (\ref{int}), we find that
\[
f(t_i;\mathbf{c}) = \sum_{j=1}^n c_j \phi_j(t_i)
= \left( A \mathbf{c} \right)_i,\;\;i=1,\ldots,m
\]
which is a system of $m$ equations and $n$ unknowns with the matrix form
\begin{equation}
\label{sys1}
A \mathbf{c} = \mathbf{y}.
\end{equation}

The curve fitting problem is to find $\mathbf{c}$ so that the graph of
$f$ passes "close to" the data points. The most commonly used
method for defining "close to" is called the least squares method.
In the least squares method, $\mathbf{c}$ is determined
by minimizing the sum of the squares of the vertical deviations between
the graph of $f$ and the data points. The problem is to find
$\mathbf{c}_{ls}$ so that
\begin{equation}
\label{lsq1}
\sum_{i=1}^{m} \left[f(t_i;\mathbf{c}_{ls})-y_i\right]^2 =
\min_{\mathbf{c} \in \rmn{n}{1}}
\sum_{i=1}^{m} \left[f(t_i;\mathbf{c})-y_i\right]^2.
\end{equation}
We can convert (\ref{lsq1}) into matrix form as follows.
First, note that
\begin{equation}
\label{sub1}
f(t_i;\mathbf{c}) = \sum_{j=1}^{n} c_j \phi_j(t_i) =
(A \mathbf{c})_i\;\;\mbox{and}\;\;
\sum_{i=1}^{m} \left[(A \mathbf{c})_i - y_i \right]^2 =
\|A \mathbf{c} - \mathbf{y}\|_2^2.
\end{equation}
From (\ref{lsq1}) and (\ref{sub1}) we see that
\begin{equation}
\label{der1}
\sum_{i=1}^{m} \left[f(t_i;\mathbf{c}_{ls})-y_i\right]^2 \leq
\sum_{i=1}^{m} \left[f(t_i;\mathbf{c})-y_i\right]^2
\;\;\mbox{for all}\;\mathbf{c}
\end{equation}
implies that
\begin{equation}
\label{der2}
\|A \mathbf{c}_{ls} - \mathbf{y}\|_2^2 \leq \|A \mathbf{c} - \mathbf{y}\|_2^2
\;\;\mbox{for all}\;\mathbf{c}.
\end{equation}
Taking the square
root of both sides of (\ref{der2}), yields the standard matrix form
of the linear least squares problem.
Find $\mathbf{c}_{ls}$ so that
\begin{equation}
\label{lsq2}
\|A \mathbf{c}_{ls} - \mathbf{y}\|_2 =
\min_{\mathbf{c} \in \rmn{n}{1}} \|A \mathbf{c} - \mathbf{y}\|_2.
\end{equation}

\begin{figure}[htb]
\centerline{\epsfig{figure=fig2.eps,height=3.0in}}
\caption{The $m=3$, $n=2$ case.}
\label{fig1}
\end{figure}

Figure \ref{fig1} provides geometric insight into the problem
of solving (\ref{sys1}) and (\ref{lsq2})
for the case $m=3$ and $n=2$. Here
$\mathbf{y} \in \rmn{3}{1}$ and $A = [\mathbf{a}_1,\mathbf{a}_2]$
is $3 \times 2$ with two
linearly independent columns,
$\mathbf{a}_1$ and $\mathbf{a}_2$. Now $Ran(A)$ is
the $\mbox{span}\{\mathbf{a}_1,\mathbf{a}_2\}$, that is, the
set of all linear combinations of the columns of $A$.
It is a two-dimensional subspace of $\rmn{3}{1}$
and is visualized in Figure \ref{fig1}
by the plane which passes through the origin and contains
$\mathbf{a}_1,\mathbf{a}_2$.
Also, for any
$\mathbf{c} \in \rmn{2}{1}$,
$A \mathbf{c} = c_1 \mathbf{a}_1+c_2 \mathbf{a}_2 \in Ran(A)$.
Now if $\mathbf{y}$ is
not in the plane $Ran(A)$, as is the case in Figure \ref{fig1}, the
linear system (\ref{sys1}) and the interpolation problem will not
have a solution.
On the other hand, the least squares problem always
has a solution $\mathbf{c}_{ls}$.
The vector $A \mathbf{c}_{ls}$ is the
vector in the plane $Ran(A)$, which is closest to $\mathbf{y}$. Also,
the vector $\mathbf{y} - A\mathbf{c}_{ls}$
will be orthogonal to the
the plane $Ran(A)$. Because the columns of $A$ are linearly independent,
or equivalently because $rank(A)=2$, $\mathbf{c}_{ls}$ is the only
solution to the least squares problem. Now imagine a case where
$\mathbf{a}_1$ and $\mathbf{a}_2$ lie along the same line. In this case,
$Ran(A)$ is a one-dimensional
subspace of $\rmn{3}{1}$ and can be visualized by a line passing
through the origin. Now there are infinitely many ways
to describe a vector in $Ran(A)$ as a linear combination of $\mathbf{a}_1$
and $\mathbf{a}_2$, and so there are infinitely many solutions to the
least squares problem. We would prefer to have a unique linear
model which fits the data. This will happen if the basis functions
used in the linear model are chosen so that the columns of $A$
are linearly independent.

The $m >3$ case works the same ways as the $m=3$ case.
For $\mathbf{c}$, $A \mathbf{c} \in Ran(A)$,
a subspace of $\rmn{m}{1}$. In the least squares problem, we
find the vector $\mathbf{c}_{ls}$ so that $A \mathbf{c}_{ls} \in Ran(A)$
is as close to the vector $\mathbf{y}$ as possible. Because we have assumed that
$n \leq m$, $rank(A) \leq n$.
If the basis functions have been well chosen, the columns of $A$ will
be linearly independent and $rank(A)=n$. In this case, (\ref{lsq2})
is said to be a full rank least squares problem and
has a unique solution.
If $rank(A) < n$, (\ref{lsq2}) is said to be rank deficient and
has infinitely many solutions.

In Orthogonal Methods course outline,
we have see that the singular value decomposition (SVD)
of $A$ can be used to solve the least squares problem. We
note that in the $m=n$ case, it can also be used to solve
(\ref{sys1}), although Gauss elimination with partial pivoting
is more frequently used. In the Orthogonal Methods course outline a
formula is given for $\mathbf{c}_{ls}$.
In the rank deficient case, this formula gives the least squares
solution which has the smallest 2-norm. There are two other methods that
are commonly used to solve the full rank least squares problem:
QR factorization with column pivoting followed by the solution of
a triangular system, and solution of the normal equations.
However, the SVD approach is regarded as the most computationally reliable
method.

As explained in the instructions for this project, you are to create an M-file
with filename P1loginid.m containing MATLAB commands and statements to solve
the following problems. Note that you can cut MATLAB code from this PDF document
and paste it into the MATLAB editor.

\begin{itemize}
% Problem 1
\item \textbf{Problem 1} In this problem you will fit noisy data using a line.
We generate
the data by taking 20 uniformly spaced samples from the line $y = 1 + 2t$ for
$t \in [0,1]$ and adding a small amount of random noise to each sample.
Add the following lines to P1loginid.m.

\begin{verbatim}
% Project 2. Last Name First Name. GroupXX

echo on

% Problem 1
% create m > 2 noisy data points lying close to a line
m = 20;
t = linspace(0,1,m)';
epsilon = .2; % Maximum noise amplitude
y = 1 + 2*t + epsilon*rand(m,1);
% Use the model c(1) + c(2)*t
% Construct the design matrix A.
A = [ones(m,1),t];
% Use the SVD to solve the least squares problem.
c = pinv(A)*y
if rank(A) == 2
   disp('The design matrix is full rank')
else
   disp('The design matrix is rank deficient.')
end
% Since A is full rank, we have found the unique
% solution to the full rank least squares problem.
% When the design matrix is rank deficient, the
% least squares problem has infinitely many
% solutions. The above computation would produce
% the solution that has the smallest 2-norm.
%
% Plot
tt = linspace(0,1,100)';
yy = c(1) + c(2)*tt;
plot(t,y,'o',tt,yy)
\end{verbatim}
At the MATLAB prompt, type P2loginid to run your M-file. Note that a semi-colon
at the end of a line suppresses screen output for that line.
You should see your plot in a window labeled Figure No. 1.
Next, add three more lines for Problem 1.
Use the MATLAB commands "xlabel" (\verb#help xlabel#),
"ylabel" (\verb#help ylabel#),
and "title" (\verb#help title#) to label the
$x$ and $y$ axes and to add explanatory text at the top of the plot.
Run your M-file again. Notice that the solution to the least squares problem
is a coefficient vector which is close to $[1,2]$.
% Problem 2
\item \textbf{Problem 2} The water level in the North Sea is mainly
determined by the so-called
$M_{2}$-tide, whose period is about 12 hours.  A reasonable but simple model
for predicting the level at any time $t$ is a function of the form
\[
h(t) = c_{1} \phi_{1}(t) + c_{2} \phi_{2}(t) +
c_{3} \phi_{3}(t),\hspace{.25in} t \mbox{ in hours.}
\]
where
\[
\begin{array}{ccc}
\phi_{1}(t) = 1, & \phi_{2}(t) = \sin \left(\frac{2 \pi t}{12}\right)
& \phi_{3}(t) = \cos \left(\frac{2 \pi t}{12}\right).
\end{array}
\]
Here we are using basis functions which are periodic with period
12 hours. Does this seem reasonable?
We wish to estimate the values of the unknown coefficients $c_{1}$,
$c_{2}$, and $c_{3}$
from a set of measured values of water level $y_1, \ldots, y_m$ made at
corresponding times $t_1, \ldots, t_m$ by solving a linear least
squares problem as discussed above.
From calculus we know that determining $c_{1}$, $c_{2}$,
and $c_{3}$ corresponds to estimating
the mean water level (bias), the amplitude of variation about the mean, and
the phase of the oscillatory water level.

Suppose we have made the measurements:
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|l|}\hline
$t_{j}$ & 0 & 2 & 4 & 6 & 8 & 10 & hours \\ \hline
$y_{j}$ & 1.0 & 1.6 & 1.4 & 0.6 & 0.2 & 0.8 & meters \\ \hline
\end{tabular}
\end{center}

Add the following lines to your M-file to solve this linear least
squares problem having $m=6$ data points and $n=3$ basis functions.

\begin{verbatim}
% Problem 2

m = 6;
t = [0;2;4;6;8;10]; % hours
y = [1;1.6;1.4;0.6;0.2;0.8]; % meters
% design matrix
A = [ones(m,1),sin(pi*t/6),cos(pi*t/6)];
c = pinv(A)*y % least squares solution
% Plot the data and the model
% plot vectors
tt = linspace(0,10,100)';
yy = [ones(100,1),sin(pi*tt/6),cos(pi*tt/6)]*c;
figure % create a new plot window
plot(t,y,'o',tt,yy)
\end{verbatim}
At the MATLAB prompt, type P2loginid to run your M-file.
You should see your plot for problem 2 in a window labeled Figure No. 2.
Next, add three more lines for Problem 2.
Use the MATLAB commands "xlabel" (\verb#help xlabel#),
"ylabel" (\verb#help ylabel#),
and "title" (\verb#help title#) to label the
$x$ and $y$ axes and to add explanatory text at the top of the plot.
Run your M-file again. Notice that the model passes "close to" the data
points but does not interpolate them.
% Problem 3
\item \textbf{Problem 3} The interpolation equations (\ref{int})
can be satisfied if and only if the linear system (\ref{sys1})
has a solution.
If $n<m$, there will be more equations than unknowns and this overdetermined
system will not generally have a solution. This is clear in Figure \ref{fig1}
where $m=3$ and $n=2$. Show that this is the case
for the example in Problem 2 by applying the rank test from the
Linear Systems and Matrices Outline.
You must compare the rank of $A$ to the rank of $[A,\mathbf{y}]$.
% Problem 4
\item \textbf{Problem 4} Add lines to your M-file to
find a straight line fit to the following
data and plot a graph of the straight line model
along with the data on the same set of axes.  Label your graph.
Note that here we have $(x,y)$ data instead of $(t,y)$ data.
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}\hline
Density of ore x  &2.8&2.9&3.0&3.1&3.2&3.2&3.2&3.2&3.3&3.4  \\ \hline
Iron content y(\%)&30 &26 &33 &31 &33 &35 &33 &37 &36 &33  \\ \hline
\end{tabular}
\end{center}
% Problem 5
\item \textbf{Problem 5} Balancing a Chemical Reaction.
\footnote{This problem appears
in \textit{FirstLeaves: A Tutorial Introduction}, B. W. Char
et. al., Springer 1992, page 197 (ISBN 0-387-97621-3).}
Balance the chemical reaction
\[
x_1 C u_2 S + x_2 H^+ + x_3 N O_3^- \longrightarrow
x_4 C u^{2+} + x_5 N O + x_6 S_8 + x_7 H_2 O
\]
by calculating the smallest possible, positive integer coefficients
$x_1,\ldots,x_7$. The principles are that the number of atoms of each
element must be conserved as well as the total electric charge.
This gives six equations for the seven coefficients. Put these
equations in the form of a homogeneous system $A\mathbf{x}=\mathbf{0}$.
The null space $N(A)$ has dimension one. Find a basis vector for
this null space. Find the solution in the form $c\mathbf{v}$ where
$\mathbf{v}$ is your basis vector and $c$ is a scalar.
Remember that the coefficients must be positive integers and they
must be as small as possible. Hint: it is possible to solve this problem
using the MATLAB functions augmovie, or ref and slash, or null.
% Problem 6
\item \textbf{Problem 6} The following problem arises later in the course
when we model heat conduction in a rod and a vibrating string.
Find a scalar $\lambda$ (eigenvalue) and a nontrivial function
$X(x)$ (eigenfunction) so that
\begin{equation}
\label{sl}
X''(x) + \lambda X(x) = 0
\end{equation}
\begin{equation}
\label{sla}
X(0) = 0
\end{equation}
\begin{equation}
\label{slb}
X(1) = 0
\end{equation}
This problem is sometimes referred to as an eigenvalue problem for an
ordinary differential equation. It is also called a Sturm-Liouville problem.
It can be shown that there are infinitely many positive eigenvalues.
We want to approximate the smallest
one, which the Sturm-Liouville theory says is $\pi^2$.
We will reduce this problem to a matrix eigenvalue problem using a
centered finite difference approximation for $X''$.

First, we discretize the interval $[0,1]$ with mesh points
$x_i = ih,\;i=0,\ldots,n+1$, and $h = 1/(n+1)$. Next, we use the
approximation
\begin{equation}
\label{fd}
X''(x_i) \approx \frac{X(x_{i+1}) - 2X(x_i) + X(x_{i-1})}{h^2}
\;\;\mbox{for}\;i = 1,\ldots,n,
\end{equation}
to derive a matrix
eigenvalue problem by evaluating (\ref{sl}) at $x_1,\ldots,x_n$,
and using (\ref{sla}), (\ref{slb}), and (\ref{fd}).
This problem has the form
\begin{equation}
\frac{1}{h^2} A Z = \lambda Z
\end{equation}
where $Z = [X(x_1),\ldots,X(x_n)]^T$ and $A$ has the number 2 on the
main diagonal, the number -1 on the first subdiagonal and first
superdiagonal, and is zero elsewhere.

Add the following lines to your M-file to solve this problem.
Experiment with the value of $n$.

\begin{verbatim}
% Problem 6

n = 100;
h = 1/(n+1); e = ones(n,1)/h^2;
A = spdiags([-e 2*e -e],-1:1,n,n);
z = eig(A); format long
y = sort(z)/pi^2;
y(1)
\end{verbatim}
%
\end{itemize}

\end{document}
