ALGEBRA LINEAR NUMÉRICA

Prévia do material em texto

Notas de Aula
A´lgebra Linear Nume´rica
Rodney Josue´ Biezuner 1
Departamento de Matema´tica
Instituto de Cieˆncias Exatas (ICEx)
Universidade Federal de Minas Gerais (UFMG)
Notas de aula da disciplina A´lgebra Linear Nume´rica do Curso de Graduac¸a˜o
em Matema´tica Computacional, ministrado durante o segundo semestre do ano de 2009.
30 de novembro de 2009
1E-mail: rodney@mat.ufmg.br; homepage: http://www.mat.ufmg.br/∼rodney.
Suma´rio
0 Introduc¸a˜o: Representac¸a˜o de Nu´meros Reais no Computador 3
0.1 Ponto Flutuante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2 Erros de Arredondamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.3 O Padra˜o de Ponto Flutuante IEEE 754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.3.1 Nu´meros normalizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.3.2 Nu´meros denormalizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.3.3 Outros valores nume´ricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 Matrizes Esparsas 7
1.1 Problema Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Problema de Poisson Unidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Problema de Poisson Bidimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Matrizes Esparsas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Implementac¸a˜o Computacional de Matrizes Esparsas . . . . . . . . . . . . . . . . . . . . . . . 11
2 Invertibilidade de Matrizes Esparsas 13
2.1 Normas Matriciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Matrizes Diagonalmente Dominantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Teorema dos Discos de Gershgorin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Propriedade FC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Matrizes Irredut´ıveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Me´todos Iterativos Lineares 31
3.1 Me´todo Iterativos Ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.1 Me´todo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.2 Me´todo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.3 Me´todo SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.4 Comparac¸a˜o da Velocidade de Convergeˆncia dos Treˆs Me´todos no Problema Modelo . 34
3.1.5 Me´todo de Jacobi Amortecido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Ana´lise de Convergeˆncia dos Me´todos Iterativos Lineares . . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Convergeˆncia dos Me´todos Iterativos Lineares . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Velocidade de Convergeˆncia dos Me´todos Iterativos Lineares . . . . . . . . . . . . . . 40
3.2.3 Convergeˆncia para Matrizes Sime´tricas Positivas Definidas . . . . . . . . . . . . . . . . 42
3.3 Convergeˆncia dos Me´todos Iterativos Lineares para Matrizes de Discretizac¸a˜o . . . . . . . . . 44
3.3.1 Convergeˆncia do Me´todo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.2 Convergeˆncia do Me´todo de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.3 Convergeˆncia do Me´todo SOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.4 Convergeˆncia do Me´todo de Jacobi Amortecido . . . . . . . . . . . . . . . . . . . . . . 59
3.3.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1
Rodney Josue´ Biezuner 2
3.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 Me´todos de Projec¸a˜o 62
4.1 Teoria Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.1.1 Representac¸a˜o Matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.2 Minimizac¸a˜o de Funcionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.3 Estimativa do Erro em Me´todos de Projec¸a˜o . . . . . . . . . . . . . . . . . . . . . . . 66
4.2 Caso Unidimensional: Me´todos de Descida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.1 Me´todos de Descida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2.2 Me´todo da Descida Mais Acentuada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Me´todos de Subespac¸os de Krylov 74
5.1 Motivac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Subespac¸os de Krylov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Algoritmo de Arnoldi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Implementac¸a˜o Pra´tica: Me´todos de Ortogonalizac¸a˜o Esta´veis . . . . . . . . . . . . . . . . . . 79
5.4.1 Me´todo de Gram-Schmidt Modificado (MGS) . . . . . . . . . . . . . . . . . . . . . . . 79
5.4.2 Me´todo de Gram-Schmidt Modificado com Reortogonalizac¸a˜o (MGSR) . . . . . . . . . 82
5.5 Me´todo de Arnoldi para Sistemas Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.6 Decomposic¸a˜o QR via MGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.7 Algoritmo de Lanczos e Me´todo do Gradiente Conjugado . . . . . . . . . . . . . . . . . . . . 87
5.8 Me´todo do Gradiente Conjugado como um Me´todo de Descida . . . . . . . . . . . . . . . . . 91
5.8.1 Convergeˆncia do Me´todo do Gradiente Conjugado em Aritme´tica Exata . . . . . . . . 94
5.9 Velocidade de Convergeˆncia do Me´todo do Gradiente Conjugado . . . . . . . . . . . . . . . . 96
5.9.1 Polinoˆmios de Chebyshev . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.9.2 Velocidade de Convergeˆncia do CG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.10 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6 O Problema do Autovalor 102
6.1 Caracterizac¸a˜o Variacional dos Autovalores de uma Matriz Sime´trica: Quociente de Rayleigh 102
6.2 Me´todo das Poteˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.1 Me´todo das Poteˆncias Inverso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2.2 Me´todo das Poteˆncias com Deslocamento . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.2.3 Iterac¸a˜o do Quociente de Rayleigh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3 Algoritmo QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Reduc¸a˜o de uma matriz a sua forma de Hessenberg . . . . . . . . . . . . . . . . . . . . 111
6.3.2 Acelerac¸a˜o do algoritmo QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.3.3 Implementac¸a˜o pra´tica do algoritmo QR . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.4 Iterac¸a˜o de subespac¸os e iterac¸a˜o simultaˆnea . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.4.1 Equivaleˆncia entre o Algoritmo QR e Iterac¸a˜o Simultaˆnea . . . . . . . . . . . . . . . . 118
6.4.2 Convergeˆncia do Algoritmo QR . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 119
6.5 Me´todo de Arnoldi e Algoritmo de Lanczos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.6 O Problema de Autovalor Sime´trico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.7 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Cap´ıtulo 0
Introduc¸a˜o: Representac¸a˜o de
Nu´meros Reais no Computador
Computadores digitais usam um nu´mero finito de bits para representar um nu´mero real, portanto eles
podem representar apenas um subconjunto finito dos nu´meros reais, o que leva a dois tipos diferentes de
limitac¸o˜es: (1) nu´meros representados na˜o podem ser arbitrariamente grandes ou arbitrariamente pequenos;
(2) existem lacunas entre os nume´ros representados. Estas limitac¸o˜es f´ısicas levam respectivamente aos erros
de overflow e underflow e aos erros de arredondamento.
Para discutir estes erros de maneira inteligente, introduzimos alguma terminologia.
0.1 Definic¸a˜o. Definimos o erro absoluto causado por uma computac¸a˜o por
Erro absoluto = |(valor calculado)− (valor exato)| .
O erro relativo causado por uma computac¸a˜o e´ definido por
Erro relativo =
∣∣∣∣erro absolutovalor exato
∣∣∣∣ .
O erro relativo permite comparar entre os erros cometidos de maneira significativa. Por exemplo, o erro
absoluto entre 1 (valor exato) e 2 (valor calculado) e o erro absoluto entre 1.000.000 (valor exato) e 1.000.001
(valor calculado) sa˜o os mesmos. No entanto, o erro relativo no primeiro caso e´ 1, enquanto que o erro
relativo no segundo caso e´ 10−6, expressando o fato intuitivo que o erro cometido no primeiro caso e´ muito
maior que o erro cometido no segundo caso. A`s vezes o erro relativo e´ expresso como uma porcentagem:
Erro percentual = [(erro relativo)× 100]%.
Assim, o erro percentual no primeiro caso e´ 100%, enquanto que o erro percentual no segundo caso e´
10−4 = 0, 0001%.
0.1 Ponto Flutuante
Na Matema´tica Pura, os nu´meros reais sa˜o infinitos, infinitamente grandes e infinitamente pequenos. Na˜o
existe um nu´mero maior ou um nu´mero menor. Ale´m disso, eles tambe´m sa˜o continuamente distribu´ıdos:
na˜o existem espac¸os entre nu´meros reais, pois entre quaisquer dois nu´meros reais sempre existe outro nu´mero
real. Mais que isso, eles sa˜o distribu´ıdos uniformemente na reta real. Um nu´mero real e´ infinitamente preciso:
3
Rodney Josue´ Biezuner 4
os nu´meros depois do ponto decimal sa˜o infinitos (incluindo o 0). Em outras palavras, usando a base 10,
nu´meros reais correspondem a se´ries da forma
a = a0 +
∞∑
n=1
an
10n
onde a0 ∈ Z e an ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
O padra˜o para representar nu´meros reais em Matema´tica Computacional e´ o nu´mero de ponto flutu-
ante. Nu´meros de ponto flutuante na˜o sa˜o infinitos: existe um nu´mero de ponto flutuante ma´ximo e um
nu´mero de ponto flutuante mı´nimo. Existe um nu´mero fixado de pontos flutuantes, logo existem espac¸os
entre eles. Nu´meros de ponto flutuante de precisa˜o simples (tipo float) tem aproximadamente 8 d´ıgitos
decimais significantes, enquanto que nu´meros de ponto flutuante de precisa˜o dupla (tipo double) tem aprox-
imadamente 17 d´ıgitos decimais significantes. O qualificativo “aproximadamente” se refere ao fato que os
nu´meros de ponto flutuante sa˜o armazenados no computador na base bina´ria, logo a conversa˜o da base
bina´ria para a base decimal introduz alguma imprecisa˜o.
Um nu´mero de ponto flutuante e´ armazenado internamente em duas partes: um significando e um
expoente, semelhante a` notac¸a˜o cient´ıfica.
Esta escolha de representac¸a˜o garante que a distribuic¸a˜o dos valores representados em ponto flutuante
na˜o sera´ uniforme. Para entender isso, vamos assumir que o significando e´ limitado a um u´nico d´ıgito decimal
e que o expoente e´ restrito aos valores −1, 0, 1. A tabela abaixo registra todos os nu´meros reais positivos
que podemos representar:
−1 0 1
0 0
1 1× 10−1= 0, 1 1× 100 = 1 1× 101 = 10
2 2× 10−1= 0, 2 2× 100 = 2 2× 101 = 20
3 3× 10−1= 0, 3 3× 100 = 3 3× 101 = 30
4 4× 10−1= 0, 4 4× 100 = 4 4× 101 = 40
5 5× 10−1= 0, 5 5× 100 = 5 5× 101 = 50
6 6× 10−1= 0, 6 6× 100 = 6 6× 101 = 60
7 7× 10−1= 0, 7 7× 100 = 7 7× 101 = 70
8 8× 10−1= 0, 8 8× 100 = 8 8× 101 = 80
9 9× 10−1= 0, 9 9× 100 = 9 9× 101 = 90
O fato do espac¸o entre os valores em ponto flutuante aumentar em proporc¸a˜o ao tamanho dos nu´meros e´
que justifica o nome ponto flutuante. Uma representac¸a˜o em que os espac¸os entre os valores representados
tem um tamanho fixo e´ chamada uma representac¸a˜o em ponto fixo.
0.2 Definic¸a˜o. Definimos a precisa˜o de um ponto flutuante como sendo o nu´mero de d´ıgitos significativos
que ele possui em seu significando. A exatida˜o de um ponto flutuante e´ a sua aproximac¸a˜o do valor
exato.
Quanto mais d´ıgitos significativos um ponto flutuante possui, mais preciso ele e´: o double 0.3333333333333333
e´ uma representac¸a˜o mais precisa do nu´mero real 1/3 do que o float 0.3333333. Por outro lado, o float
0.3333333 e´ uma representac¸a˜o mais exata de 1/3 do que o double 0.3444444444444444, apesar deste ser
um ponto flutuante mais preciso, porque a maioria dos seus d´ıgitos significativos esta˜o errados. Os erros
computacionais tais como os erros de cancelamento e arredondamento afetam a exatida˜o de um valor em
ponto flutuante. Aumentar a precisa˜o de float para double tem o potencial de aumentar a exatida˜o, mas
na˜o a garante.
Rodney Josue´ Biezuner 5
0.2 Erros de Arredondamento
Quando um valor computado esta´ entre dois valores representa´veis, ele sera´ substitu´ıdo pelo valor represen-
tado mais pro´ximo. Esta e´ a origem dos erros de arredondamento.
0.3 Definic¸a˜o. Definimos o erro de arredondamento por
Erro de arredondamento = |(valor representado)− (valor exato)| .
0.4 Definic¸a˜o. Um erro de cancelamento e´ um erro de arredondamento que ocorre quando a maioria
dos d´ıgitos significativos sa˜o perdidos durante a subtrac¸a˜o de dois valores aproximadamente iguais.
0.3 O Padra˜o de Ponto Flutuante IEEE 754
Antes do padra˜o IEEE 754 ser publicado em 1985, existiam muitos formatos de ponto flutuante implementa-
dos em hardware e software, o que dificultava a portabilidade dos programas. Os resultados obtidos variavam
de uma ma´quina para outra. Atualmente, a maioria dos fabricadores aderem ao padra˜o IEEE 754, fruto de
uma cooperac¸a˜o histo´rica entre cientistas de computac¸a˜o e desenhistas de chips de microprocessadores. A
sigla “IEEE” significa Institute of Electrical and Electronics Engineers.
Os formatos de precisa˜o aritme´tica simples float e dupla double sa˜o armazenados em 32 bits e 64 bits,
respectivamente. Cada formato divide um nu´mero em treˆs partes: sinal (um bit), expoente e frac¸a˜o. Os dois
formatos diferem quanto ao nu´mero de bits alocados para o expoente e para a frac¸a˜o. No formato float 8
bits sa˜o alocados para o expoente e 23 para a frac¸a˜o, enquanto que no formato double 11 bits sa˜o alocados
para o expoente e 52 para a frac¸a˜o. O bit de sinal representa o sinal do nu´mero: 0 para positivo e 1 para
negativo. O expoente na˜o possui sinal: para representar expoentes negativos, o padra˜o adiciona um vie´s
positivo; para obter o valor verdadeiro do expoente (sem vie´s), e´ necessa´rio subtrair o vie´s. No formato de
precisa˜o simples, o expoente com 8 bits pode armazenar valores (com vie´s) entre 0 e 255, mas 0 e 255 sa˜o
reservados; o vie´s e´ 127, de modo que os valores verdadeiros (sem vie´s) do expoente variam entre −126 e
+127. No formato de precisa˜o dupla, o expoente com 11 bits pode armazenar valores (com vie´s) entre 0 e
2047, com 0 e 2047 sa˜o reservados; o vie´s e´ 1023, de modo que os valores verdadeiros (sem vie´s) do expoente
variam entre −1022 e +1023.
0.3.1 Nu´meros normalizados
Representemos por s o sinal, e o expoente e f a frac¸a˜o.Quando e na˜o e´ um valor reservado (isto e´, 1 6 e 6 254
no formato float e 1 6 e 6 2047 no formato double) existe um algarismo 1 e um ponto bina´rio . impl´ıcitos
a` esquerda do primeiro bit de f , de modo que o nu´mero representado por s, e, f e´ o nu´mero
n = (−1)s × (1.f)× 2E
onde E = e− 127 (float) ou E = e− 1023 (double), chamado um nu´mero normalizado. O algarismo 1 e
o ponto bina´rio impl´ıcitos, juntamente com a parte fraciona´ria f , constituem o significando do nu´mero, de
modo que um nu´mero de precisa˜o simples possui 24 bits no seu significando, enquanto que um nu´mero de
precisa˜o dupla possui 53 bits no seu significando.
Assim, o maior valor poss´ıvel em mo´dulo para float corresponde a
s = 1, e = 254 e f = 11111111111111111111111,
ou seja,
23∑
i=0
1
2i
× 2127 ≈ 3, 4028× 1038,
Rodney Josue´ Biezuner 6
enquanto que o maior valor poss´ıvel em mo´dulo para double corresponde a
s = 0, e = 2047 e f = 1111111111111111111111111111111111111111111111111111,
ou seja,
52∑
i=0
1
2i
× 21023 ≈ 1, 7977× 10308.
0.3.2 Nu´meros denormalizados
Se e = 0 (um dos valores reservados) e f 6= 0, no´s temos o que se chama um nu´mero denormalizado (ou
subnormal). Existe um algarismo 0 e um ponto bina´rio . impl´ıcitos a` esquerda do primeiro bit de f , de modo
que o nu´mero representado por s, e, f e´ o nu´mero
n = (−1)s × (0.f)× 2E
onde E = −126 (float) ou E = −1022 (double).
Assim, o menor valor poss´ıvel em mo´dulo para float corresponde a
s = 0, e = 0 e f = 00000000000000000000001,
ou seja,
1
223
× 2−126 ≈ 1, 4013× 10−45,
um pouco menor do que o menor valor poss´ıvel 1 × 2−126 = 1, 1755 × 10−38 para um float normalizado,
correspondente a
s = 0, e = 1 e f = 00000000000000000000000.
O menor valor poss´ıvel em mo´dulo para double corresponde a
s = 0, e = 0 e f = 0000000000000000000000000000000000000000000000000001,
ou seja,
1
252
× 2−1022 ≈ 4, 9407× 10−324
um pouco menor do que o menor valor poss´ıvel 1× 2−1022 ≈ 2, 2251× 10−308 para um double normalizado,
correspondente a
s = 0, e = 1 e f = 0000000000000000000000000000000000000000000000000000.
A existeˆncia dos nu´meros denormalizados permitem uma convergeˆncia para zero menos abrupta. Quando
os valores computados va˜o se tornando menores e menores, atingindo o menor valor poss´ıvel para um float
ou double normalizado, ao inve´s de ca´ırem abruptamente para zero na pro´xima iterac¸a˜o, eles sa˜o convertidos
em nu´meros denormalizados.
No entanto, o espac¸o entre nu´meros representados no intervalo [1, 2] e´ igual a 2−52 ≈ 2.22 × 10−16; em
geral, no intervalo
[
2j , 2j+1
]
o espac¸o e´ 2j × 2−52, de modo que o espac¸o relativo nunca excede 2−52.
0.3.3 Outros valores nume´ricos
Se e = f = 0, o valor nume´rico e´ −0 ou +0, dependendo de s. Se f = 0 e e = 255 para float ou se e = 2047
para double, enta˜o o valor nume´rico e´ −Infinity ou +Infinity. Se f 6= 0 e e = 255 para float ou se
e = 2047 para double, enta˜o independentemente do valor de 0 no´s temos NaN (Not a Number). Por exemplo,
dividindo 0 por 0 resulta em NaN.
Em geral, no padra˜o IEEE 754 uma operac¸a˜o inva´lida produz NaN, divisa˜o por zero produz ±Infinity,
overflow produz o maior nu´mero normalizado poss´ıvel ou ±Infinity e underflow produz ±0, o menor
nu´mero normalizado poss´ıvel ou um nu´mero denormalizado.
Cap´ıtulo 1
Matrizes Esparsas
Matrizes esparsas sa˜o matrizes onde a imensa maioria das entradas sa˜o nulas. Esta e´ uma definic¸a˜o
vaga. Na˜o existe um limite inferior para o nu´mero de zeros em uma matriz, em relac¸a˜o ao tamanho desta,
a partir do qual podemos declarar uma matriz com sendo esparsa. Isto e´, na˜o existe um limite preciso a
partir do qual uma matriz deixa de ser esparsa e se torna uma matriz densa (isto e´, uma matriz em que
o nu´mero de zeros e´ irrelevante). Em geral, matrizes esparsas sa˜o definidas operacionalmente, no sentido
de que uma matriz pode ser chamada esparsa, sempre que te´cnicas especiais podem ser usadas para tirar
vantagem do grande nu´mero de zeros e sua localizac¸a˜o. Equac¸o˜es diferenciais parciais sa˜o a maior fonte de
problemas de a´lgebra linear nume´rica envolvendo matrizes esparsas. Engenheiros ele´tricos lidando com redes
ele´tricas nos anos 1960s foram os primeiros a explorar a esparcidade das matrizes de coeficientes associadas
aos problemas tratados para resolver sistemas lineares. Como os computadores tinham pouca capacidade
de armazenamento e poder de processamento, e os problemas envolviam um nu´mero enorme de varia´veis,
me´todos de soluc¸a˜o direta que tiram vantagem da existeˆncia de um nu´mero muito grande de zeros tiveram
que ser desenvolvidos.
1.1 Problema Modelo
Como fonte de matrizes esparsas, consideraremos o problema de resolver a equac¸a˜o de Poisson com condic¸a˜o
de Dirichlet discretizada atrave´s de diferenc¸as finitas em uma e duas dimenso˜es, que fornece uma matriz
esparsa sime´trica.
1.1.1 Problema de Poisson Unidimensional
Considere o problema de Dirichlet para a equac¸a˜o de Poisson no intervalo unita´rio I = (0, 1):{ −u′′ = f (x) se 0 < x < 1,
u (0) = a, u (1) = b. (1.1)
Seja h > 0. As expanso˜es de Taylor para uma func¸a˜o u a` direita e a` esquerda de um ponto x0 sa˜o dadas
respectivamente por
u(x0 + h) = u(x0) + u′(x0)h+
1
2!
u′′(x0)h2 +
1
3!
u′′′(x0)h3 + . . . ,
e
u(x0 − h) = u(x0)− u′(x0)h+ 12!u
′′(x0)h2 − 13!u
′′′(x0)h3 + . . .
Se somarmos estas duas equac¸o˜es, obtemos
u′′(x0) =
u(x0 − h)− 2u(x0) + u(x0 + h)
h2
− 2
4!
u(4)(x0)h2 − 25!u
(6)(x0)h4 − . . . ,
7
Rodney Josue´ Biezuner 8
o que fornece uma aproximac¸a˜o para a derivada segunda u′′(x0) de u em x0:
u′′(x0) ≈ u(x0 − h)− 2u(x0) + u(x0 + h)
h2
com erro
² = − 1
12
u(4)(ξ)h2 = O(h2),
onde x0 − h 6 ξ 6 x0 + h. Esta aproximac¸a˜o e´ chamada uma diferenc¸a centrada para a derivada segunda.
Divida o intervalo [0, 1] em n subintervalos de comprimento h = 1/n atrave´s de n − 1 pontos interiores
uniformemente espac¸ados:
x0 = 0, x1 = h, x2 = 2h, . . . , xn−1 = (n− 1)h, xn = nh = 1,
de modo que [0, 1] = [x0, x1] ∪ [x1, x2] ∪ . . . ∪ [xn−1, xn]. Introduzimos a notac¸a˜o:
ui = u(xi),
fi = f (xi) .
Esta e´ uma discretizac¸a˜o uniforme do intervalo [0, 1]. Uma vez discretizado o domı´nio da equac¸a˜o diferencial
parcial, procedemos a` discretizac¸a˜o desta u´ltima. Usando diferenc¸as centradas para cada ponto interior xi,
1 6 i 6 n− 1, temos
−ui−1 + 2ui − ui+1
h2
= fi. (1.2)
Esta discretizac¸a˜o em diferenc¸as finitas para a equac¸a˜o de Poisson e´ chamada fo´rmula dos treˆs pontos.
Portanto, para encontrar a soluc¸a˜o discretizada temos que resolver o sistema linear com n − 1 equac¸o˜es a
n− 1 inco´gnitas: 
h−2 (2u1 − u2) = f1 + ah−2
h−2 (−u1 + 2u2 − u3) = f2
...
h−2 (−un−3 + 2un−2 − un−1) = fn−2
h−2 (−un−2 + 2un−1) = fn−1 + bh−2
,
ou seja,
1
h2

2 −1
−1 2 −1
−1 . . . . . .
. . . . . . −1
−1 2 −1
−1 2


u1
u2
...
...
un−2
un−1

=

f1 + ah−2
f2
...
...
fn−2
fn−1 + bh−2

.
Esta e´ uma matriz tridiagonal, sime´trica e esparsa.
1.1.2 Problema de Poisson Bidimensional
Considere o problema de Dirichlet homogeˆneo para a equac¸a˜o de Poisson no quadrado unita´rio Ω = (0, 1)×
(0, 1) { −∆u = f (x, y) em Ω,
u = 0 sobre ∂Ω. (1.3)
Discretizamos o quadrado Ω atrave´s dos pontos
(xi, yj) = (ih, jh) , 0 6 i, j 6 n,
Rodney Josue´ Biezuner 9
onde
h =
1
n
,
produzindo a malha (ou gride) uniforme
Ωd =
{
(x, y) ∈ Ω : x = i∆x, y = j∆y, 0 6 i, j 6 n} .
A malha dos pontos interiores e´ dada por
Ωd = {(x, y) ∈ Ω : x = i∆x, y = j∆y, 1 6 i, j 6 n− 1} ,
enquanto que a fronteira discretizada e´ o conjunto
∂Ωd = {(x, y) ∈ ∂Ω : x = i∆x, y = j∆y, 0 6 i 6 n, 0 6 j 6 m} .
A equac¸a˜o de Poisson
−uxx − uyy = f (x, y)
pode ser agoradiscretizada. Denotamos
ui,j = u (xi, yj) ,
fi,j = f (xi, yj) .
Aproximamos cada derivada parcial de segunda ordem pela sua diferenc¸a centrada, obtendo
−uxx ≈ −ui−1,j + 2ui,j − ui+1,j∆x2 ,
−uyy ≈ −ui,j−1 + 2ui,j − ui,j+1∆y2 .
Portanto, a equac¸a˜o de Poisson discretizada toma a forma
−ui−1,j − ui,j−1 + 4ui,j − ui+1,j − ui,j+1
h2
= fi,j . (1.4)
Como a func¸a˜o u e´ calculada em cinco pontos, esta discretizac¸a˜o em diferenc¸as finitas para a equac¸a˜o de
Poisson e´ chamada a fo´rmula dos cinco pontos.
Para cada ponto interior da malha obtemos uma equac¸a˜o, logo temos um sistema linear de (n− 1)2
equac¸o˜es com o mesmo nu´mero de inco´gnitas. Diferente do caso unidimensional, no entanto, na˜o existe uma
maneira natural de ordenar os pontos da malha, logo na˜o podemos obter imediatamente uma representac¸a˜o
matricial para o problema discretizado. Precisamos antes escolher uma ordenac¸a˜o para os pontos da malha,
e como existem va´rias ordenac¸o˜es poss´ıveis, existem va´rias matrizes associadas.
Talvez a mais simples ordenac¸a˜o e´ a ordem lexicogra´fica. Nesta ordem, os pontos da malha sa˜o percorridos
linha por linha, da esquerda para a direita, de baixo para cima:
u1,1, u2,1, . . . , un−1,1, u1,2, u2,2, . . . , un−1,2, . . . . . . , u1,m−1, u2,m−1, . . . , un−1,m−1.
Neste caso, a matriz associada ao sistema linear e´ uma matriz (n− 1)2× (n− 1)2 que pode ser escrita como
uma matriz de (n− 1)2 blocos de dimensa˜o (n− 1)× (n− 1) na forma
A =
1
h2

B −I
−I B −I
−I . . . . . .
. . . . . . −I
−I B −I
−I B

(n−1)×(n−1)
Rodney Josue´ Biezuner 10
onde I e´ a matriz identidade (n− 1)× (n− 1) e B e´ a matriz (n− 1)× (n− 1) dada por
B =

4 −1
−1 4 −1
−1 . . . . . .
. . . . . . −1
−1 4 −1
−1 4

(n−1)×(n−1)
Observe que
aii = 4
para todo 1 6 i 6 (n− 1)2, enquanto que
aij = −1
se o ponto j e´ vizinho a` esquerda ou a` direita do ponto i, ou se o ponto j e´ vizinho acima ou abaixo do ponto
i. Por exemplo, se n = 4, temos
A =
1
h2

4 −1 0 −1 0 0 0 0 0
−1 4 −1 0 −1 0 0 0 0
0 −1 4 0 0 −1 0 0 0
−1 0 0 4 −1 0 −1 0 0
0 −1 0 −1 4 −1 0 −1 0
0 0 −1 0 −1 4 0 0 −1
0 0 0 −1 0 0 4 −1 0
0 0 0 0 −1 0 −1 4 −1
0 0 0 0 0 −1 0 −1 4

Observe que a matriz A e´ uma matriz sime´trica, pentadiagonal e esparsa.
1.2 Matrizes Esparsas
Outros problemas de EDPs, especialmente aqueles envolvendo derivadas primeiras (tais como problemas de
convecc¸a˜o-difusa˜o), em geral levam a matrizes na˜o-sime´tricas. Discretizac¸o˜es de outros tipos, tais como as
encontradas em elementos finitos, levam a matrizes esparsas com outro tipo de estrutura. De qualquer modo,
todos possuem em comum o fato de a matriz de discretizac¸a˜o ser uma matriz esparsa.
Existem essencialmente dois tipos de matrizes esparsas: estruturadas e na˜o-estruturadas. Uma
matriz estruturada e´ uma em que as entradas na˜o-nulas formam um padra˜o regular, frequentemente ao
longo de um nu´mero pequeno de diagonais (tais como as matrizes que vimos no problema modelo na sec¸a˜o
anterior). Os elementos na˜o-nulos podem tambe´m estar organizados em blocos (submatrizes densas) de
mesmo tamanho, organizadas ao longo de um nu´mero pequeno de blocos diagonais. Discretizac¸o˜es atrave´s de
diferenc¸as finitas tipicamente da˜o origem a matrizes esparsas com estruturas regulares. Uma matriz esparsa
em que as entradas na˜o-nulas sa˜o irregularmente localizadas e´ uma matriz esparsa irregularmente estruturada.
Os me´todos de volumes finitos ou elementos finitos aplicados a domı´nios com geometria complexa em geral
levam matrizes irregularmente estruturadas.
Esta distinc¸a˜o na˜o afeta em geral me´todos de soluc¸a˜o direta mas e´ muito importante para os me´todos de
soluc¸a˜o iterativos. Neste u´ltimos, uma das operac¸o˜es ba´sicas essenciais e´ a do produto de uma matriz por
um vetor.
Rodney Josue´ Biezuner 11
1.3 Implementac¸a˜o Computacional de Matrizes Esparsas
Para tirar vantagem do grande nu´mero de elementos nulos, esquemas especiais sa˜o necessa´rios para armazenar
matrizes esparsas na memo´ria do computador. O principal objetivo e´ representar apenas os elementos na˜o-
nulos.
O esquema mais simples de armazenamento e´ o chamado formato de coordenadas. A estrutura de dados
consiste de treˆs vetores (arrays): um vetor real contendo os valores e dois vetores inteiros, um deles contendo
os ı´ndices das linhas, enquanto que o outro conte´m os ı´ndices das colunas.
1.1 Exemplo. A matriz
A =

1 0 0 3 0
5 7 0 0 2
3 0 2 4 0
0 0 6 9 0
0 0 0 0 4

pode ser representada por
valueArray = 2 9 1 4 3 4 2 5 3 6 7 ,
rowIndexArray = 3 4 1 3 3 5 2 2 1 4 2 ,
columnIndexArray = 3 4 1 4 1 5 5 1 4 3 2 .
Cada vetor tem comprimento igual ao nu´mero de elementos na˜o-nulos da matriz. Observe que os
elementos sa˜o listados em ordem arbitra´ria. ¤
Provavelmente, o formato mais popular para armazenar matrizes esparsas gerais e´ o formato compressed
row storage (CRS). Neste esquema, as linhas da matriz sa˜o armazenadas uma a uma em um vetor real, da
primeira ate´ a u´ltima, preservando a ordem. Um segundo vetor inteiro contendo os ı´ndices das colunas e´
usado. Um terceiro vetor inteiro conte´m a posic¸a˜o no vetor de valores reais ou no vetor de ı´ndices de coluna
onde cada linha comec¸a, mais um elemento para indicar a primeira posic¸a˜o vazia dos dois vetores.
1.2 Exemplo. A matriz
A =

1 0 0 3 0
5 7 0 0 2
3 0 2 4 0
0 0 6 9 0
0 0 0 0 4

pode ser representada no formato CSR por
valueArray = 1 3 5 7 2 3 2 4 6 9 4 ,
columIndexArray = 1 4 1 2 5 1 3 4 3 4 5 ,
rowPointerArray = 1 3 6 9 11 12 .
Enquanto o comprimento dos dois primeiros vetores e´ igual ao nu´mero de elementos na˜o-nulos da
matriz., o comprimento do terceiro vetor e´ igual ao nu´mero de linhas da matriz mais um. Dentro
de cada linha os elementos ainda podem ser armazenados em ordem arbitra´ria, o que pode ser muito
conveniente. ¤
Este esquema e´ o preferido pois e´ o mais u´til para realizar as computac¸o˜es t´ıpicas, tais como multiplicac¸a˜o
da matriz por vetores. Em CRS, a multiplicac¸a˜o matriz-vetor pode ser implementada da seguinte forma (em
Rodney Josue´ Biezuner 12
C/C++ ou Java):
for( int i = 0; i < n; i++ )
{
lowerIndex = rowPointerArray[i];
upperIndex = rowPointerArray[i+1];
//loop over row i
for( int j = lowerIndex; j < upperIndex; j++ )
Av[i] += valueArray[j]* v[columArray[j]];
}
Um esquema correspondente, armazenando colunas ao inve´s de linhas e´ o compressed column storage (CCS),
usado no Octave.
Os esquemas considerados acima sa˜o chamados esta´ticos. Esquemas dinaˆmicos, envolvendo listas en-
cadeadas, em geral economizam ainda mais memo´ria e tem acesso ainda mais ra´pido a` memo´ria. Cada linha
da matriz pode ser representada por uma lista encadeada. A matriz toda e´ representada por uma lista de
listas encadeadas, seguindo a ordem de linhas da matriz. Desta forma, o in´ıcio de cada linha na˜o precisa ser
representado. O ı´ndice da coluna de cada elemento da linha ainda precisa ser representado, e´ claro, e isso
pode ser feito atrave´s de um ponteiro espec´ıfico.
Outras esquemas podem ser utilizados, tirando vantagem da estrutura da matriz esparsa. Por exem-
plo, em matrizes diagonais as diagonais na˜o-nulas podem ser armazenadas separadamente. Em matrizes
sime´tricas, e´ necessa´rio armazenar apenas os elementos da diagonal principal e da parte triangular superior
(ou inferior) da matriz, mas isso em geral implica em algoritmos mais complicados para fazer operac¸o˜es com
a matriz.
Cap´ıtulo 2
Invertibilidade de Matrizes Esparsas
Neste cap´ıtulo desenvolveremos me´todos gerais e fa´ceis de aplicar para determinar a invertibilidade de ma-
trizes esparsas, principalmente aquelas que surgem atrave´s da discretizac¸a˜o de equac¸o˜es diferenciaisparciais
atrave´s de diferenc¸as finitas. Em particular, isso implicara´ a existeˆncia e unicidade de soluc¸o˜es para sistemas
lineares envolvendo tais matrizes. Uma vez que isso esteja estabelecido, poderemos nos dedicar nos pro´ximos
cap´ıtulos a estudar me´todos iterativos para encontrar estas soluc¸o˜es.
2.1 Normas Matriciais
Lembramos o conceito de norma vetorial:
2.1 Definic¸a˜o. Seja V um espac¸o vetorial real ou complexo. Uma norma vetorial em V e´ uma func¸a˜o
|·| : V −→ R que satisfaz as seguintes propriedades:
(i) |x| > 0 para todo x 6= 0 e |x| = 0 se x = 0;
(ii) ‖αx‖ = |α| ‖x‖ para todo x ∈ V e para todo α ∈ R;
(iii) (Desigualdade Triangular) ‖x+ y‖ 6 ‖x‖+ ‖y‖ para todos x, y ∈ V.
Denotaremos por Mn (R) o espac¸o vetorial das matrizes complexas n× n e por Mn (C) o espac¸o vetorial
das matrizes complexas n × n. Quando estivermos nos referindo a qualquer um destes espac¸os (ou seja,
quando a afirmac¸a˜o que fizermos valer para qualquer um deles), usaremos a notac¸a˜o Mn simplesmente.
2.2 Definic¸a˜o. Uma norma matricial no espac¸o vetorial Mn e´ uma norma vetorial ‖·‖ : Mn −→ R que
satisfaz a propriedade submultiplicativa
‖AB‖ 6 ‖A‖ ‖B‖ (2.1)
para todas as matrizes A,B ∈Mn.
A seguir, veremos alguns exemplos das normas matriciais mais importantes em Mn. A verificac¸a˜o de que
as normas apresentadas constituem normas vetoriais e´ deixada como exerc´ıcio (Exerc´ıcio 2.1).
2.3 Exemplo. Norma l1 (norma da soma):
‖A‖1 =
n∑
i,j=1
|aij | . (2.2)
13
Rodney Josue´ Biezuner 14
De fato,
‖AB‖1 =
n∑
i,j=1
∣∣∣∣∣
n∑
k=1
aikbkj
∣∣∣∣∣ 6
n∑
i,j,k=1
|aikbkj | 6
n∑
i,j,k,l=1
|aikblj | =
n∑
i,k=1
|aik|
n∑
j,l=1
|blj | = ‖A‖1 ‖B‖1 .
¤
2.4 Exemplo. Norma l2 (norma euclidiana):
‖A‖2 =
 n∑
i,j=1
|aij |2
1/2 . (2.3)
Com efeito,
‖AB‖22 =
n∑
i,j=1
∣∣∣∣∣
n∑
k=1
aikbkj
∣∣∣∣∣
2
6
n∑
i,j=1
(
n∑
k=1
|aik|2
)(
n∑
l=1
|blj |2
)
=
 n∑
i,k=1
|aik|2
 n∑
j,l=1
|blj |2
 = ‖A‖22 ‖B‖22 .
A norma l2 tambe´m e´ chamada mais raramente (e somente para matrizes) norma de Schur, norma de
Frobenius ou norma de Hilbert-Schmidt. ¤
2.5 Exemplo. Normas lp:
De modo geral, dado p > 1, definimos a norma matricial
‖A‖p =
 n∑
i,j=1
|aij |p
1/p . (2.4)
¤
2.6 Exemplo. Norma l∞ modificada (norma do ma´ximo modificada):
A norma l∞ (norma do ma´ximo)
‖A‖∞ = max16i,j6n |aij |
e´ uma norma vetorial em Mn mas na˜o e´ uma norma matricial: por exemplo, se
A =
[
1 1
1 1
]
,
enta˜o
A2 =
[
2 2
2 2
]
e portanto ∥∥A2∥∥∞ = 2 > 1 = ‖A‖∞ ‖A‖∞ .
No entanto, um mu´ltiplo escalar desta norma vetorial e´ uma norma matricial:
‖A‖n∞ = n max16i,j6n |aij | . (2.5)
Com efeito,
‖AB‖n∞ = n max16i,j6n
∣∣∣∣∣
n∑
k=1
aikbkj
∣∣∣∣∣ 6 n max16i,j6n
n∑
k=1
|aikbkj | 6 n max
16i,j6n
n∑
k=1
‖A‖∞ ‖B‖∞
= n (n ‖A‖∞ ‖B‖∞) = n ‖A‖∞ n ‖B‖∞ = ‖AB‖n∞ .
¤
Rodney Josue´ Biezuner 15
2.7 Exemplo. Norma do operador:
Dada uma norma vetorial |·| em Rn ou Cn, ela induz uma norma matricial atrave´s da definic¸a˜o
‖A‖ = max
|x|=1
|Ax| = max
|x|61
|Ax| = sup
x6=0
|Ax|
|x| . (2.6)
Aqui vemos A como um operador linear em Rn ou Cn, portanto cont´ınuo, de modo que o ma´ximo de
A e´ atingido na esfera e na bola fechada. Para ver que a primeira e a terceira definic¸o˜es coincidem (de
modo que o sup na terceira definic¸a˜o e´ de fato um ma´ximo), use o fato que
|Ax|
|x| =
∣∣∣∣A( x|x|
)∣∣∣∣ .
Agora observe que
max
|x|=1
|Ax| 6 max
|x|61
|Ax| ,
ja´ que a bola fechada conte´m a esfera. Por outro lado, se |x| = ε < 1, segue que∣∣∣∣A( x|x|
)∣∣∣∣ = |Ax||x| = |Ax|ε > |Ax| ,
de modo que o ma´ximo de |Ax| na˜o e´ atingido no interior da bola, logo
max
|x|=1
|Ax| > max
|x|61
|Ax|
e portanto a primeira e a segunda definic¸o˜es coincidem. Finalmente, para ver que a norma do operador
e´ uma norma matricial, escreva
‖AB‖ = max
x 6=0
|ABx|
|x| = maxx6=0
( |ABx|
|Bx|
|Bx|
|x|
)
6 max
Bx 6=0
|ABx|
|Bx| maxx6=0
|Bx|
|x| 6 maxy 6=0
|Ay|
|y| maxx 6=0
|Bx|
|x| = ‖A‖ ‖B‖ .
A norma do operador satisfaz a propriedade extremamente u´til
|Ax| 6 ‖A‖ |x| (2.7)
para todo vetor x ∈ Rn ou Cn. ¤
2.8 Exemplo. Norma do ma´ximo das somas das linhas:
‖A‖L = max16i6n
n∑
j=1
|aij | . (2.8)
Esta norma e´ a norma do operador induzida pela norma vetorial l∞. De fato, se x = (x1, . . . , xn),
temos
|Ax|∞ = max16i6n
∣∣∣∣∣∣
n∑
j=1
aijxj
∣∣∣∣∣∣ 6 max16i6n
n∑
j=1
|aijxj | 6 max
16i6n
n∑
j=1
|aij | |x|∞ = ‖A‖L |x|∞ ,
de modo que
max
|x|=1
|Ax|∞ 6 ‖A‖L .
Supondo que a i-e´sima linha de A e´ na˜o-nula, definimos o vetor y = (y1, . . . , yn) ∈ Cn por
yi =

aij
|aij | se aij 6= 0,
1 se aij = 0.
,
Rodney Josue´ Biezuner 16
o que implica |y|∞ = 1, aijyj = |aij | e
max
|x|∞=1
|Ax|∞ > |Ay|∞ = max16i6n
∣∣∣∣∣∣
n∑
j=1
aijyj
∣∣∣∣∣∣ = max16i6n
n∑
j=1
|aij | = ‖A‖L .
¤
2.9 Exemplo. Norma do ma´ximo das somas das colunas:
‖A‖C = max16j6n
n∑
i=1
|aij | . (2.9)
Esta norma e´ a norma do operador induzida pela norma vetorial l1. De fato, escrevendo A em termos
de suas colunas
A = [A1 . . . An]
segue que
‖A‖C = max16j6n |Aj |1 .
Se x = (x1, . . . , xn), segue que
|Ax|1 = |x1A1 + . . .+ xnAn|1 6
n∑
i=1
|xiAi|1 =
n∑
i=1
|xi| |Ai|1 6
n∑
i=1
|xi| max
16j6n
|Aj |1
= ‖A‖C
n∑
i=1
|xi| = ‖A‖C |x|1 ,
donde
max
|x|1=1
|Ax|1 6 ‖A‖C .
Agora, se escolhermos yj = ej , temos que |yj |1 = 1 e
|Ay|1 = |Aj |1
para todo k, logo
max
|x|1=1
|Ax|1 > max16j6n |Ayj |1 = max16j6n |Aj |1 = ‖A‖C .
¤
2.10 Exemplo. p-normas:
Este e´ o nome geral para as normas do operador induzidas pela norma vetorial lp em Rn ou Cn. Para
distingui-las das normas matriciais lp no pro´prio espac¸o vetorial Mn, vamos denota´-las por
|||A|||p = sup
x 6=0
|Ax|p
|x|p
.
O caso especial da norma do operador induzida pela norma vetorial l2 (a norma vetorial euclidiana) e´
tambe´m chamada a norma espectral e satisfaz
|||A|||2 =
√
λmax = max
{√
|λ| : λ e´ um autovalor de A∗A
}
.
Rodney Josue´ Biezuner 17
De fato, A∗A e´ uma matriz hermitiana logo todos os seus autovalores sa˜o na˜o-negativos. Pela carac-
terizac¸a˜o variacional dos autovalores de uma matriz hermitiana temos
λmax = max
x 6=0
〈A∗Ax, x〉2
|x|22
= max
x 6=0
|Ax|22
|x|22
.
Observe que a 2-norma e´ diferente da norma matricial l2 (Exerc´ıcio 2.3). Note tambe´m que se A e´
uma matriz hermitiana, enta˜o A∗A = A2 e |||A|||2 e´ portanto o mo´dulo do maior autovalor de A, isto
e´, a norma espectral de A e´ o raio espectral de A, definido como sendo o maior valor absoluto dos
autovalores λ1, . . . , λn de A:
ρ (A) = max
i=1,...,n
|λi| ,
¤
2.11 Exemplo. Norma induzida por uma matriz invert´ıvel:
Se ‖·‖ e´ uma norma matricial qualquer e se S e´ uma matriz invert´ıvel, enta˜o
‖A‖S =
∥∥S−1AS∥∥ (2.10)
define uma norma matricial. Com efeito,
‖AB‖S =
∥∥S−1ABS∥∥ = ∥∥S−1ASS−1BS∥∥ 6 ∥∥S−1AS∥∥∥∥S−1BS∥∥ = ‖A‖S ‖B‖S .
¤
Lembramos que todas as normas em um espac¸o vetorial de dimensa˜o finita sa˜o equivalentes, e isso vale em
particular para normas matriciais:
2.12 Teorema. Seja V um espac¸o vetorial real ou complexo de dimensa˜o finita. Enta˜o todas as normas
vetoriais em V sa˜o equivalentes, isto e´, se ‖·‖1 e ‖·‖2 sa˜o duas normas vetoriais quaisquer em V ,
enta˜o existem constantes C1, C2 > 0 tais que
‖x‖1 6 C1 ‖x‖2
e
‖x‖2 6 C2 ‖x‖1
para todo x ∈ V .
Prova: Para mostrar a equivaleˆncia entre todas as normas de um espac¸o vetorial, por transitividade basta
fixar uma norma ‖·‖1 e mostrar que qualquer norma arbitra´ria ‖·‖2 e´ equivalente a ‖·‖1. Seja B = {e1, . . . , en}
uma base para V , de modo que todo vetor x ∈ V se escreve na forma
x =
n∑
i=1
xiei
e defina‖·‖1 como sendo a norma `1 em relac¸a˜o a esta base:
‖x‖1 =
n∑
i=1
|xi| .
Rodney Josue´ Biezuner 18
Enta˜o, se ‖·‖2 e´ uma norma qualquer em V , segue da desigualdade triangular que
‖x‖2 6
n∑
i=1
‖xiei‖2 =
n∑
i=1
|xi| ‖ei‖2
6
(
max
i=1,...,n
‖ei‖2
) n∑
i=1
|xi|
= C2 ‖x‖1 ,
onde denotamos C2 = max
i=1,...,n
‖ei‖2.
Para provar a desigualdade reversa, considere a esfera unita´ria na norma da soma S = {x ∈ V : ‖x‖1 = 1}.
A desigualdade anterior garante que a func¸a˜o x 7→ ‖x‖2 e´ cont´ınua na topologia definida pela norma ‖·‖1 e
portanto assume um valor mı´nimo m no conjunto fechado e limitado (compacto) S. Necessariamente m > 0:
se existisse e =
n∑
i=1
xiei ∈ S tal que ‖e‖2 = 0, ter´ıamos e =
n∑
i=1
xiei = 0, contrariando o fato que {e1, . . . , en}
e´ um conjunto linearmente independente. Portanto,∥∥∥∥ x‖x‖1
∥∥∥∥
2
> m
para todo x ∈ V , x 6= 0. Tomando C1 = 1/m, segue que ‖x‖1 6 C1 ‖x‖2 para todo x ∈ V . ¥
2.2 Matrizes Diagonalmente Dominantes
2.13 Definic¸a˜o. Dizemos que uma matriz An×n e´ diagonalmente dominante se
|aii| >
n∑
j=1
j 6=i
|aij | para todo i = 1, . . . , n
e estritamente diagonalmente dominante se
|aii| >
n∑
j=1
j 6=i
|aij | para todo i = 1, . . . , n.
2.14 Lema. Seja A ∈Mn. Se existe alguma norma matricial ‖·‖ tal que ‖I −A‖ < 1, enta˜o A e´ invert´ıvel.
Prova. De fato, sob esta condic¸a˜o, afirmamos que a inversa e´ dada explicitamente pela se´rie
A−1 =
∞∑
k=0
(I −A)k . (2.11)
Para todo N ∈ N podemos escrever
A
N∑
k=0
(I −A)k = [I − (I −A)]
N∑
k=0
(I −A)k =
N∑
k=0
(I −A)k −
N+1∑
k=1
(I −A)k = I − (I −A)N+1 .
Como ‖·‖ e´ uma norma matricial, temos que∥∥∥(I −A)k∥∥∥ 6 ‖I −A‖k .
Rodney Josue´ Biezuner 19
Logo, de ‖I −A‖ < 1 segue que
lim
N→∞
(I −A)N+1 = 0.
Portanto, tomando o limite quando N →∞, conclu´ımos (2.11). ¥
2.15 Corola´rio. Se A ∈Mn e´ uma matriz singular e ‖·‖ e´ uma norma matricial, enta˜o ‖I −A‖ > 1. Em
particular, se ‖·‖ e´ uma norma matricial, enta˜o ‖I‖ > 1.
Prova. Para provar a segunda afirmac¸a˜o do enunciado, basta tomar A = 0.¥
2.16 Proposic¸a˜o. Se A e´ uma matriz estritamente diagonalmente dominante, enta˜o A e´ invert´ıvel.
Prova. Denote por D a matriz diagonal cujas entradas diagonais sa˜o as entradas diagonais de A. Uma
matriz estritamente diagonalmente dominante possui, por definic¸a˜o, entradas diagonais na˜o-nulas, logo D e´
uma matriz invert´ıvel. A matriz D−1A tem apenas 1’s na diagonal principal e se mostramos que D−1A e´
invert´ıvel, isto implicara´ que A e´ invert´ıvel. Para provar isso, considere a matriz I −D−1A. Temos(
I −D−1A)
ij
=
{
0 se i = j,
−aij/aii se i 6= j.
Usemos a norma do ma´ximo das somas das linhas. Para cada 1 6 i 6 n temos
n∑
j=1
∣∣∣(I −D−1A)
ij
∣∣∣ = n∑
j=1
j 6=i
∣∣∣∣aijaii
∣∣∣∣ = 1|aii|
n∑
j=1
j 6=i
|aij | < 1,
logo
∥∥I −D−1A∥∥ < 1 e o resultado segue do Lema 2.14. ¥
A`s vezes, exigir dominaˆncia diagonal estrita em todas as linhas e´ pedir demais. Para certas matrizes,
dominaˆncia diagonal junto com dominaˆncia diagonal estrita em apenas uma linha e´ suficiente para garantir
a sua invertibilidade. As matrizes de discretizac¸a˜o obtidas no cap´ıtulo anterior satisfazem esta condic¸a˜o
(nas linhas correspondentes a` pontos adjacentes a` fronteira), e nenhuma delas e´ estritamente diagonalmente
dominante. Por outro lado, vale a pena ressaltar que esta condic¸a˜o na˜o e´ suficiente para estabelecer a
invertibilidade de uma matriz em geral, como o exemplo 4 2 10 1 1
0 1 1

demonstra.
2.3 Teorema dos Discos de Gershgorin
A primeira ferramenta teo´rica e´ o importante Teorema dos Discos de Gershgorin. Ele decorre da seguinte
observac¸a˜o: se A e´ uma matriz complexa n × n, podemos sempre escrever A = D + B, onde D = diag
(a11, . . . , ann) e´ a matriz diagonal formada pela diagonal principal de A e B consiste dos elementos restantes
de A, possuindo uma diagonal principal nula. Se definirmos Aε = D + εB, enta˜o A0 = D e A1 = A. Os
autovalores de D sa˜o a11, . . . , ann, enquanto que os autovalores de Aε devem estar localizados em vizinhanc¸as
dos pontos a11, . . . , ann, desde que ε seja suficientemente pequeno. O mesmo deve valer para os autovalores
da matriz A: eles devem estar contidos em discos centrados nos elementos a11, . . . , ann da diagonal principal
se os discos sa˜o suficientemente grandes. O Teorema de Gershgorin da´ uma estimativa precisa e simples de
calcular para os raios destes discos em func¸a˜o das entradas restantes da matriz A. Denote o disco complexo
fechado de centro em a e raio R por
DR (a) = {z ∈ C : |z − a| 6 R} .
Rodney Josue´ Biezuner 20
2.17 Teorema. (Teorema dos Discos de Gershgorin) Se A ∈Mn (C) e
Ri (A) =
n∑
j=1
j 6=i
|aij | (2.12)
denota a soma dos valores absolutos dos elementos da linha i de A excetuando o elemento da diagonal
principal, enta˜o todos os autovalores de A esta˜o contidos na unia˜o dos n discos de Gershgorin
G (A) =
n⋃
i=1
DRi(A) (aii) . (2.13)
Ale´m disso, se uma unia˜o de k destes discos forma uma regia˜o que e´ disjunta dos n−k discos restantes,
enta˜o existem exatamente k autovalores de A nesta regia˜o.
Prova. Seja λ um autovalor de A e x = (x1, . . . , xn) 6= 0 um autovetor associado. Seja k um ı´ndice tal que
|xk| > |xj | para j = 1, . . . , n,
isto e´, xk e´ a coordenada de x de maior valor absoluto. Denotando por (Ax)k a k-e´sima coordenada do vetor
Ax = λx, temos
λxk = (Ax)k =
n∑
j=1
akjxj
que e´ equivalente a
xk (λ− akk) =
n∑
j=1
j 6=k
akjxj .
Da´ı,
|xk| |λ− akk| 6
n∑
j=1
j 6=k
|akjxj | =
n∑
j=1
j 6=k
|akj | |xj | 6 |xk|
n∑
j=1
j 6=k
|akj | = |xk|Rk (A) ,
ou seja,
|λ− akk| 6 Rk (A) .
Isso prova o resultado principal do Teorema de Gershgorin (como na˜o sabemos qual k e´ apropriado para
cada autovalor λ, e um mesmo k pode servir para va´rios autovalores λ, tudo o que podemos afirmar e´ que
os autovalores esta˜o na unia˜o dos discos).
Para provar a segunda afirmac¸a˜o, escreva A = D +B, onde D = diag (a11, . . . , ann) e defina
At = D + tB
para 0 6 t 6 1. Note que
Ri (At) = Ri (tB) = tRi (A) .
Para simplificar a notac¸a˜o, assuma que a unia˜o dos primeiros k discos de Gershgorin
Gk (A) =
k⋃
i=1
DRi(A) (aii)
satisfaz Gk (A) ∩ [G (A) \Gk (A)] = ∅. Temos
DRi(At) (aii) = {z ∈ C : |z − aii| 6 Ri (At)} = {z ∈ C : |z − aii| 6 tRi (A)} ⊂ DRi(A) (aii) ,
Rodney Josue´ Biezuner 21
logo,
Gk (At) ⊂ Gk (A)
e
Gk (A) ∩ [G (At) \Gk (At)] = ∅
para 0 6 t 6 1. Porque os autovalores sa˜o func¸o˜es cont´ınuas das entradas de uma matriz, o caminho
λi (t) = λi (At)
e´ um caminho cont´ınuo que liga λi (A0) = λi (D) = aii a λi (A1) = λi (A). Seja 1 6 i 6 k. Como
λi (At) ∈ Gk (At) ⊂ Gk (A), conclu´ımos que para cada 0 6 t 6 1 existem k autovalores de At em Gk (A); em
particular, fazendo t = 1, obtemos que Gk (A) possui pelo menos k autovalores de A. Da mesma forma, na˜o
pode haver mais que k autovalores de A em Gk (A), pois os n− k autovalores restantes de A0 = D comec¸am
fora do conjunto Gk (A) e seguem caminhos cont´ınuos que permanecem fora de Gk (A). ¥
A unia˜o G (A) dos discos de Gershgorin e´ conhecida como a regia˜o de Gershgorin. Observe que enquanto
na˜o podemos em geral afirmar com certeza que cada disco de Gershgorin possui um autovalor, a segunda
afirmac¸a˜o do teorema permite-nos fazer tal conclusa˜o desde que os discos de Gershgorin sejam dois a dois
disjuntos.
O Teorema dos Discos de Gershgorin permite entender o resultado da Proposic¸a˜o 2.16: se uma matriz A e´
estritamente diagonalmente dominante, enta˜o os discos de Gershgorin DRi(A) (aii) na˜o interceptam a origem,
logo 0 na˜o pode ser um autovalor para a matriz A, o que implica que A e´ invert´ıvel. Ale´m disso, se todos
os elementos da diagonal principal de A sa˜o reais e positivos, enta˜o os autovalores de A esta˜o localizadosno
semiplano direito de C, de modo que se A e´ tambe´m sime´trica, conclu´ımos que todos os autovalores de A
sa˜o positivos.
A aplicac¸a˜o mais o´bvia do Teorema dos Discos de Gershgorin e´ na estimativa dos autovalores de uma
matriz. Usos mais refinados do Teorema de Gershgorin permitem obter conhecimento mais preciso sobre
onde os autovalores da matriz se encontram e correspondentemente melhores estimativas para o raio espectral
de uma matriz. Por exemplo, como A e At possuem os mesmos autovalores, existe um teorema dos discos
de Gershgorin equivalente para as colunas de uma matriz. Em particular, todos os autovalores de A esta˜o
localizados na intersec¸a˜o destas duas regio˜es: G (A)∩G (At). Isso implica a seguinte estimativa simples para
o raio espectral de uma matriz complexa:
2.18 Corola´rio. Se A ∈Mn (C), enta˜o
ρ (A) 6 min
 max
i=1,...,n
n∑
j=1
|aij | , max
j=1,...,n
n∑
i=1
|aij |
 = min (‖A‖L , ‖A‖C) .
Prova. O ponto no i-e´simo disco de Gershgorin que e´ mais distante da origem tem mo´dulo
|aii|+Ri (A) =
n∑
j=1
|aij |
e um resultado semelhante vale para as colunas de A. ¥
O resultado do Corola´rio 2.18 na˜o e´ surpreendente em vista do raio espectral de uma matriz ser menor que
qualquer norma matricial (veja o pro´ximo cap´ıtulo). Um resultado melhor pode ser obtido uma vez que
se observa que A e S−1AS tambe´m possuem os mesmos autovalores, qualquer que seja a matriz invert´ıvel
S. Em particular, quando S = D = diag (p1, . . . , pn) e´ uma matriz diagonal com todos os seus elementos
positivos, isto e´, pi > 0 para todo i, aplicando o Teorema de Gershgorin a` matriz
D−1AD =
(
pj
pi
aij
)
e a` sua transposta, obtemos o seguinte resultado que permite obter uma estimativa arbitrariamente boa dos
autovalores de A:
Rodney Josue´ Biezuner 22
2.19 Corola´rio. Se A ∈Mn (C) e p1, . . . , pn > 0, enta˜o todos os autovalores de A esta˜o contidos em
G
(
D−1AD
) ∩G (DAtD−1) = n⋃
i=1
z ∈ C : |z − aii| 6
1
pi
n∑
j=1
j 6=i
pj |aij |
 (2.14)
∩
n⋃
i=1
z ∈ C : |z − aii| 6 pj
n∑
i=1
i 6=j
1
pi
|aij |
 .
Em particular,
ρ (A) 6 min
p1,...,pn>0
 max
i=1,...,n
1
pi
n∑
j=1
pj |aij | , max
j=1,...,n
pj
n∑
i=1
1
pi
|aij |
 . (2.15)
2.4 Propriedade FC
Na nossa busca por propriedades para matrizes diagonalmente dominantes que garantira˜o a sua invertibil-
idade, uma observac¸a˜o fundamental e´ a de que se A e´ uma matriz diagonalmente dominante, enta˜o 0 na˜o
pode ser um ponto interior de nenhum disco de Gershgorin. De fato, se λ e´ um autovalor de A interior a
algum disco de Gershgorin enta˜o devemos ter desigualdade estrita
|λ− aii| < Ri (A) =
n∑
j=1
j 6=i
|aij |
para algum i. Se 0 e´ um autovalor de A interior a algum disco de Gershgorin, enta˜o
|aii| <
n∑
j=1
j 6=i
|aij |
para algum i e A na˜o pode ser diagonalmente dominante na linha i.
Uma condic¸a˜o equivalente para que um autovalor λ de A na˜o seja um ponto interior de nenhum disco de
Gershgorin e´ que
|λ− aii| > Ri (A) =
n∑
j=1
j 6=i
|aij | para todo i = 1, . . . , n.
Tais pontos λ na regia˜o de Gershgorin G (A) (na˜o necessariamente autovalores de A) constituem precisa-
mente a fronteira ∂G (A) da regia˜o de Gershgorin. Chamaremos a fronteira de um disco de Gershgorin
{z ∈ C : |z − aii| = Ri (A)} um c´ırculo de Gershgorin.
2.20 Lema. Seja A ∈ Mn (C) e λ um autovalor de A que na˜o e´ um ponto interior de nenhum disco de
Gershgorin. Seja x = (x1, . . . , xn) 6= 0 um autovetor associado a λ e k um ı´ndice tal que
|xk| > |xj | para j = 1, . . . , n.
Se i e´ qualquer ı´ndice tal que
|xi| = |xk|
Rodney Josue´ Biezuner 23
enta˜o o i-e´simo c´ırculo de Gershgorin passa por λ. Se, ale´m disso,
aij 6= 0,
enta˜o
|xj | = |xk|
e o j-e´simo c´ırculo de Gershgorin tambe´m passa por λ.
Prova. Como na demonstrac¸a˜o do Teorema de Gershgorin, temos
|xi| |λ− aii| 6
n∑
j=1
j 6=i
|aijxj | =
n∑
j=1
j 6=i
|aij | |xj | 6 |xk|
n∑
j=1
j 6=i
|aij | = |xk|Ri (A) (2.16)
para todo ı´ndice i. Logo, se |xi| = |xk|, temos
|λ− aii| 6 Ri (A) .
Como por hipo´tese
|λ− aii| > Ri (A)
para todo ı´ndice i, segue que
|λ− aii| = Ri (A) .
Em geral, |xi| = |xk| implica que as desigualdades em (2.16) sa˜o identidades; em particular,
n∑
j=1
j 6=i
|aij | |xj | = |xi|
n∑
j=1
j 6=i
|aij |
donde
n∑
j=1
j 6=i
|aij | (|xi| − |xj |) = 0.
Esta e´ uma soma de termos na˜o-negativos, pois |xi| > |xj |, logo se aij 6= 0 necessariamente devemos ter
|xj | = |xi| = |xk|. ¥
Este lema te´cnico tem as seguintes consequ¨eˆncias u´teis:
2.21 Teorema. Seja A ∈ Mn (C) uma matriz cujas entradas sa˜o todas na˜o-nulas e seja λ um autovalor
de A que na˜o e´ um ponto interior de nenhum disco de Gershgorin. Enta˜o todo c´ırculo de Gershgorin
de A passa por λ (isto e´, λ esta´ na intersec¸a˜o de todos os c´ırculos de Gershgorin de A) e se x =
(x1, . . . , xn) 6= 0 e´ um autovetor associado a λ enta˜o
|xi| = |xj | para todos i, j = 1, . . . , n.
Prova. Decorre diretamente do lema anterior. ¥
2.22 Corola´rio. Se A ∈ Mn (C) e´ uma matriz cujas entradas sa˜o todas na˜o-nulas e diagonalmente domi-
nante tal que |aii| >
n∑
j=1
j 6=i
|aij | para pelo menos alguma linha i, enta˜o A e´ invert´ıvel.
Rodney Josue´ Biezuner 24
Prova. Pois, como A e´ diagonalmente dominante, se 0 e´ um autovalor de A enta˜o 0 na˜o pode ser um ponto
interior de nenhum disco de Gershgorin. Por outro lado, pelo teorema anterior, segue que todo c´ırculo de
Gershgorin passa por 0. Entretanto, o i-e´simo c´ırculo de Gershgorin centrado em aii e com raio Ri < |aii|
na˜o pode passar por 0. Conclu´ımos que 0 na˜o e´ um autovalor de A, logo A e´ invert´ıvel. ¥
As matrizes do Corola´rio 2.22 sa˜o as ant´ıteses das matrizes esparsas que nos interessam. Usando com
maior cuidado a informac¸a˜o dada pelo Lema 2.20 podemos obter resultados que se aplicam a matrizes
esparsas.
2.23 Definic¸a˜o. Dizemos que uma matriz A = (aij) ∈Mn (C) satisfaz a propriedade FC se para todo par
de inteiros distintos i, j existe uma sequ¨eˆncia de inteiros distintos i1 = i, i2, i3, . . . , im−1, im = j, com
1 6 m 6 n, tais que todas as entradas matriciais
ai1i2 , ai2i3 , . . . , aim−1im
sa˜o na˜o-nulas.
Por exemplo, a matriz diagonalmente dominante na˜o-invert´ıvel 4 2 10 1 1
0 1 1
 ,
ja´ vista anteriormente, na˜o satisfaz a propriedade FC porque o par 2, 1 na˜o admite tal sequ¨eˆncia (a u´nica
sequ¨eˆncia poss´ıvel e´ a23, a31). Ja´ qualquer par de inteiros distintos i, j tal que aij 6= 0 admite a sequ¨eˆncia
trivial na˜o-nula aij , de modo que uma matriz cujas entradas na˜o-diagonais sa˜o todas na˜o-nulas satisfaz a
propriedade FC. O significado da abreviatura “FC”, ou “fortemente conexo”, ficara´ claro mais adiante.
2.24 Teorema. Seja A ∈Mn (C) uma matriz que satisfaz a propriedade FC e seja λ um autovalor de A que
na˜o e´ um ponto interior de nenhum disco de Gershgorin. Enta˜o todo c´ırculo de Gershgorin de A passa
por λ (isto e´, λ esta´ na intersec¸a˜o de todos os c´ırculos de Gershgorin de A) e se x = (x1, . . . , xn) 6= 0
e´ um autovetor associado a λ enta˜o
|xi| = |xj | para todos i, j = 1, . . . , n.
Prova. Seja x = (x1, . . . , xn) 6= 0 um autovetor associado a λ e i um ı´ndice tal que
|xi| > |xk| para k = 1, . . . , n.
Pelo Lema 2.20,
|λ− aii| = Ri (A) .
Seja j 6= i qualquer outro ı´ndice e i1 = i, i2, i3, . . . , im−1, im = j, com 1 6 m 6 n, ı´ndices tais que todas as
entradas matriciais
aii2 , ai2i3 , . . . , aim−1j 6= 0.
Como aii2 6= 0, segue da segunda afirmativa do Lema 2.20 que |xi2 | = |xi|. Mas enta˜o ai2i3 6= 0 e portanto
|xi3 | = |xi2 | = |xi|. Prosseguindo desta forma, conclu´ımos que
|xi| = |xi2 | = . . .
∣∣xim−1 ∣∣ = |xj | .
Em particular, segue novamente do Lema 2.20 que o j-e´simo c´ırculo de Gershgorin passa por λ. Como j e´
arbitra´rio,isso prova o teorema. ¥
2.25 Corola´rio. Se A ∈ Mn (C) e´ uma matriz que satisfaz a propriedade FC e diagonalmente dominante
tal que |aii| >
n∑
j=1
j 6=i
|aij | para pelo menos alguma linha i, enta˜o A e´ invert´ıvel.
Rodney Josue´ Biezuner 25
Prova. Segue do teorema anterior da mesma forma que o Corola´rio 2.22 segue do Teorema 2.21. ¥
Vamos tentar entender melhor o significado da propriedade FC. Note que ela se refere apenas a` localizac¸a˜o
dos elementos na˜o-nulos de A fora da diagonal principal – os elementos da diagonal principal e os valores
espec´ıficos dos elementos fora da diagonal principal sa˜o irrelevantes. Isso motiva as seguintes definic¸o˜es:
2.26 Definic¸a˜o. Dada uma matriz A = (aij) ∈ Mn (C) definimos o mo´dulo da matriz A como sendo a
matriz
|A| = (|aij |)
cujos elementos sa˜o os mo´dulos dos elementos da matriz A e a matriz indicadora de A como sendo
a matriz
M (A) = (µij) ,
onde
µij =
{
1 se aij 6= 0,
0 se aij = 0.
O conceito de uma sequ¨eˆncia de entradas na˜o-nulas da matriz A que aparece na definic¸a˜o da propriedade
FC pode ser visualizado em termos de caminhos em um grafo associado a A:
2.27 Definic¸a˜o. Dada uma matriz A ∈ Mn (C), o grafo direcionado de A e´ o grafo direcionado Γ (A)
com n nodos P1, . . . , Pn tais que existe um arco direcionado em Γ (A) de Pi a Pj se e somente se aij 6= 0.
Um caminho direcionado γ em um grafo Γ e´ uma sequ¨eˆncia de arcos Pi1Pi2 , Pi2Pi3 , . . . em Γ. O
comprimento de um caminho direcionado e´ o nu´mero de arcos sucessivos no caminho direcionado. Um
ciclo e´ um caminho direcionado que comec¸a e termina no mesmo no´.
Dizemos que um grafo direcionado e´ fortemente conexo se entre qualquer par de nodos distintos
Pi, Pj ∈ Γ existir um caminho direcionado de comprimento finito que comec¸a em Pi e termina em Pj .
Observe que quando Γ e´ um grafo direcionado com n nodos, se existe um caminho direcionado entre dois
nodos de Γ, enta˜o sempre existe um caminho direcionado entre estes dois nodos de comprimento menor que
ou igual a n− 1 (Exerc´ıcio 2.7).
2.28 Teorema. A ∈Mn (C) satisfaz a propriedade FC se e somente se Γ (A) e´ fortemente conexo.
Agora estamos em condic¸o˜es de verificar a invertibilidade das matrizes esparsas oriundas da discretizac¸a˜o
de EDPs atrave´s de diferenc¸as finitas:
2.29 Teorema. As matrizes de discretizac¸a˜o do problema modelo sa˜o invert´ıveis.
Prova. E´ fa´cil ver que as matrizes de discretizac¸a˜o obtidas no cap´ıtulo anterior para o intervalo e para
o quadrado sa˜o matrizes diagonalmente dominantes com dominaˆncia diagonal estrita nas linhas correspon-
dentes a pontos interiores adjacentes a` fronteira. Ale´m disso, elas satisfazem a propriedade FC. De fato, cada
ı´ndice i da matriz corresponde a um ponto interior Pi da malha e aij 6= 0 sempre que Pi e Pj sa˜o pontos
vizinhos naqueles esquemas. Enta˜o, dados dois pontos distintos Pi, Pj e´ fa´cil encontrar uma sequ¨eˆncia de
ı´ndices i1 = i, i2, i3, . . . , im−1, im = j, com 1 6 m 6 n, tais que todas as entradas matriciais
ai1i2 , ai2i3 , . . . , aim−1im
sa˜o na˜o-nulas: no caso unidimensional, basta percorrer a malha diretamente de Pi ate´ Pj (andando a partir
de Pi sempre para a direita ou sempre para a esquerda, conforme o caso, ate´ encontrar Pj), e no caso
bidimensional basta usar qualquer caminho interior de Pi ate´ Pj (pode-se usar a ordem lexicogra´fica para
percorrer a malha, ou a ordem lexicogra´fica inversa, dependendo das posic¸o˜es relativas de Pi e Pj ; no entanto,
estes caminhos sa˜o mais longos que o necessa´rio). Em outras palavras, identificando as malhas de pontos
internos com os grafos direcionados da matriz de discretizac¸a˜o, de modo que existe um arco direcionado entre
Rodney Josue´ Biezuner 26
dois pontos da malha se e somente se eles sa˜o vizinhos, os esquemas de discretizac¸a˜o considerados garantem
que estes grafos sa˜o fortemente conexos. ¥
Verificar a propriedade FC a partir do grafo direcionado de A pode ser impratica´vel se o tamanho da
matriz for muito grande ou se a matriz na˜o tiver origem na discretizac¸a˜o de um problema de EDPs. Existe
um me´todo computacional mais expl´ıcito para fazeˆ-lo:
2.30 Teorema. Sejam A ∈ Mn (C) e Pi, Pj nodos de Γ (A). Existe um caminho direcionado de compri-
mento m em Γ (A) de Pi para Pj se e somente se
(|A|m)ij 6= 0
ou, equivalentemente, se e somente se
[M (A)m]ij 6= 0.
Prova. Provaremos o teorema por induc¸a˜o. Para m = 1 a afirmativa e´ trivial. Para m = 2, temos(
|A|2
)
ij
=
n∑
k=1
(|A|)ik (|A|)kj =
n∑
k=1
|aik| |akj | ,
de modo que
(
|A|2
)
ij
6= 0 se e somente se aik, akj sa˜o ambos na˜o-nulos para algum ı´ndice k. Mas isso e´
equivalente a dizer que existe um caminho direcionado de comprimento 2 em Γ (A) de Pi para Pj .
Em geral, supondo a afirmativa provada para m, temos(
|A|m+1
)
ij
=
n∑
k=1
(|A|m)ik (|A|)kj =
n∑
k=1
(|A|m)ik |akj | 6= 0
se e somente se (|A|m)ik , akj sa˜o ambos na˜o-nulos para algum ı´ndice k. Por hipo´tese de induc¸a˜o, isso e´
equivalente a existir um caminho direcionado de comprimento m em Γ (A) de Pi para Pk e um caminho
direcionado de comprimento 1 em Γ (A) de Pk para Pj , isto e´, um caminho direcionado de comprimento
m+ 1 em Γ (A) de Pi para Pj . O mesmo argumento vale para M (A). ¥
2.31 Definic¸a˜o. Seja A = (aij) ∈ Mn (C). Dizemos que A > 0 se aij > 0 para todos 1 6 i, j 6 n e que
A > 0 se aij > 0 para todos 1 6 i, j 6 n.
2.32 Corola´rio. Seja A ∈ Mn (C). Existe um caminho direcionado de comprimento m em Γ (A) de cada
nodo Pi para cada nodo Pj se e somente se
|A|m > 0
ou, equivalentemente, se e somente se
M (A)m > 0.
2.33 Corola´rio. Seja A ∈Mn (C). A satisfaz a propriedade FC se e somente se
(I + |A|)n−1 > 0
ou, equivalentemente, se e somente se
[I +M (A)]n−1 > 0.
Rodney Josue´ Biezuner 27
Prova. Temos
(I + |A|)n−1 = I + (n− 1) |A|+
(
n− 1
2
)
|A|2 + . . .+
(
n− 1
n− 3
)
|A|n−1 + |A|n−1 > 0
se e somente se para cada par de ı´ndices i, j com i 6= j pelo menos um dos termos |A| , |A|2 , . . . , |A|n−1
tem uma entrada positiva em (i, j). Pelo Teorema 2.30, isso ocorre se e somente se existe algum caminho
direcionado em Γ (A) de Pi para Pj com comprimento 6 n−1. Isto e´ equivalente a A satisfazer a propriedade
FC. O mesmo argumento vale para M (A). ¥
Em geral, a maneira como uma matriz foi obtida (como as nossas matrizes de discretizac¸a˜o; veja a u´ltima
sec¸a˜o do cap´ıtulo) torna clara se elas sa˜o matrizes que satisfazem a propriedade FC ou na˜o. Se isso
na˜o e´ poss´ıvel, e pretende-se verificar a propriedade FC atrave´s do Corola´rio 2.33, e´ prefer´ıvel calcular
[I +M (A)]n−1, ja´ que M (A) e´ uma matriz composta apenas de 0’s e 1’s.
2.5 Matrizes Irredut´ıveis
A`s vezes, os resultados da sec¸a˜o anterior sa˜o formulados em termos de matrizes irredut´ıveis. Neste sec¸a˜o
examinaremos esta formulac¸a˜o equivalente.
Lembre-se que uma matriz de permutac¸a˜o P e´ uma matriz quadrada cujas entradas sa˜o todas 0 ou 1
e, ale´m disso, em cada linha e em cada coluna de P existe exatamente um 1. Em particular, P e´ uma matriz
ortogonal, de modo que P−1 = P t, isto e´, a inversa de P tambe´m e´ uma matriz de permutac¸a˜o. Um caso
especial de uma matriz de permutac¸a˜o e´ uma matriz de transposic¸a˜o, que e´ uma matriz de permutac¸a˜o T
igual a` matriz identidade exceto em duas posic¸o˜es, isto e´, para algum par de ı´ndices fixado k, l temos
Tij =
 δij se (i, j) 6= (k, l) , (l, k) , (k, k) ou (l, l) ,1 e (i, j) = (k, l) ou se (i, j) = (l, k) ,0 se (i, j) = (k, k) ou se (i, j) = (l, l) .
Matrizes de transposic¸a˜o sa˜o sime´tricas. O efeito de multiplicar uma matrizA por uma matriz de transposic¸a˜o
a` esquerda e´ trocar a posic¸a˜o de duas linhas da matriz A (no caso acima, as linhas k e l), enquanto que a
multiplicac¸a˜o de A por uma matriz de transposic¸a˜o a` direita muda a posic¸a˜o de duascolunas de A (no caso
acima, as colunas k e l).
TA =

1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1


a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
 =

a11 a12 a13 a14
a31 a32 a33 a34
a21 a22 a23 a24
a41 a42 a43 a44
 ,
AT =

a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44


1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
 =

a11 a13 a12 a14
a21 a23 a22 a24
a31 a33 a32 a34
a41 a43 a42 a44
 .
Pode-se provar que toda matriz de permutac¸a˜o P e´ o produto de matrizes de transposic¸a˜o P = T1 . . . Tm;
em particular, P t = Tm . . . T1. A matriz
P tAP = Tm . . . T1AT1 . . . Tm
e´ portanto obtida atrave´s da permutac¸a˜o de linhas e colunas de A, de modo que nenhum novo elemento e´
criado ou algum elemento existente de A destru´ıdo.
2.34 Definic¸a˜o. Dizemos que uma matriz A ∈Mn (C) e´ redut´ıvel se existe alguma matriz de permutac¸a˜o
P e algum inteiro 1 6 m 6 n− 1 tal que
P tAP =
[
B C
0 D
]
Rodney Josue´ Biezuner 28
onde B e´ uma matriz m×m, D e´ uma matriz (n−m)× (n−m), C e´ uma matriz m× (n−m) e 0 e´
a matriz nula (n−m)×m. Caso contra´rio, dizemos que A e´ irredut´ıvel.
Da definic¸a˜o vemos que se |A| > 0, enta˜o A e´ irredut´ıvel, e para que A seja redut´ıvel, ela precisa ter pelo
menos n− 1 zeros (caso m = 1). A motivac¸a˜o para este nome e´ a seguinte. Suponha que queiramos resolver
o sistema Ax = b e que A seja redut´ıvel. Enta˜o, se escrevermos
A = P tAP =
[
B C
0 D
]
,
teremos Ax = PAP tx = b ou AP tx = P tb; denotando x = P tx e b = P tb, resolver o sistema Ax = b e´ enta˜o
equivalente a resolver o sistema
Ax = b.
Escrevendo
x =
[
y
z
]
, b =
[
b1
b2
]
onde y, b1 ∈ Cm e z, b2 ∈ Cn−m, este sistema e´ por sua vez equivalente ao sistema{
By + Cz = b1
Dz = b2
Se resolvermos primeiro Dz = b2 e utilizarmos o valor de z encontrado na primeira equac¸a˜o resolvendo
By = b1 − Cz, teremos reduzido o problema original a dois problemas menores, mais fa´ceis de resolver.
2.35 Teorema. Uma matriz A ∈Mn (C) e´ irredut´ıvel se e somente se
(I + |A|)n−1 > 0
ou, equivalentemente, se e somente se
[I +M (A)]n−1 > 0.
Prova. Para provar o resultado, mostraremos que A e´ redut´ıvel se e somente se (I + |A|)n−1 possui pelo
menos uma entrada nula.
Assuma primeiramente que A e´ redut´ıvel, de modo que para alguma matriz de permutac¸a˜o P tenhamos
A = P
[
B C
0 D
]
P t =: PAP t.
Observe que
|A| = ∣∣PAP t∣∣ = P ∣∣A∣∣P t,
ja´ que o efeito de P e´ apenas trocar linhas e colunas. Ale´m disso, note que
A
k
=
[
Bk Ck
0 Dk
]
para alguma matriz Ck. Logo, como
(I + |A|)n−1 = (I + P ∣∣A∣∣P t)n−1 = P (I + ∣∣A∣∣)n−1 P t
= P
[
I + (n− 1) |A|+
(
n− 1
2
)
|A|2 + . . .+
(
n− 1
n− 3
)
|A|n−1 + |A|n−1
]
P t
Rodney Josue´ Biezuner 29
e todos os termos dentro dos colchetes sa˜o matrizes que tem um bloco (n−m)×m nulo no canto esquerdo
inferior, segue que (I + |A|)n−1 e´ redut´ıvel, logo possui entradas nulas e na˜o pode ser positiva.
Reciprocamente, suponha que (I + |A|)n−1 possui pelo menos uma entrada nula. Como
(I + |A|)n−1 = I +
n−1∑
m=1
(
n− 1
m
)
|A|m ,
(I + |A|)n−1 na˜o possui entradas diagonais nulas, logo podemos assumir que para algum par i 6= j temos[
(I + |A|)n−1
]
ij
= 0, o que implica [|A|m]ij = 0 para todo 1 6 m 6 n− 1. Pelo Teorema 2.30 (e observac¸a˜o
imediatamente posterior a` definic¸a˜o de grafo direcionado), na˜o existe um caminho direcionado em Γ (A) de
comprimento finito entre Pi e Pj . Defina os conjuntos de nodos
S1 := {Pk : Pk = Pj ou existe um caminho direcionado em Γ (A) entre Pk e Pj} ,
S2 = [ nodos de Γ (A)] \S1.
Por definic¸a˜o destes conjuntos, na˜o pode existir nenhum caminho de algum nodo de S2 para algum nodo de
S1, logo [|A|m]lk = 0 se Pl ∈ S2 e Pk ∈ S1. E ambos os conjuntos sa˜o na˜o-vazios, pois Pj ∈ S1 e Pi ∈ S2.
Renomeando os nodos de modo que
S1 =
{
P˜1, . . . , P˜m
}
,
S2 =
{
P˜m+1, . . . , P˜n
}
,
segue que existe uma matriz de permutac¸a˜o P tal que
P tAP =
[
B C
0 D
]
.
De fato, P e´ justamente a matriz de permutac¸a˜o que troca as colunas de tal forma que as varia´veis anteriores
correspondentes aos nodos P˜1, . . . , P˜m no sistema Ax = b sa˜o as novasm primeiras varia´veis do sistema linear
Ax = b; como na˜o existe nenhum caminho direcionado entre nenhum dos nodos P˜m+1, . . . , P˜n e qualquer um
dos nodos P˜1, . . . , P˜m, temos aij = 0 para m+ 1 6 i 6 n e 1 6 j 6 m pelo Teorema 2.30. ¥
2.36 Corola´rio. Uma matriz A ∈Mn (C) e´ irredut´ıvel se e somente se ela satisfaz a propriedade FC.
2.37 Proposic¸a˜o. Se A e´ uma matriz irredut´ıvel, diagonalmente dominante tal que |aii| >
n∑
j=1
j 6=i
|aij | para
pelo menos alguma linha i, enta˜o A e´ invert´ıvel.
Ale´m disso, se A e´ hermitiana e todos os elementos da diagonal principal de A sa˜o positivos, enta˜o
todos os autovalores de A sa˜o positivos.
Prova. O resultado segue do Teorema 2.34, do Corola´rio 2.25 e do Teorema dos Discos de Gershgorin (veja
comenta´rios apo´s o Teorema 2.18). ¥
2.38 Corola´rio. Os autovalores das matrizes de discretizac¸a˜o do problema modelo sa˜o positivos.
2.6 Exerc´ıcios
2.1 Mostre que as normas matriciais introduzidas na primeira sec¸a˜o deste cap´ıtulo (Exemplos 2.3 ate´ 2.11)
sa˜o de fato normas vetoriais.
Rodney Josue´ Biezuner 30
2.2 Mostre que a norma lp (Exemplo 2.5) e´ uma norma matricial.
2.3 Mostre que a norma l2 e´ diferente da 2-norma em Mn (veja Exemplo 2.10).
2.4 Seja V um espac¸o vetorial de dimensa˜o finita e ‖·‖1 , ‖·‖2 normas vetoriais quaisquer. Prove que existe
uma constante C > 0 tal que
1
C
‖x‖1 6 ‖x‖2 6 C ‖x‖1
para todo vetor x ∈ V .
2.5 Seja ‖·‖ uma norma matricial. Prove diretamente das propriedades de uma norma matricial que
‖I‖ > 1.
2.6 a) Seja ‖·‖ uma norma vetorial. Prove que se α > 0, enta˜o α ‖·‖ e´ tambe´m uma norma vetorial.
b) Seja ‖·‖ uma norma matricial. Conclua do Lema 2.14 que se α < 1, enta˜o α ‖·‖ na˜o e´ uma norma
matricial.
c) Seja ‖·‖ uma norma matricial. Se α > 1, podemos concluir que α ‖·‖ na˜o e´ uma norma matricial?
2.7 Mostre que se Γ e´ um grafo direcionado com n nodos, se existe um caminho direcionado entre dois
nodos de Γ, enta˜o sempre existe um caminho direcionado entre estes dois nodos de comprimento menor
que ou igual a n− 1
Cap´ıtulo 3
Me´todos Iterativos Lineares
Neste cap´ıtulo investigaremos os me´todos iterativos ba´sicos para a resoluc¸a˜o de sistemas lineares
Ax = b.
Embora a matriz A que temos em mente e´ em geral uma matriz grande e esparsa, do tipo que aparece em
esquemas de diferenc¸as finitas para equac¸o˜es diferenciais parciais, os me´todos considerados aqui requerem
em princ´ıpio apenas que A seja uma matriz invert´ıvel com todas as entradas diagonais aii na˜o-nulas (embora
a matriz A deva satisfazer crite´rios adicionais, de acordo com cada me´todo, para assegurar a convergeˆncia
para a soluc¸a˜o exata).
Me´todos iterativos requerem um chute inicial x0, ou seja, um vetor inicial que aproxima a soluc¸a˜o exata
x (se na˜o ha´ nenhuma informac¸a˜o dispon´ıvel sobre a soluc¸a˜o exata, de modo que na˜o temos como construir
o chute inicial de forma inteligente, x0 pode ser uma aproximac¸a˜o muito ruim de x). Uma vez que x0 e´
dado, o me´todo iterativo gera a partir de x0 uma nova aproximac¸a˜o x1, que esperamos deve aproximar
melhor a soluc¸a˜o exata. Em seguida, x1 e´ usada para gerar uma nova melhor aproximac¸a˜o x2 e assim por
diante. Desta forma, gera-se uma sequ¨eˆncia de vetores
(
xk
)
que espera-se convergir para x. Como na pra´tica
na˜o podemos iterar para sempre, algum crite´rio de parada deve ser estabelecido a priori. Uma vez que xk
esteja suficientemente pro´ximo da soluc¸a˜o exata quanto se precise, de acordo com uma margem de toleraˆncia
previamente fixada, pa´ra-seo processo de iterac¸a˜o e aceita-se xk como a soluc¸a˜o aproximada adequada para
o problema. Por exemplo, o crite´rio de parada pode ser estabelecido atrave´s de uma cota de toleraˆncia τ :
quando ∥∥b−Axk∥∥ < τ
ou quando ∥∥xk+1 − xk∥∥ < τ
as iterac¸o˜es sa˜o interrompidas e o u´ltimo valor aproximado obtido e´ aceito como a melhor aproximac¸a˜o da
soluc¸a˜o dentro das circunstaˆncias.
Os me´todos discutidos neste cap´ıtulo na˜o necessitam de um bom chute inicial (embora, e´ claro, quanto
melhor o chute inicial, menor o nu´mero de iterac¸o˜es necessa´rias para se chegar a` soluc¸a˜o aproximada com
a exatida˜o especificada). Embora os me´todos iterativos lineares sa˜o muitos lentos em relac¸a˜o a outros
me´todos iterativos desenvolvidos mais recentemente, sendo portanto raramente utilizados isoladamente, eles
sa˜o frequentemente usados hoje em dia como componentes de certos me´todos iterativos ultra-ra´pidos, tais
como o me´todo multigrid.
31
Rodney Josue´ Biezuner 32
3.1 Me´todo Iterativos Ba´sicos
3.1.1 Me´todo de Jacobi
O me´todo iterativo linear mais simples (que ja´ foi descrito tambe´m como o mais lento para convergir, embora
isso realmente depende da matriz A do sistema) e´ ome´todo de Jacobi (1845) Escrevendo o sistema Ax = b
na forma 
n∑
j=1
a1jxj = b1
...
n∑
j=1
anjxj = bn
,
se aii 6= 0 para todo i, cada xi pode ser isolado na i-e´sima equac¸a˜o e escrito na forma
xi =
1
aii
bi − n∑
j=1
j 6=i
aijxj
 .
Isso sugere definir um me´todo iterativo da seguinte forma: suposto xk =
(
xk1 , . . . , x
k
n
)
obtido no passo
anterior, obtemos xk+1 =
(
xk+11 , . . . , x
k+1
n
)
por
xk+1i =
1
aii
bi − n∑
j=1
j 6=i
aijx
k
j
 . (3.1)
No caso da fo´rmula de cinco pontos para o problema de Poisson, como a equac¸a˜o para cada ponto (i, j)
e´ dada por
−ui,j−1 − ui,j+1 + 4ui,j − ui−1,j − ui+1,j = h2fi,j
o me´todo de Jacobi e´
uk+1i,j =
1
4
(
uki,j−1 + u
k
i−1,j + u
k
i+1,j + u
k
i,j+1 + h
2fi,j
)
. (3.2)
No caso especial da equac¸a˜o de Laplace (f = 0) com condic¸a˜o de fronteira de Dirichlet na˜o-nula, o me´todo
de Jacobi e´ simplesmente a propriedade do valor me´dio discreta
uk+1i,j =
1
4
(
uki,j−1 + u
k
i−1,j + u
k
i+1,j + u
k
i,j+1
)
. (3.3)
Em outras palavras, calculados os valores de u em todos os pontos da malha na iterac¸a˜o anterior, o novo
valor de u em um ponto interior da malha nesta iterac¸a˜o e´ calculado atrave´s da me´dia dos seus quatro
pontos vizinhos. Os valores iniciais de u nos pontos interiores da malha para a primeira iterac¸a˜o (isto e´, o
chute inicial) podem ser atribuidos arbitrariamente ou atrave´s de algum argumento razoa´vel; por exemplo,
podemos utilizar uma me´dia ponderada dos valores de fronteira para o valor inicial em cada ponto interior
da malha, de acordo com a posic¸a˜o do ponto em relac¸a˜o aos pontos das quatro fronteiras discretizadas.
Em forma matricial, o algoritmo de Jacobi pode ser descrito da seguinte forma. Denotando por D = diag
(a11, . . . , ann) a matriz diagonal cujas entradas sa˜o as entradas diagonais de A, temos que
xk+1 = D−1
[
(D −A)xk + b] (3.4)
ou
xk+1 = D−1
(
Cxk + b
)
(3.5)
onde C = D −A e´ a matriz consistindo dos elementos restantes de A fora da diagonal principal.
Rodney Josue´ Biezuner 33
3.1.2 Me´todo de Gauss-Seidel
Um me´todo iterativo que converge cerca de duas vezes mais ra´pido que o me´todo de Jacobi (na maioria
das aplicac¸o˜es) e´ o me´todo de Gauss-Seidel (desenvolvido inicialmente por Gauss em 1819 para resolver
sistemas de equac¸o˜es lineares que apareciam no seu me´todo de quadrados mı´nimos e obtendo sua forma final
em 1874 por Seidel), onde os valores de x sa˜o atualizados dentro de cada iterac¸a˜o, sem esperar pela pro´xima.
Em outras palavras, obtido o valor de xk+1i este e´ usado no lugar de x
k
i no ca´lculo seguinte de x
k+1
i+1 . No
sistema Ax = b em que aii 6= 0 para todo i, como antes isolamos cada xi na i-e´sima equac¸a˜o mas desta vez
escrevemos
xi =
1
aii
bi − i−1∑
j=1
aijxj −
n∑
j=i+1
aijxj
 .
Enta˜o definimos
xk+1i =
1
aii
bi − i−1∑
j=1
aijx
k+1
j −
n∑
j=i+1
aijx
k
j
 (3.6)
pois os valores xk+11 , . . . , x
k+1
i−1 ja´ foram computados nesta iterac¸a˜o, enquanto que os valores x
k
i+1, . . . , x
k
n sa˜o
fornecidos pela iterac¸a˜o anterior.
Por exemplo, no caso da equac¸a˜o de Laplace, poder´ıamos utilizar a fo´rmula
uk+1i,j =
1
4
(
uk+1i,j−1 + u
k+1
i−1,j + u
k
i+1,j + u
k
i,j+1
)
(3.7)
assumindo que os pontos da malha sa˜o percorridos na ordem lexicogra´fica, de modo que quando vamos
calcular o valor de u no ponto i, j na iterac¸a˜o k + 1, nesta mesma iterac¸a˜o ja´ calculamos os valores de u em
i − 1, j e em i, j − 1, e usamos estes valores para calcular uk+1i,j ao inve´s dos valores uki,j−1 e uki−1,j obtidos
na iterac¸a˜o anterior.
Em forma matricial, o algoritmo de Gauss-Seidel pode ser descrito da seguinte forma. Dada uma matriz
A, existe uma u´nica decomposic¸a˜o
A = D − L− U (3.8)
ondeD e´ uma matriz diagonal, L e´ uma matriz estritamente triangular inferior e U e´ uma matriz estritamente
triangular superior; de fato, D = diag (a11, . . . , ann) e´ a parte diagonal de A, −L e´ a parte estritamente
triangular inferior de A e −U e´ a parte estritamente triangular superior de A. Enta˜o o algoritmo de Gauss-
Seidel pode ser definido por
xk+1 = D−1
(
Lxk+1 + Uxk + b
)
(3.9)
ou
(D − L)xk+1 = Uxk + b,
donde
xk+1 = (D − L)−1 (Uxk + b) . (3.10)
3.1 Exemplo. Existem matrizes para as quais o me´todo de Jacobi converge e o me´todo de Gauss-Seidel
diverge, e vice-versa. Veja o Exerc´ıcio 3.1. ¤
3.1.3 Me´todo SOR
O processo de corrigir uma equac¸a˜o atrave´s da modificac¸a˜o de uma varia´vel e´ a`s vezes chamado de relax-
amento. Antes da correc¸a˜o, a equac¸a˜o na˜o e´ verdadeira; como um conjunto de partes que na˜o se ajustam,
ela esta´ em estado de tensa˜o. A correc¸a˜o de uma varia´vel relaxa a tensa˜o. O me´todo de Gauss-Seidel efetua
relaxamento sucessivo, ou seja, passa de equac¸a˜o para equac¸a˜o, relaxando uma depois da outra. [Watkins]
Por este motivo, os me´todos de Jacobi e de Gauss-Seidel sa˜o tambe´m chamados me´todos de relaxamento.
Em muitos casos, a convergeˆncia pode ser substancialmente acelerada atrave´s de sobrerelaxamento. Isso
Rodney Josue´ Biezuner 34
significa que ao inve´s de fazer uma correc¸a˜o para a qual a equac¸a˜o e´ satisfeita exatamente, no´s fazemos
uma correc¸a˜o maior. No caso mais simples, escolhe-se um fator de relaxamento ω > 1 que sobrecorrige por
aquele fator em cada passo (se mover um passo na direc¸a˜o de xk para xk+1 e´ bom, mover naquela direc¸a˜o
ω > 1 passos e´ melhor). Este e´ o chamado me´todo de sobrerelaxamento sucessivo (SOR, successive
overrelaxation; desenvolvido em 1950 por Young): usando o me´todo de Gauss-Seidel obtemos
x̂k+1i =
1
aii
bi − i−1∑
j=1
aijx
k+1
j −
n∑
j=i+1
aijx
k
j
 ;
da´ı tomamos
xk+1i = x
k
i + ω
(
x̂k+1i − xki
)
.
Isso pode ser resumido em
xk+1i = x
k
i + ω
 1
aii
bi − i−1∑
j=1
aijx
k+1
j −
n∑
j=i+1
aijx
k
j
− xki
 . (3.11)
Quando ω = 1, o me´todo SOR e´ exatamente o me´todo de Gauss-Seidel. Um fator ω < 1 (subrelaxamento)
normalmente diminui a velocidade de convergeˆncia.
Para a maioria dos problemas, o melhor valor para o fator de relaxamento e´ desconhecido. Para a matriz
de discretizac¸a˜o obtida a partir da fo´rmula de cinco pontos, e´ sabido que o valor o´timo de ω e´, como veremos
na pro´xima sec¸a˜o,
ω =
2
1 + sen (pih)
. (3.12)
Em forma matricial, o me´todo SOR pode ser descrito da seguinte forma. Como antes, dada uma matriz
A escrevemos
A = D − L− U (3.13)
ondeD e´ uma matriz diagonal, L e´ uma matriz estritamente