% formatted on 970304 by morris
\documentstyle{article}
\setcounter{page}{2}
\textheight 9.5in
\textwidth 5.75in
\voffset -1in
\hoffset -0.5in

\begin{document}
%\documentstyle[12pt]{llncs}

\title{NEWTON AND RAYLEIGH QUOTIENT METHODS\\ 
	FOR TOTAL LEAST SQUARES PROBLEMS}

\author{{\AA}ke Bj\"orck \\
Department of Mathematics, Link\"oping University\\
S-581~83, Link\"oping, Sweden. e-mail: akbjo@math.liu.se}
\date{}
\maketitle


  Consider the total least squares (TLS) problems $\min_{E,r}\|(E,r)\|_F$ subject 
to $(A+E)x=b+r$. We discuss methods for solving large scale TLS problems based on the
observation by G. H. Golub, that the TLS solution $x_{TLS}$ satisfies the deregularized 
normal equations $(A^TA-\sigma_{n+1}^2I)x_{TLS}=A^Tb$, where $\sigma_{n+1}=\|(E,r)\|_F$.  
Together with the equation $\sigma_{n+1}^2=b^T(b-Ax_{TLS})$ the normal equations form 
a nonlinear system, which can be solved by Newton's method. As starting approximation 
the standard least squares solution $x_{LS}$ can be used. 
This method is closely related to Rayleigh quotient iteration, i.e., inverse 
iteration with the Rayleigh quotient shift $\rho(x)=\|b-Ax\|_2/\|(x^T,-1)\|_2$,
applied to a related symmetric eigenvalue problem. Both methods can be generalized 
to multidimensional TLS problems.

\vskip 2truemm
  In each step of either of these methods linear systems of the form 
$(A^TA-\bar\sigma^2I)z=g$ need to be solved, where $\bar\sigma$ denotes the current 
approximation to $\sigma_{n+1}$.
These linear systems can be solved by a preconditioned conjugate gradient method,
using the same preconditioners as developed for the standard least squares problem.
This makes the methods suitable for solving large scale TLS problems. Some
numerical examples will be given.

\end{document}


