Sistema de equações lineares

  • View
    40

  • Download
    1

Embed Size (px)

DESCRIPTION

Sistema de equações lineares. Caracterização. Um sistema de m equações a n variáveis é é chamado sistema de equações lineares. Ele tem a forma genérica seguinte:. Solução. Um conjunto de n valores (x 1 , ..., x n ) verificando as equações do sistema é uma solução do sistema. - PowerPoint PPT Presentation

Text of Sistema de equações lineares

  • Sistema de equaes lineares

  • CaracterizaoUm sistema de m equaes a n variveis chamado sistema de equaes lineares. Ele tem a forma genrica seguinte:

  • SoluoUm conjunto de n valores (x1, ..., xn) verificando as equaes do sistema uma soluo do sistema.Um sistema cujo os valores dos coeficientes bn so iguais a 0 um sistema homogneo:

  • Caracterizao matricialO sistema pode ser escrita sobre a forma de um produto de matrizes:onde as matrizes so definidas por:

  • Combinao linearA combinao linear de equaes a soma dessas equaes multiplicado por coeficientes reais:a1eq1+a2eq2+...+aneqn onde ai0, i{1,...,n} uma combinao linear de eq1, eq2, ..., eqn.Em relao com as variveis envolvidas nas equaes, uma equao linear, combinao linear entre as outras equaes no introduz novas relaes entre as variveis.

  • Sistemas equivalentesNum sistema de equaes lineares independentes, se uma equao trocada por uma combinao linear dela mesma e outras equaes do sistema, o novo sistema equivalente o primeiro. Os dois sistemas tm a mesma soluo.

  • Sistemas equivalentesNum sistema, se uma equao combinao linear das outras, ele equivalente ao sistema sem essa equao:

  • Equaes e variveisUm sistema de m equaes a n variaveis:Tem uma soluo unica se ele pode ser reduzido a um sistema de n equaes independentes a n variveis.Tem uma infinidade de solues, se ele equivalente a um sistema de m equaes independentes com m
  • DeterminanteUm determinante um nmero associado a um matriz quadrada (mesmo nmero de linha e coluna).A definio do determinao envolve a noo de permutao. O determinante de uma matriz A (aij o coeficiente da i-sima linha e j-sima coluna) , onde an so elementos distintos de (1,...,n) e k o nmero de permutaes para passar de (1,...,n) para (a1,..., an):

  • Calculo do determinante, caso 2x2 e 3x3O calculo do determinante 2x2:

    O calculo do determinante 3x3 feito da forma seguinte:

    Det A= =

  • Determinante, caso nxnO desenvolvimento de Laplace permite o calculo do determinante da forma seguinte:

    Onde Dij o determinante da submatriz obtido de A retidando-se a i-sima linha e j-sima coluna e multiplicado por (-1)i+j. O nmero i pode ser qualquer nmero de {1,...,n}. Esse princpio funciona para qualquer linha ou coluna.

  • Determinante, caso nxnO calculo do determinante pode ser implementado com um procedimento recursivo. O calculo de um determinante nxn determinado a partir de determinantes (n-1)x(n-1).O preo do clculo de um determinante elevado. Considerando a formula da definio, so necessrias n!(n-1)+(n!-1) ou seja n!n-1 operaes para um determinante de dimenso n: (n!-1) somas de n!(n-1) produtos, sem considerar os elementos anexos necessrios (posio de memoria, sinal, etc).

  • Determinante, um algoritmoO calculo feito usando os coeficientes da primeira linha.Determinante(m) // m: matrizse dim(m)=2 resultado=m[0][0].m[1][1]-m[1][0].m[0][1]se dim(m)=1 resultado=m[0][0]Se dim(m)>2 resultado=0 i de 1 a dim(m) construr a submatriz de m sem a primeira linha e a i-sima coluna (subm)resultado=resultado+(-1)i.m[0][i].Determinante(subm)

  • Determinante e sistemaSe um sistema de n equaes lineares a n variveis tem um determinante diferente de 0: det A0, as equaes do sistema so independentes.Nesse caso, o sistema tem uma soluo nica. Em caracterizao matricial, essa soluo escreve-se:

    onde A-1 a matriz inversa da matriz A.

  • Determinante e matriz inversaSe o determinante de uma matriz no nulo, a matriz inversa pode ser calculada.

    Onde Dij o determinante da matriz formada a partir da matriz A retirando a i-sima linha e j-sima coluna.

  • Formula de CramerPela formula de Cramer, se o determinante do sistema no nulo, o valor soluo da varivel xi dado pela formula seguinte:

    O numerator da frao o determinante da matriz formada da matriz A do sistema onde a coluna dos coeficientes de xi so subsitudos pelos termos constantes bi.

  • Exemplo

  • Custo da formula de CramerPara resolver um sistema de n equaes a n variveis, pela formula de Cramer precisam ser calculados n+1 determinante de ordem n (n linhas, n colunas).O custo da resoluo desse sistema de: (n!n-1)(n+1) operaes.Para 10 variaveis: 399167989

  • Eliminao GaussianaA eliminao Gaussiana usa a propriedade de equivalncia de sistema para eliminar progressivamente as variveis ate chegar a uma equao de uma varivel.

  • Sistema triangularNo novo sistema, podemos determinar:

    O sistema chamado sistema triangular e a matriz associada uma matriz triangular. Se fala tambm de triangular superior ou inferior para caracterizar a posio dos coeficientes no nulos.

  • Eliminao Gaussiana e determinanteO determinante de um sistema triangular o produto dos termos da diagonal.

    Em um determinante, adicionar os termos (ou os termos multiplicado por um fator) de qualquer linha (resp. coluna) a qualquer outra linha (resp. coluna) no muda o valor do determinante.

  • MtodoEscolhe uma das equaes (i-sima) com o coeficiente (ai1) de x1 no nulo. Esse coeficiente chamado de pivot (ou pivot de Gauss).Adicionar a cada uma das equaes restantes (j, ji), a primeira equao multiplicada por: -aj1/ai1Aplicar de novo o algoritmo com o sub-sistema de n-1 variveis ate chegar a uma equao de uma varivel.

  • Exemplo

  • MatrizO processo pode ser aplicado com matrizes. Nesse caso, se considera a matriz aumentada com as constantes da matriz do sistema:

    E as combinaes lineares entre as equaes so feitas entre as linhas de coeficientes.

  • Exemplo com matriz

  • ExerccioSoluo: x1=-1, x2=0, x3=1 e x4=2

  • Custo da eliminao GaussianaPara eliminar o primeiro termo das n-1 equaes de um sistema a n equao, precisamos de n-1 divises, (n-1)(n+1) multiplicaes e (n-1)(n+1) adies: 2n2+n-3. Para eliminar os termos ate a ultima equao precisamos de operaes, da ordem de 2n3/2.A resoluo do sistema triangular necessita: n divises, n(n-1)/2 multiplicaes e n(n-1)/2 adies.

  • Velocidade da resoluoUma das razes de escolher uma algoritmo no lugar de um outro em geral baseado sobre a relao entre velocidade e preciso.No caso da resoluo de sistemas lineares, a formula de Cramer precisa de muito mais operaes que a eliminao Gaussiana.

  • Estratgia de pivoteamentoResoluo do sistema seguinte usando sucessivamente 0.004 e 0.423 como pivot e calculando usando somente 4 algarismos significativos:

    A soluo do sistema e (10,1). Com 0.004 como pivot achamos (12.5,0.9994) e com 0.423 achamos (10,1).

  • Estratgia de pivoteamentoNo caso geral, para diminuir os erros de arredondamento, prefervel usar como pivot o maior coeficiente em valor absoluto da varivel a eliminar nas equaes do sistema.

  • Eliminao Gaussiana, algoritmon: numero de variveis, m: matriz aumentadaEliminacao_gauss(n, m)para i de 1 a npara j de i a n, procure o coeficiente maior em valor absolute: linha maxtroca a linha max com a linha i de mpara j de i+1 a n, para k de i a n+1, subtrai m[j][i]/m[i][i] de m[j][k]

  • Solues particularesCertas situaes precisam de determinar as solues de sistemas onde somente os termos constantes (bi) mudam:soluo de:

    e soluo de:

  • Solues particularesNesses casos, mais eficiente de triangular o sistema uma vez e resolve-lo com os diversos valores dos termos constantes (bi). Nesse caso uma segunda matriz necessria para calcular os termos constantes do sistema triangular em fones dos coeficientes de origem.

  • Solues particularesNesse caso, a matriz coluna dos termos constantes considerada como o produto da matriz identidade como essa matriz coluna. As transformaes operadas pela triangularizao sero aplicadas matriz identidade e no matriz coluna dos termos constantes.

  • Matriz InversaSe o processo de transformao do sistema continua ate obter um sistema cuja matriz a matriz identidade, a matriz de transformao dos termos constantes a matriz inversa da matriz do sistema inicial:

  • Exemplo

  • Erros de aproximaoOs erros de arredondamento tm um papel importante na soluo de sistemas de equaes lineares, principalmente por conto do grande nmero de calculo a ser efetuados.A um efeito de condensao pivotal no caso da eliminao gaussiana. Cada calculo depende dos resultados anteriores.

  • Avaliao dos errosUma forma de avaliar o erro trocar as variveis nas equaes pelos valores determinados e comparar os resultados com os termos constantes:

    Sistema: solues:

    Trocando nas equaes:

  • Avaliao dos errosUm pequeno erro sobre os resultados conduz a considerar que os valores das variveis determinados so boas aproximaes dos resultados exatos.Existem casos nos quais no podemos afirmar isso.

  • Sistema mal condicionadoConsiderando o sistema seguinte:

    Uma soluo como x1=100, x2=-98 uma soluo aceitvel do ponto de vista do critrio precedente, porm ela longe da soluo exata (70,-68).

  • Sistema mal condicionadoUm sistema de equaes que pode ser satisfeito por solues erradas um sistema mal condicionado.Do ponto de vista grfico, no caso da dimenso 2, o sistema mal condicionado quando as duas retas representando as equaes so prximas:

  • Sistema mal condicionadoUm sistema mal condicionado quando seu determinante prximo de zero.O que significa, um determinante prximo de zero ? Como multiplicando qualquer equao por um fator no muda a soluo do sistema, enquanto multiplica o determinante por esse fator, falar de um valor pequeno do determinante no significa nada.

  • Sistema mal condicionadoPara determinar se um sistema mal condicionado, existem duas possibilidades:O determinante normalizado