<!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>The Modified Gauss-Newton Method.</TITLE>
<META NAME="description" CONTENT="The Modified Gauss-Newton Method.">
<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="node131.html">
<LINK REL="previous" HREF="node129.html">
<LINK REL="up" HREF="node128.html">
<LINK REL="next" HREF="node131.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html2189"
HREF="node131.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2185"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2179"
HREF="node129.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2187"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2188"
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="tex2html2190"
HREF="node131.html">The Quasi-Newton Method.</A>
<B> Up:</B> <A NAME="tex2html2186"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2180"
HREF="node129.html">The Newton-Raphson Method.</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION001312000000000000000">
The Modified Gauss-Newton Method.</A>
</H2>
From a first guess of the
parameters <I>a</I><SUP>(1)</SUP>, a sequence
<!-- MATH: $a^{(2)},a^{(3)},\ldots$ -->
<IMG
WIDTH="119" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img278.gif"
ALT="$a^{(2)},a^{(3)},\ldots $">
is generated
and is intended to converge to a local minimum of <IMG
WIDTH="57" HEIGHT="48" ALIGN="MIDDLE" BORDER="0"
SRC="img279.gif"
ALT="$\chi^2(a)$">.
At each iteration, one computes
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
a^{(k+1)}~=~a^{(k)}~+\alpha^{(k)}~d^{(k)}
\end{displaymath} -->
<IMG
WIDTH="245" HEIGHT="36"
SRC="img280.gif"
ALT="\begin{displaymath}a^{(k+1)}~=~a^{(k)}~+\alpha^{(k)}~d^{(k)}\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
where <I>d</I><SUP>(<I>k</I>)</SUP> is a certain descent direction and
<!-- MATH: $\alpha^{(k)}$ -->
<IMG
WIDTH="42" HEIGHT="27" ALIGN="BOTTOM" BORDER="0"
SRC="img281.gif"
ALT="$\alpha^{(k)}$">
is a real
coefficient which is chosen such that
<!-- MATH: $\chi^2(a^{(k)}+\alpha^{(k)}~d^{(k)})$ -->
<IMG
WIDTH="187" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img282.gif"
ALT="$\chi^2(a^{(k)}+\alpha^{(k)}~d^{(k)})$">
is approximately minimum. The
direction <I>d</I><SUP>(<I>k</I>)</SUP> is ideally the solution of the Newton equation
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
H(a^{(k)})~d^{(k)}~=~-g(a^{(k)})
\end{displaymath} -->
<I>H</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) <I>d</I><SUP>(<I>k</I>)</SUP> = -<I>g</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)
</DIV>
<BR CLEAR="ALL">
<P></P>
which can also be rewritten
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
[J(a^{(k)})^T~J(a^{(k)})~+~B(a^{(k)})]~d^{(k)}~=~-J(a^{(k)})~r(a^{(k)})~~.
\end{displaymath} -->
[<I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)<SUP><I>T</I></SUP> <I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) + <I>B</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)] <I>d</I><SUP>(<I>k</I>)</SUP> = -<I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) <I>r</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) .
</DIV>
<BR CLEAR="ALL">
<P></P>
Neglecting the second derivatives matrix
<!-- MATH: $B(a^{(k)})$ -->
<I>B</I>(<I>a</I><SUP>(<I>k</I>)</SUP>), we obtain
the ``normal equations'' and the Gauss-Newton direction
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
J(a^{(k)})^T~J(a^{(k)})~d^{(k)}~=~-J(a^{(k)})~r(a^{(k)})
\end{displaymath} -->
<I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)<SUP><I>T</I></SUP> <I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) <I>d</I><SUP>(<I>k</I>)</SUP> = -<I>J</I>(<I>a</I><SUP>(<I>k</I>)</SUP>) <I>r</I>(<I>a</I><SUP>(<I>k</I>)</SUP>)
</DIV>
<BR CLEAR="ALL">
<P></P>
This so-called Gauss-Newton method is intended for problems where
<IMG
WIDTH="73" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img283.gif"
ALT="$\Vert B(a)\Vert$">
is small. If the Jacobian
<I>J</I>(<I>a</I>) is singular or near singular or if <IMG
WIDTH="67" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img284.gif"
ALT="$\Vert r(a)\Vert$">
is very large (the
so-called large residuals problem), the Gauss-Newton equation is not a
good approximation of the normal equations and the convergence is not
guaranteed.
<P>
The algorithm implemented here is a modification
of that Gauss-Newton method, that allows convergence even for
rank deficient Jacobians or for large residuals. The Gauss-Newton
direction is computed in
<!-- MATH: $V_1~=~\Im m~[J(a^{(k)})^T~J(a^{(k)})]$ -->
<IMG
WIDTH="278" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img285.gif"
ALT="$V_1~=~\Im m~[J(a^{(k)})^T~J(a^{(k)})]$">,
the invariant space corresponding to the non-null eigenvalues.
A correction is taken in <I>V</I><SUB>2</SUB>, the orthogonal of <I>V</I><SUB>1</SUB>,
according to the second derivatives if
the decrease of the objective function at the last
iteration is considered too small.
The Hessian matrix is estimated using finite
differences of the gradient.
<P>
This method requires the availability of the derivatives and as
the number of gradient evaluations is almost <I>p</I> at each iteration, it
is recommended for problems with a small number of parameters,
let us say <IMG
WIDTH="83" HEIGHT="39" ALIGN="MIDDLE" BORDER="0"
SRC="img286.gif"
ALT="$p~\leq~10$"><HR>
<!--Navigation Panel-->
<A NAME="tex2html2189"
HREF="node131.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2185"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2179"
HREF="node129.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2187"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2188"
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="tex2html2190"
HREF="node131.html">The Quasi-Newton Method.</A>
<B> Up:</B> <A NAME="tex2html2186"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2180"
HREF="node129.html">The Newton-Raphson Method.</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-09</I>
</ADDRESS>
</BODY>
</HTML>
