sistemas Lineares

sistemas Lineares

(Parte 1 de 11)

Instituto de Ciências Exatas e Biológicas Departamento de Computação

José Álvaro Tadeu Ferreira

Cálculo Numérico – Notas de aulas Resolução de Sistemas de Equações Lineares Simultâneas

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 2

Resolução de Sistemas de Equações Lineares Simultâneas

1 - Introdução A resolução de sistemas de equações lineares simultâneas é um dos problemas numéricos mais comuns em aplicações científicas para simular situações do mundo real. É etapa fundamental na resolução de vários problemas que envolvam, por exemplo, equações diferenciais parciais, determinação de caminhos ótimos em redes (grafos), regressão, sistemas não lineares, interpolação de pontos, dentre outros. Vários problemas da Engenharia envolvem a resolução de sistemas de equações lineares. A título de exemplo, considere-se a determinação de do potencial em redes elétricas, o cálculo da tensão em estruturas metálicas na construção civil, o cálculo da razão de escoamento em um sistema hidráulico com derivações, a previsão da concentração de reagentes sujeitos a reações químicas simultâneas. Neste texto será considerada a resolução de um sistema de equações lineares de n equações com n incógnitas, da forma mostrada em (1.1).

bxaxaxa bxaxaxa bxaxaxa

b3,, bn os termos independentes do sistema de equações. Este sistema pode ser escrito

Onde nxxx,...,,21 são as incógnitas, na,...,,1211 os coeficientes das incógnitas e b1, b2, sob a forma matricial, freqüentemente mais vantajosa, mediante o emprego da seguinte notação

A.x = b(1.2)

Em que b b x x bxA.

Assim, A é a matriz dos coeficientes das incógnitas, x o vetor coluna das incógnitas e b o vetor coluna dos termos independentes. A matriz A e os vetores coluna x e b serão considerados reais, não obstante muito do que se vai dizer neste capítulo ser generalizável ao campo complexo sem grande dificuldade.

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 3

Uma matriz bastante importante, e que será utilizada posteriormente, é a matriz aumentada de um sistema de equações lineares. Conforme mostrado a seguir, para obtê-la basta acrescentar à matriz dos coeficientes o vetor b dos termos independentes.

baaa baaa baaa

Definição 1.1 Denomina-se vetor solução (ou simplesmente solução) de um sistema de equações lineares da forma Ax = b, e denota-se por x, ao vetor que contém as variáveis xj , j = 1, · · · , n, que satisfazem, de forma simultânea, a todas as equações do sistema.

2 - Classificação de um sistema de equações com relação ao número de soluções Com relação ao número de soluções, um sistema de equações lineares simultâneas pode ser classificado em: (a) Compatível e determinado: quando admitir uma única solução. (b) Compatível e indeterminado: quando admitir um número infinito de soluções. (c) Incompatível: quando não admitir solução. Vale lembrar que, a condição para que um sistema de equações lineares tenha solução única é que o determinante da matriz dos coeficientes seja não nulo. Caso contrário será indeterminado ou incompatível.

Quando todos os termos independentes forem nulos, isto é, se bi = 0, i = 0, 1,, n, o siste-

ma é dito homogêneo. Todo sistema homogêneo é compatível, pois admitirá pelo menos a

solução trivial (xj = 0, j = 0, 1, 2,, n).

De uma forma mais ampla, pode-se considerar que resolver um sistema de equações con- siste em diagnosticar em qual das três situações ele se enquadra. Ou seja, é mais do que determinar um vetor x, uma vez que ele pode não existir ou não ser único.

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 4

3 – Métodos numéricos para a resolução de sistemas de equações lineares Os métodos numéricos destinados a resolver sistemas lineares são divididos em dois gru- pos: os métodos diretos e os métodos iterativos.

4 – Métodos Diretos Os Métodos Diretos são aqueles que, exceto por erros de arredondamento, fornecem a solução exata de um sistema de equações lineares, caso ela exista, por meio de um número finito de operações aritméticas. São métodos bastante utilizados na resolução de sistemas de equações densos de porte pequeno a médio. Entenda-se por sistema denso aquele na qual a matriz dos coeficientes tem um número pequeno de elementos nulos. São considerados sistemas de pequeno porte aqueles que possuem até trinta equações e de médio porte até cinqüenta equações. A partir daí, em geral, são considerados sistemas de grande porte.

Pertencem à classe dos Métodos diretos todos os que são estudados nos cursos de 1o e 2o graus como, por exemplo, a Regra de Cramer. Entretanto, tais métodos não são usados em problemas práticos que exigem a resolução de sistemas de equações lineares com um número relativamente grande de equações porque apresentam problemas de desempenho e eficiência. Para ilustrar este fato considere-se a Regra de Cramer. Seja um sistema de equações lineares A.x = b com o número de equações igual ao número

de incógnitas (um sistema n x n), sendo D o determinante da matriz A, e Dx1, Dx2, Dx3,,
dos coeficientes de x1, x2, x3,, xn pela coluna dos termos independentes. Sabe-se que o

Dxn os determinantes das matrizes obtidas substituindo em A, respectivamente, a coluna sistema será compatível e terá solução única se, e somente se, D 0 e, então, a única solu- ção de A.x = b é dada por:

x1 = xDD 1, x2 =

3,, xn = xnDD

D Dx2, x3 = xDD

Portanto, aplicação da Regra de Cramer exige o cálculo de n + 1 determinantes ( det A e det Ai, 1 i n). Pode ser mostrado que o número máximo de operações aritméticas envolvidas na resolução de um sistema de equações lineares com n equações e n incógnitas para este método é (n + 1)(n!)(n − 1), Para n = 20 o número total de operações efetuadas será 21 * 20! * 19 multiplicações mais um número semelhante de adições. Assim, um computador que efetue cerca de 100 milhões de multiplicações por segundo levaria 3 x 105 anos para efetuar as operações necessárias. Sendo assim, a regra de Cramer é inviável em função do tempo de computação para sistemas muito grandes e, portanto, o estudo de métodos mais eficientes torna-se necessário,

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 5 uma vez que, em geral, os casos práticos exigem a resolução de sistemas lineares de porte elevado. Antes, porém, faz-se necessário tratar da base teórica que fundamenta estes métodos.

Transformações elementares As transformações elementares constituem um conjunto de operações que podem ser efetuadas sobre as linhas ou colunas de uma matriz. No que se refere à resolução de sistemas de equações lineares, estas transformações são, normalmente, aplicadas apenas sobre as linhas da matriz dos coeficientes ou da matriz aumentada dependendo do método utilizado.

Li ← c × Li, c  , c ≠ 0, i = 1, 2,, n

1. Multiplicação de uma linha por uma constante não-nula. 2. Troca de posição entre duas linhas.

Li ⇆ Lj; i, j = 1, 2,, n; i ≠ j

3. Adição de um múltiplo de uma linha a outra linha,

Li ← Li + c × Lj, c  , c ≠ 0; i, j = 1, 2,, n; i ≠ j

Matrizes equivalentes Duas matrizes são ditas equivalentes quando é possível, a partir de uma delas, chegar à outra por meio de um número finito de transformações elementares.

Sistemas equivalentes Dois sistemas Ax = b e Ã.x = c se dizem equivalentes se possuem a mesma solução.

Matriz triangular (i) Superior: é uma matriz quadrada na qual todos os elementos abaixo da diagonal principal são nulos. (i) Inferior: é uma matriz quadrada na qual todos os elementos acima da diagonal principal são nulos.

Sistemas Triangulares É um sistema de equações lineares no qual a matriz dos coeficientes é triangular.

Teorema Seja [A | b] a matriz aumentada de um sistema de equações Ax = b, com determinante de A não nulo, e [T | c] uma matriz a ela equivalente. Sendo assim, os sistemas A.x = b e T.x = c possuem a mesma solução.

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 6

4.1 – Método de Gauss O Método de Gauss é um dos mais conhecidos e utilizados para a resolução de sistemas de equações lineares densos de pequeno a médio porte.

4.1.1 – Descrição do método A resolução de um sistema de equações lineares pelo método de Gauss envolve duas fases distintas. A primeira, chamada de fase de eliminação, consiste em efetuar transformações elementares sobre as linhas da matriz aumentada de um sistema de equações A.x = b até que, depois de n − 1 passos, se obtenha um sistema triangular superior, U.x = c, equivalente ao sistema dado. A segunda, chamada de fase de substituição, consiste em resolver o sistema triangular superior por meio de substituições retroativas.

baao baaa

Elemen. Transf.

baaa baaa baaa

3.x1 + 2.x2+ x4 = 3
9.x1 + 8.x2 – 3.x3 + 4.x4 = 6(4.1)
- 6.x1 + 4.x2 – 8.x3= -16

Para a descrição do método, seja resolver o sistema de equações lineares a seguir. 3.x1 - 8.x2 + 3.x3 - 8.x4 = 2

A e

Portanto, a matriz aumentada deste sistema de equações é

Depto de Computação – Instituto de Ciências Exatas e Biológicas – Universidade Federal de Ouro Preto

Prof. José Álvaro Tadeu Ferreira - Notas de aulas de Cálculo Numérico 7

(Parte 1 de 11)

Comentários