Zeros of Polynomial Equations in the Complex Plane

Source: Dev.to

Abstract

In this article we discuss Laguerre’s algorithm for finding zeros of polynomial equations of degree (n) in the complex plane. We derive a particular case and analyse convergence for simple roots. Examples are verified using an implementation of the algorithm, illustrating some of its virtues and limitations.

Introduction

The problem of finding the zeros of a polynomial of degree (n) has substantially influenced the development of mathematics through the centuries and remains important in both practical and theoretical applications.

Currently, the study of polynomials of the form

[ p(z)=\sum_{i=0}^{n} a_i z^{i}\qquad (1) ]

does not play a central role in mathematics or applied mathematics. In many situations the problems are linearised and solved with linear‑algebra tools and fast Fourier transforms, which may involve the roots of polynomial equations.

Nevertheless, equations of this type are still of interest in some areas of applied mathematics, and algorithms for locating their roots continue to be developed and studied.

As proved by Abel in 1827, for polynomials of degree (\ge 4) there is no formula that yields the exact solutions in radicals; consequently any problem that requires solving such a polynomial must rely on numerical methods.

In the present article we discuss Laguerre’s method in the complex plane and an implementation of it for several types of polynomials.

Theoretical Results

Initial Definitions and Theorems

Definition 1 (order of convergence).
An algorithm has convergence order (\alpha) at a root (\eta) if

[ \lim_{n\to\infty}\frac{|z_{n+1}-\eta|}{|z_n-\eta|^{\alpha}}=C\qquad (2) ]

for some constant (C\neq0).

Definition 2 (global vs. local method).
A numerical method is global if it does not require an initial value sufficiently close to a zero of the polynomial to converge; otherwise it is local.

Theorem 1.
Let (p(z)) be a polynomial of degree (n>1) with complex coefficients. Then (p(z)) has exactly (n) complex roots (counting multiplicities).

Theorem 2.
Let (p(z)) be a normalized polynomial of degree (m>4) and let

[ P={p_i : i\in{1,\dots ,\ell}} ]

be the set of its roots. For an initial point

[ u_0\in\mathbb{C}\setminus P,\qquad p’(u_0)\neq0\ \text{or}\ p”(u_0)\neq0, ]

define the sequence

[ L_p(u_0)=\bigl(u_n\bigr)_{n\in\mathbb{N}} ]

by

[ u_{n+1}=u_n-\frac{m}{,q(u_n)+s(u_n)r(u_n)}\qquad (3) ]

where

[ \begin{aligned} q(z)&=\frac{p’(z)}{p(z)},\ t(z)&=q(z)^2-\frac{p”(z)}{p(z)},\ r(z)&=\sqrt{(m-1)\bigl(mt(z)-q(z)^2\bigr)}, \end{aligned} ]

and

[ s(z)= \begin{cases} ;1, & \text{if } \operatorname{Re}q(z),\operatorname{Re}r(z)+\operatorname{Im}q(z),\operatorname{Im}r(z)\ge0,\[4pt] -1, & \text{otherwise}. \end{cases} ]

The denominator never vanishes: (q(u_n)+s(u_n)r(u_n)\neq0).

If there exists a simple root (p\in P) such that

[ |u_0-p|\le\frac{1}{2m-1}\min_{p_i\in P\setminus{p}}|p-p_i|, ]

then the sequence (L_p(u_0)) converges to (p) and

[ |u_n-p|\le\lambda^{,n},|u_0-p|,\qquad \lambda=\frac{15}{16},\qquad n\in\mathbb{N}\setminus{0}. ]

If all roots of (p(z)) are simple, then in the above inequality the quantity

[ \mu_p=\min_{p_i\in P\setminus{p}}|p-p_i| ]

can be bounded from below by

[ \Bigl(1+\frac{1}{d_0}\max_{1\le j\le\binom{m}{2}}|d_j|\Bigr)^{-\frac12} ]

(continued from the original text).

Implementation Libraries

Using the results from the previous section, the following libraries were created:

Rounding errors are most noticeable in the deflation and evalpoly routines; therefore all calculations are performed with long double precision to mitigate these errors.

Results and Discussion

A series of tests were carried out; the most representative ones are shown in the table below.

• For low‑degree polynomials the algorithm attains remarkable precision – e.g., the square‑root of a number can be approximated to 13 decimal places.
• For roots with multiplicity (\le 10) the algorithm behaves exceptionally well, even though it was not specifically designed for multiple roots.
• Starting from higher degrees, divergence begins to appear. Increasing the maximum number of iterations does not help, because for multiple roots the method converges only linearly and may require an impractically large number of iterations.
• For simple‑root polynomials with degree (n>10) the behaviour improves, yet the last two polynomials in the table illustrate a failure: the algorithm diverged while attempting to compute the final root, finding only 13 of the 14 existing roots.
• As the degree grows substantially, the overall precision deteriorates sharply.

Test Results Table

Conclusion

For a first implementation, the algorithm shows good performance on modest‑size problems. Nevertheless, with additional development time it could be considerably optimised. In its current state the code is not suitable for high‑performance production environments (e.g., Mathematica or MATLAB‑level tasks).

The complete source code is available on GitHub.

References

1. Pan, Y., & Victor, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, 39(2), 187‑220 (1997).
2. Ahlfors, L., Complex Analysis, McGraw‑Hill, 1979.
3. Møller, H., Convergence and visualization of Laguerre’s root‑finding algorithm, 9 January 2015.
4. Acton, S. F., Numerical Methods that Work, The Mathematical Association of America, 1990.
5. Kiusalaas, J., Numerical Methods in Engineering with Python 3, Cambridge University Press, 2013.