24. Метод Ньютона в многомерном случае. Организация итерационного алгоритма.

Пусть задана система нелинейных уравнений

или в более компактной форме: f(x)=0, где ─ -мерная вектор-функция (вектор-столбец). Для реализации метода решения и исследования сходимости необходимо, чтобы функции были достаточно гладкими, например, , где . Рассмотрим i-ое уравнение системы: и пусть - некоторое приближение к корню , полученное на k-ой итерации. Разложим функцию в многомерный ряд Тейлора в точке :

,

(17)

где -

- вектор-градиент функции в точке , а - скалярное произведение векторов a и b. Пренебрегая остаточным членом в (17), положим

или в более компактной матричной форме:

,

(18)

где

-

- так называемая матрица Якоби первых производных в точке .

Пусть . Разрешим систему линейных алгебраических уравнений (18) относительно x:

И положим :

(19)

Векторное уравнение (19) представляет собой итерационную процедуру Ньютона в многомерном случае. Для ее запуска необходимо задать начальную точку . Однако при произвольном выборе начальной точки нельзя гарантировать сходимость процедуры Ньютона. Вопрос о сходимости (19) в теоретическом плане более сложный, чем тот же вопрос о сходимости метода Ньютона в одномерном случае. Рассмотрим некоторые основные моменты проблемы исследования сходимости процедуры (19).

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

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

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

Замечание. Строгую формулировку достаточных условий сходимости метода Ньютона в многомерном случае можно найти в цитируемой литературе (см., например, [2]). На практике эти условия, как правило, проверить чрезвычайно сложно. Поэтому при работе на компьютере (например, в пакете MATLAB) используют метод проб и ошибок при выборе начальной точки . На начальном этапе важно найти так называемую зону притяжения, т.е. такую область , что при выборе процедура (19) сходится.

25. Численные методы решения слау. Прямые и итерационные методы, общие понятия.

Пусть задана система линейных алгебраических уравнений (ЛАУ) в стандартной форме:

,

где - матрица , , , .

Если - то решение системы существует и единственно.

Формальное решение системы можно записать по известным формулам Крамера

,

где определители вычисляются по известному правилу.

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

Прямые методы основаны на последовательном исключении неизвестных и приведении матрицы A к треугольному виду (метод Гаусса и его модификации, основанные на определенном правиле выбора главного элемента). Эти методы дают решение СЛАУ за конечное число арифметических операций – это их основное преимущество. Число операций, затрачиваемых на приведение системы к треугольному виду и последующее решение пропорционально . Основной недостаток прямых методов – возможно сильное накопление ошибок округлений при делении на малые числа. Кроме того, возможно возникновение так называемой неустранимой погрешности, если система (и соответственно матрица ) плохо обусловлена. Это свойство систем обсуждается далее в п.п.3.4.2.

Итерационные методы более эффективны в вычислении и применяются для разреженных (слабо заполненных) систем порядка и более.

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