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

Не всегда малость невязки гарантирует малость погрешности найденного решения.

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

|| e ||»|| x ||∙|| A ||∙ e ₁.

Но даже если невязка мала, вектор ошибки не обязательно мал:

||D x ||»|| x ||∙cond(A)∙ e ₁.

Обусловленность – это внутреннее свойство матрицы A, не зависит от метода решения СЛАУ. Матрицы с большим числом обусловленности дают большие ошибки при решении систем. Логарифм числа обусловленности приближенно равен числу значащих цифр, теряемых в решении системы Ax = b.

.

Например, при e ₁»10^–7, cond(A)»10⁴, относительная ошибка решения будет»10^–3, т.е. рассчитывать можно на три верных разряда в решении.

Число cond(A) измеряет насколько близка к вырожденной матрица A и, что еще важнее, насколько чувствительно решение системы Ax = b к изменениям в A и b.

A – вырожденная, если для некоторых b решение системы Ax = b не существует, а для других b оно будет не единственным. Если матрица A – почти вырожденная, то можно ожидать, что малые изменения A и b вызовут очень большие изменения в x.

Умножение x на матрицу A приводит к вектору Ax, норма которого может сильно отличаться от x ||. Это изменение нормы прямо связано с чувствительностью матрицы.

Þ || Ax || £ M∙|| x ||

Þ m∙|| x || £ || Ax ||

Отношение M/m и называют числом обусловленности матрицы A:

, (6.10)

обозначение cond от английского слова conditioned – обусловленный.

Но – норма, согласованная с нормой x.

Обозначим образ оператора Ax за y: y = Ax. Тогда x=A ^–1 y. При x ¹ 0, y ¹ 0.

.

Таким образом:

cond(A)= A ||∙|| A ^–1||. (6.11)

Покажем, что cond(A) измеряет чувствительность к погрешностям. Пусть правая часть уравнения Ax = b получила приращение («возмущение») D b, т.е. вместо истинного вектора b используется приближенный вектор b. Реакцией решения x на возмущение D b правой части будет вектор поправок D x, т.е. x +D x – решение уравнения

A (x +D x)= b +D b.

Так как Ax = b, A D x =D b, откуда D x = A ^–1D b. Нормируем равенства и воспользуемся свойством нормы:

|| b || = || Ax || £ || A ||∙|| x ||,

||D x || = || A ^–1D b || £ || A ^–1||∙||D b ||,

где матричная норма согласована с векторной нормой. Перемножим два неравенства одинакового смысла:

|| b ||∙||D x || £ || A ||∙|| x ||∙|| A ^–1||∙||D b ||,

откуда

, т.е.

. (6.12)

Легко показать, что то же самое число cond(A) служит коэффициентом роста относительных погрешностей при неточном задании элементов матрицы A. А именно, если матрица A получила возмущение D A и x +D x – решение возмущенной системы

(A +D A)(x +D x)= b,

то справедливы неравенства

и. (6.13)

С более точным соотношением зависимости относительной погрешности решения d _x от относительных погрешностей d _A и d _b одновременно можно познакомиться в учебнике В.М.Вержбицкого «Основы численных методов», с. 30.

Основные свойства числа обусловленности:

1. Так как M ≥ m, cond(A) ≥ 1.

2. Умножение матрицы A на число не меняет числа обусловленности:

cond(с∙ A) = cond(A).

3. Если D – диагональная матрица, то

.

Если мы рассмотрим матрицу

,

то cond (A) = 1 и матрица идеально обусловлена, в то время как det (A) = 10^–100. Таким образом, этот пример демонстрирует, что малость определителя матрицы A является необходимым, но не достаточным условием плохой обусловленности системы.

Число обусловленности играет фундаментальную роль в анализе ошибок округления, совершаемых в ходе гауссова исключения. Пусть A и b заданы точно, x ^* – приближенное решение, полученное методом Гаусса в арифметике с плавающей точкой. Тогда

и, где c – обычно немного больше 1.

Основной результат в исследовании ошибок округления в гауссовом исключении принадлежит Дж.Х.Уилкинсону. Он доказал, что вычисленное решение x ^* точно удовлетворяет системе

(A +D A) x ^* = b,

где D A – матрица, элементы которой имеют величину порядка ошибок округления в элементах матрица A. Тем самым все ошибки округления могут быть слиты воедино и рассматриваться как единственное возмущение, внесенное в матрицу A в момент записи в память компьютера, само же исключение осуществляется без ошибок. В этом смысле метод Гаусса – лучший алгоритм решения СЛАУ. Контроль качества вычислений может быть осуществлен по вектору невязок только для хорошо обусловленных систем