<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Outline of the Available Methods</TITLE>
<META NAME="description" CONTENT="Outline of the Available Methods">
<META NAME="keywords" CONTENT="vol1">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="vol1.css">
<LINK REL="next" HREF="node133.html">
<LINK REL="previous" HREF="node127.html">
<LINK REL="up" HREF="node127.html">
<LINK REL="next" HREF="node129.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html2161"
HREF="node129.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2157"
HREF="node127.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2151"
HREF="node127.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2159"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2160"
HREF="node216.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="icons.gif/index_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html2162"
HREF="node129.html">The Newton-Raphson Method.</A>
<B> Up:</B> <A NAME="tex2html2158"
HREF="node127.html">Fitting of Data</A>
<B> Previous:</B> <A NAME="tex2html2152"
HREF="node127.html">Fitting of Data</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H1><A NAME="SECTION001310000000000000000"> </A>
<A NAME="fit-methods"> </A>
<BR>
Outline of the Available Methods
</H1>
<P>
Let <I>y</I>(<I>x</I>,<I>a</I>) be a function where
<!-- MATH: $x = (x_1,\ldots,x_n) \in \rm I\kern-.2000em\hbox{R}^{n}$ -->
<IMG
WIDTH="215" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img261.gif"
ALT="$x = (x_1,\ldots,x_n) \in \rm I\kern-.2000em\hbox{R}^{n}$">
are the independent variables and
<!-- MATH: $a \in A \subset \rm I\kern-.2000em\hbox{R}^{p}$ -->
<IMG
WIDTH="120" HEIGHT="42" ALIGN="MIDDLE" BORDER="0"
SRC="img262.gif"
ALT="$a \in A \subset \rm I\kern-.2000em\hbox{R}^{p}$">
are the <I>p</I> parameters lying in the domain <I>A</I>. If <I>A</I> is not the whole
space
<!-- MATH: $\rm I\kern-.2000em\hbox{R}^p$ -->
<IMG
WIDTH="35" HEIGHT="22" ALIGN="BOTTOM" BORDER="0"
SRC="img263.gif"
ALT="$\rm I\kern-.2000em\hbox{R}^p$">,
the problem is said to be constrained.
<P>
If a situation can be observed by a set of events
<!-- MATH: $(y^{(i)},x^{(i)}) i=1,\ldots,m$ -->
<IMG
WIDTH="212" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img264.gif"
ALT="$(y^{(i)},x^{(i)}) i=1,\ldots,m$">,
i.e. a
set of couples representing the measured dependant and
variables, it is possible to deduce the value of the
parameters of your model <I>y</I>(<I>x</I>,<I>a</I>) corresponding to that situation.
As the measurements are generally given with some error, it is
impossible to get the exact value of the parameters but only an
estimation of them. Estimating is in some sense finding the most likely
value of the parameters. Much more events than parameters are in general
necessary.
<P>
In a linear problem, if the errors on the observations
have a gaussian distribution, the ``Maximum Likelihood Principle'' gives you
the ``best estimate'' of the parameters as the solution
of the so-called ``Least Squares Minimization'' that follows:
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
\min_{a\in A}~~\chi^2~(a)
\end{displaymath} -->
<IMG
WIDTH="110" HEIGHT="52"
SRC="img265.gif"
ALT="\begin{displaymath}\min_{a\in A}~~\chi^2~(a)\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
with
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
\chi^2~(a)~=~\sum_i~w^{(i)}~[~y^{(i)}~-~y(x^{(i)},a)~]^2~
\end{displaymath} -->
<IMG
WIDTH="379" HEIGHT="61"
SRC="img266.gif"
ALT="\begin{displaymath}\chi^2~(a)~=~\sum_i~w^{(i)}~[~y^{(i)}~-~y(x^{(i)},a)~]^2~\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
The expected variance of the so-computed estimator is minimum among all
approximation methods and is therefore called in statistics
an ``efficient estimator''.
<P>
The quantities
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
r^{(i)}(a)~=~\sqrt{w^{(i)}}~[~y^{(i)}~-~y (x^{(i)},a)~]
\end{displaymath} -->
<IMG
WIDTH="344" HEIGHT="40"
SRC="img267.gif"
ALT="\begin{displaymath}r^{(i)}(a)~=~\sqrt{w^{(i)}}~[~y^{(i)}~-~y (x^{(i)},a)~]\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
are named the residuals and <I>w</I><SUP>(<I>i</I>)</SUP> the weight of the <I>i</I><SUP><I>th</I></SUP>observation that can be, for instance, the inverse of the computed
variance of the observation.
<P>
If <I>y</I>(<I>x</I>,<I>a</I>) depends linearly on each parameter <I>a</I><SUB><I>j</I></SUB>, the problem is
also known as a Linear Regression and is solved in MIDAS by the command
<TT>REGRESSION</TT>. This chapter deals with <I>y</I>(<I>x</I>,<I>a</I>) which
have a non-linear dependance in a.
<P>
Let us now introduce some mathematical notations.
Let <I>g</I>(<I>a</I>) and <I>H</I>(<I>a</I>) be respectively the gradient and the Hessian
matrix of the function <IMG
WIDTH="58" HEIGHT="48" ALIGN="MIDDLE" BORDER="0"
SRC="img268.gif"
ALT="$\chi^2(a)$">.
They can be expressed by
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
g(a)~=~2~J(a)^T~r(a)~~~~~~and
\end{displaymath} -->
<I>g</I>(<I>a</I>) = 2 <I>J</I>(<I>a</I>)<SUP><I>T</I></SUP> <I>r</I>(<I>a</I>) <I>and</I>
</DIV>
<BR CLEAR="ALL">
<P></P>
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
H(a)~=~2~(J(a)^T~J(a)~+~B(a))
\end{displaymath} -->
<I>H</I>(<I>a</I>) = 2 (<I>J</I>(<I>a</I>)<SUP><I>T</I></SUP> <I>J</I>(<I>a</I>) + <I>B</I>(<I>a</I>))
</DIV>
<BR CLEAR="ALL">
<P></P>
where <I>r</I>(<I>a</I>) is the residuals vector
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
r(a)~=~(r^{(1)}(a),\ldots,r^{(m)}(a))~~,
\end{displaymath} -->
<IMG
WIDTH="297" HEIGHT="40"
SRC="img269.gif"
ALT="\begin{displaymath}r(a)~=~(r^{(1)}(a),\ldots,r^{(m)}(a))~~,\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
<I>J</I>(<I>a</I>) the Jacobian matrix of <I>r</I>(<I>a</I>) i.e.
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
J(a)_{ij}~={\partial {r^{(i)}} \over \partial{a_j}}
\end{displaymath} -->
<IMG
WIDTH="138" HEIGHT="65"
SRC="img270.gif"
ALT="\begin{displaymath}J(a)_{ij}~={\partial {r^{(i)}} \over \partial{a_j}}\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
and <I>B</I>(<I>a</I>) is
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
B(a)~=~\sum_i~r^{(i)}(a)~H_i(a)
\end{displaymath} -->
<IMG
WIDTH="250" HEIGHT="61"
SRC="img271.gif"
ALT="\begin{displaymath}B(a)~=~\sum_i~r^{(i)}(a)~H_i(a)\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
with <I>H</I><SUB><I>i</I></SUB>(<I>a</I>), the Hessian matrix of
<!-- MATH: $r^{(i)}(a)$ -->
<I>r</I><SUP>(<I>i</I>)</SUP>(<I>a</I>).
<P>
In the rest of the chapter, all the functions are supposed to be
differentiable if they are applied the derivation operator even when
this condition is not necessary for the convergence of the algorithm.
<P>
A certain number of numerical methods have been developed to solve the
non-linear least squares problem, four have so far been implemented in
MIDAS. A complete description of these algorithms can be found in
[<A
HREF="node146.html#gill:81">1</A>] and [<A
HREF="node146.html#gill:78">3</A>], the present document will only give a
basic introduction.
<P>
<BR><HR>
<!--Table of Child-Links-->
<A NAME="CHILD_LINKS"> </A>
<UL>
<LI><A NAME="tex2html2163"
HREF="node129.html">The Newton-Raphson Method.</A>
<LI><A NAME="tex2html2164"
HREF="node130.html">The Modified Gauss-Newton Method.</A>
<LI><A NAME="tex2html2165"
HREF="node131.html">The Quasi-Newton Method.</A>
<LI><A NAME="tex2html2166"
HREF="node132.html">The Corrected Gauss-Newton No Derivatives.</A>
</UL>
<!--End of Table of Child-Links-->
<HR>
<!--Navigation Panel-->
<A NAME="tex2html2161"
HREF="node129.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2157"
HREF="node127.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2151"
HREF="node127.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2159"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2160"
HREF="node216.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="icons.gif/index_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html2162"
HREF="node129.html">The Newton-Raphson Method.</A>
<B> Up:</B> <A NAME="tex2html2158"
HREF="node127.html">Fitting of Data</A>
<B> Previous:</B> <A NAME="tex2html2152"
HREF="node127.html">Fitting of Data</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-09</I>
</ADDRESS>
</BODY>
</HTML>
