Algorithm of Polynomial Factorization and Its Implementation in Maple

В работе предложен алгоритм факторизации Винера - Хопфа скалярных многочленов. Алгоритм, основанный на понятиях индексов и существенных многочленов, позволяет найти факторизационные множители многочлена с гарантированной точностью. Метод использует вычисления с конечными теплицевыми матрицами и дает возможность получить коэффициенты обоих факторизационных факторов одновременно. Рассмотрены вычислительные аспекты алгоритма. Найдена априорная оценка числа обусловленности используемой теплицевой матрицы. Получены формулы для вычисления лорановских коэффициентов с заданной точностью для функций аналитических и не обращающихся в нуль в кольцевой окрестности единичной окружности. Изучена устойчивость факторизационных множителей. Установлены верхние границы точности вычисления факторизационных множителей. Все оценки являются эффективными. Предложенный алгоритм был реализован в компьютерной системе Maple в виде модуля 'PolynomialFactorization'. Численные эксперименты с модулем показали хорошее согласие с теоретическим исследованием.

Ключевые слова

факторизация Винера - Хопфа; полиномиальная факторизация; теплицевы матрицы.

Литература

1. Daniele V.G., Zich R.S. The Wiener-Hopf Method in Electromagnetics. ISMB Series, New Jersey, SciTech Publishing, 2014. DOI: 10.1049/SBEW503E
2. Abrahams I.D. On the Application of the Wiener-Hopf Technique to Problems in Dynamic Elasticity. Wave Motion, 2002, vol. 36, pp. 311-333. DOI: 10.1016/S0165-2125(02)00027-6
3. Lawrie J.B., Abrahams I.D. A Brief Historical Perspective of the Wiener-Hopf Technique. Journal of Engineering Mathematics, 2007, vol. 59, pp. 351-358. DOI: 10.1007/s10665-007-9195-x
4. Clancey K., Gohberg I. Factorization of Matrix Functions and Singular Integral Operators. Basel, Birkauser, 1987.
5. Gohberg I.C., Feldman I.A. Convolution Equations and Projection Methods for Their Solution. Providence, American Mathematical Society, 1974.
6. Rogosin S., Mishuris G. Constructive Methods for Factorization of Matrix-Functions. IMA Journal of Applied Mathematics, 2016, vol. 81, no. 2, pp. 365-391. DOI: 10.1093/imamat/hxv038
7. Kisil A.V. A Constructive Method for an Approximate Solution to Scalar Wiener-Hopf Equations. Proceedings of The Royal Society A Mathematical Physical and Engineering Sciences, 2013, vol. 469, no. 2154, article ID: 20120721. DOI: 10.1098/rspa.2012.0721
8. Gautschi W. On the Condition of Algebraic Equations. Numerische Mathematik, 1973, vol. 21, no. 5, pp. 405-424. DOI:10.1007/BF01436491
9. Uhlig F. Are the Coefficients of a Polynomial Well-Condition Function of Its Roots? Numerische Mathematik, 1992, vol. 61, no. 1, pp. 383-393. DOI: 10.1007/BF01385516
10. Bini D.A., B'ottcher A. Polynomial Factorization through Toeplitz Matrix Computations. Linear Algebra Application, 2003, vol. 366, pp. 25-37.
11. Boyd D.W. Two Sharp Inequalities for the Norm of a Factor of a Polynomials. Mathematika, 1992, vol. 39, no. 2, pp. 341-349. DOI: 10.1112/S0025579300015072
12. Adukov V.M. Generalized Inversion of Block Toeplitz Matrices. Linear Algebra Appliction, 1998, vol. 274, pp. 85-124.
13. Adukov V.M. On Wiener-Hopf Factorization of Scalar Polynomials. 2018. Available at: http://arxiv.org/abs/1806.01646.
14. Gakhov F.D. Boundary Value Problems. N.Y., Dover, 1990.