Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIDADE 3 – SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES LINEARES Introdução Vários problemas como o cálculo de estruturas de redes elétricas, cálculos genéticos, custos de produção e soluções de equações diferenciais recorrem a resolução numérica de um sistema linear. O objetivo desta unidade é a utilização de algoritmos computacionais para calcular a solução única de sistemas de equações lineares através de métodos diretos (decomposição e eliminação) e métodos iterativos. Sistemas de Equações Lineares Um sistema de equações lineares é uma equação do tipo: Ax b Que pode ser representado nas formas: Algébrica: 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b Matriz Completa: 11 12 1 1 21 22 2 2 1 2 n n n n nn n a a a b a a a b a a a b Matricial: 11 12 1 1 1 21 22 2 2 2 1 2 . n n n nn n nn a a a x b a a a x b x ba a a Resolver um sistema consiste em determinar o vetor: 1 2( , , , ) T nx x x x que satisfaça todas as equações simultaneamente. Métodos Diretos São caracterizados por fornecer a solução exata para o sistema dado, não fossem os erros provenientes do processamento do algoritmo em um equipamento computacional. Sistema Triangular Inferior Considere Lx b um sistema de equações lineares onde a matriz dos coeficientes é triangular inferior, isto é, os seus coeficientes 0i jl sempre que i j e com 0iil , então: 11 1 1 21 1 22 2 2 1 1 2 2n n nn n n l x b l x l x b l x l x l x b O vetor solução deste sistema pode ser obtido tomando-se: 1 11 1 1 1 11 b l x b x l 2 21 121 1 22 2 2 2 2 2 21 1 22 22 22 1b l x l x l x b x x b l x l l l 1 1 2 2 3 3 1 1 1 1 2 2 3 3 1 1 1 i i i i i i i i i i i i i i i i i i i i b l x l x l x l x l x l x l x l x l x b x l ou na forma compacta: ( 1) 1 1 i i i i j j ji i x b l x l Algoritmo 1 1 11 b x l Para i = 2, ... , n faça ( 1) 1 1 i i i i j j ji i x b l x l Sistema Triangular Superior Considere Ux b um sistema de equações lineares onde a matriz dos coeficientes é triangular superior, isto é, os seus coeficientes 0iiu sempre que i j e com 0iiu , então: 11 1 12 2 1 1 22 2 2 2 n n n n nn n n u x u x u x b u x u x b u x b O vetor solução para este sistema é obtido fazendo-se: n nn n n n nn b u x b x l 1 1 2 2ii i ii i ii i in n iu x u x l x u x b Na forma compacta: ( 1) 1 n i i i j j j ii i x b u x u Algoritmo n n nn b x u Para ( 1),( 2), ,1i n n faça ( 1) 1 n i i i j j j ii i x b u x u Método de Decomposição LU Como observado, sistemas de equações lineares cuja matriz dos coeficientes possui a característica triangular superior ou inferior apresentam um esforço computacional menor para a obtenção de sua solução. Este fato nos motiva a buscar formas para que um sistema de equações lineares Ax b possa ser resolvido através da solução de sistemas com características triangulares permitindo, assim, a utilização dos algoritmos. Para utilizarmos estes algoritmos devemos inicialmente verificar se a matriz não é singular, e para isto, definimos os “menores principais” da matriz dos coeficientes. Definição: denomina-se “menores principais” de ordem k de uma matriz ( ) , 1,...,i jA a i j n por: det( )k kA Onde ( ) , 1,...,k iiA a i j k , k é formado pelas primeiras linhas e k primeiras colunas da matriz A. Processo de decomposição Teorema: seja A uma matriz quadrada de ordem n, se os menores principais de A, 0 1,2,..., 1i i n , então A se decompõe, de maneira única no produto de uma matriz triangular inferior ( ) , 1,...,i jL l i j n , com 1iil , por uma matriz triangular superior ( ) , 1,...,i jU u i j n . Além disso, det( ) det( )A U . Considerando o enunciado do teorema podemos montar a relação: 11 12 13 1 11 12 1 22 23 2 21 22 221 31 32 33 3 31 32 3 1 2 3 1 2 1 1 1 . 1 n n n n n n n n n nn n n nn u u u u a a a u u u a a al l l u u a a a l l l u a a a Para construção do algoritmo, construímos a matriz U por linhas e a matriz L por colunas, isto é: Cálculo da primeira linha de U: Cálculo da primeira coluna de L: 11 11 11 111u a u a 21 21 11 21 21 11 a l u a l u 12 12 12 121u a u a 31 31 11 31 31 11 a l u a l u 1 1 1 11 n n n nu a u a 1 1 1 1 1 11 n n n n n a l u a l u Se continuarmos os cálculos para as colunas e linhas, obteremos as seguintes fórmulas gerais para os elementos das matrizes L e U: Matriz U 1 1 i i j i j i k k j k u a l u para , 1,..., ,i j n i j Matriz L 1 1 1 j i j i j i k k j kj j l a l u u para , 1,..., ,i j n i j Algoritmo Para 1,..., 1,m n faça Para , 1,..., ,j m m n faça 1 1 m m j m j mk k j k u a l u Para 1,..., ,i m n 1 1 1 m i m im ik k m km m l a l u u 1mml Para m n faça 1 1 n mm nn nk k n k u a l u 1nnl ------------------------------------------------------------------------------------------------------------------- Considerando um sistema de equações lineares Ax b , cuja matriz dos coeficientes A satisfaz a condição A LU , podemos escrever o sistema de equações como: LU x b Se denominarmos Ux y , teremos substituído o cálculo da solução do sistema Ax b , pela solução de dois sistemas triangulares: um inferior Ly b e outro superior Ux y . Resumo do método 1º - Verifica-se o teorema dos menores principais; 2º - Decompõe-se a matriz utilizando o algoritmo de decomposição LU; 3º - Resolve-se o sistema Ly b , aplicando-se o algoritmo de resolução de sistema triangular inferior na matriz L, obtendo o vetor solução y; 4º - Resolve-se o sistema Ux y , aplicando-se o algoritmo de resolução de sistema triangular superior na matriz U, obtendo o vetor solução x; Exemplo Usando o método de decomposição LU, resolva o seguinte sistema de equações lineares. 1 2 3 3 2 4 1 1 1 2 . 2 4 3 2 3 x x x Solução 1º) Para resolvermos este problema, devemos calcular os menores principais, det( )k kA , da matriz dos coeficientes.Então, Tomando-se 1k , temos: 1 3 0 Tomando-se 2k , temos: 2 3 2 3 2 1 0 1 1 . Como os menores principais são diferentes de zero, podemos aplicar o teorema e transformar a matriz A em um produto LU. 2º) Devemos construir as matrizes L e U utilizando o algoritmo de decomposição. Temos que 1,2,3m ; 1,2,3j e 2,3i . Inicio Quando 1m 1j 11 11 11 11 110 3u a u a u 2j 12 12 12 12 120 2u a u a u 3j 13 13 13 13 130 4u a u a u 2i 21 21 21 21 21 11 11 0 1 3 a a l l l u u 3i 31 31 31 31 31 11 11 0 4 3 a a l l l u u 11 1l Quando 2m 2j 22 22 21 12 22 22 1 1 1 (2) 3 3 u a l u u u 3j 23 23 21 13 23 23 1 2 2 (4) 3 3 u a l u u u 3i 32 31 12 32 32 32 22 4 3 (2) 3 1 1 3 a l u l l l u 22 1l Quando 3m n 33 33 31 13 32 23 33 33 4 2 2 (4) 1 8 3 3 u a l u l u u u 33 1l Fim Feita a decomposição utilizando o algoritmo, temos as seguintes matrizes: 1 0 0 1 1 0 3 4 1 1 3 L 3 2 4 1 2 0 3 3 0 0 8 U 3º) Devemos resolver o sistema triangular inferior do tipo, Ly b : 1 2 3 1 0 0 1 1 1 0 2 3 3 4 1 1 3 y Ly b y y . Utilizando o algoritmo para sistemas triangulares inferiores, temos: Inicio Quando 1i 1 1 1 11 1 b y y l Quando 2i 2 21 1 2 2 2 22 1 2 (1) 53 1 3 b l y y y y l Quando 3i 3 31 1 32 2 3 3 3 33 4 5 3 (1) (1) 3 3 0 1 b l y l y y y y l Fim Temos, portanto que o vetor solução y é dado por: 1 2 3 1 5 3 0 y y y 4º) Resolve-se o sistema Ux y , aplicando-se o algoritmo de resolução de sistema triangular superior na matriz U, obtendo o vetor solução x; 1 2 3 3 2 4 1 1 2 5 0 3 3 3 0 0 8 0 x Ux y x x Utilizando o algoritmo: Inicio Quando 3i 3 3 3 33 0 y x x u Quando 2i 2 23 3 2 2 2 22 5 0 3 5 1 3 y u x x x x u Quando 1i 1 12 2 13 3 1 1 1 11 1 2(5) 0 3 3 y u x u x x x x u Como a solução é fornecida pelo vetor x, temos que: ( 3,5,0)Tx Método de Cholesky O método consiste em transformar a matriz dos coeficientes A, no produto TA R R , onde R é uma matriz triangular superior, com diagonal positiva e TR sua transposta. Processe de decomposição Considere uma matriz A, devemos construir os elementos da matriz triangular superior R escrevendo o produto, TR R A , então: 11 12 13 1 11 12 111 22 23 2 21 22 221 22 31 32 33 33 3 31 32 3 1 2 3 1 2 . n n n n n n n n n nn nn n n nn r r r r a a ar r r r a a ar r r r r r r a a a r r r r r a a a A construção dos elementos da diagonal de R é dada por: 2 11 11 11 11 11 11 11r r a r a r a 2 2 2 2 2 12 12 22 22 22 12 22 22 22 22 12 22 22 12r r r r a r r a r a r r a r Generalizando, temos: 1/ 2 1 2 1 i i i i i k i k r a r , 1,2,...,i n Os elementos não pertencentes à diagonal de R podem ser construídos fazendo-se: Cálculo da primeira linha de R: Cálculo da primeira coluna de L: 12 11 12 12 12 11 a r r a r r 23 12 13 12 13 22 23 23 23 22 a r r r r r r a r r 13 11 13 13 13 11 a r r a r r 24 12 14 12 14 22 24 24 24 22 a r r r r r r a r r 1 11 1 1 1 11 n n n n a r r a r r 2 12 1 12 1 22 2 2 2 22 n n n n n n a r r r r r r a r r De forma geral, 1 1 1 i i j i j k i k j ki i r a r r r , 1,2,...,i n e 1,...,j i n Algoritmo Para 1,...,i n faça 1/ 2 1 2 1 i i i i i k i k r a r Para 1,...,j i n faça 1 1 1 i i j i j k i k j ki i r a r r r Se a matriz A satisfaz ás condições TR R A , e se tomarmos o sistema Ax b pode- se escrever: ( )TR R x b Se denominarmos Rx y , teremos substituído o cálculo da solução do sistema Ax b , pela solução de dois sistemas triangulares TR y b e Rx y . Resumo do método 1º - Verifica-se o teorema dos menores principais; 2º - Decompõe-se a matriz utilizando o algoritmo de decomposição de Cholesky; 3º - Resolve-se o sistema TR y b , aplicando-se o algoritmo de resolução de sistema triangular inferior na matriz TR , obtendo o vetor solução y; 4º - Resolve-se o sistema Rx y , aplicando-se o algoritmo de resolução de sistema triangular superior na matriz R, obtendo o vetor solução x;
Compartilhar