Fatoração LU e PLU

Embed Size (px)

Citation preview

Sistemas de Equaoes Lineares c

Sistemas de Equaes Lineares coDecomposio LU: Algoritmos e Aplicaes ca co Eduardo CamponogaraDepartamento de Automao e Sistemas ca Universidade Federal de Santa Catarina

DAS-5103: Clculo Numrico para Controle e Automao a e ca

Sistemas de Equaoes Lineares c Sumrio a

Introduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Introduo ca

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Introduo ca

Decomposio LU caDado um sistema de equaes lineares, com A no-singular: co a Ax =b A decomposio LU busca encontrar trs matrizes n n de ca e maneira que P A=LU onde:

(1)

(2)

P uma matriz de pivoteamento (tambm indicada na e e literatura como matriz de permutao); ca L uma matriz diagonal inferior (Lower); e e U uma matriz diagonal superior (Upper). e

Sistemas de Equaoes Lineares c Introduo ca

Decomposio LU caEste mtodo busca transformar o problema em dois problemas e fceis de serem resolvidos, que a resoluo de sistemas lineares a e ca com matrizes triangulares.

Questo a

Qual a vantagem de quebrarmos A em duas matrizes e triangulares? A vantagem que a soluo de sistemas triangulares trivial e ca e (retrossubstituio). ca

Sistemas de Equaoes Lineares c Introduo ca

Decomposio LU caMtodo de Resoluo e ca

De posse das matrizes PLU, o mtodo de resoluo : e ca e Ax P1

= b = b (3)

LU x

Denimos y = Ux e pr-multiplicamos a equao (3) por P, e ca obtendo: P P 1 L y Ly = P b = P b (4)

Sistemas de Equaoes Lineares c Introduo ca

Decomposio LU ca

Mtodo de Resoluo: Continuao e ca ca

O sistema na equao (4) pode ser resolvido por substituio ca ca direta, o que nos leva a encontrar y . Assim, possu mos elementos para resolver: U x =y por retrosubstituio. ca (5)

Sistemas de Equaoes Lineares c Substituio Direta ca

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Substituio Direta ca

Substituio Direta caAdmita o sistema de equaes lineares: co Ly =b onde L uma matriz diagonal inferior. Usaremos um exemplo com e L R33 para exemplicar o processo, onde: y1 b1 l11 0 0 l21 l22 0 y2 = b2 y3 b3 l31 l32 l33

Sistemas de Equaoes Lineares c Substituio Direta ca

Substituio Direta caPodemos observar que y1 = b1 l11

e obtemos seu valor de imediato. No passo seguinte temos que l21 y1 + l22 y2 = b2 1 y2 = (b2 l21 y1 ) l22 mas y1 j conhecido, ento pode-se obter o valor de y2 . Desta ae a maneira, y3 e eventuais yn podem ser calculados sucessivamente.

Sistemas de Equaoes Lineares c Retrosubstituio ca

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Retrosubstituio ca

Retrossubstituio caAdmita agora o sistema de equaes lineares: co U x =y onde U uma matriz diagonal superior. e exemplo com U R33 para apresentar x1 u11 u12 u13 0 u22 u23 x2 0 0 u33 x3 Utilizamos novamente um o processo, onde: y1 = y2 y3

Sistemas de Equaoes Lineares c Retrosubstituio ca

Retrossubstituio caDa mesma maneira que na seo anterior, mas iniciando a partir ca da ultima linha de U, temos que: x3 = x2 y3 u33 1 = (y2 u23 x3 ) u22 . . .

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Obtendo LU sem Permutaes co

Primeiro consideraremos o problema da obteno da fatorao ca ca sem a matriz de permutaes. Este caso especial obtido co e fazendo P = I (identidade) no caso geral. Admita a seguinte diviso das matrizes A = L U: a a11 A12 A21 A22 = 1 0 L21 L22 u11 U12 0 U22

onde

A21 e L21 R(n1)1 so matrizes colunas; a A12 e U12 R1(n1) so matrizes linhas; a A22 , L22 , U22 R(n1)(n1) agrupam o restante das matrizes originais.

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Obtendo LU sem Permutaes co

Do produto obtemos: a11 A12 A21 A22 = u11 U12 u11 L21 L21 U12 + L22 U22

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Obtendo LU sem Permutaes coAssim podemos obter a primeira linha de U e a primeira coluna de L, fazendo: u11 = a11 U12 = A12 1 L21 = A21 u11 e ainda obtemos: L22 U22 = A22 L21 U12 = A22 1 A21 A12 a11

que nos permite calcular L22 e U22 fatorando A22 L21 U12 .

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Obtendo LU sem Permutaes co

Assim, chegamos ao seguinte algoritmo recursivo: 1) calcular a primeira linha de U: u11 = a11 e U12 = A12 ; 2) calcular a primeira coluna de L: L21 = ( a1 )A21 ; 11 3) calcular a decomposio das sub-matrizes L22 e U22 : ca L22 U22 = A22 L21 U12 .

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Obtendo LU sem Permutaes coEste algoritmo ca da seguinte maneira em pseudo-cdigo: o

AlgoritmoLU-Solve(A) 1 n rows[A] 2 for k 1 to n 3 ukk akk 4 for i k + 1 to n 5 lik aik /ukk 6 uki aki 7 for i k + 1 to n 8 for j k + 1 to n 9 aij aij lik ukj 10 return L and U

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Exemplo

Calcular a fatorao LU de ca 2 3 1 A = 6 13 5 2 19 10

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Exemplo: Continuao caIt k = 1: 2 3 1 1 0 0 2 3 1 6 4 2 = 3 1 0 0 2 16 9 1 1 0 0 It k = 2: 1 0 0 2 3 1 2 3 1 6 4 2 = 3 1 0 0 4 2 1 4 1 0 0 2 16 1 It k = 3: 2 3 1 1 0 0 2 3 1 6 4 2 = 3 1 0 0 4 2 2 16 1 1 4 1 0 0 1

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Discusso do Algoritmo a

Discusso do Algoritmo a

Podemos observar que o algoritmo modica a matriz A e que os valores contidos nas linhas e colunas k s so utilizados em o a sua iterao, assim poss que as matrizes L e U sejam ca e vel montadas na prpria matriz A. o

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Problemas do No-Pivoteamento a

Um exemplo simples mostra que nem todas as matrizes no-singulares podem ser fatoradas por A = LU: a A= 0 1 1 1

Se aplicarmos o algoritmo, teremos u11 = 0. Para calcularmos L21 = u1 A21 , teremos uma diviso por zero. Assim, a 11 elementos nulos na posio do piv devem ser evitados ca o utilizando, por exemplo, uma troca de linhas.

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

Problemas do No-Pivoteamento a

Observao caDe fato, a troca de linhas bastante comum, procurando que o e piv assuma o elemento de maior norma da coluna restante. Esta o heur stica se mostra bastante eciente para manter a estabilidade numrica do algoritmo, salvo em casos raros. e

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

O Vetor de Pivoteamento

No algoritmo que ser apresentado a seguir, utilizado um a e vetor ao invs da matriz para representar a permutao e ca entre linhas. Estas notaes so equivalentes. co a No vetor, o elemento [i] indica qual a linha da matriz I que e deve estar no local de i.

Sistemas de Equaoes Lineares c Obtendo LU sem Permutaoes c

O Vetor de Pivoteamento

ExemploO vetor = (2, 4, 1, 3) equivalente ` e a 0 1 0 0 0 0 P= 1 0 0 0 0 1 matriz 0 1 0 0

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Decomposio LU com Pivoteamento ca

A demonstrao formal do algoritmo com pivoteamento um ca e pouco mais complicada que do primeiro, e no ser coberta a a neste material. Foi demonstrado que esta decomposio existe sempre se a ca matriz A for no-singular. a Nesta implementao a decomposio ser executada na ca ca a prpria matriz A, obtendo a representao apresentada acima. o ca As permutaes sero representadas pelo vetor . co a

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Decomposio LU com Pivoteamento caAlgoritmoLUP-Solve(A) 1 n rows[A] 2 for i 1 to n 3 [i] i 4 for k 1 to n 5 p0 6 for i k to n 7 if |aik | > p 8 p |aik | 9 k i

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Decomposio LU com Pivoteamento caAlgoritmo

10 11 12 13 14 15 16 17 18 19

if p = 0 error matriz singular exchange [k] [k ] for i 1 to n exchange aki ak i for i k + 1 to n aik aik /akk for j k + 1 to n aij aij aik akj return A and

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Exemplo

ExemploCalcular a fatorao LUP da matriz ca 2 0 3 3 A= 5 5 1 2 2 0, 6 4 2 4 2 3, 4 1

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Exemplo: Continuao caIterao k=1 ca 1 2 2 3 3 (5) 1 4 (5) 3 2 0, 6 1 0, 4 4 0, 2 0 2 3 4 5 4 2 3, 4 5 4 0 1, 6 2 0, 4 1 4, 2 0, 6 2 2 1 2 3, 2 0, 2 0, 6 3 (5) 5 2 3 3 1 2 0 1 2 4 4 4 2 3, 4 2 2 0, 6 1

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Exemplo: Continuao caIterao k = 2 ca 5 3 2 0, 6 1 0, 4 4 0, 2 5 3 1 0, 4 2 0, 6 0, 2 4 5 0 (2) 1 5 (2) 0 0, 5 4 1, 6 0, 4 4, 2 4 0, 4 1, 6 4 2 3, 2 0, 2 0, 6 2 0, 2 3, 2 0, 5 5 3 1 0, 4 2 0, 6 4 0, 2 5 (2) 0 1 4 0, 4 1, 6 4, 2 2 0, 2 3, 2 0, 6

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Exemplo: Continuao caIterao k = 3 ca 3 5 1 0, 4 2 0, 6 0, 2 4 5 3 1 0, 4 4 0, 2 2 0, 6 5 2 0 0, 5 5 2 0, 5 0 4 0, 4 1, 6 (4) 4 0, 4 (4) 0, 4 2 0, 2 3, 2 0, 5 2 0, 2 0, 5 3 3 5 1 0, 4 4 0, 2 0, 6 2 5 2 0, 5 0 4 0, 4 (4) 1, 6 2 0, 2 0, 5 3, 2

Sistemas de Equaoes Lineares c Decomposio LU com Pivoteamento ca

Exemplo: Continuao caAssim 0 1 0 0 1 0, 4 0, 2 0, 6 0 0 0 1 0 1 0, 5 0 1 0 0 0 0 2 0 3 1 5 1 0 = 0 0 0 0 1 0 0, 4 1 0 3 5 2 5 0 0 0 2 4 4 3, 4 0, 6 2 2 1 2 0, 2 0, 5 3

5 4 2 0, 4 0 4 0 0

Sistemas de Equaoes Lineares c Mtodo de Crout e

Sumrio aIntroduo ca Substituio Direta ca Retrosubstituio ca Obtendo LU sem Permutaes co Decomposio LU com Pivoteamento ca Mtodo de Crout e

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout eAqui apresentamos um algoritmo alternativo para encontrar a decomposio LU sem pivoteamento. Podemos obter LU ca resolvendo um sistema de equaes no lineares conforme segue: co a L 0 0 0 11 21 22 0 0 31 32 33 0 41 42 43 44 = U 11 0 0 0 a11 a21 a31 a41 12 22 0 0 a12 a22 a32 a42 13 23 33 0 a13 a23 a33 a43 14 24 34 44 a14 a24 a34 a44 = A

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout e

Isto signica que: aij = i1 1j + i2 2j + . . . + in nj

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout eAlguns exemplos de equaes: co a13 = 11 13 + 12 23 + 13 33 + 14 43 = 11 13 a32 = 31 12 + 32 22 + 33 32 + 34 42 = 31 12 + 32 22 a22 = 21 12 + 22 22 + 23 32 + 24 42 = 21 12 + 22 12

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout e

H trs casos: a e 1) i < j : 2) i = j : 3) i > j : aij = i1 1j + i2 2j + . . . + ii ij aij = i1 1j + i2 2j + . . . + ii ij aij = i1 1j + i2 2j + . . . + ij jj (6) (7) (8)

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout e

O sistema de equaes (6), (7), e (8) possui n2 equaes e co co n2 + n variveis (a diagonal representada duas vezes). a e Uma vez que o nmero de variveis maior que o nmero de u a e u incgnitas, podemos especicar n das incgnitas o o arbitrariamente. Ento fazemos, a ii = 1, i = 1, . . . , n (9)

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout e

Algoritmo de CroutO algoritmo de Crout, que ser apresentado a seguir, resolve o a 2 + N equaes (6), (7), (8), e (9) atravs de uma sistema de N co e simples reordenao das equaes. ca co

Sistemas de Equaoes Lineares c Mtodo de Crout e

Mtodo de Crout eAlgoritmo de Crout 1) Dena ii = 1, i = 1, . . . , n 2) Para cada j = 1, . . . , n Para i = 1, . . . , j Use as equaes (6), (7), e (9) co para encontrar ij , precisamentei1

ij = aij k=1

ik kj

Para i = j + 1, j + 2, . . . , n Use a equao (8) para resolver ij ca ij =1 jj (aij j1

k=1

ik kj )

Sistemas de Equaoes Lineares c Mtodo de Crout e

Exemplo

Aqui vamos aplicar o Algoritmo de Crout para encontrar a decomposio LU da matriz: ca 10 7 0 2 6 A = 3 5 1 5

Sistemas de Equaoes Lineares c Mtodo de Crout e

Exemplo: Continuao caPassos executados pelo algoritmo: 1) 11 = a11 2) 21 = 3) 31 =1 11 (a21 1 11 (a31 11 k=1 ik kj 11

= a11 = 10

k=1 11

ik kj ) = 0.3 ik kj ) = 0.5k=1

11

4) 12 = a12 k=1

ik kj = a12 = 7

Sistemas de Equaoes Lineares c Mtodo de Crout e

Exemplo: Continuao ca5) 22 = a22 2 2.1 = 0.1 6) 32 =1 22 (a32 21 k=1 ik kj 21

= a22 21 12 = 2 (0.3)(7) =

k=1

3k k2 ) = 25 ik kj = a13 = 0

11

7) 13 = a13 k=1 21

8) 23 = a23 k=1 31

2k k3 = a23 31 13 = 6 (0.3)(0) = 6 3k k3 = a33 31 13 32 23 =k=1

9) 33 = a33

5 (0.5)(0) (25)6 = 155

Sistemas de Equaoes Lineares c Mtodo de Crout e

Exemplo: Continuao ca

Portanto, 1 0 0 1 0 L = 0.3 0.5 25 1 10 7 0 6 U = 0 0.1 0 0 155

Sistemas de Equaoes Lineares c Mtodo de Crout e

Exemplo: Continuao ca

o que nos permite vericar que: 10 7 0 1 0 0 10 7 0 2 6 1 0 0 0.1 6 = 3 LU = 0.3 5 1 5 0.5 25 1 0 0 155

Sistemas de Equaoes Lineares c Mtodo de Crout e

Comentrios Finais a

Fim! Obrigado pela presena c