Численные методы линейной алгебры

Обусловленность системы линейных алгебраических уравнений

Система линейных алгебраических уравнений (СЛАУ) в развернутой форме записывается следующим образом

(1.1)
Из теории линейной алгебры следует, что система уравнений (1.1) имеет решение (совместна) при любых правых частях в том и только в том случае, если соответствующая однородная система имеет только тривиальное решение х₁=х₂=…х_n=0. Необходимым и достаточным условием этого является условие, когда матрица А

имеет определитель, отличный от нуля, т.е. detA0. Условие совместности системы (1.1) при любых правых частях detA0 обеспечивает и единственность решения. С использованием матрицы А систему (1.1) можно переписать в виде

или в матричной форме
Ax=b. (1.2)
Пусть требуется найти решение системы (1.2). Задача решения системы (1.2) поставлена, корректна, если

1. 
   решение задачи существует;
   
2. 
   решение единственно;
   
3. 
   решение непрерывно зависит от входных данных.
   

Известно, что требования 1 и 2 будут выполнены, если detA0. Требование 3 нуждается в детализации. Входными данными в задаче (1.2) являются коэффициеты a_ij матрицы А и компоненты вектора .
Если входные данные А и заданы с некоторой погрешностью А, b, то вместо системы (1.2) решается задача
(А+А)(х+х)=b+b. (1.3)
Тогда возникает вопрос о том, как связана погрешность решения х с погрешностями входных данных А или b.
Пусть вначале А=0, а b0. Тогда из формулы (1.3) получим
Ах+Ах=b+b. (1.4)
После вычитания из (1.4) выражения (1.2) получим
Ах=b,
х=А^-1b,
следовательно
║х║║А^-1║║b║. (1.5)
Таким образом, связь между ║х║ и ║b║ установлена. Однако на практике более естественна связь между нормами относительных погрешностей, а не абсолютных.
Так как
║b║║А║║х║, (1.6)
то из (1.5) и (1.6) получим
║х║║b║║А║║А^-1║║х║║b║
или
║х║/║x║║А║║А^-1║║b║/║b║. (1.7)

Теперь пусть b=0, А0. Дополнительно предположим, что А таково, что

det(A+А)0. Тогда из формулы (1.3) получим
х+х=(A+А)^-1b. (1.8)
После вычитания из (1.8) х= А^-1b получим
х=[(A+А)^-1-A^-1]b. (1.9)
Введем обозначение
B=(A+А)
и используя тождество
B^-1- A^-1= A^-1(A-B)B^-1
находим, что
B^-1- A^-1= -A^-1А(А+А)^-1
или
(A+А)^-1- A^-1= -A^-1А(А+А)^-1. (1.10)
После подстановки (1.10) в (1.9) получим
х= -A^-1А(А+А)^-1b,
откуда
b= -х/[ A^-1А(А+А)^-1] . (1.11)
После подстановки (1.11) в (1.8) получим
х= -A^-1А(х+х)
или
║х║║А^-1║║А║║х+х║, (1.12)
║х║/║x+х ║║А║║А^-1║║А║/║А║. (1.13)
Из (1.5) и (1.12) следует, что если ║b║0 или ║А║0, то ║х║0. Это и означает непрерывную зависимость решения задачи (1.2) от входных данных. Следовательно, условия detA0, det(A+А)0 обеспечивают корректную постановку задачи (1.2).
Входящее в оценки (1.7) и (1.13) число (А)=║А║║А^-1║ называется числом обусловленности матрицы А.


Определение 1.3. Если число (А) относительно мало, то матрица А является хорошо обусловленной. Если число (А) относительно велико, то матрица А является плохо обусловленной.

Для плохо обусловленной СЛАУ недопустима, велика правая часть в неравенствах (1.7) и (1.13). Поэтому лишь очень малые погрешности входных данных задачи (1.2) гарантируют приемлемую относительную погрешность решения.

Определение 1.4. Число (А) для произвольной квадратной матрицы А удовлетворяет условию
(А) max_A/min_A1, (1.14)
где _A – собственное число матрицы А.


Определение 1.5. Число (А) для симметричной матрицы А удовлетворяет условию
(А)= max_A/min_A=1.


Пример 1.1. Дана матрица
. (1.15)
Для оценки числа обусловленности этой матрицы воспользуемся формулой (1.14). Как известно собственные значения матрицы А являются корнями характеристического уравнения
detA-E=0,
²+4+0,0003-0.
Далее получим ₁=-0,0001, ₂=-3,9999, откуда (А)₂/₁=399994^.10⁴. Отсюда следует, что матрица А плохо обусловленная.


Пример 1.2. Рассмотрим уравнение Ах=b, где матрица А задана выражением (1.15), . Тогда точное решение .
Допустим вектор b задан с погрешностью, т.е. имеем , тогда получим решение . Оценим относительную погрешность решения при b0. Из примера 1.1 известно (А) 4^.10⁴. Тогда несмотря на малость ║b║/║b║1,4143^.10^-4 относительная погрешность решения велика, т.е. ║х║/║x║0,9618(А)║b║/║b║5,6772.