Обусловленность матриц

МЕТОД ГАУССА-ЗЕЙДЕЛЯ

Лекция 38.

Вторым старым итерационным методом является метод Гаусса-Зейделя (Людвиг Зейдель (1821-1896) – немецкий астроном и математик). Отметим, что этот метод не был известен Зейделю и презирался Гауссом как бесполезный; таковы капризы исторической точности в науке. Изложим идею метода для предыдущей системы. Для этой цели перепишем ее в виде

3x1 = 7 - 4x2 + x3,

2x1 + 6x2 = - 2 - 3x3,

- x1 + x2 + 4x3 = 4.

Здесь в j-м уравнении мы перенесли в правую часть все члены, содержащие xi, для i > j. Эта запись может быть представлена в виде

Пример 38.1.

(L + D)X = -U X + B1,

где, В принятых обозначениях D означает диагональ матрицы A, U - ее верхнюю треугольную часть и L - ее нижнюю треугольную часть. Итеративный процесс в методе Гаусса-Зейделя строится по формуле

Пример 38.2.

(L + D)Xk + 1 = -U Xk + B1, k = 0, 1, 2, _, после выбора соответствующего начального приближения X0. Метод Гаусса-Зейделя можно рассматривать как модификацию метода Якоби. Основная идея модификации состоит в том, что новые значения Xi используются здесь сразу же по мере получения, в то время как в методе Якоби они не используются до следующей итерации. Приведем достаточное условие сходимости метода.

Теорема [1, 4]. Пусть || A2 || < 1, где A2 = -(L + + D)-1U, (L + D)-1 - матрица, обратная к (L + D). Тогда при любом выборе начального приближения X0 метод Гаусса-Зейделя сходится со скоростью геометрической прогрессии, знаменатель которой q # || A2 ||, и верна оценка погрешности || Xk - X || # qk || X0 - X ||.

Матрица A и правая часть B системы (Пример 37.4.) во многих случаях задаются приближенно. Причины погрешностей могут быть самые разные - от ошибок округления при вводе чисел в ЭВМ до ошибок измерения, если система связана с обработкой экспериментальных данных. Ошибки вносит также процесс вычислений. Возникает вопрос, как все это влияет на точность получаемого решения. Для ответа следует познакомиться с особой характеристикой матриц, которую называют обусловленностью.

Рассмотрим уравнение y = Ax, где матрица A ставит в соответствие любому вектору x вектор y. Считая вектор x принадлежащим единичной сфере, подсчитаем длину вектора y = Ax:

Функция j(x) непрерывна на ограниченном замкнутом множестве и поэтому достигает на нем своего максимума и минимума. Тогда

Заметим, что m $ 0; m = 0 тогда и только тогда, когда матрица A вырождена (det A = 0) и однородное уравнение Ax = 0 имеет нетривиальное решение (x? 0).

Отношение называется обусловленностью матрицы A.

Из (Пример 38.1.), (Пример 38.2.) следует двойное неравенство

Пример 38.3.

m # || Ax || # M, || x || = 1.

Для произвольного вектора x в силу линейности y = Ax неравенство (Пример 38.3.) принимает вид:

Пример 38.4.

m || x || # || Ax || # M || x ||.

С помощью этого неравенства исследуем устойчивость решения системы по отношению к малым изменениям входящих в нее величин. Для простейшего случая, когда матрица A задана точно, а правая часть – приблизительно, можно путем несложных вычислений получить оценку

Величина || DB || / || B || характеризует относительное возмущение правой части, а || Dx || / || x || – относительную ошибку в решении, вызванную этим возмущением. Обусловленность матрицы играет в (4) роль множителя, определяющего максимально возможное увеличение ошибки. Если m близко к единице, то система хорошо обусловлена: для такой системы относительная ошибка в решении сравнима с относительной погрешностью задания правой части. По мере увеличения чувствительность решения к погрешности в правой части возрастает - система становится плохо обусловленной.

Пример 38.5.

Рассмотрим систему

x1 + 0 " x2 = 1, det A = 0,01? 0,

x1 + 0,01x2 = 1, x1 = 1, x2 = 0.

Изменим в системе (Пример 38.5.) правую часть:

x1 + 0 " x2 = 1, x1 = 1, x2 = 1,

x1 + 0,01x2 = 1,01.

Видно, что небольшое возмущение правой части системы (Пример 38.5.) привело к существенному изменению решения. Это означает, что матрица A системы (Пример 38.5.) плохо обусловлена. Расчеты дают m(A) ї 200.

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

Дата добавления: 2014-01-04