Modified of Roots Finding Algorithm of High Degree Polynomials

Bandung Arry Sanjoyo, Mahmud Yunus, Nurul Hidayat

Abstract


Although the Durand-Kerner method is widely used across various fields of computer science, especially in numerical computing, it continues to encounter challenges in locating roots of high-degree polynomials, such as issues with accuracies of roots of the polynomial zeros. Our initial tests and observations on several methods for finding polynomial roots revealed that the roots' accuracy starts to degrade noticeably for polynomials where the degree exceeds 10. Based on considerations of algebraic concepts involving polynomial vector spaces, we introduce an improvement of the Durand-Kerner algorithm aimed at improving root precision. This approach includes targeted refinements in coefficient evaluation, identification of root types, and iterative polishing techniques. We also conducted a comparative evaluation to assess its effectiveness against the original Durand Kerner method and MATLAB's roots() function. Overall, the enhanced algorithm delivers superior accuracy for complex roots—particularly in cases involving multiple zero or integer roots—outperforming both benchmarks, but its execution time increases substantially with polynomial degree.

Keywords


high-degree polynomial zeros,;Durand-Kerner algorithm; polynomial root-finding; numerical stability

Full Text:

PDF

References


Aberth, O., 1973a. Iteration Methods for Finding all Zeros of a Polynomial Simultaneously. Math. Comput., 122 27, 339–344.

Aberth, O., 1973b. Iteration Methods for Finding all Zeros of a Polynomial Simultaneously. Math. Comput. 27, 339–344.

Al-Swaftah, A., Burqan, A., Khandaqji, M., 2023. Estimations of the Bounds for the Zeros of Polynomials Using Matrices, in: Zeidan, D., Cortés, J.C., Burqan, A., Qazza, A., Merker, J., Gharib, G. (Eds.), Mathematics and Computation. Springer Nature, Singapore, pp. 25–37. https://doi.org/10.1007/978-981-99-0447-1_3

Batra, P., 1998. Improvement of a convergence condition for the Durand-Kemer iteration. J. Comput. Appl. Math. 96, 117–125.

Cameron, T.R., 2019. An effective implementation of a modified Laguerre method for the roots of a polynomial. Numer. Algorithms 82, 1065–1084. https://doi.org/10.1007/s11075-018-0641-9

Corless, R.M., Sevyeri, L.R., 2020. The Runge Example for Interpolation and Wilkinson’s Examples for Rootfinding. SIAM Rev. 62, 231–243. https://doi.org/10.1137/18M1181985

Deren, W.,Fengguang, Z., 1991. On the determination of the safe initial approximation for the Durand-Kerner algorithm. J. Comput. Appl. Math. 38, 447–456. https://doi.org/10.1016/0377-0427(91)90188-P

Gallian, J.A., 2020. Contemporary abstract algebra, Tenth edition. ed. Chapman & Hall/CRC, Boca Raton.

Guggenheimer, H., 1986. Initial approximations in Durand-Kerner’s root finding method. BIT 26, 537–539. https://doi.org/10.1007/BF01935059

Hall, F.J., Marsli, R.M., Marsli, R.M., 2025. An application of Gelfand’s formula in approximating the roots of polynomials. https://doi.org/10.48550/arXiv.2505.03753

Han, D., 2000. THE CONVERGENCE OF DURAND-KERNER METHOD FOR SIMULTANEOUSLY FINDING ALL ZEROS OF THE POLYNOMIAL. J. Comput. Math. 18, 567–570.

Imbach, R., Pan, V.Y., Yap, C., Kotsireas, I.S., Zaderman, V., 2019. Root-Finding with Implicit Deflation, in: England, M., Koepf, W., Sadykov, T.M., Seiler, W.M., Vorozhtsov, E.V. (Eds.), Computer Algebra in Scientific Computing. Springer International Publishing, Cham, pp. 236–245. https://doi.org/10.1007/978-3-030-26831 2_16

Jain, V.K., 1990a. On Cauchy’s bound for zeros of a polynomial. Approx. Theory Its Appl. 6, 18–24. https://doi.org/10.1007/BF02836305

Jain, V.K., 1990b. On Cauchy’s bound for zeros of a polynomial. Approx. Theory Its Appl. 6, 18–24. https://doi.org/10.1007/BF02836305

Kan, J. van, Segal, G., Vermolen, F., 2023. Numerical Methods in Scientific Computing. TU Delft OPEN Publishing. Khomovsky, D.I., 2020. On using symmetric polynomials for constructing root finding methods. Math. Comput. 89, 2321–2331. https://doi.org/10.1090/mcom/3531 Kjellberg, G., 1984. Two observations on Durand-Kerner’s root-finding method. BIT Numer. Math. 24, 556–559. https://doi.org/10.1007/BF01934913

Liu, B., Yang, Y., Yu, M., 2024. Enhancing Numerical Stability in Multiport Network Synthesis with Modified DK Method, in: 2024 IEEE International Microwave Filter Workshop (IMFW). Presented at the 2024 IEEE International Microwave Filter Workshop (IMFW), IEEE, Cocoa Beach, FL, USA, pp. 170–172. https://doi.org/10.1109/IMFW59690.2024.10477159

Madsen, K., 1973. A root-finding algorithm based on Newton’s method. BIT Numer. Math. 13, 71–75.

Marcheva, P.I., 2023. Fixed points and convergence of iteration methods for simultaneous approximation of polynomial zeros. Univversity Of Plovdiv “Paisii Hilendarski,” Plodiv.

Marcheva, P.I., Ivanov, S.I., 2022. On the semilocal convergence of a modified weierstrass method for the simultaneous computation of polynomial zeros. Presented at the INTERNATIONAL CONFERENCE OF NUMERICAL ANALYSIS AND APPLIED MATHEMATICS ICNAAM 2020, Rhodes, Greece, p. 420012. https://doi.org/10.1063/5.0082007

Marcheva, P.I., Ivanov, S.I., 2020. Convergence Analysis of a Modified Weierstrass Method for the Simultaneous Determination of Polynomial Zeros. Symmetry 12, 1408. https://doi.org/10.3390/sym12091408

Milovanović, G.V., Mir, A., Ahmad, A., 2022. On the zeros of a quaternionic polynomial with restricted coefficients. Linear Algebra Its Appl. 653, 231–245. https://doi.org/10.1016/j.laa.2022.08.010 Orchard, H.J., 1989. The Laguerre method for finding the zeros of polynomials. IEEE Trans. Circuits Syst. 36, 1377–1381. https://doi.org/10.1109/31.41294 Pan, V.Y., 2022a. New Progress in Classic Area: Polynomial Root-squaring and Root-finding. https://doi.org/10.48550/arXiv.2206.01727

Pan, V.Y., 2022b. New Progress in Classic Area: Polynomial Root-squaring and Root-finding. https://doi.org/10.48550/arXiv.2206.01727

Pan, V.Y., 1997. Solving a Polynomial Equation: Some History and Recent Progress. SIAM Rev. 39, 187–220. https://doi.org/10.1137/S0036144595288554

Reinke, B., Schleicher, D., Stoll, M., 2023a. The Weierstrass–Durand–Kerner root finder is not generally convergent. Math. Comput. 92, 839–866. https://doi.org/10.1090/mcom/3783

Reinke, B., Schleicher, D., Stoll, M., 2023b. The Weierstrass–Durand–Kerner root finder is not generally convergent. Math. Comput. 92, 839–866. https://doi.org/10.1090/mcom/3783

Sanjoyo, B., Yunus, M., Hidayat, N., 2025. A New Initial Approximation Bound in the Durand Kerner Algorithm for Finding Polynomial Zeros. Presented at the the 9th International Conference on Mathematics: Pure, Applied and Computation, ICoMPAC 2025, Surabaya.

Shams, M., Kausar, N., Araci, S., Oros, G.I., 2023a. Numerical scheme for estimating all roots of non-linear equations with applications. AIMS Math. 8, 23603–23620. https://doi.org/10.3934/math.20231200

Shams, M., Kausar, N., Araci, S., Oros, G.I., 2023b. Numerical scheme for estimating all roots of non-linear equations with applications. AIMS Math. 8, 23603–23620. https://doi.org/10.3934/math.20231200

Shams, M., Rafiq, N., Kausar, N., Agarwal, P., Park, C., Momani, S., 2021. Efficient iterative methods for finding simultaneously all the multiple roots of polynomial equation. Adv. Differ. Equ. 2021, 495. https://doi.org/10.1186/s13662-021-03649-6 Numerical

Tassaddiq, A., Qureshi, S., Soomro, A., Hincal, E., Baleanu, D., Shaikh, A.A., 2021. A New Three-Step Root Finding Method and Its Fractal Global Behavior. Fractal Fract. 5, 204. https://doi.org/10.3390/fractalfract5040204

Wilkinson, J.H., 1959. The evaluation of the zeros of ill-conditioned polynomials. Part II. Numer. Math. 1, 167 180. https://doi.org/10.1007/BF01386382




DOI: https://doi.org/10.18860/cauchy.v10i2.37278

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 Bandung Arry Sanjoyo, Mahmud Yunus, Nurul Hidayat, Nurul Hidayat

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Gajayana Street 50 Malang, East Java, Indonesia 65144
Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id

Creative Commons License
CAUCHY: Jurnal Matematika Murni dan Aplikasi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.