Инструменты сайта


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

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

П

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

Для пояснения причины этого эффекта будем искать геометрическое место точек плоскости $ \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)^{\top}(AX-\mathcal B) \le \varepsilon^2 $$ при различных значениях $ \varepsilon $, в частности, при $ \varepsilon = 0.1 $. Очевидным решением является внутренность эллипса с центром в точке $ X_0 $. Этот эллипс оказывается очень «сплюснутым»: так, при $ \varepsilon = 0.1 $, его полуоси равны $ \approx 1.31624 $ и $ \approx 0.00380 $. При любом выборе $ X $ внутри эллипса погрешность столбца $ \widetilde{\mathcal B}= AX $ относительно столбца $ \mathcal B $ не превосходит $ \varepsilon $. Однако при одной и той же величине погрешности в столбце $ \mathcal B $ соответствующие решения системы могут меняться как очень немного, так и значительным образом.

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

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

§

Только что введенное определение завязано на метрику пространства $ \mathbb R^n $, которая выше предполагалась евклидовой. В пространствах векторов и матриц близость можно определять различными способами, и этот формализм вводится посредством понятия нормы. Соответственно, и число обусловленности вводится в зависимости от формул, задающих нормы3). В интернете можно найти доказательство следующего универсального результата $$ \operatorname{cond} (A)=\|A\| \cdot \|A^{-1}\| \ , $$ который, с практической точки зрения, абсолютно бесполезен. (Если воможно точно вычислить матрицу $ A^{-1} $, зачем вычислять число обусловленности?)

§

Еще одно замечание касается числовых эквивалентов выражений «близко к 1» и «значительно превышает 1». Понятно, что эти выражения субъективны и зависят от требований к точности представлений исходных данных и вычислений в конкретно решаемой задаче. Принято считать $ \operatorname{cond} (A)\le 10 $ хорошим числом, а $ \operatorname{cond} (A)\ge 1000 $ — плохим числом. Но это всё — условности.

П

Пример. Матрица Вандермонда $$ V= \left(\begin{array}{ccccc} 1 & 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{array} \right) $$ может считаться плохо обусловленной: $ \operatorname{cond} (V) \approx 26169.68797 $.

§

Если матрица $ A $ близка к вырожденной, то ее минимальное сингулярное число близко к нулю. Как правило (т.е. для случайно выбранных матриц) максимальное сингулярное число будет существенно отличаться от $ 0_{} $. Поэтому утверждение «матрица, близкая к вырожденной, будет и плохо обусловленной» имеет вероятностную справедливость. Но контрпримеры типа $$ A= \left(\begin{array}{cc} 0.0001 & 0 \\ 0 & 0.0001 \end{array} \right) $$ следует «держать в уме».

1)
(англ.) condition number
2)
(англ.) well- and ill- conditioned
3)
Причем нормы в пространстве векторов и в пространстве матриц должны быть аккуратно между собой согласованы — см. понятие индуцированной нормы
algebra2/condnumber.txt · Последние изменения: 2020/04/19 22:08 — au