3. Метод Брауна

В отличие от пошаговой линеаризации векторной функции , приведшей к методу Ньютона (6), Брауном (1966 г.), предложено проводить на каждом итерационном шаге поочередную линеаризацию компонент вектор - функции , т.е. линеаризовать в системе (1) сначала функцию затем и т.д., и последовательно решать получаемые таким образом уравнения. Чтобы не затенять эту идею громоздкими выкладками и лишни­ми индексами, рассмотрим вывод расчетных формул метода Брауна в двумерном случае.

Пусть требуется найти решение системы

, (17)

и пусть уже получены приближения , .

Подменим первое уравнение системы (17) линейным, полученным по формуле Тейлора для функции двух переменных:

.

Отсюда выражаем (обозначим этот результат через ):

. (18)

При находим значение переменной :

,

которое будем считать лишь промежуточным приближением (т.е. не ), поскольку оно не учитывает второго уравнения системы (17).

Подставив в вместо переменную , придем к некоторой функции только одной переменной . Это позволяет линеаризовать второе уравнение системы (17) с помощью формулы Тейлора для функции одной переменной:

. (19)

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

.

Дифференцируя по равенство (18), получаем выражение

,

подстановка которого в предыдущее равенство при , дает

.

При известных значениях и теперь можно разрешить линейное уравнение (19) относительно (назовем полученное значение ):

.

Заменяя в (18) переменную найденным значением при­ходим к значению :

.

Таким образом, реализация метода Брауна решения двумерных нелинейных систем вида (17) сводится к следующему.

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

,

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

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

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

4. Метод секущих Бройдена

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

В процессе построения методов Ньютона и секущих реше­ния нелинейного скалярного уравнения.

(20)

функция в окрестности текущей точки подменяется ли­нейной функцией (аффинной моделью)

(21)

Приравнивание к нулю последней, т.е. решение линейного уравнения

порождает итерационную формулу

(22)

для вычисления приближений к корню уравнения (20).

Если потребовать, чтобы заменяющая функцию вбли­зи точки аффинная модель имела в этой точке одинаковую с ней производную, то, дифференцируя (21), получаем значение коэффициента

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

,

или, в соответствии с (21),

, (23)

то получаем коэффициент

,

превращающий (22) в известную формулу секущих.

Равенство (23), переписанное в виде

,

называют соотношением секущих в . Оно легко обобща­ется на -мерный случай и лежит в основе вывода метода Бройдена. Опишем этот вывод.

В -мерном векторном пространстве соотношение се­кущих представляется равенством

, (24)

где , – известные -мерные векторы, – данное нелинейное отображение, а – некоторая матрица ли­нейного преобразования в . С обозначениями

, , (25)

соотношение секущих в обретает более короткую запись:

. (24а)

Аналогично одномерному случаю, а именно, по аналогии с формулой (22), будем искать приближения к решению векторного уравнения (1а) по формуле

. (26)

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

При формировании матрицы будем рассуждать следующим образом.

Переходя от имеющейся в точке аффинной модели функции

(27)

к такой же модели в точке

, (28)

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

.

Представим вектор в виде линейной комбинации фиксированного вектора , определенного в (25), и некоторого вектора , ему ортогонального:

.

Подстановкой этого представления вектора в разность получаем другой ее вид

. (29)

Анализируя выражение (29), замечаем, что первое слагае­мое в нем не может быть изменено, поскольку

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

. (30)

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

.

Таким образом, приходим к так называемой формуле пересчета С. Бройдена (1965 г.)

, (31)

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

Совокупность формул (26), (31) вместе с обозначениями (25) называют методом секущих Бройдена или просто методом Бройдена решения систем нелинейных числовых уравнений.

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

1. решить линейную систему

(32)

относительно вектора (см. (26));

2. найти векторы и (см. (25)):

, ; (33)

3. сделать проверку на останов (например, с помощью проверки на малость величин и/или ) и, если нужная точность не достигнута, вычислить новую матрицу по формуле (см. (31))

. (34)

В качестве матрицы , требуемой равенством (32) для запуска итерационного процесса Бройдена, чаще всего берут матрицу Якоби или какую-нибудь ее аппроксимацию. При этом, как отмечается, получаемые далее пересчетом (34) матрицы , , ... не всегда можно считать близкими к соответствующим матрицам Якоби , , ... (что может иногда сыграть полезную роль при вырождении матриц ). Но, в то же время, показывается, что при определенных требованиях к матрицам Якоби матрицы обладают «свойством ограниченного ухудшения», означающим, что если и происходит увеличение с увеличением номера итерации , то достаточно медленно. С помощью этого свойства доказываются утверждения о линейной сходимости к при достаточной близости к и к , а в тех предположениях, при которых можно доказать квадратичную сходимость метода Ньютона (6), – о сверхлинейной сходимости последовательности приближений по методу Бройдена.

Как и в случаях применения других методов решения нели­нейных систем, проверка выполнимости каких-то условий схо­димости итерационного процесса Бройдена весьма затруднительна и обычно заменяется проверками на выполнимость неравенств типа (16).

Формуле пересчета (34) в итерационном процессе Бройдена можно придать чуть более простой вид.

Так как, в силу (32) и (33),

,

а

,

то из формулы (34) получаем формально эквивалентную ей формулу пересчета

, (35)

которую можно использовать вместо (34) в совокупности с формулой (26) или с (32), (33) (без вычисления вектора ). Такое преобразование итерационного процесса Бройдена несколько сокращает объем вычислений (на одно матрично-векторное умножение на каждой итерации). Не следует, правда, забывать, что при замене формулы (34) формулой (35) может измениться ситуация с вычислительной устойчивостью метода; к счастью, это случается здесь крайне редко, а именно, в тех случаях, когда для получения решения с нужной точностью требуется много итераций по методу Бройдена, т.е. когда и применять его не стоит.