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

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

(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.