Журнал вычислительной математики и математической физики, 2022, T. 62, № 7, стр. 1085-1099

ВВЕДЕНИЕ

Вещественной гиперэллиптической кривой называется компактная кривая, аффинная часть которой задается уравнением ${{y}^{2}} = P(x)$, $(x,y) \in {{\mathbb{C}}^{2}}$, где $P(x)$ – вещественный многочлен без кратных корней. Вычисления, связанные с такими кривыми и их модулями, возникают во многих прикладных задачах, среди которых чебышёвская оптимизация (расчет оптимальных многополосных фильтров [1], расчет многочленов Чебышёва для нескольких отрезков [2], [3]), нахождение алгеброгеометрических решений нелинейных уравнений математической физики [4], описание магнитных состояний в планарных магнитных наноэлементах [6], моделирование течения воды под ступенчатой плотиной [6], высокоточный расчет емкостей конденсаторов сложной формы [7] и другие. Один из инструментов для таких вычислений – модель Шоттки [3], [4], позволяющая на практике работать с кривыми высоких родов.

В модели Шоттки кривая представляется как многообразие орбит действия подходящей группы Шоттки. Дифференциалы, функции и другие теоретико-функциональные объекты на кривой при этом получают явные представления – в виде тета-рядов Пуанкаре и бесконечных произведений. Члены таких рядов и произведений индексируются множеством элементов группы Шоттки. Численный расчет возникающих произведений по существу не отличается от приближенного суммирования рядов Пуанкаре, поэтому можно говорить только о рядах.

Группа Шоттки является свободной группой на $g \geqslant 1$ образующих, где $g$ – это род порождаемой кривой. Граф Кэли такой группы имеет вид бесконечного дерева с вершинами валентности $2g$. Вершины дерева Кэли взаимно однозначно соответствуют элементам группы Шоттки, а значит, и членам ряда Пуанкаре. Для приближенного суммирования ряда Пуанкаре возникает следующая задача: из бесконечного дерева Кэли требуется выделить конечное поддерево, сумма по которому хорошо приближает точное значение. Задача осложняется тем, что скорость убывания членов ряда вдоль разных ветвей дерева может значительно отличаться. Для выделения конечного поддерева, по которому ведется счет, известны два эффективных алгоритма: алгоритм Богатырёва [2], [3] с апостериорной оценкой точности и алгоритм Шмиза [9] с априорной оценкой точности. В обоих алгоритмах выделяемое поддерево заранее неизвестно и формируется непосредственно в процессе вычислений.

Ряды Пуанкаре быстро сходятся, если радиусы граничных окружностей фундаментальной области группы Шоттки невелики по сравнению с расстояниями между ними. При сближении окружностей или увеличении радиусов, а также при увеличении рода $g$, сходимость рядов замедляется и известным алгоритмам может требоваться значительное расчетное время для их приближенного суммирования. В настоящей статье предложены новые алгоритмы – модификации алгоритмов А.Б. Богатырёва и М. Шмиза, позволяющие в несколько раз сократить объем вычислений в ситуациях медленной сходимости и на десятки процентов в обычных ситуациях.

И алгоритм Богатырёва, и алгоритм Шмиза, и новые алгоритмы основываются на оценке для суммы членов ряда Пуанкаре по поддереву потомков заданной вершины через член ряда в этой вершине. Если член ряда в некоторой вершине достаточно мал, то такая оценка позволяет исключить из счета все растущее из этой вершины поддерево потомков. Оценка Богатырёва [3] уступает в точности оценке Бёрнсайда [8], [9], использованной Шмизом, однако последняя не всегда применима – а лишь в тех случаях, когда выполнен некоторый критерий на группу Шоттки. В настоящей работе получена новая оценка, восполняющая отсутствие практичной оценки для ситуаций, когда не применима оценка Бёрнсайда.

Отметим, что существует также альтернативный подход к вычислению теоретико-функциональных объектов в модели Шоттки, не связанный с непосредственным суммированием рядов Пуанкаре, а использующий ряды Лорана – метод типа коллокаций Д. Крауди, Дж. Маршалла, Н. Трефтена [10].

1. МОДЕЛЬ ШОТТКИ

Зафиксируем натуральное число $g$ и разбиение множества индексов от $1$ до $g$ на два подмножества: $\left\{ {1,2, \ldots ,g} \right\} = {{\Sigma }^{ + }} \sqcup {{\Sigma }^{ - }}$. На $g$ непересекающихся отрезках положительной полуоси как на диаметрах построим окружности ${{C}_{1}}, \ldots ,{{C}_{g}}$. Нумерация окружностей – слева направо. На всякой окружности ${{C}_{j}}$ отметим пару точек: при $j \in {{\Sigma }^{ + }}$ отметим точки пересечения с вещественной осью $u_{j}^{ \pm }: = {{c}_{j}} \pm {{r}_{j}}$, при $j \in {{\Sigma }^{ - }}$ – произвольную пару комплексно-сопряженных точек $u_{j}^{ \pm }: = {{c}_{j}} \pm i{{r}_{j}}$. Обозначим через ${{G}_{j}}$ конформную инволюцию сферы Римана с неподвижными точками $u_{j}^{ \pm }$:

Отображение ${{G}_{j}}$ переводит внешность окружности ${{C}_{j}}$ в ее внутренность, следовательно, гиперболическое преобразование ${{S}_{j}}u: = {{G}_{j}}( - u)$ переводит внешность окружности ${{C}_{{ - j}}}: = - {{C}_{j}}$ во внутренность ${{C}_{j}}$. Преобразования ${{S}_{1}}, \ldots ,{{S}_{g}}$ свободно порождают группу Шоттки, которую обозначим через $\mathfrak{S}$. Стандартная фундаментальная область $\mathcal{F}$ этой группы – это внешность $2g$ окружностей ${{C}_{1}}, \ldots ,{{C}_{g}},$ ${{C}_{{ - 1}}}, \ldots ,{{C}_{{ - g}}}$ в сфере Римана (фиг. 1). По группе Шоттки $\mathfrak{S}$ при $j \in {{\Sigma }^{ + }}$ окружность ${{C}_{j}}$ восстанавливается однозначно, ${{c}_{j}}$ и ${{r}_{j}}$ – это ее центр и радиус, а при $j \in {{\Sigma }^{ - }}$ в положении окружности ${{C}_{j}}$ имеется произвол. Фактор-пространство $X = \bar {\mathcal{F}}{\text{/}}{\kern 1pt} \sim $, где отношение эквивалентности склеивает пары граничных окружностей ${{C}_{{ - j}}}$, ${{C}_{j}}$ посредством преобразований ${{S}_{j}}$ при всех $1 \leqslant j \leqslant g$, является вещественной гиперэллиптической кривой рода $g$, на которой ${\text{|}}{{\Sigma }^{ + }}{\text{|}} + 1$ вещественных овалов и столько же ковещественных. Всякая такая кривая может быть получена в результате проделанной геометрической конструкции [11], [3]. Для кривой, заданной уравнением ${{y}^{2}} = P(x)$, построить соответствующую группу Шоттки позволяют алгоритмы численной униформизации, например классический алгоритм “раскрытия кружков” [12], восходящий к А. Пуанкаре [13]. При этом число ${\text{|}}{{\Sigma }^{ - }}{\text{|}}$ равно числу пар комплексно-сопряженных невещественных корней у $P(x)$, степень этого многочлена равна $2g + 1$ или $2g + 2$.

Эффективная теория функций на кривой в модели Шоттки строится на основе тета-рядов Пуанкаре [3], [4]. Так, ключевой объект теории – нормированный абелев дифференциал III рода ${{\eta }_{{zw}}}$ с полюсами в точках $z,w \in \bar {\mathcal{F}}$ – получается усреднением по группе Шоттки рационального дифференциала на римановой сфере:

Почленное равенство двух сумм вытекает из инфинитезимальной формы тождества двойного отношения. Ряды абсолютно сходятся, поскольку фундаментальная область $\mathcal{F}$ группы Шоттки рассматриваемого вида удовлетворяет критерию Шоттки. Сходящимися бесконечными суммами и произведениями записываются и другие аналитические объекты на кривой: мероморфные функции, мероморфные дифференциалы различных порядков, спиноры. Эта статья – о приближенном вычислении таких выражений на компьютере. Всю необходимую технику продемонстрируем на примере правого ряда из цепочки равенств (1).

2. ПОДХОДЫ БОГАТЫРЁВА И ШМИЗА

Введем обозначения ${{S}_{{ - j}}}: = S_{j}^{{ - 1}}$, ${\kern 1pt} {{c}_{{ - j}}}: = - {{c}_{j}}$, ${\kern 1pt} {{r}_{{ - j}}}: = {{r}_{j}}$, ${\kern 1pt} {{\sigma }_{{ - j}}}: = {{\sigma }_{j}}$ при $1 \leqslant j \leqslant g$. Тогда можем записать ${{S}_{j}}u = {{c}_{j}} - {{\sigma }_{j}}r_{j}^{2}{\text{/}}(u + {{c}_{j}})$ при всех $j \in \Xi : = \left\{ { \pm 1, \ldots , \pm g} \right\}$. Группа Шоттки $\mathfrak{S}$ изоморфна группе несократимых слов алфавита $\left\{ {{{S}_{j}} | j \in \Xi } \right\}$ с операцией конкатенации. Обозначим через ${\text{|}}S{\text{|}}$ количество букв в несократимой записи слова $S \in \mathfrak{S}$. Будем говорить, что слово $S \ne {\text{id}}$, начинается (соответственно заканчивается) на букву ${{S}_{j}}$, если эта буква – крайняя левая (соответственно крайняя правая) в несократимой записи слова $S$. Определим на $\mathfrak{S}$ отношение строгого частичного порядка: $S < T$, если имеет место запись $T = QS$, в которой $Q \ne {\text{id}}$ и ${\text{|}}T{\text{|}} = {\text{|}}Q{\text{|}}\; + \;{\text{|}}S{\text{|}}$. Введем на $\mathfrak{S}$ также отношение лексикографического порядка:

• для букв алфавита зафиксируем порядок ${{S}_{j}} \prec {{S}_{l}}$ при $j < l$;

• если у несократимых слов $S$ и $T$, каждое из которых имеет длину не меньше $n + 1$, первые $n$ букв справа совпадают, а $(n + 1)$-я буква справа у слова $S$ меньше, тогда $S \prec T$;

• если $S < T$, то $T \prec S$.

Дерево Кэли (фиг. 2) наглядно представляет множество элементов группы Шоттки. Вершины этого дерева взаимно-однозначно соответствуют элементам группы. Всякая вершина $S$ соединена ребрами с вершинами ${{S}_{j}}S, j \in \Xi $. Корень дерева Кэли – вершина, отвечающая тождественному преобразованию. Множество $\left\{ {S \in \mathfrak{S}\,:{\text{|}}S{\text{|}} = n} \right\}$ будем называть $n$-м уровнем дерева. Вершины, соединенные с $S$ ребром и лежащие на следующем уровне по сравнению c $S$, – это дети вершины $S$. При $S \ne {\text{id}}$ имеется одна вершина, соединенная с $S$ ребром и лежащая на предыдущем уровне, – будем называть ее родителем $S$. Назовем вершины братьями, если у них общий родитель. Если $T < S$, то вершину $S$ будем называть потомком вершины $T$, а вершину $T$ – предком вершины $S$.

Образ $S\mathcal{F}$ фундаментальной области при $S \ne {\text{id}}$ – это открытый круг за вычетом $2g - 1$ вложенных в него замкнутых кругов. Если $S$ заканчивается на букву ${{S}_{{ - j}}}$, тогда внешняя окружность области $S\mathcal{F}$ – это $S{{C}_{j}}$, внутренние – $S{{C}_{l}}$, $l \ne j$. Будем говорить, что внешняя окружность области $S\mathcal{F}$ – это окружность ${\text{|}}S{\kern 1pt} {\text{|}}$-го уровня. Например, окружности первого уровня – это ${{C}_{j}}$, $j \in \Xi $. Соседние с ${{C}_{j}}$ окружности первого уровня будем обозначать через ${{C}_{{ \leftarrow j}}}$ и ${{C}_{{j \to }}}$, т.е. положим $ \leftarrow j: = j - 1$ при $j \in \Xi {{\backslash }}\left\{ {1, - g} \right\}$, $ \leftarrow 1: = - 1$ и $ \leftarrow ( - g): = g$, а значение $j \to $ для всех $j \in \Xi $ определим из соотношения $( \leftarrow j) \to \; = j$.

Через $\operatorname{dist} ( \cdot , \cdot )$ обозначим евклидово расстояние между множествами, через ${\text{diam}}( \cdot )$ – евклидов диаметр множества.

Пусть точки $u,z,w \in \bar {\mathcal{F}}$ лежат в разных орбитах действия группы $\mathfrak{S}$. Аппроксимируем сумму правого ряда из равенств (1) суммой по конечному поддереву $\mathfrak{T} \subset \mathfrak{S}$:

где $\rho $ – евклидово расстояние от точки $u$ до объединения орбит точек $z$ и $w$. В качестве конечного поддерева $\mathfrak{T}$ можно выбрать множество $\left\{ {S \in \mathfrak{S}:{\text{|}}S{\text{|}} \leqslant n} \right\}$ с некоторым $n \geqslant 0$, т.е. несколько первых уровней дерева Кэли, взятых целиком. Такой подход предложен А.Б. Богатырёвым в работе [2] (1999) и имеет априорную оценку точности, которая получается из следующей теоремы.

Теорема 1 (см. [2], [3]). Пусть слово $S \in \mathfrak{S}$, $S \ne {\text{id}}$, начинается на букву ${{S}_{j}}$. Отношение суммы диаметров внутренних окружностей области $S\mathcal{F}$ к диаметру ее внешней окружности не превосходит $(\sqrt {{{\gamma }_{j}}} - 1){\text{/}}(\sqrt {{{\gamma }_{j}}} + 1)$, где

Определить число первых уровней дерева Кэли, по которым достаточно просуммировать для достижения произвольной заданной точности в рамках такого подхода, можно при помощи следующей оценки:

где $\gamma : = \mathop {\max }\nolimits_{1 \leqslant j \leqslant g} {{\gamma }_{j}}$. Этот подход, однако, существенно неэкономичен: вычислительная практика показывает, что скорость убывания членов ряда при движении от корня дерева Кэли вдоль разных ветвей может значительно отличаться, и в таком случае будет учтено большое число членов ряда, суммарный вклад которых пренебрежимо мал.

Другой подход, предложенный А.Б. Богатырёвым в той же работе [2], имеет апостериорную оценку точности. Граница поддерева $\mathfrak{T}$ в нем определяется по отдельности для каждой ветви – непосредственно в процессе вычислений. Пусть для всякого $T \in \mathfrak{S}$ известно число $K(T)$ такое, что $\sum\nolimits_{S \in \mathfrak{S}: \,S > T} {\text{|}}Sz - Sw{\text{|}} \leqslant K(T){\text{|}}Tz - Tw{\text{|}}$. Для простоты потребуем, чтобы $K(T)$ зависело только от первой слева буквы несократимого слова $T$. Будем добавлять вершины текущей ветви в поддерево $\mathfrak{T}$ (т.е. учитывать их в приближенном значении суммы) до тех пор, пока значение $K(T){\kern 1pt} {\text{|}}Tz - Tw{\kern 1pt} {\text{|}}$ в текущей вершине $T$ не меньше заранее выбранного малого параметра $\mu > 0$. Как только это значение станет меньше $\mu $, все поддерево потомков вершины $T$ исключим из счета и сместимся на другую ветвь – оценка для суммы выброшенных членов ряда известна. Реализуем такой подход на основе обхода в глубину.

Алгоритм 1. Реализация подхода Богатырёва с апостериорной оценкой точности

Зафиксируем малый параметр $\mu > 0$. Присвоим начальные значения переменным, в которых по окончании работы алгоритма будут записаны приближенное значение суммы и оценка погрешности, ${\text{sum}}: = (u - z{{)}^{{ - 1}}} - {{(u - w)}^{{ - 1}}}$ и ${\text{err}}: = 0$. Будем хранить в памяти массив со следующей структурой: в момент перехода в вершину $T = {{S}_{{{{i}_{{|T|}}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}}$ в $n$-й ячейке массива при $1 \leqslant n \leqslant {\text{|}}T{\kern 1pt} {\text{|}} - 1$ записаны значения $({{S}_{{{{i}_{n}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}})z$, $({{S}_{{{{i}_{n}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}})w$ и буква ${{S}_{{{{i}_{n}}}}}$, а в нулевой ячейке – числа $z$ и $w$. Перейдем в вершину ${{S}_{{ - g}}}$ и будем попеременно выполнять две операции:

1. Учет слагаемого, отвечающего текущей вершине. Пусть $T$ – вершина, в которую только что перешел алгоритм. Используя $({\text{|}}T{\text{|}} - 1)$-ю ячейку, вычислим значения $Tz$, $Tw$ и поместим их в ${\text{|}}T{\text{|}}$-ю ячейку вместе с буквой ${{S}_{{{{i}_{{|T|}}}}}}$. Прибавим слагаемое, отвечающее вершине $T$: ${\kern 1pt} {\text{sum}}: = {\text{sum}} + {{(u - Tz)}^{{ - 1}}} - {{(u - Tw)}^{{ - 1}}}.$

2. Переход к следующей вершине. Если ${\text{|}}Tz - Tw{\kern 1pt} {\text{|}} \geqslant \mu {\text{/}}K(T)$, то перейдем к наименьшему в лексикографическом порядке ребенку вершины $T$. В противном случае исключим из счета растущее из $T$ поддерево потомков, учтем его в текущей частичной оценке погрешности ${\text{err}}: = {\text{err}} + K(T){\text{|}}Tz - Tw{\kern 1pt} {\text{|}}$ и перейдем к наименьшей в лексикографическом порядке вершине $S$, удовлетворяющей условиям $T \prec S$ и ${\text{|}}S{\kern 1pt} {\text{|}} \leqslant {\text{|}}T{\kern 1pt} {\text{|}}$ (фиг. 3). Если такой вершины нет (тогда $T = S_{g}^{k}$ для некоторого $k \in \mathbb{N}$), алгоритм останавливается. Для эффективной навигации по дереву при поиске следующей вершины достаточно сохраненных в массиве букв.

По окончании работы алгоритма имеем оценку ${\kern 1pt} \left| {{{\eta }_{{zw}}}(u){\text{/}}du - {\text{sum}}} \right| \leqslant {{\rho }^{{ - 2}}} \cdot {\text{err}}.$

В статье М. Шмиза [9] (2005) на основе оценки для сумм ${\kern 1pt} \sum\nolimits_{S > T} \,{\text{|}}Sz - Sw{\kern 1pt} {\text{|/|}}Tz - Tw{\kern 1pt} {\text{|}}$ сформулирован подход жадного типа: на каждой итерации обрабатывается вершина с наибольшей оценкой вклада в сумму. Алгоритм имеет априорную оценку точности, однако конечное поддерево $\mathfrak{T}$, по которому ведется счет, также заранее неизвестно и формируется непосредственно в процессе вычислений.

Алгоритм 2. Реализация подхода Шмиза с априорной оценкой точности

Введем вес вершины ${\text{weight}}(T): = (K(T) + 1){\text{|}}Tz - Tw{\kern 1pt} {\text{|}}$. Зафиксируем целевую точность $\varepsilon > 0$. Поместим в память корень дерева Кэли и присвоим начальные значения переменным, в которых будут храниться текущее значение суммы ${\text{sum}}: = 0$ и текущая оценка погрешности ${\text{err}}: = {\text{weight}}({\text{id}})$. Для всякой сохраненной в памяти вершины $T$ будем помнить значения $Tz$, $Tw$, ${\text{weight}}(T)$ и первую слева букву слова $T$.

Итерация алгоритма: удалить из памяти вершину $T$ с максимальным весом, поместить в память ее детей и присвоить

После каждой итерации выполнена оценка $\left| {{{\eta }_{{zw}}}(u){\text{/}}du - {\text{sum}}} \right| \leqslant {{\rho }^{{ - 2}}} \cdot {\text{err}}$ и в памяти хранятся все неучтенные в сумме дети уже учтенных вершин и только они. Алгоритм останавливается, как только правая часть оценки становится меньше $\varepsilon $ – это произойдет за конечное число итераций. Для организации хранения вершин в памяти следует использовать структуру данных, позволяющую извлекать элемент с максимальным весом за логарифмическое время, например двоичную кучу.

Алгоритм 3

Жадный подход М. Шмиза можно реализовать другим способом, в котором веса вычисляются только для просуммированных вершин. Для этого вес всякой вершины $T \in \mathfrak{S}$ определим иначе – как $K(T){\text{|}}Tz - Tw{\text{|}}$. Вес вычисляется для каждой вершины, которая сохраняется в память. На каждой итерации из памяти удаляется вершина с максимальным весом, вместо нее в память помещаются все ее дети и сразу учитываются в сумме. После каждой итерации в памяти хранятся все листья поддерева просуммированных вершин, погрешность оценивается через сумму весов сохраненных вершин.

При одинаковой оценке точности на выходе число просуммированных вершин у алгоритма Шмиза в реализации 3 не больше, чем у алгоритма Богатырёва в реализации 1, и в большинстве случаев эти числа равны. Действительно, подадим на вход алгоритму Богатырёва в качестве параметра $\mu $ минимальный вес среди тех вершин, просуммированных алгоритмом Шмиза в реализации 3, дети которых также просуммированы. При таком $\mu $ алгоритм Богатырёва обойдет ровно то же конечное поддерево $\mathfrak{T}$, что и алгоритм Шмиза в реализации 3, – в предположении, что в дереве Кэли нет сразу нескольких вершин с весом, равным $\mu $.

Необходимый ингредиент и для апостериорного подхода Богатырёва, и для подхода Шмиза – оценка для сумм $\sum\nolimits_{S > T} \,{\text{|}}Sz - Sw{\kern 1pt} {\text{|/|}}Tz - Tw{\kern 1pt} {\text{|}}$. Первый способ получения такой оценки, по существу, присутствует в работе У. Бёрнсайда 1891 г. [8] и развит М. Шмизом [9]. Этот способ применим, только если выполнен определенный критерий на группу Шоттки.

Теорема 2. Пусть слово $T \in \mathfrak{S}$, $T \ne {\text{id}}$, начинается на букву ${{S}_{t}}$. Положим ${{L}_{{jk}}}: = r_{j}^{2}{\text{/dis}}{{{\text{t}}}^{2}}({{c}_{j}},{{C}_{k}})$ и ${{\lambda }_{k}}: = \sum\nolimits_{j \in \Xi : j \ne k} \,{{L}_{{jk}}}$. При выполнении условия $\lambda : = {{\max }_{{1 \leqslant k \leqslant g}}}{{\lambda }_{k}} < 1$ имеет место оценка

Доказательство. При $j \ne t$, используя явный вид преобразования ${{S}_{j}}$, запишем

Сумма членов ряда $\sum\nolimits_{S > T} \,{\text{|}}Sz - Sw{\kern 1pt} {\text{|/|}}Tz - Tw{\kern 1pt} {\text{|}}$, отвечающих детям вершины $T$, не превосходит ${{\lambda }_{t}}$; сумма членов, отвечающих внукам $T$ (детям детей), не превосходит $\lambda \cdot {{\lambda }_{t}}$; и так далее. Оценивая через геометрическую прогрессию при условии $\lambda < 1$, приходим к утверждению теоремы.

В цепочке неравенств (3) для локализации точек $Tz$, $Tw$ вместо окружностей первого уровня можно использовать окружности больших уровней – вплоть до ${\text{|}}T{\kern 1pt} {\text{|}}$-го. Тогда для константы ${{L}_{{jt}}}$ получится определение ${{L}_{{jt}}}: = r_{j}^{2}{\text{/dis}}{{{\text{t}}}^{2}}({{c}_{j}},C)$, где $C$ – ближайшая к ${{C}_{j}}$ окружность нужного уровня, лежащая внутри ${{C}_{t}}$; в остальном формулировка теоремы 2 останется без изменений. Это уточнит оценку Бёрнсайда и расширит ее область применимости, однако, как нетрудно видеть, существуют группы Шоттки, для которых критерий применимости $\lambda < 1$ не выполнен при использовании сколь угодно большого уровня.

Другой способ оценки суммы по поддереву потомков некоторой вершины через член ряда в этой вершине предложен А.Б. Богатырёвым (2005). Через $\Lambda $ обозначим предельное множество группы Шоттки $\mathfrak{S}$.

Теорема 3 (см. [3]). При $A \in \mathfrak{S}$, $A \ne {\text{id}}$, существуют числа ${{E}_{1}}(A)$ и ${{E}_{2}}(A)$, обладающие асимптотиками

такие, что выполнены двусторонние неравенства Пусть ${{E}_{1}}: = \mathop {\max }\nolimits_{A \ne {\text{id}}} {{E}_{1}}(A)$ и ${{E}_{2}}: = \mathop {\max }\nolimits_{A \ne {\text{id}}} {{E}_{2}}(A)$. Тогда при $T \ne {\text{id}}$ имеет место оценка

Недостаток такой оценки заключается в следующем: если устремить к нулю радиус какой-либо из окружностей ${{C}_{1}}, \ldots ,{{C}_{g}}$, не меняя остальные параметры, скорость сходимости ряда будет возрастать, а оценка, напротив, будет ухудшаться – константа ${{K}^{{(2)}}}$ будет стремиться к бесконечности. К примеру, при $g \geqslant 2$ и ${{\Sigma }^{ - }} = \emptyset $ зафиксируем числа ${{c}_{1}}$, ${{c}_{2}}$, ${{r}_{1}}$ и устремим к нулю ${{r}_{2}}$, тогда отношение ${\text{diam}}({{S}_{1}}{{S}_{2}}\mathcal{F}){\text{/diam}}(S_{2}^{{ - 1}}S_{1}^{{ - 1}}\mathcal{F})$ будет стремиться к бесконечности. На основе выкладок из [3, § 6.1.3] можно подобрать следующие константы под условия теоремы 3:

где за $p_{j}^{ - } < p_{j}^{ + }$ обозначены точки пересечения окружности ${{C}_{j}}$ с вещественной осью. Вычислительная практика показывает, что если оценка Бёрнсайда применима, то она значительно точнее оценки Богатырёва при таком выборе ${{E}_{1}}$ и ${{E}_{2}}$. Преимущество же оценки Богатырёва – в универсальности, тогда как область применимости оценки Бёрнсайда ограничена условием $\lambda < 1$.

3. МОДИФИКАЦИЯ АЛГОРИТМОВ

Заметим, что в алгоритме А.Б. Богатырёва (реализация 1) на основании значения $K(T){\text{|}}Tz - Tw{\text{|}}$ принимается решение об учете в сумме (т.е. о добавлении в конечное поддерево $\mathfrak{T}$) сразу всех детей вершины $T$. Это приводит к тому, что часть листьев поддерева $\mathfrak{T}$ вносит пренебрежимо малый вклад в сумму. Листовых вершин при $\mathfrak{T} \supset \left\{ {S \in \mathfrak{S}:\;{\text{|}}S{\text{|}} < n} \right\}$, $n \to \infty $ и $g > 1$ в $2g - 2$ раза больше, чем нелистовых. Особенно много неэффективной работы алгоритм производит в ситуациях, когда какие-либо из окружностей первого уровня критически близки друг к другу. В этом случае в дереве Кэли присутствуют длинные ветви, у большинства вершин которых ровно один из $2g - 1$ детей вносит весомый вклад в сумму.

Автором предложена следующая модификация: решение об учете в сумме будем принимать по отдельности для каждого ребенка ${{S}_{{ - j}}}T$ вершины $T$, при этом будем использовать оценку значения ${\text{|}}{{S}_{{ - j}}}Tz - {{S}_{{ - j}}}Tw{\text{|}}$ через значение ${\text{|}}Tz - Tw{\text{|}}$. Подходящая оценка уже встречалась: ${\text{|}}{{S}_{{ - j}}}Tz - {{S}_{{ - j}}}Tw{\text{|}} \leqslant {{L}_{{jt}}}{\text{|}}Tz - Tw{\text{|}}$, где $t \ne j$ – это индекс крайней слева буквы ${{S}_{t}}$ несократимого слова $T \ne {\text{id}}$. Положим $M({{S}_{{ - j}}}T): = (K({{S}_{{ - j}}}T) + 1){{L}_{{jt}}}$. Для вершин первого уровня положим $M({{S}_{{ - j}}}): = (K({{S}_{{ - j}}}) + 1)r_{j}^{2}{\text{/|}}(z - {{c}_{j}})(w - {{c}_{j}}){\text{|}}$. Будем добавлять ребенка ${{S}_{{ - j}}}T$ вершины $T$ в поддерево $\mathfrak{T}$, если ${\text{|}}Tz - Tw{\text{|}} \geqslant \mu {\text{/}}M({{S}_{{ - j}}}T)$, где $\mu $ – фиксированный малый параметр.

Для братьев ${{T}_{1}}$ и ${{T}_{2}}$ (т.е. вершин с общим родителем) определим старшинство следующим образом: ${{T}_{1}}$ старше ${{T}_{2}}$, если $M({{T}_{2}}) < M({{T}_{1}})$. Обозначим через $\mathfrak{B}(S)$ множество, состоящее из самой вершины $S$ и ее младших братьев. Для несократимых слов ${{T}_{1}}$ и ${{T}_{2}}$, у которых подслова из $n \geqslant 1$ справа букв являются братьями, определим старшинство так: ${{T}_{1}}$ старше ${{T}_{2}}$, если указанное подслово у ${{T}_{1}}$ старше, чем у ${{T}_{2}}$.

Алгоритм 4

Зафиксируем малый параметр $\mu > 0$. Присвоим начальные значения переменным, в которых по окончании работы алгоритма будут записаны приближенное значение суммы и оценка погрешности, ${\text{sum}}: = (u - z{{)}^{{ - 1}}} - {{(u - w)}^{{ - 1}}}$ и ${\text{err}}: = 0$. Будем хранить в памяти массив со следующей структурой: в момент перехода в вершину $T = {{S}_{{{{i}_{{|T|}}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}}$ в $n$-й ячейке массива при $1 \leqslant n \leqslant {\text{|}}T{\text{|}} - 1$ записаны числа $({{S}_{{{{i}_{n}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}})z$, ${\kern 1pt} ({{S}_{{{{i}_{n}}}}} \ldots {{S}_{{{{i}_{2}}}}}{{S}_{{{{i}_{1}}}}})w$ и модуль разности между ними, а также буква ${{S}_{{{{i}_{n}}}}}$, в нулевой ячейке – числа $z$, $w$ и ${\text{|}}z - w{\text{|}}$. Перейдем в самую старшую вершину первого уровня. Итерацию алгоритма удобно разбить на два шага:

1. Учет слагаемого, отвечающего текущей вершине. Пусть $T$ – вершина, в которую только что перешел алгоритм. Используя $({\text{|}}T{\text{|}} - 1)$-ю ячейку, вычислим значения $Tz$, $Tw$, ${\text{|}}Tz - Tw{\text{|}}$ и поместим их в ${\text{|}}T{\text{|}}$-ю ячейку вместе с буквой ${{S}_{{{{i}_{{|T|}}}}}}$. Прибавим слагаемое, отвечающее вершине $T$: ${\kern 1pt} {\text{sum}}: = {\text{sum}} + {{(u - Tz)}^{{ - 1}}} - {{(u - Tw)}^{{ - 1}}}.$

2. Переход к следующей вершине. Пусть алгоритм находится в вершине $T$. Найдем следующую вершину рекурсивной процедурой поиска. Вначале за $\mathfrak{A}$ обозначим множество, состоящее из детей вершины $T$, а также из младших, чем вершина $T$, детей ее предков. Пусть $S$ – самая старшая вершина во множестве $\left\{ {A \in \mathfrak{A}:\;{\text{|}}A{\kern 1pt} {\text{|}} = \mathop {\max }\nolimits_{U \in \mathfrak{A}} {\text{|}}U{\text{|}}} \right\}$. Если выполнено неравенство ${\text{|}}Qz - Qw{\kern 1pt} {\text{|}} \geqslant \mu {\text{/}}M(S)$, где $Q$ – родитель $S$, то поиск закончен – перейдем от $T$ к $S$. Иначе учтем вершину $S$ и всех ее младших братьев вместе с поддеревьями потомков в текущей частичной оценке погрешности ${\text{err}}: = {\text{err}}\; + \;{\text{|}}Qz - Qw{\text{|}}{\kern 1pt} \sum\nolimits_{B \in \mathfrak{B}(S)} M(B)$, переобозначим $\mathfrak{A}: = \mathfrak{A}{{\backslash }}\mathfrak{B}(S)$ и повторим процедуру поиска с новым $\mathfrak{A}$. Если $\mathfrak{A} = \emptyset $, алгоритм останавливается. Для эффективной навигации по дереву при поиске следующей вершины достаточно сохраненных в массиве букв.

По окончании работы алгоритма имеем оценку ${\kern 1pt} \left| {{{\eta }_{{zw}}}(u){\text{/}}du - {\text{sum}}} \right| \leqslant {{\rho }^{{ - 2}}} \cdot {\text{err}}.$

Жадный подход М. Шмиза в реализации 3, как и алгоритм А.Б. Богатырёва, предполагает принятие решения об учете в сумме сразу всех детей вершины $T$ на основании веса $K(T){\text{|}}Tz - Tw{\text{|}}$, т.е. разделяет ту же неэкономичность: часть листьев обработанного поддерева вносит пренебрежимо малый вклад в сумму. А в реализации 2 все вершины, находящиеся в памяти в момент достижения нужной точности, не будут учтены в сумме, при этом для каждой такой вершины $T$ вычислены значения $Tz$, $Tw$ и вес $(K(T) + 1){\text{|}}Tz - Tw{\text{|}}$. Таких вершин при $\mathfrak{T} \supset \left\{ {S \in \mathfrak{S}:\;{\text{|}}S{\text{|}} < n} \right\}$, $n \to \infty $ и $g > 1$ в $2g - 2$ раза больше, чем вершин в $\mathfrak{T}$. Избежать вычисления указанных значений для еще не учтенных в сумме вершин можно, если в определении веса вершины ${{S}_{{ - j}}}T$ использовать не само значение $|{\kern 1pt} {{S}_{{ - j}}}Tz - {{S}_{{ - j}}}Tw{\kern 1pt} |$, а его оценку через значение ${\text{|}}Tz - Tw{\text{|}}$.

Алгоритм 5

Введем вес вершины ${\text{weight}}(T): = M(T){\text{|}}Qz - Qw{\text{|}}$ при $T \ne {\text{id}}$, где $Q$ – родитель $T$. Тогда во всякой паре братьев больший вес имеет тот, который старше. Зафиксируем целевую точность $\varepsilon > 0$. Присвоим начальные значения переменным, в которых будут храниться текущее значение суммы и текущая оценка погрешности, ${\text{sum}}: = (u - z{{)}^{{ - 1}}} + {{(u - w)}^{{ - 1}}}$ и ${\text{err}}: = \sum\nolimits_{j \in \Xi } \,{\text{weight}}({{S}_{j}})$. Сохраним в памяти самую старшую вершину первого уровня. Для всякой сохраненной в памяти вершины $T$ будем помнить значения $Qz$, $Qw$, ${\text{|}}Qz - Qw{\text{|}}$, где $Q$ – родитель $T$, а также ${\text{weight}}(T)$ и две первых слева буквы слова $T$. Таким образом, чтобы сохранить в памяти вершину $T$, не нужно вычислять значения $Tz$, $Tw$, вместо них используются значения $Qz$, $Qw$, в том числе при подсчете веса $T$.

Итерация алгоритма: удалить из памяти вершину $T$ с максимальным весом, поместить в память ее старшего ребенка, а также, если $T$ не самый младший среди братьев, следующего по старшинству брата, и присвоить

Алгоритм останавливается, как только число ${{\rho }^{{ - 2}}} \cdot {\text{err}}$ становится меньше целевой точности $\varepsilon $ – это произойдет за конечное число итераций. Для организации хранения вершин в памяти имеет смысл использовать специальные структуры данных, например, двоичную кучу, позволяющую извлекать элемент с максимальным весом за логарифмическое время.

При одинаковой оценке точности на выходе число просуммированных вершин у алгоритма 5 (модифицированного алгоритма Шмиза) не больше, чем у алгоритма 4 (модифицированного алгоритма Богатырёва), и в большинстве случаев эти числа равны – ситуация ровно та же, как и в случае алгоритма Богатырёва и алгоритма Шмиза в реализации 3. Чтобы в этом убедиться, запустим алгоритм 5 для произвольной целевой точности $\varepsilon $, запомним минимальный вес среди просуммированных вершин и подадим его на вход алгоритму 4 в качестве параметра $\mu $. В результате алгоритм 4 обойдет ровно то же конечное поддерево $\mathfrak{T}$ – в предположении, что в дереве Кэли нет сразу нескольких вершин с весом, равным $\mu $.

Отметим, что для алгоритма 4 перед началом итераций необходимо вычислить и запомнить (кэшировать) значения $\varepsilon {\text{/}}M({{S}_{j}}T)$ и $\sum\nolimits_{B \in \mathfrak{B}({{S}_{j}}T)} \,M(B)$ для всех комбинаций первых двух слева букв несократимого слова ${{S}_{j}}T$, для алгоритма 5 – значения $M({{S}_{j}}T)$ и $\sum\nolimits_{j \in \Xi } \,M({{S}_{j}}T)$.

4. НОВАЯ ОЦЕНКА ДЛЯ СУММЫ ПО ПОДДЕРЕВУ ПОТОМКОВ

Теорема 4. Пусть слово $T \in \mathfrak{S}$, $T \ne {\text{id}}$, начинается на букву ${{S}_{t}}$. Имеет место оценка

Доказательство. Воспользуемся двумя тождествами, справедливыми для всех дробно-линейных преобразований $F$ и ${{z}_{1}},{{z}_{2}} \in \mathbb{C}$:

Запишем $S = AT$, где слово $A$ заканчивается на букву ${{S}_{{ - j}}}$, $j \ne t$. Имеем цепочку неравенств в которой ${{h}_{{tj}}}(x): = (x - p_{j}^{ - })(p_{j}^{ + } - x){\text{/}}({\text{diam}}({{C}_{j}}){\text{dis}}{{{\text{t}}}^{2}}(x,{{C}_{t}}))$. Максимум функции ${{h}_{{tj}}}(x)$ на отрезке $[p_{j}^{ - };p_{j}^{ + }] \ni {{A}^{{ - 1}}}\infty $ равен ${\text{diam}}({{C}_{j}}){\text{/}}(4({{p}_{{tj}}} - p_{j}^{ + })({{p}_{{tj}}} - p_{j}^{ - }))$ и достигается в точке ${{\tilde {G}}_{j}}{{p}_{{tj}}}$, где ${{p}_{{tj}}}$ – ближайшая к окружности ${{C}_{j}}$ точка окружности ${{C}_{t}}$, ${{\tilde {G}}_{j}}u: = {{\tilde {c}}_{j}} + \tilde {r}_{j}^{2}{\text{/}}(u - {{\tilde {c}}_{j}})$, ${\kern 1pt} {{\tilde {c}}_{j}}$ и ${{\tilde {r}}_{j}}$ – центр и радиус окружности ${{C}_{j}}$. Остается оценить сумму диаметров $\sum\nolimits_{A \in \mathfrak{S}:{\kern 1pt} \,AT > T} \,{\text{diam}}(A\mathcal{F})$ с помощью теоремы 2.

Для локализации точек $Tz$, $Tw$ используются окружности первого уровня. Уточнить новую оценку можно путем локализации этих точек с использованием окружностей большего уровня, как и оценку Бёрнсайда.

5. СРАВНЕНИЯ АЛГОРИТМОВ И ОЦЕНОК

Результаты сравнения алгоритмов приведены в табл. 1. Параметры примеров указаны в конце раздела (примеры 4–5). При сравнении алгоритмов величина $K(T)$ вычислялась следующим образом: при $\lambda < 1$ использовалось значение $K(T): = \min \{ K_{t}^{{(1)}},K_{t}^{{(3)}}\} $, при $\lambda \geqslant 1$ – значение $K(T): = K_{t}^{{(3)}}$, где $t$ – индекс крайней слева буквы ${{S}_{t}}$ несократимого слова $T \ne {\text{id}}$. Вместо значения ${{\rho }^{{ - 2}}}$ использовалась оценка сверху величины ${\text{|}}{{(u - Sz)}^{{ - 1}}}{{(u - Sw)}^{{ - 1}}}{\text{|}}$ при $u \in \mathcal{F}$ и $S \ne {\text{id}}$ – число ${\text{dis}}{{{\text{t}}}^{{ - 2}}}(u,\partial{ \mathcal{F}})$. В алгоритмах с апостериорной оценкой точности для малого параметра $\mu $, подаваемого на вход, подбиралось максимальное значение, с которым на выходе алгоритма достигается нужная точность $\varepsilon $. Под обработанной вершиной понимается вершина $T$, для которой вычислены значения $Tz$ и $Tw$. Во всех алгоритмах, кроме подхода Шмиза в реализации 2, каждая обработанная вершина учитывается в сумме, т.е. добавляется в поддерево $\mathfrak{T}$. Во всех рассмотренных примерах алгоритм Богатырёва и алгоритм Шмиза в реализации 3 обходили одинаковые конечные поддеревья дерева Кэли и обрабатывали одинаковое количество вершин, поэтому результаты для них объединены в одну колонку; по этой же причине объединены в одну колонку и оба новых алгоритма.

Рассмотренные примеры позволяют заключить, что при одинаковой оценке точности на выходе новые алгоритмы обрабатывают существенно меньшее число вершин, чем алгоритмы Богатырёва и Шмиза: на десятки процентов в обычных ситуациях и в несколько раз при больших $g$ или при наличии близких друг к другу граничных окружностей фундаментальной области. На фиг. 4 на двух примерах показано, как растет количество обработанных вершин с повышением точности: относительная разница между алгоритмами практически не меняется.

Модифицированный алгоритм Богатырёва (реализация 4) сопоставительно его обычной версии (реализация 1) для части вершин совершает одну лишнюю операцию сравнения двух вещественных чисел, но относительная сложность лишней операции незначительна, поскольку помимо этого обработка и учет в сумме вершины включают одно умножение вещественных чисел и следующие операции над комплексными числами: три деления, одно умножение, семь сложений и одно взятие модуля. Приближенно можно считать, что объемы вычислений, производимые этими алгоритмами, относятся как количества обработанных вершин. Так же и модифицированный алгоритм Шмиза (реализация 5) сопоставительно алгоритму Шмиза в реализации 3 совершает одно лишнее умножение двух вещественных чисел для части обработанных вершин. В этом случае относительная сложность лишней операции еще ниже, поскольку на каждой итерации совершается еще и дорогостоящее извлечение вершины с максимальным весом. В подходе Шмиза в реализации 2 большинство обработанных вершин не учитывается в сумме, а значит, для них совершается меньшее число арифметических операций, однако модифицированный алгоритм Шмиза выигрывает у этой реализации на заявленные значения и при подсчете точного числа арифметических операций.

Важно отметить, что модифицированный алгоритм Богатырёва затрачивает значительно меньшее расчетное время, чем модифицированный алгоритм Шмиза, несмотря на одинаковое число суммируемых вершин, поскольку не требует на каждой итерации поиска вершины с максимальным весом.

Отметим также, что алгоритм с априорной оценкой точности, в котором в качестве $\mathfrak{T}$ выступают несколько первых уровней дерева Кэли, взятых целиком, значительно уступает остальным алгоритмам в экономичности. При использовании оценки (2) для подсчета нужного числа уровней в примере 1 этот алгоритм просуммирует $5.38 \times {{10}^{7}}$ вершин, в примере 5 – $2.32 \times {{10}^{{15}}}$ вершин.

Результаты сравнения оценок – в табл. 2. В качестве оценки Бёрнсайда приводится значение ${{\max }_{{t \in \Xi }}}K_{t}^{{(1)}}$, в качестве новой оценки – значение $\mathop {\max }\nolimits_{t \in \Xi } K_{t}^{{(3)}}$. Оценка Богатырёва ${{K}^{{(2)}}}$ вычислялась при указанном выше выборе констант ${{E}_{1}}$ и ${{E}_{2}}$. Как видно из таблицы, новая оценка восполняет отсутствие практичной оценки для ситуаций, когда не применима оценка Бёрнсайда, т.е. когда $\lambda \geqslant 1$. Оценка Богатырёва при указанном выше выборе констант ${{E}_{1}}$ и ${{E}_{2}}$ на много порядков уступает новой оценке и, по сути, не применима в практических вычислениях. В ситуациях, когда константа $\lambda $ меньше единицы и не критически близка к ней, оценка Бёрнсайда точнее новой оценки – на 0.5–1.5 порядка. Тем самым, новая оценка нацелена на узкую сферу приложения – близкие к вырождению группы Шоттки. Такие группы возникают в практически важных задачах, например при расчете многополосных электрических фильтров методом чебышёвского анзаца [1].

Изложенная техника приближенного суммирования ряда для нормированного абелева дифференциала III рода ${{\eta }_{{zw}}}$ прямо распространяется и на другие бесконечные суммы и произведения,  которыми записываются теоретико-функциональные объекты на вещественной гиперэллиптической кривой в модели Шоттки.

Ниже приводятся параметры групп Шоттки, использованных для сравнений. Массивы, обозначенные символами $c$, $r$, $\sigma $, ${{p}^{ + }}$, ${{p}^{ - }}$, имеют длину $g$ – в них объединены значения соответствующих параметров для индексов $1, \ldots ,g$. Через $\varepsilon $ обозначена требуемая оценка точности на выходе алгоритмов. Для каждого из примеров, кроме последних двух, на рисунке изображена граница фундаментальной области. При непустом ${{\Sigma }^{ - }}$ точками на рисунке отмечены положения точек $ \pm {{c}_{j}} \pm {{r}_{j}}$ для $j \in {{\Sigma }^{ + }}$ и $ \pm {{c}_{j}} \pm i{{r}_{j}}$ для $j \in {{\Sigma }^{ - }}$.

Пример 1 (см. фиг. 5). $g = 5$, ${\kern 1pt} \sigma = (1$, $1,$ $1,$ $1,$ $1)$, ${\kern 1pt} c = (0.2$, $0.4$, $0.6$, $0.8$, $1)$, ${\kern 1pt} r = 0.01 \cdot (1$, $1,$ $1,$ $1,$ $1)$, ${\kern 1pt} u = 1 - 2i$, ${\kern 1pt} z = 3 + 5i$, ${\kern 1pt} w = - 2 - 4i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 10}}}$.

Пример 2 (см. фиг. 6). То же, что в примере 1, кроме $r = 0.05 \cdot (1,1,1,1,1)$ и $\varepsilon {{ = 10}^{{ - 7}}}$.

Пример 3 (см. фиг. 7). То же, что в примере 1, кроме $r = 0.08 \cdot (1,1,1,1,1)$ и $\varepsilon = 5 \times {{10}^{{ - 4}}}$.

Пример 4 (см. фиг. 8). $g = 15$, ${\kern 1pt} \sigma = (1$, $1$, $ \ldots ,1)$, ${\kern 1pt} c = (0.025$, $0.102$, $0.253$, $0.301$, $0.392$, $0.495$, $0.521$, $0.669$, $0.798$, $0.843$, $0.881$, $0.911$, $0.957$, $0.977$, $1)$, ${\kern 1pt} r = 0.006 \cdot (1$, $1$, $ \ldots ,1)$, ${\kern 1pt} u = 12.345$, ${\kern 1pt} z = - 10 + 5i$, ${\kern 1pt} w = 8 + 17i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 10}}}$.

Пример 5 (см. фиг. 9). То же, что в примере 4, кроме $r = (0.01$, $0.005$, $0.02$, $0.02$, $0.055$, $0.01$, $0.008$, $0.036$, $0.008$, $0.01$, $0.01$, $0.005$, $0.005$, $0.005$, $0.01)$ и $\varepsilon {{ = 10}^{{ - 6}}}$.

Пример 6 (см. фиг. 10). $g = 4$, ${\kern 1pt} \sigma = (1$, $1$, $1,$ $1)$, ${\kern 1pt} c = (0.1$, $0.25$, $0.5$, $1)$, ${\kern 1pt} r = (0.075$, $0.05$, $0.1$, $0.15)$, ${\kern 1pt} u = 0.25 + 5i$, ${\kern 1pt} z = - 2 + 0.75i$, ${\kern 1pt} w = 3 - 0.125i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 5}}}$.

Пример 7 (см. фиг. 11). $g = 7$, ${\kern 1pt} \sigma = (1$, $1$, $ \ldots ,1)$, ${\kern 1pt} c = (0.1$, $0.35$, $0.46$, $0.58$, $0.76$, $0.84$, $1)$, ${\kern 1pt} r = (0.007$, $0.025$, $0.025$, $0.007$, $0.007$, $0.025$, $0.025)$, ${\kern 1pt} u = 2 + 3i$, ${\kern 1pt} z = 4 + 5i$, ${\kern 1pt} w = 6 + 7i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 11}}}$.

Пример 8 (см. фиг. 12). То же, что в примере 7, кроме ${{r}_{1}} = 0.099$ и $\varepsilon {{ = 10}^{{ - 6}}}$.

Пример 9 (см. фиг. 13). То же, что в примере 7, кроме ${{r}_{2}} = {{r}_{3}} = 0.05$ и $\varepsilon {{ = 10}^{{ - 8}}}$.

Пример 10 (см. фиг. 14). $g = 25$, ${\kern 1pt} \sigma = (1$, $1$, $ \ldots ,1)$, ${\kern 1pt} c = (0.02$, $0.05$, $0.1$, $0.14$, $0.18$, $0.22$, $0.26$, $0.32$, $0.36$, $0.41$, $0.46$, $0.51$, $0.55$, $0.59$, $0.65$, $0.69$, $0.73$, $0.76$, $0.80$, $0.83$, $0.86$, $0.89$, $0.92$, $0.95$, $1)$, ${\kern 1pt} r = 0.012 \cdot (1$, $1$, $ \ldots ,1)$, ${\kern 1pt} u = 2 + 2i$, ${\kern 1pt} z = 1 + 2i$, ${\kern 1pt} w = 1 + 3i$, ${\kern 1pt} \varepsilon = 2.5 \times {{10}^{{ - 4}}}$.

Пример 11 (см. фиг. 15). $g = 5$, ${\kern 1pt} \sigma = ( - 1$, $1$, $1$, $1$, $1)$, ${\kern 1pt} c = (0.1$, $0.4$, $0.6$, $0.8$, $1)$, ${\kern 1pt} r = (0.12$, $0.05$, $0.05$, $0.05$, $0.05)$, ${\kern 1pt} u = 1 + i$, ${\kern 1pt} z = - 4$, ${\kern 1pt} w = 3i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 4}}}$.

Пример 12 (см. фиг. 16). $g = 5$, ${\kern 1pt} \sigma = (1$, $ - 1$, $ - 1$, $ - 1$, $1)$, ${\kern 1pt} c = (0.1$, $0.22$, $0.4$, $0.6$, $1)$, ${\kern 1pt} r = (0.05$, $0.075$, $0.03$, $0.04$, $0.05)$, ${\kern 1pt} u = 4 + 2i$, ${\kern 1pt} z = 2 + 0.7i$, ${\kern 1pt} w = - 3 + i$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 5}}}$.

Пример 13. $g = 200$, ${\kern 1pt} {{c}_{j}} = j{\text{/}}100$ и ${{r}_{j}}{{ = 10}^{{ - 4}}}$ при ${\kern 1pt} 1 \leqslant j \leqslant 200$, ${\kern 1pt} u = - 3.0312 + 5.5431i$, ${\kern 1pt} z = 9.0172 + 1.7912i$, ${\kern 1pt} w = - 4.0976 + 0.1211$, ${\kern 1pt} \varepsilon {{ = 10}^{{ - 12}}}$.

Пример 14. $g = 100$, ${\kern 1pt} {{c}_{j}} = j{\text{/}}100$ при всех $1 \leqslant j \leqslant 100$, ${\kern 1pt} {{r}_{1}} = {{r}_{2}} = {{r}_{3}} = 4 \cdot {{10}^{{ - 3}}}$, ${\kern 1pt} {{r}_{j}}{{ = 10}^{{ - 4}}}$ при $4 \leqslant j \leqslant 100$, ${\kern 1pt} u = - 1 + 2i$, ${\kern 1pt} z = 3 + i$, ${\kern 1pt} w = - 2$, ${\kern 1pt} \varepsilon = 5 \times {{10}^{{ - 8}}}$.

Автор благодарен своему научному руководителю А.Б. Богатырёву за постановку задачи и ценные обсуждения. Также за ценные обсуждения автор благодарит С.А. Горейнова, О.А. Григорьева и М.С. Смирнова.