Реализация исключения Гаусса-Иордана в Хаскеле - PullRequest
Новая
       1

Реализация исключения Гаусса-Иордана в Хаскеле

2 голосов
/ 11 декабря 2011

Мы хотим запрограммировать исключение Гаусса, чтобы вычислить базу (линейную алгебру) как упражнение для себя.Это не домашняя работа.

Сначала я подумал о [[Int]] как структуре нашей матрицы.Тогда я подумал, что мы можем отсортировать списки лексикографически.Но тогда мы должны рассчитать с матрицей.И здесь есть проблема.Может кто-нибудь дать нам несколько советов.

Ответы [ 2 ]

4 голосов
/ 11 декабря 2011

Рассмотрите возможность использования матриц из пакета hmatrix .Среди его модулей вы можете найти как быструю реализацию матрицы , так и множество алгоритмов линейной алгебры .Просмотр их источников может помочь вам с вашими сомнениями.

Вот простой пример добавления одной строки в другую путем разбиения матрицы на строки. 

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

Другой пример, на этот раз с использованием матрицыумножение. 

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)

Ср. Контейнер , Вектор , Продукт .

1 голос
/ 11 декабря 2011

Будет проще, если вы используете [[Rational]] вместо [[Int]], так как вы получите хорошее деление.

Возможно, вы захотите начать с реализации операций с элементарными строками. 

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

Для того, чтобы на самом деле выполнить гассовское исключение, вам нужен способ решить, какое число из одной строки добавить к другой, чтобы получить ноль. Итак, учитывая две строки .. 

5 4 3 2 1
7 6 5 4 3

Мы хотим добавить c раз строку 1 в строку 2, чтобы 7 стало нулем. Так 7 + c * 5 = 0 и c = -7/5. Таким образом, чтобы решить для c все, что нам нужно, это первые элементы каждой строки. Вот функция, которая находит c: 

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

Кроме того, как уже говорили другие, использование списков для представления вашей матрицы снизит производительность. Но если вы просто пытаетесь понять алгоритм, списки должны быть в порядке.

...