Содержание к диссертации
1 Введение 5
1.1 Некоторые методы решения систем нелинейных алгебраиче
ских уравнений 12
1.1.1 Метод интервалов 12
1.1.2. Метод гомотопичного продолжения решения . 13
1.1.3 Метод, использующий базисы Грёбнера . 14
2 Символьно-численный метод решения систем уравнений на
основе инволютивных базисов 24
2.1 Определения и алгоритмы вычисления 24
2.2 Параллельный алгоритм вычисление инволютивного базиса 37
2.3 Символьное и численное вычисление корней . 42
2.4 Быстрый поиск делителя Жане 43
3 Особенности программной реализации 48
3.1 Представление данных 48
3.1.1 Числа 49
3.1.2 Мономы 51
3.1.3" Полиномы 57
3.1.4 Частичный базис (Т) и множество продолжений (Q) 58
3.2 Схема программного комплекса и форматы файлов . 58
4 Решение уравнения Шредингера с центральным полиноми
альным потенциалом 61
4.1 Ангармонические осцилляторы и проблема их решения . 61
4.2 Вывод уравнений Магьяри 62
4-3 Уравнения Магьяри для большой пространственной размер
ности . 65
4.4 Результаты для полиномиальных потенциалов при различ
ных q 68
B.0.32 kotsireas [39] 99
« ВЛ.ЗЗ noon-n [39, 51, 52] 100
В.0.34 pinchonl 100
В.0.35 rbpl [53] 101
В.0.36 rbpl24 [53] 102
В.0.37 redcyc-n [ЗО] 103
В.0.38 redeco-n [45] 103
В.0.39 reimer-n [32] 103
В.0.40 virasoro [29] 103
Литература 105
Введение к работе
Объект исследования и актуальность темы.
Системы нелинейных алгебраических полиномиальных уравнений часто возникают в различных областях науки и техники: в построении фор- « мул (см. пример 1.0.4), проблеме пересечения поверхностей в геометрии
(см. пример 1.0.5), в обратной кинематической задаче (см. пример 1.0.6), в задаче об ангармонических осцилляторах, которую мы рассмотрим в главе 4 и т.д.
Численное решение систем полиномиальных уравнений сопряжено с некоторыми проблемами:
• погрешности решения
« • невозможность распознать и тем более решить недоопределенные си стемы
• возможная потеря корней
и т.п.
Этих проблем можно избежать, если использовать символьные или гибридные численно-символьные методы решения.
В связи с вышеизложенным, целью диссертационной работы является • анализ применимости инволютивных базисов Жане для решения полино миальных систем уравнений вместо базисов Грёбнера, встроенных для этой
цели во все современные системы компьютерной алгебры общематематического назначения.
В соответствии с целью исследования были рассмотрены следующие конкретные задачи:
Х- Разработка алгоритма вычисления инволютивных базисов Жане с целью достижения максимально возможной скорости вычислений;
2- Исследование поведения алгоритма на различных тестовых примерах и прикладных задачах;
3. Разработка параллельной версии алгоритма и исследование ее особенностей;
Достоверность основных результатов подтверждена строгими математическими доказательствами и многочисленными компьютерными экспериментами, а также сравнением с результатами вычислений программ, разработанными другими авторами.
Научная новизна:
J. На многочисленных тестовых примерах и в сравнении со специализированными системами компьютерной алгебры Singular [27] и Magma [54], обладающими самыми быстрыми реализациями классического алгоритма Бухбергера [6] вычисления базисов Грёбнера выявлены преимущества базисов Жане по скорости вычислений.
2. Показана естественная параллелизуемость с высокой степенью масштабируемости алгоритма вычисления базисов Жане.
3. Создан эффективный комплекс программ для численного нахождения корней полиномиальных систем основанный на вычислении ин-волютивных базисов Жане.
4. С помощью разработанного комплекса найдены условия аналитической разрешимости уравнений Шредингера с полиномиальным потенциалом при достаточно больших значениях размерности пространства.
Научная и практическая ценность. В диссертации создан комплекс программ позволяющий эффективно решать сложные нелинейные системы алгебраических уравнений со многими неизвестными, которые возникают в различных научных и технических приложениях, таких как робототехника, теоретическая физика, геометрическое моделирование, разработка математических формул, расчет электрических цепей и т.д.
Отдельный модуль для вычисления инволютивных полиномиальных базисов Жане встроен в специализированную систему компьютерной алгебры Singular, созданную в университете Кайзерслаутерна, ФРГ и являющуюся ведущей из специализированных систем, ориентированных на задачи коммутативной алгебры и алгебраической геометрии.
Апробация работы. Основные результаты и положения диссертационной работы доложены и обсуждены на:
научных семинарах ЛИТ ОИЯИ
t семинарах по компьютерной алгебре ВМК МГУ
• научном семинаре в университете Кайзерслаутерна
VI международной конференции по применению компьютерной алгебры АСА 2000, Ст.-Петербург, июнь 2000
? 2й международной конференции «Современные тенденции в вычислительной физике», Дубна, июль 2000
t IV международной конференции по компьютерной алгебре в научных вычислениях CASC2001, Констанц, ФРГ, 2001
• международной конференции по компьютерной алгебре и ее применению в физике, СААР 2001 Дубна, июнь 2001
щ международной конференция «Недоопределенные и переопределенные системы алгебраических и дифференциальных уравнений» Карлсруе, ФРГ, март 2002.
V международном конгрессе по математическому моделированию, Дубна, сентябрь-октябрь 2002.
щ V международной конференции «Симметрии в нелинейной математической физике» Киев,июнь 2003.
• VI Международная конференция по компьютерной алгебре в научных вычислениях CASC2003 Пассау, ФРГ, сентябрь, 2003
Структура и объем диссертации. Диссертация состоит из введения, грех глав, заключения, приложения и списка литературы. Диссертация содержит 111 страниц, 4 таблицы, 4 рисунка. Список литературы содержит 78 работ, из них 5 на русском, 73 на иностранных языках.
Несколько систем нелинейных алгебраических уравнений
Определение 1.0.1 Полиномом от многих переменных называется
объект f{xi,X2, —іХп) Є R
і
k=0
Определение 1.0.2 Полиномиальная система F(x) = 0 определяется множеством полиномов F.
Определение 1.0.3 Для заданной полиномиальной системы F, х назовем её решением если F(x ) = 0. Назовем х приближенным решением, если оно может быть уточнено с помощью какого либо итеративного сходящегося метода и точным решением, если оно получено с помощью символьных вычислений.
Пример 1.0.4 Рассмотрим задачу построения квадратурной формулы для численного интегрирования. Пусть подынтегральная функция f(x) определена на отрезке [о, 6]. Будем аппроксимировать интеграл взвешенной суммой 1(f) = 2wkf(xk), где Wk - веса, Xk - узлы. Цель - разработать высокоточную формулу, которая интегрирует все полиномы до определенной степени. Пусть мы используем два узла и ограничим степень полинома тройкой:
/ fdx « /(/) = wif(xi) + w2f(x2)
J а
I(xk) = mk= xkdx, k = 0,1,2,3.
Ja
Узлы и веса удовлетворяющие следующей полиномиальной системе позволяют точно интегрировать полиномы вплоть до третьей степени:
F{xi,x2,w1,w2) = 1{х°) = т0
/(я1) = ті
I(x2) = т2
7(х3) = ш3
= • w\ + w2 — то = 0 w\Xi 4- w2X2 — т\ — О
W\X\ + W2x\ — 7712 = 0 w\x\ + w2x\ — т% — О
Пример 1.0.5 Рассмотрим пересечение двух окружностей на плоско сти
Рис. 1.1. Пересечение двух окружностей на плоскости
Уравнения определяющие точки пересечения образуют следующую систему:
п./ ; ( -0)2 + fo-02 = 52 (х - 8)2 + (у - О)2 = 52
которая имеет два вещественных решения.
х2 + у2 - 25 = О
х2 + у2 - 16а: + 39 = О
Пример 1.0.6 Проблема руки робота. Рассмотрим руку робота на плоскости состоящую из двух частей, соединенных шарниром. Длины частей
соответственно а\ « аг. Задача состоит в определении углов 0і и 02 необходимых для перемещения руки в заданную точку.
1Уі Уг\ V
Xi
Рис. 1.2. Чтобы переместить руку робота в желаемую позицию надо узнать одно из двух возможных значений углов 01 И 02
Путем переносов и поворотов переместим начало координат в точку, соответствующую суставу руки. Пусть Ck = cos(0jt) и Sk = sin(0fc)r для к = 1,2. Соотношение между первой и второй системами координат выглядит такг
Xi
У\
С\ Si s1 Сі
Х2 2/2
+
aici
diSi
Выразим перенос и поворот с помощью одной матрицы:
х2 Х2
г/г = Гі 2/2
і 1
х\ Ci si а\С\
г/і = -si сі aisi
1 0 0 1
Аналогично может быть выражено соответствие между второй
и третьей системой координат используя матрицу Т2, которая выражает перенос на й2 и вращение системы координат на угол 02 так, что ее начало отсчета оказывается в точке, соответствующей концу ру
ки робота. И наконец, чтобы число неизвестных соответствовало числу уравнений необходимо добавить соотношения для синусов и косинусов:
