# Beyond Newton: A New Root-Finding Fixed-Point Iteration for Nonlinear Equations
## 2 Methods and Results
### Extension to Multiple Unknowns  
Extending to \(m\) unknowns \(x_{i}\) and \(m\) equations \(r_{i}(x_{1},\ldots,x_{m})=0\) for \(i=1,\ldots,m\), our problem is  
\[\mathrm{Find}\ x_{i}=x_{i}^{*}\ \mathrm{such\ that}\ r_{i}(\mathbf{x}^{*})=0\ \forall i=1,\ldots,m, \tag{12}\]  
where all \(m\) unknowns are collectively written as \(\mathbf{x}\). Applying the standard [PERSON]'s method gives us a system of \(m\) linear equations to be solved for step \(\Delta x_{j}^{\mathrm{N}}\)  
\[\sum_{j}r_{i,j}(\mathbf{x})\Delta x_{j}^{\mathrm{N}}=-r_{i}(\mathbf{x}), \tag{13}\]  
where \(r_{i,j}=\partial r_{i}/\partial x_{j}\) and we have dropped the subscript \(n\) to denote the current iteration value of \(\mathbf{x}\) as that is implied. There could be several different ways of extending EN method (7) to vector functions. If it is possible to recognize a subset of the equations that are most nonlinear, one may use Extended Newton method for that subset of equations and standard [PERSON]'s method for the rest. Here, we consider only the case where all equations are transformed. Thus, one straightforward extension is the following modified set of equations:  
\[\frac{(x_{i}-c_{i})r_{i}(\mathbf{x})}{r_{i}(\mathbf{x})-r_{i}(\mathbf{x}_{ci}) }=0 \tag{14}\]  
for chosen values of \(c_{i}\) (\(i=1,\ldots,m\)), and \(\mathbf{x}_{ci}\) is the vector \(\mathbf{x}\) with \(i\)-th element replaced by \(c_{i}\). Applying [PERSON]'s method we get our new system of linear equations  
\[\sum_{j}\Bigg{\{}\delta_{ij}\frac{r_{i}(\mathbf{x})}{r_{i}(\mathbf{x})-r_{i}( \mathbf{x}_{ci})}+\frac{(x_{j}-c_{i})}{[r_{i}(\mathbf{x})-r_{i}(\mathbf{x}_{ ci})]^{2}}\big{[}r_{i,j}(\mathbf{x}_{ci})r_{i}(\mathbf{x})(1-\delta_{ij})-r_{i,j}( \mathbf{x})r_{i}(\mathbf{x}_{ci})\big{]}\Bigg{\}}\Delta x_{j}^{\text{EN}}=- \frac{(x_{i}-c_{i})r_{i}(\mathbf{x})}{r_{i}(\mathbf{x})-r_{i}(\mathbf{x}_{ci} )}, \tag{15}\]  
where \(\delta_{ij}=1\) when \(i=j\) and \(0\) otherwise. For the single unknown case, we have to calculate \(r(c)\) only once and there is no need for computing \(r^{\prime}(c)\). However, in the above extension to multiple unknowns, \(r_{i}(\mathbf{x}_{ci})\) needs to be evaluated at every iteration along with \(r_{i,j}(\mathbf{x}_{ci})\). Thus, the EN method for the case with multiple unknowns leads to a cumbersome set of calculations. On the other hand, extension of the limit case of EN, the [PERSON]'s method (11), to multiple unknowns is simpler:  
\[\sum_{j}\left(r_{i,j}+\frac{1}{2}\sum_{k}r_{i,jk}\Delta x_{k}^{\text{N}} \right)\Delta x_{j}^{\text{H}}=-r_{i}, \tag{16}\]  
where \(\Delta x_{j}^{\text{N}}\) is calculated from (13) and \(r_{i,jk}=\frac{\partial^{2}r_{i}}{\partial x_{j}\partial x_{k}}\). Thus, (13) and (16) can be solved successively. To avoid solving two systems of \(m\) equations and instead obtain only one system of \(m\) equations, we multiply both sides of (16) by \(r_{i,j}\). Using an approximation that \(r_{i,i}r_{i,jk}\approx r_{i,k}r_{i,ji}\) and using (13), we get a simplified expression  
\[\sum_{j}\left(r_{i,i}r_{i,j}-\frac{1}{2}r_{i,ji}r_{i}\right)\Delta x_{j}^{ \text{OH}}=-r_{i}r_{i,i}. \tag{17}\]  
This equation gives us the step \(\Delta x_{j}^{\text{OH}}\) by solving only one system of \(m\) equations, and we call it the quasi-Halley method (QH). In numerical methods, computing the Jacobian \(r_{i,j}\) is common, but calculating another gradient \(r_{i,jk}\) for (16) may not be desirable. However, in (17), we note that if we have an expression for \(r_{i,j}\), \(r_{i,ji}\) can be computed using finite difference in only \(\mathcal{O}(m)\) operations and can be easily parallelized (unlike the iterations of [PERSON]'s method).