% formatted on 970304 by morris
\documentstyle{article}
\setcounter{page}{9}
\textheight 9.5in
\textwidth 5.75in
\voffset -1in
\hoffset -0.55in
%\documentstyle[12pt]{llncs}
%\pagestyle{empty}
\begin{document}
%\pagenumbering{arabic}
%\begin{center}
\title{Efficient Solution of the Jacobian System in Newton's Method
Close to a Root}
%\author{M. Drexler{\inst{1}} and Gene H. Golub\inst{2}}
%\institute{Oxford University Computing Laboratory, Numerical Analysis Group\\
%Wolfson Building, Parks Road, Oxford, OX1 3QD, England
%\and
%Scientific Computing and Computational Mathematics\\
%Stanford University, Stanford CA 94305, USA\\[3ex]
%Presented by M. Drexler}
\author{M. Drexler \\Oxford University Computing Laboratory,
Numerical Analysis Group\\
Wolfson Building, Parks Road, Oxford, OX1 3QD, England
\and
Gene H. Golub \\
Scientific Computing and Computational Mathematics\\
Stanford University, Stanford CA 94305, USA\\[3ex]
Presented by M. Drexler}
\date{}
\maketitle
Newton's Method can be regarded as a nested iteration scheme with the
Newton step as the outer iteration and a linear solve of the Jacobian
system as the inner iteration. We examine the interaction between
these two schemes and derive solution techniques for the linear system
from the properties of the outer Newton iteration. Contrary to inexact
Newton methods, our techniques do not rely on relaxed tolerances for
an iterative linear solve, but rather on computational speedup
achieved by exploiting the properties of the Jacobian update.
\vspace{1ex}
As the Newton iterates approach the solution of a non-linear system,
it can be shown that the corresponding update in the Jacobian varies
in magnitude according to an elementwise non-linearity that can be
measured using a local Lipschitz bound
\begin{eqnarray*}
\left| \left( \left. \frac{\partial f_i}{\partial x_j} \right|_{{\bf
x}^{(k)}} - \left. \frac{\partial f_i}{\partial x_j}
\right|_{{\bf x_*}} \right) \right| \leq \gamma_{ij}^{(k)} \cdot
\| {\bf x}^{(k)} - {\bf x_*} \|, & & 1 \leq i,j \leq n
\end{eqnarray*}
where ${\bf x}^{(k)} \in {\bf R}^n$ is the $k^{th}$ Newton iterate,
${\bf x_*}$ the solution of the non-linear $n$-dimensional system ${\bf f}({\bf
x})={\bf 0}$ and
$\gamma_{ij}^{(k)}$ the elementwise Lipschitz constant in the $k^{th}$
Newton step. For many practical problems, this explains an increasingly
sparse matrix update in the solution vicinity.
\vspace{1ex}
We consider the effects of a sparse Jacobian update on various linear
solvers of the direct and iterative kind. Due to the practical
difficulties in estimating Lipschitz constants, we examine various
empirical alternatives such as drop-tolerance schemes to determine the
most influential elements for the update. Numerical experiments are
presented and it is verified that appropriate treatment of the
Jacobian update increases computation speed substantially while the
convergence properties of Newton's method are preserved.
\end{document}
<---