Prévia do material em texto
MODELAGEM MATEMÁTICA Aula 05: SISTEMAS DE EQUAÇÕES LINEARES – MÉTODOS ITERATIVOS Apresentação Na aula passada, começamos a tratar do estudo de sistemas de equações lineares algébricas (SELA), com base nos métodos diretos. Como vimos, tais sistemas são muito úteis em tarefas diversas, como a análise de circuitos elétricos (Engenharia Elétrica), do comportamento variante no tempo de sistemas de comunicações sem �o (Engenharia de Telecomunicações), de sistemas mecânicos (Engenharia Mecânica) e da distribuição de forças em estruturas (Engenharia Civil), dentre outros. No entanto, nem sempre é possível determinar de forma direta a solução de tais sistemas. Desta forma, faz-se necessário o emprego de métodos que permitem, via repetição de procedimentos, a identi�cação da solução ou, ao menos, de valores aproximados à solução do problema. Tais métodos são os denominados métodos iterativos, bastante utilizados na resolução de sistemas de equações lineares. Assim, o objetivo desta aula é continuar os estudos de sistemas de equações lineares, mas agora com foco nos métodos iterativos. Em primeiro lugar, você aprenderá o método de Gauss-Jacobi. Em seguida, você estudará o método Gauss- Seidel. Ao �nal, você será capaz de aplicar os métodos estudados, por meio da implementação computacional de programas em Python. Objetivos Identi�car os principais métodos iterativos de resolução de sistemas de equações lineares: Gauss-Jacobi e Gauss- Seidel. Aplicar os métodos estudados com suporte da linguagem de programação Python. Método de Gauss - Jacobi Conforme descrito em Moura (2017), os métodos iterativos não apresentam uma solução exata de SELA, mas aproximações da solução, obtidas a partir do emprego de iterações sucessivas. Tal procedimento é conseguido a partir da avaliação das expressões que constituem o SELA. Sua principal vantagem em relação aos métodos diretos (que estudamos na aula passada) é simplicidade no processo de resolução, pois existem sistemas que não apresentam uma solução exata – em especial, os provenientes de aproximações do mundo físico. Tais expressões são obtidas a partir do isolamento de cada uma das variáveis, obtidas a partir de cada uma das equações do SELA. Depois disso, com base em valores previamente atribuídos às variáveis, são realizadas diversas iterações para avaliação dos novos valores obtidos, até que o critério de convergência seja alcançado. O primeiro dos métodos que estudaremos na aula de hoje é o denominado Método de Gauss-Jacobi. Vamos considerar o sistema linear apresentado a seguir: + + + . . . + = a11 x1 a12x2 a13x3 a1n xn b1 + + + . . . + = a21 x1 a22x2 a23x3 a2n xn b2 + + + . . . + = a31 x1 a32x2 a33x3 a3n xn b3 + + + . . . + = an1 x1 an2 x2 an3 x3 annxn bn Dadas as expressões que vimos, você pode isolar as incógnitas em cada equação. Desta forma, obtemos as seguintes expressões: Agora, basta você apresentar uma estimativa ou aproximação inicial para cada uma das variáveis acima para obter a solução. Ou seja, você deve escolher um conjunto de valores { } para iniciar a solução do SELA, com emprego do método de Gauss-Jacobi. = ( − − − . . . − )x1 1 a11 b1 a12x2 a13x3 a1n xn = ( − − − . . . − )x2 1 a22 b2 a21x1 a23x3 a2n xn = ( − − − . . . − )x3 1 a33 b3 a31x1 a32x2 a3n xn . . . = ( − − − . . . − )xn 1 ann bn an1 x1 an2 x2 an−1.nxn−1 , , , . . . ,x1 (0) x2 (0) x3 (0) xn (0) Com isso, como resultado da primeira iteração, obtém-se o conjunto de valores { }, de tal maneira que: , , , . . . ,x1 (1) x2 (1) x3 (1) xn (1) = ( − − − . . . − )x1(1) 1a11 b1 a12x2 (0) a13x3 (0) a1n xn (0) = ( − − − . . . − )x2(1) 1a22 b2 a21x1 (0) a23x3 (0) a2n xn (0) = ( − − − . . . − )x3(1) 1a33 b3 a31x1 (0) a32x2 (0) a3n xn (0) . . . = ( − − − . . . − )xn (1) 1ann bn an1 x1 (0) an2 x2 (0) an−1.nx (0) n−1 E assim devemos proceder sucessivamente. Por exemplo, o conjunto de valores obtido na k-ésima iteração (ou seja, { }) é expresso a partir dos valores obtidos na iteração anterior (k-1). Veja, a seguir, como �cam os cálculos nesta etapa da resolução: Assim, imaginamos que você já tenha entendido a ideia principal do Método de Gauss-Jacobi. Neste método, cada coordenada do vetor correspondente à nova aproximação é calculada a partir da respectiva equação do sistema, utilizando-se as demais coordenadas do vetor aproximação da iteração anterior. , , , . . . ,x1 (k) x2 (k) x3 (k) xn (k) = ( − − − . . . − )x1(k) 1a11 b1 a12x2 (k−1) a13x3 (k−1) a1n xn (k) = ( − − − . . . − )x2(k) 1a22 b2 a21x1 (k−1) a23x3 (k−1) a2n xn (k−1) = ( − − − . . . − )x3(k) 1a33 b3 a31x1 (k−1) a32x2 (k−1) a3n xn (k−1) . . . = ( − − − . . . − )xn (k) 1ann bn an1 x1 (k−1) an2 x2 (k−1) an−1.nx (k−1) n−1 Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online Por �m, é importante destacar que o processo é �nalizado ao se atingir uma precisão preestabelecida, calculada a partir do valor máximo de desvio para as incógnitas entre iterações sucessivas – exatamente como �zemos no caso do método de Gauss-Jacobi. De igual modo, também pode ser �nalizado ao se atingir um número máximo preestabelecido de iterações, com vantagens semelhantes. No entanto, você pode estar se perguntando: quando é que chegamos ao �nal destes cálculos? Simples: o processo é �nalizado ao se atingir uma precisão preestabelecida, calculada a partir do valor máximo de desvio para as incógnitas entre iterações sucessivas. Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online Comentário De modo alternativo, pode-se interromper o processo ao se atingir um número máximo preestabelecido de iterações. Essa última estratégia de �nalização do processo traz como vantagem a facilidade em determinar o tempo máximo de processamento numérico em um computador para cálculo da solução. O algoritmo que representa a operação descrita anteriormente é dado por: /* Dados de Entrada: vetor de estimativa inicial – x, número de variáveis – n;vetor de coe�cientes – A; vetor de termos independentes – b, número máximo de iterações – L, tolerância de erro na aproximação - tol*/ /* Resultado: vetor solução – x*/ Início i ← 0 diff ← 100000 Enquanto (i < L e diff>tol) faça y ← x Para i de 1 até n faça soma ← 0 Para j de 1 até n faça Se ( ) Então soma ← soma + Fim-Se xi← Fim-Para diff ← |x1 - y1| Para i de 2 até n faça Se (|xi – yi| >diff) Entãodiff ← |xi – yi| Fim-Se Fim-Para i ← i + 1 Fim-Enquanto Fim-GaussJacobi j ≠ i aijxj aii − somabi aii Como exemplo de aplicação, considere as matrizes A e b conforme descrito em Moura (2017): Assim, a título de ilustração, considere-se como palpite inicial os valores de x(1) = x(2) = x(3) = 1, com uma tolerância de erro na aproximação no valor de 0, 001 ou inferior. De acordo com o emprego previsto da técnica iterativa de Gauss-Jacobi para resolução de SELA, tem-se que: A = ; b = ⎡ ⎣ ⎢ 2 −1 3 −3 1 2 1 −5 −1 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 0 −3 −1 ⎤ ⎦ ⎥ x (1) = = = = 1 b(1) − A(1,2) × (2) − A(1,3) × (3) A(1,1) 0 − (−3) .(1) − 1.1 2 3−1 2 x (2) = = = = 3 b(2) − A(2,1) × (1) − A(2,3) × (3) A(2,2) (−3) − (−1).(1) − (−5).1 1 3 1 x (3) = = = = 6 b(3) − A(3,1) × (1) − A(3,2) × (2) A(3,3) −1 − (3).(1) − (2).1 −1 −6 −1 Veja que, depois da 1a iteração, os novos valores de teste são x(1) = 1, x(2) = 3 e x(3) = 6. Como a maior diferença (5, para a variável x(3)) excede a tolerância especi�cada, você precisa realizar uma nova iteração. Veja só como �ca esta segunda rodada: x (1) = = = = 1, 5 b(1) − A(1,2) × (2) − A(1,3) × (3) A(1,1) 0 − (−3) .(3) − 1.6 2 3 2 x (2) == = = 28 b(2) − A(2,1) × (1) − A(2,3) × (3) A(2,2) (−3) − (−1).(1) − (−5).6 1 28 1 x (3) = = = = 10 b(3) − A(3,1) × (1) − A(3,2) × (2) A(3,3) −1 − (3).1 − (2).3 −1 −10 −1 Após a 2a iteração, temos que os novos valores de teste são x(1) = 1,5, x(2) = 28 e x(3) = 10. Como a maior diferença (25, para a variável x(2)) também excede a tolerância especi�cada, você precisa realizar uma terceira iteração e, assim, sucessivamente. Comentário Creio que agora você tenha entendido como funciona o método de Gauss-Jacobi. Este é o método iterativo básico para resolução de sistemas de equações lineares. No entanto, não é o de convergência mais rápida. Existem alternativas que, com sutis diferenças, permitem determinar mais rapidamente a solução de um sistema de equações lineares. Dentre estes, destaca-se o método de Gauss-Seidel, que veremos na próxima seção desta aula. Método de Gauss-Seidel De modo semelhante ao exposto na seção anterior, tem-se que a resolução de um SELA por meio do Método de Gauss-Seidel considera, em princípio, um sistema linear como o descrito a seguir: Tal qual feito para o método de Gauss-Jacobi, nós podemos isolar as incógnitas em cada uma das equações: + + + . . . + = a11 x1 a12x2 a13x3 a1n xn b1 + + + . . . + = a21 x1 a22x2 a23x3 a2n xn b2 + + + . . . + = a31 x1 a32x2 a33x3 a3n xn b3 + + + . . . + = an1 x1 an2 x2 an3 x3 annxn bn = ( − − − . . . − )x1 1 a11 b1 a12x2 a13x3 a1n xn = ( − − − . . . − )x2 1 a22 b2 a21x1 a23x3 a2n xn = ( − − − . . . − )x3 1 a33 b3 a31x1 a32x2 a3n xn . . . = ( − − − . . . − )xn 1 ann bn an1 x1 an2 x2 an−1.nxn−1 Ainda de acordo com o que �zemos no método anterior, você deve estipular uma estimativa inicial para cada uma das incógnitas destacadas nas equações que acabamos de ver – ou seja, um conjunto de valores {x1(0), x2(0), x3(0), ..., xn(0)} para iniciar a solução do SELA. No entanto, conforme destacado em Moura (2017), a partir daqui nós temos a diferença em relação ao método anterior. Aqui, no Método de Gauss-Seidel, cada coordenada do vetor correspondente à nova aproximação é calculada a partir da respectiva equação do sistema, utilizando-se as coordenadas do vetor aproximação da iteração anterior, quando essas ainda não foram calculadas na iteração corrente, e as coordenadas do vetor aproximação da iteração corrente, no caso contrário. Com isso, como resultado da primeira iteração, obtém-se o conjunto de valores { } tal que: , , , . . . ,x1 (1) x2 (1) x3 (1) xn (1) = ( − − − . . . − )x1(1) 1a11 b1 a12x2 (0) a13x3 (0) a1n xn (0) = ( − − − . . . − )x2(1) 1a22 b2 a21x1 (1) a23x3 (0) a2n xn (0) = ( − − − . . . − )x3(1) 1a33 b3 a31x1 (1) a32x2 (1) a3n xn (0) . . . = ( − − − . . . − )xn (1) 1ann bn an1 x1 (1) an2 x2 (1) an−1.nx (1) n−1 Veja que na segunda equação nós utilizamos o novo valor de , e não , como aconteceu no método de Gauss-Jacobi. De igual modo, na terceira equação, além do novo valor de , nós utilizamos no lugar de . Assim, seguimos até a última equação, que naturalmente utiliza todas as novas estimativas para as variáveis anteriormente calculadas. Desta forma, podemos ver o caso geral a partir das expressões das equações na k-ésima iteração - { }). Veja, a seguir, como �cam os cálculos nesta etapa da resolução: (ou seja, x1 x1(1) x1(0) x1 x2 (1) x2 (0) { (k), (k), (k), . . . , (k)x1 x2 x3 xn = ( − − − . . . − )x1(k) 1a11 b1 a12x2 (k−1) a13x3 (k−1) a1n xn (k) = ( − − − . . . − )x2(k) 1a22 b2 a21x1 (k) a23x3 (k−1) a2n xn (k−1) = ( − − − . . . − )x3(k) 1a33 b3 a31x1 (k) a32x2 (k) a3n xn (k−1) . . . = ( − − − . . . − )xn (k) 1ann bn an1 x1 (k) an2 x2 (k) an−1.nx (k) n−1 Uma dúvida relevante que você pode se fazer é: será que sempre dá certo o emprego deste método? Infelizmente, não. Conforme destacado em Moura (2017), a iteração do método de Gauss-Seidel convergirá se, no determinante característico, cada termo da diagonal principal for maior (em valor absoluto) do que a soma dos valores absolutos de todos os outros termos na mesma linha ou coluna. Isto é, teremos garantido a convergência se e O algoritmo que representa a operação descrita anteriormente é dado por: | | > | |aii ∑ n j=1,j≠i aji | | > | |, i = 1, 2, . . . , naii ∑ n j=1,j≠i aji /* Dados de Entrada: vetor de estimativa inicial – x, número de variáveis – n;vetor de coe�cientes – A; vetor de termos independentes – b, número máximo de iterações – L, tolerância de erro na aproximação - tol*/ /* Resultado: vetor solução – x*/ Início i ← 0 diff ← 100000 Enquanto (i < L e diff>tol) faça y ← x Para i de 1 até n faça soma_antes← 0 Para j de i+1 até n faça soma_antes← soma _antes+ Fim-Para soma_depois← 0 Para j de 1 até i faça soma_depois← soma _depois+ Fim-Para soma ← soma_antes + soma _depois + xi← Fim-Para diff ← |x1 - y1| Para i de 2 até n faça Se (|xi – yi| >diff) Entãodiff ← |xi – yi| Fim-Se Fim-Para i ← i + 1 Fim-Enquanto Fim-GaussSeidel aijyj aijxj aiixi bi − soma aii Considere novamente as matrizes A e b, conforme descrito a seguir: Assim, a título de ilustração, considere-se como palpite inicial os valores de x(1) = x(2) = x(3) = 1, com uma tolerância de erro na aproximação no valor de 0, 001 ou inferior. De acordo com o emprego previsto da técnica iterativa de Gauss-Jacobi para resolução de SELA, tem-se que: A = ; b = ⎡ ⎣ ⎢ 2 −1 3 −3 1 2 1 −5 −1 ⎤ ⎦ ⎥ ⎡ ⎣ ⎢ 0 −3 −1 ⎤ ⎦ ⎥ x (1) = = = = 1 b(1) − A(1,2) × (2) − A(1,3) × (3) A(1,1) 0 − (−3) .(1) − 1.1 2 3−1 2 x (2) = = = = 3 b(2) − A(2,1) × (1) − A(2,3) × (3) A(2,2) (−3) − (−1).(1) − (−5).1 1 3 1 x (3) = = = = 10 b(3) − A(3,1) × (1) − A(3,2) × (2) A(3,3) −1 − (3).(1) − (2).3 −1 −10 −1 Você pode ver que, após a 1a iteração, os novos valores de teste são x(1) = 1, x(2) = 3 e x(3) = 10. Como a maior diferença (9, para a variável x(3)) excede a tolerância especi�cada, faz-se necessária uma nova iteração: Após realizar a 2a iteração, vemos que os novos valores de teste são x(1) = -0,5, x(2) = 46,5 e x(3) = 92,5. Como a maior diferença (82,5, para a variável x(3)) também excede a tolerância especi�cada, faz-se necessária uma terceira iteração, e assim sucessivamente. x (1) = = = = − 0, 5 b(1) − A(1,2) × (2) − A(1,3) × (3) A(1,1) 0 − (−3) .(3) − 1.10 2 −1 2 x (2) = = = = 46, 5 b(2) − A(2,1) × (1) − A(2,3) × (3) A(2,2) (−3) − (−1).(−0,5) − (−5).10 1 46,5 1 x (3) = = = = 92, 5 b(3) − A(3,1) × (1) − A(3,2) × (2) A(3,3) −1 − (3).(−0,5) − (2).46,5 −1 −92,5 −1 Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online Aplicação da linguagem Python Vamos ver os códigos em Python destes dois métodos? Com isto, creio que você estará em condições de aplicar os conhecimentos aprendidos em implementações computacionais que o ajudem a solucionar problemas em Engenharia. O código, a seguir, disponível em UFRGS (2019), implementa a solução do método de Gauss-Jacobi. rom __future__ import division import numpy as np from numpy import linalg def jacobi(A,b,x0,tol,N): #preliminares A = A.astype(’double’) b = b.astype(’double’) x0 = x0.astype(’double’) n=np.shape(A)[0] x = np.zeros(n) it = 0 #iteracoes while (it < N): it = it+1 #iteracao de Jacobi for i in np.arange(n): x[i] = b[i] for j in np.concatenate((np.arange( 0,i),np.arange(i+1,n))): x[i] -= A[i,j]*x0[j] x[i] /= A[i,i] #toleranciaif (np.linalg.norm(x-x0,np.inf) < tol): return x #prepara nova iteracao x0 = np.copy(x) raise NameError(’num. max. de iteracoes excedido.’) Já quanto ao método de Gauss-Seidel, podemos utilizar a implementação disponível em UFRGS (2019). Veja a seguir: from __future__ import division import numpy as np from numpy import linalg def gauss_seidel(A,b,x0,tol,N): #preliminares A = A.astype(’double’) b = b.astype(’double’) x0 = x0.astype(’double’) n=np.shape(A)[0] x = np.copy(x0) it = 0 #iteracoes while (it < N): it = it+1 #iteracao de Jacobi for i in np.arange(n): x[i] = b[i] for j in np.concatenate((np.arange( 0,i),np.arange(i+1,n))): x[i] -= A[i,j]*x[j] x[i] /= A[i,i] print(x[i],A[i,i]) #tolerancia if (np.linalg.norm(x-x0,np.inf) < tol): return x #prepara nova iteracao x0 = np.copy(x) raise NameError(’num. max. de iteracoes excedido.’) Atividade 1. Assinale a única alternativa que apresenta a solução para o sistema de equações lineares 10*x1 -1*x2 + 2*x3 + 0*x4 = 6 -5*x1 + 11*x2 -1*x3 + 3*x4 = 25 3*x1 -1*x2 +10*x3 -1*x4 = -11 1*x1 + 3*x2 -1*x3 + 8*x4 = 15 Utilize como estimativas iniciais o vetor [1, 1, 1, 1] e o método de Gauss-Seidel: a) x = [1.07, 2.47, -1.11, 0.68] b) x = [-1.07, 2.47, -1.11, 0.68] c) x = [1.07,- 2.47, -1.11, 0.68] d) x = [1.07, 2.47, 1.11, 0.68] e) nenhuma das alternativas anteriores. 2. Assinale a única alternativa que apresenta a quantidade de iterações necessária para encontrar solução para o sistema de equações lineares 10*x1 -1*x2 + 2*x3 + 0*x4 = 6 -5*x1 + 11*x2 -1*x3 + 3*x4 = 25 3*x1 -1*x2 +10*x3 -1*x4 = -11 1*x1 + 3*x2 -1*x3 + 8*x4 = 15 Utilize como estimativas iniciais o vetor [1, 1, 1, 1] e o método de Gauss-Seidel: a)12 b)22 c)10 d)17 e) nenhuma das alternativas anteriores. 3. Assinale a única alternativa que apresenta a solução para o sistema de equações lineares 10*x1 -1*x2 + 2*x3 + 0*x4 = 6 -5*x1 + 11*x2 -1*x3 + 3*x4 = 25 3*x1 -1*x2 +10*x3 -1*x4 = -11 1*x1 + 3*x2 -1*x3 + 8*x4 = 15 Utilize como estimativas iniciais o vetor [1, 1, 1, 1] e o método de Gauss-Jacobi: a) x = [1.07, 2.47, -1.11, 0.68] b) x = [-1.07, 2.47, -1.11, 0.68] c) x = [1.07,- 2.47, -1.11, 0.68] d) x = [1.07, 2.47, 1.11, 0.68] e) nenhuma das alternativas anteriores 4. Assinale a única alternativa que apresenta a quantidade de iterações necessária para encontrar solução para o sistema de equações lineares 10*x1 -1*x2 + 2*x3 + 0*x4 = 6 -5*x1 + 11*x2 -1*x3 + 3*x4 = 25 3*x1 -1*x2 +10*x3 -1*x4 = -11 1*x1 + 3*x2 -1*x3 + 8*x4 = 15 Utilize como estimativas iniciais o vetor [1, 1, 1, 1] e o método de Gauss-Jacobi: a) 12 b) 35 c) 25 d) 40 e) nenhuma das alternativas anteriores. 5. Assinale a única alternativa que apresenta a solução para o sistema de equações lineares 10*x1 -1*x2 + 2*x3 + 0*x4 = 6 -5*x1 + 11*x2 -1*x3 + 3*x4 = 25 3*x1 -1*x2 +10*x3 -1*x4 = -11 1*x1 + 3*x2 -1*x3 + 8*x4 = 15 Utilize como estimativas iniciais o vetor [1, 1, 1, 1] e o método de Gauss-Jacobi: a) x = [0.92, 0.87, -1.16, 1.29] b) x = [-0.92, 0.87, -1.16, 1.29] c) x = [0.92,-0.87, -1.16, 1.29] d) x = [0.92, 0.87, 1.16, 1.29] e) nenhuma das alternativas anteriores. Notas escolha Por exemplo, utilize o compilador online disponível em: https://www.onlinegdb.com/online_python_compiler, acesso em 16 OUT 19. Referências javascript:void(0); MOURA, D. F. C, Cálculo Numérico. Rio de Janeiro: SESES, 2017. 144 p. UFRGS (colaborativo). Cálculo Numérico: Um Livro Colaborativo Versão Python. Porto Alegre: UFRGS, 2019. Próxima aula Os principais métodos de interpolação polinomial; O método de Lagrange; O método de Newton; Os métodos estudados em Python, aplicando-os em situações-problema típicas em Engenharia. Explore mais Segue uma lista de sites na Internet para que você os consulte depois: Prof. Rex Medeiros. Método de Jacobi – Resolução de Sistemas Lineares. Disponível em: https://www.youtube.com/watch?v=ksGH52MMy4Iacesso em 24 de outubro de 2019. Código Exato. Resolução de sistemas lineares utilizando Python. Disponível em: https://www.youtube.com/watch? v=14N89iDB�Qacesso em 24 de outubro de 2019. Sigmoidal.Resolvendo um Sistema de Equações Lineares com Python. Disponível em: https://www.youtube.com/watch? v=ZPmtWwZ5GuU acesso em 24 de outubro de 2019. javascript:void(0); javascript:void(0); javascript:void(0);