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

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

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

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

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

||Dx||»||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^–1y. При x¹0, y¹0.

.

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

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

 

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

A(x+Dx)=b+Db.

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

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

||Dx|| = ||A^–1Db|| £ || A^–1||∙||Db||,

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

||b||∙||Dx|| £ ||A||∙||x||∙|| A^–1||∙||Db||,

откуда

, т.е.

. (6.12)

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

(A+DA)(x+Dx)=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+DA)x^* = b,

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