有关解线性代数方程组的方法的更多信息

当然，很难详细介绍所有方法，但是对我来说，这个话题似乎很有趣并且非常重要，因为每个人都面临着经常找到解决方案的任务。 在第一篇文章为什么是高斯？ 描述了高斯方法（包括修改）和一些迭代方法。 但是，鉴于对Sinn3r的批评，我决定也描述其他方法。

重新开始

因此，让我们再次需要求解线性代数方程组 $$$n$。 最引人注目的数值方法之一是使用 $$$卢$-分解矩阵。

这种直观的方法如下。 假设我们有一个线性代数方程组（以矢量形式编写）：

$$

$$Ax = b，$$

在哪里 $$$A =（a_ {ij}）$-可怕且令人困惑的非退化矩阵。 我们将其表示为另外两个矩阵的乘积： $$$L =（l_ {ij}）$是下三角矩阵，并且 $$$U =（u_ {ij}）$是上三角矩阵。 那么显然，系统采用以下形式：

$$

$$LUx = b$$

如果指定 $$$Ux = y$，则可以从其他两个系统的解决方案中找到原始系统的解决方案：

$$

$$Ly = b，$$

$$

这种方法的优点是两个辅助系统的解非常简单（由于矩阵 $$$L$和 $$ -三角形）。 但是找到这些矩阵容易吗？ 因此，将系统求解的任务简化为构建的任务 $$$卢$-矩阵分解。

算法应用说明 $$$卢$-分解在这里有足够详细的描述。 同时，我们将介绍另一种方法。

平方根法

我们在矩阵上附加条件 $$。 我们要求它是对称的，即 $$$a_ {ij} = a_ {ji}$或 $$$A ^ t = A$。 这样的矩阵可以表示为

$$

$$A = S ^ tDS，$$

在哪里 $$$S$-上三角矩阵， $$$D$是对角实矩阵，其对角元素的绝对值等于1。 同样，原始系统简化为另外两个：

$$

$$S ^ tDy = b，$$

$$

$$Sx = y，$$

由于矩阵的性质，它们也可以基本解决 $$$S$和 $$$D$。

算法公式的推导相当麻烦，并且超出了公开范围。 如果需要，可以在这里找到它们。

实现sweep方法的示例Java代码：

import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SquareRootMethod { public static void main(String[] args) throws FileNotFoundException { Scanner scanner = new Scanner(new FileReader("input.txt")); scanner.useLocale(Locale.US); int n = scanner.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] = scanner.nextDouble(); } b[i] = scanner.nextDouble(); } double[] x = new double[n + 1]; double[] d = new double[n + 1]; double[][] s = new double[n + 1][n + 1]; // for i = 1 d[1] = Math.signum(a[1][1]); s[1][1] = Math.sqrt(Math.abs(a[1][1])); for (int j = 2; j <= n; j++) { s[1][j] = a[1][j] / (s[1][1] * d[1]); } // for i > 1 //searching S and D matrix for (int i = 2; i <= n; i++) { double sum = 0; for (int k = 1; k <= i - 1; k++) { sum += s[k][i] * s[k][i] * d[k]; } d[i] = Math.signum(a[i][i] - sum); s[i][i] = Math.sqrt(Math.abs(a[i][i] - sum)); double l = 1 / (s[i][i] * d[i]); for (int j = i + 1; j <= n; j++) { double SDSsum = 0; for (int k = 1; k <= i - 1; k++) { SDSsum += s[k][i] * d[k] * s[k][j]; } s[i][j] = l * (a[i][j] - SDSsum); } } //solve of the system (s^t * d)y = b double[] y = new double[n + 1]; y[1] = b[1] / (s[1][1] * d[1]); for (int i = 2; i <= n; i++) { double sum = 0; for (int j = 1; j <= i - 1; j++) { sum += s[j][i] * d[j] * y[j]; } y[i] = (b[i] - sum) / (s[i][i] * d[i]); } //solve of the system sx = y x[n] = y[n] / s[n][n]; for (int i = n - 1; i >= 1; i--) { double sum = 0; for (int k = i + 1; k <= n; k++) { sum += s[i][k] * x[k]; } x[i] = (y[i] - sum) / s[i][i]; } //output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } } 

扫描方式

使用此方法，只能求解每行中不超过三个未知数的特定系统。 也就是说，有了系统

$$

$$斧= b$$

矩阵 $$是三对角的：

$$

$$A = \开始{pmatrix} C_1＆-B_1＆0＆\点＆0＆0 \\ -A_2＆C_2＆-B_2＆\点＆0＆0 \\ \ vdots＆\ vdots＆\ vdots＆\ ddots ＆\ vdots＆\ vdots \\ 0＆0＆\点＆-A_ {n-1}＆C_ {n-1}＆-B_ {n-1} \\ 0＆0＆\点＆0＆-A_n ＆C_n \\ \结束{pmatrix}。$$

请注意，附近的解决方案之间存在联系：

$$

$$x_ {i-1} = \ alpha_ {i-1} x_i + \ beta_ {i-1}，$$

$$$\ alpha_k，\ beta_k$-一些未知的数字。 如果找到它们和一个变量，则可以找到所有其他变量。

公式的推导

$$

$$\ alpha_1 = \ dfrac {B_1} {C_1}，\ \ alpha_i = \ dfrac {B_i} {C_i-A_i \ alpha_ {i-1}}，\ i = \ overline {2，n}，$$

$$

$$\ beta_1 = \ dfrac {b_1} {C_1}，\ \ beta_i = \ dfrac {b_i + A_i \ beta_ {i-1}} {C_i-A_i \ alpha_ {i-1}}，\ i = \上线{ 2，n}$$

在这里 。 好吧，最后

$$

$$x_n = \ dfrac {b_n + A_n \ beta_ {n-1}} {C_n-A_n \ alpha_ {n-1}}，\ x_i = \ alpha_i x_ {i + 1} + \ beta_i，\ i = n- 1，n-2，\点，1$$

请注意，在搜索公式中 $$$\ alpha_i，\ beta_i$有一个除数 $$$C_i-A_i \ alpha_ {i-1}，$可能是零，需要跟踪。 但实际上，以下语句成立，其证明在这里 ：如果满足条件，则扫描算法正确且稳定：

$$

$$C_1，C_n \ neq 0，A_i，B_i \ neq 0 \（i = \上线{2，n}），$$

$$

$$| C_i | \ geq | A_i | + | B_i |。$$

考虑解决系统问题的Java程序代码。

$$

$$\ left \ {\ begin {aligned}＆x_1 = 0，\\＆x_ {i-1} + \ xi x_ {i + 1} = \ dfrac {i} {n}，\（i = \ overline {2， n-1}），\\＆x_n = 1，\\ \结束{aligned} \ right$$

在 $$$\ xi = 2，n = 21$。

 package SystemOfLinearAlgebraicEquations; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class TridiagonalMatrixAlgorithm { public static void main(String[] args) throws FileNotFoundException { final int n = 21; double[] A = new double[n + 1]; double[] B = new double[n + 1]; double[] C = new double[n + 1]; double[] F = new double[n + 1]; double xi = 2; C[1] = 1; F[1] = 0; for(int i = 2; i <= n-1; i++) { A[i] = 1; C[i] = xi; B[i] = 1; F[i] = - (double) i / n; } A[n] = 0; C[n] = 1; F[n] = 1; double[] alpha = new double[n + 1]; double[] beta = new double[n + 1]; // right stroke alpha[1] = B[1] / C[1]; beta[1] = F[1] / C[1]; for (int i = 2; i <= n - 1; i++) { double denominator = C[i] - A[i] * alpha[i-1]; alpha[i] = B[i] / denominator; beta[i] = (F[i] + A[i] * beta[i - 1]) / denominator; } double[] x = new double[n + 1]; // back stroke x[n] = (F[n] + A[n] * beta[n - 1]) / (C[n] - A[n] * alpha[n - 1]); for (int i = n - 1; i >= 1; i--) { x[i] = alpha[i] * x[i + 1] + beta[i]; } // output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i = i + 5) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } }