# An Efficient Algorithm for the Separable Nonlinear Least Squares Problem
## 4 Examples
Our last example arises from a discretization, using the finite element method, of the one-dimensional elliptic interface problem \(-(\beta u_{x})_{x}+2=0\), for \(x\in(0,1)\), where \(\beta=\beta^{-}\) for \(0<x<\alpha\) and \(\beta=\beta^{+}\) for \(\alpha<x<1\). The boundary conditions are \(u(0)=0\) and \(u(1)=1/\beta^{+}+(1/\beta^{-}-1/\beta^{+})a^{2}\), and the interface conditions are \(lim_{x\to\alpha^{-}}u(x)=lim_{x\to\alpha^{+}}u(x)\) and \(lim_{x\to\alpha^{-}}\beta^{-}u_{x}(x)=lim_{x\to\alpha^{+}}\beta^{+}u_{x}(x)\). For more on interface problems, see [18]. In this discretization, the slopes of the basis tent functions on either side of the interface \(x=\alpha\) are modified from \(-1/h\) and \(1/h\) to \(-s_{1}\), \(-s_{2}\) and \(s_{1}\), \(s_{2}\) on the respective line segments. In our setting, \(\beta^{-}\) and \(s_{2}\) are given, and \((y_{1},y_{2})=(s_{1},\beta^{+})^{T}\) represent the nonlinear variables. **Example 3**. : _Consider the least squares solution of the overdetermined system_  
\[A(y)z+b(y)=0, \tag{24}\]  
_where the \(N\times(N+3)\) matrix \(A(y)\) is defined as_  
\[A(y)\equiv\left[ \begin{array}{cccc}\frac{\beta^{-}}{h}F_{k-1}&-\frac{\beta^ {-}}{h}e_{k-1}&0_{(k-1)\times 1}&0_{(k-1)\times(N-k-1)}\\ -\frac{\beta^{-}}{h}e_{k-1}^{T}&\frac{\beta^{-}}{h}+\beta^{-}y_{1}&-\beta^{-} y_{1}&0_{1\times(N-k-1)}\\ 0_{1\times(k-1)}&-s_{2}y_{2}&\frac{y_{2}}{h}+s_{2}y_{2}&-\frac{y_{2}}{h}e_{1}^{T }\\ 0_{(N-k-2)\times(k-1)}&0_{(N-k-2)\times 1}&-\frac{y_{2}}{h}e_{1}&\frac{y_{2}}{h}F_{N-k-1} \\ 0_{1\times(k-1)}&a_{N+1,k}(y_{1})&0&0_{1\times(N-k-1)}\\ 0_{1\times(k-1)}&0&\beta^{-}y_{1}-s_{2}y_{2}&0_{1\times(N-k-1)}\\ 0_{1\times(k-1)}&0&0&0_{1\times(N-k-1)}\end{array} \right],\]  
_with \(a_{N+1,k}(y_{1})=(\alpha-x_{k})y_{1}+(x_{k+1}-\alpha)s_{2}-1\) and_  
\[b(y)\equiv\left[ \begin{array}{c}2 hE_{(k-1)\times 1}\\ 2h+(\alpha-x_{k})-y_{1}(\alpha-x_{k})^{2}-(x_{k+1}-\alpha)+s_{2}(x_{k+1}- \alpha)^{2}\\ 2h-(\alpha-x_{k})+y_{1}(\alpha-x_{k})^{2}+(x_{k+1}-\alpha)-s_{2}(x_{k+1}- \alpha)^{2}\\ 2 hE_{(N-k-1)\times 1}-\left[(1-\alpha^{2})/h+(\alpha^{2}/h)y_{2}/\beta^{-} \right]e_{N-k-1}\\ 0\\ 0\\ (a_{N+1,k}(y))^{2}+(\beta_{1}y_{1}-s_{2}y_{2})^{2}+\gamma_{3}{}^{2}\end{array} \right],\] \begin{table}
\begin{tabular}{c c c c} \hline \(m\) & \(y_{1}^{(m)}-y_{1}^{*}\) & \(y_{2}^{(m)}-y_{2}^{*}\) & \(||y^{(m)}-y^{*}||\) \\ \hline
0 & \(1.0000\)e\(-\)001 & \(1.0000\)e\(-\)001 & \(1.4142\)e\(-\)001 \\
1 & \(-3.2975\)e\(-\)002 & \(-1.7299\)e\(-\)002 & \(3.7238\)e\(-\)002 \\
2 & \(8.5227\)e\(-\)004 & \(3.5533\)e\(-\)004 & \(9.2338\)e\(-\)004 \\
3 & \(-1.5227\)e\(-\)008 & \(-6.1721\)e\(-\)009 & \(1.6890\)e\(-\)008 \\
4 & \(-4.3532\)e\(-\)016 & \(-1.8608\)e\(-\)016 & \(4.7342\)e\(-\)016 \\ \hline \end{tabular}
\end{table} 
Table 2: Gauss–Newton type iterations for Example 2. _where \(h=1/(N+1)\) and \(x_{j}=jh\), \(x_{k}<\alpha<x_{k+1}\), and the square matrices \(F\) are tridiagonal of the form_  
\[\left[ \begin{array}{cccc}2&-1&&&\\ -1&2&-1&\\ &\ldots&&&\\ &-1&2&-1\\ &&&-1&2\end{array} \right],\]  
_the vectors \(E\) have all entries one, \(e_{j}\) are the \(j\)th standard unit vectors, and_  
\[\gamma_{1}=\frac{1-(x_{k+1}-\alpha)s_{2}}{\alpha-x_{k}},\quad\gamma_{2}=\frac {[1-(x_{k+1}-\alpha)s_{2}]\beta^{-}}{(\alpha-x_{k})s_{2}}. \tag{25}\]  
The exact least squares solution is \(y^{*}=(\gamma_{1},\gamma_{2})^{T}\). We use \(n=39\), \(k=26\), \(\ell=3\), \(n=2\), \(\beta^{-}=1\), \(s_{2}=8\), \(\alpha=2/3\) and \(\gamma_{3}=4.775\pi\). Using the Algorithm 1 with \(y^{(0)}=(56.5,7.2)^{T}\), we obtain the results in Table 3 for \(y^{(m)},m=1,2,3,4\), which shows quadratic convergence of the method. After \(y^{(4)}\) is obtained, we obtain \(z^{(4)}\) using (21). Here, \(z_{j}^{*}=(jh)^{2}/\beta^{-},j=1,2,...,k\) and \(z_{j}^{*}=(jh)^{2}/\gamma_{2}+(1/\beta^{-}-1/\gamma_{2})a^{2},j=k+1,...,N\), and the exact residual is \(A(y^{*})z^{*}+b(y^{*})=\gamma_{3}^{2}e_{N+3}\).