Число обусловленности матрицы - как посчитать и зачем

Число обусловленности матрицы - это величина, которая показывает, насколько чувствительно решение системы линейных уравнений $Ax = b$ к малым возмущениям в исходных данных. Если матрица «хорошо обусловлена», небольшая ошибка в правой части $b$ или в коэффициентах $A$ даёт небольшую ошибку в ответе $x$. Если же матрица плохо обусловлена, та же самая погрешность округления может полностью испортить результат - и не из-за плохого алгоритма, а из-за свойств самой задачи. Понимание числа обусловленности критично в численных методах, машинном обучении (регрессия), обработке сигналов и везде, где приходится решать СЛАУ на компьютере с конечной точностью.

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

Для невырожденной квадратной матрицы $A$ число обусловленности определяется как произведение нормы матрицы на норму обратной:

$$\operatorname{cond}(A) = \kappa(A) = \|A\| \cdot \|A^{-1}\|.$$

Здесь $\|\cdot\|$ - какая-либо согласованная (индуцированная) матричная норма. Значение всегда удовлетворяет $\kappa(A) \geq 1$, причём $\kappa(A) = 1$ достигается, например, на ортогональных матрицах. Чем больше число обусловленности, тем «хуже» матрица: значение порядка $10^{3}$ ещё терпимо, $10^{8}$ при вычислениях с двойной точностью означает потерю примерно половины значащих цифр, а $10^{16}$ и выше в double фактически делает матрицу численно вырожденной.

Если матрица вырождена ($\det A = 0$), обратной не существует, и число обусловленности считают равным $+\infty$. Важно: малый определитель сам по себе ещё не говорит о плохой обусловленности - определитель зависит от масштаба, а $\kappa(A)$ инвариантно к умножению матрицы на скаляр, что делает его гораздо более надёжным индикатором.

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

Связь с устойчивостью решения СЛАУ

Главный смысл величины $\kappa(A)$ раскрывается в оценке погрешности. Пусть мы решаем $Ax = b$, но правая часть известна с возмущением $\delta b$, так что фактически решается $A(x + \delta x) = b + \delta b$. Тогда относительная погрешность решения ограничена:

$$\frac{\|\delta x\|}{\|x\|} \leq \kappa(A) \cdot \frac{\|\delta b\|}{\|b\|}.$$

Число обусловленности играет роль коэффициента усиления ошибки. Если $\kappa(A) = 10^{6}$, то относительная ошибка во входных данных в $10^{-9}$ может вырасти до $10^{-3}$ в ответе. Аналогичная оценка работает и при возмущении самой матрицы $A$ на $\delta A$:

$$\frac{\|\delta x\|}{\|x\|} \lesssim \kappa(A) \cdot \frac{\|\delta A\|}{\|A\|}.$$

Практическое правило: при решении в арифметике с $t$ десятичными значащими цифрами и числе обусловленности $\kappa(A) \approx 10^{p}$ в ответе можно доверять примерно $t - p$ цифрам. Это объясняет, почему плохо обусловленные системы дают «мусор» даже при идеально точном алгоритме исключения Гаусса.

Стоит отличать обусловленность задачи от устойчивости алгоритма. Обусловленность - это внутреннее свойство самой матрицы $A$ и постановки задачи; она не зависит от того, каким методом мы решаем систему. Устойчивость же характеризует конкретный численный алгоритм: насколько он не привносит дополнительной ошибки сверх неизбежной. Хороший (обратно устойчивый) метод гарантирует, что вычисленное решение является точным решением слегка возмущённой системы. Но даже самый аккуратный алгоритм бессилен против большого $\kappa(A)$: если задача плохо обусловлена, малое возмущение, заложенное уже в представлении чисел с плавающей точкой, неизбежно усилится в $\kappa(A)$ раз. Поэтому диагностику всегда начинают с оценки числа обусловленности, а не с выбора метода.

Спектральное число обусловленности

Самый употребительный вариант - спектральное (2-норменное) число обусловленности, основанное на сингулярных числах. Для произвольной матрицы оно равно отношению наибольшего сингулярного числа к наименьшему:

$$\kappa_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}.$$

Сингулярные числа $\sigma_i$ - это арифметические корни из собственных чисел матрицы $A^{\top}A$. Для симметричной положительно определённой матрицы сингулярные числа совпадают с собственными числами, и формула упрощается до отношения максимального собственного числа к минимальному:

$$\kappa_2(A) = \frac{\lambda_{\max}}{\lambda_{\min}}.$$

Геометрически $\kappa_2$ показывает, насколько сильно матрица «вытягивает» единичную сферу в эллипсоид: отношение самой длинной полуоси к самой короткой. Близкое к единице число обусловленности означает почти изотропное преобразование, а большое - что одно из направлений почти «схлопывается» (этому отвечает малое сингулярное число).

Спектральное число обусловленности обладает удобными свойствами: оно инвариантно относительно умножения на ортогональную матрицу ($\kappa_2(QA) = \kappa_2(A)$ при ортогональной $Q$), поскольку ортогональные преобразования сохраняют длины и сингулярные числа. Именно поэтому в численных методах предпочитают ортогональные (QR, Гивенс, Хаусхолдер) преобразования: они не ухудшают обусловленность задачи. Для самосопряжённых положительно определённых матриц вычисление $\kappa_2$ сводится к нахождению крайних собственных чисел, что дешевле полного SVD и реализуется, например, степенным методом для $\lambda_{\max}$ и обратным степенным для $\lambda_{\min}$.

Разные нормы - разные числа

Поскольку определение использует норму, существует несколько чисел обусловленности одной и той же матрицы. Все они конечно различаются, но эквивалентны с точностью до множителя, зависящего от размерности $n$.

• $\kappa_1(A)$ - по столбцовой норме $\|A\|_1 = \max_j \sum_i |a_{ij}|$ (максимальная сумма модулей по столбцу).
• $\kappa_\infty(A)$ - по строчной норме $\|A\|_\infty = \max_i \sum_j |a_{ij}|$ (максимальная сумма модулей по строке).
• $\kappa_2(A)$ - спектральное, через сингулярные числа (самое точное, но дорогое в вычислении).
• $\kappa_F(A)$ - приближённая оценка через норму Фробениуса $\|A\|_F = \sqrt{\sum_{i,j} a_{ij}^2}$.

В библиотеках вроде LAPACK число обусловленности обычно оценивают в норме $\|\cdot\|_1$ или $\|\cdot\|_\infty$ функцией типа gecon, потому что точное вычисление $\|A^{-1}\|_1$ заменяют дешёвой оценкой без полного обращения. Если же нужна именно $\kappa_2$, считают сингулярное разложение (SVD). Подбор подходящей нормы - часть смежной темы про нормы и согласованность в итерационных методах СЛАУ.

Как улучшить плохо обусловленную задачу

Если $\kappa(A)$ велико, само переписывание алгоритма не спасёт - нужно менять постановку. Основные приёмы:

• Масштабирование (балансировка) - домножение строк и столбцов на диагональные матрицы так, чтобы выровнять порядки коэффициентов. Часто это самый дешёвый способ снизить $\kappa$.
• Предобуславливание - замена системы $Ax = b$ на $M^{-1}Ax = M^{-1}b$, где матрица $M$ близка к $A$, но легко обратима; тогда $\kappa(M^{-1}A) \ll \kappa(A)$, и итерационные методы сходятся быстрее.
• Регуляризация Тихонова - для задач наименьших квадратов решается $(A^{\top}A + \alpha I)x = A^{\top}b$; добавка $\alpha I$ поднимает минимальное собственное число и снижает обусловленность ценой малого смещения.
• Ортогонализация - использование QR-разложения вместо нормальных уравнений; решение через $A^{\top}A$ возводит число обусловленности в квадрат, $\kappa_2(A^{\top}A) = \kappa_2(A)^2$, чего QR избегает.

Числовой пример

Рассмотрим симметричную матрицу

$$A = \begin{pmatrix} 1 & 1 \\ 1 & 1{,}0001 \end{pmatrix}.$$

Её собственные числа примерно равны $\lambda_{\max} \approx 2{,}00005$ и $\lambda_{\min} \approx 0{,}00005$, поэтому $\kappa_2(A) \approx 4 \cdot 10^{4}$. Это значит, что относительная ошибка во входных данных усиливается примерно в сорок тысяч раз: при возмущении правой части на $10^{-6}$ решение может «уехать» на $4 \cdot 10^{-2}$. Геометрически две строки матрицы - почти параллельные прямые, точка их пересечения определяется крайне неустойчиво. Это классический портрет плохо обусловленной системы.

Частые ошибки

• Путают малый определитель с плохой обусловленностью. Определитель зависит от масштаба, $\kappa(A)$ - нет; ориентироваться надо именно на число обусловленности.
• Считают, что виноват алгоритм. Большое $\kappa(A)$ - свойство самой задачи; никакой устойчивый метод не вернёт точности, которой нет во входных данных.
• Решают через нормальные уравнения $A^{\top}A$. Это возводит число обусловленности в квадрат и теряет вдвое больше цифр, чем прямое QR-разложение.
• Игнорируют масштаб переменных. Несбалансированные единицы измерения (метры и миллиметры в одной матрице) искусственно раздувают $\kappa$; помогает простое масштабирование.
• Сравнивают $\kappa$ в разных нормах напрямую. $\kappa_1$, $\kappa_2$ и $\kappa_\infty$ дают разные числа; сопоставлять надо величины в одной и той же норме.

FAQ

Может ли число обусловленности быть меньше единицы? Нет. Для любой согласованной нормы выполняется $\|I\| = \|A A^{-1}\| \leq \|A\|\,\|A^{-1}\| = \kappa(A)$, а $\|I\| \geq 1$, поэтому $\kappa(A) \geq 1$ всегда.

Какое число обусловленности считается «плохим»? Грубый ориентир: при работе с двойной точностью (около 16 значащих цифр) значения до $10^{3}$–$10^{4}$ безопасны, $10^{8}$ означает потерю половины цифр, а выше $10^{12}$ результатам доверять нельзя без специальных мер.

Чем отличается спектральное число обусловленности от остальных? $\kappa_2$ вычисляется через сингулярные числа и даёт наиболее «честную» геометрическую оценку, но требует SVD. Нормы $\kappa_1$ и $\kappa_\infty$ дешевле и используются для быстрых оценок в LAPACK.

Коротко

Число обусловленности $\kappa(A) = \|A\|\,\|A^{-1}\|$ измеряет чувствительность решения СЛАУ к погрешностям входных данных и равно коэффициенту усиления относительной ошибки. Спектральный вариант $\kappa_2 = \sigma_{\max}/\sigma_{\min}$ имеет наглядный геометрический смысл, а оценка «теряем $\log_{10}\kappa$ значащих цифр» позволяет заранее понять, сколько точности останется в ответе. Плохо обусловленные задачи лечат масштабированием, предобуславливанием, регуляризацией и ортогональными разложениями, а малый определитель индикатором обусловленности не является.