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

Урок про число обусловленности матрицы — меру «плохости» системы линейных уравнений и предупреждение о ненадёжности решения.

Число обусловленности $\kappa(A) = \|A\| \cdot \|A^{-1}\|$ показывает, во сколько раз относительная ошибка в данных (матрице или правой части) может усилиться в относительной ошибке решения.

Почему система бывает «плохой»

В уроке про обусловленность мы видели две почти параллельные прямые: крошечный сдвиг правой части резко двигал точку пересечения. Для систем $Ax=b$ эту чувствительность измеряет число обусловленности матрицы $\kappa(A)$. Если $\kappa \approx 1$ — система «хорошая», решение устойчиво к шуму. Если $\kappa$ огромно ($10^8$, $10^{12}$) — система плохо обусловлена: даже идеальный решатель вернёт ненадёжный ответ, потому что виноваты сами данные, а не метод.

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

def реши_2x2(A, b):
    det = A[0][0]*A[1][1] - A[0][1]*A[1][0]
    x = (b[0]*A[1][1] - A[0][1]*b[1]) / det
    y = (A[0][0]*b[1] - b[0]*A[1][0]) / det
    return [x, y]

# Почти вырожденная матрица (строки почти пропорциональны)
A = [[1.0, 1.0], [1.0, 1.0001]]
b1 = [2.0, 2.0001]
b2 = [2.0, 2.0002]      # изменили последнюю цифру: возмущение 1e-4

x1 = реши_2x2(A, b1)
x2 = реши_2x2(A, b2)
print("решение при b1:", [round(v, 4) for v in x1])
print("решение при b2:", [round(v, 4) for v in x2])
отн_вход = 0.0001 / 2.0
отн_выход = abs(x2[0] - x1[0]) / abs(x1[0]) if x1[0] else float('inf')
print(f"\nвход изменился на {отн_вход:.2e} (отн.)")
print(f"выход (x) изменился на {abs(x2[0]-x1[0]):.4f} абсолютно")

Вывод:

решение при b1: [1.0, 1.0]
решение при b2: [0.0, 2.0]

вход изменился на 5.00e-05 (отн.)
выход (x) изменился на 1.0000 абсолютно

Возмущение правой части на $0.0001$ сдвинуло $x$ с 1 на 0 — на целую единицу. Усиление колоссальное. Это и есть проявление большого $\kappa(A)$: матрица почти вырождена (её строки почти совпадают), определитель крошечный ($0.0001$), и деление на него раздувает любой шум.

Как оценить κ без библиотек

Точное $\kappa$ требует норм $A$ и $A^{-1}$. Грубую, но показательную оценку можно получить так: решить систему, затем чуть возмутить правую часть и измерить, во сколько раз относительное изменение решения превысило относительное изменение данных. Этот «эмпирический коэффициент усиления» — нижняя оценка $\kappa$.

Как работает под капотом

Формально $\kappa(A) = \sigma_{\max} / \sigma_{\min}$ — отношение наибольшего и наименьшего сингулярных чисел матрицы. Геометрически: $A$ растягивает пространство в $\sigma_{\max}$ раз по одному направлению и в $\sigma_{\min}$ раз по другому; их отношение — «вытянутость» преобразования. Чем сильнее вытянутость, тем сильнее ошибка вдоль «тонкого» направления усиливается при обращении. Классический пример плохо обусловленной матрицы — матрица Гильберта $H_{ij}=1/(i+j-1)$: уже при $n=10$ её $\kappa$ превышает $10^{13}$. В библиотеке оценка — numpy.linalg.cond(A).

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

• Доверять решению, не глядя на $\kappa$. При $\kappa = 10^{10}$ и данных double в ответе достоверны лишь ~6 цифр — остальное шум.
• Винить решатель. Плохая обусловленность — свойство задачи; смена метода не поможет, нужна переформулировка или регуляризация.
• Игнорировать масштабирование. Иногда простое масштабирование строк/столбцов (приведение к сопоставимым величинам) заметно улучшает $\kappa$.

Итоги

• Число обусловленности $\kappa(A) = \|A\| \cdot \|A^{-1}\| = \sigma_{\max}/\sigma_{\min}$ — коэффициент усиления ошибки данных в ошибку решения.
• Большое $\kappa$ $\Rightarrow$ система плохо обусловлена: малый шум в данных рушит решение, и виновата задача, а не метод.
• Правило: $\kappa \approx 10^k$ $\Rightarrow$ теряется около $k$ верных цифр.
• Всегда проверяйте $\kappa$ (например, numpy.linalg.cond) перед тем, как верить решению.