Notas de Aulas de Algebra Linear Aplicada - Prof Robson Pires

ELE204 Algebra Linear Aplicada Notas de Aulas V25 Prof Robson Pires DSc rpiresunifeiedubr robsoncpiresgmailcom Universidade Federal de Itajuba UNIFEI Instituto de Sistemas Eletricos e Energia ISEE Av BPS No 1303 Bairro Pinherinho Itajuba MG CEP 37500903 BR Copyright 2023 Prof Robson Pires DSc 9 de agosto de 2023 2 Sistemas de Equações Algébricas Lineares O problema mais comumente resolvido em matemática aplicada representa a solução de um sistema de m equações lineares consistentes a n incógnitas isto é A x b 1 onde A matriz de coeficientes x vetor de incógnitas variáveis dependentes b vetor do lado direito variáveis independentes Ex Ref 200 AC China Nine Chapters in Arithmetics Três fardos de grãos de uma boa colheita dois fardos de uma colheita considerada medíocre e um fardo de uma colheita ruim são vendidos por 39 unidades monetárias UM Dois outros fardos de grãos classificados como bons três médios e um ruim são vendidos por 34 UM Adicionalmente um bom dois médios e três ruins são vendidos por 26 UM Qual o valor recebido por cada um dos tipos de grãos negociados Solução Nos dias atuais o problema acima seria equacionado da seguinte maneira 3x 2y z 39 2x 3y z 34 x 2y 3z 26 2 The measure of greatness in a scientific idea is the extent to which it stimulates thought and opens up new lines of research Paul AM Dirac Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI ii Conteudo Pagina 1 Introducao 3 11 Consideracoes Iniciais 3 12 Estrutura do Documento 3 2 Sistemas de Equacoes Algebricas Lineares 4 21 Eliminacao de Gauss e Matrizes 4 22 Metodo de GaussJordan 6 23 Sistemas Numericamente MalCondicionados 8 24 Numeros em Ponto Flutuante 8 3 Sistemas de Equacoes Algebricas Redundantes 10 31 Metodo da Equacao Normal 11 32 Propriedades de Algebra Matricial 12 321 Adicao Subtracao de Matrizes 12 322 Matrizes Transpostas 12 323 Multiplicacao de Matrizes 13 324 Matriz Identidade 13 325 Inversao de Matrizes 14 4 Fatoracao de Matrizes 15 41 Matrizes Quadradas Fatoracao LU 15 411 Reducao de Crout A LU 15 412 Reducao de Doolittle A LDU LDU LU 15 413 Reducao de Cholesky A LD12D12U LL t 16 414 Exemplo de Aplicacao 16 42 Matrizes Retangulares Fatoracao QR 19 421 NormaP 19 422 Ortogonalidade 19 423 Medida de ˆangulo entre Vetores em ℜn ou Cn 20 424 Medida de distˆancia entre Vetores em ℜn ou Cn 20 425 Base Ortonormal 20 426 Matrizes Ortogonais 20 427 Reflexoes de Householder 21 1 428 Rotacoes de Givens 24 43 Solucao do Problema Axb via Fatoracao QR 27 44 Quadro Comparativo de Esforco Computacional 28 5 Metodo de Mınimos Quadrados Ponderados MQP 29 51 Formulacao Matematica 29 52 Exemplo de Aplicacao 30 6 Esquemas de Ordenacao 33 61 Consideracoes Iniciais 33 62 Modelos de Ordenacao 33 621 Ordenacao Durante a Fatoracao 33 622 Ordenacao com Eliminacao Perfeita 33 623 Ordenacao Separada da Fatoracao 33 63 Ordenacao Estatica Tinney 1 34 64 Ordenacao Dinˆamica I Tinney 2 34 65 Ordenacao Dinˆamica II Tinney 3 34 66 Escolha de Esquema de Ordenacao 34 661 Descricao do Algoritmo Tinney 2 T2 34 662 Exemplo 35 7 Tecnicas de Esparsidade na Solucao de SEAL 38 71 Consideracoes Iniciais 38 72 Grau de Esparsidade 38 8 Exercıcios Propostos 40 81 Eliminacao de Gauss 40 82 Eliminacao de GaussJordan 40 83 Operacao em Ponto Flutuante 40 84 Sistemas Numericamente MalCondicionados 41 85 Sistemas de Equacoes Retangulares 41 86 Operacoes com Matrizes 41 87 Fatoracao LU 41 88 Norma Produto Interno e Ortogonalidade 42 89 Fatoracao QR 43 810 Metodo MQP 43 Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 2 Topicos de Algebra Linear Aplicados aos Sistemas Eletricos de Potˆencia 1 Introducao 11 Consideracoes Iniciais Os topicos de algebra linear abordados a seguir se constituem numa das ferramentas matematicas mais amplamente utilizadas em problemas de analise de sistemas de potˆencia O objetivo do texto e resgatar parcialmente os conceitos fundamentais de algebra e analise de matrizes 1 2 Tais fundamentos sao frequentemente usados nos metodos de solucao de sistemas de equacoes algebricas e diferenciais lineares existentes em problemas do tipo 3 4 fluxo de potˆencia transitorios eletromecˆanicos estabilidade de tensao estimacao de estados otimizacao etc Os conceitos nao abordados neste documento serao apresentados na oportunidade em que o pro blema tratado assim o exigir Isto devera acontecer nos modulos subsequentes ao presente 12 Estrutura do Documento O presente documento esta estruturado da seguinte maneira A Secao 2 aborda o problema de ob tencao da solucao de sistemas de equacoes algebricas lineares de grande porte A Secao 3 apresenta formalmente o problema de resolver sistemas retangulares de equacoes algebricas lineares Na Secao 4 apresentamse os metodos diretos de fatoracao de matrizes usualmente empregados na solucao de sistemas de equacoes algebricas lineares de grande porte quer sejam quadrados fatoracao LU ou retangulares fatoracao QR Na Secao 5 apresentase a formulacao classica do metodo de Mınimos Quadrados Ponderados MQP Na Secao 6 discutemse os esquemas de ordenacao de matrizes objeti vando a minimizacao do esforco computacional no processo de fatoracao de matrizes de grande porte Finalmente na Secao 7 sao propostos exercıcios relativos ao conteudo apresentado Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 3 21 Eliminação de Gauss e Matrizes Formulação do Problema a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm m n onde xi são incógnitas ai e bi são constantes conhecidas 1 Um sistema de equações lineares é dito consistente se existe pelo menos uma solução Solução Três Possibilidades 1 Solução Única Existe um e somente um conjunto de valores para xi que satisfaça todas as equações simultaneamente 2 Sem Solução Não existe um conjunto de valores para xi que satisfaça todas as equações simultaneamente isto é o conjunto solução é vazio 3 Mais de uma solução Existem inúmeros conjuntos de valores para xi que satisfazem todas as equações simultaneamente Uma das ferramentas matemáticas que permitem obter a solução das situações consideradas acima é o método da Eliminação de Gauss que possibilita transformar um sistema de equações em outro mais simples porém equivalente possuindo o mesmo conjunto de soluções através de uma sucessiva eliminação de variáveis Ex 1º passo E1 3x 2y z 39 E2 2x 3y z 34 E3 x 2y 3z 26 E1 3 x E3 2º passo primeiro E1 3x 2y z 39 resultado E2 0x 52y 12z 12 2 x E2 parcial E3 0x 4y 8z 39 E3 3º passo E1 3x 2y z 39 E2 0x 5y z 24 E3 0x 4y 8z 39 E2 54 E3 4º passo E1 3x 2y z 39 E2 0x 5y z 24 E3 0x 0y 9z 994 backsubstitution z 114 275 y 174 425 x 11112 925 Sob a forma matricial o sistema de equações anterior pode ser representado como A x b 3 2 1 39 2 3 1 34 1 2 3 26 matriz aumentada beginbmatrix 3 2 1 39 endbmatrix ext matriz aumentada triangularizada fracn33 n2 fracn3 ext multiplicações divisões fracn33 fracn22 frac5n6 ext adições subtrações A propagação de erros face às sucessivas operações em ponto flutuante pode ser desastrosa Uma maneira de minimizar este problema na solução de sistemas de equações lineares através dos métodos já apresentados é a execução de pivoteação parcial ou completa durante o processo de eliminação de Gauss 3 Sistemas de Equacoes Algebricas Redundantes Um sistema de equacoes lineares que consiste de m equacoes a n incognitas onde m n para que tenha solucao e necessario a existˆencia de pelo menos n linhas linearmente independentes Um sistema que apresente esta caracterıstica e designado de retangular ou redundante e tem a seguinte forma a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm 7 A aplicacao do metodo de eliminacao de Gauss ao sistema de equacoes descrito acima exige alguns cuidados especiais em face da obrigatoriedade de que o pivˆo deve ser sempre diferente de zero durante o processo de eliminacao Em sistemas de equacoes lineares onde m n a matriz resultante do processo de eliminacao sempre sera uma matriz triangular Para contornar este problema o metodo de eliminacao de Gauss deve ser modificado atraves dos seguintes passos Suponha que U seja a matriz aumentada associada a um sistema de equacoes retangulares apos i 1 passos de eliminacao A execucao da eliminacao subsequente deve obedecer as seguintes etapas a movendose da esquerda para a direita em U localize a primeira coluna que possui um valor diferente de zero na ou abaixo da iesima posicao ou seja uj b a posicao do pivˆo para a iesima eliminacao e a posicao i j c se necessario permute a iesima linha com a linha inferior de forma a ter um valor diferente de zero na posicao i j e entao todos os elementos abaixo do pivˆo devem ser eliminados Ex A 1 2 1 3 3 2 4 0 4 4 1 2 3 5 5 2 4 0 4 7 Solucao 1 2 1 3 3 2 4 0 4 4 1 2 3 5 5 2 4 0 4 7 1 2 1 3 3 0 0 2 2 2 0 0 2 2 2 0 0 2 2 1 1 2 1 3 3 0 0 2 2 2 0 0 0 0 0 0 0 0 0 3 1 2 1 3 3 0 0 2 2 2 0 0 0 0 3 0 0 0 0 0 E Row Echelon Form O numero de pivˆos ou o numero de linhas diferentes de zero em E ou ainda o numero de colunas Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 10 Ex Determinar o rank e identificar as colunas básicas da matriz A beginpmatrix 1 2 1 1 2 4 2 2 3 6 3 4 endpmatrix 321 Adição Subtração de Matrizes Amn imes m pm Bm imes n Aij pm Bij para i 1 ldots m j 1 ldots n 323 Multiplicação de Matrizes Sejam R1n r1 r2 rn e Cn1 c1 c2 cn O produto interno padrão de R com C é definido como sendo o escalar RC r1c1 r2c2 rnc n n i1 ric i Ex 2 4 2 1 2 3 214223 2864 Propriedades 1 AB BA p n ao comutativa 2 AB C AB AC p distributiva lado esquerdo 3 D EF DF EF p distributiva lado direito 4 ABC ABC p associativa 5 An AA A n vezes 6 ABt BtA t 7 AB BA 325 Inversão de Matrizes Seja a matriz quadrada Ann a matriz Bnn que satisfaz as condições AB In e BA In é chamada de inversa de A e é simbolizada como B A 1 Dizse ainda que a matriz B é nãosingular Então as matrizes que não possuem inversas são ditas matrizes singulares Embora nem todas as matrizes possuam inversas no entanto quando a matriz inversa existe ela é única Existência de Matrizes Inversas 1 Se A é uma matriz nãosingular então há uma única solução para x na equação matricial Ann x np b n1 cuja solução é x A 1 b 2 Um sistema de n equações lineares a n incógnitas pode ser escrito através de uma única equação matricial do tipo Ann x n1 b n1 Se A é uma matriz nãosingular então o sistema de equações lineares tem uma única solução que pode ser expressa por x A 1 b 3 A existência de A 1 implica em a A 1 existe então A é nãosingular b rankA n c A gauss jordan I d Ax 0 implica que x 0 Propriedades Sejam as matrizes A e B nãosingulares então são válidas 1 A 1 1 A 2 O produto AB também é nãosingular 3 AB 1 B 1 A 1 4 A 1 A 1 e A 1 A 1 4 Fatoração de Matrizes 41 Matrizes Quadradas Fatoração LU Se Ann é uma matriz nãosingular a qual pode ser decomposta em A LU onde L é uma matriz triangular inferior unitária e U é uma matriz triangular superior então os elementos lij cujas posições estão abaixo da diagonal principal da matriz L são múltiplos da linha j que subtraída da linha i em A eliminam os elementos que ocupam a posição i j durante o processo de eliminação de Gauss U é a matriz resultante do processo de eliminação de Gauss da matriz A a decomposição de A em A LU é chamada de fatoração LU de A sendo as matrizes L e U designadas de LU fatores de A 411 Redução de Crout A LU O algoritmo proposto por Crout fatora a matriz A de tal forma que as matrizes L e U assumem as seguintes características L matriz triangular inferior U matriz triangular superior unitária Assumindo que os elementos das matrizes A L e U são aij lij e uij respectivamente as expressões que permitem calcular todos os elementos das matrizes L e U são as seguintes lip aip p1k1 likukp para p 1 2 n i p p 1 n upj 1 lpp a jp p1k1 pkukj para p 1 2 n j p 1 n 413 Redução de Cholesky A L D12D12 U L Lt O algoritmo proposto por Cholesky só é aplicável às matrizes que são simétricas e positivas definidas isto é matrizes em que os elementos que ocupam as posições i j são numericamente iguais aos elementos das posições j i As expressões que permitem calcular os elementos da matriz L são Elementos de fora da diagonal lki frac1lii imes aki sumj1i1 lij imes lkj Elementos da diagonal lkk sqrtakk sumj1k1 lkj Nas expressões acima os índices k e i apresentam as seguintes variações k 1 2 cdots n i 1 2 cdots k 1 sendo n a dimensão da matriz a ser fatorada 414 Exemplo de Aplicação Obtém a fatoração LU da matriz apresentada a seguir através dos seguintes algoritmos a Redução de Crout b Redução de Doolittle c Redução de Cholesky A3 imes 3 left beginarrayccc 4 1 3 1 5 2 3 2 6 endarray right Solução a Redução de Crout Índices p 1 cdots 3 j p 1 cdots 3 i p cdots 3 k 1 cdots p 1 1 exto Passo p 1 i 1 3 j 2 3 e k 0 Versão 20 9 de agosto de 2023 GESis ISEE UNIFEI 16 1a coluna de L 1a coluna de A j 2 u12 1 l11 a12 1 4 j 3 u13 1 l11 a13 3 4 2o Passo p 2 i 2 3 j 3 e k 1 i 2 l22 a22 l21 u12 5 1 1 4 19 4 i 3 l32 a32 l31 u12 2 3 1 4 5 4 j 3 u23 1 l22 a23 l21 u13 4 19 2 1 3 4 5 19 3o Passo p 3 i 3 j 0 e k 1 2 i 3 l33 a33 l31 u13 l32 u23 6 3 3 4 5 4 5 19 6 9 4 25 76 65 19 Logo A 4 1 194 3 54 6519 1 14 34 1 519 1 cqf b Reducao de Doolittle b1 Obtencao da Matriz U 1o Pivˆo 4 M1 1 14 1 34 0 1 A2 M1 A 4 1 3 0 194 54 0 54 154 2o Pivˆo 194 M2 1 0 1 0 519 1 A3 M2 M1 A 4 1 3 0 194 54 0 0 6519 U b2 Obtencao da Matriz L Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 17 L M11 imes M12 left beginarrayccc 1 0 0 14 1 0 34 0 1 endarray right imes left beginarrayccc 1 0 0 0 1 0 0 519 1 endarray right left beginarrayccc 1 0 0 14 1 0 34 519 1 endarray right Logo A left beginarrayc 1 14 34 endarray right imes left beginarrayccc 4 1 3 194 54 6519 endarray right caqf c Redução do Cholesky Índices k 1 cdots 3 i 1 cdots k 1 j 1 cdots k 1 1 exto Passo k 1 i 0 j 0 lki rightarrow j 0 lkk rightarrow j 0 l11 sqrta11 2 2 exto Passo k 2 i 1 j lki rightarrow j 0 lkk rightarrow j 1 l21 frac1l11 imes a21 12 l22 sqrta22 l221 5 142 sqrt194 sqrt192 3 exto Passo k 3 i 1 2 j lki rightarrow j 1 lkk rightarrow j 1 2 i 1 rightarrow l31 frac1l11 imes a31 0 frac12 imes 3 32 i 2 rightarrow l32 frac1l22 imes a32 l21 imes l31 frac2sqrt19 imes a32 12 imes 3 frac52sqrt19 l33 sqrta33 l231 l232 sqrt6 94 2576 sqrt6519 Logo A left beginarrayccc 2 12 sqrt192 32 51 2sqrt19 sqrt6519 endarray right imes left beginarrayccc 2 12 32 sqrt192 52sqrt19 sqrt6519 endarray right cqf Versão 20 9 de agosto de 2023 GESis ISEE UNIFEI 18 42 Matrizes Retangulares Fatoração QR Uma forma alternativa de triangularizar a matriz de coeficientes do tipo Am imes n além da utilização da eliminação de Gauss row echelon form é o uso da fatoração QR No entanto a fatoração QR independentemente dos algoritmos empregados requer a introdução de conceitos relevantes de álgebra linear que devem preceder a apresentação dos Métodos Ortogonais de Householder e Givens Estes métodos executam a fatoração QR e serão apresentados nos itens subsequentes da presente seção 421 NormaP Para p geq 1 a norma p de um vetor x in mathbbRn é definida como sendo xp left sumi1n xip right1p Assim sendo permitese definir Norma1 rightarrow x1 sumi1n xi Norma2 rightarrow x2 left sumi1n xi2 right12 rightarrow norma eucidiana Normainfty rightarrow xinfty maxixi rightarrow norma infinita Ex Determinar as normas definidas acima para o vetor x 3 4 3i 1 Solução x1 9 x2 sqrt35 xinfty 5 422 Ortogonalidade Dois vetores no espaço mathbbR3 são ortogonais perpendiculares se o ângulo formado entre eles é igual ao ângulo reto 90circ No espaço ndimensional isto é mathbbRn ou mathbbCm são válidas as afirmativas abaixo mathbbRn x perp y rightarrow xy 0 mathbbCm x perp y rightarrow xy 0 Versão 20 9 de agosto de 2023 GESis ISEE UNIFEI 19 Ex a O vetor x 1 2 3 1 é ortogonal em relação a y 4 1 2 4 porque xy 4 2 6 4 0 mas uma matriz unitaria geralmente nao e ortogonal A matriz P 1 2 1 3 1 6 1 2 1 3 1 6 0 1 3 2 6 e uma matriz ortogonal porque P t P P P t I ou simi larmente porque as linhas e colunas de P constituem um con junto ortonormal 427 Reflexoes de Householder As transformacoes de Householder7 que sao transformacoes lineares obtidas atraves da aplicacao do operador R sobre um vetor v no espaco ℜn e melhor vizualizada no espaco ℜ3 conforme e mostrado na Figura 1 Figura 41 Reflexao de Householder Na figura anterior observase que o vetor Rv x y z resultante e a reflexao do vetor original v x y z em relacao ao plano formado pelos eixos xy causada pela acao do operador R sobre v no espaco ℜ3 Portanto a referida operacao e matematicamente expressa por 7Alston Scott Householder 19041993 foi um dos primeiros matematicos contemporaneo a utilizar o conceito de refletores elementares em aplicacoes numericas PhD pela Universidade de Chicago 1937 Pesquisador da Divisao de Matematica Aplicada do Laboratorio Nacional de Oak Ridge USA desde de 1946 sendo que em 1948 tornase o diretor do laboratorio e uma das figuras mais expressivas em analise numerica e calculo matricial Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 21 423 Medida de ângulo entre Vetores em ℝn ou ℂn A medida de ângulo em radianos entre dois vetores não nulos em ℝ é definido como sendo θ 0 π tal que θ cos1xyx y Se os vetores x e y são ortogonais então a medida de ângulo é obtida via Teorema de Pitágoras Contudo observe que 21 é genérica 424 Medida de distância entre Vetores em ℝn ou ℂn A distância entre os vetores x e y é definida como sendo dx y x y x1 y1² x2 y2² xn yn² 425 Base Ortonormal Seja β u1 u2 un um conjunto formado por vetores ortogonais unitários isto é ui 1 e ui uj para todo i j Então é válido afirmar que Todo conjunto ortonormal é linearmente independente Todo conjunto ortonormal de n vetores de um espaço n dimensional ℝ é uma base ortonormal de ℝ 426 Matrizes Ortogonais Uma matriz ortogonal é definida como sendo a matriz real Pnn cujas colunas e linhas constituem uma base ortonormal em ℝn Então sobre a matriz Pnn é possível afirmar As linhas ou colunas de Pnn são ortogonais P1 Pt Pnn P x₂ x₂ para todo x ℝn1 PROPRIEDADES A matriz identidade In é uma matriz ortogonal Uma matriz ortogonal pode ser considerada como matriz unitária RAj Aj 2 left fracut imes Ajut imes u right u j 1 2 cdots n Assim sendo obtémse R1A R1A11 R1A22 R1A33 beginpmatrix 5 25 4 0 0 10 0 25 10 endpmatrix A2 beginpmatrix 0 10 25 10 endpmatrix e u2 A21 A21 e1 25 beginpmatrix 1 1 endpmatrix Se hatR2 I 2 imes u2t u2u2t u2 e R2 beginpmatrix 1 0 0 R2 endpmatrix então hatR2 imes A2 beginpmatrix 25 10 10 10 endpmatrix e R2 imes R1 imes A T beginpmatrix 5 25 4 0 25 10 0 0 10 endpmatrix Finalmente P R2R1 frac125 imes beginpmatrix 0 15 20 20 12 9 15 16 12 endpmatrix P imes A T rightarrow sendo P matriz ortogonal Figura 42 Rotacoes de Givens Formulacao Matematica Com base na descricao feita no item anterior e possıvel definir um plano rotacional a partir de uma matriz ortogonal que tem a seguinte forma Pij 1 c s 1 s c 1 1 linha i linha j 33 na qual c2 s2 1 e designado de plano rotacional matricial porque esta operacao executa uma rotacao no plano i j de ℜn As variaveis c e s sugerem as funcoes cosseno e seno respectivamente sendo que a designacao do ˆangulo de rotacao θ como e mostrado no espaco ℜ2 e desnecessaria em ℜn Assim sendo a aplicacao da matriz ortogonal Pij sobre 0 x ℜn rotaciona as coordenadas i j de x de tal forma que Pij x x1 cxi sxj sxi cxj xn i j 34 Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 25 Se xi e xj são ambos nãonulos então é possível escrever c xi sqrtxi2 xj2 e s xj sqrtxi2 xj2 então Pij imes x beginpmatrix x1 vdots sqrtxi2 xj2 vdots 0 vdots xn endpmatrix Isto significa que as rotações de Givens permitem eliminar qualquer elemento do vetor x através de uma rotação no plano i j sem afetar os demais elementos do vetor exceto os elementos xi e xj A generalização da operação descrita acima permite concluir que a utilização de rotações de Givens pode ser estendida e usada na eliminação de elementos situados em posições abaixo de um dado pivô Por exemplo o processo de eliminação de todos os elementos em x que ocupam as posições abaixo do primeiro elemento pode ser obtida através de uma sequência de rotações conforme demonstrase a seguir P12 imes x beginpmatrix sqrtx12 x22 0 x3 x4 vdots xn endpmatrix P13 imes P12 imes x beginpmatrix sqrtx12 x22 0 0 x4 vdots xn endpmatrix P1n cdots P13 imes P12 imes x beginpmatrix x 0 0 vdots 0 endpmatrix Exemplo de Aplicação Obter a redução de Givens da matriz A beginpmatrix 0 20 14 3 27 4 4 11 2 endpmatrix Solução O plano rotacional que usa o elemento 1 1 para eliminar o elemento 2 1 é dado pelas expressões que calculam os parâmetros c e s apresentados anteriormente Assim sendo temse que P12 beginpmatrix 0 1 0 1 0 0 0 0 1 endpmatrix rightarrow P12 imes A beginpmatrix 3 27 4 0 20 14 4 11 2 endpmatrix Similar ao passo anterior o plano rotacional que usa o elemento 1 2 em P12 imes A para eliminar o elemento 1 3 de P12 imes A também faz uso dos parâmetros c e s Esta operação resulta em P13 frac15 beginpmatrix 3 0 4 0 5 0 4 0 3 endpmatrix rightarrow P13 imes P12 imes A beginpmatrix 5 25 4 0 20 14 0 15 2 endpmatrix Finalmente usando o elemento 2 2 em P13 imes P12 imes A para eliminar o elemento 3 2 produz os seguintes resultados P23 frac15 beginpmatrix 5 0 0 0 4 3 0 3 4 endpmatrix rightarrow P23 imes P13 imes P12 imes A T beginpmatrix 5 25 4 0 25 10 0 0 10 endpmatrix Então P P23 imes P13 imes P12 frac125 beginpmatrix 0 15 20 20 12 9 15 16 12 endpmatrix P imes A T rightarrow sendo P matriz ortogonal colunas da matriz de coeficientes A Em contrapartida quando a natureza do problema a ser resolvido e organizada por linhas da matriz A as rotacoes de Givens sao mais efi cientes computacionalmente apesar da robustez numerica de ambos os metodos serem equivalentes 44 Quadro Comparativo de Esforco Computacional O numero de operacoes em ponto flutuante envolvendo multiplicacoes divisoes ne cessarias a reducao de uma matriz de dimensao n n a uma matriz triangular superior atraves dos metodo apresentados e mostrado no quadro abaixo flops numero de operacoes em ponto flutuante Metodos de Reducao n n m n Eliminacao de Gauss n33 mn2 n33 Reflexoes de Householder 2n33 4m2n mn2 n33 Rotacoes de Givens 4n23 3n2m n3 Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 28 5 Método de Mínimos Quadrados Ponderados MQP 51 Formulação Matemática A formulação clássica do problema de mínimos quadrados ponderados weighted leastsquares foi pioneiramente proposta por CF Gauss 1795 A apresentação da referida formulação é feita com o auxílio da Figura 3 mostrada em seguida onde estão indicadas as coordenadas xi yi no espaço ℝ² que representam o conjunto F de observações feitas sobre um dado experimento isto é F x₁y₁ x₂y₂ xₘyₘ onde o parâmetro xᵢ geralmente representa o instante em que a observação yᵢ é feita Com base nas observações realizadas o problema de fazer estimativas ou previsões num instante x pode ser contornado através da abordagem clássica de encontrar uma função y fx que melhor se ajuste aos pares ordenados xᵢyᵢ em F de tal forma que o experimento pode ser estimado em qualquer instante não observado x cujo resultado pode ser avaliado através da função ȳ fx Figura 51 Problema de Regressão Linear A equação da função do exemplo mostrada na figura anterior é do tipo fx axb Portanto o problema se resume em determinar os coeficientes a e b da equação de reta que melhor ajusta os pares ordenados xᵢ yᵢ em F para que a soma dos quadrados das distâncias verticais isto é dos erros ε₁ ε₂ εₘ seja mínimo A distância de xᵢ yᵢ à reta fx axb pode ser conhecida através da expressão εᵢ fxᵢ yᵢ axi b yᵢ 41 Então o problema pode ser resolvido através da minimização da função quadrática do erro no sentido de se determinar os valores dos coeficientes a e b da equação de reta que resulta no menor valor da função objetivo ₘᵢ₁ εᵢ² ₘᵢ₁ axi b yᵢ² mínimo 42 Uma das primeiras técnicas de cálculo do valor mínimo de uma função consiste em determinar a solução do sistema de equações descrito abaixo 9 Para assegurar a existência de um mínimo global ₘᵢ₁ axibyᵢ² a 2 ₘᵢ₁ axi b yᵢ xᵢ 0 43 ₘᵢ₁ axibyᵢ² b 2 ₘᵢ₁ axi b yᵢ 0 Agrupando os termos semelhantes no sistema de equações acima obtémse ₘᵢ₁ xᵢ b ₘᵢ₁ xᵢ² a ₘᵢ₁ xᵢ yᵢ ₘᵢ₁ 1 b ₘᵢ₁ xᵢ a ₘᵢ₁ yᵢ 44 Este último de equações na forma matricial resulta A x₁ 1 x₂ 1 xₘ 1 y y₁ y₂ yₘ x a b 45 A solução do sistema de equações anterior pode ser obtida através do Método da Equação Normal de Gauss ou seja ATA x AT y 46 O sistema acima tem solução se e somente se a condição de rankA 2 for satisfeita Neste último caso o sistema tem uma única solução que é obtida através da equação x ATA¹ ATy G¹ b 47 sendo G ATA e b ATy 48 Finalmente devese observar que a soma total do quadrado dos erros ou resíduos r pode ser conhecida a partir da seguinte expressão ₘᵢ₁ rᵢ² ₘᵢ₁ axi b yᵢ² Ax bᴴ Ax b rᴴ r 49 52 Exemplo de Aplicação A administração de uma pequena empresa deseja fazer o seu planejamento financeiro anual com base no seguinte histórico de vendas expressas em milhões de Reais 10³ R Ano 1 2 3 4 5 Vendas Realizadas 23 27 30 34 Valores Estimados A qual a expectativa de vendas para o quinto ano Solução Uma solução do problema proposto é obtida através minimização da função quadrática dos resíduos que em outras palavras representa a determinação dos coeficientes da equação de reta que melhor ajusta as observações xᵢ yᵢ realizadas nos últimos quatro anos Assim sendo permitese escrever A 1 1 1 1 2 1 3 1 4 1 y 23 27 30 34 x a b Calculando G 30 10 10 4 b 303 114 Então a solução desejada é xᴴ 36 195 O que permite definir fx ax b como sendo fx y 36x 195 Finalmente a expectativa de vendas no quinto ano pode ser estimada em R 375 x 10³ Com base na função obtida podese determinar a soma ponderada do quadrado dos resíduos SPQR que representa a norma Euclidiana norma 2 do vetor de erros isto é Ano 1 2 3 4 Vendas Realizadas y 230 270 300 340 Valores Estimados ŷ 231 267 303 339 ε r y ŷ 01 03 03 01 ρ² 001 009 009 001 Então SPQR ₄ᵢ₁ rᵢ² 02 Este índice representa a soma do quadrado dos erros de cada estimativa rᵢ² cometidos no processo de estimativa das grandes desejadas Usualmente o índico SPQR é usado em bases estatísticas para inferir a existência detecção de observações errôneas No exemplo anterior os erros cometidos nas observações realizadas são ponderados igualmente ie recebem uma ponderação unitária Por outro lado se tais observações são feitas através de instrumentos que possuem classe de precisão diferentes então é razoável supor que as medidas mais R beginbmatrix sigma12 sigma22 vdots sigmam2 endbmatrix A introdução da matriz R nas equações 4749 transformam estas últimas em x AT R1 A1 AT R1 y G1 ildeb G AT R1 A quad e quad ildeb AT R1 y sumi1m left fracrisigmai right2 Ax bT R1 Ax b xT R1 x 6 Esquemas de Ordenacao 61 Consideracoes Iniciais A ordenacao e a renumeracao de barras com o objetivo primeiro de reduzir o numero de fill ins que sao elementos nao nulos que aparecem nas matrizes fatores em posicoes onde existiam elementos nulos na matriz original Para isto e desejavel que o esforco de indexacao seja pequeno quando da implementacao de um algoritmo de ordenacao elaborado com este proposito As metodologias de solucao de sistemas de equacoes algebricas lineares por metodos diretos e realizada atraves da escolha de pivˆos localizados na diagonal principal das matrizes de coeficientes na ordem em que estes aparecem na matriz ordem natural No entanto a solucao destes sistemas na ordem natural pode trazer alguns problemas por exemplo elemento diagonal nulo erros de arredondamento aumento do esforco computacional Apesar do hardware disponıvel atualmente o esforco computacional necessario no processo de fa toracao de matrizes de muito grande porte mesmo que sejam esparsas requer um tempo incompatıvel com a velocidade de calculo que algumas aplicacoes em sistemas eletricos exigem No processo de eliminacao de Gauss por exemplo sobre o qual se baseiam todos os metodos de fatoracao de matrizes a criacao de elementos nao nulos e tanto maior quanto for o numero de elementos nao nulos da linha coluna processada 62 Modelos de Ordenacao 621 Ordenacao Durante a Fatoracao A ordenacao e realizada simultaneamente ao processo de fatoracao A fatoracao de matrizes de mesma estrutura neste modelo de ordenacao e desaconselhada pois a ordenacao deve ser repetida para cada matriz A vantagem deste metodo e notada quando temse elementos diagonais cujas magnitudes sejam proximas de zero pois a ordenacao pode ser realizada com pivotamento 622 Ordenacao com Eliminacao Perfeita Esta metodologia consiste na ordenacao simbolica da matriz Desta forma prevese o aparecimento de fill ins o que permite reservar posicoes na tabela de fatores usadas nas tecnicas de armazenamento de matrizes esparsas Portanto esta ordenacao e realizada em separado o que permite utilizala para fatorar varias matrizes de mesma estrutura 623 Ordenacao Separada da Fatoracao A estrategia usada e a de obter inicialmente uma ordenacao para os nos Em seguida a fatoracao e realizada acomodandose os fill ins a medida que aparecam A grande vantagem desta ordenacao e observada quando a estrutura da matriz muda muito pouco entre cada solucao nao justificando um Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 33 esforco de reordenacao A diferenca em relacao ao modelo de ordenacao perfeita ocorre apenas na acomodacao dos fill ins que se da a medida que eles sao criados Em problemas de analise de redes trˆes esquemas de ordenacao sao reconhecidamente considerados como os mais apropriados 5 6 63 Ordenacao Estatica Tinney 1 A ordenacao ocorre em ordem crescento do grau de cada no da matriz original Se dois ou mais nos apresentarem o mesmo grau a escolha entre eles e arbitraria 64 Ordenacao Dinˆamica I Tinney 2 A ordenacao e feita segundo o grau de cada no da rede reduzida ou seja a cada passo da reducao escolhese como o proximo no a ser eliminado o de menor grau do grafo residual Portanto este metodo se baseia na ordenacao crescente do grau de adjacˆencia dos nos e apresenta bons resultados com modesto esforco computacional Se mais de um no se qualificar pelo criterio estabelecido a escolha entre eles e arbitraria 65 Ordenacao Dinˆamica II Tinney 3 A cada passo da fatoracao escolhese para ser eliminado o no da rede que uma vez eliminado introduza o menor numero de novas ligacoes no grafo residual ou seja devese eliminar o no de menor valˆencia do grafo residual Se mais de um no se qualificar a escolha entre eles e arbitraria 66 Escolha de Esquema de Ordenacao A escolha do melhor esquema de ordenacao depende do tipo de aplicacao Em problemas de analise de redes eletricas o esquema que apresenta a melhor relacao custo benefıcio e o esquema de ordenacao dinˆamica I conhecida como Tinney 2 Este esquema e o que apresenta a melhor relacao entre esforco computacional para obter a or denacao e a reducao dos requisitos computacionais para a solucao do sistema de equacoes Pelas razoes expostas acima a subsecao apresentada em seguida descreve o algoritmo e apresenta o pseudocodigo 661 Descricao do Algoritmo Tinney 2 T2 A literatura tecnica tem este metodo de ordenacao como referˆencia sendo que o seu objetivo principal e preservar a estrutura de esparsidade da matriz original apos a fatoracao desta ultima Ou seja busca se minimizar o aparecimento de elementos diferentes de zero na matriz triangularizada por exemplo matriz fator L da fatoracao LU e a matriz fator R da fatoracao QR que em posicoes equivalentes na matriz original sao nulos Assim sendo considere as seguintes definicoes fi a posicao do no i na ordenacao final Inicialmente fi 0 Di e o grau do no i no grafo reduzido Inicialmente Di e o grau do no i no grafo original Filled Graph seja uma matriz A decomposta p ex A L LT O grafo associado a matriz F L LT e chamado filled graph GF Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 34 Pseudocodigo do Algoritmo T2 Passo 1 Faca k 1 Passo 2 Selecione o no i com fi 0 tal que Di e mınimo Se este criterio selecionar mais de um no escolhese o primeiro ou o ultimo no da ordem natural Faca fi k Passo 3 Para cada no j adjacente ao no i tal que fi 0 faca Dj Dj 1 Passo 4 Para cada par de nos m e n adjacentes ao no i mas nao adjacentes entre si tal que fm fn 0 crie um novo ramo mn e aumente Dm e Dn de uma unidade Passo 5 Se k n pare Caso contrario faca k k 1 e retorne ao Passo 2 662 Exemplo Seja o grafo da rede eletrica representada pela Fig 61 Figura 61 Grafo relativo a matriz de incidˆencia do sistema teste de 10 barras A estrutura da matriz de incidˆencia que representa a rede eletrica e mostrada na Fig 63 Por sua vez a matriz triangularizada isto e matriz fator U obtida segundo a ordem natural de fatoracao mostrada abaixo Fig 62 e apresentada na Fig 64 Figura 62 Grafo do caminho de fatoracao com ordem natural Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 35 Figura 63 Matriz de incidˆencia de um sistema teste de 10 barras Figura 64 Matriz U Obtida via ordem natural de fatoracao 19 fill in O grafo que mostra o novo caminho da fatoracao10 e apresentado abaixo na Fig 65 A estrutura da matriz fator U agora obtida segundo o metodo de ordenacao T2 e mostrada na Fig 66 10e o grafo que mostra a relacao de precedˆencia entre nos para as operacoes de substituicao direta e inversa Com putacionalmente o caminho de fatoracao e uma maneira eficiente de encontrar as colunas e linhas necessarias para as substituicoes direta e inversa respectivamente Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 36 Figura 65 Grafo do caminho de fatoracao via algoritmo T2 Figura 66 Matriz fator via T2 3 fill in Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 37 7 Tecnicas de Esparsidade na Solucao de SEAL 71 Consideracoes Iniciais No planejamento e na operacao de sistemas de energia eletrica e muito comum a solucao de sistemas matriciais esparsos que representam a rede eletrica nos programas de simulacao utilizados cabendo destacar Estimacao de Estados Fluxo de Potˆencia Analise de CurtoCircuito Analise de Contingˆencias Analise de Estabilidade Dinˆamica Analise de Estabilidade Transitoria Equivalentes Externos Etc Assim as tecnicas de esparsidade sao de fundamental importˆancia para o desenvolvimento de programas computacionais eficientes Lembrando que a essˆencia da esparsidade esta fundamentada em 1 Somente elementos nao nulos sao armazenados e operados antes durante e apos o processo de fatorizacao da matriz Como em aplicacoes que envolvem modelagem da rede eletrica a percen tagem de elementos nao nulos e muito pequena a quantidade de aritmetica envolvida e muito menor se comparada com tecnicas nao esparsas 2 Economia de espaco em memoria e diminuicao do tempo de comunicacao entre o processador e a memoria 72 Grau de Esparsidade O grau de esparsidade de uma matriz e definido como sendo a percentagem de elementos nao nulos de uma matriz determinado pela seguinte relacao algebrica GE n2 nnn n2 100 53 onde n e a dimensao da matriz enquanto nnn n 2 ℓ e o numero de elementos nao nulos da matriz sendo ℓ o numero de ramos da rede Exemplo A analise nodal consolidada na simulacao de sistema de energia eletrica atraves da relacao Y E I 54 Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 38 Sendo que Y Matriz de admitˆancia nodal E Vetor de tensoes nodais I Vetor de injecoes de correntes Para o caso tıpico temse n ℓ GE 10 15 60 100 150 96 1000 1500 9960 No entanto o numero medio de ligacoes por no independe do tamanho da rede O quadro acima mostra que o ındice GE aumenta a medida que o tamanho da rede cresce Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 39 8 Exercícios Propostos 81 Eliminação de Gauss 1 Usar o método de eliminação de Gauss com substituição inversa para resolver o seguinte sistema de equações x1 x2 x3 1 quad x1 2x2 2x3 1 quad x1 2x2 3x3 1 2 Considere os seguintes três sistemas de equações onde os coeficientes são os mesmos para cada um dos três sistemas mas o lado direito são diferentes esta situação ocorre com bastante frequência 4x 8y 5z 1 quad 0 quad 0 4x 7y 4z 0 quad 1 quad 0 3x 4y 2z 0 quad 0 quad 1 Resolva os três sistemas de equações de uma única vez através do método de eliminação de Gauss aplicado à matriz aumentada da forma A b1 b2 b3 3 O seguinte sistema de equações não tem solução x1 3x2 2x3 1 quad x1 4x2 3x3 0 quad x1 5x2 4x3 0 Tente resolver este sistema usando a eliminação de Gauss e explique o que ocorre durante o processo de eliminação que indica a impossibilidade de resolvêlo 82 Eliminação de GaussJordan 4 Use o método de GaussJordan para resolver o sistema de equações apresentado em seguida x1 x2 x3 x4 1 quad x1 2x2 2x3 2x4 0 quad x1 2x2 3x3 3x4 0 quad x1 2x2 3x3 4x4 0 83 Operação em Ponto Flutuante 5 Estabeleça um quadro comparativo entre as soluções obtidas para o sistema de equações mostrado em seguida considerandose as soluções a exata b sem pivoteação porém com precisão de três dígitos t 3 c com pivoteação parcial e t 3 begincases 3x y 2 10x 3y 7 endcases b1 6 0 6 e b2 6 2 12 c Use as matrizes fatores LU para derterminar A1 10 Explique porque A 1 2 3 2 8 12 3 12 27 e uma matriz positiva definida e determine a matriz fator L da reducao de Cholesky 88 Norma Produto Interno e Ortogonalidade 11 Determine as normas 1 2 e dos seguintes vetores x 2 1 4 2 e y 1 i 1 i 1 4i 12 Considere a norma euclidiana dos seguintes vetores x 2 1 4 2 e y 1 1 1 1 Determine a distˆancia entre os vetores x e y 13 Usando a propriedade de produto interno padrao determine quais dos seguintes pares de vetores sao ortogonais no espaco indicado a x 1 3 4 e y 2 2 2 em ℜ3 b x i 1 i 2 1 i e y 0 1 i 2 1 i em C4 c x 1 2 3 4 e y 4 2 1 1 em ℜ4 d x 1 i 1 i e y 1 i 3 1 em C3 e x 0 0 0 e y y1 y2 yn em ℜn Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 42 14 Determine o ˆangulo entre os vetores mostrados abaixo x 2 1 1 e y 1 1 2 89 Fatoracao QR 15 Dados A 1 0 1 1 2 1 1 1 3 0 1 1 e b 1 1 1 1 a Determine a fatoracao QR de A b Use as matrizes fatores Q e R do item anterior para determinar a solucao do sistema de equacoes Ax b c Determine a solucao do sistema de equacoes Ax b atraves do metodo da equacao normal 810 Metodo MQP 16 Um mıssil e disparado de um territorio inimigo e sua trajetoria durante o vˆoo e rastreada por radar A sequˆencia de medicoes realizadas esta resumida no quadro abaixo Posicao X milhas 0 250 500 750 1000 Altura Y milhas 0 8 15 19 20 Suponha que a inteligˆencia do paıs amigo pressuponha que os mısseis inimigos realizam uma trajetoria segundo uma parabola Determine o quao distante da origem os mısseis irao atingir o territorio amigo Versao 20 9 de agosto de 2023 GESis ISEE UNIFEI 43 Bibliografia 1 C D Meyer Matrix Analysis and Applied Linear Algebra SAIM Ed Society for Industrial and Applied Mathematics 2000 iSBN 089874540 2 G Golub and C V Loan Matrix Computations 2nd ed John Hopkins University Press 1993 3 G Meurant Computer Solution of Large Linear Systems N Y H F T H K P JL Lions Paris G Papanicolaou Ed Sara Burgerhartstraat 25 PO Box 211 1000 AE Amsterdam The Netherlands Elsevier Science BV 1999 vol 28 iSBN 044450169X 4 L N Trefethen and I David Bau Numerical Linear Algebra SIAM Ed Society for Industrial and Applied Mathematics 1997 iSBN 089873617 5 W F Tinney and J W Walker Direct solutions of sparse network equations by optimally ordered triangular factorization Proceedings of the IEEE vol 55 no 11 pp 18011809 Nov 1967 6 N Sato and W F Tinney Techniques for exploiting the sparsity or the network admittance matrix IEEE Transactions on Power Apparatus and Systems vol 82 no 69 pp 944950 Dec 1963 44