使用自定义运算符的高斯消元

Question

使用自定义运算符的高斯消元

3

当运算符是自定义运算符而不是标准算术运算符时，实现高斯消元的好方法是什么？

以下是运算符：

加法：

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

这是一个带增广矩阵的样例方程组，其中右侧是解向量：

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。

- Killroy

请注意，由于新的运算符，一些方程组变得无法求解，因为它们的结果将是分数。我特别关注可解性问题。 - Killroy

2个回答

3

你所描述的并不是真正的自定义运算符，而是使用标准加法和乘法模2的Z₂。

这是一个域，因此你不会遇到任何“分数”问题。

高斯消元算法并不局限于实数域，它同样适用于Z₂。

- balpha

我在大学10年前挂了微积分;) 我真的很需要一个算法！ - Killroy

6

这是代数，不是微积分 :) - balpha

我在看奇幻小说，没注意听讲，好嘛？是的，我有时也不在正确的房间里... - Killroy

1

该算法是已知的 - 它是高斯消元法。没有其他东西可提供。在任何线性代数文本中都可以找到它 - 它会在第一章或第二章中出现。 - duffymo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RaYell · Accepted Answer

高斯消元算法的伪代码可以在这里找到。

无论您使用的是“普通”数字还是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;
}