Исключение по Гауссу с пользовательскими операторами

Question

Каков хороший способ реализации исключения Гаусса, когда операторы являются пользовательскими, а не стандартными арифметическими?

Вот операторы:

Дополнительно:

0 + 0 = 0
0 + 1 = 1
1 + 1 = 0

Вычитание

0 - 0 = 0
0 - 1 = 1
1 - 1 = 0

Умножение:

0 * 0 = 0
0 * 1 = 0
1 * 1 = 1

Отдел:

0 / 0 = illegal
0 / 1 = 0
1 / 1 = 1

Вот примерный набор уравнений в виде расширенной матрицы с RHS в крайнем правом столбце:

1, 1, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 1, 1, 0, 0, 1, 0, 0, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 1
0, 1, 0, 1, 1, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 0, 1
0, 0, 0, 1, 0, 0, 1, 0, 0, 1
0, 0, 0, 1, 1, 0, 1, 1, 0, 1
0, 0, 0, 0, 0, 1, 0, 0, 1, 1

Решение для этого набора:

x1 = 1
x2 = 0
x3 = 0
x4 = 0
x5 = 1
x6 = 1
x7 = 1
x8 = 1
x9 = 0

Устранение Гаусса не удалось для меня, так как я попробовал его на этом наборе.

Уравнения будут иметь 9, 16, 25 или 36 членов. Было бы здорово, если бы алгоритм легко расширялся до больших квадратов, до 100. Я ищу алгоритм, желательно в псевдокоде или JavaScript.

Answer 1

Алгоритм исключения Гаусса в псевдокоде можно найти здесь .

Не имеет значения, используете ли вы «нормальные» числа или находитесь в кольце Z ₂ , алгоритм остается тем же.

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

К сожалению, поскольку вы упомянули JavaScript, вы не можете переопределить операторы на этом языке, так что это станет немного сложнее. Полагаю, вы могли бы определить функции, которые будут выполнять работу операторов, и использовать их вместо стандартных операторов.

function add(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return (v1 + v2) % 2;
}

function subtract(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return Math.abs((v1 - v2) % 2);
}

function multiply(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    }

    return v1 * v2;
}

function divide(v1, v2) {
    if ((v1 != 0 && v1 != 1) || (v2 != 0 && v2 != 1)) {
        alert('Invalid params');
        return;
    } else if (v2 == 0) {
        alert('Divider cannot be zero');
        return;
    }

    return v1 / v2;
}

Answer 2

То, что вы описываете, на самом деле не пользовательские операторы. Скорее, это Z ₂ со стандартным сложением и умножением по модулю 2.

Это поле ; так что у вас нет проблем с «дробью».

Алгоритм исключения Гаусса не ограничен полем действительных чисел; это работает также на Z ₂ .