3. Контроль точности и уточнение приближенного решения в рамках прямых методов

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

Обозначим полученное приближенное решение через и подставим в исходное уравнение. Вектор называют невязкой приближенного решения . По величине невязки можно с некоторой осторожностью судить о близости найденного решения к точному решению x. Если |||| – недостаточно малая величина, то следует искать вектор поправку такой, что , т.е.

.

Следовательно

.

Нахождение поправки сводится к решению той же системы уравнений, где в качестве столбца свободных членов берется вектор невязки. Так как матрица коэффициентов левой части системы не меняется, нет надобности прямого хода преобразований коэффициентов при неизвестных (другими словами – LU-разложения), достаточно выполнить действия с новыми свободными членами.

Прибавив найденную поправку, получаем уточненное решение . Если величина |||| (или ||||/ ||||) окажется недостаточно малой, процесс уточнения может быть повторен: ищется поправка как приближенное решение системы , где ; тогда более точным должно быть решение .

Но сходимость к нулю невязок в таком процессе может и не наблюдаться. Обычно делают не более двух-трех шагов уточнения, причем рекомендуется производить вычисление невязок в режиме накопления. если в этом процессе не происходит сближения при k=2,3,…, то это говорит скорее всего о плохой обусловленности данной системы и о том, что ее решение не может быть уточнено таким способом.

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

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

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

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

||||||x||∙||A||∙₁.

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

||x||||x||∙cond(A)∙₁.

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

.

Например, при ₁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 – обусловленный.

Но max;\s\do11(x№0 – норма, согласованная с нормой x.

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

.

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

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

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

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

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

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

||x|| = ||A^–1b||  || A^–1||∙||b||,

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

||b||∙||x||  ||A||∙||x||∙|| A^–1||∙||b||,

откуда

, т.е.

. (6.12)

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

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

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

и . (6.13)

С более точным соотношением зависимости относительной погрешности решения _x от относительных погрешностей _A и _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+A)x^* = b,

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