Программирование, 2021, № 5, стр. 22-43

2.1. Евклидова геометрия [4, 5]

Здесь имеется длина вектора

а группа преобразований $X* = AY{\text{*}}$ ее сохраняет: т. е. $A{\text{*}}A = E$ – единичная матрица, или

Матрицы с этим свойством называются ортогональными. Они образуют группу невырожденных квадратных матриц $O(n)$ над полем $\mathbb{R}$. В группу преобразований включается и параллельный перенос

где X⁰ – фиксированный вектор. Эти преобразования сохраняют углы и вообще форму, включая площади и объемы.

2.2. Аффинная геометрия [4, 5]

Здесь имеются два пространства: основное ${{\mathbb{R}}^{n}}$ = = {X} и сопряженное (т.е. двойственное) $\mathbb{R}_{ * }^{n}$ = {Y}, а преобразования

сохраняют скалярные произведения векторов сопряженных (двойственных) пространств:

Следовательно,

т.е.

Множество взаимно однозначных аффинных отображений пространства ${{\mathbb{R}}^{n}}$ в себя образует группу, обозначаемую Aff ${{\mathbb{R}}^{n}}$. Эта группа отображается на полную линейную группу $GL(n,\mathbb{R})$, состоящую из квадратных невырожденных матриц размера n × n. В группу аффинных преобразований также входят параллельные переносы (2.1).

В этой геометрии прямые, плоскости и любые линейные многообразия переходят в прямые, плоскости и линейные многообразия соответственно. При этом углы не сохраняются, но сохраняется ортогональность между векторами прямого и двойственного пространств:

Кроме скалярного (или внутреннего) произведения двух векторов имеется внешнее произведение $n - 1$ вектора ${{X}_{1}},\; \ldots ,\;{{X}_{{n - 1}}} \in {{\mathbb{R}}^{n}}$:

где $I = ({{i}_{1}},\; \ldots ,\;{{i}_{n}})$ – набор ортов, а Y = (y₁, ..., ${{y}_{n}}) \in \mathbb{R}_{ * }^{n}$ – набор алгебраических дополнений максимального порядка. Оно позволяет вычислять нормаль Y  к векторам ${{X}_{1}},\; \ldots ,\;{{X}_{{n - 1}}}$. Аффинная геометрия позволяет решать системы линейных уравнений.

2.4. Алгебраическая геометрия [7]

Алгебраическая геометрия [7] Она изучает алгебраические многообразия, заданные в ${{\mathbb{R}}^{n}}$ системой алгебраических (т.е. полиномиальных) уравнений ${{f}_{i}}(X) = 0$, $i = 1,\; \ldots ,\;m$, где ${{f}_{i}}$ – многочлены. При этом рассматриваются бирациональные преобразования

в которых ${{p}_{i}}$, ${{q}_{i}}$, ${{r}_{i}}$, ${{s}_{i}}$ – многочлены. При таких преобразованиях кривые линии могут переходить в прямые и наоборот.

Пример 2. Рассмотрим кривую “Декартов лист”, заданную уравнением

и попробуем ее параметризовать одной переменной. Кривая на плоскости ${{x}_{1}},{{x}_{2}}$ имеет вид, показанный на рис. 2. На нем изображены лист Декарта, секущая прямая и асимптота. Точка ${{x}_{1}} = {{x}_{2}}$ = 0 является ее двойной точкой. Положим ${{x}_{2}} = k{{x}_{1}}$ и подставим это в уравнение кривой. После сокращения на $x_{1}^{2}$ получаем

т.е.

Каждой точке кривой (2.2) при $({{x}_{1}},{{x}_{2}}) \ne 0$ соответствует одна определенная прямая ${{x}_{2}} = k{{x}_{1}}$ с наклоном k, который является искомым параметром.

Пример 3. Найдем параметризацию окружности $x_{1}^{2} + x_{2}^{2} = 1$, начиная с ее точки ${{x}_{1}} = 0$, ${{x}_{2}} = 1$, чтобы каждой точке окружности соответствовала одна прямая ${{x}_{2}} - 1 = k{{x}_{1}}$ и одна точка оси ${{x}_{1}}$, по которой эти прямые пересекаются.

Через точку ${{x}_{1}} = 0$, ${{x}_{2}} = 1$, лежащую на нашей окружности, проведем прямую с наклоном k. Ее уравнение есть

т.е. ${{x}_{2}} = 1 + k{{x}_{1}}$. Подставляем его в уравнение окружности $x_{1}^{2} + x_{2}^{2} - 1 = 0$ и получаем уравнение

Вместе с уравнением (2.3) оно имеет два решения

${\text{и}}$

Замена (2.5) дает преобразование $k \to ({{x}_{1}},{{x}_{2}})$, а формула (2.3) – обратное преобразование (x₁, ${{x}_{2}}) \to k$:

Получаем бирациональное преобразование. Здесь параметром является наклон k прямой или точка $B = ( - 1{\text{/}}k,0)$. Рисунок 3 показывает параметризацию точками $B$ точек окружности $A$.

В алгебраической геометрии имеется

Теорема 1. Алгебраическое многообразие $f(X)$ = 0 с ${\text{ord}}f \leqslant n$ всегда бирационально эквивалентно пространству ${{\mathbb{R}}^{{n - 1}}}$.

В этой геометрии возможно раздутие точки в прямую или плоскость и к пространству ${{\mathbb{R}}^{n}}$ добавлена бесконечно удаленная гиперплоскость $\tilde {\mathbb{R}}_{\infty }^{{n - 1}}$. Алгоритмы алгебраической геометрии позволяют решать некоторые системы алгебраических уравнений, но они недостаточны для решения таких систем в сложных случаях.

2.5. Степенная геометрия [2, 8]

Пусть $X = ({{x}_{1}},\; \ldots ,\;{{x}_{n}})$, $Q = ({{q}_{1}},\; \ldots ,\;{{q}_{n}})$, X^Q = = $x_{1}^{{{{q}_{1}}}}\; \cdots x_{n}^{{{{q}_{n}}}} = exp\left\langle {lnX,Q} \right\rangle $, где lnX = $(ln{{x}_{1}}, \ldots ,ln{{x}_{n}})$. Преобразование

переводит X^Q в ${{Y}^{{Q{{A}^{ * }}}}}$, ибо

Рассмотрим сумму

В результате преобразования (2.6) она перейдет в сумму

Если все ${{Q}_{i}}$ лежат в одной гиперплоскости L, т.е. $\left\langle {{{Q}_{i}},N} \right\rangle = c = {\text{const}}$, тогда линейное преобразование

может перевести гиперплоскость L в гиперплоскость ${{p}_{n}} = c = {\text{const}}$. Тогда сумма (2.7) содержит ${{y}_{n}}$ только в степени $c$, множитель $y_{n}^{c}$ можно вынести за скобку и после сокращения на $y_{n}^{c}$ останется многочлен только от переменных ${{y}_{1}},\; \ldots ,\;{{y}_{{n - 1}}}$. Здесь для векторных показателей $Q \in {{\mathbb{R}}^{n}}$ получается аффинная геометрия. При этом векторы lnX, lnY лежат в сопряженном пространстве $\mathbb{R}_{ * }^{n}$. Преобразования степенной геометрии включают параллельный перенос (2.1), линейные замены $X = YA$ и степенные преобразования (2.6). Алгоритмы алгебраической и степенной геометрий позволяют решать алгебраические уравнения любой сложности при использовании соответствующего программного обеспечения [9].

В принципе, степенная геометрия пригодна и для упрощения более сложных уравнений – обыкновенных дифференциальных и в частных производных [2, 10–13].

2.6. Другие геометрии

В качестве основного пространства можно рассматривать многообразия. Имеются еше дифференциальная геометрия, неевклидовы геометрии и, наконец, топология, в которой преобразования – это любые непрерывные трансформации.

Более подробное изложение евклидовой, аффинной и проективной геометрий см. в [14].

3.1. Теория

При первом чтении здесь можно полагать, что n = 2. Тогда многогранник становится многоугольником и все объекты легко изображаются рисунками на двух плоскостях: основной ${{\mathbb{R}}^{2}}$ и двойственной $\mathbb{R}_{ * }^{2}$ (см. [8, Гл. 1]).

Пусть в ${{\mathbb{R}}^{n}}$ задано несколько точек $\{ {{Q}_{1}}, \ldots ,{{Q}_{k}}\} $ = S. Их выпуклая оболочка

является многогранником. Его граница $\partial \Gamma $ состоит из вершин $\Gamma _{j}^{{(0)}}$, ребер $\Gamma _{j}^{{(1)}}$ и граней $\Gamma _{j}^{{(d)}}$ разных размерностей $d:1 < d \leqslant n - 1$. Если задан вещественный $n$-вектор $P = ({{p}_{1}},\; \ldots ,\;{{p}_{n}})$, то максимум и минимум скалярного произведения $\left\langle {P,Q} \right\rangle = {{p}_{1}}{{q}_{1}}$ + + ... + p_nq_n на множестве S достигаются на точках ${{Q}_{i}}$, лежащих на границе $\partial \Gamma $. Выделим для каждой грани $\Gamma _{j}^{{(d)}}$ (включая вершины $\Gamma _{j}^{{(0)}}$ и ребра $a_{j}^{{(1)}}$) то множество векторов $P$, для которых максимум $\left\langle {P,Q} \right\rangle $ достигается на точках ${{Q}_{i}} \in \Gamma _{j}^{{(d)}}$. Это будет ее нормальный конус

При этом вектор P лежит в пространстве $\mathbb{R}_{ * }^{n}$, двойственном пространству ${{\mathbb{R}}^{n}}$. Вообще, здесь мы находимся в ситуации аффинной геометрии.

Пример 4. Пусть n = 2 и множество S состоит из трех точек ${{Q}_{1}} = (3,\;0)$, ${{Q}_{2}} = (0,\;3)$, ${{Q}_{3}} = (1,\;1)$. Их выпуклая оболочка $\Gamma $ – это треугольник с этими вершинами $\Gamma _{j}^{{(0)}} = {{Q}_{j}}$, $j = 1,2,3$ и тремя ребрами $\Gamma _{j}^{{(1)}}$ на плоскости ${{\mathbb{R}}^{2}}$. На рис. 4 изображены носитель и многоугольник $\Gamma $ примера 4.

Ребро $\Gamma _{1}^{{(1)}} = [{{Q}_{1}},{{Q}_{3}}]$, его направляющий вектор ${{R}_{1}}\, = \,{{Q}_{3}}\, - \,{{Q}_{1}}\, = \,(2, - {\kern 1pt} 1)$. Нормальный вектор ${{N}_{1}}$ = (1, 2). Но этот вектор ${{N}_{1}}$ направлен от ребра $\Gamma _{1}^{{(1)}}$ внутрь треугольника $\Gamma $. Поэтому внешняя нормаль ${{\tilde {N}}_{1}} = ( - {\kern 1pt} 1$, –2). Натянутый на него луч $\lambda {{\tilde {N}}_{1}} = ( - \lambda $, ‒2λ) с $\lambda > 0$ является нормальным конусом ${\mathbf{U}}_{1}^{{(1)}}$. Аналогично находим ${\mathbf{U}}_{2}^{{(1)}} = \lambda $(–2, –1) и ${\mathbf{U}}_{3}^{{(1)}}$ = λ(1, 1) с $\lambda > 0$. Нормальный конус вершины $\Gamma _{1}^{{(0)}} = {{Q}_{1}}$ есть

Аналогично находим нормальные конусы

Нормальные конусы ${\mathbf{U}}_{j}^{{(d)}}$ граней $\Gamma _{j}^{{(d)}}$ многоугольника $\Gamma $ рис. 4 показаны на рис. 5.

Итак, на сопряженной плоскости $\mathbb{R}_{ * }^{2}$ лучи, нормальные к ребрам $\Gamma _{j}^{{(1)}}$ и направленные наружу треугольника $\Gamma $, образуют нормальные конусы ${\mathbf{U}}_{j}^{{(1)}}$ ребер $\Gamma _{j}^{{(1)}}$ (рис. 5). Секторы между ними – это нормальные конусы ${\mathbf{U}}_{j}^{{(0)}}$ вершин $\Gamma _{j}^{{(0)}}$.

Пусть в силу исходной задачи нас интересует не вся граница $\partial \Gamma $, а только ее часть, соответствующая некоторому множеству $\mathcal{K}$ направлений $P$. Тогда множество $\mathcal{K}$ назовем конусом задачи. Он не обязательно выпуклый. Через $\partial \Gamma (\mathcal{K})$ обозначим ту часть границы $\partial \Gamma $, для элементов которой $\Gamma _{j}^{{(d)}}$ их нормальные конусы ${\mathbf{U}}_{j}^{{(d)}}$ пересекаются с конусом задачи $\mathcal{K}$. Назовем $\partial \Gamma (\mathcal{K})$ – границей задачи.

Пример 5. Пусть n = 2 и ${{\mathcal{K}}_{1}}$ – это верхняя полуплоскость ${{\mathcal{K}}_{1}} = {\text{\{ }}P = ({{p}_{1}},{{p}_{2}}):{{p}_{2}} > 0{\text{\} }}$, ${{\mathcal{K}}_{2}}$ – это правая полуплоскость ${{\mathcal{K}}_{2}} = \left\{ {P = ({{p}_{1}},{{p}_{2}}):{{p}_{1}} > 0} \right\}$, и ${{\mathcal{K}}_{3}}$ – это третий квадрант ${{\mathcal{K}}_{3}} = \left\{ {P = ({{p}_{1}},{{p}_{2}}) < 0} \right\}$, тогда $\partial \Gamma ({{\mathcal{K}}_{1}})$ – это верхняя часть границы $\partial \Gamma $, $\partial \Gamma ({{\mathcal{K}}_{2}})$ – это правая часть границы $\partial \Gamma $ и $\partial \Gamma ({{\mathcal{K}}_{3}})$ – это пересечение левой и нижней частей границы $\partial \Gamma $.

Для многоугольника $\Gamma $ примера 4 границы задач таковы:

Конусы этих задач и границы задач примеров 4 и 5 показаны на рис. 6.

Все векторы нормального конуса ${\mathbf{U}}_{j}^{{(d)}}$ ортогональны грани $\Gamma _{j}^{{(d)}}$.

3.2. Программное обеспечение

Для работы с выпуклыми множествами имеется различное программное обеспечение. Здесь кратко опишем только те программы, которые могут быть использованы как для вычисления выпуклых оболочек, так и для вычисления их нормальных конусов.

Пакет Qhull [15] используется во многих пакетах прикладных программ, как коммерческих, так и свободных, программный интерфейс с пакетом Qhull имеют системы для научных расчетов Matlab, GNU Octave, системы компьютерной алгебры Mathematica и Maple, библиотеки SciPy и geometry для языков программирования Python и R соответственно.

Применение этого пакета совместно с системой компьютерной алгебры Maple для исследования алгебраических сингулярностей описано в работе авторов [16].

Основной особенностью пакета является то, что вычисления производятся с использованием вещественных чисел, а не в поле рациональных чисел, что удобно при работе с многогранником Адамара. При вычислениях многогранника Ньютона требуются дополнительные действия для приведения результатов вычислений к рациональным значениям.

Пакет PolyhedralSets системы Maple [17]. Начиная с версии 2015 года система компьютерной алгебры Maple включает в себя пакет PolyhedralSets. Он позволяет, в частности, вычислять выпуклую оболочку множества, давать ее $H$‑ или $V$-представления, т.е. либо в виде уравнений гиперплоскостей границы, либо в виде набора крайних точек и лучей, линейная комбинация которых дает неограниченную выпуклую оболочку. В этом пакете все вычисления производятся в поле рациональных чисел, что несколько упрощает его использование для исследования многогранников Ньютона, но делает бесполезным при работе с многогранником Адамара. Отметим, что пакет PolyhedralSets по сравнению с пакетом Qhull имеет крайне низкую производительность. Ниже приведен листинг 1 программы вычисления нормальных конусов выпуклого многоугольника листа Декарта (пример 4) в системе Maple.

Листинг 1: Maple

># Загрузка библиотеки

>with(PolyhedralSets):

>SuppFolium := [ [3, 0], [0, 3], [1, 1]]:

>ConvSuppFolium:=

     ConvexHull (PolyhedralSet ( SuppFolium)):

>Relations (ConvSuppFolium);

$\left[ { - {{x}_{1}} - 2{{x}_{2}} \leqslant - 3,\; - {{x}_{1}} - \tfrac{{{{x}_{2}}}}{2} \leqslant - \tfrac{3}{2},\;{{x}_{2}} + {{x}_{1}} \leqslant 3} \right]$

Результат вычислений дает H-представление выпуклой оболочки, из которой уже легко получить внешние нормальные векторы (–1, –2), $( - 1, - 1{\text{/}}2)$, (1, 1), найденные в примере 4.

Другие пакеты. Большой выбор библиотек для исследования в области вычислительной геометрии предоставляет свободно распространяемая система компьютерной алгебры Sage [18]. Она позволяет работать с библиотеками: cdd [19], PPL (Parma Polyhedral Library) [20], polymake, Qhull и другими. Пример вычисления выпуклой оболочки и нормальных конусов листа Декарта с использованием Qhull и SymPy [21] на языке Python приведен в листинге 2.

Листинг 2: SymPy

# Загрузка библиотек

from scipy.spatial import ConvexHull

import sympy as sym

import sympy.printing as printing

import numpy as np

# Уравнение листа Декарта

x, y = sym.var (“x y”)

Folium=sym.Poly (x**3+y**3=3*x*y, [x, y])

print (printing.latex (Folium))

${\text{Poly}}({{x}^{3}} - 3xy + {{y}^{3}},x,y,domain = \mathbb{Z})$

# Вычисление носителя и выпуклой оболочки

support=np.array ([[x, y] for x, y in\

             Folium.monoms ( ) ] )

CH=ConvexHull (support)

# Вычисление нормальных конусов к граням

CH_ncoeffs=CH. equations [: , : 2]

mincoeffs=np.min(np.abs (CH_ncoeffs), axis=1)

CH_NC=np.array (CH_ncoeffs/mincoeffs [ :, None], \

             dtype=np.int)

printing.latex (CH_NC)

[[1, 1] [−2 −1] [−1 −2]]

4.1. Алгоритм

Для многочлена

с вещественными или комплексными коэффициентами a_k его корни всегда выражаются в радикалах, если $m \leqslant 4$ (формулы Кардано и Феррари – XVI век).

Согласно Абелю и Галуа (1830) общее уравнение ${{f}_{m}}(x) = 0$ с $m > 4$ неразрешимо в радикалах от его коэффициентов. Для уравнения пятой степени Эрмит, Кронекер и Бриоски (1858) показали, что его корни могут быть выражены через тета-функции Якоби [22]. При $m > 6$ известно, в каких сложных функциях от коэффициентов a_k оно разрешается [23], но явных формул, пригодных для вычисления, пока нет. Имеются различные способы определения числа вещественных корней на заданном интервале $x \in [a,b]$ и их приближенных значений.

Опишем новый способ вычисления приближенных значений корней многочлена (4.1). Для этого на вещественную плоскость ${{q}_{1}},{{q}_{2}}$ наносятся точки

образующие суперноситель , и строится их выпуклая оболочка которая называется многоугольник Адамара [24] (Hadamard, 1893). Граница $\partial {\mathbf{H}}$ является ломаной линией. Каждому ребру $\Gamma _{j}^{{(1)}}$ и вершине $\Gamma _{j}^{{(0)}}$ этой границы $\partial {\mathbf{H}}$ соответствует граничное подмножество ${\mathbf{S}}_{j}^{{(d)}}$ точек , лежащих на $\Gamma _{j}^{{(d)}}$, и укороченный многочлен

В укороченный многочлен входят те и только те слагаемые ${{a}_{k}}{{x}^{k}}$, у которых модуль ${\text{|}}{{a}_{k}}{{x}^{k}}{\text{|}}$ наибольший при фиксированном $\left| x \right|:ln\left| x \right| = {{p}_{1}}$, ибо тогда

а экспонента – монотонная функция.

Если $\Gamma _{j}^{{(d)}}$ – вершина, то укороченный многочлен (4.2) является мономом, который не имеет ненулевого корня. Если же $\Gamma _{j}^{{(d)}}$ – ребро, то укороченный многочлен (4.2) имеет ненулевые корни, которые дают приближенные значения для корней полного многочлена (4.1). Кроме исключительных случаев, укороченные многочлены (4.2) существенно проще исходного многочлена (4.1), и их корни вычисляются легче.

Поскольку вектор $({{p}_{1}},1)$ лежит в верхней полуплоскости двойственной плоскости $\mathbb{R}_{ * }^{2}$, то конус задачи здесь $\mathcal{K} = \left\{ {P = ({{p}_{1}},{{p}_{2}}):{{p}_{2}} > 0} \right\}$, т.е. – это верхняя полуплоскость. Поэтому согласно примеру 5 раздела 3 соответствующая часть $\partial {\mathbf{H}}(\mathcal{K})$ границы $\partial {\mathbf{H}}$ – это ее верхняя часть. Ее назовем ломаной Адамара и обозначим $\tilde {H}$ [24], [8, гл. IV, § 2, п. 2.1].

Пример 6. В этом примере метод ломанной Адамара дает хорошие начальные приближения как для вещественных, так и для комплексных корней.

Рассмотрим многочлен

с корнями $x_{k}^{0} = 0, \pm i, \pm 3$. Его ломаная Адамара натянута на три вершины $(1,\;ln9)$, $(3,\;ln8)$, (5, 0) и показана на рис. 7. Она имеет два ребра $\Gamma _{1}^{{(1)}}$ и $\Gamma _{2}^{{(2)}}$.

Ребрам $\Gamma _{1}^{{(1)}}$ и $\Gamma _{2}^{{(2)}}$ соответствуют укороченные многочлены

корни которых ${{x}_{1}} = 0$, ${{x}_{{2,3}}} = \pm \sqrt {9{\text{/}}8} i \approx \pm 1.060660i$ и ${{x}_{{4,5}}} = \pm \sqrt 8 \approx \pm 2.828427$ дают приближенные значения ненулевых корней полного многочлена $f(x)$. Для их уточнения можно использовать метод Ньютона, т.е. искать разложение корня ${{x}^{0}} = x + {{\varepsilon }_{1}} + {{\varepsilon }_{2}} + \; \ldots $ Для первых добавок ${{\varepsilon }_{1}}$ из уравнения $f(x) + {{\varepsilon }_{1}}f{\kern 1pt} {\text{'}}(x) = 0$ получаем значение ${{\varepsilon }_{1}} = - f(x){\text{/}}f{\kern 1pt} {\text{'}}(x)$. Значения приближенных корней x_k, добавок ${{\varepsilon }_{1}}$ в ${{x}_{k}}$, $k = 2,\; \ldots ,\;5$, и уточненных значений ${{x}_{k}} + {{\varepsilon }_{1}}$ показаны в табл. 1. В ее нижней строке указаны значения точных корней $x_{k}^{0}$ многочлена (4.3). Дальнейшие вычисления показывают, что достаточно еще 4-х итераций, чтобы получить приближенные значения корней с точностью до 10-го знака после запятой.

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

Пример 7. С помощью ломаной Адамара найдем приближенные значения корней многочлена

с корнями $x_{k}^{0}\, = \, \pm \frac{1}{2}\sqrt { - 6\, \pm \,2i\sqrt 3 } \, \approx \, \pm 0.340625$ ± 1.271230i. Его ломаная Адамара натянута на три вершины $(0,\;ln3)$, $(2,\;ln3)$, $(4,\;0)$ и показана на рис. 8.

Она имеет два ребра $\Gamma _{1}^{{(1)}}$ и $\Gamma _{2}^{{(2)}}$, которым соответствуют укороченные многочлены

с соответствующими корнями ${{x}_{{1,2}}} = \pm i$ и x_{3, 4} = = $ \pm \sqrt 3 i \approx \pm 1.732051i$.

Итерации этих корней по методу Ньютона не сходятся к точным значениям корней. Для ${{x}_{{1,2}}}$ получаем периодическую последовательность значений с периодом 2 вблизи $ \pm 1.042i$. Итерации корней ${{x}_{{3,4}}}$ вообще демонстрируют хаотическое поведение.

В целом метод ломаной Адамара состоит в том, что исходный многочлен заменяется набором более простых многочленов, корни которых вычисляются просто и дают такие приближения корней исходного многочлена, которые достаточно хороши для численного уточнения по методу Ньютона. В конце раздела 6 объясняются случаи, когда уточнения не сходятся к точному значению.

4.2. Программное обеспечение

Отметим, что имеются многочисленные программы, позволяющие численно находить с любой точностью корни любого многочлена. Любая система компьютерной алгебры позволяет делать это численно. Так, например,

• в системе Mathematica это делает функция NRoots;

• в Python имеется пакет высокоточной арифметики mpmath, где вычисление корней осуществляет функция polyroots;

• в системе Maple имеется специальный пакет RootFinding, содержащий функции для изолирования вещественных и комплексных корней с произвольной точностью.

Ниже приведен пример вычисления корней многочлена 7-й степени пример 3 из статьи [1] в системе Maple с помощью пакета RootFinding (см. листинг 3).

Листинг 3: Maple

with( RootFinding):

>f7 :=–4320–9336*x–4972*x^2–3754*x^3–1426*x^4+104*x^5+51*x

    ^6+3*x^7:

>Analytic (f7, x , r e =–10. .10 , im=–10. .10 , digits = 25);

[ –0.5818662859936160237203075,

  –2.098451028439695378650494,

  5.255155425603335889745440,

  –9.839354523877774394108640 – 0.9310465789411591695975430*

     I,

  –9.839354523877774394108643 + 0.9310465789411591695975413*

     I,

  0.05193546829276215042132425 – 1.514851641026718679226917*

     I,

  0.05193546829276215042132410 + 1.514851641026718679226917*

     I]

Замечание 1. Общие корни $(x_{1}^{0},x_{2}^{0})$ двух многочленов $f({{x}_{1}},{{x}_{2}})$ и $g({{x}_{1}},{{x}_{2}})$ можно найти с помощью метода исключения [25, 26], который позволяет исключить одну из неизвестных (скажем ${{x}_{1}}$) и получить их результант, как многочлен $h({{x}_{2}})$ от другой неизвестной (здесь ${{x}_{2}}$). Найдя корни $x_{2}^{0}$ многочлена $h({{x}_{2}})$ и подставив их значения в многочлены f и $g$, получаем два алгебраических уравнения от одной неизвестной ${{x}_{1}}$. Из них находим общие корни.

Замечание 2. Имеется большое число способов вычисления результанта двух многочленов, самым популярным, но далеко не самым эффективным из которых является метод Сильвестра [25, 26]. Все системы компьютерной алгебры имеют встроенные функции для вычисления результанта, используя при этом метод псевдоделения, предложенный Якоби (см., подробнее, [27, 28]). В системе Maple для пары многочленов замечания 1 достаточно просто вызвать команду resultant(f,g,x2).

5.1. Локальный анализ простой точки

Теорема 2. (Коши [2]). Если при ${{X}^{0}} = 0$ производная $\partial f{\text{/}}\partial {{x}_{i}} \ne 0$, то все решения уравнения (6.1) вблизи точки ${{X}^{0}} = 0$ содержатся в разложении

где ${{b}_{k}}$ – постоянные, а $j = 3 - i$.

5.2. Локальный анализ особой точки ${{X}^{0}} = 0$ и точек $(0,\infty )$, $(\infty ,0)$, $(\infty ,\infty )$ [8, гл. 1, § 2], [2, гл. 2]

Запишем многочлен $f(X)$ в виде

где $X = ({{x}_{1}},{{x}_{2}})$, $Q = ({{q}_{1}},{{q}_{2}})$, ${{X}^{Q}} = x_{1}^{{{{q}_{1}}}}x_{2}^{{{{q}_{2}}}}$, ${{f}_{Q}} \in \mathbb{C}$ – постоянные. Пусть ${\mathbf{S}}(f) = {\text{\{ }}Q:{{f}_{Q}} \ne 0{\text{\} }} \subset {{\mathbb{R}}^{2}}$. Множество ${\mathbf{S}}$ называется носителем (support) многочлена $f(X)$. Пусть оно состоит из точек ${{Q}_{1}},\; \ldots ,\;{{Q}_{k}}$. Выпуклая оболочка носителя ${\mathbf{S}}(f)$ – это множество которое называется многоугольником Ньютона. Граница $\partial {\mathbf{N}}(f)$ состоит из вершин $\Gamma _{j}^{{(0)}}$ и ребер $\Gamma _{j}^{{(1)}}$, где  j – это номер.

Каждой обобщенной грани $\Gamma _{j}^{{(d)}}$ соответствуют: ее граничное подмножество ${\mathbf{S}}_{j}^{{(d)}} = {\mathbf{S}} \cap \Gamma _{j}^{{(d)}}$, ее укороченный многочлен

и свой нормальный конусгде $P = ({{p}_{1}},{{p}_{2}}) \in \mathbb{R}_{ * }^{2}$, а плоскость $\mathbb{R}_{ * }^{2}$ сопряжена плоскости ${{\mathbb{R}}^{2}}$.

Пусть ${{x}_{1}} \in \mathbb{C}$, ${{x}_{1}} \to 0$ или $\infty ,$ а $o(1)$ – функция от ${{x}_{1}}$, которая при этом стремится к нулю. На кривой

где $b = {\text{const}} \in \mathbb{C}$, $p \in \mathbb{R}$, моном где $Q = ({{q}_{1}},{{q}_{2}})$, ${{X}^{Q}} = x_{1}^{{{{q}_{1}}}}x_{2}^{{{{q}_{2}}}}$, ${{f}_{Q}} = {\text{const}} \in \mathbb{C}$, $X\, \in \,{{\mathbb{C}}^{2}}$, принимает значения

При этом $P = (1,p)$,

и

Это означает, что при заданных P и $\omega $ наибольшие модули имеют те мономы (5.4) суммы (5.3), на которых величина

достигает максимума.

Если ${{x}_{1}} \to 0,$ то $\omega = - 1$ и вектор $\omega P = ( - 1, - p).$ Следовательно, здесь конус задачи $\mathcal{K}$ – это левая полуплоскость плоскости $\mathbb{R}_{ * }^{2}$ и точки Q с максимальными значениями произведения (5.5) лежат на левой части границы $\partial {\mathbf{N}}.$

Если ${{x}_{1}} \to \infty ,$ то ω = 1 и вектор $\omega P = (1,p).$ Следовательно, здесь конус задачи $\mathcal{K}$ – это правая полуплоскость плоскости $\mathbb{R}_{ * }^{2}$ и точки $Q$ с наибольшими значениями произведения (5.5) лежат на правой части границы $\partial {\mathbf{N}}.$

Будем искать решения уравнения

в виде разложений где ${{f}_{Q}}$, ${{b}_{k}} = {\text{const}} \in \mathbb{C}$, $Q \in {{\mathbb{R}}^{2}}$, ${{p}_{k}} = {\text{const}} \in \mathbb{R}$, $\omega {{p}_{k}} > \omega {{p}_{{k + 1}}}$.

В этих разложениях показатели степени p_k возрастают вместе с k, если ${{x}_{1}} \to 0$, и убывают, если ${{x}_{1}} \to \infty $.

Итак, доказана

Теорема 3. Для решений (5.7) уравнения (5.6) укороченное решение

является решением укороченного уравнениясоответствующего элементу границы $\Gamma _{j}^{{(d)}}$ с внешним нормальным вектором $\omega (1,{{p}_{1}}).$

Теперь заметим, что левая часть укороченного уравнения (5.6), соответствующего вершине, состоит из одного монома (5.4). Такое укороченное уравнение имеет только нулевой корень и не дает первое приближение (5.8). Поэтому теорема 3 относится только к укороченным уравнениям (5.9), соответствующим ребрам, т.е. d = 1.

Пример 8. Пусть

Носитель состоит из трех точек ${{Q}_{1}} = (3,\;0)$, ${{Q}_{2}} = (0,\;3)$, ${{Q}_{3}} = (1,\;1)$ (пример 4 раздела 3). Их выпуклая оболочка – это треугольник $\Gamma = {\mathbf{N}}$ с этими вершинами (рис. 4 раздела 3). Он имеет три ребра $\Gamma _{1}^{{(1)}}$, $\Gamma _{2}^{{(1)}}$ и $\Gamma _{3}^{{(1)}}$ с внешними нормалями $ - (2,\;1)$, –(1, 2), (1, 1) соответственно. Ребру $\Gamma _{1}^{{(1)}}$ соответствует укороченное уравнение $\tilde {f}_{1}^{{(1)}} = x_{1}^{3} - 3{{x}_{1}}{{x}_{2}} = 0$. Оно имеет решение

Ребру $\Gamma _{2}^{{(1)}}$ соответствует укороченное уравнение $\tilde {f}_{2}^{{(1)}} = x_{2}^{3} - 3{{x}_{1}}{{x}_{2}} = 0$. Оно имеет решение

Ветви (5.11) и (5.12) относятся к окрестности нуля ${{x}_{1}} = {{x}_{2}} = 0,$ поскольку внешние нормали соответствующих ребер $\Gamma _{1}^{{(1)}}$ и $\Gamma _{2}^{{(1)}}$ имеют обе координаты отрицательными. Наконец, ребру $\Gamma _{3}^{{(1)}}$ соответствует укороченное уравнение $\tilde {f}_{3}^{{(1)}} = x_{1}^{3} + x_{2}^{3}$ = $({{x}_{1}} + {{x}_{2}})(x_{1}^{2} - {{x}_{1}}{{x}_{2}} + x_{2}^{2}) = 0$. Оно имеет только одно вещественное решение

Оно относится к окрестности бесконечности ${{x}_{1}} = {{x}_{2}} = \infty $, ибо у внешней нормали к ребру $\Gamma _{3}^{{(1)}}$ обе координаты положительны. Куски (5.11)–(5.13) кривой (5.10) вблизи нуля и бесконечности показаны на рис. 9.

По укороченному уравнению (5.9) однозначно определяется знак $\omega $ и показатель степени ${{p}_{1}}.$ Если в сумме (5.3) все векторные показатели степени $Q = ({{q}_{1}},{{q}_{2}})$ имеют рациональные компоненты ${{q}_{1}}$ и ${{q}_{2}}$, то показатель ${{p}_{1}}$ – рационален. Для коэффициента ${{b}_{1}}$ получаем алгебраическое уравнение

Будем различать 2 случая:

а) ${{b}_{1}}$ – простой корень уравнения (5.14), тогда

б) ${{b}_{1}}$ – кратный корень уравнения (5.14), тогда

Для вычисления второго члена ${{b}_{2}}x_{1}^{{{{p}_{2}}}}$ разложения (5.7) решения уравнения (5.6) делаем замену

Тогда уравнение (5.6) принимает вид

где $r = \left\langle {(1,{{p}_{1}}),Q} \right\rangle $ с $Q \in {\mathbf{S}}_{j}^{{(1)}}$, с такими $Q{\text{'}} = (q_{1}^{'},q_{2}^{'})$, что $\omega q_{1}^{'} < 0$. Если в исходном уравнении (5.6) все показатели $Q = ({{q}_{1}},{{q}_{2}})$ целочисленные, то ${{p}_{1}}$ – рациональное число со знаменателем $s$. Тогда в случае а) при $\omega = - 1$ к уравнению где ${{y}_{1}} = x_{1}^{{1/s}}$ применима теорема 2, которая дает разложение (5.7) с рациональными показателями степени ${{p}_{k}}$, имеющими общий знаменатель $s$. Аналогично в случае а) при ω = 1 для ${{y}_{1}} = x_{1}^{{ - 1/s}}$ применима теорема 2.

В случае б) после замены (6.15) надо снова строить многоугольник Ньютона для уравнения

находить его ребра и т.д. Если на некотором шаге k мы приходим к простому корню ${{b}_{k}}$ укороченного уравнения вида (5.14), то по теореме 2 получаем степенное разложение (5.7) решения исходного уравнения (5.6).

Если на каждом шаге получаем только кратные решения ${{b}_{k}}$, то многочлен $f(X)$ надо разложить на неприводимые полиномиальные множители ${{f}_{l}}(X)$:

используя алгоритмы разложения на множители [25, § 53], [29, Часть III, п. 6] имеющиеся в любой системе компьютерной алгебры. В каждом множителе ${{f}_{l}}(X)$ все ветви простые и имеют вид (5.7). Иначе многочлены ${{f}_{l}}(X)$ и $\partial {{f}_{l}}(X){\text{/}}\partial {{x}_{2}}$ имели бы общий полиномиальный множитель. Итак, доказана

Теорема 4. Для полиномиального уравнения (5.6) все решения ${{x}_{2}}({{x}_{1}})$ разлагаются в ряды вида (5.7), где все показатели степени p_k суть рациональные числа с общим знаменателем.

Для окрестности точки X = 0 теорема 4 – это теорема В. Пюизё, 1850 г. [30], т.е. для конуса задачи $\mathcal{K} = \{ P = ({{p}_{1}},{{p}_{2}}):{{p}_{1}}$, p₂ < 0}. Соответствующая часть (левая нижняя) границы $\partial {\mathbf{N}}$ называется ломаной Ньютона. Разложения теоремы 2 сходятся (см. [31], § 184), поэтому сходятся и все разложения (5.7) для решений полиномиальных уравнений (5.6).

Пример 9 (продолжение примера 8). В случае ребра $\Gamma _{1}^{{(1)}}$ после подстановки ${{x}_{2}} = x_{1}^{2}\left( {\frac{1}{3} + {{y}_{2}}} \right)$ получаем

Для многочлена в скобках укороченное уравнение есть $ - 3{{y}_{2}} + x_{1}^{3}{\text{/}}27 = 0$. Поэтому ${{y}_{2}} = x_{1}^{3}{\text{/}}81$ и

В случае ребра $\Gamma _{2}^{{(1)}}$ после подстановки x₂ = = $\sqrt {{{x}_{1}}} ( \pm \sqrt 3 + {{y}_{2}})$ получаем

Укороченное уравнение для многочлена в скобках – это $x_{1}^{{3/2}} + 6{{y}_{2}} = 0,$ т.е. ${{y}_{2}} = - x_{1}^{{3/2}}{\text{/}}6$. Итак,

Наконец, для ребра $\Gamma _{3}^{{(1)}}$ для укороченного решения (5.13) после подстановки ${{x}_{2}} = {{x}_{1}}( - 1 + {{y}_{2}})$ в (5.10) получаем

Носитель и многоугольник Ньютона этого многочлена показаны на рис. 10. Здесь ${{x}_{1}} \to \infty $, ${{y}_{2}}\, \to \,0$, поэтому конус задачи $\mathcal{K}\, = \,{\text{\{ }}P\,:\,{{p}_{1}}\, > \,0$, p₂ < 0}, т.е. надо рассмотреть правую нижнюю часть границы многоугольника. Там есть только одно ребро $\tilde {\Gamma }_{1}^{{(1)}}$ с укороченным уравнением

Его решение ${{y}_{2}} = - \tfrac{1}{{{{x}_{1}}}}$. Итак, здесь

и разложение идет по убывающим степеням ${{x}_{1}}$. Прямая – это асимптота ветвей, уходящих в бесконечность.

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

Уточненные куски (5.18), (5.19), (5.21) листа Декарта (2.2), (5.10) вблизи нуля и бесконечности показаны на рис. 11.

5.3. Вещественная кривая

Если у многочлена (5.1) все коэффициенты ${{f}_{Q}}$ вещественны, то уравнение (5.3) при $x \in \mathbb{R}$ определяет вещественную кривую F на плоскости ${{x}_{1}},{{x}_{2}}$. Для нее в разложении (5.2) теоремы 2 все коэффициенты b_k вещественны, а из разложений (5.7) теоремы 4 имеют смысл только те, в которых все коэффициенты b_k вещественны. Поскольку они вычисляются последовательно, то на каждом шаге надо оставлять только вещественные коэффициенты b_k, а комплексные отбрасывать.

В особой точке $X = 0$ разложение (5.2) начинается с квадратичных членов

Рассмотрим дискриминант выписанной в (6.23) квадратичной формы ${{g}_{2}}$.

Теорема 5. Если $\Delta < 0$, то кривая $F$ не имеет вещественных ветвей, проходящих через критическую точку $X = 0$.

Пусть имеются два многочлена степени 2 и 3 соответственно:

Их результант (т.е. результат исключения переменной x из них) – это многочлен от их коэффициентов

Если многочлены $g$ и $h$ имеют общий корень, то результант $\Omega $ тождественно равен нулю.

Теорема 6. Пусть в особой точке $X = 0$

где ${{f}_{k}}(X)$ – это однородные формы степени k по ${{x}_{1}}$, ${{x}_{2}}$, форма и ее дискриминант $\Delta = 0$, а результант $\Omega $ форм ${{f}_{2}}$ и ${{f}_{3}}$ отличен от нуля. Тогда вблизи точки $X = 0$ кривая $F$ – это полукубическая парабола видагде $\alpha $ – это кратный корень многочлена ${{f}_{2}}(1,\alpha )$.

5.4. Эскиз вещественной кривой

Пусть у многочлена $f(X)$ все коэффициенты вещественны, тогда на вещественной плоскости $X \in {{\mathbb{R}}^{2}}$ можно нарисовать все ее ветви, используя локальный анализ, описанный выше. Разобьем эту процедуру на несколько шагов.

Шаг 1. Разлагаем многочлен $f(X)$ на полиномиальные множители (5.16), используя указанные выше алгоритмы. Далее строим эскизы кривых для каждого неразложимого множителя ${{f}_{l}}(X)$ отдельно.

Шаг 2. Находим все вещественные конечные особые точки ${{X}^{0}}$ кривой  f = 0, в которых

используя метод исключения или метод базиса Грёбнера.

Шаг 3. Вблизи каждой особой точки ${{X}^{0}}$ находим все вещественные ветви вида (5.7), перенося ее в начало координат и используя методы разделов 3, 5.2 и 5.3.

Шаг 4. Находим точки пересечения кривой с осями ${{x}_{1}} = 0$ и ${{x}_{2}} = 0$, как решения уравнений $f(0,{{x}_{2}}) = 0$ и $f({{x}_{1}},0) = 0$, используя методы раздела 4 и уточняя их по теореме 2.

Шаг 5. Находим конечные точки пересечения кривой с бесконечностями ${{x}_{1}} = \infty $ и ${{x}_{2}} = \infty $ по укороченным уравнениям с $P = (1,\;0)$ и $P = (0,\;1).$ Для каждой из них вычисляем начальные члены разложений типа (5.7).

Шаг 6. Находим ветви кривой при ${{x}_{1}} \to 0$, ${{x}_{2}} \to \infty $, используя часть границы $\partial {\mathbf{N}}$ с конусом задачи ${{\mathcal{K}}_{1}} = \left\{ {P:{{p}_{1}} < 0,{{p}_{2}} > 0} \right\}$. Аналогично при ${{x}_{1}} \to \infty $, ${{x}_{2}} \to 0$ – с конусом задачи ${{\mathcal{K}}_{2}} = \left\{ {P:{{p}_{1}} > 0,{{p}_{2}} < 0} \right\}$.

Шаг 7. Находим ветви кривой при ${{x}_{1}},{{x}_{2}} \to \infty $, используя часть границы $\partial {\mathbf{N}}$ с конусом задачи ${{\mathcal{K}}_{3}} = \left\{ {P:{{p}_{1}} > 0,{{p}_{2}} > 0} \right\}$.

Шаг 8. Соединяем найденные куски ветвей кривой, учитывая, что вне особых точек X⁰ ветви кривой не пересекаются.

Пример 10 (продолжение примеров 8 и 9). Здесь применение наших шагов к многочлену (5.10) дает следующее.

1. Многочлен неразложим.

2. У него только одна особая точка ${{X}^{0}} = 0$.

3. Вблизи этой точки мы нашли две ветви (5.18) и (5.19).

4. Кривая пересекается с осями только в точке $X = 0$.

5. С бесконечностями ${{x}_{1}} = \infty $ и ${{x}_{2}} = \infty $ кривая не пересекается, так как им соответствуют вершины ${{Q}_{1}}$ и ${{Q}_{2}}$.

6. С конусами задач ${{\mathcal{K}}_{1}}$ и ${{\mathcal{K}}_{2}}$ пересекаются только нормальные конусы ${\mathbf{U}}_{2}^{{(0)}}$ и ${\mathbf{U}}_{1}^{{(0)}}$ вершин ${{Q}_{2}}$ и ${{Q}_{1}}$ соответственно (рис. 5 раздела 3). Поэтому нет ветвей с ${{x}_{1}} \to 0$, ${{x}_{2}} \to \infty $ и ${{x}_{1}} \to \infty $, ${{x}_{2}} \to 0$.

7. Конусу задачи ${{\mathcal{K}}_{3}}$ соответствует ребро $\Gamma _{3}^{{(1)}}$, которое дало в бесконечности ветвь (5.21).

8. Соединяя найденные куски кривой из рис. 9, получаем рис. 2, на котором пунктирная прямая – это асимптота (5.22).

5.5. Программное обеспечение

В системе Maple имеется замечательный пакет algcurves, который позволяет исследовать плоские алгебраические кривые: строить их эскизы с высокой точностью, вычислять их род, находить особые точки, для кривых рода 0 находить рациональную параметризацию по методу [32], для эллиптических кривых приводить к нормальной форме Вейерштрасса. Пакет позволяет строить эскиз кривой $f(x,y) = 0$ путем численного интегрирования дифференциального уравнения $f_{x}^{'}\, + \,f_{y}^{'}y{\text{'}}$ = 0 для некоторого набора начальных условий, определяемых точками, в которых хотя бы одна из частных производных функции $f(x,y)$ равна нулю. Использование данного пакета для исследования набора кривых с разными порядками особенностей показало, что в случае особенностей высоких порядков качество эскиза получается не слишком высоким.

Рассмотрим пример исследования листа Декарта с помощью этого пакета. Вначале найдем особые точки кривой, вычислим ее род и рациональную параметризацию, а затем построим разложение ветвей в окрестности нуля и бесконечности. Последовательность вычислений в системе компьютерной алгебры Maple приведена в листинге 4.

Листинг 4. Maple

>with(algcurves):

>Folium:=x^3+y^3=3*x*y:

# Особые точки

>singularities (Folium, x, y);

  [[0, 0, 1], 2, 1, 2]

# Род

>genus (Folium, x, y);

   0

# Параметризация

>Param_Folium:=zip (‘= ‘, [x, y], parametrization (Folium, x, y, t))

$\left[ {x = \tfrac{{3{{t}^{2}}}}{{{{t}^{3}} + 1}},y = \tfrac{{3t}}{{{{t}^{3}} + 1}}} \right]$

# Ветви вблизи нуля

>branch1 := sort (puiseux (Folium, x = 0, y, 9) [1], x, ascending);

>branch2 := sort (puiseux (Folium, x = 0, y, 5) [2], x, ascending);

$\tfrac{{{{x}^{2}}}}{3} + \tfrac{{{{x}^{5}}}}{{81}} + \tfrac{{{{x}^{8}}}}{{729}}$

$\sqrt 3 \sqrt x - \tfrac{{{{x}^{2}}}}{6} - \tfrac{{\sqrt 3 }}{{72}}{{x}^{{\tfrac{7}{2}}}}$

# Ветвь вблизи бесконечности

>branch_inf := expand (puiseux (Folium, x = infinity, y , 4) [1]);

$ - 1 - \tfrac{1}{{3{{x}^{3}}}} + \tfrac{1}{{3{{x}^{2}}}} - x$

Начиная с версии 12 система компьютерной алгебры Wolfram Mathematica [33] включает процедуру AsymptoticSolve, реализующую асимптотическое представление решений уравнений или систем уравнений (не обязательно алгебраических) в виде либо рядов Тейлора, либо рядов Лорана, либо рядов Пьюизе в окрестности конечной или бесконечной точек. Если точка особая, то процедура пытается вычислить асимптотические разложения всех ветвей. В этом случае можно указать, что следует ограничиться только вещественными разложениями. Листинг 5 демонстрирует такое вычисление разложения ветвей листа Декарта в окрестности особой точки и бесконечности.

Листинг 5: Mathematica

Folium = x^3+y^3 – 3 x y == 0

${{x}^{3}} - 3xy + {{y}^{3}}$

AsymptoticSolve [Folium, {y, 0}, {x , 0, 5}, Reals, Direction –> "

   FromAbove"]

$\left\{ {\left\{ {y \to \tfrac{{{{x}^{2}}}}{3} + \tfrac{{{{x}^{5}}}}{{81}}} \right\}} \right.,\left\{ {x \to - \sqrt 3 \sqrt x - \tfrac{{{{x}^{2}}}}{6} + \tfrac{{{{x}^{{7/2}}}}}{{24\sqrt 3 }} - \tfrac{{{{x}^{5}}}}{{162}}} \right\},$

$\left. {\left\{ {x \to \sqrt 3 \sqrt x - \tfrac{{{{x}^{2}}}}{6} - \tfrac{{{{x}^{{7/2}}}}}{{24\sqrt 3 }} - \tfrac{{{{x}^{5}}}}{{162}}} \right\}} \right\}$

AsymptoticSolve [Folium==0, y, x–>Infinity, Reals,

   SeriesTermGoal–>5]

$\left\{ {\left\{ {y \to - 1 - \tfrac{1}{{3{{x}^{3}}}} + \tfrac{1}{{3{{x}^{2}}}} - x} \right\}} \right\}$

5.6. Большой пример

Пример 11. Рассмотрим пример исследования некоторой нетривиальной кривой, имеющей несколько особых точек. Все дальнейшие вычисления выполнялись в системе компьютерной алгебры Maple с использованием описанных выше пакетов. Такие же вычисления несложно реализуются в других системах компьютерной алгебры, таких как Mathematica и SymPy.

В работах [9, 16] рассматривалась устойчивость в линейном приближении одной многопараметрической системы Гамильтона. В процессе исследования возникла необходимость изучить нули некоторого многочлена $g(x,y,z)$ 6-го порядка от трех переменных $x$, $y$, $z$ (см. формулу (3.7) в [16]). Здесь исследуем алгебраическую кривую $f(y,z)\mathop = \limits^{{\text{def}}} \mathop {\left. {g(x,y,z)} \right|}\nolimits_{x = 0} = 0$ в соответствии со схемой подпункта 5.4, где

Шаг 1. Многочлен (5.25) факторизуется на два множителя: линейный $3z - 2y$ и полином пятой степени

Далее рассматриваем только кривую $\mathcal{F}:h(y,z)$ = = 0.

Шаг 2. Находим особые точки кривой, решая систему $h = \partial h{\text{/}}\partial y = \partial h{\text{/}}\partial z = 0$. Для этого вычислим базис Грёбнера $\mathcal{G}\mathcal{B}\mathcal{J}$ данной системы, выбрав чисто лексикографический порядок переменных (см. [34, Гл. 2]). Полученный идеал является нульмерным, т.е. исходная система имеет конечное число особых точек. Их координаты легко определить, если вычислить два базиса Грёбнера для порядков $y > z$ и $z > y$ соответственно и выписать первые полиномы получившихся базисов:

Кубические полиномы в (5.27) и (5.28) имеют по одному вещественному корню ${{y}_{3}}$, ${{z}_{3}}$ соответственно, следовательно, особых точек три: $({{y}_{1}},{{z}_{1}}) = (0,0)$, $({{y}_{2}},{{z}_{2}}) = (14,27)$ и $({{y}_{3}},{{z}_{3}})$.

Шаг 3. Найдем все вещественные ветви в окрестности каждой из особых точек $({{y}_{i}},{{z}_{i}})$, $i = 1,2,3$.

а) Разложение в точке $({{y}_{1}},{{z}_{1}}) = (0,\;0)$. Здесь конус задачи есть ${{\mathcal{K}}_{3}} = \left\{ {P = ({{p}_{1}},{{p}_{2}}) < 0} \right\}$. Непосредственные вычисления показывают, что квадратичная форма ${{h}_{2}}$ ряда Тейлора многочлена h есть полный квадрат $ - 1728{{(3y - 2z)}^{2}}$ и имеет общий множитель с кубичной формой ${{h}_{3}}$. Таким образом, теоремы 5 и 6 неприменимы, и здесь необходимо применить технику подраздела 5.2.

Вычисляем выпуклую оболочку носителя многочлена (5.26) с использованием пакета PolyhedralSets. Многоугольник Ньютона и его ребра показаны на рис. 12.

Ребру $\Gamma _{1}^{{(1)}}$ соответствует укороченный многочлен $h_{1}^{{(1)}} = - 1728{{(3y - 2z)}^{2}}$. Выполним подстановку $3y - 2z = t$ и получим многочлен $\tilde {h}$ в переменных $y$, $t$:

Единственному ребру $\tilde {\Gamma }_{1}^{{(1)}}$ выпуклой оболочки носителя ${\mathbf{S}}(\tilde {h})$, попадающему в конус задачи ${{\mathcal{K}}_{3}}$, соответствует укороченный многочлен $\tilde {h}_{1}^{{(1)}}$ = –12(12t – – y²)². Следовательно, здесь требуется еще одна подстановка $t = u + {{y}^{2}}{\text{/}}12$. Она приводит к многочлену $\tilde {\tilde {h}}_{1}^{{(1)}}$ от переменных y, $u$. Его носитель имеет единственное ребро из конуса задачи ${{\mathcal{K}}_{3}}$, которому соответствует многочлен $\tilde {\tilde {h}}_{1}^{{(1)}} = - 1728{{u}^{2}}$ + 4y⁵/3. Таким образом, получаем два решения u_{1, 2} = = $ \pm {{y}^{{5/2}}}{\text{/}}36$. Выполняя обратную подстановку, в итоге получаем разложения двух ветвей

которые в особой точке (0, 0) имеют касание второго порядка. Вычисления с использованием функции puisex из пакета algcurves системы Maple или с использованием функции AsymptoticSolve системы Mathematica приводят к таким же результатам.

б) Разложение в точке $({{y}_{2}},{{z}_{2}}) = (14,\;27)$. Вычисляем (с точностью до постоянного множителя) квадратичную форму ${{h}_{2}}$ в особой точке $({{y}_{2}},{{z}_{2}})$:

Ее дискриминант $\Delta = - 560$, следовательно, по теореме 5 вещественных ветвей нет, а особая точка является точкой пересечения комплексных ветвей, в которой обнуляются их мнимые части.

в) Разложение в точке $({{y}_{3}},{{z}_{3}}) \approx (2.34274429915$, $3.2427747207226)$. Как было указано выше, координаты $({{y}_{3}},{{z}_{3}})$ этой точки являются корнями кубических многочленов

Эти многочлены имеют по одному вещественному и по паре комплексно-сопряженных корней, значения которых могут быть записаны в кубических радикалах. Однако в таком виде проводить символьные вычисления крайне неудобно из-за громоздкости получающихся выражений. Можно предложить три способа вычисления асимптотических разложений ветвей в этом случае.

Способ 1. Каждый корень многочленов (5.30) заменяется своим приближенным числовым значением, вычисленным с достаточной точностью. При подстановке этих значений в исходный многочлен появляются “паразитные” мономы с малыми коэффициентами. Для избавления от них следует сделать оценку абсолютной величины их коэффициентов и на каждом шаге вычислений удалять те мономы, коэффициенты которых не превышают полученной оценки. В силу приближенного характера коэффициентов применение теорем 5 и 6 потребует другого способа работы с дискриминантами и результантами.

Способ 2. Можно проводить все вычисления с полиномами в расширении поля рациональных чисел $\mathbb{Q}$ алгебраическими числами $\gamma $, $\delta $ – корнями многочленов (5.30). В этом случае на каждом шаге вычислений следует выполнять упрощение коэффициентов получающихся многочленов. Многие системы компьютерной алгебры позволяют проводить такого рода расчеты. Например, пакет Algebraic системы Maple содержит различные процедуры для работы с многочленами, коэффициенты которых суть алгебраические числа. Функция AlgebraicNumber системы Mathematica позволяет работать с корнями алгебраического уравнения как с обычными числами. Результат вычислений асимптотических разложений ветвей представляет собой ряд с коэффициентами, зависящими от алгебраических чисел $\gamma $, $\delta $. Заменяя их соответствующими числовыми значениями, получим ряды с приближенными коэффициентами. Основной недостаток этого способа заключается в том, что далеко не всегда удается упростить получающиеся выражения до соответствующих тривиальных значений, что в итоге приводит к громоздким выражениям и, как следствие, к трудоемким вычислениям.

Способ 3. По-видимому, самым общим способом аналитического вычисления асимптотических разложений ветвей кривой является способ вычисления по модулю иделал $\mathcal{J}$, определяющему особую точку. Все вычисления выполняются с использованием базиса Гребнера этого идеала с априорно заданным лексикографическим порядком переменных. В нашем случае используем пакет Groebner системы Maple и процедуры Basis и NormalForm из него.

Сделаем замену переменных $y = {{y}_{3}} + \eta $, $z = {{z}_{3}}$ + + ζ. Нульмерный идеал $\mathcal{J}$, определяющий особую точку $({{y}_{3}},{{z}_{3}})$, состоит из многочленов (5.30) и производных $h_{y}^{'}$, $h_{z}^{'}$. Его базис Гребнера $\mathcal{G}\mathcal{B}\mathcal{J}$ с лексикографическим порядком ${{y}_{3}} < {{z}_{3}}$ имеет вид

Для особой точки $({{y}_{3}},{{z}_{3}})$ первой невырожденной формой является квадратичная форма h₂ вблизи точки $({{y}_{3}},{{z}_{3}})$ ряда Тейлора:

Ее дискриминант по модулю идеала равен нулю.

Вычисляем кубичную форму h₃ вблизи точки $({{y}_{3}},{{z}_{3}})$:

и их результант (5.24), который оказывается равен с точностью до постоянного множителя т.е. отличен от нуля. Следовательно, применима теорема 6. Ищем квадратичную форму (5.31) в виде $a{{(\zeta - b\eta )}^{2}}$ для того, чтобы получилась полиномиальная по y₃ замена переменных $\zeta = \tau + b\eta $. Тогда кубичная форма (5.32) в новых переменных $\eta $, $\tau $ примет вид ${{h}_{3}}({{y}_{3}} + \eta ,{{z}_{3}} + \tau + b\eta ) = a{{\tau }^{2}} - c{{\eta }^{3}} + \; \ldots $. Здесь a, $b$, $c$ – полиномы от y₃, а точками обозначены мономы, содержащие $\eta $ в степени 2 и менее. Тогда укороченный многочлен, соответствующий ребру выпуклой оболочки h с нормалью из конуса задачи ${{\mathcal{K}}_{3}}$ есть $a{{\tau }^{2}} - c{{\eta }^{3}}$. Следовательно, получаем разложение ветвей в окрестности точки $({{y}_{3}},{{z}_{3}})$ в виде

Вычисления по модулю идеала $\mathcal{G}\mathcal{B}\mathcal{J}$ приводят к следующим результатам:

Поскольку $c < 0$, то $\eta < 0$ и разложение в переменных $y$, $z$ принимает вид

при $y \leqslant {{y}_{3}} \approx 2.342744299$.

Шаг 4. Ребрам $\Gamma _{2}^{{(1)}}$ и $\Gamma _{5}^{{(1)}}$ соответствуют укороченные многочлены

Их нули дают координаты пересечения кривой $\mathcal{F}$ с осями $Oz$ и $Oy$ соответственно. Многочлен $\hat {h}_{2}^{{(1)}}$ имеет два вещественных корня: 0 и $2.747016946$, а многочлен $\hat {h}_{5}^{{(1)}}$ – только корень 0.

Шаг 5. Ребру $\Gamma _{4}^{{(1)}}$ соответствует укороченный многочлен $\hat {h}_{4}^{{(1)}} = 250{{y}^{4}}(10z - 27)$. Значит при $y \to \infty $ имеем $z \to 27{\text{/}}10$. Применяя технику пункта 5.3, находим разложение ветви кривой на бесконечности:

Итак, кривая $\mathcal{F}$ имеет горизонтальную асимптоту.

Стремящейся к $\infty $ координате z в многоугольнике Γ соответствует верхняя вершина, т.е. при $z = \infty $ нет точек кривой $\mathcal{F}$.

Шаг 6. Конусам задач ${{\mathcal{K}}_{1}}$ и ${{\mathcal{K}}_{2}}$ соответствуют только вершины многоугольника Ньютона рис. 12.

Шаг 7. Ребру $\Gamma _{3}^{{(1)}}$ соответствует укороченный многочлен

который не имеет нетривиальных вещественных корней. Следовательно, ветвей соответствующих конусу задачи ${{\mathcal{K}}_{1}} = {\text{\{ }}P:{{p}_{1}} > 0,\;{{p}_{2}} > 0{\text{\} }}$ нет.

Шаг 8. Теперь имеется достаточно информации для построения эскиза кривой, который приведен на рис. 13. На нем показан график кривой $\mathcal{F}$ кроме точки $({{y}_{2}},{{z}_{2}}) = (14,\;27)$. Вблизи особых точек $({{y}_{1}},{{z}_{1}})$ и $({{y}_{3}},{{z}_{3}})$ пунктиром показаны ветви, вычисленные приближенно, и асимптота z = 2.7.

Рассмотрим другой способ вычисления особых точек кривой $\mathcal{F}$ и ее разложения в их окрестностях. Этот способ существенно использует систему компьютерной алгебры Maple и, в частности, пакет algcurves из нее. Особенность пакета algcurves состоит в том, что все вычисления по умолчанию производятся в поле комплексных чисел $\mathbb{C}$, что требует дополнительных усилий при исследовании вещественных кривых.

Функция genus из указанного выше пакета позволяет вычислить род кривой $\mathcal{F}$ с помощью команды genus(F,y,z). Ее род оказывается равным 0, т.е. эта кривая допускает рациональную параметризацию. Функция parametrization пакета algcurves позволяет вычислить эту рациональную параметризацию. Однако ее непосредственное применение приводит к очень громоздкому результату (здесь он не приводится), слабо пригодному для дальнейших вычислений. Последующие упрощения полученного в результате выражения приводят к параметризации кривой $\mathcal{F}$ в виде

Кривая $\mathcal{F}$ на рис. 13 построена с использованием этих формул.

Особые точки кривой могут быть вычислены с использованием функции singularities(F,y,z), но в нашем случае часть из них представляется в виде алгебраических чисел. Покажем, как найти такие точки используя только вычисленную выше параметризацию (5.33) кривой $\mathcal{F}$.

Особые точки кривой – это точки,

1. в которых либо обе производные одновременно обращаются в нуль: $y{\text{'}}(s) = z{\text{'}}(s) = 0$,

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

В случае 1 вычисления приводят к уравнению

которое имеет два вещественных корня ${{s}_{1}} = 0$, ${{s}_{3}} \approx - 85.62562644$. Эти значения параметра s определяют особые точки $({{y}_{1}},{{z}_{1}})$ и $({{y}_{3}},{{z}_{3}})$ соответственно.

В случае 2 выполняем подстановку $s = u + i{v}$ в (5.33) и решаем систему ${\text{Im}}y(u\, + \,i{v}) = {\text{Im}}z(u\, + \,i{v})$ = 0, ${v} \ne 0$. Ее решения суть ${{s}_{2}} = - 1{\text{/}}3 \pm i\sqrt {35} {\text{/}}3$ и ${{s}_{4}} = - 3{\text{/}}5 \pm i9{\text{/}}5$. Значению s₂ соответствует особая точка $({{y}_{2}},{{z}_{2}})$, а значению ${{s}_{4}}$ – бесконечно-удаленная точка $( \pm \infty ,0)$.

Наконец, зная координаты особых точек и параметризацию (5.33), можно вычислить разложение ветвей кривой $\mathcal{F}$ в их окрестности с использованием команды series. Так, например, для точки $({{y}_{1}},{{z}_{1}})$ это разложение имеет вид

что согласуется с разложением (5.29), полученным выше.

В заключение отметим, что непосредственное применение процедуры puisex из пакета algcurves приводит к результатам, где разложения кривой представлены в виде громоздких выражений от алгебраических чисел – корней соответствующего уравнения третьей степени, задающего особые точки. В такой форме использовать полученные ряды для визуализации кривой и численных расчетов фактически невозможно.