# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 3 Algorithm  
We now give a detailed Algorithm 1 based on the analysis from the last section.  
```
Algorithm 1: Given the function \(F(y,z)=A(y)z+b(y)\) with a matrix \(A(y)\) that is full rank in a neighborhood of \(y^{*}\), a small positive real number \(\epsilon\), a positive integer \(m_{0}\), and a point \(y^{(0)}\) near the solution \(y^{*}\). For \(m=0,1,2,...,m_{0}\), do steps \((a)\)-\((l)\): (a) Compute the LU factorization (13) of \(A(y^{(m)})\) : \[P(y^{(m)})A(y^{(m)})=L(y^{(m)})U(y^{(m)});\] (b) Form the matrix \(S(y^{(m)})\) and the matrix \(\overline{M}(y^{(m)})\) as in (14); (c) Use (16) and the factorization (18) to form the matrix \(C(y^{(m)})\); (d) Compute \(f(y^{(m)})=C^{T}(y^{(m)})b(y^{(m)})\); (e) Use (11) and (20) to solve for \([C(y^{(m)})]^{\prime}_{j},\ j=1,...,n\); (f) Use (8) to form \(f^{\prime}(y^{(m)})\); (g) Use (12) and (20) to solve for \([C^{T}(y^{(m)})]^{\prime\prime}_{j,k},\ j,k=1,...,n\); (h) Use (9) to find the \((j,k)\)-th entry of \(H_{i}(y^{(m)}),\ i=1,\ldots,\ell\); (i) Form the matrix \([(f^{\prime}(y^{(m)}))^{T}f^{\prime}(y^{(m)})+\Sigma_{i=1}^{\ell}f_{i}(y^{(m) })H_{i}(y^{(m)})]\) for the left-hand side of (6); (j) Form the vector \(-(f^{\prime}(y^{(m)}))^{T}f(y^{(m)})\) for the right side of (6); (k) Compute \(y^{(m+1)}\) by solving (6); (l) If \(||y^{(m+1)}-y^{(m)}||<\epsilon\) stop, output \(y^{*}\approx y^{(m+1)}\) and \(z^{*}\) from (21) using (19) and (20). Otherwise, if \(m<m_{0}\), replace \(m\) by \(m+1\) and go to \((a)\); if \(m=m_{0}\), output that the method fails to obtain \(y^{*}\) within given \(m_{0}\) and \(\epsilon\).
```  
**Algorithm 1**Given the function \(F(y,z)=A(y)z+b(y)\) with a matrix \(A(y)\) that is full rank in a neighborhood of \(y^{*}\), a small positive real number \(\epsilon\), a positive integer \(m_{0}\), and a point \(y^{(0)}\) near the solution \(y^{*}\). For \(m=0,1,2,...,m_{0}\), do steps \((a)\)-\((l)\): (a) Compute the LU factorization (13) of \(A(y^{(m)})\) : \[P(y^{(m)})A(y^{(m)})=L(y^{(m)})U(y^{(m)});\] (b) Form the matrix \(S(y^{(m)})\) and the matrix \(\overline{M}(y^{(m)})\) as in (14); (c) Use (16) and the factorization (18) to form the matrix \(C(y^{(m)})\); (d) Compute \(f(y^{(m)})=C^{T}(y^{(m)})b(y^{(m)})\); (e) Use (11) and (20) to solve for \([C(y^{(m)})]^{\prime}_{j},\ j=1,...,n\); (f) Use (8) to form \(f^{\prime}(y^{(m)})\); (g) Use (12) and (20) to solve for \([C^{T}(y^{(m)})]^{\prime\prime}_{j,k},\ j,k=1,...,n\); (h) Use (9) to find the \((j,k)\)-th entry of \(H_{i}(y^{(m)}),\ i=1,\ldots,\ell\); (i) Form the matrix \([(f^{\prime}(y^{(m)}))^{T}f^{\prime}(y^{(m)})+\Sigma_{i=1}^{\ell}f_{i}(y^{(m)}) H_{i}(y^{(m)})]\) for the left-hand side of (6); (j) Form the vector \(-(f^{\prime}(y^{(m)}))^{T}f(y^{(m)})\) for the right side of (6); (k) Compute \(y^{(m+1)}\) by solving (6); (l) If \(||y^{(m+1)}-y^{(m)}||<\epsilon\) stop, output \(y^{*}\approx y^{(m+1)}\) and \(z^{*}\) from (21) using (19) and (20). Otherwise, if \(m<m_{0}\), replace \(m\) by \(m+1\) and go to \((a)\); if \(m=m_{0}\), output that the method fails to obtain \(y^{*}\) within given \(m_{0}\) and \(\epsilon\). ```  
**Algorithm 2**The algorithm 2  
Note that the cost of solving (6) for \(y^{(m+1)}-y^{(m)}\) is only \(O(1)\) since the matrix involved is only \(\ell\times\ell\) and we assume \(\ell=O(1)\). Thus, the overall cost per iteration remains \(2N^{3}/3+O(N^{2})\), the primary cost being the LU factorization of \(A(y^{(m)})\). The standard Gauss-Newton method, which omits the second derivative terms, omits steps _(g)_ and _(h)_, but the resulting method is no longer quadratically convergent.