Детерминант матрицы на C#

28.12.2018 at 22:40

Детерминант (или определитель) матрицы можно вычислить огромным количеством способов. Мы воспользуемся следующей формулой:

где — определитель матрицы, полученной из исходной вырезанием 1 строки и j столбца.

Для начала научимся вырезать из матрицы столбец:

private Matrix CreateMatrixWithoutColumn(int column)
{
    if (column < 0 || column >= this.N)
    {
        throw new ArgumentException("invalid column index");
    }
    var result = new Matrix(this.M, this.N - 1);
    result.ProcessFunctionOverData((i, j) => 
        result[i, j] = j < column ? this[i, j] : this[i, j + 1]);
    return result;
}

Здесь все просто: сдвигаем все элементы на 1 влево, если они находятся справа от вырезаемого столбца.

Аналогично вырезаем строку

private Matrix CreateMatrixWithoutRow(int row)
{
    if (row < 0 || row >= this.M)
    {
        throw new ArgumentException("invalid row index");
    }
    var result = new Matrix(this.M - 1, this.N);
    result.ProcessFunctionOverData((i, j) => 
        result[i, j] = i < row ? this[i, j] : this[i + 1, j]);
    return result;
}

Добавим в класс матрицы свойство — квадратная она или нет

public bool IsSquare { get => this.M == this.N; }

Теперь можно считать детерминант матрицы

public double CalculateDeterminant()
{
    if (!this.IsSquare)
    {
        throw new InvalidOperationException(
            "determinant can be calculated only for square matrix");
    }
    if (this.N == 2)
    {
        return this[0, 0] * this[1, 1] - this[0, 1] * this[1, 0];
    }
    double result = 0;
    for (var j = 0; j < this.N; j++)
    {
        result += (j % 2 == 1 ? 1 : -1) * this[1, j] * 
            this.CreateMatrixWithoutColumn(j).
            CreateMatrixWithoutRow(1).CalculateDeterminant();
    }
    return result;
}

Разберем по частям. Первая — проверка на квадратность. Она нужна потому, что посчитать определитель можно только у квадратно матрицы.

Следующая часть — определитель матрицы размера 2. Этот кусок кода нужен для выхода из рекурсии (а наша функция рекурсивна).

if (this.N == 2)
{
    return this[0, 0] * this[1, 1] - this[0, 1] * this[1, 0];
}

и потом идет уже сама формула детерминанта. Непонятным может быть кусок

j % 2 == 1 ? 1 : -1

это просто способ посчитать -1 в степени j + 1.

Кеширование результата

Вычисление определителя — достаточно тяжелая операция. Логично будет добавить кеширование результата. Добавим приватное поле

private double precalculatedDeterminant = double.NaN;

в начале вычисления детерминанта вернем закешированное значение, если оно есть

if (!double.IsNaN(this.precalculatedDeterminant))
{
    return this.precalculatedDeterminant;
}

если его нет — его нужно сохранить после вычисления. Самое важное при работе с кешированием — инвалидация кеша. В нашем случае сбрасывать кеш нужно тогда, когда изменится значение какого-либо элемента матрицы. Для этого доработаем свойство-индексатор

public double this[int x, int y]
{
    get
    {
        return this.data[x, y];
    }
    set
    {
        this.data[x, y] = value;
        this.precalculatedDeterminant = double.NaN;
    }
}

Рабочий код как всегда лежит на гитхабе

Tags: