如果要求您解决具有三个未知数的简单系统，您将怎么办？ 每个人都为自己形成了自己最便捷的方法。 有很多方法可以求解线性代数方程组。 但是，为什么偏重于高斯方法呢？
第一件事
让我们从一个简单的开始。 给出一个三阶线性方程组：
$$显示$$ \左\ {\开始{对齐} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1，\\ a_ {21} x_1 + a_ {22} x_2 + a_ { 23} x_3 = b_2，\\ a_ {31} x_1 + a_ {32} x_2 + a_ {33} x_3 = b_3。 \\ \结束{aligned} \ right。$$显示$$
高斯方法在于依次“破坏”主对角线以下的术语。 第一步，将第一个方程式乘以
$ inline $ \ dfrac {a_ {21}} {a_ {11}} $ inline $ 并从第二个减去（类似地乘以
$ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ 并从第三个中减去）。 也就是说，经过这种转换，我们得到以下信息：
$$显示$$ \左\ {\开始{对齐} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1，\\ a_ {22}'x_2 + a_ {23}'x_3 = b_2'，\\ a_ {32}'x_2 + a_ {33}'x_3 = b_3'。 \\ \结束{aligned} \ right。$$显示$$
现在第二个方程乘以
$ inline $ \ dfrac {a_ {32}'} {a_ {22}'} $ inline $ 并从第三个减去：
$$显示$$ \左\ {\开始{对齐} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1，\\ a_ {22}'x_2 + a_ {23}'x_3 = b_2'，\\ a_ {33}''x_3 = b_3''。 \\ \结束{aligned} \ right。$$显示$$
我们有一个相当简单的系统，很容易找到它
$内联$ x_3 $内联$ 然后
$内联$ x_2 $内联$ 和
$内联$ x_1 $内联$ 。
细心的读者一定会注意到：如果对角线元素等于零会怎样？ 例如，如果该怎么办
$ inline $ a_ {11} = 0 $ inline $ ？ 著名的高斯方法到此结束吗？
不用担心！ 找吧
$ inline $ \ max | a_ {1j} | $ inline $ 和交换
$内联$ j $内联$ 第一行（不失一般性，假设
$ inline $ \ max | a_ {1j} | = a_ {13} $内联$ ） 注意当一切
$ inline $ a_ {1j} = 0 $ inline $ 不可能，因为在这种情况下系数矩阵的行列式消失了，无法求解该系统。 因此，在第一行上重新排列了第三个方程后，我们执行前面描述的步骤。
可以在每次迭代中（即，在
$内联$ k $内联$ 迭代寻找
$ inline $ \ max | a_ {kj} | $ inline $ 然后改变
$内联$ j $内联$ 和
$内联$ k $内联$ th线。 通过选择列中的主要元素，搜索列中最大元素的算法称为高斯方法。
还有另一种方式。 可以上
$内联$ k $内联$ 迭代寻找
$ inline $ \ max | a_ {ik} | $ inline $ ，然后更改行而不是列。 但重要的是要记住一些数组中更改列的索引
$内联$ \ alpha $内联$ （然后恢复变量的确切顺序）。
实现此算法的简单代码示例：
import java.io.FileReader; import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.Locale; import java.util.Scanner; public class GuassianEliminationSearchMainElementsAtString { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1];
为什么是高斯？
还有另一种解决SLAE的方法。 其中之一是Cramer方法。 它包括对一定数量行列式的初步计算，借助这些行列式可以立即计算变量的值。 在原始系统下，此方法将如下所示：
$$显示$$ \ Delta = \开始{vmatrix} a_ {11}＆a_ {12}＆a_ {13} \\ a_ {21}＆a_ {22}＆a_ {23} \\ a_ {31}＆ a_ {32}和a_ {33} \\ \结束{vmatrix}，\ Delta_1 = \开始{vmatrix} b_1＆a_ {12}＆a_ {13} \\ b_2＆a_ {22}＆a_ {23} \ \ b_3＆a_ {32}＆a_ {33} \\ \结束{vmatrix}，$$显示$$
$$显示$$ \ Delta_2 = \开始{vmatrix} a_ {11}＆b_1＆a_ {13} \\ a_ {21}＆b_2＆a_ {23} \\ a_ {31}＆b_3＆a_ {33} \\ \结束{vmatrix}，\ Delta_3 = \开始{vmatrix} a_ {11}和a_ {12}和b_1 \\ a_ {21}和a_ {22}和b_2 \\ a_ {31}和a_ {32 }＆b_3 \\ \结尾{vmatrix}，$$显示$$
$$显示$$ x_i = \ dfrac {\ Delta_i} {\ Delta}。
但是请记住-什么是预选赛？
根据定义，矩阵的行列式
$内联$ A =（a_ {ij}）$内联$ 有一个数量
$$ display $$ \ sum \ limit_ {1 \ leq i_1 <\点<i_n \ leq n}（-1）^ {N（i_1，\点，i_n）} a_ {1i_1} \点a_ {ni_n}， $$显示$$
在哪里
$内联$ N（i_1，\点，i_n）$内联$ -通配符
$ inline $ i_1，\点，i_n。
行列式包含
$ inline $ n！$ inline $ 条款。 要解决这个系统，你需要算
$内联$ n + 1 $内联$ 行列式。 足够大
$内联$ n $内联$ 它非常昂贵。 例如，当
$内联$ n = 12 $内联$ 操作次数变为
$ inline $ 12！（12 +1）= 6227020800，$ inline $ 高斯渐近法
$内联$ n ^ 3 $内联$ 只需要
$内联$ 12 ^ 3 = 1728 $内联$ 操作。
迭代方法
所谓的迭代方法也适合作为求解SLAE的算法。 它们包括顺序计算近似值，直到其中之一尽可能接近精确答案为止。
首先，选择任意向量
$内联$ x ^ 0 $内联$ 是零近似值。 向量建立在其上。
$内联$ x ^ 1 $内联$ -这是第一个近似值。 依此类推。 计算在以下时间结束
$ inline $ || x ^ k-x ^ {k + 1} || <\ varepsilon $内联$ 在哪里
$内联$ \ varepsilon $内联$ -预先设置一些值。 最后一个不等式意味着我们每次迭代对解决方案的“改进”几乎都是微不足道的。
考虑流行的Jacobi方法，这是求解SLAE的最简单的迭代方法之一。
首先，我们以以下形式编写系统：
$$显示$$ \ sum \ limits_ {j \ leq n} a_ {ij} x_j = b_i，\ i = \上线{1，n}。 $$显示$$
分开
$内联$ i $内联$ -th词，并通过其他所有方式表达：
$$ display $$ x_i = \ dfrac {b_i-\ sum \ limits_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}，\ i = \ overline {1，n}。$$ display $ $
现在，只需将“计数器”挂在变量上，即可获得Jacobi迭代方法：
$$ display $$ x_i ^ k = \ dfrac {b_i-\ sum \ limits_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}}，\ i = \ overline {1，n}， \ k = 0,1，\点$$显示$$
请注意，使用此方法的先决条件是沿主对角线不存在零。
Java中的Jacobi方法实现：
作为一个 $内联$ \ varepsilon $内联$ 预先计算出所谓的机器ε。 import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class JacobiMethod { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; double[] x0 = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); x0[i] = b[i] / a[i][i]; } double EPS = EPSCalc(); double[] x = new double[n+1]; double norm = Double.MAX_VALUE; int counter = 0; do{ for(int i = 1; i <= n; i++) { double sum = 0; for(int j = 1; j <= n; j++) { if(j == i) continue; sum += a[i][j] * x0[j]; } x[i] = (b[i] - sum) / a[i][i]; } norm = normCalc(x0, x, n); for(int i = 1; i <= n; i++) { x0[i] = x[i]; } counter++; } while(norm > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x0[i]); } pw.flush(); pw.close(); } static double normCalc(double []x1, double[] x2, int n) { double sum = 0; for(int i = 1; i <= n; i++) { sum += Math.abs(x1[i] - x2[i]); } return sum; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } }
Jacobi方法的一种改进是松弛方法。 它的主要区别在于，借助预选参数，可以大大减少迭代次数。 让我们简要描述该方法的主要思想。
从原来的系统，我们再次表达
$内联$ x $内联$ ，但让我们对计数器进行一些不同的设置并添加参数
$内联$ \ omega $内联$ ：
$$ display $$ x_i ^ k = \ dfrac {\ omega \ left（b_i-\ sum \ limits_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k + 1}-\ sum \ limits_ {j = i + 1} ^ n a_ {ij} x_j ^ k \ right）} {a_ {ii}} +（1- \ omega）x_i ^ k，\ i = \上线{1，n}，\ k = 0,1，\点$$显示$$
在
$ inline $ \ omega = 1 $ inline $ 一切都变成了Jacobi方法。
因此，我们将寻找一些“好的”
$内联$ \ omega $内联$ 。 设置一些数字
$内联$ s $内联$ 我们将取值
$ inline $ \ omega \ in（0,2）$内联$ ，我们将针对每一种规范
$ inline $ || x ^ {k + 1} -x ^ k ||，\ k = \上线{1，s} $ inline $ 。 对于这些规范中的最小规范，请记住此值
$内联$ \ omega $内联$ ，并以此解决我们的系统。
Java方法说明：
在这里 $内联$ s = 5 $内联$ import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SuccessiveOverRelaxation { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); } double EPS = EPSCalc(); double w = bestRelaxationParameterCalc(a, b, n); double[] x = new double[n + 1]; int counter = 0; double maxChange = Double.MAX_VALUE; do { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm ; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } counter++; } while(maxChange > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(w + " is the best relaxation parameter"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } static double bestRelaxationParameterCalc(double[][]a, double[]b, int n) { double bestW = 1, bestMaxChange = Double.MAX_VALUE; for (double w = 0.05; w <= 2; w += 0.05) { double[] x = new double[n + 1]; double maxChange = 0; for (int s = 0; s < 5; s++) { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } } if (maxChange < bestMaxChange) { bestMaxChange = maxChange; bestW = w; } } return bestW; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } }
而不是结论
还有更多算法可以解决SLAE。 例如，平方根法，其中所需的系统由两个“简单”的系统代替，其“解”由基本公式计算； 扫描法，用于特定的三对角矩阵。 每个人都选择用于其问题的方法。