Не всегда малость невязки гарантирует малость погрешности найденного решения.
Гауссово исключение с выбором главного элемента гарантированно дает малые невязки. Малость здесь трактуется относительно, т.е. по отношению к элементам матрицы A, элементам матриц в промежуточных вычислениях и к компонентам вычисленного решения.
|| e ||»|| x ||∙|| A ||∙ e 1.
Но даже если невязка мала, вектор ошибки не обязательно мал:
||D x ||»|| x ||∙cond(A)∙ e 1.
Обусловленность – это внутреннее свойство матрицы A, не зависит от метода решения СЛАУ. Матрицы с большим числом обусловленности дают большие ошибки при решении систем. Логарифм числа обусловленности приближенно равен числу значащих цифр, теряемых в решении системы Ax = b.
.
Например, при e 1»10–7, cond(A)»104, относительная ошибка решения будет»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 в момент записи в память компьютера, само же исключение осуществляется без ошибок. В этом смысле метод Гаусса – лучший алгоритм решения СЛАУ. Контроль качества вычислений может быть осуществлен по вектору невязок только для хорошо обусловленных систем