Численная устойчивость алгоритмов линейной алгебры¶

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

¶Сущность проблемы

При вычислениях на ЭВМ каждое число представляется с относительной погрешностью порядка машинного эпсилон (обычно 10⁻¹⁶ для double). В ходе выполнения алгоритма эти локальные ошибки накапливаются. Для некоторых алгоритмов (например, наивного исключения Гаусса без выбора ведущего элемента) накопление может быть катастрофическим: ошибка растёт экспоненциально или пропорционально 2ⁿ, где n — размерность матрицы. Устойчивые алгоритмы ограничивают рост ошибки полиномом низкой степени (обычно O(n³)).

¶Классификация

Различают два основных типа устойчивости:

• Прямая (прямой анализ ошибок) — оценивается разность между вычисленным и точным результатом при одинаковых входных данных. Требует знания точного решения, что на практике недоступно.
• Обратная (обратный анализ ошибок) — введена Джеймсом Уилкинсоном в 1960-х годах. Вычисленное решение рассматривается как точное решение задачи с малыми возмущениями входных данных. Алгоритм называется обратно устойчивым, если относительная норма возмущения входных данных имеет порядок машинного эпсилон.

Обратная устойчивость является предпочтительной характеристикой, так как она не зависит от обусловленности задачи.

¶Обусловленность и устойчивость

Устойчивость алгоритма не следует путать с обусловленностью задачи. Обусловленность — свойство самой математической задачи (например, матрицы), показывающее, насколько чувствительно решение к малым изменениям входных данных. Число обусловленности cond(A) = ||A|| · ||A⁻¹||. Даже идеально устойчивый алгоритм не может дать точный результат для плохо обусловленной задачи: относительная ошибка решения ограничена снизу величиной cond(A) · ε.

Соотношение между ними выражается неравенством: ошибка решения ≤ (фактор устойчивости алгоритма) × (число обусловленности) × ε. Для обратно устойчивых алгоритмов фактор устойчивости близок к единице.

¶Примеры устойчивых и неустойчивых алгоритмов

¶Устойчивые алгоритмы

• Метод Гаусса с выбором ведущего элемента (частичным или полным) — обратно устойчив, коэффициент роста ограничен.
• QR-разложение (через отражения Хаусхолдера или вращения Гивенса) — обратно устойчиво для большинства задач.
• Сингулярное разложение (SVD) — обратно устойчиво.
• Метод сопряжённых градиентов для симметричных положительно определённых матриц — устойчив на практике.

¶Неустойчивые алгоритмы

• Метод Гаусса без выбора ведущего элемента — для матриц с малыми ведущими элементами (например, матриц Гильберта) даёт катастрофическую потерю точности.
• Вычисление собственных значений через характеристический полином — крайне неустойчиво, так как корни полинома чрезвычайно чувствительны к возмущениям коэффициентов.
• Решение линейных систем через обратную матрицу (вычисление A⁻¹ и умножение на b) — в два-три раза менее устойчиво, чем прямое решение методом Гаусса.

¶Критерии и методы оценки

На практике устойчивость оценивают через коэффициент роста элементов матрицы в процессе преобразований (например, для метода Гаусса — отношение максимального элемента на промежуточных шагах к максимальному элементу исходной матрицы). Для обратной устойчивости проверяют невязку: r = b − A·x̂. Малая относительная невязка (||r|| / (||A||·||x̂||) ~ ε) свидетельствует об обратной устойчивости.

¶Значение для практики

Численная устойчивость определяет применимость алгоритма в реальных вычислениях. Для больших разреженных систем (например, в методе конечных элементов) выбор неустойчивого алгоритма приводит к полной потере точности. Современные библиотеки (LAPACK, Eigen, MATLAB) реализуют исключительно обратно устойчивые алгоритмы, что гарантирует достоверность результатов для широкого класса задач.

Интересный факт: метод Гаусса с частичным выбором ведущего элемента на практике почти всегда устойчив, хотя строгого доказательства полиномиальной ограниченности коэффициента роста не существует — контрпримеры (матрицы Райта) дают рост порядка 2ⁿ, но они крайне искусственны и не встречаются в прикладных задачах.

¶Источники

• Уилкинсон Дж. Х. «Алгебраическая проблема собственных значений». — М.: Наука, 1970.
• Голуб Дж., Ван Лоун Ч. «Матричные вычисления». — М.: Мир, 1999.
• Тыртышников Е. Е. «Основы численных методов линейной алгебры». — М.: Физматлит, 2017.
• Higham N. J. «Accuracy and Stability of Numerical Algorithms». — SIAM, 2002.