条件数と数値安定性

条件数は、問題の解がデータ摂動に対してどれほど敏感であるかを測定し、安定性は、特定のアルゴリズムが有限精度演算でどれほどの誤差を追加するかを測定します。これらが組み合わさって、計算結果の精度が決定されます。

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

アルゴリズムが安定していれば、常に正確な答えが得られますか？

いいえ。後方安定なアルゴリズムは、その答えが近くの問題に対して厳密であることのみを保証します。問題自体が悪条件である場合、その近くの問題は非常に異なる解を持つ可能性があり、前方誤差は依然として大きくなる可能性があります。

単位丸め誤差とは何ですか？

単位丸め誤差は、実数が最も近い浮動小数点数に丸められたときに発生する最大相対誤差です。これは浮動小数点演算の粒度を設定し、実質的にすべての安定性境界に現れます。