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

7.4. Модификации метода Ньютона

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

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

1) вычисление компонент вектора

2) вычисление компонент матрицы Якоби

3) решение системы линейных алгебраических уравнений (7.16).

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

1. Упрощенный метод Ньютона.

Заменим в расчетных формулах метода Ньютона (7.16), (7.17) матрицу зависящую от постоянной матрицей . В результате получим расчетные формулы упрощенною метода Ньютона:

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

По сравнению с методом Ньютона число итераций, необходимое для достижения заданной точности существенно возрастает. Тем не менее общие вычислительные затраты могут оказаться меньше. Причины этого состоят в следующем. Во-первых, вычисление матрицы Якоби производится здесь только один раз; во-вторых, как нетрудно видеть, при использовании упрощенного метода Ньютона (7.19), (7.20) многократно решается система линейных уравнений с фиксированной матрицей А и различными правыми частями. Это означает, что при решении систем (7.19) методом Гаусса возможно применение LU-разложения матрицы А, которое резко уменьшает число операций, необходимых для вычисления (см. гл. 5).

2. Использование формул численного дифференцирования.

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

Параметры это конечно-разностные шаги

Если в расчетных формулах метода Ньютона (7.16), (7.17) заменить матрицу аппроксимирущей ее матрицей с элементами то получим следующий итерационный метод:

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

Следующие три метода можно рассматривать как варианты метода (7.22), (7.23), в которых реализованы специальные подходы к вычислению вектора Для того чтобы приведенные ниже рассуждения были формально корректными, в формуле (7.21) положим если оказалось, что

3. Метод ложного положения.

Пусть с — фиксированный вектор. Положим Тогда формулы (7.21) — (7.23) определяют метод ложного положения, обладающий линейной скоростью сходимости в случае, если вектор с и начальное приближение выбраны достаточно близко к решению.

4. Метод секущих.

В одном из наиболее популярных своих вариантов метод секущих можно рассматривать как метод (7.21) — (7.23), где Метод секущих является двухшаговым: для вычисления очередного приближения используют два предыдущих приближения Для того чтобы начать вычисления, необходимо задать два начальных приближения

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

5. Метод Стеффенсена.

Вычисления по методу Стеффенсена производят по формулам (7.21) — (7.23), где

Замечательно то, что хотя этот метод не требует вычисления

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

По-видимому, для решения нелинейных систем вида (7.1) метод Стеффенсена чаще окажется лучшим выбором, чем метод секущих или метод ложного положения.

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

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