Iteration Methods for Simultaneous Extraction of a Part of All Roots of Algebraic Equations

Dr. Anton Iliev

March 18, 2003, 2:30 p.m. T 811

The problem of finding the roots of equations arises in solving important theoretical and practical problems, such as characteristic equations of matrices and differential or difference equations. The numerous methods developed for solving such equations fall into two basic categories: methods for individual and simultaneous determination of the roots. Individual roots can be found by various methods. Over the past several decades, methods for simultaneous finding of all roots (SFAR) have been developed. This fact is explained by two reasons: first, these methods are more stable and have wider domains of convergence; second, these methods are well suited for implementation on computers with parallel processing. Historically, it is interesting to note that Weierstrass predicted such methods in 1891. Each method for SFAR admits a Gauss-Seidel modification, which leads to better approximations at every step, but rules out any possibility of parallel determination of the roots. When such parallel method is implemented on a parallel computer, the computations are shared between different processors. The results obtained at each step are exchanged, and the process of finding of roots is accelerated. The task in this lecture is to show how it can build iteration methods with raised speed of convergence and at the same time they give opportunities for simultaneous searching of only one part of all roots (real, complex, lying in given area, satisfying given conditions).