Baixe o app para aproveitar ainda mais
Prévia do material em texto
Apostila de Introdução Aos Métodos Numéricos PARTE II 2o Semestre - 2002 Profa. Salete Souza de Oliveira Buffoni 2 Índice SISTEMAS LINEARES....................................................................................................................3 INTRODUÇÃO ....................................................................................................................................3 MÉTODOS DIRETOS: ELIMINAÇÃO DE GAUSS ...................................................................................4 Sistema linear com n=3 ...............................................................................................................5 Exemplo: ......................................................................................................................................7 SISTEMAS LINEARES....................................................ERRO! INDICADOR NÃO DEFINIDO. Minimizando erros numéricos: Estratégia de Pivoteamento.....................................................10 Avaliando os erros na solução de um sistema linear ................................................................12 QUARTA LISTA DE EXERCÍCIOS ............................................................................................15 MÉTODOS ITERATIVOS: GAUSS-SEIDEL .............................................................................16 Introdução..................................................................................................................................16 Descrição do Método.................................................................................................................17 Exemplo: ....................................................................................................................................18 CRITÉRIOS DE CONVERGÊNCIA DO MÉTODO DE GAUSS-SEIDEL .............................20 Critério de Sassenfeld ................................................................................................................20 Critério das Linhas ....................................................................................................................21 QUINTA LISTA DE EXERCÍCIOS..............................................................................................24 SEXTA LISTA DE EXERCÍCIOS ................................................................................................25 3 Sistemas Lineares Introdução Um sistema linear consiste em um conjunto de n equações lineares envolvendo m variáveis (xi). Uma equação linear é aquela que só apresenta termos que são proporcionais às variáveis (termos do tipo ai⋅xi), isto é, não apresenta nenhuma função aplicada a variável xi, como xn, ln(x), cos(x), como ilustrado abaixo envolvendo m variáveis (x1, x2, x3,...,xm): bxaxaxaxa mm =⋅++⋅+⋅+⋅ L332211 Um sistema linear quadrado é aquele em que o número de variáveis é igual ao número de equações (m=n). Portanto, um sistema linear quadrado pode ser escrito na forma: nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa =⋅++⋅+⋅ =⋅++⋅+⋅ =⋅++⋅+⋅ L M L L 2211 22222121 11212111 Resolver um sistema linear significa encontrar os valores numéricos das variáveis x1, x2, x3,..., xn que satisfazem todas as equações do sistema. Duas perguntas fundamentais devem ser feitas em relação a um sistema linear: 9 Existe solução para o sistema linear? 9 Em caso afirmativo, será que ela é única? Cada sistema linear estudado deve ser analisado a fim de se obter as respostas para essas perguntas. Três casos são possíveis: 9 O sistema não possui nenhuma solução (sistema impossível); 9 O sistema possui uma solução (sistema possível e único); 9 O sistema possui infinitas soluções. É preciso manter em mente essas três possibilidades de comportamento de um sistema linear a fim de evitar surpresas e poder interpretar a solução de um problema. 4 Sistemas de equações lineares aparecem com bastante freqüência na resolução de problemas práticos envolvendo as mais variadas situações. Estima-se que aproximadamente 75% dos problemas científicos envolvem a resolução de um sistema de equações lineares. Um exemplo pode ser visto no livro texto de M. A. G. Ruggiero. Os métodos usados na resolução de sistemas lineares podem ser de dois tipos: diretos ou iterativos. Métodos diretos são aqueles que, a menos de erros de arredondamento, fornecem a solução exata do sistema linear, caso ela exista. Métodos iterativos são equivalentes àqueles vistos no módulo passado: a partir de uma estimativa inicial, repetimos determinado cálculo diversas vezes, utilizando sempre a estimativa da etapa anterior como estimativa para a etapa seguinte. Métodos Diretos: Eliminação de Gauss O método direto que abordaremos no curso é o método da eliminação de Gauss. Neste método procuramos reescrever um sistema linear quadrado como um sistema linear triangular, isto é, um sistema da forma: nnnn nn nn bxa bxaxa bxaxaxa =⋅ =⋅++⋅ =⋅++⋅+⋅ M L L 22222 11212111 Esse sistema é de fácil resolução. Partindo-se da solução da última equação, que é dada por: nn n n a b x = obtém-se o resultados das outras equações recursivamente, isto é: ii n ij jiji i a xab x ∑ += ⋅− = 1 A fim de se transformar um sistema linear quadrado em um sistema linear triangular, manipula-se as equações multiplicando-as por determinados fatores numéricos e subtraindo-as uma 5 das outras de forma a zerar os termos apropriados. Da álgebra linear, sabemos que essas operações não alteram a solução do sistema. Vamos verificar como essa manipulação pode ser feita para um sistema de 3 equações e 3 variáveis e depois podemos generalizar o procedimento para n dimensões. Sistema linear com n=3 Um sistema linear quadrado com n=3 é dado pelas equações: 3333232131 2323222121 1313212111 bxaxaxa bxaxaxa bxaxaxa =⋅+⋅+⋅ =⋅+⋅+⋅ =⋅+⋅+⋅ A fim de resolver esse sistema pelo método de eliminação de Gauss, vamos transforma-lo em um sistema linear triangular, como mencionado anteriormente. Inicialmente, vamos multiplicar a primeira equação pelo fator: 11 21 21 a a m = e subtraí-la da segunda equação. Essa primeira equação é chamada de linha pivô e o elemento a11 é o elemento pivô. Pela expressão de m21 conclui-se que o elemento pivô não pode ser nulo. Caso isso ocorra, essa linha deve ser trocada por outra linha que não apresente o pivô igual a zero. Com essa operação, o sistema se transforma em: 3333232131 2323222 1313212111 0 bxaxaxa bxaxa bxaxaxa =⋅+⋅+⋅ ′=⋅′+⋅′+ =⋅+⋅+⋅ onde, 12212222 amaa ⋅−=′ 13212323 amaa ⋅−=′ 12122 bmbb ⋅−=′ 6 Em seguida, podemos multiplicar a primeira equação (a linha pivô) por: 11 31 31 a a m = e subtraí-la da terceira equação. Com essa operação, o sistema se transforma em: 3333232 2323222 1313212111 0 0 bxaxa bxaxa bxaxaxa ′=⋅′+⋅′+ ′=⋅′+⋅′+ =⋅+⋅+⋅ onde, 12313232 amaa ⋅−=′ 13313333 amaa ⋅−=′ 13133 bmbb ⋅−=′ Note que, com essas operações, conseguimos transformar a segunda linha do sistema na forma triangular. Para finalizarmos a triangulação do sistema, basta “zerar” o termo de x2 na terceira equação. Para isso, vamos utilizar o mesmo procedimento usado anteriormente. Desta vez, a segunda linha será a linha pivô e o elemento a’22 será o elemento pivô, que deve ser diferente de zero. Mais uma vez, caso esse elemento seja nulo, essa linha deve ser trocada por outra linha que não apresente um pivô igual zero. Caso isso não seja possível, ou seja, todas as outras linhas apresentam o pivô nulo, o sistema não terá solução determinada. Portanto, vamos multiplicar a segunda linha pelo fator: 22 32 32 a a m ′ ′= e subtraí-la da terceira equação.Com essa operação, o sistema se transforma em: 7 3333 2323222 1313212111 0 bxa bxaxa bxaxaxa ′′=⋅′′+ ′=⋅′+⋅′ =⋅+⋅+⋅ onde, 23323333 amaa ′⋅−′=′′ 23233 bmbb ′⋅−′=′′ Com isso, obtivemos o sistema linear triangular que desejávamos. Esse sistema pode ser resolvido de maneira recursiva, sendo o resultado dado por: 33 3 3 a b x ′′ ′′= , 22 33 3 232 22 3232 2 a a bab a xab x ′ ′′ ′′⋅′−′ =′ ⋅′−′= e 11 33 3 13 22 33 3 232 121 11 3132121 1 a a b a a a bab ab a xaxab x ′′ ′′⋅− ′ ′′ ′′⋅′−′ ⋅− =⋅−⋅−= Esse procedimento pode ser estendido facilmente para sistemas com n>3. A única diferença será o número maior de operações a serem realizadas. Exemplo: Vamos resolver o sistema de 4 equações e 4 incógnitas, dado por: 601082 48104 4111236 7532 432 4321 4321 4321 −=⋅+⋅−⋅− =⋅+⋅+−⋅ =⋅+⋅+⋅−⋅ −=⋅+⋅+−⋅ xxx xxxx xxxx xxxx 8 Para facilitar a resolução do problema, vamos representa-lo na forma de uma matriz aumentada, que corresponde a uma matriz cujos elementos são os fatores aii, e ela é “aumentada” incluindo-se os fatores bi. Portanto, o sistema acima ficará na forma: −−− − − −− 6010820 481014 4111236 75312 A primeira linha será a linha pivô e o número 2 é o elemento pivô. Vamos utilizar essa linha e esse elemento para zerar o primeiro elemento de cada linha seguinte. Portanto, multiplicando a primeira linha por 6/2=3 e subtraindo-a da segunda linha, teremos: ( ) ( ) −−− − =⋅−−−=⋅−=⋅−=⋅−−−=⋅− −− 6010820 481014 25374435113331203130326 75312 Podemos realizar a mesma operação para as outras duas linhas. Porém, vamos multiplicar a primeira linha pelo fator 4/2=2 antes de subtraí-la da terceira linha, e no caso da quarta linha, não precisamos realizar nenhuma operação, pois seu primeiro elemento já é igual a zero. Portanto, teremos a matriz aumentada: ( ) ( ) −−− =⋅−−−=⋅−=⋅−=⋅−−−=⋅− − −− 6010820 1827422584231012110224 254300 75312 Vamos continuar a triangulação do sistema zerando os elementos da segunda coluna da terceira e quarta linha. Porém, devemos notar que a segunda linha, que seria a linha pivô desta etapa, apresenta o elemento pivô igual a zero. Portanto, não podemos utiliza-la como linha pivô nesta etapa. Devemos troca-la por outra linha. Vamos prosseguir, trocando a segunda linha pela terceira. Com isso, a terceira linha passa a ser a linha pivô. Mais que isso, não precisamos realizar nenhuma operação com a segunda linha, pois ela já apresenta o elemento da segunda coluna igual a 9 zero. Portanto, basta multiplicar a nova linha pivô por –2/1=-2 e subtrai-la da quarta linha, ou seja, teremos: ( ) ( ) ( ) ( ) ( ) −=−⋅−−=−⋅−−=−⋅−−=−⋅−− − − −− 242186062210024802120 254300 182410 75312 A próxima etapa corresponderia a operação que anularia o elemento da terceira coluna da quarta linha. Porém, esse elemento já é nulo. Portanto, já podemos obter a solução desse sistema, que será dada por: x4 = -24/6 = -4 x3 = [25 – (-4)⋅(-4)]/3 = 3 x2 = [18 – (-2) ⋅(-4) – 4⋅3]/1 = -2 e x1 = [-7 - 5⋅(-4) - 3⋅3 – (-1)⋅(-2)]/2 = 1 10 Minimizando erros numéricos: Estratégia de Pivoteamento Um problema que pode ocorrer durante a resolução de um sistema linear pelo método da eliminação de Gauss se refere a erros de arredondamento ou truncamento durante as operações envolvidas. A fim de ilustrar esse problema e definirmos um procedimento que pode minimiza-lo, vamos considerar o seguinte exemplo. Seja o sistema linear: 3814222 134311027 57524 321 321 321 =⋅+⋅+⋅ =⋅−⋅+⋅ =⋅+⋅+ xxx xxx xxx Antes mesmo de resolve-lo pelo método de eliminação de Gauss, podemos notar que ele apresenta uma solução exata dada por x1=1, x2=1 e x3 =1 (substitua esses valores nas equações do sistema acima para verificar que realmente eles correspondem à solução exata). Porém, vamos resolve-lo utilizando esse método e, para ilustrar o problema provocado por arredondamentos, vamos utilizar apenas 3 algarismos significativos durante todos os cálculos e comparar o resultado obtido com essa solução exata. Ou seja, vamos supor que estamos usando uma calculadora que representa números com apenas 3 algarismos. Iniciamos a resolução do sistema escrevendo-o na forma de uma matriz aumentada, ou seja: − 3814222 134311027 575241 A primeira linha será a linha pivô e devemos multiplica-la pelo fator 27/1 e subtrai-la da segunda linha. Em seguida, multiplicamos essa linha por 22/1 e a subtraímos da terceira linha. Portanto, teremos: (Fazendo truncamento) ×−=⋅−×−=⋅−−=⋅−=⋅− ×−=⋅−×−=⋅−−=⋅−=⋅− 33 33 1021.15722381013.1522214864222012222 1041.157271341040.1522732427110012727 575241 Em seguida, a segunda linha será a linha pivô e devemos multiplica-la pelo fator –86/2=-43 e subtrai-la da terceira linha, ou seja, teremos: 11 ( ) ( ) ( ) ( ) ( ) ×−= =×−⋅−−×− ×−= =×−⋅−−×−=⋅−−− ×−×− 4 33 4 33 33 1018.6 1041.1431021.1 1013.6 1040.1431013.1 0243860 1041.11040.120 575241 Com isso terminamos a triangulação do sistema, que será dado por: 4 3 4 3 3 3 2 321 106.18106.13 1014.110 40.12 57524 ×−=⋅×− ×−=⋅×−⋅ =⋅+⋅+ x xx xxx A partir dai, podemos calcular a solução desse sistema. A solução do sistema será dada por: x3 = -61800/(-61300)=1.01 x2 =[ -1410 – (-1400)⋅1.01]/2 = 0.0 x1 = [57 - 52⋅1.01 -4⋅0.0]/1 = 4.5 Note que essa solução é muito diferente da solução exata que deveríamos ter encontrado. E essa discrepância foi resultado dos arredondamentos e truncamentos que fizemos durante o cálculo dos valores das variáveis xi. A fim de minimizar os efeitos de arredondamento na solução de um sistema linear, utiliza-se a chamada estratégia de pivoteamento. Nessa estratégia, no início de cada etapa em que uma coluna da matriz aumentada deve ser zerada, escolhemos como linha pivô aquela que apresenta o elemento pivô de maior módulo. Portanto, no exemplo acima, iniciaríamos a solução do sistema trocando a segunda linha pela primeira, pois a segunda linha apresenta um elemento pivô (primeiro elemento da linha) maior que a primeira linha (27 > 1). Ou seja, teremos: − 3814222 575241 134311027 Em seguida, multiplicamos a primeira linha (linha pivô) por 1/27 e a subtraímos da segunda linha. Também devemos multiplica-la por 22/27 e subtrai-la da terceira linha. Com isso, teremos: 12 ( ) ( ) −=⋅−=−⋅−−=⋅−=⋅− =⋅−=−⋅−−=⋅−=⋅− − 7113427 22385.16327 22146.8711027 22202727 2222 5213427 1571.52327 15207.011027 1402727 11 134311027 Mais uma vez, antes de iniciar a próxima etapa, devemos procurar pela linha que apresenta o elemento pivô (o primeiro elemento não nulo) de maior módulo. Neste caso, será a terceira linha. Portanto, vamos trocá-la pela segunda linha, o que resulta na matriz aumentada: − −− − 521.5207.00 715.166.870 134311027 Vamos agora multiplicar a linha pivô por (–0.07)/(-87.6) e subtrai-la da terceira linha, ou seja: ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) =−⋅−−−=⋅−−−=−⋅−−−− −− − 1.52716.87 07.0521.525.166.87 07.01.5206.876.87 07.007.00 715.166.870 134311027 A solução do sistema triangular que resultou dessas operações é dada por:x1 = 52.1/52.1 = 1.0 x2 = [-71-16.5⋅1.0]/(-87.6) = 0.999 x3 = [134 – (-3)⋅1.0 – 110⋅0.999]/27 = 1.0 Portanto, obtivemos uma solução muito próxima da solução exata do sistema utilizando a estratégia do pivoteamento. Avaliando os erros na solução de um sistema linear Como vimos na seção anterior, devido aos erros numéricos de arredondamento ou truncamento e devido ao grande número de operações realizadas na resolução de sistemas lineares, o resultado que obtemos está sujeito a erros, ou seja, pode não representar a solução exata do problema. Portanto, precisamos sempre avaliar a solução obtida, ou seja, precisamos nos perguntar qual é o erro do resultado que obtivemos. 13 Para facilitar a visualização de como podemos avaliar esses erros, vamos escrever um sistema de equações lineares da forma matricial, ou seja, o sistema linear: nnnnnn nn nn bxaxaxa bxaxaxa bxaxaxa =⋅++⋅+⋅ =⋅++⋅+⋅ =⋅++⋅+⋅ L M L L 2211 22222121 11212111 pode ser escrito como, A⋅x = b onde, = nnnn n n aaa aaa aaa A L MOMM L L 21 22221 11211 , = nx x x x M 2 1 e = nb b b b M 2 1 Ao resolver esse sistema devido aos erros numéricos cometidos, obtemos como solução, ao invés dos valores x, valores que chamaremos de x’. Portanto, o erro será dado por: Erro = x – x’. 14 Uma operação simples que podemos realizar para verificar a diferença entre o valor real (x) e o valor que obtivemos (x’) é calcularmos: A⋅x’ = b’ Podemos em seguida calcular a diferença entre b e b’, que chamaremos de resíduos: Resíduo = b – b’ Quanto menor for o resíduo, menor será o erro que cometemos. Note que o resíduo não é o erro, mas apenas uma estimativa do mesmo, pois: Resíduo = b – b’ = A⋅x - A⋅x’ = A⋅(x – x’) = A⋅erro 15 Quarta Lista de Exercícios 1 ) O que é um sistema de equações lineares quadrado? 2 ) A fim de se poder interpretar a resolução de um sistema de equações lineares é preciso saber quais são os possíveis tipos de soluções que podemos encontrar. Cite os três tipos de soluções possíveis de um sistema linear e comente o que você faria em cada caso. 3 ) No método de eliminação de Gauss, um sistema linear quadrado é transformado em um sistema triangular. Qual a vantagem de se fazer isso? 4 ) Dado o sistema linear, 72.48.26.3 15.21.4 84.24.25.1 2.822.3 41 421 431 321 =⋅+⋅ =+⋅+⋅ =⋅−⋅+− =⋅++⋅ xx xxx xxx xxx Encontre sua solução através do método de eliminação de Gauss. 16 Métodos Iterativos: Gauss-Seidel Introdução É bastante comum encontrarmos sistemas lineares que envolvem uma grande porcentagem de coeficientes nulos. Esses sistemas são chamados de sistemas esparsos. Para esses tipos de sistemas, o método de Eliminação de Gauss não é o mais apropriado, pois ele não preserva essa esparsidade, que pode nos ser útil por facilitar a resolução do sistema. Um método mais apropriado para esse tipo de sistema é o método iterativo de Gauss-Seidel. Este método consiste em encontrar, dada uma estimativa inicial xi 0, uma seqüência de estimativas xi k que após um número suficientemente grande de iterações convirja para a solução do sistema de equações. nnnn x x x x x x x x x x x x x x x x x x x x 210 4 2 4 1 4 0 4 3 2 3 1 3 0 3 2 2 2 1 2 0 2 1 2 1 1 1 0 1 MMMM →→→ Uma outra vantagem deste método é o fato de não estar tão suscetível ao acúmulo de erros de arredondamento como o método de Eliminação de Gauss. Porém, como todo processo iterativo, este método sempre apresentará um resultado aproximado, que será tão próximo do resultado real conforme o número de iterações realizadas. Além disso, também precisamos nos preocupar com a convergência desse método. 17 Descrição do Método Seja o seguinte sistema de equações: nb nx.nna 1nx.1nna ... 3x.na 2x.na 1x.na 3b nx.n3a 1nx.1n3a ... 3x.33a 2x.32a 1x.31a 2b nx.n2a 1nx.1n2a ... 3x.23a 2x.22a 1x.21a 1b nx.n1a 1nx.1n1a ... 3x.13a 2x.12a 1x.11a 1321 =+−−++++ =+−−++++ =+−−++++ =+−−++++ M Isolando xi a partir da linha i, temos : ( ) ( ) ( ) ( )11,21 311,32322313 33 3 211,23231212 22 2 111,13132121 11 1 ...... 1 .... 1 .... 1 .... 1 21 −− −− −− −− −−−−= −−−−= −−−−= −−−−= nnnnnn nn n nnnn nnnn nnnn xaxaxab a x xaxaxaxab a x xaxaxaxab a x xaxaxaxab a x M 18 O processo iterativo é obtido a partir dessas equações, fazendo: +−−−−+−+−=+ −−−−−+−+−=+ −−−−−−+−=+ −−−−−−−=+ 1k 1nx.1n,na... 1k 2x.2na 1k 1x.1nanbnna 11k nx k nx.n3a k 1nx.1n,3a... 1k 2x.32a 1k 1x.31a3b33a 11k 3x k nx.n2a k 1nx.1n,2a... k 3x.23a 1k 1x.21a2b22a 11k 2x k nx.n1a k 1nx.1n,1a... k 3x.13a k 2x.12a1b11a 11k 1x Como todo processo iterativo, precisamos definir um critério de parada. Podemos usar a diferença relativa entre duas iterações consecutivas para estabelecer o critério de parada. Define-se por diferença relativa a expressão: ≠ = = ≠− ≤≤ = + + + + + =+ 0 x 0 x se 1 0 x x se 0 0 x se x k ixx .Máx ni1 d k i 1k i k i 1k i 1k i 1k i 1k i 1k R Quando o valor de dR k+1 for pequeno o bastante para a precisão desejada, podemos para o processo iterativo. Exemplo: Resolva: 19 .210.5 kRd com 0z6y3x3 6zy4x3 5zyx5 −≤ =++ =++ =++ ( ) ( ) ( ) ( )yxzyxz zxy zyx +−=⇒+−= −−= −−= 2 1 33 6 1 36 4 1 5 5 1 kx k xd ky k yd kz kzd k Rd -1 - 0 - 1 - - 0,8 2,25 0,65 1 -0,725 2,379 2,379 1,015 0,212 0,92 0,293 -0,967 0,250 0,293 1,009 0,006 0,985 0,066 -0,997 0,030 0,066 1,002 0,007 0,998 0,0013 -1 0,003 0,013 x = 1,002 y = 0,998 z = -1 Verificação: 5.(1,002) + (0,998) + (-1) = 5,008 ≅ 5 ok 3.(1,002) + 4.(0,998) + (-1) = 5,998 ≅ 6 ok 3.(1,002) + 3.(0,998) + 6.(-1) = 0 ok 20 Critérios de Convergência do Método de Gauss-Seidel Como todo processo iterativo, a sua convergência para a solução exata não é garantida para qualquer sistema. Existem certas condições que devem ser satisfeitas por um sistema de equações lineares para se garantir a convergência do método. Uma condição suficiente, porém não necessária, para a convergência do método de Gauss-Seidel para um dado sistema linear, corresponde ao Critério de Sassenfeld. Critério de Sassenfeld Vamos definir as quantidades βi dadas por: ∑ = ⋅= n j jaa 2 1 11 1 1β e +⋅⋅= ∑∑ += − = n ij ij i j jij ii i aaa 1 1 1 1 ββ , para i = 2, 3, ..., n. onde n é a ordem do sistema linear que queremos resolver e aij são os coeficientes das equações que compõem esse sistema.O Critério de Sassenfeld garante que o método de Gauss-Seidel convergirá para um dado sistema linear se a quantidade M, definida por: i ni M βmax 1 ≤≤ = for menor que 1 (M<1). Exemplo: Mostre que a solução do sistema linear dado pelas equações: 0.1048.02.14.0 0.12.02.01.0 8.73.06.036.0 4.02.02.02 4321 4321 4321 4321 −=⋅+⋅+⋅+⋅ =⋅++⋅−⋅− −=⋅−⋅−⋅+⋅ =⋅+⋅−+⋅ xxxx xxxx xxxx xxxx convergirá pelo método de Gauss-Seidel. 21 Para realizar essa verificação, vamos utilizar o critério de Sassenfeld. Inicialmente, é preciso se calcular os valores das quantidades βi. No caso do sistema acima, elas serão dadas por: ( ) ( ) ( ) ( ) 2736.0358.08.044.02.17.04.0 4 1 358.02.044.02.07.01.0 1 1 44.03.06.07.06.0 3 1 7.02.02.01 2 1 4 3 2 1 =⋅+⋅+⋅⋅= =+⋅+⋅⋅= =++⋅⋅= =++⋅= β β β β Em seguida, é preciso verificar qual dessas quantidades tem o maior valor. Neste caso, será a quantidade β1 que é igual a 0.7 (maior valor entre todos os βi). Portanto, como: 7.0max 41 == ≤≤ i i M β é menor que 1, sabemos que a solução desse sistema irá convergir usando o método de Gauss- Seidel. Critério das Linhas Existe um outro critério que pode garantir a convergência do método de Gauss-Seidel para um dado sistema, chamado de critério das linhas. Segundo esse critério, um determinado sistema irá convergir pelo método de Gauss-Seidel, se: ii n ij j ij aa <∑ ≠=1 , para i=1, 2, 3, ..., n. Exemplo: O sistema do exemplo acima satisfaz o critério das linhas e essa verificação pode ser feita de maneira quase imediata, observando-se que: 22 4.28.02.14.04 5.02.02.01.01 5.13.06.06.03 4.12.02.012 43424144 34323133 24232122 14131211 =++=++>= =++=++>= =++=++>= =++=++>= aaaa aaaa aaaa aaaa É importante notar alguns detalhes sobre esses critérios. Ambos os critérios mencionados acima são condições suficientes, porém não são necessárias para garantir a convergência da solução de um sistema linear pelo método de Gauss-Seidel. Isso significa que um sistema pode não satisfazer esses critérios e ainda convergir. Por exemplo, um sistema pode não satisfazer o critério das linhas e satisfazer o critério de Sassenfeld, o que garantirá sua convergência. Exemplo: Seja o sistema: 1826 2310 21 21 =⋅+⋅ =+⋅ xx xx Note que esse sistema não satisfaz o critério das linhas, pois: 62 2122 =<= aa porém, ele satisfaz o critério de Sassenfeld: ( ) 3.01.06 2 1 1.01 10 1 2 1 =⋅⋅= =⋅= β β ⇒ 13.0max 41 <== ≤≤ i i M β que garantirá sua convergência. Outra observação importante se refere à ordem com que as equações aparecem no sistema. Apesar da ordem das equações não alterar a solução do sistema, ela pode alterar a convergência do mesmo pelo método da Gauss-Seidel. Exemplo: Seja o sistema: 23 1535 19104 21 21 =⋅+⋅ =⋅+⋅− xx xx Na forma como ele está representado acima, ele não satisfaz o critério das linhas (verifique isso), portanto sua convergência não é garantida. Porém, se trocarmos a ordem das duas equações, o sistema satisfaz esse critério, e sua convergência pelo método de Gauss-Seidel é garantida (verifique isso também). 24 Quinta Lista de Exercícios 1 ) No método de Gauss-Seidel, como em todo método iterativo, a convergência na resolução do problema para a solução procurada não é sempre garantida. Que condição um sistema linear deve satisfazer para que esse método convirja para a sua solução? 2 ) Dado o sistema linear, 923 1 33 321 21 31 =⋅++⋅ =− =+⋅ xxx xx xx Verifique se o método de Gauss-Seidel convergiria para o sistema acima: (a) Segundo o critério das linhas; (b) Segundo o critério de Sassenfeld; (c) O que você pode concluir da solução dos dois itens anteriores? 3 ) Dado o sistema linear, 12 12 12 12 43 432 21 321 =⋅+− =−⋅+− =−⋅ =−⋅+ xx xxx xx xxx (a) O sistema irá convergir pelo método iterativo de Gauss-Seidel, isto é, ele satisfaz o critério de Sassenfeld? (b) Se as duas primeiras linhas forem trocadas, ele satisfaz o critério de Sassenfeld? O que se pode afirmar sobre a convergência do sistema? (c) Encontre sua solução através do método de Gauss-Seidel usando como estimativa inicial os valores (x1 =0, x2 =0, x3 =0, x4 =0) e utilize como critério de parada M k < 0,5. 25 Sexta Lista de Exercícios 1 ) O que é e para que serve a estratégia de pivoteamento? 2 ) Cite três características do Método de Gauss-Seidel que é comum a todo processo iterativo. 3 ) Dado o sistema linear, 11243 9427 32 321 321 321 =⋅−⋅+⋅ =⋅+⋅−⋅ −=−−⋅ xxx xxx xxx encontre sua solução através do método de eliminação de Gauss utilizando a estratégia do pivoteamento. 4 ) Dado o sistema linear, 79.042 57.155 94.54 321 321 321 =⋅+⋅+ −=−⋅+− =++⋅ xxx xxx xxx (d) Verifique que o sistema irá convergir pelo método iterativo de Gauss-Seidel, isto é, que ele satisfaz o critério de Sassenfeld; (e) Encontre sua solução através do método iterativo de Gauss-Seidel usando como estimativa inicial os valores (x1 =0, x2 =0, x3 =0) e utilize como critério de parada a condição M k < 0,5. 26 Referências Bibliográficas RUGGIERO/LOPES - Cálculo Numérico. Makron Books CHAPRA/CARRALE - Numerical Methods for Engineers. Ed. McGrawHill CONTE - Elementos de Análise Numérica. Ed. Globo BARROSO - Cálculo Numérico - Ed. Harper & How do Brasil MARCELO G. MUNHOZ- Notas de Aula - FACENS
Compartilhar