©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu...
-
Upload
miguel-marcial -
Category
Documents
-
view
227 -
download
1
Transcript of ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu...
![Page 1: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/1.jpg)
©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico
Cálculo Numérico – CN Prof. Lineu Mialaret
Aula 16: Sistemas de Equações Lineares (4)
Instituto Federal de Educação, Ciência e Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
Licenciatura em Matemática
10 Semestre de 2013
![Page 2: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/2.jpg)
©Prof. Lineu MialaretAula 16 - 2/34Cálculo Numérico
Seja o sistema linear Ax = b. Um processo de fatoração para a resolução do sistema
linear acima consiste em decompor a matriz A (matriz dos coeficientes) num produto de dois ou mais fatores, e resolver uma sequência de sistemas lineares que conduz à solução do sistema original.
Ou seja, Caso possa se fazer a fatoração A = CD, o sistema linear
Ax = b pode ser escrito como (CD)x = b.Se y = Dx, então resolver o sistema linear Ax= b é o
mesmo que resolver o sistema linear Cy = b e em seguida solucionar o sistema Dx = y.
Os processos de fatoração são vantajosos pois permitem resolver qualquer sistema linear que tenha a matriz A como matriz de coeficientes.
Fatoração LU (1)
![Page 3: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/3.jpg)
©Prof. Lineu MialaretAula 16 - 3/34Cálculo Numérico
A fatoração LU é um dos processos de fatoração mais empregados para se resolver sistemas lineares. Nessa fatoração, a matriz L é uma matriz triangular inferior
com diagonal unitária e a matriz U é uma matriz triangular superior.
Fatoração LU (2)
![Page 4: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/4.jpg)
©Prof. Lineu MialaretAula 16 - 4/34Cálculo Numérico
A obtenção dos fatores L e U por fórmulas dificulta o uso de estratégias de pivoteamento, e por esta razão, para se obter esses fatores será usado o processo de Gauss.
Para exemplificar, seja o seguinte sistema linear e a respectiva matriz A, apresentados a seguir,
Cálculo dos Fatores L e U (1)
![Page 5: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/5.jpg)
©Prof. Lineu MialaretAula 16 - 5/34Cálculo Numérico
Os multiplicadores da 1ª iteração do processo de Gauss são apresentados a seguir,
Para se eliminar x1 da linha i (i = 2,3,...), multiplica-se a linha 1 por mi1 e subtrai-se o resultado da linha i.
Cálculo dos Fatores L e U (2)
![Page 6: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/6.jpg)
©Prof. Lineu MialaretAula 16 - 6/34Cálculo Numérico
Os coeficientes aij(0) são alterados para aij
(1) , onde
Isso equivale a pré-multiplicar a matriz A(0) pela matriz M(0) onde M(0) é
Cálculo dos Fatores L e U (3)
![Page 7: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/7.jpg)
©Prof. Lineu MialaretAula 16 - 7/34Cálculo Numérico
Ou seja,
Cálculo dos Fatores L e U (4)
![Page 8: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/8.jpg)
©Prof. Lineu MialaretAula 16 - 8/34Cálculo Numérico
Portanto, M(0)A(0) = A(1) (que é a mesma matriz obtida no final da 1ª iteração do processo de Gauss).
Supondo que a22(1) não seja zero, o multiplicador m32 será
Para se eliminar x2 da linha 3, multiplica-se a linha 2 por m32 e subtrai-se o resultado da linha 3.
Os coeficientes aij(1) são alterados para
Cálculo dos Fatores L e U (5)
![Page 9: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/9.jpg)
©Prof. Lineu MialaretAula 16 - 9/34Cálculo Numérico
As operações efetuadas na matriz A(1) são equivalentes a pré-multiplicar A(1) por M(1), onde
Cálculo dos Fatores L e U (6)
![Page 10: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/10.jpg)
©Prof. Lineu MialaretAula 16 - 10/34Cálculo Numérico
Portanto, M(1)A(1) = A(2) (que é a mesma matriz obtida no final da 2ª iteração do processo de Gauss).
Tem-se então que
Cálculo dos Fatores L e U (7)
![Page 11: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/11.jpg)
©Prof. Lineu MialaretAula 16 - 11/34Cálculo Numérico
É fácil verificar que
Cálculo dos Fatores L e U (8)
![Page 12: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/12.jpg)
©Prof. Lineu MialaretAula 16 - 12/34Cálculo Numérico
Então,
Ou seja,
Cálculo dos Fatores L e U (9)
![Page 13: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/13.jpg)
©Prof. Lineu MialaretAula 16 - 13/34Cálculo Numérico
Sintetizando, Fatorou-se a matriz A em duas matrizes triangulares L e U,
sendo que o fator L é triangular superior com diagonal unitária e seus elementos lij para i > j são os multiplicadores mij obtidos no processo de Eliminação de Gauss; e
O fator U é triangular superior e é a matriz triangular obtida no final da fase de triangularização do Processo de Eliminação de Gauss.
Cálculo dos Fatores L e U (10)
L U
![Page 14: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/14.jpg)
©Prof. Lineu MialaretAula 16 - 14/34Cálculo Numérico
Teorema da Fatoração LU (1)
![Page 15: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/15.jpg)
©Prof. Lineu MialaretAula 16 - 15/34Cálculo Numérico
Teorema da Fatoração LU (2)
![Page 16: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/16.jpg)
©Prof. Lineu MialaretAula 16 - 16/34Cálculo Numérico
Exemplo 1: Resolver o sistema linear a seguir usando-se a Fatoração LU.
Usando-se o Processo de Gauss, para se triangularizar a Matriz A, tem-se na Etapa 1
Cálculo dos Fatores L e U (11)
![Page 17: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/17.jpg)
©Prof. Lineu MialaretAula 16 - 17/34Cálculo Numérico
Então tem a seguinte manipulação de linhas
A matriz A(1) é
Cálculo dos Fatores L e U (12)
![Page 18: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/18.jpg)
©Prof. Lineu MialaretAula 16 - 18/34Cálculo Numérico
Como a21(1) e a31
(1) são nulos, pode-se guardar os multiplicadores nessas posições
Cálculo dos Fatores L e U (13)
![Page 19: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/19.jpg)
©Prof. Lineu MialaretAula 16 - 19/34Cálculo Numérico
Na 2ª Etapa tem-se
Tem-se então
Cálculo dos Fatores L e U (14)
Multiplicadores nas posições aij = 0
![Page 20: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/20.jpg)
©Prof. Lineu MialaretAula 16 - 20/34Cálculo Numérico
Os fatores L e U são
Solucionando-se L(Ux) = b
Cálculo dos Fatores L e U (15)
Lembrar do Teorema da Fatoração LU
![Page 21: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/21.jpg)
©Prof. Lineu MialaretAula 16 - 21/34Cálculo Numérico
Solucionando-se L(Ux) = b
Cálculo dos Fatores L e U (16)
Lembrar do Teorema da Fatoração LU
![Page 22: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/22.jpg)
©Prof. Lineu MialaretAula 16 - 22/34Cálculo Numérico
Exercício 1: Resolver o sistema linear a seguir usando-se a Fatoração LU.
Cálculo dos Fatores L e U (11)
![Page 23: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/23.jpg)
©Prof. Lineu MialaretAula 16 - 23/34Cálculo Numérico
Exercício 1: Resolver o sistema linear a seguir usando-se a Fatoração LU.
Solução:
Cálculo dos Fatores L e U (12)
![Page 24: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/24.jpg)
©Prof. Lineu MialaretAula 16 - 24/34Cálculo Numérico
A estratégia de pivoteamento parcial na fatoração LU requer a permutação de linhas na matriz A(k), quando necessário.
Para isso, é necessárioDefinir o que é uma matriz de permutação;Como usar o pivoteamento parcial na fatoração LU; e Analisar quais os efeitos das permutações na solução dos
sistemas lineares Ly = b e Ux = y.
Fatoração LU com Pivoteamento Parcial (1)
![Page 25: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/25.jpg)
©Prof. Lineu MialaretAula 16 - 25/34Cálculo Numérico
Uma matriz quadrada de ordem n é denominada de Matriz de Permutação quando ela pode ser obtida a partir da Matriz Identidade de ordem n permutando-se suas linhas (ou colunas).
Fazendo-se a pré-multiplicação de uma matriz A por uma matriz de permutação P obtém-se a matriz PA com as linhas permutadas e esta permutação de linhas é a mesma efetuada na matriz identidade para se obter a matriz P.
Fatoração LU com Pivoteamento Parcial (2)
![Page 26: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/26.jpg)
©Prof. Lineu MialaretAula 16 - 26/34Cálculo Numérico
Exemplo 2:
Fatoração LU com Pivoteamento Parcial (3)
![Page 27: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/27.jpg)
©Prof. Lineu MialaretAula 16 - 27/34Cálculo Numérico
Fatoração LU com Pivoteamento Parcial (4)
![Page 28: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/28.jpg)
©Prof. Lineu MialaretAula 16 - 28/34Cálculo Numérico
Exemplo 3: Resolver o sistema linear a seguir usando-se a Fatoração LU com pivoteamento parcial.
Usando-se o Processo de Gauss, tem-se na Etapa 1
Ou seja, deve-se fazer a permutação das linhas 3 e 1
Fatoração LU com Pivoteamento Parcial (5)
![Page 29: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/29.jpg)
©Prof. Lineu MialaretAula 16 - 29/34Cálculo Numérico
Ou seja, deve-se fazer a permutação das linhas 3 e 1
Fazendo-se a eliminação na matriz A´(0) tem-se
Fatoração LU com Pivoteamento Parcial (6)
![Page 30: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/30.jpg)
©Prof. Lineu MialaretAula 16 - 30/34Cálculo Numérico
Na 2ª Etapa, tem-se,
Então deve-se fazer a permutação das linhas 2 e 3, obtendo-se
Fatoração LU com Pivoteamento Parcial (7)
![Page 31: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/31.jpg)
©Prof. Lineu MialaretAula 16 - 31/34Cálculo Numérico
Fazendo-se a eliminação tem-se,
Os fatores L e U são
Fatoração LU com Pivoteamento Parcial (8)
![Page 32: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/32.jpg)
©Prof. Lineu MialaretAula 16 - 32/34Cálculo Numérico
Fatoração LU com Pivoteamento Parcial (9)
![Page 33: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/33.jpg)
©Prof. Lineu MialaretAula 16 - 33/34Cálculo Numérico
Solução dos sistemas lineares,
Fatoração LU com Pivoteamento Parcial (10)
![Page 34: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/34.jpg)
©Prof. Lineu MialaretAula 16 - 34/34Cálculo Numérico
Solução dos sistemas lineares,
Fatoração LU com Pivoteamento Parcial (11)
![Page 35: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/35.jpg)
©Prof. Lineu MialaretAula 16 - 35/34Cálculo Numérico
Exercício 2: Resolver o sistema linear a seguir usando-se a Fatoração LU com pivoteamento parcial.
Fatoração LU com Pivoteamento Parcial (12)
![Page 36: ©Prof. Lineu MialaretAula 16 - 1/34Cálculo Numérico Cálculo Numérico – CN Prof. Lineu Mialaret Aula 16: Sistemas de Equações Lineares (4) Instituto Federal.](https://reader035.fdocumento.com/reader035/viewer/2022081513/570638421a28abb8238f1703/html5/thumbnails/36.jpg)
©Prof. Lineu MialaretAula 16 - 36/34Cálculo Numérico
Exercício 2: Resolver o sistema linear a seguir usando-se a Fatoração LU com pivoteamento parcial.
Solução:
Fatoração LU com Pivoteamento Parcial (13)