Baixe o app para aproveitar ainda mais
Prévia do material em texto
Sistemas de Equac¸o˜es Lineares Introduc¸a˜o Me´todos Iterativos Introduc¸a˜o I Os me´todos diretos na˜o sa˜o os mais indicados para resolver sistemas esparsos e os sistemas de grande porte. I O refinamento do algoritmo de Gauss e´ uma forma de me´todo iterativo. I Os algoritmos iterativos partem de uma soluc¸a˜o inicial e sistematicamente geram uma sequeˆncia de iterandos. I Dada uma aproximac¸a˜o inicial x0 da soluc¸a˜o de Ax = b, o processo iterativo pode ser descrito como: xk+1 = G (xk), k = 1, 2, . . . , I Aqui vamos estudar os me´todos de Jacobi e de Gauss-Seidel. 4 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Me´todo de Jacobi Seja Ax = b um sistema de equac¸o˜es lineares quadrado, expresso na forma: a11 a12 . . . a1n a21 a22 . . . a2n ... ... ... ... an1 an2 . . . ann x1 x2 ... xn = b1 b2 ... bn (1) 6 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Me´todo de Jacobi Assumindo que ajj 6= 0 para j = 1, . . . , n, podemos expressar (1) na forma:{ xj = 1 ajj (bj − aj1x1 − aj2x2 − . . . −aj ,(j−1)xj−1 − aj ,(j+1)xj+1 − . . .− aj ,nxn ) (2) para j = 1, . . . , n, onde sa˜o conhecidos os valores de x1, x2, . . . , xj−1, xj+1, . . . , xn a serem utilizados no lado direito da expressa˜o acima. 7 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Me´todo de Jacobi O Me´todo de Jacobi consiste no processo iterativo dado por: xk+1j = 1 ajj ( bj − aj1x k 1 − aj2x k 2 − . . . −aj ,(j−1)x k j−1 − aj ,(j+1)x k j+1 − . . .− aj ,nx k n ) (3) para j = 1, . . . , n. 8 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Me´todo de Jacobi Observac¸o˜es I Se o sistema Ax = y e´ na˜o singular, sempre sera´ poss´ıvel obter ajj 6= 0 se trocarmos as equac¸o˜es adequadamente. I Em sistemas esparsos, o me´todo de Jacobi evita multiplicac¸o˜es desnecessa´rias, simplificando a expressa˜o acima. 9 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Me´todo de Jacobi Algoritmo (x1, . . . , xn, aij , bj , lim) 1) k ← 1 2) Enquanto k < lim Para j = 1, . . . , n zj = 1 ajj (bj − aj1x1 − aj2x2 − . . . −aj ,(j−1)xj−1 − aj ,(j+1)xj+1 − . . .− aj ,nxn ) Se teste de convergeˆncia e´ satisfeito Sa´ıda(zj : j = 1, . . . , n) Caso contra´rio xj ← zj , j = 1, . . . , n k ← k + 1 3) Sa´ıda“Algoritmo na˜o convergente”. 10 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Exemplo do Me´todo de Jacobi Vamos tomar como exemplo o sistema de equac¸o˜es lineares dado por: 5x1 + − 3x4 − x5 = 2 −x1 + 4x2 − x5 = 3 + 2x3 − x4 = −1 −x1 + 4x4 − 2x5 = 0 − x4 + 2x5 = −1 (4) 11 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Exemplo do Me´todo de Jacobi Primeiramente, obtemos o operador iterativo que corresponde a`s equac¸o˜es: xk+11 = 1 5(2 + 3x k 4 + x k 5 ) xk+12 = 1 4(3 + x k 1 + x k 5 ) xk+13 = 1 2(−1 + x k 4 ) xk+14 = 1 4(x k 1 + 2x k 5 ) xk+15 = 1 2(−1 + x k 4 ) (5) O processo iterativo acima ao ser aplicado na resoluc¸a˜o de (4) produz a sequ¨eˆncia de iterandos dada na Tabela 1. 12 / 61 Sistemas de Equac¸o˜es Lineares Me´todo de Jacobi Exemplo do Me´todo de Jacobi Tabela: iterandos obtidos pelo processo iterativo de Jacobi Iterac¸a˜o 1 2 . . . 35 36 x1 1 1.20 . . . 0.0869574059 0.086957108 x2 1 1.25 . . . 0.6086962107 0.608696020 x3 1 0.00 . . . -0.6521793252 -0.652173522 x4 1 0.75 . . . -0.3043470441 -0.304347311 x5 1 0.00 . . . -0.6521733252 -0.652173522 13 / 61
Compartilhar