Устойчивость алгоритма и обусловленность задачи

Урок различает два понятия, которые легко спутать: обусловленность задачи и устойчивость алгоритма — и показывает, почему важны оба.

Обусловленность — насколько сильно ответ задачи меняется при малом изменении входных данных (свойство задачи). Устойчивость — не раздувает ли алгоритм ошибки сверх неизбежного (свойство метода).

Обусловленность: виновата задача, не алгоритм

Некоторые задачи по своей природе чувствительны: крошечное изменение входа даёт большое изменение ответа. Такие задачи называют плохо обусловленными. Никакой, даже идеальный, алгоритм не спасёт — если данные известны с погрешностью (а они всегда такие), ответ будет неточен. Число обусловленности κ измеряет коэффициент усиления: относительная ошибка ответа ≈ κ × относительная ошибка данных.

# Плохо обусловленная система: две почти параллельные прямые
def реши_2x2(a, b, c, d, e, f):
    det = a * d - b * c
    x = (e * d - b * f) / det
    y = (a * f - e * c) / det
    return x, y

# Прямые почти совпадают: коэффициенты отличаются в 4-м знаке
x1, y1 = реши_2x2(1.0, 1.0, 1.0, 1.001, 2.0, 2.001)
# Чуть-чуть пошевелим правую часть (последнюю цифру)
x2, y2 = реши_2x2(1.0, 1.0, 1.0, 1.001, 2.0, 2.002)

print(f"решение 1: x={x1:.4f}, y={y1:.4f}")
print(f"решение 2: x={x2:.4f}, y={y2:.4f}")
print(f"вход изменился на 0.001, ответ x — на {abs(x2 - x1):.4f}")

Вывод:

решение 1: x=1.0000, y=1.0000
решение 2: x=0.0000, y=2.0000
вход изменился на 0.001, ответ x — на 1.0000

Изменили правую часть на 0.001 — ответ x прыгнул с 1 на 0, изменился на целую единицу! Усиление в тысячу раз. Это плохо обусловленная задача: геометрически мы ищем пересечение двух почти параллельных прямых, и малейший сдвиг резко двигает точку пересечения. Алгоритм тут ни при чём — виновата сама задача.

Устойчивость: виноват алгоритм

Бывает наоборот: задача хорошо обусловлена, а конкретный алгоритм сам раздувает ошибки. Такой алгоритм называют неустойчивым. Пример из прошлого урока — вычисление малого корня через вычитание близких чисел: задача нормальная, но формула плохая. Хороший численщик подбирает устойчивый алгоритм для хорошо обусловленной задачи. А для плохо обусловленной — честно сообщает, что высокая точность недостижима в принципе.

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

Формально число обусловленности задачи y = f(x) в точке — это κ = |x·f'(x) / f(x)| (для функции одной переменной). Большое κ означает: производная велика относительно значения, ответ «крутой» по входу. Для систем линейных уравнений роль κ играет число обусловленности матрицы (отдельный урок в разделе про СЛАУ). Практическое правило: если κ ≈ 10^k, то вы теряете примерно k верных значащих цифр по сравнению с точностью данных. Поэтому при κ = 10^8 и данных с 15 цифрами в ответе достоверны лишь ~7.

import math

# Обусловленность вычисления f(x) = ln(x) около x = 1:
# kappa = |x * f'(x) / f(x)| = |x * (1/x) / ln(x)| = 1/|ln(x)|
for x in [2.0, 1.1, 1.001]:
    kappa = abs(1.0 / math.log(x))
    print(f"x={x:<6}: число обусловленности ln = {kappa:.1f}")

Вывод:

x=2.0   : число обусловленности ln = 1.4
x=1.1   : число обусловленности ln = 10.5
x=1.001 : число обусловленности ln = 1000.5

Чем ближе x к 1 (где ln(x) → 0), тем хуже обусловлено вычисление логарифма: возле x = 1.001 относительная ошибка входа усиливается в тысячу раз. Знание этого помогает заранее понять, где ждать потери точности.

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

• Винить алгоритм за плохую обусловленность. Если задача плохо обусловлена, смена метода не поможет — нужны более точные данные или переформулировка задачи.
• Игнорировать обусловленность СЛАУ. Большое κ(A) — сигнал, что решение системы крайне чувствительно к шуму; результату нельзя слепо доверять.
• Считать, что устойчивый алгоритм даёт точный ответ всегда. Устойчивость лишь гарантирует «не хуже неизбежного» — обусловленность задачи остаётся потолком.

Итоги

• Обусловленность — свойство задачи: коэффициент усиления ошибки данных в ошибку ответа (κ).
• Устойчивость — свойство алгоритма: не раздувает ли он ошибки сверх неизбежного.
• Правило большого пальца: κ ≈ 10^k ⇒ теряется около k верных цифр.
• Цель: устойчивый алгоритм для хорошо обусловленной задачи; для плохо обусловленной высокая точность недостижима в принципе.