Примеры итерационных методов

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

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

Примеры итерационных методов

Пример 1. Метод релаксации представляет собой частный случай метода (4.29):

, ; задан, (4.29)

когда , . Это стационарный итерационный метод, который можно записать в виде

,

где (расписать, дом зад №5).

Метод сходится, если . В данном случае (доказать, дом зад №5) и

.

Пример 2. Метод Ньютона для системы уравнений (4.27)

,

, (4.27)

...

,

строится следующим образом.

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

и отбросим величины второго порядка малости. Тогда система (4.27) заменится системой уравнений

, (4.32)

линейной относительно приращений , . Решение системы (4.32) примем за следующее приближение и обозначим через

.

Таким образом, итерационный метод Ньютона для (4.27) определяется системой уравнений

, (4.33)

из которой последовательно, начиная с заданного , находятся векторы , .

Систему (4.33) можно записать в векторном виде (доказать, дом зад №5)

, , задан, (4.34)

где матрица определена выше. Таким образом, метод Ньютона имеет канонический вид (4.29)

, ; (4.29)

где

, .

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

Приведем без доказательства теорему о сходимости метода Ньютона.

Пусть множество -мерных вещественных векторов с нормой , норма матрицы , подчиненная данной норме вектора. Обозначим

и предположим, что в шаре функции , непрерывно дифференцируемы.

Теорема 2. Предположим, что в матрица удовлетворяет условию Липшица с постоянной , т. е.

для любых . Пусть в матрица существует, причем элементы ее непрерывны и

.

Если начальное приближение таково, что и

,

причем

,

то система уравнений (4.28) имеет решение , к которому сходится метод Ньютона (4.34). Оценка погрешности дается неравенством

.

Без доказательства.

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

(4.35)

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

Пример 4. Метод Ньютона с параметром имеет вид

. (4.36)

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

Пример 5. Нелинейный метод Якоби для системы (4.27) имеет вид (расписать, дом. зад. №5)

, . (4.37)

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

Пример 6. Нелинейный метод Зейделя состоит в последовательном решении уравнений (расписать, дом. зад. №5)

(4.38)

относительно переменной , .

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

Приведем пример гибридного метода.

Пример 7. Внешние итерации – по Зейделю, а внутренние по Ньютону. Здесь в качестве основной (внешней) итерации выбирается нелинейный метод Зейделя (4.38), а для нахождения используется метод Ньютона. Обозначим . Тогда внутренние итерации определяются следующим образом:

(4.39)

, , , .

Здесь индексом обозначен номер внутренней итерации.

Иногда в (4.39) делают всего одну внутреннюю итерацию, полагая , , . Тогда приходим к следующему итерационному методу:

(4.40)

В частности, при метод (4.40) принимает вид

(4.41)

(расписать m=3, l=2, дом. зад. №5)