Числа обусловленности

Число обусловленности системы при заданной правой части

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

\[ \mathbf{A x}=\mathbf{f}, \]

а также систему, получающуюся из нее возмущением правой части на вектор \(\delta f\) (это не \(\delta\) умноженное на \(f\), а вектор возмущения):

\[ A \mathrm{x}^{\prime}=\mathrm{f}+\delta \mathrm{f} . \]

В силу линейности,

\[ \delta \mathrm{x} \equiv \mathrm{x}^{\prime}-\mathrm{x}=\mathbf{A}^{-1} \delta \mathbf{f} . \]

Оценим относительную погрешность решения в некоторой норме

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathrm{x}\|}=\frac{\left\|\mathbf{A}^{-1} \delta \mathbf{f}\right\|}{\|\mathrm{x}\|} \leqslant \frac{\left\|\mathbf{A}^{-1}\right\|\|\delta \mathbf{f}\|}{\|\mathrm{x}\|}=\frac{\left\|\mathbf{A}^{-1}\right\|\|\mathrm{f}\|}{\|\mathrm{x}\|} \cdot \frac{\|\delta \mathbf{f}\|}{\|\mathrm{f}\|} \]

Считаем, что матричная норма согласована с векторной, и мы можем оценить \(\left\|\mathbf{A}^{-1} \delta \mathbf{f}\right\|\) сверху произведением норм \(\left\|\mathbf{A}^{-1}\right\| \cdot\|\delta \mathbf{f}\|\).

Мы получили связь между относительной погрешностью решения и относительной погрешностью правой части системы уравнений:

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathrm{x}\|} \leqslant \frac{\left\|\mathbf{A}^{-1}\right\|\|\mathrm{f}\|}{\|\mathrm{x}\|} \cdot \frac{\|\delta \mathbf{f}\|}{\|\mathrm{f}\|} . \]

Величина

\[ \mathcal{V}(\mathbf{A}, \mathbf{f})=\frac{\left\|\mathbf{A}^{-1}\right\|\|\mathbf{f}\|}{\|\mathbf{x}\|}=\frac{\left\|\mathbf{A}^{-1}\right\|\|\mathbf{f}\|}{\left\|\mathbf{A}^{-1} \mathbf{f}\right\|} \]

называется числом обусловленности системы при заданной правой части и показывает, во сколько раз может возрасти относительная погрешность решения по сравнению с погрешностью правой части при решении системы \(\mathbf{A x}=\mathbf{f}\).

Отметим, что \(\left\|\mathbf{A}^{-1} \mathbf{f}\right\| \leqslant\left\|\mathbf{A}^{-1}\right\|\|\mathbf{f}\|\), и число \(\mathcal{V}\) всегда не меньше единицы.

Примечание о достижении равенства:

При выводе оценки

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \mathcal{V}(\mathbf{A}, \mathbf{f}) \frac{\|\delta \mathbf{f}\|}{\|\mathbf{f}\|}, \quad \mathcal{V}(\mathbf{A}, \mathbf{f})=\frac{\left\|\mathbf{A}^{-1}\right\|\|\mathbf{f}\|}{\|\mathbf{x}\|} . \]

неравенство возникло из

\[ \left\|\mathbf{A}^{-1} \delta \mathbf{f}\right\| \leqslant\left\|\mathbf{A}^{-1}\right\| \cdot\|\delta \mathbf{f}\|, \]

которое для подчиненных норм является точным. То есть, можно предъявить такой вектор \(\delta f\), что для него неравенство превратится в равенство, а оценка

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \mathcal{V}(\mathbf{A}, \mathbf{f}) \frac{\|\delta \mathbf{f}\|}{\|\mathbf{f}\|} \]

станет равенством

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|}=\mathcal{V}(\mathbf{A}, \mathbf{f}) \frac{\|\delta \mathbf{f}\|}{\|\mathbf{f}\|} . \]

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

С одной стороны, число обусловленности \(\mathcal{V}(\mathbf{A}, \mathbf{f})\) не может быть меньше единицы (опять-таки, можно предъявить \(\mathrm{f}\), на котором \(\mathcal{V}(\mathbf{A}, \mathbf{f})=1)\), но может ли оно для заданной матрицы \(\mathbf{A}\) принимать сколь угодно большие значения?

Найдем универсальную, не зависящую от \(f\), оценку сверху числа обусловленности:

\[ \mathcal{V}(\mathbf{A}, \mathbf{f}) \leq \sup _{\mathbf{f} \neq \mathbf{0}} \frac{\left\|\mathbf{A}^{-1}\right\|\|\mathbf{f}\|}{\left\|\mathbf{A}^{-1} \mathbf{f}\right\|}=\left\|\mathbf{A}^{-1}\right\| \sup _{\mathbf{x} \neq \mathbf{0}} \frac{\|\mathbf{A} \mathbf{x}\|}{\|\mathbf{x}\|}=\left\|\mathbf{A}^{-1}\right\| \cdot\|\mathbf{A}\| . \]

Данная оценка достигается, когда \(\|\mathbf{A} \mathbf{x}\|=\|\mathbf{A}\| \cdot\|\mathrm{x}\|\).

Число \(\mu(\mathbf{A}) \equiv\|\mathbf{A}\| \cdot\left\|\mathbf{A}^{-1}\right\|\) называется числом обусловленности матрицы и дает универсальную оценку относительной погрешности решения системы с матрицей А:

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \mu(\mathbf{A}) \frac{\|\delta \mathbf{f}\|}{\|\mathbf{f}\|} \]

какой бы ни была правая часть \(\mathbf{f}\).

Общая оценка погрешности при возмущённой матрице

Можно показать, что если возмущается не только правая часть \(\mathrm{f}\), но и сама матрица \(\mathbf{A}\), то при условии \(\left\|\mathbf{A}^{-1}\right\| \cdot\|\delta \mathbf{A}\|<1\) верно

\[ \frac{\|\delta \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \frac{\mu(\mathbf{A})}{1-\mu(\mathbf{A}) \frac{\|\delta \mathbf{A}\|}{\|\mathbf{A}\|}}\left(\frac{\|\delta \mathbf{f}\|}{\|\mathbf{f}\|}+\frac{\|\delta \mathbf{A}\|}{\|\mathbf{A}\|}\right) \]

Это и есть погрешность решения при погрешности коэффициентов решения.

Доказательство можно найти в Петров И.Б., Лобанов А.И. Лекции по вычислительной математике, 2006, стр. 37.

Некоторые свойства числа обусловленности

• При \(||\mathbf{x}|| = 1\) выполняется \(\mu = \frac{sup||\mathbf{Ax}||}{inf||\mathbf{Ax}||}\)

• \(\mu \geq \frac{\max\limits_{i}|\lambda_i(\mathbf{A})|}{\min\limits_{i}|\lambda_i(\mathbf{A})|}\)

• \(\mu \geq 1\)
  

• \(\mu(\mathbf{AB}) \geq \mu(\mathbf{A})\mu(\mathbf{B})\)

Вычисление чисел обусловленности в разных нормах

Общая формула для евклидовой нормы

Число обусловленности \(\mu(\mathbf{A})\) зависит от выбранной матричной нормы. Например, для евклидовой нормы \(\sigma_{\max }\left(\mathbf{A}^{-1}\right)=\frac{1}{\sigma_{\min }(\mathbf{A})}\) и число обусловленности матрицы в евклидовой норме принимает вид

\[ \mu_e(\mathbf{A})=\frac{\sigma_{\max }(\mathbf{A})}{\sigma_{\min }(\mathbf{A})} = \sqrt{\frac{\lambda_\text{max}(\mathbf{A}^{\top} \mathbf{A})}{\lambda_\text{min}(\mathbf{A}^{\top} \mathbf{A})}} \]

Оценка числа обусловленности для бесконечной и \(\ell_1\) нормы

Поскольку бесконечная и \(\ell_1\) матричные нормы связаны соотношением

\[ \|\mathbf{A}\|_{\infty}=\left\|\mathbf{A}^{\top}\right\|_1, \]

аналогично оказываются связанными числа обусловленности

\[ \mu_{\infty}(\mathbf{A})=\mu_1\left(\mathbf{A}^{\top}\right) \]

Трудность практической оценки числа обусловленности заключается в оценке нормы \(\left\|\mathbf{A}^{-1}\right\|\). Введем важное понятие диагонального преобладания.

Строгое диагональное преобладание

Определение. Обозначим \(d_i=\left|a_{i i}\right|-\sum_{j \neq i}\left|a_{i j}\right|\). Говорят, что матрица имеет строгое диагональное преобладание, если для каждой строки

\[ d_i>0 \quad \Leftrightarrow \quad\left|a_{i i}\right|>\sum_{j \neq i}\left|a_{i j}\right|, \quad \forall i=1, \ldots, n \]

Т.е. диагональное преобладание означает, что модуль \(i\)-го элемента на диагональ больше суммы модулей всех остальных элементов на \(i\)-ой строке.

Теорема (Varah, 1974).

Если матрица А имеет строгое диагональное преобладание, то

\[ \left\|\mathbf{A}^{-1}\right\|_{\infty}<\frac{1}{\min _i d_i}=\frac{1}{\min _i\left|a_{i i}\right|-\sum_{j \neq i}\left|a_{i j}\right|} \]

Подставляя эту оценку в определение \(\mu_{\infty}(\mathbf{A})\), получаем

\[ \mu_{\infty}(\mathbf{A})<\frac{\max _i\left|a_{i i}\right|+\sum_{j \neq i}\left|a_{i j}\right|}{\min _i\left|a_{i i}\right|-\sum_{j \neq i}\left|a_{i j}\right|} . \]

Аналогичная оценка для \(\mu_1(\mathbf{A})\) получается при наличии у матрицы диагонального преобладания по столбцам.

Оценка для конкретной задачи

Вернемся к системе

\[\begin{split} \left(\begin{array}{cc} 10 & 9 \\ 9 & 8 \end{array}\right)\left(\begin{array}{l} x_1 \\ x_2 \end{array}\right)=\left(\begin{array}{c} 19 . \\ 17 . \end{array}\right), \quad \mathbf{A}^{-1}=\frac{1}{-1}\left(\begin{array}{cc} 8 & -9 \\ -9 & 10 \end{array}\right) \end{split}\]

и посчитаем ее числа обусловленности в разных нормах:

\[\begin{split} \begin{aligned} \|\mathbf{A}\|_{\infty}=&\|\mathbf{A}\|_1=19, \quad\left\|\mathbf{A}^{-1}\right\|_{\infty}=\left\|\mathbf{A}^{-1}\right\|_1=19 \\ & \mu_1(\mathbf{A})=\mu_{\infty}(\mathbf{A})=19 \cdot 19=361 \end{aligned} \end{split}\]

Матрица симметрична, значит

\[ \mu_e(\mathbf{A})=\left|\frac{\lambda_{\max }(\mathbf{A})}{\lambda_{\min }(\mathbf{A})}\right|=\frac{\sqrt{82}+9}{\sqrt{82}-9} \approx 326 . \]

Таким образом, погрешность в \(3 \%\) в правой части решения приводит примерно к \(1000\%\) ошибки в решении!

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

Фактически, при решении системы

\[\begin{split} \left(\begin{array}{cc} 10 & 9 \\ 9 & 8 \end{array}\right)\left(\begin{array}{l} x_{1} \\ x_{2} \end{array}\right)=\left(\begin{array}{l} 19 \\ 17 \end{array}\right) \end{split}\]

мы пытаемся разложить вектор \(\mathbf{f}=(19,17)^{\top}\) по базису из почти коллинеарных векторов \(\mathbf{e}_{1}=(10,9)^{\top}\) и \(\mathbf{e}_{2}=(9,8)^{\top}\)

Минимальное значение числа обусловленности равно 1 (когда векторы, составленные из коэффициентов матрицы системы, ортогональны), а максимальное значение не ограничено. В некотором приближении можно рассматривать как «меру мультиколлинеарности» гиперплоскостей, которые заданы уравнениями системы - число обусловленности стремится к бесконечности, когда матрица стремится к вырожденной.

С другой стороны, дело не только в том, что матрица может быть близка к вырожденной. Большие числа обусловленности также получаются, когда элементы матрицы сильно отличаются друг от друга, но матрица не стремится к вырожденной. Например

\(\ \mathbf{A}\ =\ diag\ \left(x,1,1\ldots1\right),\ x>1\ \ \ \ \ \ \rightarrow\ ||\mathbf{A}|| = x \)

\(\ \mathbf{A}^{-1}\ =\ diag\ \left(1/x,1,1\ldots1\right),\ x>1\ \ \ \ \ \ \rightarrow\ ||\mathbf{A}^{-1}|| = 1 \)

\(\mu=x\)

Число обусловленности зависит от выбранной нормы и в разных нормах оно может иметь более конкретный геометрический смысл. Например, для евклидовой нормы \(\sigma_{\max }\left(\mathbf{A}^{-1}\right)=\frac{1}{\sigma_{\min }(\mathbf{A})}\) и число обусловленности матрицы в евклидовой норме принимает вид

\[ \mu_{e}(\mathbf{A})=\frac{\sigma_{\max }(\mathbf{A})}{\sigma_{\min }(\mathbf{A})} \]

Геометрически, \(\mu_{e}(\mathbf{A})\) показывает насколько неравномерно преобразование А растягивает пространство по своим главным направлениям. На рисунке изображён круглый диск и результат умножения всех векторов внутри этого диска на матрицу \(\mathbf{A}\)