matemática - métodos numéricos para álgebra linear-completo

Prévia do material em texto

MÉTODOS NUMÉRICOS PARA ÁLGEBRA 
LINEAR 
INTRODUÇÃO 
O objetivo, desse trabalho, é apresentar alguns dos mais usuais métodos numéricos para 
resolver sistemas lineares. A forma de apresentação, através de uma linguagem 
orientada ao uso de hipertexto, tem duplo objetivo: o pimeiro, permitir aos alunos que 
possam estudar sozinhos e/ou resolver seus problemas de forma independente; o 
segundo, trabalhar com os atuais alunos da disciplina de Métodos Numéricos de 1996, 
do curso de Engenharia de Computação da PUC-Rio. Esses alunos receberam o texto já 
digitado por mim e fizeram, comigo, o restante de todo o trabalho. 
A organização do trabalho foi feita em duas partes integradas e complementares: um 
tutorial sobre a parte conceitual com exemplos e uma parte que contém algumas rotinas 
que podem ser usadas sem dificuldades para que se resolvam sistemas lineares. Os 
algorítmos escolhidos para implementação foram: dois métodos diretos: Eliminação de 
Gauss e Fatoração de Crout; e três métodos iterativos: Jacobi, Gauss-Seidel e Sobre-
relaxação. 
 2
Index 
1. Complementos de Álgebra linear 
2. Métodos Diretos para Solução de Sistemas Lineares 
3.Métodos Iterativos 
 
1 - COMPLEMENTOS DE ÁLGEBRA LINEAR 
Uma das mais usadas estruturas algébricas é sem dúvida a matriz. Sua utilização nas 
mais variadas formulações matemáticas permite a simplificação não só da parte teórica, 
mas também das próprias aplicações. A resolução de Sistemas Lineares está nesse caso. 
Na definição e resolução desses sistemas, a forma matricial está sempre presente, seja 
na esquematização dos métodos diretos, seja no estudo da convergência dos métodos 
iterativos. Vamos, portanto, rever alguns pontos fundamentais sobre matrizes, 
necessários neste capítulo. 
1.1 - Definições Iniciais 
Vejamos, inicialmente, algumas notações importantes usadas daqui em diante: 
X : vetor de n componentes reais; 
X : vetor de n componentes complexas; 
: matriz real de n linhas e m colunas; 
: matriz complexa de n linhas e m colunas; 
I : matriz identidade; 
: matriz inversa de A; = I; 
0 : matriz nula; 
A = (aij), i n, j m: matriz de n linhas e m colunas, cujos elementos são aij. 
1.2 - Álgebra Matricial 
Dadas duas matrizes A e B podemos definir operações de adição e multiplicação da 
seguinte forma: sejam A e B matrizes de , então: 
 3
A = B = 
C = A + B = isto é: cij = aij + bij, i n, j m. 
Claro, para se realizar a adição de matrizes, é preciso que ambas tenham a mesma 
dimensão. 
Exemplo 1.1 
A = B = C = A + B = 
A multiplicação, ao contrário da adição, não presume as mesmas dimensões para as 
duas matrizes. 
Por definição, temos: C = A x B ; Cij = 
isto é, o único que se exige é que o número de colunas da matriz A seja igual ao número 
de linhas de B, para que todas as parcelas (aik . bkj ) estejam definidas. 
Exemplo 1.2 
Sejam A e B do exemplo anterior 
C = A x B = 
1.3 - Sistemas Lineares 
Um sistema linear é a reunião de equações algébricas lineares, que devem ser resolvidas 
simultaneamente, isto é, deve haver uma solução única que satisfaça a todas as equações 
ao mesmo tempo. 
 
 4
Exemplo 1.3 
x + y + z = 3
{ y + z = 5
x + y = 3
Esse é um sistema de três equações e três incógnitas, cuja solução é x = -2, y = 5 e z = 0, 
isto é, esses valores satisfazem as três equações simultaneamente. A solução de um 
sistema é, portanto, a solução comum a todas as equações. 
Há certas operações entre as equações de um sistema que preservam a solução original. 
Por exemplo, se somarmos duas linhas completas e colocarmos essa nova equação no 
lugar de uma das que foram somadas, continuamos com a solução original. 
Exemplo 1.4 
No exemplo anterior somando a 1a equação com a 3a, colocando o resultado no lugar da 
3a equação, teremos um sistema cuja solução é a mesma do sistema anterior: 
x + y + z = 3
{ y + z = 5
2x + 2y + z = 6
Exemplo 2.1 
Multiplicando a 2a equação do mesmo sistema teríamos: 
x + y + z = 3
{ 2y + 2z = 10
x + y = 3
que continua tendo a solução anterior. 
Essas operações são exemplos das chamadas operações elementares. Cada uma delas 
pode ser representada pela multiplicação de uma matriz, chamada matriz elementar, 
pela matriz do sistema. Assim, nos nossos exemplos anteriores o resultado da adição das 
duas equações seria obtida se multiplicássemos a matriz A do sistema dado, pela matriz 
elementar 
P1 = , pois P1.A = 
P2 = , pois P2.A = 
e vemos que P1.A representa a matriz do sistema do exemplo 1.4 e P2.A representa a 
matriz do exemplo 2.1. 
 5
De um modo geral as matrizes elementares são obtidas da matriz identidade, mudando-
se um dos seus elementos. 
As operações definidas com uso de matrizes elementares são a base da definição dos 
chamados métodos de eliminação, pois permitem transformar um dado sistema em outro 
mais simples de se resolver. 
1.4 - Estudo Matricial de Sistemas Lineares 
1.4.1 - Introdução 
O estudo da resolução de um sistema linear pode ser grandemente facilitado se lhe 
aplicarmos os nossos conhecimentos sobre matrizes. Neste parágrafo, faremos 
exatamente isso. Usaremos os conceitos dados para determinar a resolução de um 
sistema linear em geral. 
1.4.2 - Forma Matricial de um Sistema Linear 
Seja o sistema dado: 
3x + 2y + z = 6
(1.1) { x + 3y + z = 5
2x + 2y + 3z = 7
Então, sua representação matricial será AX = B, onde: 
A = ; X = ; B = 
e sua solução, x= y = z = 1 ; X = (1 1 1)t. 
De agora em diante, todo estudo feito com sistema linear será com a sua forma 
matricial. Veremos, adiante um modo muito simples de se determinar a solução de um 
sistema chamado método de eliminação de Gauss. 
 
 6
2. MÉTODOS DIRETOS PARA SOLUÇÃO DE 
SISTEMAS LINEARES 
Vamos, nesse parágrafo, examinar os mais usuais médotos diretos para solução 
numérica de sistemas lineares. Esses métodos são conhecidos como métodos de 
eliminação e métodos de fatoração. 
2.1 - Método de Eliminação de Gauss 
Dado um sistema linear qualquer da forma: 
a11.x1 + a12.x2 + . . . + a1n.xn = b1
(2.1) a21.x1 + a22.x2 + . . . + a2n.xn = b2
. . . . . .
an1.x1 + an2.x2 + . . . + ann.xn = bn
o método de Gauss consiste em fazer operações entre linhas deste sistema até 
chegarmos a um novo sistema (que terá a mesma solução que o inicial) com a forma 
triangular: 
a'11.x1 + a'12.x2 + . . . + a'1n.xn = b'1
a'22.x2 + . . . + a'2n.xn = b'2
(2.2) . . . . . .
a'nn.xn = b'n
Claro que a determinação da solução de (1.3) é óbvia e direta: o valor de x(n) já está 
determinado na última equação. O valor de x(n-1) será determinado na penúltima, 
substituindo-se o valor de x(n); o valor de x(n-2) será obtido na penúltima linha com os 
valores já determinados de x(n) e x(n-1) , e assim por diante até determinamos x(1). 
Então, desde que se consiga levar o sistema (1.2) na forma (1.3) sem alterar suas 
soluções, o nosso problema está resolvido. Vejamos, então, como fazer esta 
transformação. Usaremos um exemplo para tornar o processo mais claro. 
Consideremos outra vez o sistema (1.1). Os passos a executar são: 
1. considerar a 1a linha como base para a eliminação ; 
2. zerar todos os coeficientes da 1a coluna abaixo da a11; 
3. zerar todos os coeficientes abaixo da diagonal principal; para isso vamos fazer: 
3.1. calcular o elemento mi1= - (ai1 / a11) , 1 i n; 
3.2. vamos somar à 2a equação a 1a , multiplicada pelo coeficiente m21, e colocar o 
resultado na 2a linha. Isto também não altera a solução do sistema; repetir para as 
equações abaixo, usando mi1 na i-ésima equação; 
3.3. calcular o elemento m12= - (a'i2/ a'22) ; 
3.4. repetir o passo 3.2 com as demais equações. 
 7
Para representar todas as mudanças vamos formar uma matriz com duas partes: a 1a 
será a matriz dos coeficientes e a 2a será o vetor dos termos independentes: 
B = (esta matriz se chama matriz aumentada). 
Todos os passos indicados serão realizados sobre B, e assim economizamos tempo e 
simplificamos a notação: 
Passo 1: Com m21 = -1/3 zeramos o elemento da posição (2,1): 
 
Passo 2: Com m31 = - 2/3 zeramos o elemento da posição (3,1): 
 
Passo 3: Com m32 = - (a'32/ a'22)= -2/7 zeramos o elemento da posição (3,2): 
 
A matriz final será: 
B' = Então x3 = (45/21)/(45/21) = 1. 
Voltando à penúltima linha B', teremos: 
(7/3) x2 + (2/3) x3 = 3 e como x3 = 1; 
(7/3) x2 + (2/3) = 3 ; x2 = 1. 
Da 1a linha vem: 
3x1+ 2x2 + x3 = 6 e como x2 = x3 = 1: 
3x1+ 2 + 1 = 6 ; x1= 1. 
 8
A solução final é dada pelo vetor X= (1 1 1)t. 
2.2 - Método de Eliminação de Gauss-Jordan 
Este método é uma complementação ao método de Gauss. Ele transforma o sistema 
dado em um outro diagonal, isto é, onde todos os elementos fora da diagonal são nulos. 
O método de Gauss exigia apenas que se chegasse à forma triangular. Veremos com o 
exemplo anterior como funciona o método de Gauss-Jordan. 
Como vimos o sistema (1.1) tem a matriz aumentada: 
B = 
Então procuraremos chegar a outra matriz, com os passos do método anterior, com a 
forma diagonal: 
B = , que será associada a um sistema da forma: 
 
Isto quer dizer que se conseguirmos chegar da matriz B à matriz B', a solução do 
sistema é imediata. Podemos, ainda, dividindo cada linha pelo elemento da diagonal, 
chegar à matriz identidade. 
Por exemplo: 
a) 
b) 
c) 
 9
d) 
e) 
f) 
Observações: 
(1) Eliminamos de uma só vez o 1o e 3o elemento da 2a coluna, fazendo: 
- 1a linha nova = 1a linha antiga - 2/3 da 2a linha; 
- 3a linha nova = 3a linha antiga - 2/3 da 3a linha; 
(2) Eliminamos o 1o e o 2o elemento da 1acoluna, fazendo: 
- 1a linha nova = 1a linha antiga - 3/21 da 3a linha; 
- 2a linha nova = 2a linha antiga - 2/7 da 3a linha. 
Assim o sistema resultante será: x1 = 1; x2 = 1; x3 = 1 ou seja , temos diretamente a 
solução exata do sistema. 
2.3 - Método de Gauss-Jordan na Inversão de Matrizes 
Uma análise rápida do método de eliminação de Gauss nos mostra que, ao invés de 
resolvermos um sistema completo da forma (1.1), resolvemos, na realidade, um sistema 
triangular da forma (1.3). Isso quer dizer que, a partir do sistema dado, geramos outro, 
que conserva suas soluções originais. 
De um modo mais formal, podemos dizer que saímos de um sistema geral 
(2.3) AX = B 
e chegamos a outro sistema 
(2.4) A' X = B' 
cuja matriz A' é triangular, mas as soluções são as mesmas que do sistema (1.1). 
Naturalmente a passagem de uma forma à outra não pode ser arbitrária. Para termos a 
garantia de que as raízes são preservadas só permitimos operações elementares sobre as 
linhas do sistema. Cada uma dessas operações, como veremos abaixo, equivale à 
 10
multiplicação da matriz do sistema por uma matriz elementar. Assim, a cada 
transformação fica definida uma certa matriz Gi e temos: 
(2.5) A1 = G1.A, A1 = G2.G1 A, . . ., A1 = Gk . . . G2.G1.A 
Quando, para um certo k, Ak for triangular, teremos: 
(2.6) A' = Ak . 
Naturalmente, se modificamos um dos membros do sistema, também deveremos 
modifcar o outro, isto é: 
Gk . . . G2.G1.A.X = Gk . . . G2 G1.A.B 
(2.7) A'.X = B' A' = Gk. . . G2.G1.A 
B' = Gk. . . G2.G1.B 
No caso do método de Gauss-Jordan, essas multiplicações são extendidas de modo a se 
formar no fim do processo a matriz identidade ou seja: 
Gm . . .G2.G1.A.X = Gm . . .G2.G1.B 
(2.10) Gm . . .G2.G1.A = I 
Gm . . .G2.G1.B = B'', m > k 
I.X = X = B'' 
Este resultado é o que nos permite utilizar o método de eliminação para inverter 
matrizes: 
A.X = B 
Gm . . .G2.G1.X = I.X = X = B'' = Gm . . .G2.G1.B 
e, já que I.X = X = B'' e X = , verificamos que se fizermos o produto Gm . . 
.G2.G1 teremos, na realidade, calculado a matriz . Assim, criamos um algoritmo que 
calcula : 
Seja a mariz aumentada 
(2.11) A1 = ( A | I ) 
Vamos multiplicar A1 por G1 ,G2 , . . ., Gm 
Então: 
Gm . . .G2.G1.( A| I ) 
 11
= (Gm . . .G2.G1.A | Gm . . .G2.G1.I ) 
= ( I | Gm . . .G2.G1 = ) 
e claro, o produto Gm . . .G2G1 = fica automaticamente determinado. 
Exemplo 1.6 
Seja A = Vamos calcular a sua inversa. Então: 
 
Então: = = 1/4. 
Observação: algumas vezes todas as tentativas que fazemos para levar a matriz A na 
matriz identidade são infrutíferas. Acontece que a inversa de A pode não existir. Para 
evitar isso, basta verificar se det(A) é diferente de 0. 
Por exemplo, a matriz 
A = pela eliminação de Gauss-Jordan é levada em 
A = . 
 12
Como se pode verificar é impossível obter do lado esquerdo a matriz identidade; mas 
det(A)=0 e A não tem inversa. 
2.4 - Fatoração de A 
Observamos que no caso do método de Gauss, podemos transformar uma dada matriz A 
em outra A', triangular superior. Vamos agora, explicitar o que acontece com as 
matrizes Gi definidas anteriormente, obter um novo método direto, chamado método 
compacto de Banachievicz ou Doolittle. Ele representa a fatoração da matriz A no 
produto L.U onde L é triangular inferior e U triangular superior, isto é, A = L.U. 
Vejamos como isso funciona. 
Consideremos o produto, G = Gm . . .G2.G1 , onde cada Gi é triangular inferior da 
forma: 
G i = 
Então, o produto G dessas matrizes também será triangular inferior com diagonal de 
elementos 1. Além disso, desde que existe (pois det Gi = 1) também existirá a 
inversa : 
 
Observando-se a forma das matrizes : 
= 
 13
podemos escrever que também é triangular inferior, com elementos 1 na diagonal. 
Assim, após a triangularização de A, teremos: 
Gm . . .G2.G1.A = A' , ou seja, 
G.A = A', e A = .A'. 
Logo, chamando de L e A' de U, teremos decomposto a matriz A em um produto de 
duas matrizes L e U, respectivamente triangular inferior e superior. 
Esse método usa o fato de que é possível determinar duas matrizes L e U tais que seu 
produto seja A e determinar essas matrizes diretamente. 
Se X é a solução do sistema A.X = B , então desde que A = L.U, temos: L.U.X = B. 
Escrevendo: U.X = Y e L.Y = B, 
vemos que reduzimos a solução do sistema original na solução de dois subsistemas 
interligados, ambos com matrizes triangulares o que facilita sua solução. Consideremos, 
então, as matrizes L e U na sua forma geral: 
L = U = 
Então, a igualdade L.U = A, feita diretamente nos dará o valor dos l's e dos u's , de 
acordo com os produtos: 
(2.12) 
(2.13) 
(2.14) 
(2.15) 
 14
(2.16) 
(2.17) 
e assim, sucessivamente vamos determinando os l's e u's que definem L e U. 
Observação: as condições u11diferente de 0, . . . , unn diferente de 0, são equivalentes à 
exigência det (Ak) diferente de 0, onde Ak, k = 1, . . ., n, são as sucessivas matrizes 
obtidas de A ao longo da diagonal: A11 = (a11); etc. 
Exemplo 1.7 
A = L = e U = 
Então: 
L = e U = 
2.5 - Método de Crout 
Da mesma forma que fatoramos A em um produto L.U, fixando os elementos lii = 1, 
podemos escrever A = L.U onde, agora fixamos os elementos uii = 1, fazendo com 
sejam calculados no processo. Essa fatoração recebe o nome de método de Crout e sua 
utilização é a adaptação, para esse caso, do método anterior. No exemplo 1.7 a aplicação 
do método de Crout daria: 
 15
L = e U = 
e a obtenção dos lij e uij se dá de forma análoga. 
2.6 - Fatoração de Matrizes Reais Simétricas e Positivo-Definidas 
Em certos casos, a fatoração da matriz A apresenta vantagens. Por exemplo, se A for 
real, simétrica e positivo-definida a fatoração é bastante facilitada e conhecida como 
método de Cholesky. 
Se A é positivo-definida, então: 
(A.X , X) = 
qualquer que seja X , X diferente de 0 (estamos trabalhando com A real). Uma das 
características dessas matrizes é que todos os determinantes de ordens desde 1 a n 
definidos sobre sua diagonal são positivos: 
 
Essas matrizes, quando são reais e simétricas, admitem uma fatoração mais simples, da 
forma 
A = L Lt 
que utiliza apenas a matriz triangular L. O procedimento de obtenção dos elementos (lij) 
de L é o mesmo dos métodos anteriores, levando-se em consideração o fato de que U = 
Lt. Nesse caso podemos definir o algoritmo: 
a)Podemos garantir que L11 é real pois, desde que A é positivo-definida, temos que a11 > 
0. O mesmo acontece com as demais raízes que ocorrem nos passos abaixo: 
b) 
 16
c) 
2.7 - Conclusão 
Apresentamos os métodos diretos, e estes, após um certo número de operações 
fornecem a solução exata de um sistema, pelo menos teoricamente. Isto porque, quando 
fazemos muitas divisões e multiplicações, introduzimos erros de arredondamento 
produzidos pelo computador. Por isso, os métodos diretos só são indicados para o caso 
em que temos um sistema pequeno, de modo que, em sua solução tenhamos de fazer um 
número reduzido de operações; senão a solução que vamos obter muitas vezes se afasta 
da solução real. 
Para os sistemas maiores, esse efeito diminui com outros métodos que garantem em 
certos casos, qualquer precisão desejada. Estes métodos são chamados métodos 
iterativos, onde usamos uma aproximação inicial da solução e a melhoramos quantas 
vezes sejam necessárias para chegarmos a uma precisão satisfatória. 
2.8 - Exercícios Propostos 
1) Seja (métrica em R) 
Mostre que T é um operador de contração. 
2) Inverta a matriz com o método de Gauss-Jordan. 
3) Mostre que o algoritmo Xn+1 = Xn ( 2.I - A.Xn ) permite aproximar a inversa de 
uma matriz (nxn). 
4) Construa uma matriz M(4x4) real redutível . Em seguida resolva o sistema MX = Y 
reduzindo-o a dois subsistemas. 
Obs : Yt = (1,1,1,1) 
5) Considere o seguinte sistema: 
5x + y = 13500 
x + 5y -(3/2)z + w = 11250 
x + y + 5z = 12000 
 17
(1/2)x - y + w = 4250 
a) Utilizando determinante, verifique se o sistema tem solução. Se existe, ache-a por 
eliminação Gaussiana. 
b) O sistema acima pode ser escrito da forma A.X = Y . Utilizando a inversa de A 
resolva-o. 
6) Sem realizar a decomposição, mostre que é possível decompor M, abaixo, no produto 
Ut.U ( U triangular superior) e, em seguida determine a matriz U. 
 
7) Resolva o sistema AX = B, onde A e B são dados abaixo, usando o fato de que A é 
redutível. 
 
8) Inverta a matriz A, usando a partição indicada: 
 
9) Usando a fatoração de A em L.U , resolva o sistema AX = B 
b) Determine a inversa de A 
c) Defina a matriz M = Mi.Mi-1 ..... M2.M1 que leva a matriz A em sua inversa (são 
matrizes elementares) 
 
 18
3. MÉTODOS ITERATIVOS PARA SISTEMAS 
LINEARES 
3.1 Solução Iterativa 
Até agora procuramos resolver um sistema linear obtendo a solução exata (pelo menos 
teoricamente), combinando suas linhas. Há, entretanto, algumas dificuldades quando 
devemos calcular a solução de um sistema de grandes proporções. O grande volume de 
operações de multiplicação e de divisões agrega, a cada passo, erros de truncamento 
que, somados ao longo do processo, podem nos levar a soluções absolutamente falsas. 
Assim sendo, a grande simplicidade de tais métodos perde-se na possibilidade do 
acúmulo incontrolável de erros. 
A maneira de se superar essa dificuldade é definir novas famílias de métodos, agora 
iterativos, à semelhança do que é feito na determinação de raízes de uma função 
algébrica f(x), isto é, na solução de f(x) = 0. Vamos, pois, generalizar o procedimento 
usado nesse caso, passando de uma função algébrica a uma equação matricial F(X) = 0 
da forma 
(3.1) F(X) = A X - B 
onde A é uma matriz (n x n) , X e B vetores de n componentes. 
Da mesma forma usada para a solução da equação f(x) = 0, transformamos a equação 
(3.1) na forma iterativa 
(3.2) 
onde H é chamada matriz de iteração do método definido e X é o vetor solução. Então, 
resolver iterativamente um sistema linear significa buscar um vetor X tal que aplicado à 
equação (3.2), defina uma identidade. Isto é, estamos procurando um vetor X que seja, 
ao mesmo tempo, raiz de F e ponto fixo de . 
Vamos, inicialmente, definir alguns métodos iterativos, e posteriormente verificar, suas 
condições de convergência. 
 19
3.2 - Métodos de Jacobi e Gauss-Seidel 
A forma mais simples de se determinar a matriz H, a partir do sistema Ax = b é a 
seguinte: 
Seja A a matriz do sistema, da forma 
A = (3.3) 
Vamos supor que A foi reordenada de modo que todos os seus elementos da diagonal 
sejam não-nulos: 
. 
Vamos então tirar o valor de cada xi na i-ésima equação (i = 1, 2, . . ., n). Como 
assumimos que aii é não nulo, podemos escrever: 
 
Se considerarmos o lado esquerdo do sistema como os elementos de um novo passo de 
iteração (k+1) e os elementos do lado direito como elementos do passo anterior (k), 
teremos: 
 
e então: 
representam os dois vetores que aproximam a solução do sistema, respectivamente na 
iteração k+1 e k. K é um vetor constante da forma K = ( b1 / a11 b2 / a22 . . . bn / ann) e 
 20
J é a matriz que define o processo iterativo. Neste caso, esse processo é o chamado 
Método Iterativo de Jacobi e, por isso, a matriz J é chamada de Matriz de Iteração de 
Jacobi e tem a forma 
J = (3.5) 
Exemplo 3.1 
Vamos resolver o sistema : 
2.x1 + x2 = 5 
x1+ 2.x2 = 4 
Tiramos inicialmente o valor de x1 na primeira equação e de x2 na segunda equação: 
x1 = (5/2) - (1/2) x2 x1= 0.x1 - (1/2).x2 + 5
{ ou {
(3.6)
x2 = 2 - (1/2) x1 x2 = - (1/2).x1 + 0.x2 + 2
Assim escrevemos o sistema na forma matricial X = J X + C , onde: 
X = , J = , C = 
Agora façamos o seguinte: 
1. Chamamos de e as aproximações iniciais (arbitrárias, como vamos ver 
posteriormente) das componentes de X, ou seja, definimos um vetor : 
 
2. Aplicamos do lado direito do sistema (3.6) obtendo um novo valor para x1 e x2. 
Digamos que escolhemos = = 0; assim obtemos os valores: 
 
 
 21
3. Usamos estes valores novamente no sistema (3.6) obtendo os valores: 
 
4. O próximo passo será: 
 
5. Para os demais: 
etc... 
Como vemos, o valor das componentes de X(i) vão se aproximando da solução exata, 
x1 = 2 e x2 = 1, na medida em que vamos calculando novas iterações. Como já 
dissemos anteriormente, esse método é chamado Método Iterativo de Jacobi e a matriz J 
é a sua matriz de iteração. 
Podemos, entretanto, introduzir uma variação na escolha dos índices (k) e (k+1), 
caracterizando um novo processo iterativo. Com o intuito de aproveitar os valores já 
encontrados em em passo da iteração, faremos a seguinte modificação no método de 
Jacobi: 
vemos que ao calcularmos o valor x2(1) na primeira iteração, dispomos do valor x1(1) 
que já foi calculado antes e que, assim, poderá ser usado no lugar de x1(0). 
Analogamente, no cáculo de x3(3) temos os valores de x1(2) e x2(2) que poderão ser 
usados. E assim por diante. 
Com esta modificação introduzida, temos o Método Iterativo de Gauss-Seidel. Então, 
para qualquer iteração o sistema (3.4) ficará: 
 
Nesse caso a matriz de iteração será obtida substituindo-se diretamente os valores que 
vão sendo calculados, isto é, depois do cálculo de x1(1) substituimos esse valor na 
avaliação de x2(1); em seguida, na avaliação de x3(1) já podemos usar esses valores que 
já foram atualizados, x1(1) e x2(1). Assim, vamos atualizando os valores obtidos, 
 22
durante o próprio passo da iteração. Isso significa que não damos um passo completo 
com os valores (k) do passo anterior, como no Método de Jacobi e sim, vamos usando 
as modificações feitas imediatamente. Deste modo, temos: 
 
Vejamos, com um exemplo simples, a forma da matriz desse método iterativo. 
Exemplo 3.2 
Para o sistema : 
2.x1 + x2 = 5 
x1 + 2.x2 = 4 
separamos as variáveis x1 e x2 da seguinte forma: 
x1 = 5/2 - 1/2.x2 
x2 = 2 - 1/2.x1 
escolhemos os índices da iteração k e k+1: 
 
Então, a matriz de Gauss-Seidel (R1) é obtida desse sistema, observando-se que 
devemos ter : 
 
 
 
 
 23
3.3 - Estudo da Convergência dos Métodos de Jacobi e 
Gauss-Seidel 
Como vimos, métodos iterativos têm a forma X = H X + K onde H é uma matriz (n x n) 
e K n é um vetor. 
A partir de uma aproximação inicial x(0), fazemos as iterações: 
 
e, de modo geral, . 
Fica fácil verificar que esta sequência irá convergir se , (com a norma 
definida no problema dado),pois, neste caso, a k - ésima aproximação vai estar tão 
próxima do valor exato do vetor X quanto se queira. Caso contrário diverge. 
Da mesma forma que no problema f(x) = 0, precisamos de condições gerais de 
convergência para a aplicação desses métodos iterativos a sistemas lineares. Mas, como 
estamos tratando com matrizes, essas condições tornam-se mais complexas. 
Vejamos, inicialmente, como se comporta a propagação do erro nesses casos. Seja U 
solução exata do sistema dado. Então, por definição, U = HU + K. Assim, o erro no 
passo k será dado por: 
 
onde, é o erro inicial. 
Fica, portanto, claro que o acúmulo de erro em cada passo, cresce com a potência da 
matriz de iteração H, isto é, se cometemos um erro inicial , o erro final, na k-ésima 
iteração será de . Assim, se tender a zero à medida que k cresce, podemos 
esperar que o erro diminua. Caso contrário certamente vamos ter resultados 
desastrosos, pois não nos aproximaremos nunca do valor exato de U, já que poderá 
ser maior que , para todo k. 
Vamos examinar a condição necessária para que . Um dos resultados da 
Álgebra Linear* nos diz que essa condição se verifica se e somente se todos os 
autovalores de H forem, em módulo, menores que um. Resta-nos, então definir esses 
novos elementos, isto é, os autovalores de uma dada matriz. 
 
 24
Definição 3.1 
Dada uma matriz A, dizemos que o escalar é seu autovalor, se existir um vetor x 
diferente de 0, tal que . Nesse caso dizemos que x é autovetor de A associado 
a . 
Obsevação: Quando é possível diagonalizar uma matriz, os elementos que vão aparecer 
na diagonal da nova matriz serão exatamente seus autovalores. A determinação desses 
números é feita a partir da própria definição. Seja ; 
então: 
(3.8) 
é um novo sistema linear homogêneo, obtido do antigo, e que mantém suas soluções 
originais. Sabemos que um sistema homogêneo só tem solução não trivial x diferente de 
0, quando o determinante da matriz do sistema for nulo. No nosso caso a matriz do 
sistema é . 
Então a equação 
det = 0 (3.9) 
representa um polinômio e as suas raízes são os autovalores de A. 
Definição 3.2 
Dizemos que duas matrizes A e B são similares, se existe uma matriz M, inversível, tal 
que . Quando isso acontece, dizemos que M define uma transformação de 
similaridade. Nesse caso, as matrizes similares têm os mesmos autovalores, isto é, a 
similaridade preserva autovalores de uma matriz. 
Exemplo 3.3 
Calcular os autovalores de A = . 
 
 
 
Voltemos à nossa matriz H, supondo que ela possui todos seus autovalores distintos 
(quando houver autovalores de multiplicidade maior que um, o estudo se torna um 
 25
pouco mais complexo). Então, sabemos que existe uma tranformação de similaridade 
que leva a matriz H na sua forma diagonal M, isto é: 
, M é a matriz diagonal onde (autovalores de H). 
Então: 
Assim se , teremos também . Mas desde que: 
(3.10) 
e o limite acima tende a zero se somente se . 
Logo, se os autovalores de H (que são os mesmos de M, pois elas são matrizes 
similares) têm módulos menores do que um, a matriz vai tender à matriz nula e 
assim, o erro vai tender a zero. 
Definição 3.3 
Sejam (i autovalores de uma matriz A tal que . Então , é 
chamado raio espectral de A. Podemos, então, apresentar o seguinte teorema sobre 
condições necessárias e suficientes para a convergência de um processo iterativo para a 
solução de sistemas lineares. 
Teorema 3.1 
O método iterativo converge à solução U, qualquer que seja o vetor 
inicial X0, se e somente se . 
Exemplo 3.4 
Sendo a matriz A = , as matrizes de iteração serão: 
 
Logo a iteração de Jabobi converge e a de Gauss-Seidel diverge. 
 26
3.4 - Obtenção Geral de Métodos Iterativos 
Vamos ver, agora, como explicar, matematicamente, a obtenção dos métodos de Jacobi 
e Gauss-Seidel. Em seguida, apresentamos outro método iterativo, a Sobre-Relaxação. 
Consideremos, novamente, o problema AX = B ou, equivalentemente: 
F (X) = B - A X, F (X) = 0 
Sabemos que para resolvê-lo iterativamente devemos definir uma função de iteração 
tal que: 
 
tenha como ponto fixo a solução U do problema considerado. 
Voltado ao parágrafo anterior, vemos que o método de Jacobi pode ser obtido do 
sistema (3.4.a), onde a matriz J ou matriz iteração de Jacobi tem a forma (3.5). Vejamos 
agora, como interpretar matricialmente esse resultado. Consideremos o sistema dado 
reescrito da seguinte forma, sendo A desdobrada como segue: 
A= D - E - F, (D - E - F) X = B (3.11) 
onde: 
* D é a matriz diagonal formada pelos elementos diagonais de A; 
* E é a matriz triangular estritamente inferior, formada pelos simétricos dos elementos 
da parte triangular inferior de A; 
* F é a matriz triangular estritamente superior, formada pelos simétricos dos elementos 
da parte triangular superior de A. 
Então, podemos separar em duas partes a equação (3.11), obtendo: 
D X = (E + F) X + B 
ou, supondo que existe o inverso de cada elemento de D: 
(3.12) 
Comparando essa última expressão (3.12) com a (3.4.a) vemos que se considerarmos a 
iteração 
(3.13) 
ambas representam o mesmo processo. Isso quer dizer que a matriz de Jacobi tem a 
forma: 
 
 27
ou, se fizermos (3.13-a) 
Da mesma forma podemos definir a matriz do método de Gauss-Seidel. Basta que a 
partir de (3.12), consideremos a característica fundamental desse método, isto é, os 
elementos já calculados em um passo são imediatamente aproveitados no próximo 
passo. Olhando o sistema (3.7) podemos verificar que isso é representado pela iteração: 
(3.14) 
ou seja, usando L e U e reescrevendo temos: 
 
o que fornece: (3.15) 
desde que, (I - L) certamente é inversível (verifique que essa matriz é triangular inferior 
com diagonal formada de elementos iguais a 1 e, assim det(I - L) = 1 e ela tem inversa). 
Assim, a matriz de iteração do método de Gauss-Seidel é dada por: 
(3.16) 
 
3.4.1 - Algoritmo de Sobre-Relaxação 
Vejamos agora como podemos obter um método que generaliza o método de Gauss-
Seidel. Consideremos a equação: 
(3.17) 
onde ( é um parâmetro usado para que se possa tentar obter convergência mais rápida 
que o método de Gauss-Seidel. Observando-se a equação (3.18), vemos que ela 
apresenta como solução as próprias soluções do sistema original A X = B, isto é, H(X) 
= 0 e F(X) = 0 têm as mesmas raízes. Assim se escrevermos 
 
estaremos definindo um processo iterativo que pode nos levar às raízes de F. 
Da mesma forma que anteriormente, separamos A em três matrizes independentes: 
 
Considerando agora, iterações do tipo realizadas pelo algoritmo de Gauss-Seidel, 
podemos obter: 
 28
 
isto é: 
 
ou seja: 
(3.19) 
pois (como você pode verificar) a matriz tem inversa. 
A equação (3.19) fornece assim, a expressão da matriz da Sobre-Relaxação: 
(3.20) 
É fácil verificar que se tivermos , essa matriz se reduz a R1, a matriz de Gauss-
Seidel. 
Exemplo 3.5 
Aplique a Sobre-Relaxação a um sistema de três equações e três incógnitas. 
Naturalmente, para usar na prática a Sobre-Relaxação, não é necessário a definição 
matricial de . Podemos fazer diretamente: 
 
Para: ,teremos: 
 
e sucessivamente continuamos o cálculo para k = 1, 2, . . . 
 
 
 29
3.4.2 - Convergência da Sobre-Relaxação 
Consideramos a iteração: 
definida sobre o problema AX = B. 
Já vimos que, sendo U solução desse problema, podemos ter certeza de que: 
 
e o erro cometido na k-ésima iteração será dado por: 
 
Assim, como já foi visto, a convergência desse processo se dará quando a potência k de 
H tender a zero, à medida que k cresce infinitamente. Já vimos também que esse fato se 
dá quando os autovalores de H têm módulo menor que 1. Vejamos então, como se 
comportam os autovalores da matriz de iteração da sobre-relaxação, 
(3.21) 
Já vimos anteriormente que, o determinante de uma matriz é igual ao produto de seus 
autovalores. Para , esse resultado fornece: 
 
mas, (3.22)pois é triangular inferior, com elementos diagonais iguais a 1. O mesmo 
acontece com sua inversa, (verifique!). O valor de é obtido 
facilmente, se verificarmos que essa matriz é triangular superior, com elementos 
diagonais todos iguais a . Assim: 
(3.23) 
De (3.22) e (3.23) temos que: 
Chamamos de o raio espectral de , podemos escrever por definição que: 
 
Assim: . 
Para garantirmos a convergência de um processo iterativo definido com a matriz H, já 
vimos que é necessário e suficiente que: . 
 30
Logo, a sobre - relaxação converge se , pois nesse caso: 
. 
Podemos resumir esse resultado no seguinte teorema: 
Teorema 3.2 
O método da Sobre-Relaxação converge sempre que . Existem famílias muito 
importantes de matrizes para as quais, por condições de convergência w deve assumir 
valores, apenas entre 1 e 2. Por isso o processo é chamado de Sobre-Relaxação. 
Exemplo 3.6 
Para o sistema (3.1), a solução com uso da sobre - relaxação, seria: 
 
Considerando-se, por exemplo, w = 1,05, teremos: 
 
e assim sucessivamente. O valor de w deve ser escolhido de forma a diminuir o erro e 
algumas vezes isso pode ser facilmente feito. Vide P. Albrecht [1], pág. 105, 112 e 113. 
 
3.5 - MÉTODOS BLOCO ITERATIVOS 
Suponhamos que seja particionada em blocos da forma: 
(3.24) 
onde , são quadradas e regulares com . Se 
aplicarmos os métodos iterativos apresentados no item anterior, ao sistema 
 31
 
chegamos a novos métodos iterativos que têm a forma: , onde 
(3.25) 
 
O índice B indica uma certa partição em blocos da matriz, usada quando temos 
particular interesse nesta partição. 
: matrizes bloco triangular estritamente inferiores; 
: matrizes bloco triangular estritamente superiores; 
chegamos às fórmulas Bloco Jacobi, Bloco Gauss-Seidel e da Bloco Sobre-Relaxação, 
que serão apresentadas em seguida. Em cada passo k é preciso resolver n sistemas 
lineares por métodos diretos, pois a inversão de Db não se reduz mais a uma simples 
divisão, como ocorria nos métodos não blocos. 
Em geral é aconselhável calcular as inversas antes do início da iteração, para facilitar 
a resolução dos n sistemas em cada passo. Entretanto, se são tridiagonais, prefere-se 
a resolução sucessiva pela eliminação de Gauss. Esse caso especial é frequente no 
tratamento da equações diferencias parciais: os chamados métodos linha (line-methods), 
são exemplos típicos para a combinação da iteração bloco com a eliminação de Gauss. 
3.5.1 - Iteração Bloco Jacobi 
Com: , obtemos: 
(3.26) 
Definição 3.3 
A matriz é chamada matriz bloco de Jacobi. 
 
 
 32
Exemplo 3.7 
(3.27) 
separando os subsistemas, como se eles fossem independentes, chegamos a: 
 
e resolvendo-se cada um desses subsistemas, isoladamente, tem-se: 
 
Esta é a iteração: com 
 
Exemplo 3.8 
Verifiquemos a convergência do método bloco iterativo de Jacobi do sistema 
 
cuja matriz bloco é: 
 33
(3.28) 
Então: 
(3.29) 
. 
Então, para esse sistema, a partição em blocos indicada favoreceu a convergência, isto 
é, o método bloco de Jacobi deve convergir mais rápido que o método simples. 
3.5.2 - Iteração Bloco Gauss-Seidel 
Com: , obtemos: 
(3.30) 
(3.31) 
Definição 3.4 
A matriz é chamada matriz bloco de Gauss-Seidel. 
3.5.3 - Bloco Sobre-Relaxação 
Com: , obtemos: 
(3.32) 
(3.33) 
Definição 3.5 
A matriz é chamada matriz bloco da Sobre-
Relaxação. 
Como vantagem da iteração bloco citamos: 
 34
1. São aplicáveis quando o sistema é grande demais para ser armazenado na memória do 
computador. 
2. Em certos casos converge mais rapidamente do que os métodos de iteração simples. 
 
3.6 - Teoremas de Comparação e Condições Suficientes 
para Convergência 
Geralmente, não é possível afirmar, a priori, qual dos métodos iterativos apresentados é 
o melhor. No entanto, em alguns casos especiais é possível estabelecerem-se critérios de 
comparação entre os métodos e condições suficientes para a convergência, que são de 
aplicação relativamente simples e facilitam a decisão prévia pelo melhor método . 
Assim sendo, serão examinados a seguir os seguintes casos particulares: 
(a) A matriz J ( de Jacobi, de bloco ou não) associada à matriz A é não-negativa: J 0. 
(b) A matriz A do sistema é de diagonal estritamente dominante ou de diagonal 
dominante e irredutível. 
(c) A matriz A é hermitiana. 
3.6.1 - Matrizes de Jacobi Não-Negativas 
Seja J = L + U 0 a matriz de Jacobi associada à matriz A do sistema Ax = B; então, 
podemos comparar a convergência dos métodos de Jacobi e Gauss-Seidel pelo seguinte 
teorema de Stein e Rosenberg: 
Teorema 3.3 
Sejam J, R1 (n,n) as matrizes ( blocos ou não) de Jacobi e Gauss-Seidel 
respectivamente, com : 
J = L+U 0 , U0 , L0 
Então, se: 
(a) (J) 1, tem-se (R1) (J) 
(b) (J) =1, tem-se (R1) = (J) 
(c) (J) 1, tem-se (R1) (J) 
Assim, sob as hipóteses deste teorema, ambos os métodos de Jacobi e Gauss-Seidel 
convergem ou divergem. Se convergem, o método de Gauss-Seidel converge 
assintoticamente mais rápido do que o método de Jacobi. 
 35
Limitamos a demonstração ao caso em que J é iredutível: 
Seja =(R1). Se =0, então, (J) < 1 e 
(J) = (L + U) > (L) = 0 pois U 0. 
Assim, (a) é satisfeita e pode-se, agora, considerar > 0. 
Como (I - L)-1 = I + L + .... + Ln-1 0 e U 0, tem-se: 
R1 = (I - L)-1 U 0 
Então, existe (vide Teorema 4.21) um y n tal que y 0 e R1y = y, donde: Uy = (I - L)y e, 
sendo 0: 
(U + L)y = y; (-1 U + L)y = y 
Como J é suposta irredutível e não-negativa, (U + L) e (-1 U + L) são irredutíveis e não-
negativas. Se fosse para z 0, w 0: 
(U + L)z = kz, k > ou ( -1 U + L)w = w, > 1, 
então z > 0, w > 0 e z y, w y logo: 
(U + L) = , ( -1 U + L) = 1 
- se 0 < < 1 : = (U + L) < (U + L) = (U + L) = (J) < ( -1U + L) = 1, 
- se = 1 : = (U + L ) = (J) = 1, 
- se > 1 : = (U + L) > (U + L) = (J) > (J) > > (-1 U + L ) = 1 
Usando a teoria das matrizes não-negativas pode-se também tirar conclusões sobre a 
vantagem da partição em blocos, através do seguinte teorema de Fiedler-Pták: 
Teorema 3.4 
Seja J = L + U 0 e R1b = (I - L -B)-1 (U - B), R1 = (I - L )-1 U , onde B (n,n) é uma 
matriz tal que : 
U - B 0 , B 0 , B 0 ; R1b 0; R1b 0. 
Então, se 0 < (J) < 1, tem-se (R1b) < (R1). 
Demonstração: Se k = (R1b) e = (R1), então existe um vetor x 0, x 0, tal que R1bx=kx , 
ou seja : 
(U - B)x = ( I - L - B ) kx, [k-1 (U - B) + (L + B)] x = x. 
Então, analogamente à demonstração anterior, tem-se: 
 36
[k-1 (U - B) + (L + B)] = 1; (-1 U + l) = 1 
Como 0 < < (J) < 1 tem-se: 
1 = (-1 U + L) = (-1 (U - B) + L + -1 B) >> (-1 (U - B) + L + B) 
Então: (k-1(U - B) + ( L + B)) > (-1(U - B) + L + B), donde se conclui que: k < 
Por este teorema vê-se que uma partição em blocos de A é apropriada para acelerar a 
convergência assintótica da iteração de Gauss-Seidel, se U B U, UB U. 
Teorema 3.5 
Sejam J, R( (n, n) as matrizes (blocos ou não) de Jacobi e da sobre- relaxação. Se J é 
irredutível, J = L + U 0 e (J) < 1, então: 
(a) R( converge para todo 0 < 1 
(b) (R(1) < (R(2) < 1, se 0 < 1 < 2 1 
Demonstração: 
(= B(-1 C( com B( = 1/ (I - L); C( = 1/ (U + (1 -)I). 
Seja 0 < 1 e S = B( - C(= I - J, então C( 0 e B( e S são regulares com B-1( 0, S-1 0. 
Logo, com B-1( C(= R( obtem-se: 
(R() =[ (S-1C()] / [1 + (S-1 C()] < 1, o que prova (a). 
S-1 = I + J + J2 + ... é irredutível, pois J é irredutível. Logo, para 0 < < 1, S-1C( é 
também irredutível pois C(= (cij) 0 e cij 0. 
Além disso, se 0 < 1 < 2 1, tem-se S-1 C(1 S-1 C(2 com C(1 > C(2 . 
Então: ( S-1 C(1 ) > (S -1 C(2) e, portanto, (b) fica provado. 
O Teorema anterior apresenta uma classe de matrizes para as quais a sub-ralaxação ( < 1 
) não é aconselhável. 
3.6.2 - Matrizes de Diagonal Dominante 
Definição 3.6 
Uma matriz A= (aij) (n,n) é dita de diagonal dominante se : 
(a) | aij | | aij | = r ij i= 1,2,. . .,n ( j ( i ) e 
(b) Existe, pelo menos, um k tal que : |ak k| > r kjA é dita de diagonal estritamente dominante se : 
 37
| aij | > | a ij | i= 1,2,. . .,n ( j ( i ) 
Teorema 3.6 
Seja A (n,n): 
(a) de diagonal estritamente dominante ou , 
(b) de diagonal dominante e irredutível. 
Então, tanto o método (não bloco) de Jacobi como o de Gauss-Seidel convergem. 
Demonstração: Para o caso (a), usando-se o Teorema de Gershgorin e para o caso (b) 
usando-se o Teorema já apresentado tem-se: ( | J | ) < 1. Então, segue: (J) ( | J | ) < 1 o 
que prova a convergência do método de Jacobi. Sendo L triangular inferior, obtem-se de 
R1 = (I - L)-1U : 
| R1 | = | (I + L+. . . +Ln-1) U | (I + |L| + . . .+|L|n- 1) |U| 
(I - | L| )-1 | U|= R1 
Como R*1 é a matriz de Gauss-Seidel, associada à matriz de Jacobi | J | , segue do 
teorema de Stein-Rosenberg e dos teoremas já apresentados: 
(R1) (|R1|) (R* i ) ( | J | ) < 1 
Como P= || J || L = máx. 1/|aii| . |aij| <1 no caso das matrizes de diagonal estritamente 
dominante, obtem-se a seguinte estimativa de erro da iteração de Jacobi, sendo ui as 
componentes da solução exata: 
máx | xi (k+1) - ui | __P__ máx = | xi (k+1) - xi (k) | i 1- P i 
Esta estimativa vale também no caso da iteração de Gauss-Seidel, se A é de diagonal 
estritamente dominante e P = R1L . 
3.6.3 - Matrizes Hermitianas 
Seja A (n,n) hermitiniana, positiva e definida e tal que A = B - C - C* onde B é positiva 
definida. Neste caso, pode-se demonstrar que a condição 0 < < 2 necessária para a 
convergência da sobre-relaxação também é suficiente: 
Teorema 3.7 (Ostrowski) 
Sob as hipóteses anteriores, a iteração: 
x (k + 1) = (B - C)-1 (C* + (1 - )B)x(k) + (B - C)-1 b 
converge para todo , com 0 < < 2. 
 38
Demonstração: Seja S = (B - C)-1 (C* + (1 - )B ). Deve-se demonstrar que: ( S)<1. 
Como : 
det (S - I) = det (B - C)-1 . det (C* + (1 - )B - (B - C)), 
então todos os autovalores de S são raízes de 
det (C* + (1 - )B - (B - C)) = 0. 
Seja x 0 um vetor tal que: 
[B - C]x = [C* + (1 - )B]x 
Multiplicando por 2/ e somando (A - B + C + C*) = 0 à expressão entre colchetes 
obtem-se: 
(2/ - 1) + (A + C* -C )]x = [ B (2/ - 1) - A + (C* - C)]x 
Como (C* - C)* = - (C*- C) é fácil provar que (x T(C*- C)x é imaginário puro para 
qualquer x0. 
Como: (x T Ax= a ; (xTBx = b ; (xT (C*-C)x = ic, obtem-se : 
[(2/w-1)b + a + ic] = [(2/w-1)b - a + ic] 
Então, se 0<W 
| | = |(2/w -1)b + ic - a| / |(2/w-1)b + ic + a | < 1 , pois (2/w-1) > 0, a>0 , b>0 
Como a sobre-relação (bloco ou não) é um caso particular da iteração obtem-se o 
seguinte Corolário : 
Corolário 3.1 
Seja A hermitiana e positiva definida. Então, a sobre-relaxação (bloco ou não) converge 
para todo 0 < w < 2. 
Pela multiplicação por A* sempre se pode reduzir o sistema Ax=B, det A0, a um 
problema com uma matriz hermitiana e positiva definida. Entretanto, este procedimento 
não é aconselhável porque, em geral, piora consideravelmente o condicionamento do 
sistema. 
Um caso especial das matrizes hermitianas e positivas definidas são as matrizes de 
Stieltjes. 
Definição 3.7 
Uma matriz A= (aij) (n,n) é chamada matriz de Stieltjes se A é simétrica, positiva 
definida e se aij 0 para todo ij. 
 39
Para essas matrizes pode-se decidir quando a iteração bloco de Gauss-Seidel converge 
assintoticamente mais rápido do que a iteração não bloco: 
Teorema 3.8 
Seja A uma matriz irredutível de Stieltjes. Se existe uma patição de A em blocos tal que, 
pelo menos uma das matrizes Aii contenha elementos não nulos fora da diagonal, então 
o método bloco de Gauss-Seidel converge assintoticamente mais rápido do que o 
método não bloco. 
A demonstração é baseada no Teorema já apresentado e no fato de que a inversa de uma 
matriz irredutível de Stieltjes é positiva. 
 
3.7 - Sobre-relaxação para Sistemas Consistentemente 
Ordenados 
O teorema de Stein-Rosenberg possibilita comparação da convergência assintótica do 
método de Jacobi com a do método de Gauss-Seidel, no caso de matrizes não-negativas. 
Neste parágrafo, o objetivo é comparar a convergência assintótica do método de Jacobi, 
com o da sobre-relaxação, estabelecendo uma relação entre os autovalores das matrizes 
J e 
Obtem-se, assim, uma possibilidade de estudar o efeito causado pela reordenação na 
matriz A à convergência assintótica da sobre-relaxação e de determinar o valor ótimo do 
parâmetro w. 
3.7.1 - Relação entre os Autovalores de J e Rw 
Sob quais hipóteses sobre J existe uma relação entre os autovalores de 
? 
Seja autovalor de , w não nulo. Então: 
. 
Dividindo por sendo q e r números naturais, segue : 
 
Com , obtem-se: 
 
 40
Portanto, se os autovalores de são independentes de a então, 
, são autovalores de L + U. 
Definição 3.8 
A matriz J é chamada consistentemente (r, q) - ordenada se os autovalores de 
são independentes de a. Chamaremos um sistema Ax = B 
consistentemente ordenado se a matriz de Jacobi de A for consistentemente ordenada. 
Reciprocamente seja autovalor de J = L +U e J consistentemente (r, q) ordenada. Então, 
segue-se de : 
 
que para qualquer a não nulo, especialmente para 
: 
 
Então, 
Se vemos que também são autovalores de 
J. 
Se satisfaz segue: 
 
Portanto, é autovalor de . 
Teorema 3.9 
Seja J consistentemente (r, q) - ordenada. Seja não nulo, um autovalor de e 
definido por : 
 
Então, é um autovalor da matriz de Jacobi J. Reciprocamente, se é um autovalor de J 
e se satisfaz à equação acima, então é autovalor de . 
Teorema 3.10 
Seja J consistentemente (r,q) - ordenada. Se é autovalor de J, então 
, também o serão. 
 
 41
Corolário 3.2 
Seja o sistema Ax = B consistentemente (r,q) - ordenado; então, ambas as iterações 
(bloco ou não) de Jacobi e Gauss-Seidel convergem ou divergem .Se convergem, então : 
 
Observa-se que esse corolário fornece, sob hipóteses diferentes, um resultado mais 
preciso do que o Teorema de Stein-Rosenbgerg. 
Do Teorema acima segue que a convergência assintótica da sobre-relaxação é a mesma 
para todas as (r,q) - ordenações (se existirem) de um sistema Ax = B. Antes, porém, de 
se estudar a influência de ordenação do sistema Ax = B em , deve-se estudar 
quais as matrizes que são consistentemente ordenadas. 
3.7.2 - Uma Classe de Matrizes Consistentemente (r-q) - ordenadas 
Não é fácil, em geral, determinar quando uma matriz J é consistentemente ( r,q) - 
ordenada ou quando existe uma ordenação consistente. Há, entretanto, uma classe 
importante de matrizes onde essas propriedades são facilmente reconhecidas : são as 
matrizes fracamente cíclicas. Essa propiedade é verificada considerando-se matrizes 
regulares S(a) tais que : 
r e q primos entre si. 
Obviamente J será consistentemente (r,q) - ordenada se existirem matrizes S(a) que 
satisfaçam à equação acima. Seja o caso especial : 
 
onde os Ij, j=0,1,...,n-1 são as matrizes identidade. Temos, com a partição induzida por 
S(a): 
 42
 
Logo, J é consistentemente (r,q) - ordenada se todas as sub-matrizes da matriz acima são 
nulas a menos das matrizes da r-ésIMA diagonal inferior e da q-ésIMA diagonal 
superior. 
Definição 3.9 
As matrizes acima são chamadas de matrizes 2-banda. 
Teorema 3.11 
Se J é fracamente cíclica de índice p, então existe uma matriz de permutação P tal que 
é consistentemente (1 , p-1) - ordenada. 
A reordenação (P é a matriz de permutação) de uma matriz A não influencia o 
raio espectral da matriz de Jacobi, pois se A tem a matriz de iteração de Jacobi, 
, então tem a matriz de Jacobi: 
 
Então, 
O raio espectral de matriz de sobre-relaxação depende, entretanto, da ordenação de 
A. Por esta razão pode-se meljhorar a convergência assintónica da sobre-relaxação pela 
reordenação do sistema em consideração. 
Ainda não existe uma teoria completa para decidir, no caso geral, qual reordenação do 
sistema Ax=B resulta na melhor convergência assintónica da sobre-relaxação. 
Entretanto, em dois casos particulares essa decisão é possível: 
(a) Se é simétrica,irredutível e , então pode-se demonstrar que a 
ordenação consistente, se existe, é a mais indicada de todas as reordenações da forma 
. 
(b) Se existem (r,q) - ordenações de J com diferentes valores de (r,q) ( como, por 
exemplo, no caso das matrizes fracamnte cíclicas) e se os autovalores de , 
 43
são negativos por exemplo, se J é simétrica e positiva definida), então a (1,p-1) - 
ordenação é a melhor quanto à convergência da sobre-relaxação. Isto é: 
Teorema 3.12 
Seja J consistentemente (r,q) - ordenada com e sejam o autovalores de 
, reais e não negativos. 
a) Se r é diferente de 1, então 
b) Se r=1, então onde o valor "ótimo" é a única 
raiz real no intervalo (1, q+1/q) da equação : 
 
Observações: 
-A relação (equação acima) possibilita a determinação do melhor parâmetro w da sobre-
relaxação, se os autovalores de J são conhecidos. 
-Como no caso das matrizes de Jacobi não-negativas, a melhor escolha é . 
 
3.8 - Exercícios Propostos 
1) Dado o sistema A X = B mostre que o método iterativo de Jacobi converge, onde 
 
2) Dadas as seguintes matrizes : 
 
 44
 
a) Construa a forma canônica de Jordan de A 
b) Calcule 
c) Aplique à matriz A o teorema de Gerschgorin (que localiza autovalores no plano 
complexo) 
d) Calcule , um autovalor qualquer de B = . Calcule um autovetor v de B , 
associado ao autovalor , que tenha norma igual a 2. 
3) Limite os autovalores das matrizes A1 , A2 , A3 dadas abaixo : 
; ; 
4) Com o método bloco da sobre-relaxação e com w = 1.1 , calcule a aproximação X1 
do sistema abaixo , com a partição indicada . Escreva também a matriz de iteração desse 
método. Use Xo = (0,-1,1,0)t . Verfique cuidadosamente a convergência . Seria possível 
garantir a convergência de algum método simples ? 
 
5) Considerando-se 
 45
e 
a) Usando o método da partição geral, calcule a inversa de A 
b) Resolva o sistema Ax = B usando a inversa calculada. 
6) Dadas as seguintes matrizes abaixo : 
 
a) Determine limites para todos os autovelores das matrizes A1 , A2 , A3 
b) Determine o maior autovalor , em módulo , da matriz A1 e o autovetor a ele 
associado. 
c) Usando o método das potências pelo menos uma vez, determine todos os autovalores 
de A3 
d) Determine os autovetores de A2 
7) Para a matriz 
a) Usando o método de Jacobi , pelo menos uma vez , determine os autovalores de 
b) Sabendo-se que = 5 é o maior autovalor de A1 , determine um autovetor unitário a 
ele associado 
c) Calcule o determinante de . 
 46
d) Escreva a forma canônica de Jordan de A1 
8) Considere as matrizes A1 e A2 abaixo. Com elas resolva os sistemas A1.x = b e A2.x 
= b , ( b1 e b2 também dados ) com os métodos ( A1 e A2 são 60 X 60 ) : 
a) Eliminação de Gauss , sem pivoteamaneto 
b) Eliminação de Gauss , com pivoteamaneto 
c) Crout 
d) Iteração de Jacobi 
e) Iteração de Gauss-Seidel 
Para cada método e cada matriz , imprima a solução obtida e o erro absoluto (a solução 
os dois sistemas é Xi = 1 ) 
Compare os resultados. 
 
 
b1 = ( 6 , 7 , 7 , .... , 7 , 7 ,7 , 6 )t; b2 = ( 7 , 7 , 7, ... , 7 ,7 ,7 , 6 ,6 )t 
 47
9) Verifique a convergência do método bloco de Jacobi aplicado ao sistema Ax = b 
dado por: 
 
Calcule a 2a aproximação da solução. 
10) Usando w = 1,2 calcule a 2a aproximação da solução do sistema abaixo, com a 
sobre-relaxação. Verifique a convergência. 
 
11) Dado o sitema Ax = B abaixo, aplicamos a ele o método da sobre-relaxação, 
também definido abaixo: 
 
Algoritimo: 
a) Determine a matriz , de iteração da sobre-relaxação. (Obs. indique todos os 
cálculos realizados) 
b) Considerando para a norma || || = e levando em conta que 
, verifique se para w1=1 e w2=1.04 a convergência da sobre-relaxação 
se verificará. (Obs. indique todas as suposições e conclusões) 
12) Resolva o sistema pelo método iterativo de Gauss-Seidel. Faça 4 iterações a partir 
de Xo = (0,0,0,0)t. 
 48
 
13) Para o sistema AX = b, onde A e b são dados abaixo, com a partição indicada, com 
Xo =0 , calcule X2 com o método bloco de Jacobi. Em seguida, examinando as matrizes 
de iteração desse método bloco e do método simples de Jacobi, determine o que 
apresenta melhor convergência assintótica. 
 
14) Dada a matriz 
 
a) Determine os autovalores e autovetores da matriz A , abaixo , usando o método das 
potências . 
b) Para a mesma matriz A , resolva o sistema Ax = b com o método bloco de Gauss-
Seidel Onde b = (1,1,1,1)t. 
c) Verifique a convergência do método aplicado no item anterior . 
15) Seja o sistema Ax = B dado por : 
 
 
 
 49
a) Com a iteração definida pela fórmula: 
 
Calcule a aproximação X(1) da solução u do sistema. 
Use w = 1.08 ; X(o) = (1,1,1)t 
b) Se tivermos w=1, que método iterativo será definido?