50
4 2 5 1 0011 0010 UNIVERSIDADE FEDERAL DE UBERLÂNDIA FACULDADE DE MATEMÁTICA Unidade II SISTEMAS LINEARES

Unidade II - Sistemas Lineares

Embed Size (px)

DESCRIPTION

Para quem esta precisando de uma ajuda em calculo numérico, aqui você encontra na apostila mais completa de professores de universidades federais.

Citation preview

Slide 14
2
5
1
A resolução de sistemas lineares pode surgir em diversas áreas do conhecimento.
O caso geral, em que o sistema linear envolve m equações com n incógnitas, o sistema pode apresentar uma única solução, infinitas soluções ou não admitir solução.
*
Os métodos de resolução de equações lineares são classificados em:
Métodos Diretos - fornecem a solução exata de um sistema linear, a menos dos erros de máquina, através da realização de um número finito de operações.
Métodos Iterativos – fornecem uma seqüência de aproximações para a solução X a partir de uma solução inicial X(0).
O sistema é representado por A x = b
*
A: matriz de coeficientes, n x n;
X =(x1, x2, ..., xn)t: vetor de variáveis, n x 1
b: vetor independente, n x 1 (constantes)
Tal sistema linear pode ser escrito na forma equivalente:
X = CX + d
*
4
2
5
1
Partindo de um vetor X(0) (vetor aproximação inicial), constrói-se uma seqüência iterativa de vetores:
Primeira aproximação
De um modo geral, a aproximação X(k+1) é dada por:
Segunda aproximação
OBSERVAÇÃO: k é chamado de índice de iteração.
Sendo um processo iterativo, necessitamos de um critério de parada. E para isto temos que ter uma medida entre as aproximações X(k+1) e X(k). Para isto vamos usar o conceito de norma de matrizes.
X(1) = CX(0) + d
X(2) = CX(1) + d
4
2
5
1
Definição:
Uma norma em é uma aplicação que satisfaz as seguintes propriedades:
As normas matriciais mais usadas são:
*
Além disso, as normas satisfazem as seguintes propriedades:
*
onde X é a solução do sistema linear.
*
4
2
5
1
*
4
2
5
1
Seja . uma norma qualquer de matriz. Se C<1 o processo iterativo X(k+1)=CX(k)+d fornecerá uma seqüência {X(k)} convergente para a solução do sistema AX = b.
Critério de convergência
Sendo o erro em cada iteração dado por e(k) =X(k) – X e usando as propriedades de norma segue que:
Demonstração:
Seja X solução do sistema. Então: X = CX + d.
*
4
2
5
1
Logo a seqüência {X(k)} converge para a solução do sistema X se
e isto ocorre se a matriz C satisfaz a
condição
4
2
5
1
Seja o sistema linear:
*
Desta forma, tem-se o sistema equivalente X = CX + d, onde
e
Dada uma aproximação inicial: X(0)
o Método de G.Jacobi consiste em obter seqüência: X(1), X(2),..., X(k)
através da relação recursiva: X(k+1)=CX(k)+d.
*
Observe que o processo iterativo utiliza somente estimativas da iteração anterior.
Assim,
4
2
5
1
Observando as equações de iteração no método de Jacobi ou seja
nota-se que na iteração de ordem (k+1) são usadas as componentes xj(k) da iteração anterior.
4
2
5
1
No Método de Gauss-Seidel para calcular a componente xj da iteração (k+1), utiliza-se as componentes já atualizadas x1(k+1), x2(k+1), ..., xj-1(k+1) e as componentes ainda não atualizadas da iteração anterior xj+1(k), xj+2(k), ..., xn(k).
x1(k+1)= (b1 - a12 x2 (k) - a13 x3 (k) - a13 x3 (k) - ... - a1n xn (k)
x2(k+1)= (b2 - a21 x1 (k+1) - a23 x3 (k) – a24 x4 (k) - ... - a2n xn (k)
.
.
.
xn(k+1)= (bn - an1 x1(k+1) - an2 x2 (k+1) – an3x4 (k+1) - ... - ann-1 xn-1 (k+1)
4
2
5
1
Interpretação Geométrica do Método de Gauss-Seidel
Considere o sistema linear 2x2 dado pelas equações abaixo e geometricamente representados pela retas r1 e r2.
r2
r1
y
x
Temos:
4
2
5
1
Inicie no ponto (x10, x20) = (0,0).
Para determinar (x11, x20), substitua na reta r1 o valor x20, ou seja mova ao longo da reta horizontal iniciando no ponto (0, 0) até encontrar a reta r2.
O próximo ponto (x11, x21), é determinado movendo-se ao longo de uma reta vertical iniciando no ponto (x11, x20) até encontrar a reta r1.
Continuando desde modo, aproxima-se sucessivamente da solução do sistema, no caso da seqüência ser convergente.
y
x
r2
r1
4
2
5
1
r2
r1
y
x
4
2
5
1
definindo:
4
2
5
1
Define-se
Se β<1, então o Método de Gauss-Seidel gera uma seqüência convergente para a solução do sistema, qualquer que seja o vetor inicial. Além disso, quanto menor for o valor de β mais rápida é a convergência.
4
2
5
1
4
2
5
1
Os Métodos Diretos são aqueles que após um número finito de operações fornecem a solução exata do sistema, a menos dos erros de arredondamentos.
Definição:
Dois sistemas lineares são equivalentes se estes tem a mesma solução.
Podemos obter um sistema equivalente ao dado, efetuando as seguintes operações elementares:
Trocar duas equações;
somar uma equação a outra multiplicada por uma constante;
4
2
5
1
Sistema Triangular Superior
Denomina-se sistema triangular superior a todo sistema Ax =b em que aij = 0, para j < i.
4
2
5
1
4
2
5
1
O Método de Eliminação de Gauss consiste em transformar um sistema linear Ax= b em um sistema triangular superior equivalente.
Considere o sistema linear:
onde det(A) ≠ 0, isto é, o sistema admite uma única solução.
4
2
5
1
O sistema linear pode ser representado na forma de matriz estendida [A0 | b0 ], ou seja:
onde o índice superior indica a etapa do processo.
Etapa 1
Eliminar a incógnita x1 das equações k = 2, 3, ..., n. Sendo a11(0) ≠0, subtraímos da linha k a primeira linha multiplicada por:
4
2
5
1
Os elementos mk1 são chamados de multiplicadores e o elemento a11(0) é chamado de pivô da Etapa 1. Indicando a linha k da matriz por Lk(0), esta etapa se resume em:
Ao final desta etapa tem-se:
que representa um sistema linear equivalente ao sistema original, onde a incógnita x1 foi eliminada das equações k = 2, 3,..., n.
4
2
5
1
Etapa 2
Eliminar a incógnita x2 das equações k = 3, 4, ..., n. Supondo que a22(1) ≠ 0,vamos tomar este elemento como pivô desta etapa e desta forma os multiplicadores são dados por
A eliminação segue com as seguintes operações sobre as linhas:
4
2
5
1
obtendo ao final da etapa a matriz
Com procedimentos análogos ao das etapas 1 e 2 elimina-se as incógnitas xk das equações k + 1, k + 2, ..., n e ao final de n -1 etapas tem-se a matriz:
4
2
5
1
Esta matriz representa um sistema triangular superior equivalente ao sistema original. Logo a solução deste sistema, obtido pela Retro-Solução (substituição regressiva), é solução do sistema original.
4
2
5
1
Assim,
4
2
5
1
4
2
5
1
Em cada etapa k da eliminação temos o cálculo do multiplicador
Se o pivô |akk(k-1)| << 1, ou seja, próximo de zero, os erros de arredondamento se tornam significativos, pois operar números de grandezas muito diferentes aumenta os erros.
A estratégia de pivotamento parcial é baseada na operação elementar: Trocar duas equações.
No início de cada etapa k escolhemos como pivô o elemento de maior módulo entre os coeficientes akk(k-1) para i = k, k + 1, ..., n.
4
2
5
1
Exemplo
Etapa 1: Escolha do pivô
Com o objetivo de tornar os multiplicadores mk1< 1, trocamos a linha L1 com a linha L3, obtendo,
4
2
5
1
e com isto obtemos a matriz
4
2
5
1
Etapa 2: Escolha do pivô
Neste caso trocamos a linha L2 com a linha L3, obtendo,
Eliminar x2 da linha 3.
4
2
5
1
Retro-Solução: Encontrar a solução do sistema triangular superior.
Logo a solução do sistema é dada por x = (1, 0, 1)T .
4
2
5
1
4
2
5
1
Vamos supor que desejamos resolver os sistemas lineares Ax = b1, Ax = b2, Ax = bk, onde a matriz A é a mesma para todos os sistemas. A matriz triangular superior, resultante do processo de eliminação, não depende do vetor b e portanto será a mesma em qualquer um dos sistemas.
Assim podemos resolver estes sistemas num único processo de eliminação usando a matriz estendida (A |b1|b2|...| bk) e aplicando a Retro-Solução para cada vetor bk.
4
2
5
1
O Cálculo da inversa de uma matriz é um caso particular do esquema acima. A inversa de uma matriz ARnxn, denotada por A-1, é uma matriz nxn tal que
AA-1 = I
Como exemplo vamos considerar uma matriz A de dimensão 3 3
cuja a inversa A-1 é dada por
4
2
5
1
4
2
5
1
Portanto cada coluna k da inversa da matriz A é solução de um sistema linear, onde o vetor dos termos independentes é a k-ésima coluna da matriz identidade, isto é
4
2
5
1
Portanto, se temos uma matriz nxn, podemos achar a inversa resolvendo n sistemas lineares, representados pela matriz estendida (A | b1| b2 | ... | bk) , onde os vetores bk são os vetores unitários ( 1 na posição k e zeros nas demais posições).
ï
ï
î
ï
ï
í
ì