<!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 Newton-Raphson Method.</TITLE>
<META NAME="description" CONTENT="The Newton-Raphson 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="node130.html">
<LINK REL="previous" HREF="node128.html">
<LINK REL="up" HREF="node128.html">
<LINK REL="next" HREF="node130.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html2177"
HREF="node130.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2173"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2167"
HREF="node128.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2175"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2176"
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="tex2html2178"
HREF="node130.html">The Modified Gauss-Newton Method.</A>
<B> Up:</B> <A NAME="tex2html2174"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2168"
HREF="node128.html">Outline of the Available</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION001311000000000000000">
The Newton-Raphson Method.</A>
</H2>
This is the simplest one.
The necessary condition for the function <IMG
WIDTH="58" HEIGHT="48" ALIGN="MIDDLE" BORDER="0"
SRC="img272.gif"
ALT="$\chi^2(a)$">to have an extremum is that the partial derivatives vanish i.e.
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
\sum_{i}~r^{(i)}~{\partial {r^{(i)}} \over \partial{a_j}} = 0
\quad (j=1,\ldots,p)~~
\end{displaymath} -->
<IMG
WIDTH="310" HEIGHT="70"
SRC="img273.gif"
ALT="\begin{displaymath}\sum_{i}~r^{(i)}~{\partial {r^{(i)}} \over \partial{a_j}} = 0
\quad (j=1,\ldots,p)~~\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
or, equivalently,
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
J(a)^T~r(a)~=0~~~.
\end{displaymath} -->
<I>J</I>(<I>a</I>)<SUP><I>T</I></SUP> <I>r</I>(<I>a</I>) =0 .
</DIV>
<BR CLEAR="ALL">
<P></P>
This is usually a system of non-linear equations that, numerically, can
be solved using the Newton-Raphson's method also called in the
one-dimensional case the tangents method.
The Taylor development of the function limited to the first order
is taken around some initial guesses of the parameters. The resulting
linear system
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
J(a^{(k)})^T~J(a^{(k)})~\Delta a^{(k)}~=~-J(a^{(k)})~r(a^{(k)})
\end{displaymath} -->
<IMG
WIDTH="416" HEIGHT="40"
SRC="img274.gif"
ALT="\begin{displaymath}J(a^{(k)})^T~J(a^{(k)})~\Delta a^{(k)}~=~-J(a^{(k)})~r(a^{(k)})\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
gives thus a correction to the solution
and
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{displaymath}
a^{(k+1)}~=~a^{(k)}~+~\gamma~\Delta a^{(k)}
\end{displaymath} -->
<IMG
WIDTH="246" HEIGHT="39"
SRC="img275.gif"
ALT="\begin{displaymath}a^{(k+1)}~=~a^{(k)}~+~\gamma~\Delta a^{(k)}\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
is taken as the new approximation of the optimum. The
relaxation factor <IMG
WIDTH="18" HEIGHT="39" ALIGN="MIDDLE" BORDER="0"
SRC="img276.gif"
ALT="$\gamma$">
is a parameter of the method.
The convergence of the process towards the solution
of the non-linear minimization problem has been proven for locally
convex <IMG
WIDTH="57" HEIGHT="48" ALIGN="MIDDLE" BORDER="0"
SRC="img277.gif"
ALT="$\chi^2(a)$">
or under other assumptions impossible to detail here.
These conditions are not generally fulfilled in real problems. Moreover,
the algorithm ignores the second order conditions and therefore, may
end on a saddle point or never converge.
Two different relaxation factors may lead to different solutions or
one may give convergence and the other one not.
No general rule can be given for the choice of a good relaxation factor.
<HR>
<!--Navigation Panel-->
<A NAME="tex2html2177"
HREF="node130.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html2173"
HREF="node128.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html2167"
HREF="node128.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html2175"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<A NAME="tex2html2176"
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="tex2html2178"
HREF="node130.html">The Modified Gauss-Newton Method.</A>
<B> Up:</B> <A NAME="tex2html2174"
HREF="node128.html">Outline of the Available</A>
<B> Previous:</B> <A NAME="tex2html2168"
HREF="node128.html">Outline of the Available</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-09</I>
</ADDRESS>
</BODY>
</HTML>
