ピボット要素

ピボットまたはピボット要素は、特定の計算を行うためにアルゴリズム(ガウス消去法、単体法など)によって最初に選択される、行列または配列の要素です。行列アルゴリズムの場合、ピボット エントリは通常、少なくとも 0 と異なる必要があり、多くの場合は 0 から離れている必要があります。この場合、この要素を見つけることは ピボット処理 と呼ばれます。ピボット処理の後に行または列を入れ替えて、ピボットを固定位置にしてアルゴリズムを正常に進め、丸め誤差を減らすことができます。これは、行階段形式を検証するためによく使用されます。

ピボットは、行列内の行または列の交換または並べ替えと考えられるため、順列行列による乗算として表すことができます。ただし、アルゴリズムでは時間がかかりすぎるため、行列要素を移動することはほとんどありません。代わりに、順列を追跡するだけです。

全体的に、ピボット処理により、アルゴリズムの計算コストにさらに多くの操作が追加されます。これらの追加操作は、アルゴリズムが機能するために必要な場合もあります。また、最終結果に 数値の安定性が追加されるため、これらの追加操作が価値のある場合もあります。

ガウス消去法の場合、アルゴリズムではピボット要素がゼロでないことが求められます。ピボット要素がゼロの場合は、行または列を交換する必要があります。以下のシステムでは、消去を実行するために行 2 と行 3 を交換する必要があります。

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}$

ピボットの結果得られるシステムは次のようになり、消去アルゴリズムと後方置換によってシステムにソリューションを出力できるようになります。

${\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}$

さらに、ガウス消去法では、絶対値の大きいピボット要素を選択することが一般的に望ましい。これにより、数値安定性が向上します。次のシステムは、ガウス消去法と後方置換を実行すると、丸め誤差の影響を大きく受けます。

${\displaystyle \left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]}$

このシステムでは、 x ₁ = 10.00 およびx ₂ = 1.000という正確な解が得られますが、4 桁の演算を使用して消去アルゴリズムと後方置換を実行すると、a ₁₁の値が小さいため、小さな丸め誤差が伝播します。ピボットを使用しないアルゴリズムでは、x ₁ ≈ 9873.3 およびx _{2 ≈ 4 という近似値が得られます。この場合、2 つの行を入れ替えて、} a ₂₁がピボット位置になる ようにすることが望ましいです。

${\displaystyle \left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].}$

このシステムを考慮すると、消去アルゴリズムと 4 桁の演算を使用した後方置換により、正しい値x ₁ = 10.00 およびx ₂ = 1.000 が生成されます。

部分ピボットでは、アルゴリズムは、現在ピボット要素と見なされている行列の列から絶対値が最大のエントリを選択します。具体的には、行列を行階段形式に縮小する場合、部分ピボットは、列の行縮小の前に行を入れ替えて、ピボット要素が同じ列の下の要素と比較して最大の絶対値を持つようにします。部分ピボットは、通常、丸め誤差を十分に削減するのに十分です。

ただし、特定のシステムやアルゴリズムでは、許容できる精度を得るために完全なピボット（または最大ピボット）が必要になる場合があります。完全なピボットでは、行と列の両方を交換して、行列内の最大（絶対値）の要素をピボットとして使用します。完全なピボットは、通常、数値安定性を保証するために必要ではなく、最大要素の検索にかかる追加コストのため、完全なピボットによってもたらされる数値安定性の向上は、通常、最小の行列を除くすべての行列での効率の低下によって相殺されます。したがって、めったに使用されません。^[1]

ルークピボットと呼ばれる別の戦略も行と列の両方を交換しますが、選択されたピボットが、残りの部分行列全体で可能な最大のものではなく、その行で可能な最大のエントリとその列で可能な最大のエントリの両方であることのみを保証します。^[2]シリアルコンピュータで実装された場合、この戦略の予想コストは部分ピボットの約3倍に過ぎず、したがって完全ピボットよりも安価です。ルークピボットは、理論的にも実践的にも部分ピボットよりも安定していることが証明されています。

部分ピボット戦略のバリエーションとして、スケール ピボットがあります。このアプローチでは、アルゴリズムは、その行のエントリと比較して最大のエントリをピボット要素として選択します。この戦略は、エントリの大きさの大きな差が丸め誤差の伝播につながる場合に適しています。スケール ピボットは、行のエントリの大きさが大きく異なる次のようなシステムで使用してください。以下の例では、現在のピボット要素 30 は 5.291 より大きいですが、その行の他のエントリと比較すると比較的小さいため、2 つの行を交換することが望ましいでしょう。この場合、行を交換しないと、前の例のように丸め誤差が伝播します。

${\displaystyle \left[{\begin{array}{cc|c}30&591400&591700\\5.291&-6.130&46.78\\\end{array}}\right]}$

行列 A のピボット位置は、行列 A の簡約された行階段形式で行の先頭の 1 に対応する位置です。Aの簡約された行階段形式は一意であるため、ピボット位置は一意に決定され、簡約プロセスで行の交換が実行されるかどうかに依存しません。また、行のピボットは、行階段形式の上の行のピボットの右側に現れる必要があります。

この記事には、クリエイティブ・コモンズの表示/共有ライセンスに基づいてライセンスされているPivoting on PlanetMathの資料が組み込まれています。

• RL Burden、JD Faires、数値解析、第 8版、Thomson Brooks/Cole、2005 年。ISBN 0-534-39200-8 
• GH Golub、CF Loan、『行列計算』、第 3 版、Johns Hopkins、1996 年。ISBN 0-8018-5414-8。 
• 福田 孔明;テルラキ タマス(1997)。トーマス M. リーブリング、ドミニク デ ヴェラ (編)。「クリスクロス法: ピボット アルゴリズムの新たな視点」。数理計画、シリーズ B。1997年ローザンヌで開催された第 16 回国際数理計画シンポジウムの論文。79 (1–3): 369–395。CiteSeerX 10.1.1.36.9373。doi :  10.1007 /BF02614325。MR 1464775。S2CID  2794181。 ポストスクリプト プレプリント。
• Terlaky, Tamás; Zhang, Shu Zhong (1993). 「線形計画法のピボットルール: 最近の理論的発展に関する調査」Annals of Operations Research . 最適化問題における退化。46–47 (1): 203–233. CiteSeerX  10.1.1.36.7658 . doi :10.1007/BF02096264. ISSN  0254-5330. MR  1260019. S2CID  6058077.