4.8.1 Методы решения

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

X = (Хх, . . . , хп) .

Метод простых итераций в многомерном случае применяется к системе уравнений, заданных в форме (4.2). Итерации организуются так же, как в одномерном случае:

Х(к+1) = Ги(Х(к)) . (4.13)

Только, в отличие от одномерного варианта, X - это вектор переменных, §¥л - вектор функций.

В качестве критерия окончания используется оценка степени приближения к корню за итерацию: какая-либо норма ||Х^к+1) - Х<к)||. Например, можно заканчивать расчет, если изменение каждой переменной X} на итерации окажется меньше заданной допустимой погрешности.

Условие сходимости метода в многомерном случае сводится к тому, чтобы якобиан системы функций (определитель матрицы Якоби, состоящей из производных функций) был по модулю меньше единицы. Конечно, в реальных задачах оценивать якобиан нереально. Так что просто остается в силе рекомендация разд. 4.4: строить уравнения так, чтобы функции по возможности имели малые производные. А в алгоритме реализации надо предусматривать проверку, не расходится ли метод, как это делалось в одномерном случае.

Многомерный метод Ньютона выглядит следующим образом. Исходная система уравнений имеет вид:

Г(Х) = о и задано начальное приближение корня Х*°). Обозначим как Х<к) приближение корня, полученное на к-ой итерации. Тогда на следующей к+1-ой итерации строится линейная аппроксимация Га(Х) вектора функций Г(Х) вида ра(Х) = г(х(к)) + а(х(к)) . (х - х(к))

где J - матрица Якоби, т.е. матрица, элементами которой являются частные производные:

4.8 Решение систем нелинейных уравнений

и определяется значение вектора X = Х(к+1), при котором эта аппроксимация равна нулю. Нетрудно видеть, что это сводится к расчету очередного приближения по формуле х(к+1) = х(к) + д где вектор А - поправка Ньютона, определяемая решением системы линейных уравнений а(х(к)) • А = - г(х(к)) . (4.14)

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

Так же, как и одномерный вариант, многомерный метод Ньютона может расходиться. Поэтому чаще применяют модифицированный метод, описанный в разд. 4.5. Формула (4.12) этого метода в многомерном случае имеет вид:

Х(К+1) = Х(к) + £ . Д/ (4Л5)

где поправка Ньютона А по-прежнему определяется соотношением (4.14).

Для того чтобы организовать выбор параметра отслеживается поведение невязки на двух последовательных итерациях. Под невязкой в данном случае понимается какая-то норма вектора Е(Х), например, максимальная по модулю величина т^(Х). Тогда алгоритм модифицированного метода Ньютона на некоторой к+1-ой итерации сводится к следующему:

Шаг 1. 1; = 1.

Шаг 2. Из решения системы (4.14) определяется поправка Ньютона А.

Шаг 3. Рассчитывается по соотношению (4.15) значение Х<к+1).

Шаг 4. Рассчитывается максимальная невязка - значение |^(Х(к+1))|тах.

Шаг 5. Текущая невязка |^(Х(к+1))|тах сравнивается с невязкой на предыдущей итерации |11(Х*к>)|тах. Если |^(Х(к+1>)|тах > |^(Х(к))|тах, значит метод начинает расходиться. Тогда параметр t уменьшается (например, в 2 раза) и происходит возврат на шаг 3.

Шаг 6. Проверяются критерии окончания. Если они выполнены, то расчет завершается. В противном случае переходом на шаг 1 начинается следующая итерация.

Как видно из приведенного алгоритма, если невязка все время уменьшается, то параметр Ь всегда равен 1 и алгоритм работает как обычный метод Ньютона. Но если невязка возросла, то повторяются шаги 3-5 со все уменьшающимся параметром пока невязка на данной итерации не станет меньше или хотя бы равной невязке предыдущей итерации. Таким образом, данный метод не может расходиться, так как невязка просто не может увеличиваться от итерации к итерации.

Повторение шагов 3-5 при возникновении опасности расходимости - не слишком трудоемкий процесс. Он не связан с вычисление поправки Ньютона А и, значит, не требует расчетов производных и решения системы (4.14). Однако так как теоретически цикл по шагам 3-5 может оказаться бесконечным, надо ограничить минимальное значение параметра Если t станет меньше некоторого предельного значения, следует прервать расчет, известив пользователя об отсутствии сходимости.

4.7 Приложение для решения уравнения автоматически выбираемым методом || Оглавление || 4.8.2 Программная реализация методов


Приемы программирования в Delphi на основе VCL



Новости за месяц

  • Май
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс