Equações Lineares

  • View
    238

  • Download
    3

Embed Size (px)

DESCRIPTION

Equações Lineares

Text of Equações Lineares

  • Sistemas de equacoes lineares

    Joaquim Joao JudiceJoao Manuel Patrcio

    Departamento de Matematica da Universidade de Coimbra1996

  • Conteudo

    Introducao 3

    Notacao 5

    1 Exemplos de Sistemas de Equacoes Lineares 1

    2 Alguns Conceitos de Algebra Linear Numerica 82.1 Precisao numerica e erros de arredondamento . . . . . . . . . . . . . . . . . . . . . 82.2 Vectores e Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Normas e valores proprios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Perturbacao de sistemas de equacoes lineares . . . . . . . . . . . . . . . . . . . . . 18

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

    3 Classes de Matrizes 233.1 Operacoes Pivotais, Transformada principal e Complemento de Schur . . . . . . . 233.2 Matrizes diagonalmente dominantes . . . . . . . . . . . . . . . . . . . . . . . . . . 303.3 Matrizes Positivas Denidas e Positivas SemiDenidas . . . . . . . . . . . . . . . 343.4 Matrizes P e P0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.5 Matrizes S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.6 Matrizes Z e K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.7 Matrizes H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

    4 Metodos Directos para Sistemas de Equacoes Lineares comMatrizes QuadradasDensas 514.1 Resolucao de sistemas triangulares . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Decomposicao LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3 Complemento de Schur e decomposicao LU . . . . . . . . . . . . . . . . . . . . . . 564.4 Escolha parcial de pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.5 Escalonamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.6 Renamento iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.7 Estimacao do numero de condicao de uma matriz . . . . . . . . . . . . . . . . . . . 674.8 Metodo dos bordos para a decomposicao LU . . . . . . . . . . . . . . . . . . . . . 694.9 Metodo directo para a decomposicao LU . . . . . . . . . . . . . . . . . . . . . . . . 724.10 Decomposicao LDU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764.11 Classes de matrizes nao simetricas com decomposicao LU estavel . . . . . . . . . . 784.12 Resolucao de sistemas com matrizes simetricas . . . . . . . . . . . . . . . . . . . . 854.13 Calculo do determinante e da inversa de uma matriz . . . . . . . . . . . . . . . . . 104

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

    1

  • 5 Metodos Directos para Sistemas de Equacoes Lineares com Estrutura Especial1115.1 Matrizes com estrutura de banda . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.2 Matrizes com estrutura de blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

    6 Armazenagem e Operacoes com Vectores e Matrizes Esparsas 1276.1 Armazenagem de vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.2 Operacoes com vectores esparsos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1286.3 Armazenagem de matrizes esparsas . . . . . . . . . . . . . . . . . . . . . . . . . . . 1316.4 Operacoes com matrizes esparsas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

    7 Metodos Directos para Sistemas de Equacoes Lineares com Matrizes Esparsas1477.1 Matrizes simetricas positivas denidas . . . . . . . . . . . . . . . . . . . . . . . . . 1487.2 Matrizes nao simetricas com pivots diagonais estaveis . . . . . . . . . . . . . . . . 1607.3 Matrizes nao simetricas com pivots diagonais instaveis . . . . . . . . . . . . . . . . 1637.4 Uso do Complemento de Schur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1697.5 Experiencia computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

    8 Metodos Iterativos para Sistemas de Equacoes Lineares com Matrizes Quadra-das 1748.1 Metodos iterativos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1748.2 Convergencia dos metodos iterativos basicos . . . . . . . . . . . . . . . . . . . . . . 1808.3 Caractersticas dos metodos iterativos basicos . . . . . . . . . . . . . . . . . . . . . 1888.4 Metodo da Particao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1918.5 Metodo dos Gradientes Conjugados . . . . . . . . . . . . . . . . . . . . . . . . . . . 1938.6 A tecnica de Precondicionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2008.7 Decomposicao incompleta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2048.8 Experiencia computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

    9 Matrizes ortogonais 2149.1 Denicao e propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2149.2 Matrizes de Householder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2159.3 Matrizes de Givens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

    10 Resolucao de sistemas de equacoes lineares com matrizes rectangulares 22510.1 Metodos directos para sistemas verticais . . . . . . . . . . . . . . . . . . . . . . . . 22510.2 Metodos directos para sistemas horizontais . . . . . . . . . . . . . . . . . . . . . . 23010.3 Metodos iterativos para sistemas rectangulares . . . . . . . . . . . . . . . . . . . . 233

    Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

    Bibliografia 239

  • Introducao

    Os sistemas de equacoes lineares surgem em praticamente todas as areas da matematica aplicada.O grande desenvolvimento dos meios de calculo automatico a que se tem assistido ultimamentetem possibilitado resolver sistemas com cada vez maior numero de variaveis e de equacoes. Estelivro apresenta as tecnicas mais conhecidas para a resolucao destes problemas e debruca-se sobreas questoes teoricas e praticas que lhes estao subjacentes.

    Este trabalho e tambem uma compilacao das aulas por nos leccionadas na disciplina de AlgebraLinear Numerica do terceiro ano da Licenciatura em Matematica do Departamento de Matematicada Universidade de Coimbra. Nesse sentido procuramos apresentar as varias tecnicas para a re-solucao de sistemas de equacoes lineares de um modo detalhado para que nao surjam quaisquerduvidas sobre o seu funcionamento. Alem disso tivemos especial cuidado em apresentar as imple-mentacoes desses processos para o caso de sistemas com grande numero de variaveis e equacoes.A escolha de uma tecnica para a resolucao de um dado sistema depende da ordem, esparsidade,estrutura e classe da sua matriz. A importancia de todos esses aspectos e devidamente realcadaneste livro, sendo apresentadas em muitos casos conclusoes seguras sobre o algoritmo a escolherpara a resolucao do sistema em causa. Dado o caracter didactico deste livro resolvemos omitiralguns resultados e demonstracoes mais tecnicas. Alem disso muitos processos importantes paraa resolucao de sistemas foram simplesmente omitidos, por total indisponibilidade de tempo. Noentanto esses assuntos sao discutidos em alguns dos livros mencionados na Bibliograa.

    Apesar de termos alguma preocupacao em apresentar os assuntos de um modo um poucodiferente do habitual, aproveitamos sempre que possvel ideias, resultados e demonstracoes deoutros autores. Isso aconteceu nomeadamente nos exemplos que constituem o primeiro captulodo livro, que permitem vericar a importancia da ordem, esparsidade e estrutura da matriz naresolucao do sistema.

    Nos captulos 2 e 3 sao discutidos alguns conceitos de algebra linear que estao normalmenteassociados a` resolucao de sistemas de equacoes lineares. Assim, sao apresentadas as denicoese propriedades de normas vectoriais e matriciais, numero de condicao, complemento de Schur ealgumas classes de matrizes.

    O captulo 4 e dedicado aos chamados metodos directos para sistemas de equacoes lineares.Esses processos procuram obter a solucao exacta do sistema usando decomposicoes da sua matrizem matrizes triangulares ou diagonais. As decomposicoes LU e LDU sao discutidas com bastantedetalhe tanto do ponto de vista teorico como pratico e computacional, sendo dado especial enfasea`s varias formas de as obter, tanto no caso nao simetrico como simetrico. A estabilidade dessasdecomposicoes e estudada com bastante cuidado, sendo discutidas a tecnica de escolha parcial depivot e as classes de matrizes com pivots diagonais estaveis. Ainda relacionados com a precisaoda solucao do sistema, sao descritos os processos de escalonamento, de renamento iterativo e asestimativas do numero de condicao de uma matriz. Finalmente os problemas de determinacao damatriz inversa e do calculo do determinante de uma matriz sao abordados na ultima seccao destecaptulo.

    Os captulos 5 e 7 debrucam-se sobre o uso de metodos directos na resolucao de sistemas deequacoes lineares com matrizes esparsas. Assim, as matrizes com estrutura de banda e blocosao discutidas no captulo 5, sendo as matr