1.      Обусловленность СЛАУ.

Ошибки округления в вычислениях по схеме Гаусса.

 

Для того, чтобы найти количественную характеристику обусловленности СЛАУ введем некоторые понятия. Рассмотрим множество Rn  n-мерных вещественных векторов x = (x1, x2,…, xn).

Определение 1. Нормой вектора    x     называется такое действительное число, обозначаемое || x ||,  что;

1)     " (x Î Rn) || x || ³ 0; причем || x || = 0 Û x = 0;

2)     "(l Î R) "(x Î Rn)   || lx || = | l | || x ||;

3)     "(x, y Î Rn) || x + y || £ || x || + || y ||.

Линейное пространство с введенной в ней нормой называется вещественным нормированным пространством.

Векторную норму можно определить различными способами. Например, при помощи каждого из следующих соотношений:

;    ;       ;      

 

Рассмотрим множество Mn вещественных матриц порядка n.

Определение 2. Нормой матрицы   A  называется такое действительное число, обозначаемое || x ||,  что;

1)     " (A Î Mn) || A || ³ 0; причем || A || = 0 Û A = 0;

2)     "(l Î R) "( A Î Mn)   || l A || = | l | || A ||;

3)     "( A, B Î Mn) || A + B || £ || A || + || B ||.

4)     "( A, B Î Mn) || AB || £ || A || || B ||.

Матричную норму, удовлетворяющую следующему условию согласования

"( AÎ Mn) "(x Î Rn)  || Ax || £ || A || || x ||

называют нормой Фробениуса или евклидовой нормой.

Нормы матрицы , согласованные с указанными выше нормами, определяются соответственно соотношениями

;       ;       .

В тех случаях, когда безразлично, какую из норм следует употреблять, пишут просто || x ||, || A ||.

Рассмотрим СЛАУ, записанную в векторно-матричной форме,

Ax = b,                                                                           (2.1)

где - A невырожденная матрица порядка n.

Пусть правая часть уравнения (2.1) получила приращение Db, т.е. вместо истинного вектора b используется приближенный вектор b +Db. Реакцией решения на возмущение правой части будет вектор поправок Dx, т.е., если x - решение системы (2.1), то x +Dx - решение СЛАУ

A(x +Dx) = b +Db                                                                (2.2)

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

Вычитая из (2.2) равенство (2.1) почленно получим равенство

ADx = Db,

из которого находим

Dx = A-1 Db.                                                                     (2.3)

Нормируя равенства (2.1) и (2.3) получаем ||Ax ||= ||b||, ||Dx||= ||A-1 Db||. По свойству согласованной номы выводим

||b|| £ ||A|| ||x ||,       ||Dx|| £ ||A-1 || ||Db||.

Перемножая эти неравенства, получим

||b||×||Dx||  £ ||A||×||x ||×||A-1 ||×||Db||.

Разделим обе части неравенства ||b||×||x || , получим

.                                                            (2.4)

Положительное число .- называется числом или мерой обусловленности матрицы A и обозначается символом cond A.

Можно показать, что число cond A служит коэффициентом роста относительной погрешности при неточном задании элементов матрицы A. Если матрица A получит возмущение DA, x  +Dx - решение возмущенной системы

(A+DA)(x +Dx) = b,

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

.                                     (2.5)

Неравенства (2.4) и (2.5) показывают, что чем больше число обусловленности, тем сильнее сказываются на решении СЛАУ ошибки в исходных данных. Если число велико, то система плохо обусловлена. Используя свойства обратной матрицы, заметим, что

и число обусловленности не может быть меньше 1.

Решение считается ненадежным, если cond A ³ (eмаш)-1 или даже cond A ³ (eмаш)-0,5.

Далее можно получить оценку обусловленности матрицы, через ее собственные значения. Действительно пусть собственные значения матрица упорядочены по модулю:|l1| ³ |l2| ³³ |ln|. Тогда имеет место оценка cond A ³ . Таким образом, эта величина оценкой служит мерой обусловленности снизу. Но непосредственный подсчет обусловленности при больших размерах матрицы дорого стоит из-за необходимости обращать матрицу или находить ее собственные значения.

Пример. Рассмотрим систему из примера 1 лекции 1.3

.

Имеем .Матрица системы , имеет обратную матрицу  Норма  . Тогда число обусловленности

cond A=1101×1011=1113111 > 106.

По формуле (2.4) получаем оценку относительной погрешности

.

Так как норма решения равна 1, то оценка абсолютной погрешности решения равна. Тогда как решение возмущенной системы вписывается в оценку .

При решении системы n уравнений с n неизвестными по методу Гаусса на ЭВМ желательно в памяти ЭВМ хранить всю матрицу. При этом потребуется запомнить n×(n + 2) чисел. При решении СЛАУ с большим числом неизвестных  бывает невозможно хранить в памяти всю матрицу. Поэтому матрицу разбивают на блоки и работают с блоками, что замедляет работу.

Подсчитаем число арифметических операций, необходимых для решения системы линейных уравнений по методу Гаусса. При решении СЛАУ с выбором главного элемента в столбце потребуется n(n - 1) + (n - 1)(n - 2) + …+ 1 + 2 +…+2(n - 2)+2(n - 1) = (n + 1)(n +2)n/3+ +(n + 1)n = O(n3), n3/6 + n2 - n/3 = O(n3) умножений и делений. Таким образом при решении СЛАУ  потребуется O(n3) операций.