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

• Автор: Фомочкина, Анастасия Сергеевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 113 с. : ил.

Оглавление
Оглавление
Введение
Глава 1. Выход в (п+1)-мерное пространство
1.1. Постановка задачи
1.2. Теоретическое обоснование
1.3 Алгоритм
1.4 Моделирующая программа
1.5. Тестирование метода
1.6. Выводы
Глава 2. Некоторые сведения из топологии
Глава 3. Использование свойств неподвижной точки для решения систем линейных уравнений
3.1. Постановка задачи
3.2. Теоретическое обоснование
3.3. Алгоритм
3.4. Моделирующая программа
3.5. Тестирование метода
3.5.1. Тестирование на СЛАУ, полученных с помощью датчика случайных чисел
3.5.2. Тестирование на СЛАУ, коэффициенты которых представляют собой матрицу Гильберта
3.6. Выводы
Глава 4. Использование свойств неподвижной точки для решения систем нелинейных уравнений
4.1. Постановка задачи
4.2. Теоретическое обоснование
4.3. Алгоритм для случая п=
4.4. Моделирующие программы
4.5. Тестирование метода
4.5.1. Тестирование на системах квадратных уравнений
4.5.2. Тестирование метода с построением таблицы углов
4.5.3 Тестирование метода на системе, возникающей при расчете
пространственной траектории горизонтальной скважины
4.6. Выводы
Заключение
Список литературы
Введение
Актуальность темы исследования
Работа посвящена созданию новых вычислительных алгоритмов для решения систем, как линейных, так и нелинейных уравнений. Предлагаемые алгоритмы основываются на геометрической интерпретации задачи. Несмотря на то, что задача решения систем уравнений является классической задачей, создание новых вычислительных алгоритмов не теряет своей актуальности.
Случай линейных систем
Для линейных систем существует большое количество методов их решения, которые хорошо себя зарекомендовали в случаях систем с хорошо обусловленными матрицами и ограниченным количеством уравнений. Но, учитывая, что значительное количество актуальных задач, возникающих при построении математических моделей, сводятся к решению систем линейных алгебраических уравнений (СЛАУ), то и требования к таким системам растет. К примеру, к СЛАУ сводятся задачи интерполяции дискретно заданных функций или задачи построения сеточных аппроксимаций многомерных краевых задач для систем дифференциальных уравнений в частных производных [14,45,47]. Такие задачи возникают при математическом моделировании для сложных междисциплинарных приложений, включающих гидро-газодинамические процессы, динамику напряженно-деформационных состояний и другие [18,39,40]. Само понятие многомерной задачи быстро эволюционирует, и сейчас необходимо говорить о решениях СЛАУ с размерностями порядка Ю10 на многопроцессорных вычислительных системах с числом ядер, или потоков, в десятки и сотни тысяч [9,32].
В случае систем большой размерности алгебраические методы их решения приводят к значительным отклонениям вычисленного решения от истинного за счет накопления ошибки в длинных последовательностях взаимозависимых операций. Такие методы плохо распараллеливаются, и как следствие при их
реализации не могут эффективно использоваться многопроцессорные системы, которые стремительно развиваются в настоящее время [5,6,16,17,20,40].
Второй проблемой является плохая обусловленность системы. В этом случае иногда необходимо знать хотя бы, в какой области находится решение. На этот вопрос алгебраические методы ответить не могут.
Случай нелинейных систем
Также часто задачи математического моделирования сводятся к решению систем нелинейных уравнений. Они возникают, например, при нахождении экстремумов функции нескольких переменных или при аппроксимации дискретно заданных функций математическими моделями, нелинейными по отношению к параметрам и так далее [2,13,31,41]. Такие задачи возникают повсеместно в различных областях науки, например, в химии [28], в электротехнике, в проектировании кустовых скважин [33], в оперативном управлении большими трубопроводными системами, в частности, при идентификации их параметров и других[42,52]. Чаще всего при решении нелинейных систем применяются итерационные методы типа метода Ньютона, использующие линеаризацию [1,11,43]. Но такими методами ищется только одно решение, хотя на самом деле их бывает много. Какое из них искать пользователь решает из сторонних соображений так же, как и какое начальное приближение задать, что является определяющим в нелинейном случае.
Целью работы является создание и исследование новых вычислительных методов для нахождения области, содержащей решения систем вида:
^(х„...,хи) =

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

х =а,,х, + а,,х, +...а, х
1 нов 11 1cm 12 2 cm ln пет

Л» = + + -«„Л
Пусть в этом пространстве задан симплекс с вершинами х'(х‘,х’,...,х‘),..., хп+'(х"+1,х"+...,х"*') и точка с координатами x(l(^,°,x20,...,x“) лежит на грани
І/ І І 1 І+Г / i+r J+r *.J+r
симплекса с вершинами х (х1,х2,...9хп)9...9х (х^ ,х2 9...9хп ).
Тогда образ точки х0(х°,х°,...,х°) при преобразовании F лежит внутри симплекса с вершинами F(x‘l,x‘2,...,x'n), F(x'[ ,х2...,х'^[)
F(x?',x?,...Xr).
До казательство:
Выразим точку через точки х'х'+г с помощью барицентрических координат ось..., аг. Это значит, что х,° = а,х! + а2х"’ +...+а X*'
4 = аА + X + -+«*Г (
х° = a{x'n + агх'+1 +... + агх'+'
т-r v» 7 г / 0 0 0 —0 /—0 —0 —0
Найдем теперь точку r (х( ,х2,...,хп) = х (х2 ,х2 ,...,хи ):
С —о о . о , о
х, =а11х1 +а12х2 +...а1пхп
(3.2)
Л =а„Л +а„2Х2+-а„Л Подставим в (3.2) выражение (3.1), получим
х;0 -ап(аХ +,.. + агх|,+г) + ,.. + 01л(а]х; + „. + агх'+г)
(3.3)
Л° =ani(aX + ...+ ах'4) + ■■■ + а„„(а,х‘„ + ■■■ + агхТ)
Раскрыв скобки в (3.3) получим