PHP算法求解1级线性方程组

Question

我有一个 1 级方程组要用 PHP 求解。方程比变量多，但方程不比变量少。

系统如下所示。 n 个方程，m 个变量，变量是 x[i]，其中“i”取值从 1 到 m。系统可能有解决方案，也可能没有。m 最大为 100，n 最大为 ~5000(千)。

我将不得不解决几千个这样的方程组。速度可能是个问题，但我目前正在寻找用 PHP 编写的算法。

a[1][1] * x[1] + a[1][2] * x[2] + ... + a[1][m] * x[m] = number 1
a[2][1] * x[1] + a[2][2] * x[2] + ... + a[2][m] * x[m] = number 2
...
a[n][1] * x[1] + a[n][2] * x[2] + ... + a[n][m] * x[m] = number n

有 Cramer Rule 可以做到这一点。我可以制作 1 个系数方阵，用 Cramer 规则求解系统(通过计算矩阵的行列式)，然后我应该检查未使用的方程中的值。我相信我可以自己尝试 Cramer，但我正在寻找更好的解决方案。

这是计算科学的问题， http://en.wikipedia.org/wiki/Computational_science#Numerical_simulations我知道有一些复杂的算法可以解决我的问题，但我不知道哪个可以解决，哪个最适合我的情况。一种算法会比仅理论和演示更好地利用我。

我的问题是，有人知道用 PHP 编写的某种类、脚本或代码来求解 1 年级线性方程组吗？或者我可以尝试 API 或 Web 服务，最好是免费的，付费的也可以。

谢谢

Answer 1

我正好需要这个，但是找不到行列式函数，所以我自己做了一个。 Cramer 规则也起作用。也许它会对某人有所帮助。

/**
 * $matrix must be 2-dimensional n x n array in following format
 * $matrix = array(array(1,2,3),array(1,2,3),array(1,2,3))
 */
function determinant($matrix = array()) {
    // dimension control - n x n
    foreach ($matrix as $row) {
        if (sizeof($matrix) != sizeof($row)) {
            return false;
        }
    }
    // count 1x1 and 2x2 manually - rest by recursive function
    $dimension = sizeof($matrix);
    if ($dimension == 1) {
        return $matrix[0][0];
    }
    if ($dimension == 2) {
        return ($matrix[0][0] * $matrix[1][1] - $matrix[0][1] * $matrix[1][0]);
    }
    // cycles for submatrixes calculations
    $sum = 0;
    for ($i = 0; $i < $dimension; $i++) {
        // for each "$i", you will create a smaller matrix based on the original matrix
        // by removing the first row and the "i"th column.
        $smallMatrix = array();
        for ($j = 0; $j < $dimension - 1; $j++) {
            $smallMatrix[$j] = array();
            for ($k = 0; $k < $dimension; $k++) {
                if ($k < $i) $smallMatrix[$j][$k] = $matrix[$j + 1][$k];
                if ($k > $i) $smallMatrix[$j][$k - 1] = $matrix[$j + 1][$k];
            }
        }
        // after creating the smaller matrix, multiply the "i"th element in the first
        // row by the determinant of the smaller matrix.
        // odd position is plus, even is minus - the index from 0 so it's oppositely
        if ($i % 2 == 0){
            $sum += $matrix[0][$i] * determinant($smallMatrix);
        } else {
            $sum -= $matrix[0][$i] * determinant($smallMatrix);
        }
    }
    return $sum;
}
/**
 * left side of equations - parameters:
 * $leftMatrix must be 2-dimensional n x n array in following format
 * $leftMatrix = array(array(1,2,3),array(1,2,3),array(1,2,3))
 * right side of equations - results:
 * $rightMatrix must be in format
 * $rightMatrix = array(1,2,3);
 */
function equationSystem($leftMatrix = array(), $rightMatrix = array()) {
    // matrixes and dimension check
    if (!is_array($leftMatrix) || !is_array($rightMatrix)) {
        return false;
    }
    if (sizeof($leftMatrix) != sizeof($rightMatrix)) {
        return false;
    }
    $M = determinant($leftMatrix);
    if (!$M) {
        return false;
    }
    $x = array();
    foreach ($rightMatrix as $rk => $rv) {
        $xMatrix = $leftMatrix;
        foreach ($rightMatrix as $rMk => $rMv) {
            $xMatrix[$rMk][$rk] = $rMv;
        }
        $x[$rk] = determinant($xMatrix) / $M;
    }
    return $x;
}