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

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

Постановка задачи

Дана система линейных уравнений

                   (1)

Введём обозначения: вектор  - вектор аргументов:

Аналогично вектор функций

Рекомендуемые материалы

Тогда систему 1 можно переписать в виде:

Система линейных уравнений в общем виде неразрешима. Поэтому мы будем рассматривать только численные методы решения системы линейных уравнений.

Метод Ньютона

Для уравнения имеет вид:

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

где  - вектор аргументов на -ом шаге итерации

 - значения вектора функций (системы уравнений ) при

 - обратная матрица Якоби

- матрица, Якоби-матрица, состоящая из частных производных

Вполне естественно очевидно, что формулу Ньютона можно применять в том случае, когда Якоби-матрица неособенная, невырождённая, то есть .

Пример:

Дано:

Матрица Якоби

Превоначальная оцнка

1)          

2)  

3)  

-=-=

и так далее

Результаты итераций лучше всего сводить в таблицу

Прекращаем вычисления, когда  - заданная точность.

Как и в любых численных методах встают следующие задачи: о сходимости метода и о выборе начального значения.

Сходимость метода Ньютона

Вопросами сходимости метода Ньютона занимались такие учёные, как Виллус, Стёпин, Островский, Канторович и другие. Мы же будем рассматривать сходимость, единственность корня и выбор начального условия по Канторовичу. При рассмотрении этих характеристик метода ипользуются понятия нормы. Поэтому прежде дадим определения :

-нормой - называется максимальная сумма модулей элементов по строкам.

-нормой - называется максимальная сумма модулей элементов по столбцам.

-нормой - нызывается квадратный корень из суммы квадратов модулей элементов матрицы

Пример:

Для оценки матриц, используемых в методе Ньютона для нелинейных систем, будем использовать -нормы, а именно

Теорема о существовании корней и сходимости процесса Ньютона

Пусть дана нелинейная система уравнений

,

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

1)  матрица Якоби при  имеет обратную функцию

   

2)  

3)  

4)  постоянные  удовлетворяют неравенству

Тогда процесс Ньютона при начальном приблежении  сходится к решению  - есть решение такое, что

Для проверки условия  даёт оценку расходимости начального и первого приблежения.

Быстрота сходимости процесса Ньютона

Если выполнимы все четыре условия теоремы 1, то для последовательных приближений ,  справедливо неравенство:

где  - искомое решение, а

При  сходимость метода - сверхбыстрая.

Единственность решения

Если выполнимы все четыре условия, в области

то содержится единственное решение системы

Выбор начального условия

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

Модифицированный метод Ньютона

При использовании метода Ньютона наиболее трудоёмким является процесс вычисления обратной матрицы Якоби.

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

Метод итераций

Дана система нелинейных уравнений:

или

             (1)

Допустим, что систему 1 можно привести к виду:

           (2)

Введём обозначения:

,       ,

Можно систему уравнений 2 переписать в виде:

Приведённое матричное уравнение и есть формула метода итераций

Необходимое и достаточное условие сходимости процесса итерации

Пусть функции  и  непрерывны в области , причём в области  выполнимо неравенство:

где  - некоторая константа.

Если последовательные приближения

,     

не выходят из области , то этот процесс сходится к единственному решению системы.

Следствие:

оценка пиближённо

На практике лучше всего рассматривать матрицу с элементами

Для сходимости должно выполнятся условие

1)  

2)  

3)  

Метод скорейшего спуска (градиентный метод)

Дана система линейных уравнений:

            (1)

В матричном виде

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

Рассмотрим функцию

      (2)

Очевидно, что если мы найдём решение системы уравнений 1 , то это решение является и решением системы уравнений 2 и наоборот.

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

Берём точку  - нулевое приближение. Через точку  проходит поверхность уровня и . Если  близка , то поверхность = будет похожа на элипсоид.

Из точки  движемся по нормали к поверхности  до тех пор, пока эта нормаль не коснётся  другой поверхности:

И так далее.

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

Градиент функции U

 - набла или grad - есть вектор приложенный к точке , имеющий направление нормали. Из векторных произведений

,              (3)

Как определить ? Для этого рассматривают скалярную функцию :

Уравнение 3 можно преобразовать так, чтобы не было явного выражения градиента. Введем обозначения , тогда итерационная формула градиентного метода будет иметь вид:

,

где

Вычисления производятся до тех пор, пока не станет справедливым следующее неравенство:

e,

где e - заданная точность вычисления.

Пример. Дана система нелинейных уравнений:

Найти решение системы градиентным методом с точностью e=0,01

Определим начальное приближение как:

Вектор-функция имеет вид:

Якобиан, или матрица частных производных имеет вид:

1 итерация

2 итерация

  

Решение системы нелинейных уравнений представлено в таблице:

Вместе с этой лекцией читают "Экскурсия и ее сущность".

Таким образом, решение системы уравнений имеет вид:

Сходимость градиентного метода

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

В любом случае метод может остановитья в точке относительного метода.