# Beyond Newton: A New Root-Finding Fixed-Point Iteration for Nonlinear Equations
## 2 Methods and Results  
The basin of attraction for a root \(x^{*}\) is defined as the set of initial guesses from which a given fixed-point iteration converges to \(x^{*}\) (this can be seen as the domain of convergence for initial guesses). Naturally, it is desirable to have a large basin of attraction for the root so that convergence is achieved for a wide range of initial guesses. For convergence we need \(e_{n+1}<e_{n}\), i.e., \(N(\zeta,x_{n})e_{n}<1\) using (4). Thus, size of the basin depends on nonlinearity \(N(\zeta,x_{n})\).  
Figure 1: **(a)** Convergence of the standard [PERSON]’s method (red lines), the Extended Newton method with \(c\in(-50,50)\) (gray lines), and the [PERSON]’s method (blue line) for solving \(e^{x}-500=0\) (solid curves with initial guess \(x_{0}=0\) and dashed curve with initial guess \(x_{0}=3\)). **(b)** (From left) Iterations taken to converge for the standard [PERSON]’s method, the Extended Newton method, and the [PERSON]’s method for solving \(r(x)=e^{x}-H=0\): with \(H=500\) and varying initial guess \(x_{0}\) (top), and with \(x_{0}=0\) and varying \(H=e^{x^{*}}\) (bottom)  
We pose the following question: can we pre-multiply the original equation by a function so that we obtain a larger (or, if possible, infinite) basin of attraction? That is, instead of solving (1), can we solve  
\[\text{Find }x=x^{*}\text{ such that }P(x^{*})r(x^{*})=0, \tag{5}\]  
_still using [PERSON]'s method_? The idea is to choose a \(P(x)\) that decreases the nonlinearity \(N\) and, hence, gives a larger basin of attraction, while retaining at least quadratic convergence close to the root. For (5), the measure of nonlinearity is \(N(\zeta,x_{n})=\left|\left[P(x)r(x)\right]^{\prime\prime}\big{|}_{x=\zeta}/ \big{[}P(x)r(x)\big{]}^{\prime}\big{|}_{x=x_{n}}\right|\). To minimize \(N\), we equate \(N=0\), which gives  
\[P(x)=\alpha\frac{x-c}{r(x)}, \tag{6}\]  
for arbitrary integration constants \(\alpha\) and \(c\). We note that if \(P(x)\) is not a function of \(x\), we do not change the nonlinearity of the problem, and this case would fall under the purview of the highly developed field of linear preconditioning. Thus, without loss of generality, we set \(\alpha=1\). However, multiplying the above form of \(P(x)\) by \(r(x)\) has two problems: it (1) eliminates the original root \(x=x^{*}\) and (2) introduces a new root \(x=c\). To solve these problems, we add another constant \(\kappa\
eq 0\) in the denominator of \(P(x)\) in (6), \(P(x)=\frac{x-c}{r(x)+\kappa}\). This avoids the elimination of the \(x^{*}\) root. In addition, we eliminate the undesirable new root \(x=c\) by choosing \(\kappa\) such that \(r(c)+\kappa=0\), i.e., \(\kappa=-r(c)\) and \(P(x)=\frac{x-c}{r(x)-r(c)}\). Thus, instead of applying [PERSON]'s method to \(r(x)=0\), if we apply [PERSON]'s method to our new equation  
\[\frac{x-c}{r(x)-r(c)}r(x)=0, \tag{7}\]  
we get a new fixed-point iteration  
\[x_{n+1}=x_{n}+\Delta x^{\text{EN}}=x_{n}-\frac{(x_{n}-c)r(x_{n})}{r(x_{n})-(x _{n}-c)r^{\prime}(x_{n})\frac{r(c)}{r(x_{n})-r(c)}}. \tag{8}\]  
The superscript \({}^{\text{EN}}\) denotes \"Extended Newton\" method.