ハスケルでGauss-Jordan消去を実装する

Question

ガウス消去をプログラムして、自分自身の運動として基底（線形代数）を計算したい。宿題ではありません。

私はまず[[Int]]を私たちのマトリックスの構造として考えました。リストを辞書的に並べ替えることができると私は思った。しかし、行列を計算する必要があります。そして、問題があります。誰かが私たちにいくつかのヒントを与えることができますか？

Answer 1

hmatrixパッケージの行列を使用することを検討してください。そのモジュールの中には、高速のimplementation of a matrixと多くのlinear algebra algorithmsがあります。彼らの情報源を閲覧することは、あなたの疑問を助けるかもしれません。

ここでは、行列を行に分割して行を追加する簡単な例を示します。

import Numeric.Container 
import Data.Packed.Matrix 

addRow :: Container Vector t => Int -> Int -> Matrix t -> Matrix t 
addRow from to m = let rows = toRows m in 
    fromRows $ take to rows ++ 
      [(rows !! from) `add` (rows !! to)] ++ 
      drop (to + 1) rows 

もう1つの例として、今回は行列乗算を使用します。

addRow :: (Product e, Container Vector e) => 
      Int -> Int -> Matrix e -> Matrix e 
addRow from to m = m `add` (e <> m) 
    where 
    nrows = rows m 
    e = buildMatrix nrows nrows 
     (\(r,c) -> if (r,c) /= (to,from) then 0 else 1) 

Cf. Container,Vector,Product。

Answer 2

の代わりに[[Rational]]を使用すると簡単になるでしょう。

おそらく、基本的な行操作を実装することから始めたいと思うでしょう。

swap :: Int -> Int -> [[Rational]] -> [[Rational] 
swap r1 r2 m = --a matrix with r1 and r2 swapped 

scale :: Int -> Rational -> [[Rational]] -> [[Rational]] 
scale r c m = --a matrix with row r multiplied by c 

addrow :: Int -> Int -> Rational -> [[Rational]] -> [[Rational]] 
addrow r1 r2 c m = --a matrix with (c * r1) added to r2 

実際には、ガウス消去を行うには、複数の行のうち何行を追加してゼロを得るかを決める方法が必要です。したがって、2行が与えられます。

5 4 3 2 1 
7 6 5 4 3 

7がゼロになるように、行2にc倍の行1を追加します。従って 7 + c * 5 = 0および c = -7/5。ですから、Cを解くためには、各行の最初の要素が必要です。ここでは、Cを見つける機能があります：

whatc :: Rational -> Rational -> Rational 
whatc _ 0 = 0 
whatc a b = - a/b 

また、他の人があなたの行列はあなたに悪化した性能が得られます表すためにリストを使用して、言ってきたように。しかし、アルゴリズムを理解しようとしているだけなら、リストはうまくいくはずです。