étodos uméricos - ufsj.edu.br · Pelo teorema e sabendo que uma matriz singular tem determinante nulo então: A OI v 0 det ... Soma dos elementos da diagonal principal é igual

Prof. Erivelton Geraldo Nepomuceno

2016

SISTEMAS DE EQUAÇÕES LINEARES

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

UNIVERSIDADE DE JOÃO DEL-REI

PRÓ-REITORIA DE PESQUISA

CENTRO FEDERAL DE EDUCAÇÃO

TECNOLÓGICA DE MINAS GERAIS

DIRETORIA DE PESQUISA E PÓS-GRADUAÇÃO

étodos

uméricos

Conteúdo

1. Conceitos fundamentais

2. Métodos diretos para resolução de SL: Métodos para resolução de SL triangulares Método de eliminação de Gauss Método de decomposição LU Decomposição de Cholesky Decomposição espectral

3. Inversão de matrizes através de métodos diretos

4. Métodos iterativos para resolução de SL Método iterativo de Jacobi–Richardson Método iterativo de Gauss – Seidel

5. Análise de erros na solução de SL

6. Cálculo de autovalores e autovetores 2

A solução de um sistema de equações lineares algébricas é um dosprocessos numéricos mais utilizados para simular situações reais. É umaetapa fundamental na solução de problemas que envolvem por exemplo:

Equações diferenciais parciais Otimização Regressão Sistemas não lineares Equações integrais

É muito importante a escolha e implementação de um método eficientepara solução do SL devido principalmente da dois fatores:

Esforço computacional requerido (tempo/memória) Precisão dos resultados

Introdução

Uma equação é linear se cada termo contém não mais do que uma variável e cada variável aparece na

primeira potência. 3

Conceitos Fundamentais

4

Conceitos Fundamentais

Matriz é um conjunto de elementos dispostos em formaretangular.

O tamanho de uma matriz é determinado pelo seu número de linhase colunas. Uma matriz com m linhas e n colunas é dita m x n.

Os elementos podem ser números, expressões ou outras matrizes.

Os elementos de uma matriz são delimitados por colchetes ouparênteses e são referenciados por dois índices, o primeiro indicaa linha e o segundo a coluna.

5

Conceitos FundamentaisFormas de Matrizes:Matrizes com determinados formatos e elementos frequentes:

1

21

11

ma

a

a

naaa 11211

000

000

000

mnd

d

d

d

000

000

000

000

33

22

11

1000

0100

0010

0001

Coluna A(mx1): Nula: A(mxn) aij=0, i, j

Diagonal: A(mxn) dij=0, ij Identidade: A(mxn) eij=1, i=j e eij=0, ij

Linha A(1xn):

6

Conceitos FundamentaisFormas de Matrizes:

018637

93111621

21704

126535

98041

12000

80130

09160

00030

08001

Densa: (5x5) Esparsa: (5x5) Simétrica dij= dji0, i,j A=AT

mnmm ddmdd

ddd

dd

d

3

0

00

000

21

333231

2221

11

mn

n

n

n

d

dd

ddd

dddd

000

00

0

333

22322

1131211

Triangular inferior: A(mxn) dij=0, i<j Triangular superior: A(mxn) dij=0, i>j

7624

6850

2591

4013

7

Conceitos FundamentaisOperações Matriciais:

Transposição:

68210

50492

17365

651

807

243

196

025

TAA

Adição/Subtração: (Matrizes devem ter as mesmas dimensões)

36

32

910

132

32

80

68

52BABABA

Uma matriz complexa é Hermitiana se ela é igual aos seu complexocinjugado transposto.

8


Multiplicação por escalar: (resulta em matriz de mesma dimensão)

3040

25105

68

52AA

Multiplicação por matriz: (o número de colunas de A(m1xp) deveser igual ao número de linhas de B(pxn2) sendo AxB=C(m1xn2):

2

1

1 ,...,2,1,...,2,1, njmibaCp

k

kjikij

4841

126

53

04

61

653

012ABBA

9


Produto interno e externo: multiplicação de vetores que resulta emum escalar ou uma matriz.

10


Determinante: Uma matriz quadrada de ordem n tem um númeroassociado chamado determinante:

2231322213

2331332112

2332332211

333231

232221

131211

12212211

2221

1211

1111

)det(

)det(

)det(

aaaaa

aaaaa

aaaaaA

aaa

aaa

aaa

A

aaaaAaa

aaA

aAaA

Se det(A) = 0 matriz é singular (não tem inversa).

11


Posto

02211 nnvvv

Um conjunto de vetores {v1, v2, ...,vn} é dito linearmente dependentese existirem escalares 1, 2, ..., n não todos nulos, tais que:

Os vetores v1, v2, ...,vn são linearmente independentes se a igualdade éverificada somente para todos os escalares 1, 2, ..., n nulos.

Posto de uma matriz A é o número máximo de vetores linha ou colunade A que são linearmente independentes.

Linhas 2 e 4 obtidas pela combinação linear das linhas 1 e 3: L2=L1+L3 L4=2L1-L3Posto(A)=2. 12


Traço: O traço de uma matriz quadrada é definido como a somados elementos da sua diagonal principal.

n

i

iiaA1

traço

13


Inversa: A inversa de uma matriz quadrada A de ordem n A-1 é:

Sendo In a matriz identidade de ordem n. Observa-se que a leicomutativa existe para o produto de uma matriz por sua inversa.

14


Algumas operações:

Se , então e

15

Conceitos FundamentaisAutovalores e Autovetores:

Seja a matriz:

Tal que:

▪ A Matriz A possui um autovalor = 2 e um correspondenteautovetor v = [1 2]T .

▪ Também e verdade para = 4 e v = [2 3]T .

▪ A matriz de ordem n possui n autovalores e n autovetores.

▪ Relação fundamental: vAv 16


O problema do autovalor é encontrar a solução não trivial (não nula) dosistema homogêneo:

▪ Teorema: Se M for uma matriz de ordem n, então o sistemahomogêneo My = 0 tem solução não trivial se, e somente se, Mfor singular.

▪ Pelo teorema e sabendo que uma matriz singular temdeterminante nulo então:

0 vIA

0det IA

17


Exemplo:

1 = 2 e 2 = 4

18


Polinômio Característico:

▪ O Polinômio Dn() de grau n é o polinômio característicos de A.▪ Os n zeros i são autovalores de A.▪ Expandindo o determinante para n = 3 tem-se:

19


Polinômio Característico:

Relações de Girard (relações entre raízes e coeficientes de umaequação algébrica):

20


Duas importantes propriedades são obtidas:

Soma dos elementos da diagonal principal é igual a soma dosautovalores:

Determinante de uma matriz é igual ao produto dos seusautovalores:

Isso mostra que uma matriz singular tem, no mínimo, umautovalor nulo. 21


Exemplo:

Uma matriz com elementos reais tem seu polinômiocaracterístico com coeficientes reais.

Uma matriz com elementos reais tem autovalores reais e/oucomplexos conjugados em pares.

22


Exemplo: Calcular os autovalores da matriz:

Polinômio característico:

Zeros do polinômio característico:O processo de calcular osautovalores por intermédioda determinação dos zerosdo polinômio característico,apesar de ser simples, éineficiente em termoscomputacionais. Existemoutros métodos maiseficientes.

23


Outras Propriedades dos Autovalores:

1. Considerando que det(A) = det(AT ), então os autovalores deA, representados por (A), são iguais a (AT ).

2. Se A for uma matriz triangular de ordem n:

det(A- I)=(a11- )(a22- ) ... (ann- ) = 0

Logo os autovalores de uma matriz triangular ou diagonal sãoiguais aos elementos da diagonal principal.

3. O posto de matriz quadrada e igual ao numero deautovalores não nulos.

24


Outras Propriedades dos Autovalores:

4. Se i são os autovalores de A, então i-1 são os autovalores

de A-1 por porque :

25

Conceitos FundamentaisNormas:

É o termo utilizado para expressar magnitude (número real nãonegativo) de um vetor ou de matriz. O conceito de norma éestreitamente ligado ao de comprimento do vetor.

As normas vetoriais são definidas em termos da norma-p. Assimpara um vetor x de tamanho n tem-se:

Norma-1 ou norma de soma de magnitudes

26


Norma-2 ou norma Euclidiana

Norma- ou norma de máxima magnitude

27


▪ Uma Norma vetorial é uma função que associaum numero real a cada vetor e que satisfaz as condições:

Condições das normas vetoriais:

28

e se, e somente se,

são vetores e é um escalar


Exemplo: Calcular as normas 1, 2 e do vetor:

29


Normas matriciais:

Norma-1 ou norma de soma máxima de coluna

Norma- ou norma de soma máxima de linha

Norma de Frobenius

30


Norma-2 ou norma espectral

▪ max é o maior autovalor de A em modulo▪ max e o maior valor singular de A, ou seja, raiz quadrada

do maior autovalor em modulo da matriz ATA).

31


Condições das normas matriciais:

32

e se, e somente se,

A e B são matrizes de mesma ordem e k e um escalar.


Exemplo: Calcular as normas 1, , F e 2 da matriz:

33

Conceitos FundamentaisSistemas de equações lineares:

Conjunto de m equações polinomiais com n variáveis xi de grau 1:

Forma matricial:

▪ Ou simplesmente Ax = b, onde A é a matriz dos coeficientes, x é ovetor solução e b é o vetor dos termos independentes.

▪ Se A for uma matriz quadrada (nxn) não singular:Ax = b A-1Ax = A-1b x = A-1b. 34


Classificação dos SL segundo a forma da matriz de coeficientes:

▪ Sistema sobredeterminado: tem-se mais equações do que incógnitas,ou seja, A(mxn) m n e posto(A)=n.

▪ Sistema subdeterminado: existem mais incógnitas do que equações,ou seja, m < n e posto(A) = m.

Sistema não tem solução ou existe um número infinito de soluçõesque satisfaça Ax=b.

▪ Situação mais comum é quando m = n, matriz de coeficientes équadrada. Resolver o sistema é encontrar as n incógnitas quesatisfaçam as n equações. 35


Classificação dos SL segundo o número de soluções:

▪ Única solução: det(A) 0. Geometricamente, a solução de umasistema linear de ordem n é um ponto no n comum aos nhiperplanos descritos por cada uma das n equações, ou seja, oponto que satisfaz simultaneamente às n equações. Por exemplo:

O número de soluções depende do determinante da matriz dos coeficientes.

Vetor solução x é a interseção dos três planos descritos por cada umadas três equações. X =[5 1 10]T e det(A) = 251 0.

36


37


▪ Infinitas soluções: det(A) = 0. No exemplo a seguir o sistema admiteinfinitas soluções uma para cada valor de .

Geometricamente no sistema com det(A) = 0, os três planos seinterceptam em uma linha reta:

38


39


▪ Sem solução: det(A) = 0.

Neste caso geometricamente no sistema com det(A) = 0, os trêsplanos nunca se interceptam simultaneamente, ou seja, o sistema nãoadmite solução:

40


41


Solução:

▪ Métodos diretos: solução obtida com número finito deoperações aritméticas. Exemplos de métodos diretos:

▪ Sistemas triangulares▪ Eliminação de Gauss▪ Decomposição LU▪ Decomposição de Cholesky

▪ Métodos iterativos: solução exata obtida somente com númeroinfinito de operações, é estabelecido um erro aceitável.

Existem duas grandes classes de métodos para resolução desistemas lineares:

42


Solução:

Os métodos diretos, em princípio, desprezando os erros dearredondamento, produzem uma solução, se houver, em um númerofinito de operações aritméticas. Um método iterativo, por outrolado, requerer, em geral, um número infinito de operaçõesaritméticas para produzir a solução exata. Assim, um métodoiterativo tem um erro de truncamento e o direto não tem. Poroutro lado, em sistemas de grande porte os erros dearredondamento de um método direto podem tornar a solução semsignificado, enquanto que nos métodos iterativos os erros dearredondamento não se acumulam. Entretanto, ambos são úteis,tem vantagens e limitações.

43


Sistemas equivalentes:

São sistemas de equações lineares que possuem o mesmo vetorsolução:

44

45

Métodos diretos para resolução de SL

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.

Sistemas TriangularesEm sistemas triangulares as soluções são facilmente obtidas.

Sistema triangular inferior:

▪ Solução obtida via substituições sucessivas:

46

Sistemas Triangulares

▪ Generalizando:

▪ Esquematicamente:

47


▪ Exemplo: Calcular a solução do sistema triangular inferior:

48

Sistemas Triangulares Sistema triangular superior:

▪ Solução obtida via substituições sucessivas:

49


▪ Continuando:

▪ Esquematicamente:

50


▪ Exemplo Calcular a solução do sistema triangular inferior:

Os elementos x são obtidos em ordem reversa.

51

1. Aderito Luis Martins Araujo , Analise Numerica Engenharias Mecânica e de Materiais.

2. Frederico Ferreira Campos Filho, Algoritmos Numéricos.

Referencias Bibliográficas

52

Documents

étodos uméricos - ufsj.edu.br · Pelo teorema e sabendo que uma matriz singular tem determinante nulo então: A OI v 0 det ... Soma dos elementos da diagonal principal é igual