ВОПРОС 15 (2)

Прямые и итерационные методы решения систем линейных алгебраических уравнений. Примеры методов. Достаточное условие сходимости одношаговых итерационных методов. Сходимость метода Якоби.

Рассмотрим систему линейных алгебраических уравнений

Ax = f, (1)

где А — матрица mхm, х=(х₁ х₂ … х_m)^Т – искомый вектор, f =(f₁ f_{2 …} f_m)^T – заданный вектор. Предполагается, что определитель матрицы А отличен от нуля, так что решение х существует и единственно. Для большинства вычислительных задач характерным является большой порядок матрицы А. Известно, что систему (1) можно решить, по крайней мере, двумя способами: либо по формулам Крамера, либо методом последовательного исключения неизвестных (методом Гаусса). При больших m первый способ, основанный на вычислении определителей, требует порядка m! арифметических действий, в то время как метод Гаусса только O(m³) действий. Поэтому метод Гаусса в различных вариантах широко используется при решении на ЭВМ. задач линейной алгебры.

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

Итерационные методы (их называют также методами последовательных приближений) состоят в том, что решение х системы (1) находится как предел при n->∞ последовательных приближений х⁽ⁿ⁾, где n – номер итерации. Как правило, за конечное число итераций этот предел не достигается. Обычно задается некоторое малое число ε>0 (точность) и вычисления проводятся до тех пор, пока не будет выполнена оценка

||x⁽ⁿ⁾-x||<ε (2)

Число итераций n=n(ε), которое необходимо провести для получения заданной точности е (т. е. для выполнения оценки (2)), для многих методов можно найти из теоретических рассмотрений. Качество различных итерационных процессов можно сравнивать по необходимому числу итераций n(ε).

К прямым методам относятся метод Крамера, метод Гаусса, метод прогонки (для трехдиагональных матриц).

Итерационные методы: метод Якоби, метод Гаусса – Зейделя, метод релаксации.

Исследование сходимости итерационных методов

Рассмотрим систему линейных алгебраических уравнений Ax=f с невырожденной действительной матрицей А и одношаговый стационарный итерационный метод, записанный в каноническом виде

где x₀ задан.

Теорема 1. Пусть А – симметричная положительно определенная матрица, τ>0 и пусть выполнено неравенство

В – 0,5τA>0. (4)

Тогда итерационный метод (2) сходится.

Доказательство. Достаточно показать, что среднеквадратичная норма решения z_n, уравнения (3) стремится к нулю при n->∞ и при любой начальной погрешности z₀. Покажем сначала, что при условии (4) числовая последовательность J_n=(Az_n, z_n) является невозрастающей. Из уравнения (3) найдем

откуда получим

Вследствие симметричности матрицы А имеем

Поэтому

(5)

Отсюда, учитывая условие (4), получаем неравенство

Таким образом, числовая последовательность J_n=(Az_n, z_n) монотонна и ограничена снизу нулем. Следовательно, существует

(6)

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

Отсюда и из (5) получаем неравенство

Переходя в этом неравенстве к пределу при и учитывая (6), убеждаемся в том, что существует

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

и тем самым

Теорема 1 доказана.

Метод Якоби имеет следующий канонический вид

где D=diag[a₁₁, a₂₂, … a_mm]. Таким образом в данном случае B=D, τ=1

Следствие 1. Пусть А – симметричная положительно определенная матрица с диагональным преобладанием, т. е.

(8)

Тогда метод Якоби сходится.

Доказательство. Условие сходимости (4) в данном случае имеет вид A<2D. Покажем, что это матричное неравенство следует из неравенств (8). Рассмотрим положительно определенную квадратичную форму

и воспользуемся оценками

Из условий симметричности и положительной определенности матрицы А имеем a_ij=a_ji, a_ii>0, i,j= 1, 2,..., m, и поэтому предыдущая оценка приводит к неравенству

Перепишем условие (8) в виде

Тогда из неравенства (9) получим

Что и требовалось доказать.