Solução Numérica de Sistemas de Equações: Decomposição Gaussiana e Métodos Iterativos

CÁLCULO NUMÉRICO Profa Dra Marina Vargas SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES Métodos diretos Decomposição gaussiana Eliminação gaussiana Métodos de fatoração LU e LDU Condicionamento Iterativos GaussJacobi GaussSeidel DECOMPOSIÇÃO GAUSSIANA Seja uma matriz 𝐴𝑚𝑥𝑛dada por 𝐴1 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑚 1 𝑎1𝑛 1 𝑎21 1 𝑎22 1 𝑎2𝑘 1 𝑎2𝑚 1 𝑎2𝑛 1 𝑎𝑘1 1 𝑎𝑘2 1 𝑎𝑘𝑘 1 𝑎𝑘𝑚 1 𝑎𝑘𝑛 1 𝑎𝑚1 1 𝑎𝑚2 1 𝑎𝑚𝑘 1 𝑎𝑚𝑚 1 𝑎𝑚𝑛 1 DECOMPOSIÇÃO GAUSSIANA 𝐴𝑘 uma matriz semelhante a 𝐴 1 já triangularizada 𝐴𝑘 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑚 1 𝑎1𝑛 1 0 𝑎22 2 𝑎2𝑘 2 𝑎2𝑚 2 𝑎2𝑛 2 0 0 𝑎𝑘𝑘 𝑘 𝑎𝑘𝑚 𝑘 𝑎𝑘𝑛 𝑘 0 0 𝑎𝑚𝑘 𝑘 𝑎𝑚𝑚 𝑘 𝑎𝑚𝑛 𝑘 DECOMPOSIÇÃO GAUSSIANA Note que 𝐴 2 𝑀1 𝐴 1 𝐴 𝑚 𝑀𝑚1 𝐴 𝑚1 Portanto precisamos de m1 passos para concluir a decomposição PASSO 1 Se 𝑎11 1 0 então 𝐴 𝐴1 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑚 1 𝑎1𝑛 1 𝑎21 1 𝑎22 1 𝑎2𝑘 1 𝑎2𝑚 1 𝑎2𝑛 1 𝑎𝑘1 1 𝑎𝑘2 1 𝑎𝑘𝑘 1 𝑎𝑘𝑚 1 𝑎𝑘𝑛 1 𝑎𝑚1 1 𝑎𝑚2 1 𝑎𝑚𝑘 1 𝑎𝑚𝑚 1 𝑎𝑚𝑛 1 Existe uma matriz 𝑀1 𝑚𝑥𝑚 tal que 𝑀1 1 𝑎21 1 𝑎11 1 1 1 1 1 𝑎𝑚1 1 𝑎11 1 1 com 𝑚21 𝑎21 1 𝑎11 1 𝑚31 𝑎31 1 𝑎11 1 𝑚𝑚1 𝑎𝑚1 1 𝑎11 1 tal que 𝐴 2 𝑀1 𝐴 1 𝐴2 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑚 1 𝑎1𝑛 1 0 𝑎22 2 𝑎2𝑘 2 𝑎2𝑚 2 𝑎2𝑛 2 0 𝑎𝑘2 2 𝑎𝑘𝑘 2 𝑎𝑘𝑚 2 𝑎𝑘𝑛 2 0 𝑎𝑚2 2 𝑎𝑚𝑘 2 𝑎𝑚𝑚 2 𝑎𝑚𝑛 2 PASSO 2 𝒂𝟐𝟐 𝟐 𝟎 Existe uma matriz 𝑀2 𝑚𝑥𝑚 tal que 𝐴 3 𝑀2 𝐴 2 𝑀2𝑀1𝐴 1 𝑀2 1 1 𝑎32 2 𝑎22 2 1 𝑎42 2 𝑎22 2 1 1 𝑎𝑚2 2 𝑎22 2 1 com 𝑚32 𝑎32 2 𝑎22 2 𝑚42 𝑎42 2 𝑎22 2 𝑚𝑚2 𝑎𝑚2 2 𝑎22 2 𝐴3 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑚 1 𝑎1𝑛 1 0 𝑎22 2 𝑎2𝑘 2 𝑎2𝑚 2 𝑎2𝑛 2 0 0 𝑎𝑘𝑘 3 𝑎𝑘𝑚 3 𝑎𝑘𝑛 3 0 0 𝑎𝑚𝑘 3 𝑎𝑚𝑚 3 𝑎𝑚𝑛 3 PASSO k 𝒂𝒌𝒌 𝒌 𝟎 𝐴𝑘1 𝑎11 1 𝑎12 1 𝑎1𝑘 1 𝑎1𝑛 1 0 𝑎22 2 𝑎2𝑘 2 𝑎2𝑛 2 𝑎𝑘𝑘 𝑘 𝑎𝑘𝑛 𝑘 0 0 0 0 𝑎𝑘1𝑘1 𝑘1 𝑎𝑘1𝑛 𝑘1 0 0 0 0 0 0 𝑎𝑚𝑘1 𝑘1 𝑎𝑚𝑛 𝑘1 O processo deve ser seguido até o passo 𝑟 onde 𝑟 min𝑚 1 𝑛 Portanto 𝐴𝑘1 𝑀𝑘𝐴𝑘 𝑀𝑘𝑀𝑘1 𝑀1𝐴1 EXEMPLO Seja 𝐴 2 4 2 1 1 5 4 1 2 A decomposição de Gauss ocorrerá em 𝑟 min23 2 passos PASSO 1 𝑎11 0 𝑀1 1 0 0 1 2 1 0 4 2 0 1 𝐴2 𝑀1𝐴1 1 0 0 1 2 1 0 4 2 0 1 2 4 2 1 1 5 4 1 2 2 4 2 0 3 6 0 7 2 PASSO 2 𝑎22 0 𝑀2 1 0 0 0 1 0 0 7 3 1 𝐴3 𝑀2𝐴2 1 0 0 0 1 0 0 7 3 1 2 4 2 0 3 6 0 7 2 2 4 2 0 3 6 0 0 12 Os elementos 𝐚𝐤𝐤 𝐤 são os elementos pivôs ELIMINAÇÃO GAUSSIANA Uma matriz elementar triangular inferior de ordem n e índice k pode ser escrita como M In mek T onde ei T m 0 para i 1 k e m m1 m2 mn é ortogonal a todos os vetores canônicos 𝑒1 𝑒2 𝑒𝑘 ELIMINAÇÃO GAUSSIANA Então 1 0 0 m1 m2 mn 0 m1 0 0 1 0 m1 m2 mn 0 m2 0 0 1 posição k 0 m1 m2 mn 0 mk 0 ELIMINAÇÃO GAUSSIANA M 1 1 1 0 0 0 mk1 mn 0 1 posição k 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 mk1 0 0 mn coluna k 0 M 1 0 0 0 0 0 0 1 0 0 0 mk1 0 0 mn 1 Resultado 1 Se M In m ek T então M1 In m ek T ELIMINAÇÃO GAUSSIANA Ak1 In mkek T 𝑀𝑘 Ak Ak1 Ak 0 0 mk1k mmk 0 0 akk k akn k Ak1 Ak 0 0 0 0 0 0 0 0 0kk 0 0 0 0 mk1kakk k mk1kakn k 0 0 0 0 mmkakk k mmkakk kakn k PIVOTEAMENTO COMPLETO Seja a matriz 𝐴 𝑘 da forma Ak akk k alkck k Caso o pivô akk k 0 e os demais ak1k k amk k forem diferentes de zero então podemos realizar o chamado pivoteamento completo A troca de linhas equivale a realizar uma prémultiplicação da matriz como se segue Iklk Ak A k Já a troca entre as colunas kk por ck pode ser calculada através de uma pós multiplicação calculada por A k Ikck 𝐴 𝑘 PIVOTEAMENTO COMPLETO PIVOTEAMENTO COMPLETO Seja a matriz 𝐴 𝑘 da forma Ak akk k alkck k 𝐴 𝑘1 𝑀𝑘 𝑃𝑘 𝐴 𝑘 𝑄𝑘 EXEMPLO Seja A 1 2 3 4 5 6 7 8 9 então P23 1 0 0 0 0 1 0 1 0 Assim P23A 1 0 0 0 0 1 0 1 0 1 2 3 4 5 6 7 8 9 1 2 3 7 8 9 4 5 6 EXEMPLO Considerando Q23 1 0 0 0 0 1 0 1 0 escrevemos AQ23 1 2 3 4 5 6 7 8 9 1 0 0 0 0 1 0 1 0 1 3 2 4 6 5 7 9 8 REFERÊNCIAS JUSTO D A R SAUTER E AZEVEDO F S GUIDI L F KONZEN P H A REAMAT Cálculo numérico Disponível em httpswwwufrgsbrreamatCalculoNumericolivroscimainhtml Acesso em 09 de mai de 2021 CHAPRA S C CANALE R P Métodos numéricos para engenharia 7 ed Porto Alegre AMGH 2016 DORNELLES FILHO A A Fundamentos de Cálculo numérico São Paulo Bookman 2016 BURDEN R L FAIRES J D Análise numérica São Paulo Cengage Learning 2015 FILHO C FF Algoritmos Numéricos Uma Abordagem Moderna de Cálculo Numérico 3ª edição Rio de Janeiro LTC 2018 Muito obrigada Profa Dra Marina Vargas