A quasi cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm (Q1339331)

The author describes a method of approximating the basins of attraction for Newton's method (or more generally, fixed point iteration) by means of mappings of cells \(\Omega_ j\), \(j= 1\cdots N_ C\) which partition a cell \(\Omega\subset \mathbb{R}^ N\). The sink cell is defined as the set of all points outside of \(\Omega\). Consider a dynamical system governed by a map \({\mathbf g}: \mathbb{R}^ N\to\mathbb{R}^ N\). The ``point-to-point'' map \({\mathbf g}\) induces a ``cell- to-cell'' map \({\mathbf C}\) as follows: the image of a cell \({\mathbf z}\) is the cell to which the image of the central point of \({\mathbf z}\) is mapped by \({\mathbf g}\). Equivalently, a map of the set \(\{0\cdots N_ C\}\) into itself is defined. The evolution is then described by the iteration of the cell function: \({\mathbf z}(n+1)= {\mathbf C}({\mathbf z}(n))\). A cell \({\mathbf z}^*\) such that \({\mathbf z}^*= {\mathbf C}({\mathbf z}^*)\) is called an equilibrium cell. A periodic motion of period \(k\) is a sequence of \(k\) cells \({\mathbf z}^*(l)\), \(l= 1,\dots, k\) such that \({\mathbf z}^*(m+1)= {\mathbf C}^ m({\mathbf z}^*(1))\), \(m= 1\cdots k-1\), and \({\mathbf C}^ k({\mathbf z}^*(1))= {\mathbf z}^*(1)\). Every cell \({\mathbf z}^*(l)\) of the sequence is called a periodic cell of period \(k\). Now it is evident that every cell \(\Omega_ j\), \(j= 1\cdots N_ C\) is either mapped to the sink cell or to a periodic cell after at most \(N_ C\) iterations. The standard experimental approach to studying Newton's method (and fixed point iterations) is to choose a mesh of points in \(\Omega\) and iterate with \({\mathbf g}\) until either a convergence criterion is met or a chosen maximum number of iterations is exceeded. The present method cuts down the computational cost of approximation (at least crudely) the basins of attraction of the fixed point iteration. The author discusses steps for improving the approximation of the boundaries and for implementing the complex case also in polar coordinates.