c++ - Fraction クラスのオーバーフロー (C++)

Question

基本操作用に通常の分数クラスを作成しました。唯一の問題は、膨大な数の操作があるため (私はガウス消去法を行っています)、分子または分母のいずれかにオーバーフローがあることです。

100 個の方程式があるので、100 x 100 の行列です。そして、最終結果は 10^-6 の精度である必要があります。私は何をすべきか？

Answer 1

@Chris Aが彼のコメントですでに示唆しているように、分母と分子には任意精度の整数を使用します。使用できる実装例はGNU MP Bignumです。

そして、できるだけ早く分数を単純化 (「キャンセル」) してください。これにより、分母と分子が小さく保たれます。したがって、最大公約数が重要になる場合があります。

Answer 2

〜670000の算術演算を必要とするアルゴリズムに正確な有理算術を使用すると、失敗する運命にあります。どうして他のことを考えたことがありますか？に正確な結果が必要な場合は10^-6、（ああ、わかりません）の精度で作業し、10^-20ピボットを使用します。

Answer 3

100x100 行列の条件が悪いため、おそらくオーバーフロー/アンデフローが発生しています。部分的なピボットを使用していない場合は、使用する必要があります。

より良い代替手段は、ガウス消去法以外のものを使用することです。部分的なピボットを使用しても、ガウス消去法は依然として悪条件の行列に関連する問題の影響を受けます。1 つの代替方法は、特異値分解による疑似逆行列の構築を使用することです。SVD を使用して行列 A を UVW* 形式に分解します。A の疑似逆行列は UV^{-1}W* で、V^{-1} は対角行列 V の疑似逆行列です。これは簡単に計算できます。一見逆説的に見える 1/(小さい数) = 0.

Answer 4

完全な NxN 行列 A のLU 分解(ピボットなしのガウス消去法の行削減フェーズに相当) には ~2N³/3 の乗算と除算が必要であることはよく知られています。部分的なピボットでも、この操作数は保持されます。

浮動小数点演算では、すべてのステップで丸め誤差が発生する可能性があります。最悪の場合、丸め誤差が指数関数的に蓄積される可能性があるため、除去ステップの「前方」誤差分析は精度の有効な推定値を生成しません。しかし、J・H・ウィルキンソンは「後方エラー分析」を示しました現実的な推定値を与えることができます。たとえば、A 正定行列または対角優勢行列の場合、完全ピボットを使用したガウス消去法によって計算された解は、解かれるシステムの「適度な」摂動の正確な解です (通常は、部分的なピボット)。残差のサイズは、摂動のサイズと行列の条件数から推定できます。通常、行列の条件数は、A のノルムと A の逆行列のノルムの比として定義されます。A が特異値の場合、これは無限大になり、A が特異値に近い場合、任意に大きくなります。条件数が、摂動サイズ (通常は浮動小数点演算のマシン イプシロン) を許容範囲を超える残差エラーに増幅するのに十分な大きさである場合、行列は悪条件であると言います。それ以外の場合、A は条件が整っていると言います。

もちろん、代わりに整数または有理数の正確な演算を使用して、浮動小数点演算の丸め誤差を回避することも考えられます。

しかし、正確な整数保存演算は一般にエントリの急速な成長につながり、行列が上記の意味で適切に調整されていても、オーバーフローが発生します。 エントリの増加を最小限に抑えるためのさまざまな戦略が提案されており、ヨルダンにまでさかのぼります (彼の名前は、線形システムの解の代わりに逆行列を計算するバージョンの消去法でガウスに関連付けられることがよくあります)。W. Kahan は特に簡潔に説明しています。任意精度の整数 (または有理数) の実装は、この問題に対処します。

しかし、そのような正確な方法が密な行列での浮動小数点演算と競合できるかどうかは疑わしいようです。ガウスの消去法などの直接法で目的の精度が得られない場合は、残差を計算して確認し (行列 A に計算された解を掛けて、右辺のベクトルから減算します)、次の式で補正項を再度解きます。行列 A が同じであるが、右側が残差に対応する線形システム。ガウス消去法の縮小フェーズが実際に LU 因数分解として実行された場合、反復補正を解くために必要なのはバックソルブ フェーズだけです。

使用可能な浮動小数点の精度から最高の精度を引き出す必要がある場合は、直交行列に基づく直接法が役立ちます (ハウスホルダー変換とギブンズ変換を参照)。

肝心なのは、線形システムのソリューションはしばしば再発明される車輪であり、ソフトウェアの再利用のより強力なケースはほとんど想像できないということです。このプレゼンテーションの 3 番目のスライドを参照してください。「数値線形代数ソフトウェアの書き方 -- やめてください! 可能な限り、数値線形代数計算を実行するために、既存の成熟したソフトウェア ライブラリに頼ってください。」