PHP算法解决一元线性方程组

Question

PHP算法解决一元线性方程组

phpalgorithmmathequation-solvinglinear-equation

4

我需要在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法则来解决这个问题。我可以制作一个系数的1个方阵，用Cramer法则（通过计算矩阵的行列式）解决系统，然后我应该检查未使用的方程中的值。我相信我可以自己尝试Cramer，但我正在寻找更好的解决方案。

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

我的问题是，是否有人知道在PHP中编写的类、脚本、代码或其他形式的API或Web服务，用于解决1级线性方程组？或者我可以尝试一个API或Web服务，最好是免费的，有偿的也可以。

谢谢。

- Daniel Ifrim

1

不要在这么大的矩阵上使用克莱姆法则！行列式计算会严重影响性能。此外，如果您的方程数大于变量数，您可能会对最小二乘逼近感兴趣，即找到所有方程的平方误差之和最小的x。这归结为找到一组不同的（希望不是超定的）方程的解，因此这里的答案也将对此有所帮助。 - MvG

4个回答

1

这个包使用高斯消元法。我发现它在处理更大的矩阵时执行速度较快（即更多的变量/方程）。

- Ivo Renkema

1

维基百科应该有伪代码来将代表您方程的矩阵简化为行阶梯形式。一旦矩阵处于该形式，您可以遍历行以找到解决方案。

有一个未维护的PEAR包，可能会节省您编写代码的工作。

另一个问题是，您是否主要关注“宽”系统（变量比方程多，通常有许多可能的解决方案）还是“窄”系统（方程比变量多，通常没有解决方案），因为最佳策略取决于您所处的情况 - 窄系统可能会受益于使用线性回归技术，例如最小二乘法。

- Victor Nicollet

0

这里有一个基于JAMA的真正优秀的软件包：http://www.phpmath.com/build02/JAMA/docs/index.php

我已经使用它进行简单的线性回归，一直到高度复杂的多元线性回归（在此基础上编写了自己的向后逐步MLR函数）。非常全面，希望能满足您的需求。

速度可能是一个问题，但它的效果很好，并且在BSMLR计算结果交叉参考时与SPSS相匹配。

- Robbie

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

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

- Uli · Accepted Answer

我正需要这个，但我找不到行列式函数，所以我自己写了一个。还有克莱姆法则函数。也许它会对别人有所帮助。

/**
 * $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;
}