Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Янович Денис Александрович

Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений
<
Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Янович Денис Александрович. Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений : Дис. ... канд. физ.-мат. наук : 05.13.18 : Дубна, 2003 111 c. РГБ ОД, 61:04-1/1005

Содержание к диссертации

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 так, что ее начало отсчета оказывается в точке, соответствующей концу ру

ки робота. И наконец, чтобы число неизвестных соответствовало числу уравнений необходимо добавить соотношения для синусов и косинусов:

Похожие диссертации на Алгоритмы и программы вычисления инволютивных базисов и их применение для решения систем нелинейных алгебраических уравнений