Решение уравнений и систем уравнений на эвм

Численные методы решения систем нелинейных уравнений

Введение

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

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

Для численного решения применяются итерационные методы последовательных приближений (простой итерации) и метод Ньютона в различных модификациях. Итерационные процессы естественным образом обобщаются на случай системы нелинейных уравнений вида:

(1)

Обозначим через вектор неизвестных и определим вектор-функцию Тогда система (1) записывается в виде уравнения:

(2)

Теперь вернёмся к всеми любимому Python и отметим его первенство среди языков программирования, которые хотят изучать [1].

Этот факт является дополнительным стимулом рассмотрения числительных методов именно на Python. Однако, среди любителей Python бытует мнение, что специальные библиотечные функции, такие как scipy.optimize.root, spsolve_trianular, newton_krylov, являются самым лучшим выбором для решения задач численными методами.

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

Так, в публикации [2], на основании проведенных вычислительных экспериментов, доказано, что библиотечная функция newton_krylov, предназначенная для решения больших систем нелинейных уравнений, имеет в два раза меньшее быстродействие, чем алгоритм TSLS+WD
(two-step least squares), реализованный средствами библиотеки NumPy.

Целью настоящей публикации является сравнение по числу итераций, быстродействию, а главное, по результату решения модельной задачи в виде системы из ста нелинейных алгебраических уравнений при помощи библиотечной функции scipy.optimize.root и методом Ньютона, реализованного средствами библиотеки NumPy.

Возможности решателя scipy.optimize.root для численного решения систем алгебраических нелинейных уравнений

Библиотечная функция scipy.optimize.root выбрана в качестве базы сравнения, потому что имеет обширную библиотеку методов, пригодных для сравнительного анализа.

scipy.optimize.root(fun, x0, args=(), method=’hybr’, jac=None, tol=None,callback=None, ptions=None)
fun — Векторная функция для поиска корня.
x0 –Начальные условия поиска корней

method:
hybr -используется модификация Пауэлл гибридный метод;
lm – решает системы нелинейных уравнений методом наименьших квадратов.
Как следует из документации [3] методы broyden1, broyden2, anderson, linearmixing, diagbroyden, excitingmixing, krylov являются точными методами Ньютона. Остальные параметры являются «не обязательными» и с ними можно ознакомится в документации.

Методы решения систем нелинейных уравнений

Приведенный далее материал действительно можно прочитать в литературе, например в [4], но я уважаю своего читателя и для его удобства приведу вывод метода по возможности в сокращенном виде. Те, кто не любит формулы, этот раздел пропускают.

В методе Ньютона новое приближение для решения системы уравнений (2) определяется из решения системы линейных уравнений:

(3)

Определим матрицу Якоби:

(4)

Запишем(3) в виде:

(5)

Многие одношаговые методы для приближенного решения (2) по аналогии с двухслойными итерационными методами для решения систем линейных алгебраических уравнений можно записать в виде:

(6)

где — итерационные параметры, a — квадратная матрица n х n, имеющая обратную.

При использовании записи (6) метод Ньютона (5) соответствует выбору:

Система линейных уравнений (5) для нахождения нового приближения может решаться итерационно. В этом случае мы имеем двухступенчатый итерационный процесс с внешними и внутренними итерациями. Например, внешний итерационный процесс может осуществляться по методу Ньютона, а внутренние итерации — на основе итерационного метода Зейделя

При решении систем нелинейных уравнений можно использовать прямые аналоги стандартных итерационных методов, которые применяются для решения систем линейных уравнений. Нелинейный метод Зейделя применительно к решению (2) дает:

(7)

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

Основные вычислительные сложности применения метода Ньютона для приближенного решения систем нелинейных уравнений связаны с необходимостью решения линейной системы уравнений с матрицей Якоби на каждой итерации, причем от итерации к итерации эта матрица меняется. В модифицированном методе Ньютона матрица Якоби обращается только один раз:

(8)

Выбор модельной функции

Такой выбор не является простой задачей, поскольку при увеличении числа уравнений в системе в соответствии с ростом числа переменных результат решения не должен меняться, поскольку в противном случае невозможно отследить правильность решения системы уравнений при сравнении двух методов. Привожу следующее решение для модельной функции:

Функция f создаёт систему из n нелинейных уравнений, решение которой не зависит от числа уравнений и для каждой из n переменных равно единице.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью библиотечной функции optimize.root для разных методов отыскания корней

Только один из методов, приведенных в документации [3] прошёл тестирование по результату решения модельной функции, это метод ‘krylov’.

Решение для n=100:

Вывод: С увеличением числа уравнений вдвое заметно появление ошибок в решении. При дальнейшем увеличении n решение становится не приемлемым, что возможно из-за автоматической адаптации к шагу, эта же причина резкого падения быстродействия. Но это только моё предположение.

Программа для тестирования на модельной функции c результатами решения системы алгебраических нелинейных уравнений с помощью программы написанной на Python 3 с учётом соотношений (1)-(8) для отыскания корней по модифицированному методу Ньютона

Решение для n=100:

Решение для n=200:

Solution:
[1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1.]
Newton iteration = 14
Newton method time 1.869 seconds

Чтобы убедиться в том, что программа действительно решает систему, перепишем модельную функцию для ухода от корня со значением 1 в виде:

Получим:
Solution:
[ 0.96472166 0.87777036 0.48175823 -0.26190496 -0.63693762 0.49232062
-1.31649896 0.6865098 0.89609091 0.98509235]
Newton iteration = 16
Newton method time 0.046 seconds

Вывод: Программа работает и при изменении модельной функции.

Теперь вернёмся к начальной модельной функции и проверим более широкий диапазон для n, например в 2 и 500.
n=2
Solution:
[1. 1.]
Newton iteration = 6
Newton method time 0.048 seconds
n=500

Решение систем линейных уравнений с помощью ЭВМ

РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ С ПОМОЩЬЮ ЭВМ

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

Система m линейных алгебраических уравнений с n неизвестными в линейной алгебре — это система уравнений вида:

Здесь m — количество уравнений, а n — количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn – коэффициенты при неизвестных системы, b1, b2,… bm — свободные члены. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно.

Решение системы m линейных алгебраических уравнений с n неизвестными — это совокупность n чисел (c1; c2; …; cn ) таких, что подстановка каждого ci вместо xi в систему обращает все её уравнения в тождества.

Система линейных уравнений может быть представлена в матричной форме:

Системы m линейных алгебраических уравнений с n неизвестными решаются различными методами.

Прямые (или точные) методы позволяют найти решение за определённое количество шагов. Итерационные методы основаны на использовании повторяющегося процесса и позволяют получить решение в результате последовательных приближений.

Метод Гаусса — Жордана (метод полного исключения неизвестных) — это метод, который используется для решения систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь и немецкого геодезиста и математика Вильгельма Йордана.

Алгоритм этого метода таков.

— Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.

— Если самое верхнее число в этом столбце есть ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.

— Все элементы первой строки делят на верхний элемент выбранного столбца.

— Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.

— Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.

— После повторения этой процедуры раз получают верхнюю треугольную матрицу.

— Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.

— Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).

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

Метод Крамера – это способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Назван по имени Габриэля Крамера (1704–1752), придумавшего метод.

Для системы n линейных уравнений с n неизвестными (над произвольным полем)

с определителем основной матрицы системы, отличным от нуля, решение записывается в виде:

(i-ый столбец матрицы системы заменяется столбцом свободных членов).

В высшей алгебре описаны и другие методы решения систем линейных уравнений. Но все они имеют ограниченную сферу использования.

При решении практических задач приходится находить решения систем линейных уравнений с большой степенью точности, потому что целочисленные решения встречаются довольно редко. Кроме того, математические модели некоторых явлений, процессов приводят к системам линейных уравнений с большим числом уравнений и неизвестных (например, при составлении прогноза погоды специалисты получают системы, в которых до пятидесяти уравнений с таким же числом неизвестных). Это приводит к громоздким вычислениям или вообще к невозможности решить систему линейных уравнений точными методами.

Поэтому в таких случаях используют итерационные методы, которые позволяют для их реализации использовать компьютерную технику и информационные технологии.

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

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

В моей исследовательской работе эти методы описаны подробно и подкреплены практическими задачами. Здесь же мы только называем эти методы.

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

В настоящее время разработан целый ряд дополнительных программных обеспечений(ПО), используемых для реализации итерационных методов (в частности, Excel, MathCad, Derive, Maple, Mathlab, Mathematica). Эти дополнительные ПО доступны каждому, они значительно упрощают решение систем линейных уравнений различных видов и различных степеней сложности.

1. Л, Солодовников . М.”Просвещение”.1974г. – С.160

2. Кондрашов зачетных заданий. Часть1. Красноярск. РИО КГПУ. 2001г. – С.102

3. Кураш высшей алгебры. М.”Наука”. 1971г. – С.432

4. , , “Численные методы”. М.”Академия”. 2005г. – С.384

5. Ларин алгебра. Часть1. Красноярск. РИО КГПУ. 2005г. – С.115

6. Окунев алгебра. М.”Просвещение”. 1968г. – С.336

7. Степанова лекций по курсу ”Численные методы”. Красноярск. РИО КГПУ. 2010г. – С.161

8. Степанова по курсу “Численные методы”. Красноярск. РИО КГПУ. 2003г. – С.66

Решение систем полиномиальных уравнений на ЭВМ Текст научной статьи по специальности « Математика»

Текст научной работы на тему «Решение систем полиномиальных уравнений на ЭВМ»

ления менее релевантных ИО. Второй тип штрафа менее предпочтителен, так как приводит к тому, что актор может покинуть площадку.

Реализация описанного подхода позволила обеспечить работоспособность автоматизированных интеллектуальных систем управления распределением производственных ресурсов в режиме реального времени. Анализ ритмичности взаимодействия при производственном планировании (см. рис. 2) и информационное управление интересом акторов позволили разработать регламенты работы плановых отделов, мастеров и распределителей работ при формировании сменно-суточных заданий и обеспечить своевременную реакцию на события, приводящие к изменению планов.

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

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

доставляющего максимальному количеству сотрудников предприятия доступ в единое информационное пространство.

1. Колчин А.Ф., Овсянников М.В., Стрекалов А.Ф., Сумароков С.В. Управление жизненным циклом продукции. М.: Ахарсис, 2002. 304 с.

2. Leitäo P. Holonic rationale and bio-inspiration on design of complex emergent and evolvable systems // Trans. on large-scale data and knowledge centered systems I, LNCS 5740, 2009. SpringerVerlag Berlin Heidelberg, pp. 243-266.

3. Бурков В.Н., Коргин Н.А., Новиков Д.А. Введение в теорию управления организационными системами. М.: Либро-ком, 2009. 264 с.

4. Каляев И.А. Стратегии группового управления в распределенных системах // Управление в распределенных сете-центрических и мультиагентных системах: матер. науч.-технич. сем. СПб: Концерн ЦНИИ «Электроприбор», 2010. C. 8-9.

5. Прикладной анализ случайных процессов; [под ред. С.А. Прохорова]. Самара: Изд-во СНЦ РАН, 2007. 582 с.

6. Иващенко А.В. Модель многоакторной интегрированной информационной среды предприятия // Вестн. СамГУПС. Самара: СамГУПС, 2012. № 1 (15). C. 103-109.

7. Иващенко А.В. Управление согласованным взаимодействием пользователей интегрированной информационной среды предприятия. Самара: Изд-во СНЦ РАН, 2011. 100 с.

1. Kolchin А.Б., Ovsyannikov М^., Strekalov А.Б., Sumaro-kov S.V., Upravlenie zhiznennym tsiklom produktsii (Product Lifecycle Management), Moscow, Akharsis, 2002, 304 p.

2. Leitäo P., Holonic rationale and bio-inspiration on design of complex emergent and evolvable systems. Trans. on large-scale data and knowledge centered systems I, LNCS 5740, 2009, SpringerVerlag Berlin Heidelberg, pp. 243-266.

3. Burkov V.N., Korgin NA, Novikov DA., Vvedenie v teo-riyu upravleniya organizatsyonnymi sistemami (Introduction in Organizational System Management Theory), Moscow, Librokom, 2009, 264 p.

4. Kalyaev 1.А., Materialy nauchno-tekhnicheskogo seminara «Upravlenie v raspredelennykh setetsentricheskikh i multiagentnykh sustemakh» (Materials of Scientific and Technical Seminar «Management in Distributed Network-Centric and Multiagent Systems»), St. Petersburg, Kontsern «Elektropribor», 2010, pp. 8-9.

5. Prikladnoy analiz sluchainykh protsessov (Application Analysis of Random Processes), [ed. by SA. Prokhorov], Samara, Izd. Samara Research Center RAS, 2007, 582 p.

6. Ivashchenko А^., VestnikSamGUPS (Journ. of the Samara State Univ. of Railway Transport), 2012, no. 1 (15), pp. 103-109.

7. Ivashchenko А^., Upravlenie soglasovannym vzaimo-deystviyem polzovateley integrirovannoy informatsionnoy sredy predpriyatiya (Management of Consistent Interaction of Enterprise Integrated Information Environment Users), Samara, Izd. Samara Research Center RAS, 2011, 100 p.

РЕШЕНИЕ СИСТЕМ ПОЛИНОМИАЛЬНЫХ УРАВНЕНИЙ НА ЭВМ

(Самарский государственный аэрокосмический университет им. академика С.П. Королева (национальный исследовательский университет), ilyozi-nJ@yandex.ru)

Предложен ускоренный алгоритм поиска базисов Грёбнера, используемых при решении систем полиномиальных уравнений. Данный алгоритм рассматривает проблему переполнения разрядной сетки и некорректных вычислений при проведении расчетов на ЭВМ. Классический алгоритм Бухбергера и обновленный алгоритм Фужера требуют

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

Ключевые слова: системы полиномиальных уравнений, базис Грёбнера, алгоритм Фужера, алгоритм Бухберге-

SOLUTION OF SIMULTANEOUS POLYNOMIAL EQUATIONS ON A COMPUTER Lyozin I.A., Ph.D. (Samara State Aerospace University, ilyozin@yandex.ru)

Abstract. The article offers the accelerated algorithm of Groebner bases search used in the course of solution of simultaneous polynomial equations. The proposed algorithm considers the issue of word size overflow and incorrect computations in the course of calculating on the computer. The classical Buchberger’s algorithm and the updated Faugere’s algorithm require a lot of steps; meanwhile they do not contain any additional actions on correction of floating point numbers computations that causes some errors and incorrect computation of simultaneous equations roots and irrational factors. The new algorithm by several times reduces the number of operations of polynom quantity reduction, does not store all possible pairs of polynoms and does not check them for the fact that one can be expressed in terms of the other. The algorithm proposed in the article operates only with that number of polynoms which are now a basis. The basis is expanded if none of the polynoms represented in it can be represented in the form of combination of the other polynoms of this basis. Otherwise, the extra polynom shall be removed from the basis that helps avoid overgrowth of the basis and excess operations with this polynom. In order to avoid the problem of incorrect computations because of the word size of the computer the algorithm envisages post-check. If any of the polynoms is reduced, then the initial polynom should be represented by the combination of the reduced polynom and the rest of the basis polynoms. If the values of coefficients of the equal monoms do not coincide after that, then the coefficients of the reduced polynom require correction by the error size.

Keywords: systems of polynomial equations, Grobner basis, Faugere algorithm, Buchberger algorithm.

Системы полиномиальных уравнений в общем случае решаются построением базиса Грёбнера из базиса, составленного многочленами рассматриваемой системы, и решением системы уравнений, левые части которых являются многочленами, составляющими базис Грёбнера [1]. В числе самых широко распространенных методов для построения базиса Грёбнера — алгоритм Бухбергера и алгоритм Фужера 3. Однако оба они при относительной простоте выполняемых преобразований имеют очень высокую операционную сложность, что затрудняет, а зачастую делает невозможным вычисление базиса.

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

Следовательно, требуется найти алгоритм, позволяющий строить базис Грёбнера с меньшей вычислительной сложностью, чем имеющиеся алгоритмы, а также работать с иррациональными коэффициентами. За основу данного метода можно взять некоторые приемы из уже упомянутых алгоритмов Бухбергера и Фужера.

Итак, пусть K — поле вещественных чисел, К[х, у] — кольцо многочленов от двух переменных с коэффициентами из К. Рассмотрим некоторый идеал I над кольцом многочленов, в который входят полиномы из системы. Множество H= является базисом идеала I. Зададим лексикографическое упорядочение мономов в многочленах:

Рх > Чх М Рх = Чх Ру > Чу )•

Используя операции сложения и умножения над многочленами, входящими в базис Н, необходимо редуцировать его так, чтобы построить базис Грёбнера идеала I.

Введем понятие ^-полинома [2]:

Здесь ЬТ(/) представляет старший терм многочлена /(.х, у), а ЬСМ/ /) равен наименьшему моному, который делится на старшие мономы многочленов/(х, у) и/(х, у). Операцией редуцирования произвольного полинома /(х, у) из К[х, у] относительно Н является нахождение такого минимального многочлена г(х, у), который выражается в виде

f (х у) ^Нг (х у ) = f (х у ЬХ а (х у )у (х у), (3)

где а(х, у) еК[х, у] и /(х, у) еН.

Базис Н можно назвать базисом Грёбнера, если для любых двух полиномов /(х, у) и /(х, у) из Н выполняется условие

При заданном лексикографическом упорядочении (1) базис Грёбнера будет составлен парой многочленов, удовлетворяющих условию (4), вида

Множество решений системы, составленной из полиномов (5), будет соответствовать множеству решений системы.

Алгоритм нахождения базиса Грёбнера представлен в виде блок-схемы (см. рис.).

На вход алгоритма редукции подается базис Н идеала I, составленный из множества полиномов исходной системы уравнений. Каждая итерация алгоритма редуцирования базиса начинается с того, что в базисе Н ищется полином /(х, у) с минимальным старшим мономом, который может быть редуцирован относительно множества полиномов, состоящего из всех полиномов базиса, кроме выбранного полинома. Дальнейшее выполнение алгоритма разбивается на две ветви.

Если такой полином найден, он исключается из базиса и находится остаток г(х, у) от редукции этого полинома. Произвольный полином является редуцируемым относительно некоторого множе-

ства полиномов, если в этом множестве есть многочлены, старшие мономы которых являются делителями старшего монома редуцируемого полинома. Редукция полинома — итеративный процесс. Если перед редукцией остаток г(х, у) принять равным исходному редуцируемому полиному /(х, у), то на каждом шаге уменьшения остатка осуществляется поиск максимального полинома /(х, у) в множестве Н, который может редуцировать остаток г(х, у), и выполняется редукция

г ( ^ у ) = г ( ^ у )-ЬС ( г ). / ( ^ у У , (6)

где ЬС(г) — коэффициент перед старшим мономом многочлена г(х, у).

Редуцирование по формуле (6) следует продолжать до тех пор, пока остаток г(х, у) не станет нередуцируемым. Когда редуцирование завершено и остаток г(х, у) не является нулевым полиномом, он добавляется в базис Н.

Перед добавлением остатка в базис следует провести корректировку коэффициентов для г(х, у). В кольце К[х, у] необходимо найти такие многочлены а&1(х, у), аь,г(х, у), а&г(х, у) и аИ,г(х, у), чтобы можно было представить полиномы g(x, у) и И(х, у) в базисе Н+<г>:

8 (х у) = X а8,- (х’ у )л (х’ У )+ а8,г (х У )г (х У ) , ^ (7)

Ь (х’ у) = X (х’ у)л (х’ у) + аь, г (х у)г (х у) ■

Если решение системы (7) не находится, значит, при вычислениях в коэффициентах остатка накопилась методическая погрешность из-за способа представления вещественных чисел в памяти ЭВМ. Так как уже имеющиеся в базисе полиномы имеют правильные значения коэффициентов, необходимо откорректировать коэффициенты остатка г(х, у) в соответствии со значениями погрешности для каждого из коэффициентов в системе (7). Эта задача решается подобно задаче редуцирования: сначала определяются значения коэффициентов для полиномов а&(х, у) и ак(х, у), затем вычисляются разности:

г8 (х у) = 8 (х у)- X а8,1 (х у)л (х у) =

= а8 ,г ( х, у ) г ( х, у ) ,

гь (х у) = И (х у)- X аК1 (х у)л (х у) =

Если разности представляют собой нулевые полиномы, то одну или несколько базисных функций /(х, у) нужно исключить из суммы и повторить операцию. По оставшимся разностям вычисляются коэффициенты полиномов а&г(х, у) и аИ,г(х, у) и корректируются (при необходимости) коэффициенты г(х, у). После этого г(х, у) добавляется в

Блок-схема алгоритма редукции системы уравнений

базис Н и алгоритм редуцирования базиса идет на очередную итерацию.

По второй ветви алгоритм редуцирования базиса развивается, если в базисе Н не найден полином, который может быть редуцирован. В таком случае набор базисных функций должен быть расширен для продолжения редукции. Из всех возможных пар полиномов базиса /(х, у) и /(х, у), для которых не выполняется условие (4), нужно найти пару с минимальным ЬСЫ(/и /).

Если такая пара найдена, редуцированный остаток ^-полинома этой пары включается в базис Н, предварительно пройдя корректировку коэффициентов, как это было описано ранее. Если же такой пары многочленов в базисе Н нет, значит, этот базис полностью редуцирован и является базисом Грёбнера.

Таким образом, в результате работы алгоритма получим базис, составленный из пары многочленов (5). Теперь для решения исходной системы нужно вычислить все корни у полиномиального уравнения одной переменной/у(х, у)=0, подставить по очереди эти значения в многочлен /х(х, у), превращая его в полином одной переменной, и рассчитать соответствующие корни ; уравнения

Сравнительный анализ на конкретных примерах показал, что новый алгоритм в несколько раз быстрее существующих, что с учетом его адаптации к вычислениям на ЭВМ делает данный алгоритм более предпочтительным при решении задач нахождения базисов Грёбнера и, как следствие, отыскания корней систем полиномиальных уравнений.

1. Прасолов В.В. Многочлены. М.: МЦНМО, 2001.

2. Buchberger B. Grobner Bases: an Algorithmic Method in Polynomial Ideal Theory / Recent trends in multidimensional system theory, U. Reidel Publishing Company, 1985.

3. Buchberger’s algorithm. URL: http://www.geocities.com/ famancin/buchberger.html (дата обращения: 01.06.12).

4. Faugere J.C. A new efficient algorithm for computing Grobner bases (F4) // Journal of Pure and Applied Algebra, 1999, no. 139, pp. 61-88.

1. Prasolov V.V., Mnogochleny (Polynomials), Moskovsky Tsentr Nepreryvnogo Matematicheskogo Obrazovaniya, 2001.

2. Buchberger B. Grobner Bases: an Algorithmic Method in Polynomial Ideal Theory. Recent trends in multidimensional system theory, U. Reidel Publishing Company, 1985.

3. Buchberger’s algorithm, available at: www.geocities.com/ famancin/buchberger.html (accessed 01.06.12).

4. Faugere J.C., A new efficient algorithm for computing Grobner bases (F4), Journal of Pure and Applied Algebra, 1999, no. 139, pp. 61-88.

ИССЛЕДОВАНИЕ АППРОКСИМАТИВНЫХ ВОЗМОЖНОСТЕЙ РАДИАЛЬНО-БАЗИСНОЙ СЕТИ С ОРТОГОНАЛЬНЫМИ ПОЛИНОМАМИ

(Самарский государственный аэрокосмический университет им. академика С.П. Королева (национальный исследовательский университет), chuchyck@yandex.ru)

Описывается постановка задачи аппроксимации, обосновывается возможность использования в качестве аппрок-симатора плотности распределения вероятности радиально-базисной нейронной сети, приводятся аппроксимирующее выражение для данной сети и выражение для целевой функции, с помощью которой происходит подбор параметров базисных функций и значений весов. Рассматривается возможность использования при аппроксимации плотности распределения вероятности радиально-базисной сетью не только традиционных функций Гаусса, но и сигмои-дальных и степенных функций и ортогональных полиномов Лежандра, Чебышева I и II рода, Лагерра и Эрмита. Приводятся соответствующие формулы. Сравниваются погрешности аппроксимации путем вычисления среднего квадратического отклонения. В качестве примеров приводится аппроксимация плотности вероятности Симпсона и Рэлея радиально-базисной сетью c сигмоидальными, степенными функциями, а также полиномами Лежандра, Чебышева I и II рода, Лагерра и Эрмита. Дается рекомендация по использованию радиально-базисной сети с полиномами Лежандра, Чебышева I и II рода в качестве базисных функций при увеличении числа нейронов в скрытом слое, так как такая сеть позволяет достичь более низких значений среднего квадратического отклонения, чем сеть с традиционными функциями Гаусса.

Ключевые слова: аппроксимация, радиально-базисная сеть, ортогональные полиномы, Лежандр, Чебышев, Ла-герр, Эрмит.

источники:

http://pandia.ru/text/78/541/10665.php

http://cyberleninka.ru/article/n/reshenie-sistem-polinomialnyh-uravneniy-na-evm