Mais sobre métodos para resolver sistemas de equações algébricas lineares

É claro que é muito difícil contar em detalhes sobre todos os métodos, mas para mim esse tópico parece interessante e extremamente importante, pois todos enfrentam a tarefa de encontrar uma solução com bastante frequência. No primeiro artigo Por que Gauss? o método de Gauss foi descrito (inclusive com modificações) e alguns métodos iterativos. No entanto, dadas as críticas ao Sinn3r , decidi descrever outros métodos também.

Começar de novo

Então, precisamos novamente resolver um sistema de equações algébricas lineares de ordem $$$n$ . Um dos métodos numéricos mais impressionantes é um método que usa $$$Lu$ -deposição da matriz.

Este método intuitivo é o seguinte. Suponha que tenhamos um sistema de equações algébricas lineares (escritas em forma vetorial):

$$

$$Ax = b,$$

onde $$$A = (a_ {ij})$ - uma matriz não degenerada terrível e confusa. Nós o representamos como o produto de duas outras matrizes: $$$L = (l_ {ij})$ É uma matriz triangular inferior e $$$U = (u_ {ij})$ É a matriz triangular superior. Então, obviamente, o sistema assume a forma:

$$

$$LUx = b.$$

Se designado $$$Ux = y$ , a solução para o sistema original é encontrada na solução de dois outros sistemas:

$$

$$Ly = b,$$

$$

$$Ux = y.$$

A vantagem deste método é que as soluções de dois sistemas auxiliares são muito simples (devido ao fato de as matrizes $$$L$ e $$$U$ - triangular). Mas é fácil encontrar essas matrizes? Portanto, a tarefa de resolver o sistema é reduzida à tarefa de criar $$$Lu$ -deposições para a matriz.

Descrição do algoritmo aplicando $$$Lu$ A decomposição é descrita em detalhes suficientes aqui . Enquanto isso, veremos outro método.

Método da raiz quadrada

Nós impomos condições adicionais à matriz $$$A$ . Exigimos que seja simétrico, ou seja, $$$a_ {ij} = a_ {ji}$ ou $$$A ^ t = A$ . Essa matriz pode ser representada como

$$

$$A = S ^ tDS,$$

onde $$$S$ - matriz triangular superior, $$$D$ É uma matriz real diagonal e seus elementos diagonais são iguais à unidade em valor absoluto. Da mesma forma, o sistema original é reduzido para dois outros:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

que também são resolvidos elementarmente devido às propriedades das matrizes $$$S$ e $$$D$ .

A derivação de fórmulas algorítmicas é bastante complicada e permanece além do escopo da publicação. Se desejar, eles podem ser encontrados aqui .

Exemplo de código Java que implementa o método de varredura:

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(); } } 

Método de varredura

Usando esse método, apenas sistemas específicos com não mais que três incógnitas em cada linha podem ser resolvidos. Ou seja, com o sistema

$$

$$Ax = b$$

matriz $$$A$ é tridiagonal:

$$

$$A = \ begin {pmatrix} C_1 & -B_1 & 0 & \ dots & 0 & 0 \\ -A_2 & C_2 & -B_2 & \ dots & 0 & 0 \ 0 \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots \\ 0 & 0 & \ dots & -A_ {n-1} & C_ {n-1} e -B_ {n-1} \\ 0 & 0 & \ dots & 0 & -A_n & C_n \\ \ end {pmatrix}.$$

Observe que há uma conexão de soluções vizinhas:

$$

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

$$$\ alpha_k, \ beta_k$ - alguns números desconhecidos. Se os encontrarmos e uma única variável, podemos encontrar todas as outras.

Derivação de fórmulas

$$

$$\ 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 = \ overline { 2, n}$$

presente aqui . Bem, no final

$$

$$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, \ pontos, 1$$

Observe que nas fórmulas de pesquisa $$$\ alpha_i, \ beta_i$ existe uma divisão por número $$$C_i - A_i \ alpha_ {i-1},$ que pode vir a ser zero e precisa ser rastreado. Mas, de fato, a seguinte declaração é válida, cuja prova está aqui : o algoritmo de varredura está correto e estável se as condições forem atendidas:

$$

$$C_1, C_n \ neq 0, A_i, B_i \ neq 0 \ (i = \ overline {2, n}),$$

$$

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

Considere o código do programa Java que resolve o sistema.

$$

$$\ left \ {\ begin {alinhado} & x_1 = 0, \\ & x_ {i-1} + \ xi x_ {i + 1} = \ dfrac {i} {n}, \ (i = \ overline {2, n-1}), \\ & x_n = 1, \\ \ end {alinhado} \ right.$$

às $$$\ 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(); } }