
\documentclass [11pt] {article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig}

\textheight 7.5 in
\textwidth 5 in
\topmargin 0.0 in
\input{../newcomm}

\begin{document}

\title {Least Squares Approximation}
\author{Gerald Farin\\
Computer Science and Engineering\\
Arizona State University\\
Tempe, AZ 85287-5406\\
email {\tt farin@asu.edu}\\ }

\maketitle


In many applications, one is given more data points than can be
interpolated by a polynomial curve. In such cases, an
{\em approximating} curve will be needed. Such a curve does not
pass through the data points exactly; rather it passes near them,
still capturing the shape inherent to the given points. The
technique best known for finding such curves is known as
{\em least squares approximation}\index{least squares}.

To make matters more precise, assume we are given $P+1$ data points
$\pp_0,\ldots, \pp_P$, each $\pp_i$ being associated with a
parameter value $t_i$.
 We wish to find a polynomial curve $\xx(t)$ of a given degree $n$
such that the distances $\|  \pp_i - \xx(t_i) \|$ are small.
Ideally, we would have $\pp_i=\xx(t_i); i=0,\ldots,P$. If our
polynomial curve $\xx(t)$ is of the form
$$
	\xx(t)={\bf c}_0 C^n_0(t)+\ldots +{\bf c}_nC^n_n(t)
$$
for some set of basis functions $C^n_i(t)$, then we would have
$$
\begin{aligned}
	{\bf c}_0C^n_0(t_0)+\ldots+{\bf c}_nC^n_n(t_0) &= \pp_0\\
						&\vdots\\
	{\bf c}_0C^n_0(t_P)+\ldots+{\bf c}_nC^n_n(t_P) &= \pp_P.
\end{aligned}
$$
This may be condensed into matrix form:
$$
       \begin{bmatrix}
        C^n_0(t_0)& \ldots & C^n_n(t_0)\\
        \quad       &  \vdots   & \quad \\
        \quad       &  \vdots   & \quad \\
        C^n_0(t_P)   &  \ldots & C^n_n(t_P) 
        \end{bmatrix}
        \begin{bmatrix}
        {\bf c}_0\\ \vdots\\{\bf c}_n 
        \end{bmatrix}
	=
	\begin{bmatrix}
        {\bf p}_0\\ \vdots\\ \vdots\\{\bf p}_P 
        \end{bmatrix}.
$$
Or, even shorter:
\begin{equation}
	M {\bf C} = {\bf P}.
	\label{eq:leastsys}
\end{equation}
Since we assume the number $P$  of data points is larger than the
degree $n$ of the curve, this linear system is clearly overdetermined.
We attack it   by simply multiplying both sides by
$M^{\rm T}$:
\begin{equation}
	M^{\rm T}M {\bf C} =M^{\rm T} {\bf P}.
	\label{eq:leastsys1}
\end{equation}
This is a linear system with $n+1$ equations in $n+1$ unknowns,
with a square coefficient matrix $M^{\rm T}M$. Its soulution is
staightforward.

But is the solution meaningful? After all, we employed a rather
crude trick in going from (\ref{eq:leastsys}) to 
(\ref{eq:leastsys1}). It turns out that our solution is not
only meaningful -- in fact it is {\em optimal}.

In order to justify this claim (and also making it more precise),
we give a second derivation of (\ref{eq:leastsys1}). 

Consider the following expression:
\begin{equation}
	f({\bf c}_0,\ldots,{\bf c}_n)=
	\sum_{i=0}^P \| \pp_i - \xx(t_i) \|^2.
	\label{eq:leastset}
\end{equation}
If the curve $\xx(t)$ does not deviate from the data points 
$\pp_i$ by much, then $f$ will attain a small value. Ideally,
if $\xx$ were to pass through all $\pp_i$ exactly,  we would
have $f=0$. 

If we substitute the full definition of $\xx(t)$ into 
(\ref{eq:leastset}), we obtain
\begin{equation}
	f({\bf c}_0,\ldots,{\bf c}_n)=
	\sum_{i=0}^P \| \pp_i - \sum_{j=0}^n{\bf c}_jC^n_j(t_i) \|^2.
\end{equation}
We wish to find a set of ${\bf c}_i$ such that the value of $f$
becomes minimal. Since $f$ is a multivariate function of 
all components of the 
${\bf c}_i$, such a minimum is achieved if $f'$s partials with
respect to all these components vanish:
$$
	\frac{\partial f}{\partial {\bf c}^d_k} = 0;~~
	k=0,\ldots,n; ~~ d=1,2 ~~ {\rm or}~~ d=1,2,3,
$$
where the superscript $d$ labels the individual components of 
the ${\bf c}_k$. Computing the required derivatives yields
$$	
	\sum_{i=0}^P\big[\pp^d_i - \sum_{j=0}^n{\bf c}^d_jC^n_j(t_i)
	\big]
	C^n_k(t_i)
	=  0; ~~k=0,\ldots,n; ~~~~ d=1,2 ~~ {\rm or}~~ d=1,2,3.
$$
Upon rearranging, we see that this is 
identical to (\ref{eq:leastsys1})!

The linear system (\ref{eq:leastsys1}) is known as the system of
{\em normal equations}, and goes back to Gauss.

 





%\bibliographystyle{plain}
%\bibliography{../../fourth/refs}




\end{document}

\bef
        \epsfig{file=coons_ex.ps,height=3.5in}
        \caption{Discrete Coons patches: an example.}
        \label{fig:coons_ex}
\eef
