Sistemas Lineares e Inversão de Matrizes

Métodos Numéricos Computacionais

Douglas Rodrigues

São Paulo State University - UNESP

School of Sciences / Department of Computing
Bauru, SP - Brazil
Sistemas Lineares e Inversão de
Matrizes
Sistemas Lineares e Inversão de Matrizes

Um problema fundamental normalmente encontrado na descrição

matemática de fenômenos fı́sicos é o da solução simultânea de um
conjunto de equações. Traduzido para a linguagem matemática, tais
fenômenos passam a ser descritos por um conjunto de m equações em
que se deseja determinar a solução de n variáveis de interesse,
normalmente chamadas de incógnitas.

1
Sistemas Lineares e Inversão de Matrizes

Um sistema de equações lineares ou simplesmente sistema linear é

um conjunto de m equações lineares, ou seja, é um conjunto de equações
lineares do tipo:


a11 x1 + a12 x2 + · · · + a1n xn = b1


a21 x1 + a22 x2 + · · · + a2n xn = b2


.. .. .. ..
. . . .





am1 x1 + am2 x2 + · · · + amn xn = bm


em que aij e bi são constantes reais, para i = 1, . . . , m e j = 1, . . . , n.

2
Sistemas Lineares e Inversão de Matrizes

Na forma matricial, este sistema é representado por Ax = b sendo

     
a11 a12 · · · a1j · · · a1n x1 b1
 21 a22 · · · a2j · · · a2n 
 a   x   b2 
 2   
 . .. .. ..   .. 
  .. 
 .. . . .   .  .
  
A= x =  b= 
  
 ai1 ai2 · · · aij · · · ain 

 xj   bi 
 .. .. .. ..   ..  ..
     
 
 . . . .   .   . 
am1 am2 · · · amj · · · amn xn bm
| {z } | {z } | {z }
Matriz dos coeficientes Vetor de Vetor dos termos
de ordem m×n incógnitas de independentes de
ordem n×1 ordem m×1

Quando m = n, o sistema de equações lineares é dito quadrado.

Resolver um sistema Ax = b consiste em determinar um vetor
x ∗ = (x1 , x2 , . . . , xn )T que satisfaça simultaneamente todas as equações
lineares que compõem o sistema.
3
Sistemas Lineares e Inversão de Matrizes

Classificação do Sistema Linear quanto à Solução

Os tipos de soluções dos sistemas lineares dependem da matriz A:

1. Sistema Possı́vel ou Compatı́vel

ˆ Admite solução.

4
Sistemas Lineares e Inversão de Matrizes

2. Sistema Possı́vel e Determinado

ˆ Possui uma única solução;
ˆ O determinante de A deve ser diferente de zero (A é uma matriz não
singular);
ˆ Se b for um vetor nulo (constantes nulas), a solução do sistema será
a solução trivial, ou seja, o vetor x também será nulo.

5
Sistemas Lineares e Inversão de Matrizes

3. Sistema Possı́vel e Indeterminado

ˆ Possui infinitas soluções;
ˆ O determinante de A deve ser nulo (A é uma matriz singular);
ˆ O vetor de constantes b deve ser nulo ou múltiplo de uma coluna de
A.

6
Sistemas Lineares e Inversão de Matrizes

4. Sistema Impossı́vel ou Incompatı́vel

ˆ Não possui solução;
ˆ O determinante de A deve ser nulo;
ˆ O vetor b não pode ser nulo ou múltiplo de alguma coluna de A.

7
Sistemas Lineares e Inversão de Matrizes

Definições

1. Um sistema linear Ax = b é homogêneo se o vetor

b = (b1 , b2 , . . . , bm )T = 0. Um sistema homogêneo é sempre
consistente, uma vez que o vetor nulo é sempre solução deste
sistema.

8
Sistemas Lineares e Inversão de Matrizes

3. Matriz Transposta Seja A ∈ Rn×n com A = (aij ), i = 1, . . . , n e

j = 1, . . . , n. A matriz transposta de A, denotada por AT , é definida
a partir da matriz A por: AT = (bij ), i = 1, . . . , n e j = 1, . . . , n tal
que bij = aji .  
a11 a12 · · · a1n
 a21 a22 · · · a2n 
 
A= .  .. .. .. 
 .. . . . 


an1 an2 · · · ann

 
a11 a21 · · · an1
 a12 a22 · · · an2 
 
T
A = .  .. .. .. 
 .. . . . 


a1n a2n ··· ann

9
Sistemas Lineares e Inversão de Matrizes

4. Matriz Simétrica Uma matriz A ∈ Rn×n , com A = (aij ),

i = 1, . . . , n e j = 1, . . . , n é simétrica se aij = aji (i ̸= j), com i,
j = 1, . . . , n.  
a11 a12 · · · a1n
 a12 a22 · · · a2n 
 
A=  .. .. .. .. 
 . . . . 


a1n a2n ··· ann

10
Sistemas Lineares e Inversão de Matrizes

4. Matriz Triangular Inferior Uma matriz A ∈ Rn×n , com A = (aij ),

i = 1, . . . , n e j = 1, . . . , n é triangular inferior se aij = 0, para
i < j, com i, j = 1, . . . , n.
 
a11 0 0 0 0
 a
 21 a22 0 0 0  
a31 a32 a33 0 0 
 
A=
 .. .. .. ..
 
.

 . . . 0 
an1 an2 an3 ··· ann

11
Sistemas Lineares e Inversão de Matrizes

4. Matriz Triangular Superior Uma matriz A ∈ Rn×n , com A = (aij ),

i = 1, . . . , n e j = 1, . . . , n é triangular superior se aij = 0, para
i > j, com i, j = 1, . . . , n.
 
a11 a12 a13 · · · a1n
22 a23 · · ·
 0 a a2n 
 
0 0 a33 · · · a3n 
 
A=
 .. .. .. ..
 
.

 . . . 0 
0 0 0 · · · ann

12
Sistemas Lineares e Inversão de Matrizes

Observações

ˆ Sistema triangular inferior: matriz do sistema é uma matriz

triangular inferior.
ˆ Sistema triangular superior: matriz do sistema é uma matriz
triangular superior.

13
Sistemas Lineares e Inversão de Matrizes

5. Sistemas Equivalentes Sejam P e P ′ dois sistemas lineares

(quadrados ou retangulares). Diz-se que o sistema P ′ é equivalente
a P (notação: P P ′ ) se P ′ é obtido de P a partir das seguintes
operações elementares:
ˆ Trocar a posição de linhas ou de colunas de P;
ˆ Multiplicar uma linha de P por um escalar a ̸= 0;
ˆ Multiplicar uma linha de P por um escalar a ̸= 0 e somar a uma
outra linha do sistema.
Se P e P ′ são equivalentes, então a solução de P ′ é solução de P.

14
Sistemas Lineares e Inversão de Matrizes

Exemplo: Considere

(
x1 + x2 = 2
P:
x1 − x2 = 0

Multiplicando a 1a linha de P por α = −1 e adicionando à 2a linha de P,

obtém-se o sistema equivalente P ′ dado por
(
′ x1 + x2 = 2
P :
0x1 − 2x2 = −2

Na forma matricial,

! !
1 1 2 ′ 1 1 2
P= P = → matriz triangular superior.
1 −1 0 0 −2 −2

15
Sistemas Lineares e Inversão de Matrizes

Classificação dos sistemas lineares

ˆ Métodos Diretos: são aqueles que fornecem solução exata do

sistema linear, caso ela exista, após um número finito de operações.
ˆ Métodos Iterativos: geram uma sequência de vetores {x (k) } a
partir de uma aproximação inicial x (0) . Sob determinadas condições,
esta sequência converge para a solução x ⋆ , caso ela exista.

16
Sistemas Triangulares
Sistemas Triangulares

Para sistemas lineares Ax = b possı́veis e determinados (det(A) ̸= 0) de

dimensão n × n, o vetor solução x, é dado por x = A−1 b. No entanto,
calcular explicitamente a inversa de uma matriz não é aconselhável,
devido à quantidade de operações envolvidas. Surge então a necessidade
de utilizar técnicas mais avançadas e eficientes como as apresentadas a
seguir.

17
Sistema Triangular Inferior

Seja o sistema triangular inferior, com aii ̸= 0 para i = 1, 2, . . . , n:



 a11 x1 = b1


a21 x1 + a22 x2

= b2
.. .



 . = ..

an1 x1 + an2 x2 + · · · + ann xn = bn


18
Sistema Triangular Inferior

Por substituição progressiva pode-se resolvê-lo pelas fórmulas:

b1
x1 =
a11

Pi−1
bi − j=1 aij xj
xi = , i = 1, 2, . . . , n.
aii

19
Sistema Triangular Inferior

Exemplo: Resolver o sistema triangular inferior,

    
1 0 0 y1 9
 0 1 0  y2  = 1
    
1 1
2 2 1 y3 7

20
Sistema Triangular Inferior

Resolução: Por substituição progressiva tem-se:

y1 = 9

y2 = 1

1 1
y1 + y2 + y3 = 7 ⇒ y3 = 2
2 2
Portanto,

 
9
y ∗ = 1
 
2

21
Sistema Triangular Superior

Seja aii ̸= 0 com i = 1, 2, . . . , n e o sistema triangular superior dado por:



 a11 x1 + a12 x2 + . . . + a1n xn = b1


a22 x2 + . . . + a2n xn

= b2
.. .



 . = ..

ann xn = bn


22
Sistema Triangular Superior

Por substituição retroativa pode-se resolvê-lo pelas fórmulas:

bn
xn =
ann

Pn
bi − j=i+1 aij xj
xi = , i = n − 1, . . . , 1.
aii

23
Sistema Triangular Superior

Exemplo: Resolver o sistema triangular superior,

    
2 1 3 x1 9
 0 −1 1  x2  = 1
    
0 0 1 x3 2

24
Sistema Triangular Superior

Resolução: Por substituição retroativa tem-se:

x3 = 2

−x2 + x3 = 1 ⇒ x2 = 1

2x1 + x2 + 3x3 = 9 ⇒ x1 = 1

Portanto,

 
1
y ∗ = 1
 
2

25
Métodos Diretos
Método de Gauss Jordan

Seja o sistema linear Ax = b, onde A tem todas as submatrizes principais

não singulares, ou seja, det(Ak ) ̸= 0, k = 1, . . . , n. O método de Gauss
Jordan consiste em transformar o sistema original Ax = b em um sistema
equivalente A′ x = b ′ , onde a matriz dos coeficientes A′ é uma matriz
diagonal.
Para isso utiliza-se aplicações sucessivas da operação: “Subtrair de uma
equação outra equação multiplicada por uma constante não nula”.

26
Método de Gauss Jordan

Descrição do Método: considere o sistema:



a11 x1 + a12 x2 + · · · + a1n xn = b1

a21 x1 + a22 x2 + · · · + a2n xn = b2


.. .. .. ..
. . . .





am1 x1 + am2 x2 + · · · + amn xn = bm


27
Método de Gauss Jordan

A matriz dos coeficientes aumentada é dada por:

 (1) (1) (1) (1) 

a11 a12 ··· a1n b1
(1) (1) (1) (1)
a21 a22 ··· a2n b2
 
A(1) = 
 
.. .. .. .. .. 
.
 
 . . . . 
(1) (1) (1) (1)
an1 an2 ··· ann bn

em que

(1)
aij = aij ,

(1)
bi = bi ,
em que i, j = 1, 2, . . . , n.

28
Método de Gauss Jordan

Passo 1:
(1)
Por hipótese tem-se que a11 ̸= 0, pois det(A(1) ) ̸= 0.
Eliminar a incógnita x1 da 2a , 3a , . . ., na equações (isto é, zerar os
elementos da primeira coluna abaixo da diagonal principal). Isso é
feito da seguinte forma:
(1)
a21
ˆ Subtrair da 2a equação a 1a equação multiplicada por m21 = (1) .
a11
(1)
a31
ˆ Subtrair da 3a equação a 1a equação multiplicada por m31 = (1) .
a11
(1)
an1
ˆ Subtrair da na equação a 1a equação multiplicada por mn1 = (1) .
a11

29
Método de Gauss Jordan

Ao final desta etapa, tem-se a seguinte matriz:

 (1) (1) (1) (1) 

a11 a12 ··· a1n b1
(1) (1) (1)
0 a22 ··· a2n b2
 
A(2) = 
 
.. .. .. .. .. 
.
 
 . . . . 
(1) (1) (1)
0 an2 ··· ann bn

30
Método de Gauss Jordan

em que,

(1)
ai1
mi1 = (1)
, i = 2, 3, . . . , n
a11

(2) (1) (1)

aij = aij − mi1 a1j , i = 2, 3, . . . , n, j = 1, 2, . . . , n

(2) (1) (1)

bi = bi − mi1 b1 , i = 2, 3, . . . , n
(1)
ai1
Observação: Os elementos mi1 = (1) , i = 2, 3, . . . , n são denominados
a11
(1)
multiplicadores e o elemento a11 é denominado pivô da primeira etapa.

31
Método de Gauss Jordan

Passo 2:
(2)
Por hipótese tem-se que a22 ̸= 0, pois det(A(2) ) ̸= 0.
Eliminar a incógnita x2 da 1a , 3a , 4a , . . ., na equações (isto é, zerar
os elementos da segunda coluna acima e abaixo da diagonal
principal). Para isso:
(2)
a12
ˆ Subtrair da 1a equação a 2a equação multiplicada por m12 = (2) .
a22
(2)
a32
ˆ Subtrair da 3a equação a 2a equação multiplicada por m32 = (2) .
a22
(2)
a42
ˆ Subtrair da 4a equação a 2a equação multiplicada por m42 = (2) .
a22
(2)
an2
ˆ Subtrair da na equação a 2a equação multiplicada por mn2 = (2) .
a22

32
Método de Gauss Jordan

Ao final desta etapa, tem-se a seguinte matriz:

 
(1) (3) (3) (3)
a11 0 a13 ··· a1n b1
 (2) (2) (2) (2) 

 0 a22 a23 ··· a2n b2 

(3) (3) (3)
A(3) =
 0 0 a33 ··· a3n b3 

 .. .. .. .. .. 

 . . . . . 

(3) (3) (3)
0 0 an3 ··· ann bn

33
Método de Gauss Jordan

em que,

(2)
ai2
mi2 = (2)
, i = 3, 4, . . . , n
a22

(3) (2) (2)

aij = aij − mi2 a2j , i = 3, . . . , n, j = 2, . . . , n

(3) (2) (2)

bi = bi − mi2 b2 , i = 3, . . . , n

34
Método de Gauss Jordan

Seguindo raciocı́nio análogo, procede-se até a etapa n obtendo a matriz

final:

 
(1) (n+1)
a11 0 0 ··· 0 b1
 (2) (n+1) 

 0 a22 0 ··· 0 b2 

(3) (n+1)
A(3) =
 0 0 a33 ··· 0 b3 

 .. .. .. .. .. 

 . . . . . 

(n) (n+1)
0 0 0 ··· ann bn

35
Método de Gauss Jordan

com

(n)
ain
min = (n)
ann

(n+1) (n) (n)

aij = aij − min anj , i = 1, . . . , n − 1, j = n

(n+1) (n)
bi = bi − min bn(n) , i = 1, . . . , n − 1

36
Método de Gauss Jordan

O sistema correspondente é dado por:

(1) (n+1)
a11 x1 = b1
(2) (n+1)
a22 x2 = b2
(3) (n+1)
a33 x3 = b3 (1)
..
.
(n)
ann xn = bn(n+1)

que é equivalente ao sistema linear original.

37
Método da Decomposição LU

O processo de Decomposição LU é uma das técnicas mais utilizadas para

resolver um sistema linear Ax = b. Esta técnica consiste na
decomposição da matriz A em um produto de matrizes L e U.
Considera-se L uma matriz triangular inferior com a diagonal unitária e U
uma matriz triangular superior.

38
Método da Decomposição LU

Teorema:

Seja A = (aij ) uma matriz quadrada de ordem n, e Ak o menor

principal, constituı́do das k primeiras linhas e k primeiras colunas de
A.
Se det(Ak ̸= 0), k = 1, 2, . . . , n − 1, pois sempre é considerado
det(A) ̸= 0, existe uma única matriz triangular inferior L = (lij ),
com l11 = l22 = . . . = lnn = 1, e uma única matriz triangular superior
U = (uij ) tal que L × U = A.
Além disso, det(A) = u11 × u22 × . . . × unn .

39
Método da Decomposição LU

Observação: As
 submatrizes 
correspondentes aos menores principais
2 4 −1
da matriz A =  8 1 0  são obtidas como segue:
 
3 1 5

ˆ A1 = submatriz formada de A considerando a 1a linha e a 1a coluna,

ou seja, A1 = (2)
ˆ A2 = submatriz formada de A considerando as!2 primeiras linhas e
2 4
as 2 primeiras colunas, ou seja, A2 =
8 1
ˆ A3 = submatriz formada de A considerando  as 3 primeiras
linhas e
2 4 −1
as 3 primeiras colunas, ou seja, A3 = A =  8 1 0 
 
3 1 5

40
Processo de Decomposição da Matriz A em LU

Para obter os fatores lij e uij das matrizes L e U pode-se aplicar as

definições de produto e igualdade de matrizes, ou seja, L × U = A:
1 0 0 ··· 0 u11 u12 u13 ··· u1n a11 a12 a13 ··· a1n
    
l21
 1 0 ··· 0
 0
 u22 u23 ··· u2n 

a21
 a22 a23 ··· a2n 

l31 l32 1 ··· 0
 0 0 u33 ··· u3n  a31 a32 a33 ··· a3n 
=

   
 . . . .  . . . .   . . . . 
 . . . .. . 
 . . . .. .   . . . .. . 
 . . . . .  . . . . .   . . . . . 
ln1 ln2 ln3 ··· 1 0 0 0 ··· unn an1 an2 an3 ··· ann
| {z }| {z } | {z }
L U A

41
Processo de Decomposição da Matriz A em LU

Para obter os elementos da matriz L e da matriz U, deve-se calcular os

elementos da linha de U e os elementos da coluna de L na seguinte
ordem:
ˆ 1a linha de U:

a11 = u11 


a12 = u12 


.. ⇒ u1j = a1j , j = 1, 2, . . . , n
.






a1n = u1n
ˆ 1a coluna de L:

a21
a21 = l21 u11 ⇒ l21 = u11




a31 
a31 = l31 u11 ⇒ l31 = u11 
 ai1
.. ⇒ li1 = , i = 2, . . . , n
u11
.





an1 

an1 = ln1 u11 ⇒ ln1 = u11
42
Processo de Decomposição da Matriz A em LU

ˆ 2a linha de U:

a22 = l21 u12 + u22 ⇒ u22 = a22 − l21 u12

a23 = l21 u13 + u23 ⇒ u23 = a23 − l21 u13
..
.
a2n = l21 u1n + u2n ⇒ u2n = a2n − l21 u1n

ˆ 2a coluna de L:
a32 −l31 u12
a32 = l31 u12 + l32 u22 ⇒ l32 = u22
a42 −l41 u12
a42 = l41 u12 + l42 u22 ⇒ l42 = u22
..
.
an2 −ln1 u12
an2 = ln1 u12 + ln2 u22 ⇒ ln2 = u22

43
Processo de Decomposição da Matriz A em LU

Calculando 3a linha, 3a coluna, 4a linha, 4a coluna etc., obtém-se as

fórmulas gerais:

uij = aij − Pi−1 lik ukj i ≤j
k=1
Pj−1
lij = aij − k=1 lik ukj i >j
ujj

44
Aplicação da Decomposição LU na resolução de Sistemas Line-
ares

Seja o sistema linear Ax = b de ordem n, em que A satisfaz às condições

da Decomposição LU (Teorema). Então o sistema Ax = b pode ser
escrito como:
(LU)x = b

L(Ux) = b

Fazendo Ux = y , a solução do sistema linear pode ser obtida a partir da

resolução dos sistemas triangulares:

Ly = b

Ux = y

45
Aplicação da Decomposição LU na resolução de Sistemas Line-
ares

Observações:

ˆ A Decomposição LU fornece um dos algoritmos mais eficientes para

o cálculo do determinante de uma matriz.
ˆ Se det(A) ̸= 0 e para algum k, det(Ak ) = 0 é possı́vel trocar a linha
k por uma linha abaixo dela e se det(Ak ) ̸= 0 pode-se efetuar a
decomposição. Lembrar de trocar também o termo independente.

46
Método de Gauss Compacto

Seja o sistema linear Ax = b, de ordem n, em que A possui todas as

submatrizes não singulares.
O Método de Gauss Compacto é uma maneira prática de se obter as
matrizes L e U da Decomposição LU, armazenando-as de forma
compacta. Os termos independentes bi , i = 1, . . . , n são obtidos da
mesma maneira que os elementos uij e serão chamados de uin+1 ,
i = 1, . . . , n.

47
Construção do método

Seja o sistema linear

 
a11 a12 a13 ··· a1n

 a21 a22 a23 ··· a2n 

a31 a32 a33 ··· a3n
 
 
.. .. .. .. ..
 
.
 
 . . . . 
an1 an2 an3 ··· ann

Primeiro, monta-se a matriz ampliada (A|b) de ordem n × (n + 1):

 
a11 x1 a12 x2 ··· a1n xn b1
a21 x1 a22 x2 ··· a2n xn b2
 
 
 .. .. .. .. .. 
. . . . .
 
 
an1 x1 an2 x2 ··· ann xn bn

em que ain+1 = bi , i = 1, 2, . . . , n.
48
Método de Gauss Compacto

Em seguida, construir a matriz n × (n + 1), em que os termos

independentes bi , com i = 1, 2, . . . , n, obtidos da mesma maneira que os
elementos uij , serão chamados de uin+1 , i = 1, 2, . . . , n.
Assim, sobre a matriz original armazena-se a matriz:

 
u11 u12 ··· u1n u1,n+1
l21 u22 ··· u2n u2,n+1 
 

 .. .. .. .. 
. . . .
 
 
ln1 ln2 ··· lnn un,n+1

49
Método de Gauss Compacto

Para determinar os termos uij e lij , i, j = 1, 2, . . . , n utiliza-se as mesmas

expressões da Decomposição LU, entretanto, i = 1, 2, . . . , n e
j = 1, 2, . . . , n, n + 1:

uij = aij − Pi−1 lik ukj i ≤j
k=1
Pj−1
lij = aij − l ik u kj
ujj
k=1
i >j

Determinados os elementos uij e lij , i, j = 1, 2, . . . , n resolve-se o sistema

Ux = b ′ , em que b ′ é a última coluna da tabela (elementos uin+1 ,
i = 1, 2, . . . , n).

50
Método de Gauss Compacto

Observação: Se L é triangular inferior com lij = 1, i = 1, 2, . . . , n e b ′ é

obtido da maneira descrita anteriormente então b = Lb ′ . Desta forma
basta resolver apenas o sistema triangular superior Ux = b ′ .

51
Sistemas Associados

Uma das vantagens do método de Gauss Compacto, é poder resolver de

uma só vez vários sistemas associados a uma mesma matriz dos
coeficientes.

52
Método de Cholesky

Para a aplicação do método de Cholesky é necessário o conceito de

matriz definida positiva, cuja definição é dada a seguir.
Definição: Uma matriz real simétrica An×n é chamada definida
positiva se det(Ak ) > 0, k = 1, 2, . . . , n.
Teorema: Se A é simétrica e definida positiva então A pode ser
decomposta unicamente em L ∗ LT sendo L uma matriz triangular inferior
com elementos diagonais positivos.

53
Método de Cholesky

O Método de Cholesky é definido para a resolução de sistemas lineares de

ordem quadrada n cuja matriz dos coeficientes seja simétrica e definida
positiva. A decomposição feita a seguir considera estas hipóteses.

··· ···
 a11 a12 a1n
  l11
 l11 l12 l1n

a21 a22 ··· a2n l21 l22 l22 ··· l2n
=
    
. . .. . . . .. .. .
 . . . . . . .

. . 
. . . . . .
an1 an2 ··· ann ln1 ln2 ··· lnn lnn

Assim, a matriz dos coeficientes A é decomposta no produto L ∗ LT , em

que L é uma matriz triangular inferior com elementos da diagonal
estritamente positivos.

54
Método de Cholesky

Aplicando a definição de produto matricial em A = L ∗ LT , obtém-se as

seguintes fórmulas para os elementos de L e sua transposta:
Elementos da Diagonal Principal


2
a11 = l11


 2 2
a22 = l21

+ l22
..



 .

2 2 2
ann = ln1 + ln2 + · · · + lnn


55
Método de Cholesky

Desta forma, para elementos da diagonal principal tem-se

l11 = √a11

q
lii = aii − Pi−1 l 2 , i = 1, 2, . . . , n.
k=1 ik

56
Método de Cholesky

Elementos não diagonais



 a21 = l21 l11


a32 = l31 l11
 
ai1
1a coluna . ⇒ li1 = , i = 1, 2, . . . , n

.. l11



an1 = ln1 l11




 a32 = l31 l21 + l32 l22

 (
a42 = l41 l21 + l42 l22
 Pj−1
aij − k=1 lik ljk
2a coluna . ⇒ lij = , i = 2, 3, . . . , n

 .. ljj



an2 = ln1 l21 + ln2 l22


57
Método de Cholesky



 aj+1,j = lj+1,1 lj1 + lj+1,2 lj2 + · · · + lj+1,j ljj


aj+2,j = lj+2,1 lj1 + lj+2,2 lj2 + · · · + lj+2,j ljj

j-ésima coluna .

 ..



an,j = ln1 lj1 + ln2 lj2 + · · · + lnj ljj


Assim, para os elementos fora da diagonal principal tem-se


li1 = ai1 , i = 1, 2, . . . , n
l11 P
j−1
lij = aij − k=1 lik ljk , 2 < j < 1.
ljj

58
Método de Cholesky

Uma vez calculada a matriz L, a solução do sistema Ax = b fica reduzida

à solução dos seguintes sistemas triangulares:

Ax = b (
T
Ly = b
(LL )x = b ⇒
T
LT x = y
L(L x) = b

59
Método de Cholesky

Observações:

ˆ Utilizando a Decomposição de Cholesky, tem-se que A = L ∗ LT .

Portanto, det(A) = (det(L))2 = (l11 ∗ l22 ∗ . . . ∗ lnn )2 .
ˆ Se A não é definida positiva as fórmulas ainda valem, mas
trabalha-se com números complexos.

60
Cálculo da Matriz Inversa
Cálculo da Matriz Inversa

Seja A uma matriz quadrada de ordem n. Se det(A) ̸= 0, então existe

uma matriz B, tal que:

AB = BA = I ( I é a matriz identidade)

A matriz B é chamada de matriz inversa de A e representada por

B = A−1 e vale a relação

AA−1 = A−1 A = I

61
Cálculo da Matriz Inversa

Dessa forma,

··· ··· ···

    
a11 a12 a1n b11 b12 b1n 1 0 0
a21 a22 ··· a2n 
 b21
 b22 ··· b2n  0 1 ··· 0
=
   
 . . .   . . .  . . .
 . . .. .   . . .. .  . . .. .
 . . . .  . . . .  . . . .
an1 an2 ··· ann bn1 bn2 ··· bnn 0 0 ··· 1
| {z }| {z } | {z }
A A−1 I

Portanto, para determinar as n colunas da matriz A−1 resolve-se n

sistemas lineares utilizando qualquer método visto anteriormente.

62
Cálculo da Matriz Inversa

    
a11 a12 ··· a1n b11 1
a21 a22 ··· a2n  b21  0
    
  .  =  .  ⇒ Primeira coluna de A−1

 .. .. .. ..   .  .
. . . .   .  .


an1 an2 ··· ann bn1 0

    
a11 a12 ··· a1n b12 0
a21 a22 ··· a2n  b22  1
    
  .  =  .  ⇒ Segunda coluna de A−1

 .. .. .. ..   .  .
. . . .   .  .


an1 an2 ··· ann bn2 0

    
a11 a12 ··· a1n b1n 0
a21 a22 ··· a2n   2n  0
b
    
  .  =  .  ⇒ n-ésima coluna de A−1

 .. .. .. ..   .  .
. . . .   .  .


an1 an2 ··· ann bnn 1 63
Cálculo da Matriz Inversa

. . .
Resumidamente, seja A−1 = [b1 ..b2 .. · · · ..bn ] a matriz inversa de A, tal que
bj é a j-ésima coluna de A−1 para j = 1, 2, . . . , n. Além disso, considere
. . .
e a j-ésima coluna da matriz identidade I , ou seja, I = [e ..e .. · · · ..e ],
j n×n 1 2 n
tal que

 
0
.
 .. 
 
ej = 1 → j-ésima linha de e.
 
.
.
.
0

64
Cálculo da Matriz Inversa

Sabendo que AA−1 = I e utilizando as partições efetuadas anteriormente

pode-se escrever:

. . . . . .
A[b1 ..b2 .. · · · ..bn ] = [e1 ..e2 .. · · · ..en ]

Isto fornece o sistema linear Abj = ej , para j = 1, 2, . . . , n. Assim,

resolvendo estes sistemas por qualquer método de sistemas lineares
(desde que suas condições sejam satisfeitas), encontra-se cada coluna de
A−1 .

65
Cálculo da Matriz Inversa

Observação: Se det(A) = 0 diz-se que a matriz A é não inversı́vel ou

singular.
As colunas de A−1 podem ser obtidas utilizando:

66
Cálculo da Matriz Inversa

Método de Decomposição LU

Abj = ej (LU)bj = ej , para j = 1, 2, . . . , n.

Resolve-se os sistemas:

(
Lyj = ej
j = 1, 2, . . . , n
Ubj = yj

67
Cálculo da Matriz Inversa

Método de Gauss Compacto

Deve-se utilizar o mesmo esquema da resolução de sistemas matriciais
associados, isto é:
··· ···
a a a
 b b b
 1 0 · · · 0
11 12 1n 11 12 1n
··· ··· ···
a21 a22 a2n
 b21 b22 b2n
0 1 0
=  ..
 
 .. .
. .. .  .
. .
.
. .. . 
.
.
. .. .
.
. . . . . . . . . . . .
an1 an2 ··· ann bn1 bn2 ··· bnn 0 0 ··· 1

Fazendo A × B = I as colunas da matriz B são as colunas da matriz

inversa, desde que A × A = I .

68
Cálculo da Matriz Inversa

Método de Cholesky (somente para matriz simétrica e positiva definida)

(LLT )bj = ej , j = 1, 2, . . . , n

Resolve-se o sistema:
(
Lyj = ej
j = 1, 2, . . . , n
LT bj = yj

69
Métodos Iterativos
Métodos Iterativos

Métodos iterativos são aqueles que se baseiam na construção de

sequências de aproximações. A partir de uma aproximação inicial, a cada
passo, os valores calculados anteriormente são utilizados para melhorar a
aproximação obtendo resultados aproximados.
Para utilizar tais métodos é necessário o conceito de norma de matrizes
apresentado a seguir.

70
Norma de Vetores

A maioria dos métodos utilizam como critério de parada algum tipo de

norma de vetores.
Definição: Chama-se norma de um vetor x, ∥x∥, qualquer função
definida num espaço vetorial E, com valores em ℜ, satisfazendo as
seguintes condições:

1. ∥x∥ > 0, com ∥x∥ = 0 ⇔ x = 0

2. ∥λx∥ = |λ| ∗ ∥x∥, ∀λ ∈ ℜ
3. ∥x∥ ≤ ∥x∥ + ∥y ∥ (desigualdade triangular).

71
Norma de Vetores

Definição: Os principais tipos de normas de vetores são:

Pn
1. ∥x∥1 = i=1 |xi | Norma 1
qP
n 2
2. ∥x∥E = i=1 xi Norma Euclidiana
3. ∥x∥∞ = max1≤i≤n |xi | Norma Infinito

Definição: Dada uma sequência de vetores x (k) ∈ E, diz-se que a

sequência {x (k) } converge para x ∈ E se ∥x (k) − x∥ ← 0, quando k ← ∞.

72
Métodos Iterativos

Como mencionado anteriormente, um método iterativo consiste em

calcular uma sequência x (1) , x (2) , . . . , x (k) de aproximações da solução x ∗
do sistema Ax = b, a partir de uma aproximação inicial x (0) , utilizando
A, b e a solução aproximada obtida na iteração anterior. Os métodos
iterativos são utilizados principalmente em matrizes esparsas e de grande
porte, pois preservam a esparsidade da matriz A.

73
Método de Jacobi-Richardson (Jacobi)

Considere aii ̸= 0 para i = 1, 2, . . . , n e o sistema de equações lineares



a11 x1 + a12 x2 + · · · + a1n xn = b1

a21 x1 + a22 x2 + · · · + a2n xn = b2



 .. .. .. ..


 . . . .

am1 x1 + am2 x2 + · · · + amn xn = bm


74
Método de Jacobi-Richardson (Jacobi)

O Método de Jacobi consiste na determinação de uma sequência de

(k) (k) (k)
aproximantes de ı́ndice k, x1 , x2 , . . . , xn , com k = 1, 2, 3, . . ., a partir
(0) (0) (0)
de valores iniciais x1 , x2 , . . . , xn , com k = 1, 2, 3, . . ., através do
processo iterativo definido por:

(k)
b1 −a12 x2 −···−a1n xn(k)

(k+1)
x1

 = a11
(k)
b2 −a21 x1 −···−a2n xn(k)

 (k+1)
x =
2 a22


···
 (k) (k)
 (k+1)
 bn −an1 x1 −···−ann−1 xn−1
xn = ann

75
Método de Jacobi-Richardson (Jacobi)

Critério de Convergência
O Método de Jacobi converge quando um dos critérios abaixo é
satisfeito:

ˆ Critério das Linhas:

n
X aij
max <1
1≤i≤n aii
j=1
j̸=i

ˆ Critério das Colunas:

n
X aij
max <1
1≤j≤n ajj
i=1
i̸=j

76
Método de Jacobi-Richardson (Jacobi)

Critério de Parada (CP)

O método iterativo de Jacobi-Richardson para quando:

∥x (k+1) − x (k) ∥∞
<ϵ
∥x (k+1) ∥∞

sendo ϵ um valor pré-estabelecido para a precisão.

77
Método de Jacobi-Richardson (Jacobi)

Observações:

ˆ A convergência independe de x (0) .

ˆ No método de Jacobi todos os valores de x da iteração k + 1
dependem dos valores de x da iteração k, por isso o método é
também chamado de Método dos deslocamentos simultâneos.
ˆ Na implementação utiliza-se também como critério de parada um
número máximo de iterações.

78
Método de Gauss-Seidel

O método de Gauss-Seidel é uma variante do método de Jacobi que

acelera a busca da solução para o sistema.
No método de Jacobi, o processo iterativo é descrito como:
(k)
b1 −a12 x2 −···−a1n xn(k)

(k+1)


x1 = a11
(k)
b2 −a21 x1 −···−a2n xn(k)

x (k+1) =

2 a22


· · ·
 (k) (k)
 (k+1)
 bn −an1 x1 −···−ann−1 xn−1
xn = ann

(k+1) (k+1)
Observe que quando se calcula x2 o valor de x1 já é conhecido e,
(k+1) (k+1) (k+1)
quando se calcula x3 já se sabe x2 e x1 .

79
Método de Gauss-Seidel

(k+1) (k)
Como x1 é uma melhor aproximação de x1 que x1 , pode-se utilizá-lo
(k+1) (k+1) (k+1)
no cálculo de x2 , assim como pode-se utilizar x2 e x1 no
(k+1)
cálculo de x3 .
Assim como no método de Jacobi, dado o sistema linear, o Método de
Gauss-Seidel consiste na determinação de uma sequência de aproximantes
(k) (k) (k)
de ı́ndice k, x1 , x2 , . . . , xn , com k = 1, 2, 3, . . ., a partir de valores
(0) (0) (0)
iniciais x1 , x2 , . . . , xn , com k = 1, 2, 3, . . ., através do processo
definido por:
(k) (k)
b1 −a12 x2 −a13 x3 −···−a1n xn(k)

(k+1)
x1

 = a11
(k+1) (k)
b2 −a21 x1 −a23 x3 −···−a2n xn(k)

 (k+1)
x =
2 a22


 ···
 (k+1) (k+1) (k+1)
 (k+1)
 bn −an1 x1 −an2 x2 −···−ann−1 xn−1
xn = ann

80
Método de Gauss-Seidel

Critério de Convergência
O método de Gauss-Seidel converge quando um dos critérios é satisfeito:

ˆ Critério das Linhas:

n
X aij
max <1
1≤i≤n aii
j=1
j̸=i

ˆ Critério de Sassenfeld: max βi < 1 sendo βi calculado por

1≤i≤n
recorrência:
i−1   Xn
X aij aij
βi = βj +
aii aii
j=1 i+1

81
Método de Gauss-Seidel

Critério de Parada (CP)

Dada uma precisão ϵ, o método iterativo de Gauss-Seidel para quando:

∥x (k+1) − x (k) ∥∞
<ϵ
∥x (k+1) ∥∞

82
Método de Gauss-Seidel

Observações:

ˆ Dado um sistema linear Ax = b pode acontecer que o método de

Jacobi seja convergente enquanto o método de Gauss-Seidel seja
divergente e vice-versa.
ˆ A convergência para os métodos: Jacobi e Gauss-Seidel não depende
do valor inicial x (0) .
ˆ O critério de parada é igual para os dois métodos.
ˆ O método de Jacobi usa sempre o valor de x da iteração anterior,
enquanto o método de Gauss-Seidel usa sempre o valor de x mais
recente.

83
Questions?

Thank you!