Computational geometry as a tool for studying root-finding methods

Ivan Miodrag Petkovic, Lidija Zoran Rancic


We present an efficient method  from Computational geometry, a branch of computer science devoted to the study of algorithms, for mathematical visualization of a third order root solver.
For  many decades  the quality of iterative methods for solving nonlinear equations were analyzed  only by using numerical experiments. The disadvantage of this approach is the inconvenient fact that convergence behavior  strictly depends on the choice of initial approximations and the structure of functions whose zeros are sought, which often makes the convergence analysis very hard and incomplete. For this reason in this paper we apply dynamic study  of iterative processes relied on basins of attraction, a new and powerful methodology developed at the beginning of the 21th century.
This approach provides graphic visualization of the behavior of convergent sequences and, consequently, offers  considerably better insight into  the quality of  applied root solvers, especially into the domain of convergence. For demonstration, we present dynamic study of one parameter family of Halley's type  introduced in the first part of the paper. Characteristics of this family are discussed by basins of attractions for various values of the involved parameter. Special attention is devoted to clusters of polynomial roots, one of the most difficult problems in the topic. The  analysis of the methods and presentation of basins of attractions are performed by the computer algebra system {\it Mathematica}.


  • There are currently no refbacks.