Aula 07 - Método Iterativo de Gauss-Seidel

Prévia do material em texto

Método Iterativo de 
Gauss-Seidel
2024/2
BCC760 - Cálculo Numérico
Prof. Geovani Martins
geovani@ufop.edu.br
2
Método Iterativo de Gauss-Seidel
Ementa
I) Resolução de Sistemas de Equações Lineares Simultâneas
1. Introdução
2. Métodos Diretos
2.1 - Método de Eliminação de Gauss
2.2 - Método da Decomposição LU
3. Métodos Iterativos
3.1 - Método de Jacobi
3.2 - Método de Gauss-Seidel
3.3 - Convergência
4. Aplicações
3
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Assim como no Método de Jacobi, o sistema de equações lineares AX = B, em
que 𝐝𝐞𝐭 𝐀 ≠ 𝟎 e diagonal principal 𝐚𝐢𝐢 ≠ 𝟎 ∀ 𝐢 , deve ser escrito na forma
equivalente explicitando uma incógnita em cada equação.
• A diferença é que, na k-ésima iteração, ao realizar-se a atualização de uma das
componentes do vetor 𝐗𝐤, são utilizadas as componentes já atualizadas nesta
iteração e, as demais, ainda não atualizadas, da iteração anterior.
• Portanto, o Método de Gauss-Seidel é similar ao Método de Jacobi, com a
diferença de que nesse método aproveita-se os resultados obtidos na
mesma iteração.
𝐗 = 𝐌𝐗 + 𝐜
4
Método Iterativo de Gauss-Seidel
• Tem-se, então, a função de iteração e o esquema iterativo:
Método de Gauss-Seidel
(𝒌)
(𝒌)
(𝒌)
(𝒌)
5
Método Iterativo de Gauss-Seidel
• Tem-se, então, a função de iteração e o esquema iterativo:
Método de Gauss-Seidel
6
Método Iterativo de Gauss-Seidel
• Tem-se, então, a função de iteração e o esquema iterativo:
Método de Gauss-Seidel
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌) (𝒌)
(𝒌 − 𝟏) (𝒌 − 𝟏) (𝒌 − 𝟏)
(𝒌)
(𝒌 − 𝟏)
(𝒌 − 𝟏) (𝒌 − 𝟏) (𝒌 − 𝟏)
(𝒌 − 𝟏) (𝒌 − 𝟏)
Método Iterativo de Gauss-Seidel
• Forma matricial:
• Forma geral:
Método de Gauss-Seidel
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌)
(𝒌 − 𝟏)
(𝒌 − 𝟏)
(𝒌 − 𝟏)
(𝒌) (𝒌 − 𝟏)
; ;
8
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
9
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• A função de iteração é dada por:
10
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
11
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
12
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
13
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
14
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
15
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
16
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
17
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
18
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 1: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, quatro casas decimais.
• Os resultados da aplicação do Método de Gauss-Seidel são apresentados no
quadro a seguir:
Portanto, a solução do sistema 
linear é:
X = [ 0,5000 0,2500 0,2500 ] t 
com precisão ε = 0,0001
19
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
𝑥1 − 7𝑥2 + 2𝑥3 = −4
8𝑥1 + 𝑥2 − 𝑥3 = 8
2𝑥1 + 𝑥2 + 9𝑥3 = 12
20
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• A função de iteração é dada por:
𝑥1 − 7𝑥2 + 2𝑥3 = −4
8𝑥1 + 𝑥2 − 𝑥3 = 8
2𝑥1 + 𝑥2 + 9𝑥3 = 12
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
21
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• Os resultados da aplicação do método de Gauss-Seidel são apresentados no
quadro a seguir:
0 000 -----
3
2
1
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
22
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• Os resultados da aplicação do método de Gauss-Seidel são apresentados no
quadro a seguir:
0 000 -----
-4,00
3
2
1 40,00 40,00-2,22
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
23
Método Iterativo de Gauss-SeidelMétodo de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• Os resultados da aplicação do método de Gauss-Seidel são apresentados no
quadro a seguir:
0 000 -----
280,44
-4,00
3
2
1 40,00
-2.237,74 2.277,74
40,00-2,22
187,65
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
24
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• Os resultados da aplicação do método de Gauss-Seidel são apresentados no
quadro a seguir:
0 000 -----
128.543,49-16.043,48 -10.716,06 130.781,23
280,44
-4,00
3
2
1 40,00
-2.237,74 2.277,74
40,00-2,22
187,65
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
25
Método Iterativo de Gauss-Seidel
Método de Gauss-Seidel
• Exemplo 2: Resolva o sistema linear pelo Método de Gauss-Seidel com o limite de
6 iterações ou uma precisão menor que 10(−2). Utilize X0 = [0 0 0]t como estimativa
inicial e retenha, nos cálculos, duas casas decimais.
• Os resultados da aplicação do método de Gauss-Seidel são apresentados no
quadro a seguir:
0 000 -----
128.543,49-16.043,48 -10.716,06 130.781,23
280,44
-4,00
3
2
1 40,00
-2.237,74 2.277,74
40,00-2,22
187,65
Não está convergindo!
𝑥1
(𝑘)
= −4 + 7𝑥2
(𝑘−1)
− 2𝑥3
(𝑘−1)
𝑥2
(𝑘)
= 8 − 8𝑥1
(𝑘)
+ 𝑥3
(𝑘−1)
𝑥3
(𝑘)
= (12 − 2𝑥1
(𝑘)
- 𝑥2
(𝑘)
)/9
26
Convergência dos Métodos Iterativos
Critérios de Convergência
• É condição suficiente para que os métodos iterativos gerem uma sequência que
converge para a solução de um sistema de equações AX = B, qualquer que seja a
aproximação inicial 𝐗𝟎, que:
a) o critério das linhas seja satisfeito, isto é, se:
b) o critério das colunas seja satisfeito, isto é, se:
• Quanto mais próximo de zero estiverem as relações e , mais rápida
será a convergência.
27
Convergência dos Métodos Iterativos
Critérios de Convergência
• É condição suficiente para que os métodos iterativos gerem uma sequência que
converge para a solução de um sistema de equações AX = B, qualquer que seja a
aproximação inicial 𝐗𝟎, que:
a) o critério das linhas seja satisfeito, isto é, se:
b) o critério das colunas seja satisfeito, isto é, se:
Estes dois critérios envolvem condições que são apenas suficientes, se pelo
menos uma delas for satisfeita, então está assegurada a convergência, entretanto se
nenhuma das duas for satisfeita nada se pode afirmar.
28
Convergência dos Métodos Iterativos
Critérios de Convergência
• Seja uma matriz
• A é diagonalmente dominante se:
• A é estritamente diagonal dominante se:
29
Convergência dos Métodos Iterativos
Critérios de Convergência
• Seja uma matriz
• A é diagonalmente dominante se:
• A é estritamente diagonal dominante se:
30
Convergência dos Métodos Iterativos
Critérios de Convergência
• Seja uma matriz
• A é diagonalmente dominante se:
• A é estritamente diagonal dominante se:
31
Convergência dos Métodos Iterativos
Critérios de Convergência
• Exemplo: Considere a matriz
32
Convergência dos Métodos Iterativos
Critérios de Convergência
• Exemplo: Considere a matriz
Tem-se que:
33
Convergência dos Métodos Iterativos
Critérios de Convergência
• Exemplo: Considere a matriz
Tem-se que:
Para
Para
Para
34
Convergência dos Métodos Iterativos
Critérios de Convergência
• Exemplo: Considere a matriz
Tem-se que:
Para
Para
Para
Portanto, conclui-se que a
matriz A é diagonalmente
dominante.
35
Convergência dos Métodos Iterativos
Critérios de Convergência
• Critérios suficientes para a convergência de métodos iterativos:
• Matriz A estritamente diagonal dominante.
• Matriz A diagonalmente dominante e sistema linear irredutível.
• Critério de Sassenfeld para o Método de Gauss-Seidel (não iremos abordar
aqui).
• Pode acontecer do Método de Jacobi convergir e o Método de Gauss-Seidel
não, e vice-versa.
• A convergência dos métodos iterativos não depende da aproximação inicial,
mas quanto melhor for a aproximação inicial menor será o número de iterações
necessárias para atingir uma determinada precisão.
Obs: Se preciso, reordene as equações para garantir a convergência.
36
Complexidade dos Métodos Iterativos
Complexidade
• Avaliar a quantidade de operações requeridas em um método iterativo, em cada
iteração, é bastante simples.
• O que não é trivial é determinar o número exato do total de operações
realizadas.
• Uma vez que é estabelecido um número máximo de iterações, no pior caso, este
será o número de vezes que as iterações serão executadas.
• Pode ser demonstrado que, para um sistema de n equações, o número total de
operações, por iteração, é (2n2 – n).
37
Complexidade dos Métodos Iterativos
Complexidade
• O Método de Eliminação de Gauss requer (4.n3 + 9.n2 – 7.n)/6 operações
aritméticas.
• Os Métodos de Jacobi e Gauss-Seidel requerem (2.n2 - n) operações aritméticas
por iteração.
• Para valores grandes de n, os números de operações aritméticas são,
aproximadamente,
• Método de Gauss: 4.n3
• Jacobi e Gauss-Seidel: 2.n2 por iteração
38
Considerações Finais
Métodos Diretos x Iterativos
Indicador Método Direto Método Iterativo
Aplicação
Para a resolução de sistemas de 
equações densos de pequeno a médio 
porte.
Para a resolução de sistemas de 
equações de grande porte, notadamente 
os esparsos.
Esparsidade
Destrói a esparsidade da matriz dos 
coeficientes durante a fase de 
eliminação.
Preserva a esparsidade da matriz dos 
coeficientes.
Convergência
Se a matriz dos coeficientes não é 
singular, então a solução é sempre 
obtida.
Há garantia de se obter a solução somente 
sob certas condições.
Número de 
operações
É possível determinar, a priori, o 
número de operações necessárias.
Não é possível determinar a complexidade 
a priori.
Erros de 
arredondamento
São ampliados durante os cálculos. 
Podem ser minimizados usando uma 
técnica de pivotação.
Não afetam os resultados obtidos em cada 
iteração. Apenas a solução final pode 
conter erro.
39
Exercícios
Método Iterativo de Gauss-Seidel
• Exercício 01: Resolva o sistema de equações lineares a seguir pelo Método
Iterativo de Gauss-Seidel. Utilize X0 = [1 1,5 0] t como estimativa inicial, a
precisão menor ou igual a 10-3 (ε ≤ 0,001) e kmáx = 10. Se necessário, retenha 4
casas decimais nos cálculos.
Solução: X = 1.5002 2,0001 0,5000 𝑡 com precisão ε = 0,0004 (k = 7).
൝ 2𝑥1 − 4𝑥2 + 2𝑥3 = −4
−𝑥1 + 𝑥2 + 5𝑥3 = 3
3𝑥1 + 2𝑥2 − 𝑥3 = 8
40
Exercícios
Método Iterativo de Gauss-Seidel
• Exercício 02: Considere o seguinte sistema de equações lineares:
(a) É possível aplicar os métodos iterativos com convergência assegurada? Justifique
sua resposta e, se necessário, reordene as equações do sistema de modo que a
convergência dos métodos iterativos esteja assegurada.
(b) Caso a convergência seja garantida pelo sistema proposto ou reordenado,
resolva-o pelo Método Iterativo de Gauss-Seidel. Admita solução inicial nula e a
precisão ε ≤ 0,001. Considere um limite de até 8 iterações. Se necessário, retenha
3 casas decimais nos cálculos.
Solução: X = 1.500 1,000 − 2,000 𝑡 com precisão ε = 0,001 (k = 5).
൝ 4𝑥1 + 𝑥2 + 𝑥3 = 5
−2𝑥1 + 5𝑥2 + 𝑥3 = 0
3𝑥1 + 𝑥2 + 6𝑥3 = −6,5
Bons estudos!
geovani@ufop.edu.br