C# Поиск определителя n*n матрицы рекурсией

[Lfybkf]

 public Matrixx GetMinor(Matrixx A, Matrixx B, int m, int i, int j)
        {
            int ki, kj, di, dj;
            di = 0;
            for (ki = 0; ki < m -1; ki++)
            {
                if (ki == i) { di = 1; }
                dj = 0;
                for (kj = 0; kj < m -1 ; kj++)
                {
                    if (kj == j) { dj = 1; }
                    B.Matr[ki, kj] = A.Matr[ki + di, kj + dj];
            
                }

            }
            return B;
        }
        public double MatrixxDet(Matrixx A, int n)
        {
            int i, k;
            double partdet, determinant;
            Matrixx B = new Matrixx(n, n);
            partdet = 0; k = 1; determinant = 0;
            if (n == 1) { partdet += A.Matr[0, 0]; }
            else
            {
                if (n == 2) { partdet += A.Matr[0, 0] * A.Matr[1, 1] - A.Matr[1, 0] * A.Matr[0, 1];  }
                else
                {
                    for (i = 0; i < (n); i++)
                    {
                        B = GetMinor(A, B, n, i, 0);
                      
                        partdet = partdet + k * A.Matr[0, i] * MatrixxDet(B, n - 1);
                        
                        k = -k;
                    }
                    determinant = partdet;
                }
            }
            return determinant;
        }

Не работает программа, не пойму в чем ошибка, помогите пожалуйста!

[Lfybkf]

Делал по этому коду с Delphi. Помогите его на C# перевести.

procedure GetMatr(a:matr; var b:matr; m,i,j:integer);
{ Вычеркивание из матрицы строки и столбца }
var ki,kj,di,dj:integer;
  begin
  di:=0;
  for ki:=1 to m-1 do
    begin
    if (ki=i) then di:=1;
    dj:=0;
    for kj:=1 to m-1 do
      begin
      if (kj=j) then dj:=1;
      b[ki,kj]:=a[ki+di,kj+dj];
      end;
    end;
  end;
Function Determinant(a:matr;n:integer):longint;
{ Вычисление определителя матрицы }
var i,j,d,k:longint;
    b:matr;
  begin
  d:=0; k:=1;
  if (n<1) then
    begin
    writeln('Determinant: Cann''t run. N=',n); halt;
    end;
  if (n=1)
    then d:=a[1,1]
  else if (n=2)
    then d:=a[1,1]*a[2,2]-a[2,1]*a[1,2]
  else { n>2 }
    for i:=1 to n do
      begin
      GetMatr(a,b,n,i,1);
      {writeln('i=',i,' a[',i,',1]=',a[i,1]);
      PrintMatr(b,n-1);}
      d:=d+k*a[i,1]*Determinant(b,n-1);
      k:=-k;
      end;
  Determinant:=d;
  end;

[MyLastHit]

{{delete}}

плохо соображаю к ночи, но если как по делфи коду, циклы записать так:

for (ki = 1; ki < m; ki++)
...
for (kj = 1; kj < m; kj++)

[Lfybkf]

Все равно, не работает(
Может быть, кто-нибудь еще поймет в чем ошибка моя? Уже 3й день не могу с этим разобраться(

[Партизанин]

Lfybkf, есть несколько ньюансов, которые Вы не учли...
Вот пожалуй более точный перевод, хотя за полную правильность не ручаюсь...

// n - размерность матрицы A, col - колонка, row - строка - ищем минор A[row][col]
        public void Minor(Matrix A, ref Matrix B, int n, int col, int row) 
        {
            int di, dj;
            for (int ki = 0; ki < n; ki++)
            {
                if (ki == row) di = 1;
                dj = 0;

                for (int kj = 0; kj < n; kj++)
                {
                    if (kj == col) dj = 1;
                    B[ki][kj] = A[ki + di][kj + dj];
                }
            }
        }

        public long Determinant(Matrix A, int n) // n - размерность матрицы A
        {
            int k = 1; // Коэффициент минора
            long d = 0; // Хранит выводимый результат - определитель
            Matrix B = new Matrix(); // 

            if (n < 1) return null;
            if (n == 1) return A[0][0];
            if (n == 2) return A[0][0] * A[1][1] -
                               A[0][1] * A[1][0];

            for (int i = 0; i < n; i++)
            {
                Minor(A, B, n, i, 0); // Ищем миноры только 1-ой строки
                d += k * A[i][0] * Determinant(B, n - 1);
                k *= -1;
            }

            return d;
        }
    }

[Партизанин]

Lfybkf, вобщем-то сам столкнулся с проблемой вычисления определителя матрицы... Сам дошёл до следующей реализации рекурсивного алгоритма:

В коде класс Matrix содержит список списков типа double:

    public class Matrix
    {
        private List<MatrixRow> mr; // Список строк матрицы
        // ... //
    }
    public class MatrixRow
    {
        private List<double> cells; // Список ячеек строки
        // ... //
    }

Код методов по нахождению минора и определителя следующий:

        // Нахождение минора введённой матрицы M[row][col] // без изменений знака!!!
        public Matrix Minor(Matrix M, int row, int col)
        {
            Matrix temp = new Matrix(); // Временная матрица
            M.CopyMatrix(ref temp); // Просто копирование во временную матрицу temp для сохранения исходной M

            temp.Mr.RemoveAt(row);

            for (int i = 0; i < temp.Mr.Count; i++)
                temp.Mr[i].Cells.RemoveAt(col);

            return temp; // Возвращаем полученный минор
        }

        // Нахождение определителя введённой матрицы
        public double Determinant(Matrix M)
        {
            // Проверки 
            if (M.Mr.Count == 0) return 0;
            if (M.Mr.Count != M.Mr[0].Cells.Count) return 0;

            if (M.Mr.Count == 1) return M.Mr[0].Cells[0];
            if (M.Mr.Count == 2) return M.Mr[0].Cells[0] * M.Mr[1].Cells[1] -
                                        M.Mr[0].Cells[1] * M.Mr[1].Cells[0];

            double det = 0;
            for (int j = 0; j < M.Mr[0].Cells.Count; j++)
                det += M.Mr[0].Cells[j] * Determinant(Minor(M, 0, j)) * Math.Pow(-1, j);

            return det;
        }

Единственно, что очень смущает: при большой размерности матрицы - этот алгоритм требует огромного количества шагов на выполнение. Мне же нужно посчитать матрицу как минимум 18х18 по курсовому. На 6х6 работает нормально - это точно, дальше - сейчас тестирую...

[Партизанин]

В итоге на матрице с размерами 11х11 получилось около 300 000 000 операций, чего ожидал около 3-х минут... При том, что это количество операций выросло где-то в 10 раз в сравнении с вычислением матрицы 10х10 - дальше и не тестировал...
(точнее тестировал 18х18, как мне и надо, но не дождался)

Пришёл к выводу, что данный алгоритм делает очень много повторных (а следовательно и ненужных) вычислений... Ведь при расчёте нового определителя - на каждом шаге перебираются всё те же миноры, что и на прошлых итерациях + чуть-чуть новых... А данный алгоритм всёравно будет их заново просчитывать...

Если необходимо вычислить определитель именно рекурсивным методом - то приведённый код выдаёт правильные результаты (сверял, правда, с он-лайновыми вычислителями), но при большой размерности матрицы советую использовать метод Гаусса.

Метод Гаусса вместо 300 000 000 операций на том же наборе данных выдал всего 2 600! Выгода очевидна!!!

Так выглядит реализация метода Гаусса:

public double DetGauss(Matrix M)
        {
            double det = 1; // Хранит определитель, который вернёт функция
            int n = M.Mr.Count; // Размерность матрицы
            int k = 0;
            const double E = 1E-9; // Погрешность вычислений

            for (int i = 0; i < n; i++)
            {
                k = i;
                for (int j = i + 1; j < n; j++)
                    if (Math.Abs(M.Mr[j].Cells[i]) > Math.Abs(M.Mr[k].Cells[i]))
                        k = j;

                if (Math.Abs(M.Mr[k].Cells[i]) < E)
                {
                    det = 0;
                    break;
                }
                Swap(ref M, i, k);

                if (i != k) det *= -1;

                det *= M.Mr[i].Cells[i];

                for (int j = i + 1; j < n; j++)
                    M.Mr[i].Cells[j] /= M.Mr[i].Cells[i];

                for (int j = 0; j < n; j++)
                    if ((j != i) && (Math.Abs(M.Mr[j].Cells[i]) > E))
                        for (k = i + 1; k < n; k++)
                            M.Mr[j].Cells[k] -= M.Mr[i].Cells[k] * M.Mr[j].Cells[i];
            }
            return det;
        }

Функция Swap() меняет строки указанной местами:

        // Функция меняет указанные строки указанной матрицы местами
        public void Swap(ref Matrix M, int row1, int row2)
        {
            double s = 0;

            for (int i = 0; i < M.Mr[row1].Cells.Count; i++)
            {
                s = M.Mr[row1].Cells[i];
                M.Mr[row1].Cells[i] = M.Mr[row2].Cells[i];
                M.Mr[row2].Cells[i] = s;
            }
        }

P.S.: Сообщение писал на скорую руку, так что комментировать особо некогда было...
P.S.S.: Класс Matrix описан сообщением ранее...