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

Методы решения систем уравнений обычно разделяют на две большие группы. К первой группе относят методы, которые называют точными. Они позволяют для любых систем найти точные значения неизвестных после конечного числа арифметических операций, каждая из которых выполняется точно. Ко второй группе относятся все методы, которые не являются точными. Их называют приближёнными, численными, или итерационными. Точное решение при использовании этих методов получается в результате бесконечного процесса приближений. [1, с. 24]

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

− метод простой итерации;

− метод Ньютона решения систем нелинейных уравнений;

− метод градиентного спуска;

− метод натурального градиента (является модификацией метода градиента, скорейшего спуска). Он будет использоваться при разработке программного комплекса.

2 Алгоритмы и методы для решения нелинейных алгебраиеских уравнений на основе метода натуральных градиентов

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

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

– в разработанном приложении необходимо предусмотреть возможность ввода данных для расчета из текстового файла, формата txt;

– так же обеспечить решение системы нелинейных алгебраических уравнений с не менее 30000 неизвестных;

– задание ip-адресов вычислительных узлов осуществить в xml-файле;

– реализовать линейное и распределенное решение;

– для коммуникации использовать протокол TCP/IP;

– для реализации использовать язык C#;

– сравнить распределенное решение с линейным. Провести исследование зависимости времени нахождения решения от размерности системы и количества вычислительных узлов.

2.2 Aлгоритм метода натуральных градиентов

Рассмотрим алгоритму натурального градиента [1, c. 55]:

а) ввод элементов модели ;

б) вычисление потери ;

в) вычисление градиента (2.1)

; (2.1)

г) вычисление информационной матрицы Фишера или его эмпирической версии;

д) вычислить естественный градиент (2.2)

; (2.2)

е) обновить вектор неизвестных по формуле (2.3).

, (2.3)

где − это скорость обучения.

2.3 Алгоритмы линейного и распределенного решения

Для линейного решения загружается файл с тестовыми данными, пример на рисунке 2.1.

Рисунок 2.1 – Содержание файла с тестовыми данными

После происходит инициализация переменных и задается приближение, транспонированиие и переможение матриц. Далее проверяем сходимость ряда задаем точность решения и устанавливаем флаг на нахождение решения.

Далее засекаем секундомер на затраченное время для заданного интервала. И запускаем цикл, условие которого – пока невязка большая или количество итераций не превысило допустимое значение, производим промежуточное решение и его вывод.

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

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

Далее проверяется сходимость ряда задаем точность решения и устанавливаем флаг на нахождение решения.

Далее включаем секундомер для измерения затраченного время для заданного интервала. И запускаем цикл, условие которого – пока невязка большая или количество итераций не превысило допустимое значение, производим промежуточное решение и его вывод. Далее производится расчет Якобиана – параллельно, посылается х1 на несколько компьютеров. Далее делим значение, полученное в результате расчета Якобиана, на две части. И после последующего решения Якобиана, выводится его решение по частям. После производится расчет и вывод невязки и финальный расчет системы уравнений. Посылается контрольный байт: если решение не найдено и количество итераций не достигло своего максимума, то возвращается 0 – и продолжаем, иначе возвращается 3 – что означает конец расчета. Эти данные отправляются, а так же происходит остановка счетчика, который был запущен ранее и вывод затраченного на решение времени. Так же выводится информация о том, на какой итерации произошла расходимость или что приближенное решение не найдено. После производится вывод информации о том, на какой итерации была найдена расходимость или, наоборот, приближенное решение было найдено.

Передача данных с сервера и обработка данных осуществляется по запрограммированному алгоритму:

а) подготовка данных для отправки;

б) установка соединения по IPv4 с первым клиентом;

в) создание сокета;

г) соединение сокета по IPv4 с первым клиентом;

д) отправление данные через сокет;

е) получение ответа через сокет;

ж) освобождение сокет;

з) установка соединения по IPv4 со вторым клиентом;

и) создание сокета;

к) соединение сокета по IPv4 со вторым клиентом;

л) отправка данных через сокет;

м) получение ответа через сокет;

н) освобождение сокета;

о) выполнение обработки данных.

Функциональная схема сервера показана в приложении Г. На ней изображен весь процесс обработки данных и передачи информации.