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

basins of attraction convergence dynamical system equilibrium cell fixed point iteration Newton's method periodic cell periodic motion root-finding algorithm

Mathematics Subject Classification ID

Dynamical systems and ergodic theory (37-XX) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

Review text

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A quasi cell mapping approach to the global dynamical analysis of Newton's root-finding algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1339331)