Baixe o app para aproveitar ainda mais
Prévia do material em texto
Profs.: Bruno Correia da Nóbrega Queiroz José Eustáquio Rangel de Queiroz Marcelo Alves de Barros Resolução Numérica de Sistemas Lineares – Parte I Cálculo NuméricoCálculo Numérico Módulo VMódulo V 2 Sistemas Lineares Forma Geral onde: aaijij coeficientes xxii incógnitas nnnn22n11n 2nn2222121 1nn1212111 bxa...xaxa bxa...xaxa bxa...xaxa =+++ =+++ =+++ 3 Exemplo 01 2, 4, 5, 4, 1, 5, 2, 4 e 5 coeficientes x1, x2 e x3 incógnitas Sistemas Lineares 1x5x4x2 2x5x1x4 5x5x4x2 321 321 321 −=++ =−+ =−+ 4 Sistemas Lineares Forma Matricial onde: 4 Ax = bAx = b = nn3n2n1n n22221 n11211 aaaa aaa aaa A = n 2 1 b b b b = n 2 1 x x x x 5 Sistemas Lineares 1x5x4x2 2x5x1x4 5x5x4x2 321 321 321 −=++ =−+ =−+ 5 Exemplo 02 Forma Geral Forma Matricial − = − − 1 2 5 x x x . 542 514 542 3 2 1 6 Sistemas Lineares Classificação I ImpossívelImpossível NãoNão possui solução Exemplo 03 6 =+ =+ 9x2x2 3xx 21 21 7 Sistemas Lineares Classificação II PossívelPossível Possui 1 ou mais soluções DeterminadoDeterminado Solução únicaúnica Exemplo 04 =− =+ 8xx 4xx 21 21 8 Classificação III PossívelPossível Possui 1 ou mais soluções IndeterminadoIndeterminado Mais de umaMais de uma solução Exemplo 05 Sistemas Lineares =+ =+ 8x2x2 4xx 21 21 9 Sistemas Lineares Classificação IV PossívelPossível Possui 1 ou mais soluções HomogêneoHomogêneo Vetor b=0b=0 (x=0 sempre existe solução) Exemplo 06 =+ =+ 0x3x2 0xx 21 21 10 Sistemas Lineares = nn3n2n1n 333231 2221 11 aaaa 0aaa 00aa 000a A Sistemas Triangulares: Possibilidade de resolução de forma RetroativaRetroativa InferiorInferior 11 Sistemas Lineares = nn n333 n22322 n1131211 a000 aa00 aaa0 aaaa A Sistemas Triangulares: Possibilidade de resolução de forma RetroativaRetroativa SuperiorSuperior 12 Solução Retroativa Exemplo 7: Dado o sistema: Primeiro passo para sua resolução: 2x2 3x5x4 1x2xx 10xx5x4x3 4 43 432 4321 = =− −=−+ −=+−+ 1 2 2x4 == 13 Solução Retroativa Exemplo 7: Segundo passo: Terceiro passo: 2x 315x4 3x5x4 3 3 43 = =⋅− =− 1x 1122x 1x2xx 2 2 432 −= −=⋅−+ −=−+ 14 Solução Retroativa Exemplo 7: Último passo: 1x 10125)1(4x3 10xx5x4x3 1 1 4321 = −=+⋅−−⋅+ −=+−+ 15 Métodos Numéricos DiretosDiretos Solução pode ser encontrada através de um número finito de passos Método de GaussMétodo de Gauss Método da Eliminação de JordanMétodo da Eliminação de Jordan Fatoração LUFatoração LU 16 Métodos Numéricos IterativosIterativos Solução a partir de uma seqüência de seqüência de aproximações aproximações para o valor do vetor solução xx , até que seja obtido um valor que satisfaça à precisão préestabelecida Método de JacobiMétodo de Jacobi Método de Gauss – SiedelMétodo de Gauss – Siedel 17 Método de Gauss Propósito Transformação do sistema linear a ser resolvido em um sistema linear triangularsistema linear triangular; Resolução do sistema linear triangular de forma retroativaretroativa 18 Método de Gauss Transformação do Sistema Linear Troca da ordem das linhas; Multiplicação de uma das equações por um número real não nulo; Substituição de uma das equações por uma combinação linear dela mesma com outra equação. 19 Método de Gauss Passos do Método de Gauss Construção da matriz aumentada AbAb 19 [ ] = nnn3n2n1n 2n22221 1n11211 baaaa baaa baaa Ab 20 Método de Gauss Passos do Método de Gauss Passo 1: Eliminar os coeficientes de xEliminar os coeficientes de x11 presentes nas linhas 2,3,...,n sendo a21 = a31, = ... = an1 = 0 sendo aa1111 chamado de pivô da colunapivô da coluna Substituir a linha 2, LL22, pela combinação linear 11 21 211212 a am:onde,LmL =⋅− 21 Método de Gauss 11 31 3113133 a am:onde,LmLL =⋅−= Passos do Métdo de Gauss Substituir a linha 3, L3, pela combinação linear: 22 Método de Gauss Passos do Método de Gauss Devese continuar a substituição até a linha n; Caso algum elemento app=0, achar outra linha k onde akp≠ 0 e trocar tais linhas. Caso a linha k não exista, o sistema linear não possui solução. 23 Método de Gauss Passos do Método de Gauss Eliminar os coeficientes de x2 nas linhas 3, 4, ..., n (fazer a32=a42=...=an2 = 0); Eliminar os coeficientes de x3 nas linhas 4, 5, ..., n (fazer a43=a53=...=an3 = 0) e assim sucessivamente. 24 Método de Gauss Exemplo 8: Resolver o sistema: Matriz aumentada Ab 1xx3x2 3x3x4x4 5xx3x2 321 321 321 −=+− =−+ =−+ [ ] −− − − = 1132 3344 5132 Ab 25 Método de Gauss Exemplo 8: Fazse: Assim: 2 a am,LmLL 11 21 2112122 ==⋅−= [ ] [ ][ ]7120L 513223344L22 −−−= −⋅−−= 26 Método de Gauss Exemplo 8: Fazse: Assim: 1 a am,LmLL 11 31 2313133 ==⋅−= [ ] [ ] [ ]6260L 513211132L 3 3 −−= −⋅−−−= 27 Método de Gauss Exemplo 8: Obtémse a matriz: [ ] −− −−− − = 6260 7120 5132 Ab 28 Método de Gauss Exemplo 8: Substituindo a linha 3 por: Têmse: 3 a am,LmLL 22 32 3213233 ==⋅−= [ ] [ ] [ ]15500L 712037260L 3 3 = −−−⋅−−−= 29 Método de Gauss Exemplo 8: A matriz [Ab] fica assim com os seguintes valores: [ ] −−− − = 15500 7120 5132 Ab 30 Método de Gauss Exemplo 8: Usase a solução retroativa: =⇒=⇒=−+⇒=−⋅+ =⇒=−−⇒−=−− =⇒= 2x2x2536x25xx3x2 2x73x27xx2 3x15x5 111321 2232 33 31 Método de Gauss Exemplo 9: Resolver o sistema. Representando o sistema pela matriz aumentada: 38x14x2x22 134x3x110x27 57x52x4x 321 321 321 =++ =−+ =++ −= 3814222 134311027 575241 ]AB[ 32 Método de Gauss Exemplo 9: Escolhendo a primeira linha como pivô, obtémse: [ ] [ ] [ ] [ ] ( ) [ ] [ ]12101130860L 5752411/223814222LmLL 1410140020L 575241)1/27(134311027LmLL 3 13133 2 12122 −−−= ⋅−=⋅−= −−= ⋅−−=⋅−= 33 Método de Gauss Exemplo 9: Representando o sistema pela matriz aumentada: −−− −−= 12101130860 1410140020 575241 ]AB[ 34 Exemplo 9: Escolhendo agora a segunda linha como pivô, têmse: Obtêmse a seguinte matriz ampliada: Método de Gauss [ ] ( ) [ ] [ ]618006130000L 14101400202/8612101130860LmLL 3 13133 −−= −−⋅−−−−−=⋅−= −− −−= 618006130000 1410140020 575241 ]AB[ 35 Método de Gauss Exemplo 9: O que termina com a triangulação: ×−=⋅×−⋅+⋅ ×−=⋅×−⋅+⋅ =⋅+⋅+ 4 3 4 21 3 3 3 21 321 106.18x106.13x0x0 1014.1x10 40.1x2x0 57x52x4x 36 Método de Gauss Exemplo 9: Com solução: Um pouco diferente da solução exata: XX11=1,X=1,X22=1 e X=1 e X33=1=1 x3 = 61800/(61300)=1.01 x2 =[ 1410 – (1400)⋅1.01]/2 = 0.0 x1 = [57 52⋅1.01 4⋅0.0]/1 = 4.5 37 Método do Pivoteamento Parcial Semelhante ao método de Gauss; Minimiza a amplificação de erros de arredondamento durante as eliminações; Consiste em escolher o elemento de maior módulo em cada coluna para ser o pivô. 38 Método do Pivoteamento Parcial Exemplo 10: Resolver o sistema com precisão de 3 casas decimais =⋅+⋅+⋅ =⋅−⋅+⋅ =⋅+⋅+ 38x14x2x22 134x3x110x27 57x52x4x 321 321 321 39 Método do Pivoteamento Parcial Exemplo 10: Matriz aumentada original deve ser ajustada: − 3814222 134311027 575241 − 3814222 575241 134311027 40 Método do Pivoteamento Parcial Exemplo 10: Sistema inalterado, elemento pivô 2727. Encontrar as novas linhas: ]715.166.870[L ]134311027[)27/22(]3814222[LmLL ]521.5207.00[L ]134311027[)27/1(]575241[LmLL 3 13133 2 12122 −−= −⋅−=⋅−= −= −⋅−=⋅−= 41 Método do Pivoteamento Parcial Exemplo 10: A matriz ampliada fica da forma: Usando o elemento 87.687.6 como pivô, temse: −− − − 715.166.870 521.5207.00 134311027 − −− − 521.5207.00 715.166.870 134311027 ]56.5208.5200[L ]715.166.870[)6.87/07.0(]521.5207.00[LmLL 3 23233 = −−⋅−−=⋅−= 42 Método do Pivoteamento Parcial Exemplo 10: A matriz ampliada fica na forma: −− − 56.5208.5200 715.166.870 134311027 43 Método do Pivoteamento Parcial Exemplo 10: A solução do sistema triangular que resultou dessas operações é: Solução muito próximamuito próxima da exata. x3 = 52.08/52.56 = 0.991 x2 = [7116.5⋅0,991]/(87.6) = 0.997 x1 = [134 – (3)⋅0,991 – 110⋅0.997]/27 = 1.011 44 Método de Jordan Consiste em efetuar operações sobre as equações do sistema, com a finalidade de obter um sistema diagonal equivalente; Um sistema diagonal é aquele em que os elementos aaijij da matriz coeficiente [A] são iguais a zero, para ii≠j≠j, i, j = 1,2,...,n. 45 Método de Jordan Sistema diagonal equivalente: = nn n333 n222 n111 a000 aa00 a0a0 a00a ]A[ 46 Método de Jordan Exemplo 11: A partir do sistema: Com matriz aumentada: 4x2x3x2 2x3x2x5 1xx5x 321 321 321 =++ =++ =++ [ ] = = 4232 1151 1325 4232 2325 1151 Ab 47 Método de Jordan Exemplo 11: Substituindo a linha 2 por: Substituindo a linha 3 por : [ ] [ ] [ ]8.04.06.40L 2.05/1 a am,1325)5/1(1151LmLL 2 11 212112122 = ===⋅−=⋅−= [ ] [ ] [ ]6.38.02.20L 4.05/2 a am,1325)5/2(4232LmLL 3 11 31 3113133 = ===⋅−=⋅−= 48 Método de Jordan Exemplo 11: A matriz ampliada resulta em: Substituindo a linha 3 por: [ ] = 6.38.02.20 8.04.06.40 1325 Ab [ ] [ ] [ ]217.3609.000L 478.06.4/2.2 a am,8.04.06.40)6.4/2.2(6.38.02.20LmLL 3 22 32 3223233 = ===⋅−=⋅−= 49 Método de Jordan Exemplo 11: A matriz ampliada resulta em: Substituindo a linha 2 por [ ] = 478.0609.000 8.04.06.40 1325 Ab [ ] [ ] [ ]3141.106.40L 217.3609.000)609.0/4.0(8.04.06.40LmLL 2 32322 −= ⋅−=⋅−= 50 Método de Jordan Exemplo 11: Matriz ampliada resulta em: Substituindo a linha 1 por [ ] −= 478.0609.000 314.106.40 1325 Ab [ ] [ ] [ ]5714.1305L 6.4/2 a am,314.106.40)6.4/2(1325L 1 22 12 121 = ==−⋅−= 51 Método de Jordan Exemplo 11: Substituindo a linha 1 por: A matriz ampliada fica da seguinte forma: [ ] [ ] [ ]277.14005L 609.0/3 a am,478.0609.000)609.0/3(5714.1305L 1 33 13 131 −= ==⋅−= [ ] − − = 478.0609.000 314.106.40 277.14005 Ab 52 Método de Jordan Exemplo 11: E as soluções são: x1 =0.78 , x2= 0.28, x3=2.85x1 =0.78 , x2= 0.28, x3=2.85 53 Decomposição em LU O objetivo é fatorar a matriz dos coeficientes AA em um produto de duas matrizes LL e UU. Seja: [ ] ⋅ = nn n333 n22322 n1131211 nn3n2n1n 3231 21 u000 uu00 uuu0 uuuu mmmm 0 01mm 001m 0001 LU 54 Decomposição em LU E a matriz coeficiente A: Têmse: = nn3n2n1n n22221 n11211 aaaa aaa aaa A [ ] ⋅ == = nn n333 n22322 n1131211 nn3n2n1n 3231 21 nn3n2n1n n22221 n11211 u000 uu00 uuu0 uuuu mmmm 0 01mm 001m 0001 ]LU[ aaaa aaa aaa A 55 Decomposição em LU Para se obter os elementos da matriz LL e da matriz UU, devese calcular os elementos das linhas de UU e os elementos da colunas de LL como segue. 56 Decomposição em LU 1ª linha de U: Fazese o produtoproduto da 1ª 1ª linha de LL por todas todas as colunas de U U e a iguala com todos os elementos da 1ª1ª linha de AA, assim: == =⇒=⋅ =⇒=⋅ =⇒=⋅ .n,...,2,1j,au ,auau1 ,auau1 ,auau1 j1j1 n1n1n1n1 12121212 11111111 57 Decomposição em LU 1ª coluna de L: Fazse o produto de todas as linhas de L, (da 2ª 2ª a até a nª nª),), pela 1ª coluna de U e a iguala com os elementos da 1ª coluna de A, (abaixo da diagonal abaixo da diagonal principalprincipal), obtendo , == =⇒=⋅ =⇒=⋅ =⇒=⋅ .n,...,2,1l, u am , u amaum , u amaum , u amaum 11 1l1l 11 1l 1l1l111l 11 31 31311131 11 2121211121 58 Decomposição em LU 2ª linha de U: Fazse o produto da 2ª linha de L por todas as colunas de U, (da 2ª 2ª até a nªnª), e igualando com os elementos da 2ª linha de A, (da diagonal principal em da diagonal principal em diantediante), obtêmse , =⋅−= ⋅−=⇒=+⋅ ⋅−=⇒=+⋅ ⋅−=⇒=+⋅ .n,...,3j,umau ,umauauum ,umauauum ,umauauum j121j2j2 n121n2n2n2n2n121 1321232323231321 1221222222221221 59 Decomposição em LU 2ª coluna de L: Fazse o produto de todas as linhas de L (da 3ª 3ª até a nª nª) pela 2ª coluna de U e a iguala com os elementos da 2ª coluna de A, (abaixo da diagonal principalabaixo da diagonal principal), obtendo , = ⋅− = ⋅− =⇒=⋅+⋅ ⋅− =⇒=⋅+⋅ ⋅− =⇒=⋅+⋅ .n,...,3l, u umam , u umamaumum , u umamaumum , u umamaumum 22 121l2l 2l 22 121l2l 2l2l222l121l 22 124142 424222421241 22 123132 323222321231 60 Decomposição em LU Temos a seguinte fórmula geral: >⋅−= ≤⋅−= ∑ ∑ − = .jl,u/)uma(m ,jl,umau jjkjlkljlj 1l 1k kjlkljlj 61 Decomposição em LU Resumo de Passos: Seja um sistema Ax = bAx = b de ordem n, ondeA satisfaz as condições da fatoração LU. Então, o sistema Ax = bAx = b pode ser escrito como: Lux = bLux = b 62 Decomposição em LU Resumo dos Passos: Fazendo Ux = yUx = y, a equação acima reduzse a Ly = bLy = b. Resolvendo o sistema triangular inferior Ly Ly = b= b, obtémse o vetor yy. 63 Decomposição em LU Resumo dos Passos: Substituição do valor de yy no sistema Ux Ux = y= y ⇒ Obtenção de um sistema triangular superior cuja solução é o vetor xx procurado; Aplicação da fatoração LU na resolução de sistemas lineares ⇒ Necessidade de solução de dois sistemas triangulares 64 Erros Avaliação de Erros No sistema AA⋅⋅x = bx = b , onde: o erro da soluçãoerro da solução é x – x’x – x’ . = = = n 2 1 n 2 1 nn2n1n n22221 n11211 b b b ]b[ a a a ]x[ aaa aaa aaa ]A[ 65 Procedimento de Determinação do Erro Determinar: AA⋅⋅x’ = b’x’ = b’ Erros Avaliação de Erros 66 Erros – Resíduo Procedimento de Determinação do Erro Fazer: Resíduo Resíduo = b – b’ Resíduo =Resíduo = b – b’ = A⋅x A⋅x’ = A⋅(x – x’) = AA⋅⋅erroerro 67 Erros – Resíduo Verificase que: O resíduo nãonão é o erro, apenasapenas uma estimativa do mesmo; Quanto menormenor for o resíduo, menormenor será o erro. 68 Exemplo 12: Refinar a solução do sistema: Cuja solução encontrada através pelo método de Gauss, utilizando a solução retroativa é: −=+−− −=+−− −=−+− =+++ 3,106x5,21x2,13x0,81x0,21 8,80x4,11x5,23x8,8x3,53 7,49x1,45x5,11x8,8x5,24 4,16x0,11x3,9x0,3x7,8 4321 4321 4321 4321 ]´00,197,098,197,0[x )0( −= Erros – Resíduo 69 Exemplo 12: O resíduo calculado é: Vêse pelo resíduo que a precisão alcançada não foi satisfatória. O vetor xx(0)(0) é chamado de vetor soluçãovetor solução. − =−= 594,0 594,0 214,0 042,0 Axbr )0()0( Erros – Resíduo 70 Exemplo 12: Com o intuito de melhorar a solução, considerase um novo vetor xx(1)(1) chamado de vetor solução melhoradovetor solução melhorado. Erros – Resíduo 71 Exemplo 12: De forma que : xx(1) = (1) = xx(1) + (1) + δδ(0)(0), onde δ(0) é o vetor de correçãovetor de correção. Assim: )0()0( )0()0( )0()0( )0()0( )1( rA AxbA bAAx b)x(A bAx =δ −=δ =δ+ =δ+ = Erros – Resíduo 72 Exemplo 12: Calcular o vetor de correção: − = δ δ δ δ −− −− −− 594,0 594,0 214,0 042,0 5,212,130,810,21 4,115,238,83,53 1,455,118,85,24 0,113,90,37,8 4 3 2 1 Erros – Resíduo 73 Exemplo 12: A solução é: − =δ 0000,0 0294,0 0195,0 0295,0 )0( Erros – Resíduo 74 Exemplo 12: Desta forma, a solução melhorada será: − =δ+= 0000,1 9999,0 0000,2 0000,1 xx )0()0()1( Erros – Resíduo 75 Exemplo 12: Cujo novo resíduo é: − − =−= 013,0 024,0 011,0 009,0 Axbr )1()1( Erros – Resíduo 76 Exemplo 12: Utilizando o mesmo procedimento, têmse que: xx(2)(2)=x=x(1)(1)++δδ(1)(1) Assim, o vetor correção, calculado por A A δδ(1)(1)=r=r(1)(1), é: − − − =δ 0000,0 0007,0 0002,0 0002,0 )1( Erros – Resíduo 77 Exemplo 12: Achase assim uma solução melhorada: − = 0000,1 0000,1 0000,2 0000,1 x )2( Erros – Resíduo 78 Exemplo 12: Que possui resíduo: = 0 0 0 0 r )2( Erros – Resíduo 79 Sistemas Lineares Bibliografia Ruggiero, M. A. Gomes & Lopes, V. L. da R. Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo Cálculo Numérico: Aspectos teóricos e computacionaisNumérico: Aspectos teóricos e computacionais. . MAKRON Books, 1996, 2MAKRON Books, 1996, 2ªª ed. ed. Asano, C. H. & Colli, E. Asano, C. H. & Colli, E. Cálculo Numérico: Cálculo Numérico: Fundamentos e AplicaçõesFundamentos e Aplicações. Departamento de . Departamento de Matemática Aplicada – IME/USP, 2007.Matemática Aplicada – IME/USP, 2007. Sanches, I. J. & Furlan, D. C. Sanches, I. J. & Furlan, D. C. Métodos NuméricosMétodos Numéricos. . DI/UFPR, 2006.DI/UFPR, 2006. Paulino, C. D. & Soares, C. Erros e Propagação de Paulino, C. D. & Soares, C. Erros e Propagação de Erros, Erros, Notas de aulaNotas de aula, SE/ DM/ IST [Online] , SE/ DM/ IST [Online] http://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_20http://www.math.ist.utl.pt/stat/pe/qeb/semestre_1_20 042005/PE_erros.pdf042005/PE_erros.pdf [Último acesso 07 de Junho de [Último acesso 07 de Junho de 2007].2007].
Compartilhar