# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 4 Examples  
We present three examples to illustrate our algorithm for computing the least squares solution of overdetermined separable equations. Our examples have large \(N\) and small \(n,\ell\), approximating the theoretical characteristic that \(n,\ell=O(1)\) as \(N\to\infty\). Similar results hold if we use much larger \(N\). **Example 1**. : _Consider the least squares solution of the overdetermined system_  
\[A(y)z+b(y)\equiv\left[ \begin{array}{c}\left(A_{1}(y)\right)_{(2k+1)\times(2k+1) }+I_{2k+1}\\ \left(A_{2}(y)\right)_{\ell\times(2k+1)}\end{array} \right]z+\left[ \begin{array} []{c}\left(b_{1}(y)\right)_{(2k+1)\times 1}\\ \left(b_{2}(y)\right)_{\ell\times 1}\end{array} \right]=0, \tag{22}\]  
_where_  
\[A_{1}(y)=\left[ \begin{array}{cccc}-2&1&&\\ 1&-2&1&\\ &\cdots&&\\ &1&-2&1\\ &&1&-2\end{array} \right],\quad b_{1}(y)=0_{(2k+1)\times 1},\]  
\[A_{2}(y)=\left[ \begin{array}{c}e^{T}{}_{k+1}\\ 0\end{array} \right],\quad b_{2}(y)=\left[ \begin{array}{c}-1\\ 0.02\sqrt{\alpha(y,y^{*},\beta)}\end{array} \right],\]  
_with_  
\[\alpha(y,y^{*},\beta)=(y-y^{*})^{2}-(y-y^{*})sin(2(y-y^{*}))-0.5 cos(2(y-y^{*}) )+\beta\]  
_and \(y\in\mathbf{R}\) (thus \(n=1\)), and where \(e_{k+1}\) is the \((k+1)\)-th standard unit vector in \(\mathbf{R}^{2k+1}\). The selected value of \(y^{*}\in\mathbf{R}\) is the value of the exact solution \((y^{*},z^{*})\). Here, \(\ell=2\)._  
The problem can be regarded as a constrained generalized eigenvalue problem. We choose \(n=21\), \(\beta=9.5\), and \(y^{*}=0.25 cos^{2}(\pi/44)\approx 49.1228712506303890\). For the eigenvalues of matrices of the form of \(A_{1}(y)\), see [17]. Beginning with \(y^{(0)}=48\) and using Algorithm 1, we obtain the results in Table 1 for \(y^{(m)},m=1,2,3,4\), which shows quadratic convergence of the method. After \(y^{(4)}\) is obtained, we compute \(z^{(4)}\approx z^{*}\) using (21), where \(z^{*}\in\mathbf{R}^{21}\), \(z^{*}_{j}=sin(j*\pi/22)\), \(j=1,\ldots,21\). We find that \(\|z^{(4)}-z^{*}\|=5.2774\times 10^{-15}\), and the 2-norm of the residual of \(A(y^{(4)})z^{(4)}+b(y^{(4)})\) is \(\approx\)0.06. **Example 2**. : _Consider the least squares solution of the overdetermined system_  
\[A(y)z+b(y)\equiv\left[ \begin{array}{c}A_{1}(y)\\ A_{2}(y)\end{array} \right]z+\left[ \begin{array}{c}b_{1}(y)\\ b_{2}(y)\end{array} \right]=0, \tag{23}\]  
_where_  
\[A_{1}(y)=\left[ \begin{array}{cccc}1&&&\\ 1&1&&\\ &\ddots&\ddots&\\ &&1&1\end{array} \right]_{N\times N},\quad b_{1}(y)=\left[ \begin{array}{c}-1- y_{1}\\ 0\\ \ldots\\ 0\end{array} \right]_{N\times 1},\]  
\[A_{2}(y)=\left[ \begin{array}{cccc}y_{1}&0&0&0&\ldots&0\\ y_{2}&y_{1}&0&0&\ldots&0\\ 0&y_{2}&y_{1}&0&\ldots&0\end{array} \right]_{3\times N},\quad b_{2}(y)=\left[ \begin{array}{c}1-y_{1}+y_{1}^{2}\\ 1+y_{1}-y_{2}+y_{1}y_{2}\\ 2-y_{1}+y_{2}-y_{2}^{2}\end{array} \right].\] \begin{table}
\begin{tabular}{c c c} \hline \(m\) & \(y^{(m)}\) & \(||y^{(m)}-y^{*}||\) \\ \hline
0 & 4.800000000000e+001 & 1.1229e+000 \\
1 & 4.90312546237768e+001 & 9.1617e-002 \\
2 & 4.91243552951534e+001 & 1.4840e-003 \\
3 & 4.91228716369764e+001 & 3.8635e-007 \\
4 & 4.91228712506304e+001 & 2.8422e-014 \\ \hline \end{tabular}
\end{table} 
Table 1: Gauss–Newton type iterations for Example 1. Here, we use \(y=(y_{1},y_{2})\), thus \(n=2\), and \(\ell=3\). We choose \(n=23\). The least squares solution of (23) is \((y^{*})^{T}=[0,0]\). Beginning with \([y^{(0)}]^{T}=[0.1,0.1]\) and using Algorithm 1, we obtain the results in Table 2 for \(y^{(m)},m=1,2,3,4\). These results show the expected quadratic convergence. After \(y^{(4)}\) is obtained, we compute \(z^{(4)}\approx z^{*}\) using (21). Here, \(z^{*}\in\mathbb{R}^{23}\), \(z^{*}_{j}=(-1)^{j+1}\), \(j=1,\ldots,23\), and the exact residual is \(A(y^{*})z^{*}+b(y^{*})=e_{24}+e_{25}+2e_{26}\). We find that \(\|z^{(4)}-z^{*}\|=5.0974\times 10^{-15}\), while 2-norm of the residual of \(A(y^{(4)})z^{(4)}+b(y^{(4)})\) is \(2.4494897427831779\approx\sqrt{6}\).