2. Метод ньютона, его реализации и модификации

Пусть – некоторая последовательность невырожден­ных вещественных -матриц. Тогда, очевидно, последовательность задач

,

имеет те же решения, что и исходное уравнение (lа), и для приближенного нахождения этих решений можно формально записать итерационный процесс

, (5)

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

Положим , где

– матрица Якоби вектор - функции . Подставив это в (5), получаем явную формулу метода Ньютона

, (6)

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

. (7)

Применение (7) предполагает при каждом решение линейной алгебраической системы

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

.

К решению таких линейных систем можно привлекать самые раз­ные методы как прямые, так и итерационные (см. гл. 2, 3) в зависимости от размерности решаемой задачи и специфики матриц Якоби (например, можно учитывать их симметрию, разреженность и т.п.).

Сравнивая (7) с формальным разложением в ряд Тейлора

,

видим, что последовательность в методе Ньютона получа­ется в результате подмены при каждом нелинейного уравнения или, что то же (при достаточной гладкости ), уравнения

линейным уравнением

,

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

Фактором, осложняющим применение метода Ньютона к решению -мерных систем, является необходимость решения -мерных линейных задач на каждой итерации (обращения матриц в (6) или решения СЛАУ в (7), вычислительные затраты на которые растут с ростом , вообще говоря, непропорционально быстро. Уменьшение таких затрат – одно из направлений модификации метода Ньютона.

Если матрицу Якоби вычислить и обратить лишь один раз – в начальной точке , то от метода Ньютона (6) придем к модифицированному методу Ньютона

. (8)

Этот метод требует значительно меньших вычислительных за­трат на один итерационный шаг, но итераций при этом может потребоваться значительно больше для достижения заданной точности по сравнению с основным методом Ньютона (6), поскольку, являясь частным случаем МПИ (с ), он имеет лишь скорость сходимости геометрической прогрессии.

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

Например, простое чередование основного (6) и модифицированного (8) методов Ньютона приводит к итерационной формуле

, (9)

где , . За здесь принимается результат последовательного применения одного шага основного, а затем одного шага модифицированного метода, т.е. двухступенчатого процесса

(10)

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

Задачу обращения матриц Якоби на каждом -м шаге мето­да Ньютона (6) можно попытаться решать не точно, а приближенно. Для этого можно применить, например, итерационный процесс Шульца, ограничиваясь минимумом – всего одним шагом процесса второго порядка, в котором за начальную матрицу принимается матрица, полученная в результате преды­дущего -го шага. Таким образом, приходим к методу Ньютона с последовательной аппроксимацией обратных матриц:

, (11)

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

Применение той же последовательной аппроксимации обратных матриц к простейшему рекурсивному методу Ньютона (9) или, что то же, к двухступенчатому процессу (10) определяет его аппроксимационный аналог

, (12)

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

.

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

При удачном задании последовательности малых векторов (постоянной или сходящейся к нулю) полученный таким путем разностный (или иначе, дискретный) метод Ньютона

(13)

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

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

(14)

где

,

Этот метод является двухшаговым и требует задания двух начальных точек и . При сходимость метода (14) имеет порядок . Можно рассчитывать на такую же скорость и в многомерном случае.

К методу секущих так же, как и к методу Ньютона, можно применить пошаговую аппроксимацию обратных матриц на основе метода Шульца. Расчетные формулы этой модификации легко выписать, заменив в совокупности формул ААМН (11) матрицу на матрицу из (14).

Замечание 7.1. Для останова процесса вычислений в быстросходя­щихся методах таких, как метод Ньютона, методы секущих и т.п., часто вполне успешно применяют простой критерий:

. (15)

Это можно объяснить двумя причинами. Во-первых, оценки погрешности здесь довольно «дороги». Имеется в виду как их получение (особенно для различных модификаций базовых методов), так и их реальное применение. Во-вторых, в силу своей быстрой сходимости, к моменту достижения требуемой малости нормы поправки эти методы набирают такую инерцию, что зачастую «проскакивают» установленный порог точности, т.е. выход по критерию (15) дает значение значительно (иногда на несколько порядков) меньшее, чем . Отслеживать факт сходимости в процессе итераций для того, чтобы реагировать на возможную расходимость в случаях, когда заранее не обеспечены условия сходимости применяемого метода, можно с помощью текущих проверок на уменьшение от шага к шагу поправок и невязок, т.е. выполнение неравенств

и . (16)