Sistemas Lineares e Métodos de Solução

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

cap4:
gain(x) = |Ax| / |x| -> fator de ampliacao do operador f(x)=Ax na direcao de x
matriz singular: det(A)=0
matriz simetrica: A=Atransposta
-Normas:
norma maxima (infinita) = no caso de uma norma matricial
	linhas: a linha que tiver o maior somatório em módulo
	Colunas: a coluna que tiver o maior somatório em módulo
norma da soma = somatório do módulo dos elementos de um vetor ||x||1
norma euclidiana = raiz do somatório dos quadrados dos elementos de um vetor ||x||2
erros computacionais
-metodos diretos:
	quando utiliza numero de passos finitos
	cramer e gauss-cramer
	erro total= erro de entrada + erro de aritmetica = (x-arrex)+(arrex-arre'x)= Ea
-metodos iterativos:
	processos iterativos
	jacobi e gauss-siedel
	erro total= erro de entrada+erro de aritmetica +erro de disccretizacao
etapas da solucao de sistemas lineares:
1-Descomplexficação: transformação de uma sistemas complexo em um sistema real
2-estruturacao: escolha de algoritmo eficiente
3-calculo: calculo e estimativa de exatidao da mesma
-Método de eliminacao de Gauss:
mais conhecido e mais usado p pequeno porte(ate 30 variaveis), medio porte(ate 50 variaveis) e grande porte/denso(mais de 50 variaveis)
	fazer a triangularização e depois a retrosubstituição para achar os valores
produz solucao exata desde q A n seja singular e haja troca de linhas quando necessario
-gauss com Pivoteamento = Pegar o maior elemento absoluto de cada coluna antes a cada iteração
	Minimiza os erros de arredondamento
-Condicionamento de uma matriz:
resíduo = r = b - Ax
numero de condicionamento de uma matriz(k(A))
k(A)=||A||inf * ||A^-1||inf
quanto maior o k, mais sensivel eh o sistema
propriedades:
	-k(A)>= 1, POIS 1=||I||=||AA^-1||=<||A||*||A^-1||=K(A)
	-k(I)=1
	-para todo alfa E R, k(alfa*A)=K(A)
	-se D=diag(d1,d2,...,dn) entao k(D)= max{|dj|: j=1,...,n}/min{|dj|: j=1,...,n}
mal-condicionado: quando a aproximacao de menor residuo nao eh a melhor ou mais exata
	pequenas alteracoes de entrada, grandes erros na saida(teoria do caos)
fluxo:
	faz a troca de linhas para ter o maior elemento an posição A11 -> 1 iteração -> faz a troca de linhas com Ai1 = 0 de forma com que A22 tenha o maior elemento -> segunda iteração. e assim segue 
-Refinamento de Gauss:
seja Ax=b e xk a sequencia obtida por refinamentos, se:
	k(A)<1/(16u(n^3+3n^2) e os residuos rk sao calculados c precisao dupla, entao:
		xk converge p a solucao exata
passos:
1) achar raizes com gauss com pivoteamento
2) calcula Ax1
3)calcula o residuo r1=b-Ax1
4)calcula Az1=r1
5) calcula o proximo iterando (x2) assim: x2=x1+z1 onde z1 é a correção
Problema: achar z1
r1 = b - Ax1
Az1 = b - Ax1
Resolver o seguinte sistema:
Az1 = r1
analise de condicionamento atraves de refinamento
	mal-condicionado: residuos pequenos, mas correcoes grandes
	bem-condicionado: refinamentos nao devem ser feitos mais de duas vezes
-Equacionamento matricial:
U = PMPMPMP...A
L = as inversas do de cima vezes
lembrando que Pt = inv(P) e que inv(M) = -M (troca os sinais)
M1 eh a matriz identidade com elementos para zerar primeira coluna
M2 eh a matriz identidade com elementos para zerar segunda coluna(triangularizando)
M1M2A=U
-Decomposição LU
	Propriedades:
	- A matriz L é uma matriz triangular inferior onde sua diagonal principal sempre vale 1
	- A matriz U é uma matriz triangular superior.
	- P eh uma matriz de pivoteamento ou permutacao
	Ly=Pb
	Ux=y
Basicamente Usa-se P A = L U
LU sem permutacao(P=I)
A=LU
[a11 A12] [1 0][u11 U12]
[A21 A22] = [L21 L22][0 U22]
1)calcular a primeira linha de U: u11=a11 e U12=A12
2)calcular a primeira coluna de L: L21=A21/a11
3)calcular a decomposicao das submatrizes L22 E U22 atraves de A22-L21U12
LU com pivoteamento:
coloca-se vetor na frente e conforme a troca de linhas troca-se os numeros do vetor. faz L21 e U12
|1| * |2 0 2 0,6| |3|*|5 5 4 2|
|2| |3 3 4 -2| = |2| |3 0 1,6 -3,2| e assim por diante
|3| |5 5 4 2| |1| |2 -2 0,4 -0,2|
|4| |-1 -2 3,4 -1| |4| |-1 -1 4,2 -0,6|
-GAUSS-JORDAN:
etapas:
1)transformar Ax=b em Ux=bbarra
2)transformar Ux=bbarra em Dx=^b onde D eh matriz diagonal
usada para calcular inversa e achar raizes
-SVD: A=UEV^T
metodo poderoso p tratar matrizes singulares ou quase singulares.
n faz apenas diagnostico, mas tbm encontra soluçao util.
condicionamento:
k(A) = maior elemento da diagonal principal de E/menor elemento da diagonal principal de E
A eh singular se k(A) = inf
A eh mal condicionada se k(A) eh numero muito grande
espaco gerado(range(A)):
as colunas de U q tem como correspondente colunas n nulas em E formam base ortonormal do range(A)
espaco nulo(null(A)):
colunas de V q tem como correspondente colunas nulas em E formam uma base ortonormal do null(A)
metodos iterativos:
JACOBI:
atualiza os valores na proxima iteracao
xn^k+1 = 1/lambidan(bn + coeficientes e variaveis restantes)
ex: 5x1-3x4-x5 = 2	x1k+1=1/5*(2+3x4k+x5k)
 -x1+4x2-x5 = 3	x2k+1=1/4*(3+x1k+x5k)
GAUSS-SIEDEL:
atualiza valores a cada passo na mesma iteracao
xn^k+1 = 1/lambidan(bn + valores calculados anteriormente)
algoritmos preparadores:
tranformar Ax=b em x=Bx+d p obter processo iterativo convergente -> xk+1=Bxk+d
tipo: preparador classico e preparador unitario
Convergencia:
metodo das linhas: se o modulo do elemento diagonal principal for maior q a soma dos modulos dos elementos da linha
norma de B < 1 : achamos a matriz, jacobi converge
usos: achar polinomio p(t)=x1+x2t+x3t^2+...+xnt^n-1 q passe pelos pontos