条件数与数值稳定性

条件数衡量问题解对数据扰动的敏感程度，而稳定性衡量特定算法在有限精度算术中引入的误差量；两者共同决定了计算结果的准确性。

Definition

条件数是问题固有的属性，描述其精确解如何响应输入扰动，而数值稳定性是算法的属性，描述其在舍入误差存在下解决问题的忠实程度。

Scope

本主题涵盖浮点算术和单位舍入误差、线性系统求解和函数求值等问题的条件数、前向误差和后向误差，以及前向误差受条件数乘以后向误差限制的经验法则，以及后向稳定性和前向稳定性的定义。

Core questions

• 浮点算术是如何建模的，单位舍入误差的作用是什么？
• 问题的条件数衡量什么？它如何为线性系统和函数求值定义？
• 前向误差、后向误差和条件数之间有什么关系？
• 后向稳定算法与前向稳定算法有何区别？为什么后向稳定性通常是目标？

Key theories

条件数

条件数是数据中的相对扰动在解中可能被放大的因子；对于线性系统，它等于矩阵范数乘以逆矩阵的范数，并且它设定了可实现精度的上限，与算法无关。

后向误差分析

与其直接限制答案中的误差，不如证明计算结果是附近问题的精确解；当这个附近问题与原始问题的差异在单位舍入误差的量级时，算法是后向稳定的。

前向误差等于条件数乘以后向误差

数值分析的核心经验法则是，前向（解）误差近似受问题条件数乘以后向误差的限制，清晰地分离了问题和算法的贡献。

Mechanisms

浮点数以有限精度表示实数，因此每个基本运算都会产生一个受单位舍入误差限制的相对误差。后向误差分析通过将这些误差归因于数据扰动而非结果来跟踪它们，从而产生以下形式的界限：计算结果等于受扰动输入的精确结果。将后向误差界限与问题的条件数相结合，可以得出前向误差估计，这解释了为什么稳定的算法在病态问题上仍然会失去精度。

Clinical relevance

当计算结果必须可靠时，理解条件数和稳定性至关重要：它解释了为什么某些最小二乘公式会失去精度，指导模拟和数据分析中稳定算法和适定公式的选择，并警告当病态模型无论使用何种方法都无法产生可靠答案时的情况。

History

概念框架由威尔金森（Wilkinson）建立，他在1960年代的后向误差分析解释了高斯消元法的实际可靠性，后来由海厄姆（Higham）在整个领域进行了系统化和扩展；IEEE 754浮点标准随后为舍入行为奠定了坚实且可移植的基础。

Key figures

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

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

如果一个算法是稳定的，它总是能给出准确的答案吗？

不。后向稳定算法只保证其答案对于一个附近问题是精确的；如果问题本身是病态的，那么那个附近问题可能有一个非常不同的解，因此前向误差可能仍然很大。

什么是单位舍入误差？

单位舍入误差是将实数舍入到最近的浮点数时产生的最大相对误差；它设定了浮点算术的粒度，并出现在几乎所有稳定性界限中。