Baixe o app para aproveitar ainda mais
Prévia do material em texto
UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 44 Unidade IV - Sistemas Lineares IV.1 - Introdução O Problema que aparece no cálculo de estruturas, em redes elétricas, e em solução de equações diferenciais é o da resolução de um sistema linear de “ n ” equações a “ n ” incógnitas. Sn é um sistema tal que: S a x x x a x x x a x x x n n n n n n nn n 11 1 12 2 21 1 2 2 1 1 2 2 a + a = b a + a = b + a + a = b 1n 1 22 2 n S an j n i j j x (1 i n) 1 Sob a forma matricial Sn pode ser escrito como A x = b, onde A é uma matriz de ordem “ n ” , b e x são matrizes n 1. A matriz B = a a a b a a a b a a a b n n n n nn n 11 21 1 1 21 22 2 2 1 2 é chamada de matriz estendida do sistema Sn . Definição: O vetor x = ( x 1 , x 2 , ... , x n ) t constitui uma solução para Sn se para xi = x i (1 i n) as equações de Sn forem satisfeitas. Um sistema linear pode ser classificado do seguinte modo: 1. Compatível (quando possuí solução): a. Determinado (única solução) b. Indeterminado (infinitas soluções) 2. Incompatível (quando NÃO possuí solução) Exemplos: 1) O sistema Ax = 0 é homogêneo e todo sistema homogêneo é compatível, pois admite pelo a solução trivial. 2) O sistema S2 = x x x x 1 2 1 2 0 1 é incompatível. Geometricamente temos: x 2 x1 + x2 = 0 x 1 x1 + x2 = 1 As retas são paralelas UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 45 3) O sistema S2 = x x x x 1 2 1 2 0 0 O sistema é incompatível e determinado. Geometricamente temos: x 2 x1 - x2 = 0 x 1 x1 + x2 = 0 4) O sistema S2 = x x1 2 1 2 0 2 2 0 x x é incompatível indeterminado. Geometricamente temos: x 2 x 1 Retas Coincidentes x1 + x2 = 0 2x1 + 2x2 = 0 UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 46 IV.1.1 - Sistemas triangulares Seja Sn um sistema da forma Ax = b, onde A = ai j tal que: aij 0 se j < i com i, j = 1, n ou: S a a n 22 nn a x a x a x b x a x b x b n n n n n n 11 1 12 2 1 1 2 2 2 ... ... Um sistema deste tipo é dito triangular superior. Observe que os sistemas triangulares superiores determinados, isto é, quando a i j 0 (i, j = 1,n) são facilmente resolvidos pelo processo retroativo, que consiste em: a) Obter o valor de xn da n-ésima equação por meio da relação: xn = b a n nn (ann 0) b) Substituir o valor de xn na equação de ordem (n-1) para obter xn - 1 . E assim sucessivamente, até calcular x1 . Se algum elemento da diagonal principal for zero, teremos a situação: ax , se:1 b a xij j j i n 1 1 b a xij j j i n 1 1 sistema indeterminado b1 a xij j j i n 1 sistema incompatível Exemplo: Resolver o S4 pelo processo retroativo: S x x - 2x 4x - 5x 2 4 4 3 4 3 4 5 10 1 3 2 1 2 3 4 2 3 4 x x x x x Solução: Da 4 a . equação vem: x4 2 2 1 Da 3 a . equação vem: x3 3 5 4 2 Da 2 a . equação vem: x2 1 2 2 1 1 Da 1 a . equação vem: x1 10 4 10 1 3 1 Resposta : x = (1 -1 2 1) UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 47 IV.1.2 - Norma de um vetor Norma de um vetor x = (x1 , x2 , x3 ,..., xn) é todo número real denotado por || ||, associado a x, que satisfaz a: || x || > 0 e || x || = 0 x = 0 || x + y || || x || + || y || onde x, y rn || c · x || = | c | · || x || onde c r Definição 1: A maior componente em módulo do vetor x é uma norma para x. || x || = máx | xi | onde 1 i n x = (3 – 50) x + y = (5 – 4 3 ) x = 5 x + y = 5 ... x + y = 8 y = (2 1 3) y = 3 Seja c = -2 c · x = (-6 10 0) || c x || = 10 = | c | · || x || Definição 2: O | |xi i n 1 também é uma norma para o vetor x. É conhecida como norma c. IV.1.3 - Transformações elementares São operações sobre as equações dos sistemas lineares, tais como: a) Trocar a ordem de duas equações do sistema; b) Multiplicar uma equação do sistema por uma constante não nula; c) Adicionar duas equações do sistema. Definição : Dois sistemas lineares Sn e Sn’ são equivalentes quando Sn’ é obtido de Sn por meio de transformações elementares. Nesse caso, Sn tendo solução, Sn’ também terá. Os métodos para resolução de sistemas lineares são: I - Métodos de eliminação. II - Métodos iterativos. IV.2 - Método de eliminação de Gauss Dado o sistema Sn , a matriz estendida é: B a a a b a a a b a a a b n n n n nn n 11 12 1 1 21 22 2 2 1 2 O método de Gauss consiste em transformar a matriz B em uma matriz triangular superior, da seguinte forma: 1 0 1 0 0 1 0 0 0 1 12 1 13 1 1 1 1 1 23 2 2 2 2 2 3 3 3 3 a a a b a a b a b b n n n n n ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) , onde os índices superiores indicam o número de modificações realizadas em cada linha. UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 48 Aplica-se o processo retroativo para se obter a solução desejada. Algoritmo do método: Eliminação de ordem k: Supondo akk ( k - 1) 0, dividir a linha lk ( k -1) por akk ( k - 1) (“pivô”), obtendo-se assim uma nova linha lk ( k ) . “Zerar” os elementos aik (i = i +1, n) usando-se a transformação: li (k) = li (k - 1) - ai k · lk (k) , com (k = i +1, n) e (i = 2, n) . IV.2.1 - Condensação pivotal parcial Os métodos de eliminação são exatos, mas podem conduzir a soluções errôneas devido ao erro de arredondamento. Para evitar isto, usaremos a condensação pivotal parcial, cujo procedimento é redispor as linhas de tal forma que a linha do elemento pivô permaneça fixa e que o elemento pivô seja escolhido dentre os elementos da coluna que tem o maior valor absoluto. A finalidade da condensação pivotal parcial é: Minimizar o erro de arredondamento. Evitar a divisão por zero. Testar a singularidade do sistema. Exemplo: Resolver o sistema S x x x x x x x x x 3 1 2 3 1 2 3 1 2 3 2 3 40 39 36 106 7 63 25 5 12 32 + pelo método de eliminação de Gauss com condensação pivotal parcial. Solução: 2 3 40 39 36 106 7 63 25 5 12 32 36 106 7 63 2 3 40 39 25 5 12 32 36 2 25 1 2 94 019 1 75 0 2 88 39 62 42 5 0 68 5 7 25 75 5 1 1 1 2 1 2 1 1 3 1 3 1 1 CPP L L L L L L L L ( ) ( ) ( ) ( ) ( ) / , , , , , , , , , CPP L L L L L 1 2 94 0 19 1 75 0 68 5 7 25 75 75 0 2 88 39 62 42 5 68 5 2 88 1 2 94 0 19 1 75 0 1 0 106 1106 0 0 39 315 39 315 2 2 2 1 3 2 3 1 2 2 , , , , , , , , , / ( , ) , , , , , , , , ( ) ( ) ( ) ( ) ( ) L L3 3 3 1 39 315 1 2 94 019 1 75 0 1 0 106 1106 0 0 1 1 ( ) ( ) / , , , , , , Pelo Processo Retroativo: x3 = 1 x2 = - 1,106 + 0,106 = -1 x1 = -1,75 - 0,19 + 2,94 = 1 Resp.: x = (1 -1 1) t IV.3 - Métodos Iterativos A solução x de um sistema linear AX = B pode ser obtida utilizando-se um método iterativo, que consiste em gerar uma seqüência de soluções x (1) , x (2) , x (3) , ..., x (k) , aproximações de x , sendo dada uma aproximação inicial x (0) . UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 49 Para se aplicar o método é necessário transformar o sistema dado em: x = F (x) + d , onde: * F é uma matriz de ordem n, chamada de matriz iteração; * x, d são matrizes n 1 Sendo x (0) = (x1 (0) , x2 (0) , ..., xn (0) ) a aproximação inicial, determinamos: x Fx d x Fx d x Fx d x Fx dk k (1) ( ) ( ) (1) ( ) ( ) ( ) ( ) 0 2 3 2 1 O critério de parada é dado por lim ( ) k kx x 0 . Neste caso, temos x (k) como solução aproximada. Obs.: x x má x x xk i k i ( ) ( ) 1 i n IV.3.1 - Método de Jacobi Considere o sistema: S a x a x a x b a x a x a x b a x a x a x b n n n n n n n nn n n 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 ... ... ... Explicitemos x1 na 1ª equação x2 na 2ª equação x n na n-ésima equação Daí resulta: x )( 1 k = 1 (b1 – a12 x2 – a13 x )1( k x - ... – a1n x )1( k n a 11 x )( 2 k = 1 (b2 – a21 x )1( 1 k – a23 x )1( k x - ... – a2n x )1( k n É necessário que aii 0 (i = 1,n). a 22 . . . xn (k) = 1 (bn– an1 x )1( 1 k – an2 x2 (k-1) - ... – an n-1 x )1( 1 k n a nn Desse modo, podemos escrever o sistema da forma x = F x + d. x = (x1 , x2, ..., xn ) t UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 50 F a a a a a a a a a a a a a a a a a a n n n nn n nn n nn 0 0 0 12 11 13 11 1 11 21 22 23 22 2 22 1 2 3 d b a b a b a n nn t 1 11 2 22 O método de Jacobi consiste em: partindo-se da aproximação inicial x(0) gera-se a seqüência de aproximações x(1), x(2), ..., x(k) como critério de parada, utilizamos x xk k( ) ( ) 1 , onde = precisão desejada para raiz. Exemplo: Resolver o sistema: S x x x x 2 1 2 1 2 2 1 2 3 pelo método de Jacobi, com 2 casas decimais exatas. Solução: Equações de iteração: x x x x X k k k k 1 2 1 2 1 1 0 1 2 1 1 2 3 0 9 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( , 0,9) 1ª. Iteração x )1( 1 = ½ (1+0,9) = 0,95 x )1( 2 = ½ (3- 0,9) = 1,05 x(1) – x(0) = 0,95 – 0,9) (1,05 – 0,9) = (0,5) (0,15) = 0,15 > 10-3 2ª. Iteração x )2( 1 = ½ (1+1,05) = 1,025 x )2( 2 = ½ (3 – 0,95) = 1,025 x(2) – x(1) = 0,075 > 10-3 3ª.Iteração x )3( 1 = ½ (1+ 1,025) = 1,0125 x )3( 2 = ½ (3 – 1,025) = 0,9875 x3 – x2 = 0,0375 > 10-3 UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 51 4ª. Iteração x1 (4) = ½ (1+ 0,9875) = 0,99375 x2 (4) = ½ (3 – 0,9875) = 0,99375 x4 – x3 = 0,01875 > 10-3 5ª. Iteração x1 (5) = ½ (1+ 0,99375) = 0,996875 x2 (5) = ½ (3 – 0,99375) = 1,003125 x(5) – x(4) = 0,009375 > 10-3 6ª. Iteração x1 (6) = ½ (1+ 1,003125) = 1,0015625 x2 (6) = ½ ( 3 – 0,996875) = 1,0015625 x(6) – x(5) = 0,0046875 > 10-3 7ª. Iteração x1 (7) = ½ (1 + 1, 003125) = 1,00078125 x2 (7) = ½ (3 – 0.996875) = 0,99921875 x(7) – x(6) = 0,00234375 > 10-3 8ª. Iteração x1 (8) = ½ (1 + 0,99921875) = 0,99960938 x2 (8) = ½ (3 – 1,00078125) = 0,99960938 x(8) – x(7) = 0,00117187 > 10-3 9ª. Iteração x1 (9) = ½ (1 + 0,99960938) = 0,99980469 x2 (9) = ½ (3 – 0,99960938) = 1,00019531 x(9) – x(8) = 0,00058593 < 10-3 Resp: x = ( 0,99 1,00) t (0,01 0,01) t UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 52 IV.3.2 - Método de Gauss-Seidel Seja o sistema AX = b, na forma X = F X + b. O método iterativo de Gauss-Seidel consiste em: partindo-se da solução inicial x(0) = ( x1 (0) x2 (0) x3 (0) ... xn (0) ) gerar a seqüência de aproximações x(1), x(2), ..., x(k) através das equações de iteração: ) ... ( 1 ) ... ( 1 ) ... ( 1 ) ... ( 1 )( 1)1( )( 22 )( 11 )( )1( 3 )( 332 )( 2313 33 )( 3 )1( 2 )1( 323 )( 1212 22 )( 2 )1( 1 )1( 313 )1( 2121 11 )( 1 k nnn k n k nn nn k n k nn kkk k nn kkk k nn kkk xaxaxab a x xaxaxab a x xaxaxab a x xaxaxab a x Como critério de parada utilizamos || x(k) - x(k - 1) || < a precisão desejada. Obs.: Este método converge mais rápido que o de Jacobi. Exemplo: Resolver o sistema: 2x x x 1 2 1 2 1 2 3x pelo método de Gauss-Seidel com 2 casas decimais. 1ª. Iteração x (0) = (0,9 0,9) = 0,001 3)0()1( )1( 2 )( 1 )( 2 )1( 1 )1( 2 )( 1 10125,0 025,1)95,03( 2 1 )3( 2 1 95,0)9,01( 2 1 )1( 2 1 xx xxx xxx kk kk 2ª. Iteração x x x x 1 2 2 2 2 1 3 1 2 1 1 025 1 0125 1 2 3 1 0125 0 99375 0 0625 10 ( ) ( ) ( ) ( ) ( , ) , ( , ) , , 3ª. Iteração x x x x 1 3 2 3 3 2 3 1 2 1 0 99375 0 996875 1 2 3 0 996875 1 0015625 0 015625 10 ( ) ( ) ( ) ( ) ( , ) , ( , ) , , UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 53 4ª. Iteração 3)3()4( )4( 2 )4( 1 100039063,0 9996094,0)0007813,13( 2 1 0007813,1)0015625,11( 2 1 xx x x 5ª. Iteração 3)4()5( )5( 2 )5( 1 100009766,0 0009765,1)9992187,03( 2 1 9998047,0)9996094,01( 2 1 xx x x Resp: x = (0,99 1,00) t (0,01 0,01)t IV.3.3 - Convergência dos métodos iterativos Seja o sistema AX = b, na forma: (1) x = F x + d , e a iteração definida por: (2) x (k + 1) = F x (k) + d Subtraindo (1) de (2) x (k + 1) - x = F (x (k) - x) Fazendo e (k + 1) = x (k + 1) - x e(k + 1) = F e(k) Teorema : A condição suficiente para que a iteração dada em (2) convirja é que os elementos f i j da matriz F satisfaçam a desigualdade: | |f Li j i n 1 1 j = 1, n Corolário 1: (Critério das linhas) A condição suficientepara que a iteração dada em (2) convirja é que: | | | |a ai i i j j j i n i = 1, n 1 Corolário 2: (Critério das colunas) A condição suficiente para que a iteração dada em (2) convirja é que: | | | |a aj j i j i i j n j = 1, n 1 Observações: A matriz que satisfaz a hipótese dos corolários 1 ou 2 é chamada de matriz diagonal dominante estrita. Na prática são usados os critérios de suficiência expressos nos corolários 1 ou 2, tanto para o método de Jacobi quanto para o método de Gauss-Seidel. Basta que o sistema satisfaça apenas a um desses critérios para se ter a convergência garantida, independente da escolha do vetor inicial. UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 54 IV.3.4 - Qual o método melhor ? Não se pode garantir de início que método será mais eficiente. Os métodos de eliminação se prestam a sistemas de pequeno porte com matrizes de coeficientes densos; também resolvem satisfatoriamente vários sistemas lineares com a mesma matriz de coeficientes. Os métodos iterativos, quando a convergência é garantida, são bastante vantajosos na resolução de sistemas de grande porte com matrizes de coeficientes esparsos ( grande quantidade de zeros entre seus elementos ). Os sistemas oriundos da discretização de equações diferenciais parciais são exemplos típicos. IV.3.5 - Noções de matrizes mal condicionadas Considere o sistema S x x 2 2 1 1 001 2 001 0 999 1999 x + x 1 2 , , , , . Uma das soluções é x = (1 1) t . Se utilizarmos o método de Jacobi, na 5ª. Iteração encontraríamos como solução aproximada x 1 = (2,000 0,001) t , que diverge da solução. Isto aconteceu porque os coeficientes da matriz associada estão mal condicionados. Uma forma de se detectar o mal condicionamento é através do determinante normalizado de uma matriz. Se esse determinante for, sensivelmente, menor que 1 dizemos que a matriz está mal condicionada. Definição: Para a matriz A, associada ao sistema Sn , definimos determinante normalizado de A, e denotamos por det (norm A) a: det ( = det A ... 1 n norm A) 2 , onde: n1,=i ... 223 2 2 2 1 iniiii aaaa Obs.: No sistema S2 dado: 4135066,11999,0 4149208,1001,11 110105,0 000001,2 10,999 001,11 10,999 001,11 =A) (normdet 22 2 22 1 66 21 UERJ - CTC - IME - Departamento de Informática e Ciência da Computação Cálculo Numérico — Professora Mariluci Ferreira Portes 55 Lista de exercícios sobre a Unidade IV 1) Resolva pelo processo retroativo os seguintes sistemas : a) 3 x1 + 4 x2 - 5 x3 + x4 = -10 x2 + x3 - 2 x4 = -1 4 x3 - 5 x4 = 3 2 x4 = 2 b) 3 x1 + 4 x2 - 5 x3 + x4 = -10 x3 - 2 x4 = 0 4 x3 - 5 x4 = 3 2 x4 = 2 2) Resolva pelo método de Gauss, com condensação pivotal parcial. a) 2 x1 + 2 x2 + x3 + x4 = 7 x1 - x2 + 2 x3 - x4 = 1 3 x1 + 2 x2 - 3 x3 - 2 x4 = 4 4 x1 + 3 x2 + 2 x3 + x4 = 12 b) 8,7 x1 + 3,0 x2 + 9,3 x3 + 11,0 x4 = 16,4 24,5 x1 - 8,8 x2 + 11,5 x3 - 45,1 x4 = - 49,7 52,3 x1 - 84,0 x2 - 23,5 x3 + 11,4 x4 = - 80,8 21,0 x1 - 81,0 x2 - 13,2 x3 + 21,5 x4 = -106,3 c) x1 + x2 + 2 x3 = 4 2 x1 - x2 - x3 = 0 x1 - x2 - x3 = -1 3) Resolva os sistemas abaixo usando o método de Gauss-Seidel. a) x1 + x2 + x3 = 3 2 x1 - 2 x2 + x3 = 1 3 x1 - x2 + 2 x3 = 4 b) 2 x1 - x2 + x3 = 3 x1 + 3 x2 - 2 x3 = 1 x2 + 2 x3 = 8 Trabalho Computacional: Programar o método de Gauss com condensação pivotal parcial para resolver o sistema: 8,7 x1 + 3,0 x2 + 9,3 x3 + 11,0 x4 = 16,4 24,5 x1 - 8,8 x2 + 11,5 x3 - 45,1 x4 = - 49,7 52,3 x1 - 84,0 x2 - 23,5 x3 + 11,4 x4 = - 80,8 21,0 x1 - 81,0 x2 - 13,2 x3 + 21,5 x4 = -106,3
Compartilhar