2 - Sistemas de equações lineares

Prévia do material em texto

Análise Numérica – Sistemas de Equações Lineares
Prof. Matheus Nohra Haddad
matheus.haddad@ufop.edu.br
Sala A302
Departamento de Computação e Sistemas
Universidade Federal de Ouro Preto
mailto:matheus.haddad@ufop.edu.br
SISTEMAS DE EQUAÇÕES LINEARES
 Um sistema de equações lineares pode ser representado na forma:
𝑎11 𝑎12 ⋯ 𝑎1𝑛 𝑥1
𝑎21 𝑎22 ⋯ 𝑎2𝑛 𝑥2
⋮ ⋮ ⋱ ⋮ ⋮
𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛 𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
𝐴𝑥 = 𝑏
Matriz dos coeficientes
Vetor solução
Vetor de termo independentes
NÚMERO DE SOLUÇÕES
 O número de soluções de um sistema linear pode ser determinado 
de acordo com o determinante da matriz dos coeficientes.
 det 𝐴 ≠ 0 – Solução única.
 det 𝐴 = 0 – Infinitas ou nenhuma solução.
 Quando o determinante for igual a zero o que pode determinar se o 
sistema tem infinitas ou nenhuma solução é o escalonamento da matriz 
dos coeficientes junto com o vetor de termos independentes.
MÉTODOS PARA SOLUÇÃO DE SISTEMAS LINEARES
 Métodos diretos
 São aqueles em que a solução exata é obtida com um número finito de 
operações
 Métodos iterativos
 A solução é obtida por meio de iterações. A precisão da solução é 
determinada de acordo com o número de iterações.
SISTEMAS TRIANGULARES
 São sistemas nos quais a matriz dos coeficientes A é triangular 
inferior ou superior;
SISTEMAS TRIANGULARES
 Inferior
𝑙11 0 ⋯ 0
𝑙21 𝑙22 ⋯ 0
⋮ ⋮ ⋱ ⋮
𝑙𝑛1 𝑙𝑛2 ⋯ 𝑙𝑛𝑛
𝑥1
𝑥2
⋮
𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
 Neste sistema a solução pode ser calculada simplesmente por 
substituições sucessivas.
ALGORITMO DE SUBSTITUIÇÕES SUCESSIVAS
𝑙11 0 ⋯ 0
𝑙21 𝑙22 ⋯ 0
⋮ ⋮ ⋱ ⋮
𝑙𝑛1 𝑙𝑛2 ⋯ 𝑙𝑛𝑛
𝑥1
𝑥2
⋮
𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
𝑙11𝑥1 = 𝑏1
1
𝑏1
𝑥 =
𝑙11
𝑙21𝑥1 + 𝑙22𝑥2 =𝑏2
2
𝑏2 − 𝑙21𝑥1
𝑥 =
𝑙22
ALGORITMO DE SUBSTITUIÇÕES SUCESSIVAS
𝑙11 0 ⋯ 0
𝑙21 𝑙22 ⋯ 0
⋮ ⋮ ⋱ ⋮
𝑙𝑛1 𝑙𝑛2 ⋯ 𝑙𝑛𝑛
𝑥1
𝑥2
⋮
𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
𝑙31𝑥1 + 𝑙32𝑥2 + 𝑙33𝑥3 = 𝑏3
3
𝑏3 −
𝑥 =
𝑙31𝑥1 + 𝑙32𝑥2
𝑙33
ALGORITMO DE SUBSTITUIÇÕES SUCESSIVAS
𝑙11 0 ⋯ 0
𝑙21 𝑙22 ⋯ 0
⋮ ⋮ ⋱ ⋮
𝑙𝑛1 𝑙𝑛2 ⋯ 𝑙𝑛𝑛
𝑥1
𝑥2
⋮
𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
𝑥𝑖 =
𝑗 =1𝑏𝑖 − ∑
𝑖−1 𝑙𝑖𝑗𝑥𝑗
𝑙𝑖 𝑖
ALGORITMO DE SUBSTITUIÇÕES SUCESSIVAS
 Transformando em pseudocódigo
Algoritmo Substituições sucessivas
Utilizado para soluções de sistemas triangulares 
Entrada:
A – Matriz dos coeficientes
b – Vetor de termos independentes
n – Ordem do sistema
Saída:
x – Vetor solução
Para i = 1 até n faça
soma = 0;
Para j = 1 até i – 1 faça
soma = soma + A(i,j)*x(j);
Fim para
x(i) = (b(i) - soma)/A(i,i); 
Fim Para
ALGORITMO DE SUBSTITUIÇÕES RETROATIVAS
𝑢11 𝑢12 ⋯ 𝑢1𝑛 𝑥1 
0 𝑢22 ⋯ 𝑢2𝑛 𝑥2
⋮ ⋮ ⋱ ⋮ ⋮
0 0 0 𝑢𝑛𝑛 𝑥𝑛
=
𝑏1
𝑏2
⋮
𝑏𝑛
𝑥 =
𝑗 =𝑖+1𝑏𝑖 − ∑
𝑛 𝑢𝑖𝑗𝑥𝑗
𝑙𝑖 𝑖
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 -2 8 -1 -15
3 4 -6 5 29
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/ 1 = −2 -2 8 -1 -15
3 4 -6 5 29
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 −𝑚21𝐿1 + 𝐿2
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 −𝑚31𝐿1 + 𝐿3
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 0 6 -3 -15 −𝑚31𝐿1 + 𝐿3
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 𝑚32 = 6/2 = 3 0 6 -3 -15 −𝑚31𝐿1 + 𝐿3
6
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 𝑚32 = 6/2 = 3 0 6 -3 -15 −𝑚31𝐿1 + 𝐿3
6 −𝑚32𝐿4 + 𝐿5
ELIMINAÇÃO DE GAUSS
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 𝑚32 = 6/2 = 3 0 6 -3 -15 −𝑚31𝐿1 + 𝐿3
6 0 0 -12 -36 −𝑚32𝐿4 + 𝐿5
ELIMINAÇÃO DE GAUSS (ALGORITMO)
Algoritmo Eliminação de Gauss
Objetivo: Determinar o sistema triangular superior 
Entrada:
A – Matriz dos coeficientes
b – Vetor de termos independentes 
n – Ordem do sistema
Saída:
A – Matriz dos coeficientes escalonada
b – Vetor de termos independentes ajustados 
Para j = 1 até n - 1 faça
Para i = j+1 até n faça
m(i,j) = A(i,j)/A(j,j); 
Para k = 1 até n faça
A(i,k) = -m(i,j)*A(j,k) + A(i,k);
Fim para
b(i) = -m(i,j)*b(j) + b(i);
Fim para
Fim para
L
Multiplicador
A b Operação
1 1 -3 2 11
2 𝑚21 = −2/1 = −2 -2 8 -1 -15
3 𝑚31 = 4/1 = 4 4 -6 5 29
4 0 2 3 7 −𝑚21𝐿1 + 𝐿2
5 𝑚32 = 6/2 = 3 0 6 -3 -15 −𝑚31𝐿1 + 𝐿3
6 0 0 -12 -36 −𝑚32𝐿4 + 𝐿5
DECOMPOSIÇÃO LU
 Podemos decompor uma matriz qualquer A no produto de duas 
outras, uma triangular inferior L (Lower) e outra triangular 
superior U (Upper).
𝐴 = 𝐿𝑈
 Podemos usar esta propriedade para ajudar na solução de um 
sistema linear. Então vejamos:
𝐴𝑥 = 𝑏
𝐿𝑈𝑥 = 𝑏
 Podemos então fazer uma transformação de variáveis.
𝑈𝑥 = 𝑦
𝐿𝑦 = 𝑏
DECOMPOSIÇÃO LU
 Utilizamos a eliminação de Gauss para determinar a matrizes L e U:
 A matriz L é obtida utilizando os multiplicadores.
𝐿 =
0 0 ⋯ 0
1 0 ⋯ 0
1
𝑚21
𝑚31 𝑚32
⋮ ⋮
𝑚𝑛1 𝑚𝑛2
1 ⋯ 0
⋮ ⋱ ⋮
𝑚𝑛3 ⋯ 1
 A matriz U é obtida utilizando a matriz A escalonada.
𝑈 =
𝑢11 𝑢12 ⋯ 𝑢1𝑛
0 𝑢22 ⋯ 𝑢2𝑛
⋮ ⋮ ⋱ ⋮
0 0 ⋯ 𝑢𝑛𝑛
PROPRIEDADES DO DETERMINANTE
 Se duas linhas de matriz forem trocadas, então o determinante 
troca o sinal.
 det 𝐵 = −1 𝑡det 𝐴 onde t = número de trocas
 Se todos os elementos de uma linha de A forem multiplicados por
uma constante k então o valor do determinante fica multiplicado
pela mesma constante.
 B(1,:) = kA(1,:) então det(B) = kdet(A)
PROPRIEDADES DO DETERMINANTE
 Se um múltiplo escalar de uma linha ou coluna de A for somado à
outra linha ou coluna, respectivamente, então o determinante não
se altera.
B = A e B 𝑖, : = 𝐴 𝑖, : + 𝑘𝐴 𝑙, : com 𝑙 ≠ 𝑖 então det(B) = det(A)
 Se uma matriz for triangular 𝑛
det(A) = ∏ 𝑎𝑖𝑖
𝑖=1
 Se C = AB então
det 𝐶 = det 𝐴 det 𝐵
PROPRIEDADES DO DETERMINANTE
 Utilizando estas propriedades é possível calcular o determinante 
facilmente dentro dos algoritmos de solução de sistemas lineares.
PROPRIEDADES DO DETERMINANTE
 Cálculo do determinante com decomposição LU
 Usando a propriedade do determinante de uma matriz triangular
𝑛
det(L) = ∏ 𝑙𝑖𝑖
𝑖=1
𝑛
det(U) = ∏ 𝑢𝑖𝑖
𝑖=1
PROPRIEDADES DO DETERMINANTE
 Usando a propriedade da multiplicação de matrizes e determinantes
det 𝐴 = det 𝐿 det 𝑈
𝑖=1
det 𝐿 = 1, det 𝑈 = ∏ 𝑢𝑖 𝑖
det 𝐴
𝑛
= 1 ∏ 𝑢𝑖𝑖 ∴ det 𝐴
𝑖=1
𝑛
= ∏ 𝑢𝑖𝑖
𝑖=1
𝑛
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 1 -3 2 11
2 -2 8 -1 -15
3 4 -6 5 29ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/ 4 = 0,25 1 -3 2 11
2 -2 8 -1 -15
3 4 -6 5 29
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/ 4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 −𝑚11𝐿3 + 𝐿1
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 −𝑚21𝐿3 + 𝐿2
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 0 5 1,5 -0,5 −𝑚21𝐿3 + 𝐿2
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 𝑚12 = −1,5/ 5 = −0,3 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 0 5 1,5 -0,5 −𝑚21𝐿3 + 𝐿2
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 𝑚12 = −1,5/ 5 = −0,3 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 0 5 1,5 -0,5 −𝑚21𝐿3 + 𝐿2
−𝑚12𝐿2 + 𝐿1
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 𝑚12 = −1,5/ 5 = −0,3 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 0 5 1,5 -0,5 −𝑚21𝐿3 + 𝐿2
1 0 0 1,2 3,6 −𝑚12𝐿2 + 𝐿1
ELIMINAÇÃO DE GAUSS COM PIVOTAÇÃO PARCIAL
 Dispositivo prático
𝐴 =
1 3 2
−2 8
4 −6 5
−1 , 𝑏 =
11
−15
29
L Multiplicador A b Operação
1 𝑚11 = 1/4 = 0,25 1 -3 2 11
2 𝑚21 = −2/4 = −0,5 -2 8 -1 -15
3 4 -6 5 29
1 𝑚12 = −1,5/5 = −0,3 0 -1,5 0,75 3,75 −𝑚11𝐿3 + 𝐿1
2 0 5 1,5 -0,5 −𝑚21𝐿3 + 𝐿2
1 0 0 1,2 3,6 −𝑚12𝐿2 + 𝐿1
𝒑 = 3 2 1
SOLUÇÃO DE SISTEMA LINEAR COM PIVOTAÇÃO PARCIAL
 Para iniciar o processo de solução do sistema linear baseado na
decomposição da matriz dos coeficientes precisamos determinar
uma matriz P.
 A matriz P é uma matriz identidade com as linhas na ordem do
vetor p.
 Para o exemplo acima teríamos uma matriz P.
0 0 1
𝑃 = 0 1 0
1 0 0
 O vetor p = [3 2 1] por isto a terceira linha foi trocada de lugar com
a primeira.
SOLUÇÃO DO SISTEMA LINEAR COM PIVOTAÇÃO PARCIAL
 Fazendo a transformação de variáveis
𝑃𝐴 = 𝐿𝑈
 Multiplicando por P o sistema Ax=b
𝑃𝐴𝑥 = 𝑃𝑏
𝐿𝑈𝑥 = 𝑃𝑏
 Fazendo a mudança de variáveis
𝐿𝑦 = 𝑃𝑏
𝑈𝑥 = 𝑦
SOLUÇÃO DO SISTEMA LINEAR COM PIVOTAÇÃO PARCIAL
 Montando a matriz L
 Os valores de 𝑚𝑖𝑗 são dados tais que j é a posição da coluna do elemento e i = p(k)
onde k é o número da linha.
 Para o exemplo anterior temos:
𝐿 =
𝑝 = 3 2 1
1
𝒎𝒊𝟏
𝒎𝒊𝟏
0 0
1 0
𝒎𝒊𝟐 1
𝒎𝒊𝟏 ∴ 𝑖 = 𝑝 2
𝒎𝒊𝟏 ∴ 𝑖 = 𝑝 3
𝒎𝒊𝟐 ∴ 𝑖 = 𝑝 3
= 2 ∴ 𝒎𝟐𝟏
= 1 ∴ 𝒎𝟏𝟏
= 1 ∴ 𝒎𝟏𝟐
𝐿 =
1
𝒎𝟐𝟏
𝒎𝟏𝟏 𝒎𝟏𝟐
0 0
1 0
1
SOLUÇÃO DO SISTEMA LINEAR COM PIVOTAÇÃO PARCIAL
 Para o exemplo anterior
𝐿 =
1
𝒎𝟐𝟏
𝒎𝟏𝟏
0 0
1 0
𝒎𝟏𝟐 1
1 0 0
𝐿 = −𝟎,𝟓 1 0
𝟎,𝟐𝟓 −𝟎,𝟑 1
𝑈 =
4 −6 5
0 5 1,5
0 0 1,2
CÁLCULO DO DETERMINANTE
 De acordo com a decomposição pela eliminação de Gauss com 
pivotação
𝑃𝐴 = 𝐿𝑈
det 𝑃𝐴 = det 𝐿𝑈
 Usando as propriedades de determinante
det 𝐴 =
det 𝐿 det 𝑈
det 𝑃
det 𝐿 = ∏ 𝑙𝑖𝑖 = 1
det 𝑈 = ∏𝑢𝑖𝑖
DECOMPOSIÇÃO DE CHOLESKY
 Utilizada quando a matriz dos coeficientes é simétrica e definida 
positiva.
 Diz que uma matriz A simétrica e definida positiva pode ser 
decomposta na multiplicação de uma matriz triangular inferior 
pela sua transposta.
𝐴 = 𝐿𝐿𝑇
DECOMPOSIÇÃO DE CHOLESKY
 Determinando os elementos de L.
𝑙11 0 0 0
𝑙21
𝑙31
𝑙22 0
𝑙32 𝑙33
𝑙41 𝑙42 𝑙43 𝑙44
𝑙11 𝑙21 𝑙31
0 0 𝑙22 𝑙32
0 0 0 𝑙33
0 0 0
𝑙41
𝑙42
𝑙43
𝑙44
=
𝑎11
𝑎21
𝑎31
𝑎41
𝑎12
𝑎22
𝑎32
𝑎42
𝑎13
𝑎23
𝑎33
𝑎43
𝑎14
𝑎24
𝑎34
𝑎44
DECOMPOSIÇÃO DE CHOLESKY
 Determinando os elementos de L.
𝑙11 0 0 0
𝑙21
𝑙31
𝑙22 0
𝑙32 𝑙33
𝑙41 𝑙42 𝑙43 𝑙44
𝑙11 𝑙21 𝑙31
0 0 𝑙22 𝑙32
0 0 0 𝑙33
0 0 0
𝑙41
𝑙42
𝑙43
𝑙44
=
𝑎14
𝑎24
𝑎34
𝑎11
𝑎21
𝑎31
𝑎41
𝑎12
𝑎22
𝑎32
𝑎42
𝑎13
𝑎23
𝑎33
𝑎43 𝑎44
41𝑙
2 + 𝑙2 + 𝑙2 + 𝑙2
42 43 44 = 𝑎44
44𝑙
2 = 𝑎44 − 41𝑙
2 + 𝑙2 + 𝑙2
42 43
𝑙44 = 𝑎44 − 41𝑙
2 + 𝑙2 + 𝑙2
42 43
DECOMPOSIÇÃO DE CHOLESKY
 Determinando os elementos de L.
𝑙11
𝑙21
𝑙31
𝑙41
0 0
𝑙22 0
𝑙32 𝑙33
𝑙42 𝑙43
0 𝑙11 𝑙21 𝑙31 𝑙41
0 0 𝑙22 𝑙32 𝑙42
0 0 0 𝑙33 𝑙43
𝑙44 0 0 0 𝑙44
=
𝑎11
𝑎21
𝑎31
𝑎41
𝑎12
𝑎22
𝑎32
𝑎42
𝑎13
𝑎23
𝑎33
𝑎43
𝑎14
𝑎24
𝑎34
𝑎44
𝑙44 = 𝑎44 − 41𝑙
2
42+ 𝑙
2
43+ 𝑙
2
𝑙𝑖𝑖 =
𝑗 =1
𝑖−1
𝑖 𝑗
𝑎𝑖𝑖 − ∑ 𝑙2 , 𝑗 = 1,2, ⋯ , 𝑛
DECOMPOSIÇÃO DE CHOLESKY
 Determinando os elementos de L.
𝑙11
𝑙21
0 0 0
𝑙22 0 0
𝑙31 𝑙32 𝑙33 0
𝑙41 𝑙42 𝑙43 𝑙44
𝑙11 𝑙21 𝑙31
0 𝑙22 𝑙32
0 0 𝑙33
0 0 0
𝑙41
𝑙42
𝑙43
𝑙44
=
𝑎13
𝑎23
𝑎33
𝑎11
𝑎21
𝑎31
𝑎41
𝑎12
𝑎22
𝑎32
𝑎42 𝑎43
𝑎14
𝑎24
𝑎34
𝑎44
𝑙41𝑙31 + 𝑙42𝑙32 + 𝑙43𝑙33 = 𝑎43
43
𝑎43 −
𝑙 =
𝑙41𝑙31 + 𝑙42𝑙32
𝑙33
DECOMPOSIÇÃO DE CHOLESKY
 Determinando os elementos de L.
𝑙11
𝑙21
𝑙31
𝑙41
0 0
𝑙22 0
𝑙32 𝑙33
𝑙42 𝑙43
0 𝑙11 𝑙21 𝑙31 𝑙41
0 0 𝑙22 𝑙32 𝑙42
0 0 0 𝑙33 𝑙43
𝑙44 0 0 0 𝑙44
=
𝑎11
𝑎21
𝑎31
𝑎41
𝑎12
𝑎22
𝑎32
𝑎42
𝑎13
𝑎23
𝑎33
𝑎43
𝑎14
𝑎24
𝑎34
𝑎44
43
𝑎43 −
𝑙 =
𝑙41𝑙31 + 𝑙42𝑙32
𝑙33
𝑙𝑖𝑗 =
𝑘=1𝑎𝑖𝑗−∑
𝑗−1 𝑙𝑖𝑘𝑙𝑗𝑘
𝑙𝑗𝑗
𝑗 = 1,2, ⋯ , 𝑛 − 1 e 𝑖 = 𝑗 + 1, 𝑗 + 2, ⋯ ,𝑛
SOLUÇÃO DO SISTEMA LINEAR COM DECOMPOSIÇÃO DE CHOLESKY
 Forma do sistema linear
𝐿𝐿𝑇𝑥 = 𝑏
𝐿𝑇𝑥 = 𝑦
𝐿𝑦 = 𝑏
CÁLCULO DO DETERMINANTE
 Usando as propriedades de determinante
𝐴 = 𝐿𝐿𝑇
det 𝐴 = det 𝐿 det 𝐿𝑇
det 𝐴
𝑛 𝑛
= ∏ 𝑙𝑖 𝑖 ∏ 𝑙𝑖 𝑖 ∴ det
𝑖=1 𝑖=1
2𝑛
det(A) = ∏𝑙𝑖𝑖
𝑖=1
MÉTODOS ITERATIVOS ESTACIONÁRIOS
 Nestes métodos partimos de uma solução inicial 𝑥0 e construímos 
uma sequência 𝑥1, 𝑥2,⋯ , 𝑥𝑘 que deve convergir para a solução exata
𝑥∗ do sistema.
 Seja 𝑀 uma matriz de iteração e 𝒄 um vetor constante qualquer. 
Um método iterativo pode ser definido como
𝑥𝑘+1 = 𝑀𝑥𝑘 + 𝒄
 Um método definido desta forma é dito estacionário quando 𝑀 for 
fixa durante todo o processo de determinação da solução.
CONDIÇÃO DE CONVERGÊNCIA
 Teorema
 O método iterativo converge com qualquer valor inicial 𝑥0 se e somente 
se, 𝜌 𝑀 < 1, sendo 𝜌 𝑀 o raio espectral da matriz de iteração 𝑀.
 O cálculo do raio espectral pode ser mais caro que o cálculo da 
solução. Podemos então utilizar o critério das linhas para os 
métodos de Jacobi e Gauss-Seidel.
CONDIÇÃO SUFICIENTE DE CONVERGÊNCIA
𝑎𝑖 𝑖
 Teorema
 É condição suficiente para a convergência dos métodos iterativos de 
Jacobi e Gauss-Seidel que a matriz dos coeficientes 𝐴 seja diagonal
estritamente dominante, ou seja,
𝑛
>∑ 𝑎𝑖𝑗
𝑗=1
𝑗≠𝑖
, 𝑖 = 1,2, ⋯ ,𝑛
CRITÉRIO DE PARADA
 Com a sequência gerada pelo método iterativo, convergente, então
lim 𝑥𝑘 =𝑥∗
𝑘→∞
 Para 𝑘 > 0 a solução é obtida comexatidão crescente.
 Critérios de parada
𝑥𝑘 − 𝑥𝑘+1
𝑥𝑘
≤ 𝜀
𝑘 ≤ 𝑘𝑚𝑎𝑥
CRITÉRIO DE PARADA
 A norma adotada pode ser a infinita
1≤𝑖≤𝑛
𝑖max 𝑥
𝑘 − 𝑥𝑘−1
1≤𝑖≤𝑛
max 𝑥𝑘𝑖
𝑖
MÉTODO DE JACOBI
 Incialmente faremos seguinte decomposição da matriz 𝐴
𝐴 = 𝐷 + 𝐸 + 𝐹
𝑎11 𝑎12 ⋯ 𝑎1𝑛
𝑎21 𝑎22 ⋯ 𝑎2𝑛
⋮ ⋮ ⋱ ⋮
𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛
=
𝑎11 0 ⋯ 0
0 𝑎22 ⋯ 0
⋮ ⋮ ⋱ ⋮
0 0 ⋯ 𝑎𝑛𝑛
+
0 𝑎12 ⋯ 𝑎1𝑛
0 0 ⋯ 𝑎𝑛2
⋮ ⋮ ⋱ ⋮
0 0 ⋯ 0
+
0
𝑎12
⋮
𝑎𝑛1
0 ⋯ 0
0 ⋯ 0
⋮ ⋱ ⋮
𝑎𝑛2 ⋯ 0
APLICANDO AO SISTEMA
𝐴𝑥 = 𝑏
(𝐷 + 𝐸 + 𝐹)𝑥 = 𝑏
𝐷𝑥 + (𝐸 + 𝐹)𝑥 = 𝑏
𝐷𝑥 = 𝑏 −(𝐸 + 𝐹)𝑥
 Se existir a inversa de D então
𝑥𝑘+1 = −𝐷−1 𝐸 + 𝐹 𝑥𝑘 + 𝐷−1𝑏
 Ou seja
𝑥𝑘+1 = 𝐽𝑥𝑘 + 𝐶
MÉTODO DE JACOBI NA FORMA MATRICIAL
 Manuseando a equação anterior temos
1𝑥
𝑘+1
2𝑥
𝑘+1
𝑥𝑘+13
⋯
𝑛𝑥
𝑘+1
=
0 11 11 11
− 𝑎21/𝑎 22 0 −
𝑎23/𝑎 22 −
𝑎2𝑛/𝑎 22
− 𝑎31/𝑎 33 −
𝑎32/𝑎 33 −
𝑎3𝑛/𝑎 33
⋮
−𝑎𝑛1/𝑎 𝑛 𝑛
⋮
−𝑎𝑛2/𝑎 𝑛 𝑛
0
⋮
−𝑎𝑛3/𝑎 𝑛 𝑛
− 𝑎12/𝑎 −
𝑎13/
𝑎 ⋯ −
𝑎1𝑛/𝑎
⋯
⋯
⋱
⋯
⋮
0
1𝑥
𝑘
2𝑥
𝑘
𝑥𝑘3
⋯
𝑛𝑥
𝑘
+
𝑏1/𝑎 11
𝑏2/𝑎 22
𝑏3/𝑎
33
𝑏𝑛/
⋮
𝑎𝑛 𝑛
𝑥𝑘+1 𝐽 𝐶
MÉTODO DE JACOBI NA FORMA EQUAÇÕES
 Podemos também expressar o método na forma de equações
1𝑥
𝑘+1 =
1
𝑎11
−𝑎12𝑥𝑘 − 𝑎 𝑥𝑘 − ⋯ − 𝑎 𝑥𝑘 + 𝑏
2 13 3 1𝑛 𝑛 1
⋮
𝑛𝑥
𝑘+1 =
1
𝑎𝑛𝑛
−𝑎 𝑥𝑘 − 𝑎 𝑥𝑘 − ⋯ − 𝑎𝑛1 1 𝑛2 2 𝑛 ,𝑛−1 𝑛−1𝑥
𝑘 + 𝑏𝑛
 Iniciando fazendo 𝑥0 = 0
0
𝑖
1𝑥 = 𝑐 então 𝑥 =
𝑏
𝑎𝑖 𝑖
 Então
𝑥0 =
𝑏𝑖
𝑎𝑖 𝑖𝑖
𝑖 𝑖
𝑖
MÉTODO DE GAUSS-SEIDEL
 Partimos da mesma decomposição
𝐴 = 𝐷 + 𝐸 + 𝐹
 O sistema linear fica da seguinte forma
𝐷 + 𝐸 + 𝐹 𝑥 = 𝑏
𝐷 + 𝐸 𝑥 = −𝐹𝑥 + 𝑏
 A iteração é obtida pela fórmula de recorrência
𝑥𝑘+1 = −1 𝑥𝑘 +𝐷 + 𝐸 𝐷 + 𝐸 −1𝑏
𝑥𝑘+1 = 𝑆𝑥𝑘 + 𝐶
MÉTODO DE GAUSS-SEIDEL
 Na forma de equações
1𝑥
𝑘+1 =
1
−𝑎 𝑥𝑘 − 𝑎12 2 13 3𝑥
𝑘 − ⋯ − 𝑎1𝑛 𝑛𝑥
𝑘 + 𝑏1
2𝑥
𝑘+1 =
𝑎11 
1
−𝑎21 1𝑥
𝑘+1 − 𝑎23 3𝑥
𝑘 − ⋯ − 𝑎2𝑛 𝑛𝑥
𝑘 + 𝑏2
3𝑥
𝑘+1 =
𝑎22
1
𝑎33
−𝑎31 1𝑥
𝑘+1 − 𝑎32 2𝑥
𝑘+1 − ⋯ − 𝑎3𝑛 𝑛𝑥
𝑘 + 𝑏3
⋮
𝑛𝑥
𝑘+1 =
1
𝑎𝑛𝑛
−𝑎𝑛1 1𝑥
𝑘+1 − 𝑎𝑛2 2𝑥
𝑘+1 − ⋯ − 𝑎𝑛 ,𝑛−1 𝑛−1𝑥
𝑘+1 + 𝑏𝑛
MÉTODO DE GAUSS-SEIDEL
 Valor inicial
𝑥0 =
𝑏𝑖
𝑎𝑖 𝑖