Buscar

Anexo MA aula unidade2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

4
2
5
1
UNIVERSIDADE FEDERAL DE UBERLÂNDIA
FACULDADE DE MATEMÁTICA
 
Unidade II
SISTEMAS LINEARES
4
2
5
1
Introdução
4
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. 
Neste capítulo vamos analisar esquemas numéricos para soluções de sistemas lineares de n equações com n incógnitas, supondo que este tenha uma única solução:
4
2
5
1
		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 
onde aij são os coeficientes, xj são as incógnitas e os bj são os termos independentes.
4
2
5
1
Métodos Iterativos
4
2
5
1
 Métodos Iterativos
	Vamos considerar um sistema linear AX = b, onde: 
		
		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
onde:
 	C: matriz com dimensões n x n;
 
	d: vetor com dimensões n x 1;
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
k = 0, 1, 2, ...
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:
4
2
5
1
Além disso, as normas			 satisfazem as seguintes propriedades:
4
2
5
1
onde X é a solução do sistema linear.
O conceito de norma nos permite definir convergência de uma seqüência de vetores {Xk}. Dizemos que X(k)→X se
4
2
5
1
Com isto podemos definir os critérios de parada: Dado um e > 0 
4
2
5
1
Critério de convergência
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
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 
Quanto menor || C || mais rápido a convergência do processo.
4
2
5
1
Método iterativo de 
Gauss-Jacobi
4
2
5
1
	Seja o sistema linear:
4
2
5
1
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.
4
2
5
1
Observe que o processo iterativo utiliza somente estimativas da iteração anterior.
Assim, 
4
2
5
1
Método iterativo de 
Gauss-Seidel
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)
x3(k+1)= (b3 - a31 x1(k+1) - a32 x2 (k+1) – a34x4 (k) - ... - a3n 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.
4
2
5
1
r2
r1
4
2
5
1
Critério de Sassenfeld
4
2
5
1
Seja o sistema linear
e
para j = 2, 3, ..., n.
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
Métodos diretos
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;
multiplicar uma equação por uma constante;
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
Método de Eliminação
 de Gauss
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
Pivotamento Parcial
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
Inversão de matrizes
pelo método de Gauss
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 ARnxn, 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
Logo tem-se:
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).
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais