Computational geometry as a tool for studying root-finding methods


Ivan Petković, Lidija Z Rančić




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 Mathematica.