Число обусловленности матрицы как найти

Число обусловленности матрицы

Дается очень интуитивное представление о важной характеристике квадратной матрицы, существенной для решения систем линейных уравнений с этой матрицей.

Пример. Система линейных уравнений $ AX =\mathcal B $ при

$$ A=\left(\begin-2 & 2 \\ 19 & -18 \end \right), \ B= \left(\begin1 \\ 2 \end \right),\ X= \left(\beginx_1 \\ x_2 \end \right), $$ имеет решение $ X_0= [11.0, 11.5]^ $. При небольшом возмущении столбца правых частей $ \mathcal B= [1.0,2.1]^ $ решение меняется в пределах того же возмущения: $ X= [11.1, 11.6]^ $. Но вот при $ \mathcal B= [1.1,2.0]^ $ решение изменится более существенно: $ X= [11.9, 12.45]^ $. Обнаруженный эффект принципиально важен для численных методов решения систем линейных уравнений: с какой точностью следует производить вычисления?

Для выяснения причины этого эффекта будем искать геометрическое место точек плоскости $ \mathbb R^2 $, удовлетворяющих неравенству $$ (-2 x_1 +2x_2-1)^2+(19x_1 -18 x_2-2)^2 \le \varepsilon^2 \iff $$ $$ \iff (AX-\mathcal B)^(AX-\mathcal B) \le \varepsilon^2 $$ при различных значениях $ \varepsilon $, в частности, при $ \varepsilon = 0.1 $. Очевидным решением является внутренность эллипса с центром в точке $ X_0 $. Этот эллипс оказывается очень «сплюснутым»: так, при $ \varepsilon = 0.1 $, его полуоси равны $ \approx 1.31624 $ и $ \approx 0.00380 $. При любом выборе $ X $ внутри эллипса погрешность столбца $ \widetilde= AX $ относительно столбца $ \mathcal B $ не превосходит $ \varepsilon $. Однако при одной и той же величине погрешности в столбце $ \mathcal B $ соответствующие решения системы могут меняться как очень немного, так и значительным образом.

Известно, что форма эллипса, заданного неявным алгебраическим уравнением второго порядка, определяется только мономами второго порядка. В разбираемом примере — элементами матрицы $$ A^ A = \left(\begin365 & -346 \\ -346 & 328 \end \right) \, . $$ Полуоси определяются через посредство собственных чисел этой матрицы. Именно, $$ \lambda_1\approx 0.00577, \lambda_2 \approx 692.99422 $$ и длины полуосей равны $ 1/ \sqrt $ и $ 1/ \sqrt $. В геометрии величина отношения длин малой полуоси к большой называется коэффициентом сжатия эллипса или эллиптичностью. А в алгебре обратная величина, т.е. $$ \sqrt \approx 346.49711 $$ носит другое название. ♦

Для матрицв $ A \in \mathbb R^ $ обозначим $ \sigma_ $ ее максимальное сингулярное число, а $ \sigma_ $ — минимальное. При $ \sigma_ \ne 0 $ величина $$ \operatorname (A)= \sigma_/\sigma_ $$ называется числом обусловленности матрицы 1) $ A $. Очевидно, $ \operatorname (A) \ge 1 $. При $ \operatorname (A) $ близком к $ 1 $ матрица называется хорошо обусловленной, при $ \operatorname (A) \gg 1 $ матрица $ A $ называется плохо обусловленной 2) .

Пример. Матрица Вандермонда

$$ V= \left(\begin1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2^2 & 2^3 & 2^4 \\ 1 & 3 & 3^2 & 3^3 & 3^4\\ 1 & 4 & 4^2 & 4^3 & 4^4\\ 1 & 5 & 5^2 & 5^3 &5^4 \end \right) $$ может считаться плохо обусловленной: $ \operatorname (V) \approx 26169 $.

Пример. Матрица Гильберта

$$ \mathfrak H_4= \left[\frac \right]_^4 = \left( \begin1 & 1/2 & 1/3 & 1/4 \\ 1/2 & 1/3 & 1/4 & 1/5 \\ 1/3 & 1/4 & 1/5 & 1/6 \\ 1/4 & 1/5 & 1/6 & 1/7 \end \right) $$ плохо обусловлена: $ \operatorname (\mathfrak H_4) \approx 15513 $.

Число обусловленности матрицы

Число обусловленности матрицы показывает насколько матрица близка к матрице неполного ранга (для квадратных матриц — к вырожденности).

Рассмотрим систему линейных уравнений

Если матрица A вырожденная, то для некоторых b решение x не существует, а для других b оно будет неединственным. Следовательно, если A почти вырожденная, то можно ожидать, что малые изменения в A и b вызовут очень большие изменения в x. Если же взять в качестве A единичную матрицу, то решение системы (1) будет x=b. Следовательно, если A близка к единичной матрице, то малые изменения в A и b должны влеч за собой малые изменения в x.

Рассмотрим это на численном примере

 

Как видно из Рис. 1, векторы строки матрицы A — и линейно зависимы. Следовательно существует нуль-пространство N(A) ортогональное к и . Так как b∈R(A), имеем множество решений ,,. . Если же взять , то b∉R(A) и, следовательно, система линейных уравнений не имеет решения. Далее, изменим в (2) вектор строку матрицы A. Пусть . Тогда система (2) имеет единственное решение . Получили, что малое изменение в A или b совешенно меняет решение системы (2). Такие матрицы называют плохо обусловленными.

Для оченки обусловленности матрицы вычисляют число обусловленности матрицы (обозначается символом "cond"). Для вычисления числа обусловленности введем понятия нормы для векторов x. В качестве нормы возмем l-норму вектора:

Умножая вектор х на матрицу A приводит к новому вектору Ax, норма которого может слишком отличаться от нормы вектора x. Эта чувствительность матрицы A мы хотим измерять. Максимальное и минимальное изменение Ax при изменении можно задать следующими числами:

Отношение Q/q называется числом обусловленности матрицы A:

В системе (1) изменим b на Δb. Тогда имеем:

Из (1) и (7) следует A·Δx=Δb. Тогда, учитывая (4) и (5) получим следующие неравенства:

Следовательно при q≠0 имеем:

При относительном изменении правой части , относительная ошибка может составить .

Если q=0, то cond(A)=+∞, т.е. матрица неполного ранга (вырожденная). Чем больше cond(A), тем ближе матрица A к неполному рангу (к вырожденности). Чем ближе матрица к единичной матрице, тем больше cond(A) близка к 1 и , следовательно, матрица далека от неполного ранга (далека от вырожденности).

Свойства числа обусловленности матрицы:

1. cond(A)>=1 (т.к. Q>=q).
2. cond(P)=1, где P-матрица перестановок или единичная матрица.
3. cond(λA)=cond(A), где λ скаляр.
4. , где D диагональная матрица.

Свойства 3 и 4 показывают, что cond(A) является лучшей критерией оценки вырожденности квадратных матриц, чем определитель. Действительно, если взять в качестве матрицы A квадратную диагональную матрицу 100×100 с элементами 0.1 на главной диагонали, то det(A)=(0.1) 100 =10 -100 , что очень малое число и показывает близость к вырожденности в то время, как строки и столбцы матрицы ортогональны и, в действительности матрица далека от вырожденности. Если же применять cond, то получим cond(A)=1.

Следующий пример иллюстрирует понятие числа обусловленности матрицы. Рассмотрим систему линейных уравнений (1), где

Тогда решением системы линейных уравнений будет . Если же правую заменить на , решением системы будет . Обозначим Δb=b-b1 и Δx=x-x1. Тогда

Из (13) видно, что очень малое изменение в b, совершенно изменил решение x. Так как

Неравенство (15) показывает что матрица A плохо обусловлена, т.е. близка к вырожденности. С помощью экспериментальных вычислений мы обнаружили плохую обусловленность матрицы A. А как, на самом деле, вычислить число обусловленности матрицы. В выражении (4) Q называется нормой матрицы и ее можно вычислить с помощью следующего вырaжения:

где a_j — j-ый столбец матрицы A. Оказывается, что 1/q является нормой обратной к A (если существует) матрицы A -1 : . Тогда

Вы можете вычислить обусловленность матрицы используя матричный онлайн калькулятор. Для этого вычислите обратную к матрице A, вычислите нормы для матриц A и A -1 и, используя выражение (17), вычислите cond(A).

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

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

( 2.4)

( 2.5)

Теорема. Пусть правая часть и невырожденная матрица СЛАУ (2.4) вида соответственно. Пусть существует обратная матрица

( 2.6)

При получаем оценку при наличии погрешности только правых частей

( 2.7)

если в (2.5) положить

( 2.8)

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

( 2.9)

называется числом обусловленности матрицы Число обусловленности определяет, насколько погрешность входных данных может повлиять на решение системы (2.1) . Почти очевидно, что всегда Действительно

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