В.Г.Потемкин "Пакет прикладных программ по решению систем нелинейных полиномиальных уравнений"

Решение систем нелинейных полиномиальных уравнений (СНПУ) – это проблема, с которой часто сталкиваются исследователи при решении уравнений в частных производных, алгебраической геометрии, решении задач оптимизации. Отсутствие единого подхода к решению таких задач приводило к созданию многочисленных решателей, в том числе и в рамках известных систем Maple, Mathematica. Особенность таких решателей заключается в том, что в них всегда включается некоторый итеративный алгоритм локального типа. Мы ставили целью построить строго алгебраический алгоритм глобального типа, гарантирующий нахождение всех действительных и комплексных решений СНПУ.
Не ограничивая общности, будем рассматривать СНПУ с двумя переменными. Определим класс СНПУ2 как систему из p уравнений следующего вида

В настоящее время существует два подхода к решению таких систем: символьный подход, основанный на теории идеалов и вычислении базисов Гребнера для отыскания решений в аналитической форме [4], и численный подход, основанный на решении системы спектральных для прямоугольных пучков матриц [1-3]. Рассмотрим схемы, поясняющие эти подходы.

Спектральный метод
Схема смешанного символьно-числового алгоритма
Примеры решения задач в среде MATLAB
Реализация СНПУ2 в виде GUI-интерфейса
Литература

Спектральный метод

;

;

где x, y – векторы алгебраической структуры; [x y] – произведение Кронекера;
N = lx*ly, l_x = s_x +1, l_y = s_y + 1; p – число уравнений СНПУ2.

Теоретические основы.

Пусть и Тогда можно найти такой вектор , чтобы выполнялось условие .

Лемма: Произведение Кронекера двух векторов алгебраической структуры всегда можно преобразовать к следующей форме
.

Как следствие, в матрице Q могут быть выделены соответствующие подматрицы, которые удовлетворяют следующему соотношению:

Это порождает соотношения вида , из которых формируется спектральная задача по переменной x

Аналогично формируется спектральная задача по переменной y

Должно также выполняться условие

Последние три соотношения формируют систему спектральных задач

где a_x, b_x, a_y, b_y – прямоугольные матрицы;
Rx(x), Ry(y) – матрицы обобщенных собственных векторов.

Схема смешанного символьно-числового алгоритма

Опыт решения практических задач [6, 8-9, 12-13] показал, что применение только спектрального метода недостаточно для решения многих типов задач. Причина заключается в том, что структура идеала, соответствующего исходной СНПУ, обладает тем свойством, что степень переменных и число уравнений могут превышать начальные. Поэтому для решения СНПУ общего вида предлагается применять смешанную схему

Примеры решения задач в среде MATLAB

Плохо обусловленная задача.

F = [x^5 - y^3*x^3 + a,  (1+a)*x^2 - y^4]

tdeg:

GB = [x^7 - (a+1)^3*x^5 + x^2*a + y^3*a + a*(1+a)*y^2 + a*(1+a)^2*y,
y*x^5 - (1+a)*x^5 + y*a, -x^5 + y^3*x^3 - a, -x^2*(1+a)*+ y^4]

plex:

GB = [y^12 - (1+a)*y^11 + a*(a+1)^3*x,
y^20 - y^19*(a+1)*2 + y^18*(a+1)^2 – a^2*(a+1)^5]

[ Nl Nr N0 Ni ]

Nxf = 2 2 2 3

sf = 5 4

Nxtdeg = 0 0 1 3

sg = 7 4

На рис. 1 показан профиль числа действительных решений с уровнями 0-2-4-5-4-2-4, а также график интегральной точности в зависимости от параметра a решаемой СНПУ2.

Рис. 1

Вычисление особых точек для кривой со случайными коэффициентами [6].

f1 = x^5-x^2*y^3+x*y^4-x^4+x*y^3-y^4+x^3+x^2*y+x*y^2-2*x^2-y^2+x;
f2 = diff(f1,y);
F = [f1, f2];

Геометрические образы этих кривых и точки, соответствующие решениям, показаны на рис. 2, а.

а

б

Рис. 2

На рис. 2,б показаны все действительные и комплексные решения СНПУ, причем действительные решения обозначены кружками и соответствуют парам {x, y}, а комплексные решения, отмеченные крестиками, выведены комплексно-сопряженными парами. Не трудно убедиться, что полное число решений для этой СНПУ равно 16.

Решение уравнений в частных производных.

Рассматриваются уравнения многокомпонентной диффузии для случая трех компонентов [9].

СНПУ3:

На рис. 3, а показаны концентрации компонентов по радиусу разделительного аппарата, а на рис. 3, б погрешность решения, не превышающая значения 2е-6, что для данной задачи характеризует высокую точность определения концентраций, поскольку кривые соответствуют двойному экспоненциальному росту. По оси абсцисс отложен безразмерный радиус.

Рис. 3

Реализация СНПУ2 в виде GUI-интерфейса

На рис. 4 показана реализация решателя СНПУ2 в виде графического интерфейса пользователя в среде MATLAB 6.

Рис. 4

Он предназначен для решения СНПУ с двумя переменными и одним параметром. Решения представляются как в графической, так и в числовой форме с указанием точности и времени вычислений. В процессе работы пользователь может изменять значения параметра a, а также структуру уравнений. Решатель использует разработанный авторами ППП SNАE2, который выполняет числовые расчеты, опираясь на RGSVD-алгоритм [5], который позволяет определять структуру Кронекера прямоугольных пучков матриц. Точность решений, обеспечиваемая пакетом, находится в пределах 10-6 – 10-14 и контролируется в процессе решения.

Решатель функционирует в среде MATLAB 5.3, 6 совместно с ППП Extended Symbolic Toolbox на платформах Windows, UNIX.

ППП SNAE2, реализующий базовые операции спектрального метода, функционирует в среде MATLAB без использования ППП Extended Symbolic Toolbox и может быть реализован либо в виде приложения времени исполнения (Run-time Application), либо в виде независимо исполняемого приложения (Stand-alone Application) [14, 15].

Решатель СНПУ2 предназначен для специалистов в области решения уравнений в частных производных, смешанных дифференциально-алгебраических уравнений, алгебраической геометрии, прикладных математиков и инженеров, а также студентов различных учебных заведений – от университетов до школы, использующих в своих расчетах системы нелинейных полиномиальных уравнений.

Литература

1. Kronecker L.  Algebraische Reduktion der Scharen bilinearer Formen. Sitz.-Ber. Akad. Wiss. Phys.-Math. Klasse. - Berlin, 1890. S.763-776.
2. Кублановская В. Н. О связи спектральной задачи для линейных пучков матриц с некоторыми задачами алгебры. Записки научных семинаров ЛОМИ "Численные методы и вопросы организации вычислений". – Л.:, 1978, 80, с. 98-116.
3. Matrix Pencils. Edited by Kagstrom B., Ruhe A. Lecture Notes in Mathematics, 973, Berlin: Springer-Verlag, 1983.
4. B. Buchberger. Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory, Multidimensional Systems Theory (N.K. Bose ed.), D. Reidel Publ. Comp., 1985, pp. 184-232.
5. Kagstrom B. RGSVD - An Algorithm for Computing the Kronecker Structure and Reducing Subspaces of Singular A-l B Pencils. SIAM J. Sci. Stat. Comput., 1986, 7(1), pp.185-211.
6. Cellini P., Gianni P., Traverso C.  Algorithms for the Shape of Semialgebraic Sets. A New Approach. AAECC-9: Applied Algebra, Algebraic Algorithms and Error-Correcting codes. Lecture Notes in Computer Science, 539, Berlin: Springer-Verlag, 1991, pp. 1-18.
7. Stetter H. J. Multivariate Polynomial Equations as Matrix Eigenproblems. In: Contributions in Numerical Mathematics. World Scientific Series in Applicable Analysis, 1993, 2, pp. 355-371.
8. Borisevich V.D., Potemkin V.G. Direct method for SNAE solving in modeling of gas flow in centrifuge, 4th Workshop Proc. "Separation Phenomena in Liquids and Gases," August, 19-23, 1994, Tsinghua University, Beijing, P.R. China, pp. 115-127.
9. Potemkin V.G., Borisevich V.D., Yupatov S.V. Direct method of solving finite difference nonlinear equations for multicomponent diffusion in a gas centrifuge, 5th Workshop Proc. "Separation Phenomena in Liquids and Gases," September, 22-26, 1996, Iguassu Falls, Brazil, pp. 49-65.
10. В.Д.Борисевич, В.Г.Потемкин, С.П.Струнков. Пакет прикладных программ для решения систем нелинейных алгебраических уравнений от двух переменных. – М: МИФИ, 1998. –52 с.
11. Borisevich V.D., Potemkin V.G., Strunkov S.P., Wood H.G. Spectral Method for Solving SNAE with Two Variables (Theory and MATLAB Toolbox), 1997-1999, (MEPhI), Wood H.G. (University of Virginia).
12. Borisevich V.D., Potemkin V.G., Wood H.G. A New Approach for Finding All Zeros for systems of nonlinear Functions. An International Journal Computers & Mathematics with Application, v.40 (8-9), 2000, pp.965-970.
13. Borisevich V.D., Potemkin V.G., Strunkov S.P., Wood H.G. Global Methods for Solving Systems of Nonlinear Algebraic Equations. An International Journal Computers & Mathematics with Application, v.40 (8-9), 2000, pp.1015-1025.
14. Borisevich V.D., Potemkin V.G. Solving SNPE as a New Basic Symbolic-Numerical Operation for Modeling PDE. 7^th Int. Conf. on Application of Computer Algebra, ACA'2001, 31.05-3.06, 2001, Albuquerque, New Mexico, USA.
15. Potemkin V.G.,Borisevich V.D. SNPE Solver for MATLAB Environment. 7^th Int. Conf. on Application of Computer Algebra, ACA'2001, 31.05-3.06, 2001, Albuquerque, New Mexico, USA.