Главная > Математика > Методы вычислений, Т.2
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

Рассмотрим систему уравнений с неизвестными

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

не вырождена. При этих условиях решение а системы (24) можно найти следующим образом. Пусть

— матрица, обратная к Рассмотрим систему уравнений

или коротко в векторной форме

Решение системы (24) является и решением системы (27), которая имеет специальный вид, рассмотренный в п. 1. Покажем, что а можно найти методом итераций, описанным в п. 1, примененным к системе (27), т. е. покажем, что последовательность

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

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

Очевидно, что при

Так как

то

ибо

Используя (32), можно записать (34) в виде

где единичная матрица. Матрица является непрерывной функцией своих аргументов, и при Если достаточно близко к а, то и а матрица достаточно близка к единичной матрице близка к нулевой матрице. Как бы мы ни определили норму вектора х и соответственно норму матрицы, имеет место неравенство

Так как нулевая матрица имеет норму, равную нулю, а

близка к нулевой, то существует такое что если то

Если , то

Следовательно, и

Предположим, что мы уже доказали, что

Тогда

Таким образом, неравенства (38) справедливы при всех Последовательно применяя их, получим неравенство

Так как

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

При более жестких ограничениях на функции можно доказать более сильную теорему, доказательство которой можно найти в статье Канторовича «Функциональный анализ и прикладная математика» ):

Теорема. Если в области О функции имеют вторые производные, не превосходящие по абсолютной величине числа в точке матрица не вырождена и выполнено условие

где

то система (24) имеет решение которое находится в области

и может быть получено как предел последовательности

и быстрота сходимости оценивается неравенством

Векторное равенство (28) эквивалентно системе линейных алгебраических уравнений

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

Вместо системы (27) рассматривают систему

или в векторной записи

где достаточно близок к решению а системы (24), а следовательно и (46), которую также решают методом итераций, описанным в п. 1.

От функций будем требовать выполнения тех же условий, которые накладывались в начале этого пункта. Используя (32), можно записать:

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

а из (47)

т. е. будет иметь место условие Липшица с константой Далее, из (46)

и выбирая достаточно близким к можно добиться выполнения неравенства

а выполнение неравенств (49) и (51), как это было показано в п. 1, гарантирует, что в окрестности существует единственное решение системы (46), которое может быть получено как предел последовательности

где за начальное приближение можно взять любую точку указанной окрестности. Но этим решением и будет т. е.

и сходимость метода доказана.

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

Этот процесс, который можно рассматривать как видоизменение метода Ньютона, хотя сходится и медленней, чем процесс Ньютона,

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

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

Пример. Уточнить по методу Ньютона приближенные значения решения системы

Для этого будем последовательно решать системы:

где

Таким образом, мы получили точное решение.

<< Предыдущий параграф Следующий параграф >>
Оглавление