O que você fará se for solicitado a resolver um sistema simples com três incógnitas? Cada um formou uma abordagem própria e mais conveniente para ele pessoalmente. Existem muitas maneiras de resolver um sistema de equações algébricas lineares. Mas por que a preferência é dada especificamente ao método de Gauss?
Primeiras coisas primeiro
Vamos começar com um simples. Seja dado um sistema de equações lineares de terceira ordem:
exibição $$ $$ \ esquerda \ {\ begin {alinhada} 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. \\ \ end {alinhado} \ right. $$ display $$
O método Gauss consiste em "destruir" sequencialmente os termos abaixo da diagonal principal. Na primeira etapa, a primeira equação é multiplicada por
$ inline $ \ dfrac {a_ {21}} {a_ {11}} $ inline $ e subtraído do segundo (e igualmente multiplicado por
$ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ e subtraído do terceiro). Ou seja, após essa conversão, obtemos o seguinte:
exibição $$ $$ \ esquerda \ {\ begin {alinhada} 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'. \\ \ end {alinhado} \ right. $$ display $$
Agora a segunda equação é multiplicada por
$ inline $ \ dfrac {a_ {32} '} {a_ {22}'} $ inline $ e subtraído do terceiro:
exibição $$ $$ \ esquerda \ {\ begin {alinhada} 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' '. \\ \ end {alinhado} \ right. $$ display $$
Temos um sistema bastante simples, do qual é fácil encontrar
$ inline $ x_3 $ inline $ então
$ inline $ x_2 $ inline $ e
$ inline $ x_1 $ inline $ .
Um leitor atento notará definitivamente: e se os elementos diagonais forem iguais a zero? O que fazer se, por exemplo,
$ inline $ a_ {11} = 0 $ inline $ ? O famoso método Gauss termina aí?
Nada para se preocupar! Vamos encontrar
$ inline $ \ max | a_ {1j} | $ inline $ e trocar
$ inline $ j $ inline $ primeira e primeira linha (sem perda de generalidade, suponha que
$ inline $ \ max | a_ {1j} | = a_ {13} $ inline $ ) Observe que o caso em que tudo
$ inline $ a_ {1j} = 0 $ inline $ não pode ser, pois nesse caso o determinante da matriz de coeficientes desaparece e não é possível resolver o sistema. Assim, depois de reorganizar a 3ª equação na primeira linha, executamos as etapas descritas anteriormente.
A procura do elemento módulo máximo pode ser tratada a cada iteração, ou seja, em
$ inline $ k $ inline $ -ª iteração a procurar
$ inline $ \ max | a_ {kj} | $ inline $ então mude
$ inline $ j $ inline $ e
$ inline $ k $ inline $ ª linha. O algoritmo no qual o elemento máximo na coluna é pesquisado é chamado de método de Gauss, com a escolha do elemento principal na coluna.
Existe outro caminho. Pode
$ inline $ k $ inline $ -ª iteração a procurar
$ inline $ \ max | a_ {ik} | $ inline $ , altere não as linhas, mas as colunas. Mas é importante lembrar os índices das colunas variáveis em alguma matriz
$ inline $ \ alpha $ inline $ (para restaurar a ordem exata das variáveis).
Um exemplo de um código simples que implementa esse algoritmo:
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];
Por que Gauss?
Há outra maneira de resolver o SLAE. Um deles é o método Cramer. Consiste no cálculo preliminar de um determinado número de determinantes, com a ajuda dos quais os valores das variáveis são calculados instantaneamente. Sob o sistema original, este método será semelhante a este:
exibição $$ $$ \ Delta = \ begin {vmatrix} a_ {11} e a_ {12} e a_ {13} \\ a_ {21} e a_ {22} e a_ {22} e a_ {23} \\ a_ {31} e a_ {32} e a_ {33} \\ \ end {vmatrix}, \ Delta_1 = \ begin {vmatrix} b_1 e a_ {12} e a_ {13} \\ b_2 e a_ {22} e a_ {23} \ \ b_3 e a_ {32} e a_ {33} \\ \ end {vmatrix}, $$ display $$
exibição $$ $$ \ Delta_2 = \ begin {vmatrix} a_ {11} & b_1 & a_ {13} \\ a_ {21} & b_2 & a_ {23} \\ a_ {31} & b_3 & a_ {33} \\ \ end {vmatrix}, \ Delta_3 = \ begin {vmatrix} a_ {11} e a_ {12} e b_1 \\ a_ {21} e a_ {22} e b_2 \\ a_ {31} e a_ {32 } & b_3 \\ \ end {vmatrix}, $$ display $$
$$ display $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ display $$
Mas lembre-se - o que é um qualificador?
Por definição, o determinante de uma matriz
$ inline $ A = (a_ {ij}) $ inline $ existe uma quantidade
exibição $$ $$ \ soma \ limites_ {1 \ leq i_1 <\ pontos <i_n \ leq n} (-1) ^ {N (i_1, \ pontos, i_n)} a_ {1i_1} \ pontos a_ {ni_n}, $$ display $$
onde
$ inline $ N (i_1, \ pontos, i_n) $ inline $ - curinga
$ inline $ i_1, \ dots, i_n. $ inline $
O determinante contém
$ inline $ n! $ inline $ termos. Para resolver o sistema, você precisa contar
$ inline $ n + 1 $ inline $ determinantes. Em tamanho suficientemente grande
$ inline $ n $ inline $ é muito caro Por exemplo, quando
$ inline $ n = 12 $ inline $ o número de operações se torna
$ 12 inline $ 12! (12 + 1) = 6227020800, $ inline $ enquanto o método de Gauss com assintóticos
$ inline $ n ^ 3 $ inline $ exigirá apenas
$ inline $ 12 ^ 3 = 1728 $ inline $ operações.
Métodos Iterativos
Os chamados métodos iterativos também são adequados como algoritmos para resolver SLAEs. Eles consistem em calcular seqüencialmente as aproximações até que uma delas esteja o mais próximo possível da resposta exata.
Primeiro, algum vetor arbitrário é selecionado
$ inline $ x ^ 0 $ inline $ É uma aproximação zero. Um vetor é construído sobre ele.
$ inline $ x ^ 1 $ inline $ - esta é a primeira aproximação. E assim por diante Os cálculos terminam quando
$ inline $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ inline $ onde
$ inline $ \ varepsilon $ inline $ - algum valor definido antecipadamente. A última desigualdade significa que nosso “aprimoramento” da solução a cada iteração é quase insignificante.
Considere o método Jacobi popular, que é um dos métodos iterativos mais simples para resolver SLAEs.
Para começar, escrevemos o sistema da seguinte forma:
$$ exibir $$ \ soma \ limites_ {j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n}. $$ display $$
Separar
$ inline $ i $ inline $ -th termo e expressá-lo através de todo o resto:
$$ display $$ x_i = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}. $$ display $ $
Agora basta pendurar os "contadores" nas variáveis e obter o método de iteração 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, \ dots. $$ display $$
Observe que um pré-requisito para usar esse método é a ausência de zeros na diagonal principal.
Implementação do método Jacobi em Java:
Como $ inline $ \ varepsilon $ inline $ é tomada uma chamada máquina epsilon pré-calculada. 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; } }
Uma modificação do método Jacobi é o método de relaxamento. Sua principal diferença é que, com a ajuda de um parâmetro pré-selecionado, o número de iterações é reduzido significativamente. Vamos descrever brevemente a idéia principal do método.
Do sistema original, expressamos novamente
$ inline $ x $ inline $ , mas vamos configurar os contadores de forma um pouco diferente e adicionar o parâmetro
$ inline $ \ omega $ inline $ :
$$ 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- \ ômega) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ pontos. $$ exibir $$
At
$ inline $ \ omega = 1 $ inline $ tudo se transforma em um método Jacobi.
Então, vamos procurar algumas "boas"
$ inline $ \ omega $ inline $ . Defina algum número
$ inline $ s $ inline $ e tomaremos valores
$ inline $ \ omega \ in (0,2) $ inline $ , para cada um dos quais consideraremos as normas
$ inline $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s} $ inline $ . Para a menor dessas normas, lembre-se deste valor
$ inline $ \ omega $ inline $ , e com ele resolveremos nosso sistema.
Ilustração do método Java:
aqui $ inline $ s = 5 $ inline $ 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; } }
Em vez de uma conclusão
Existem muitos outros algoritmos para resolver o SLAE. Por exemplo, o método da raiz quadrada, no qual o sistema desejado é substituído por dois sistemas "simples", cujas soluções são calculadas por fórmulas elementares; método de varredura, usado para matrizes tridiagonais tão específicas. Todo mundo escolhe qual método usar para o seu problema.