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

Обусловленность измеряет чувствительность решения задачи к возмущениям в ее данных, в то время как устойчивость измеряет величину ошибки, которую конкретный алгоритм добавляет при вычислениях с конечной точностью; вместе они определяют точность вычисленного результата.

Definition

Обусловленность — это внутреннее свойство задачи, описывающее, как ее точное решение реагирует на возмущения входных данных, тогда как численная устойчивость — это свойство алгоритма, описывающее, насколько точно он решает задачу, несмотря на ошибки округления.

Scope

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

Core questions

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

Key theories

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

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

Анализ обратной ошибки

Вместо того чтобы напрямую ограничивать ошибку в ответе, показывается, что вычисленный результат является точным ответом для близкой задачи; алгоритм является обратно устойчивым, когда эта близкая задача отличается от исходной на величину порядка единичной ошибки округления.

Прямая ошибка равна числу обусловленности, умноженному на обратную ошибку

Центральное эмпирическое правило численного анализа гласит, что прямая ошибка (ошибка решения) приблизительно ограничена числом обусловленности задачи, умноженным на обратную ошибку, четко разделяя вклады задачи и алгоритма.

Mechanisms

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

Clinical relevance

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

History

Концептуальная основа была заложена Уилкинсоном, чей анализ обратной ошибки в 1960-х годах объяснил практическую надежность метода Гаусса и впоследствии был систематизирован и расширен на всю область Хайэмом; стандарт IEEE 754 для чисел с плавающей запятой впоследствии обеспечил надежную и переносимую основу для поведения округления.

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

Если алгоритм стабилен, всегда ли он будет давать точный ответ?

Нет. Обратно устойчивый алгоритм гарантирует лишь, что его ответ точен для близкой задачи; если сама задача плохо обусловлена, эта близкая задача может иметь очень другое решение, поэтому прямая ошибка все еще может быть большой.

Что такое единичная ошибка округления?

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