2- Resolução de Sistemas de Equações de+Equações+  · Um sistema de equações lineares,

  • View
    221

  • Download
    0

Embed Size (px)

Text of 2- Resolução de Sistemas de Equações de+Equações+  · Um sistema de equações lineares,

  • 1

    2- Resoluo de Sistemas de Equaes Lineares Um sistema de equaes lineares, com m equaes e n variveis, escrito geralmente como:

    =+++

    =

    =+++

    =+++

    mnmnmm

    nn

    nn

    bxaxaxa

    bxaxaxa

    bxaxaxa

    L

    MMMM

    L

    L

    2211

    22222121

    11212111

    onde ija so coeficientes mi L1=

    jx so varveis nj L1=

    ib so constantes mi L1=

    A resoluo de um sistema linear determina os valores de )1( njx j L= que

    satisfazem as m equaes. O sistema linear pode ser representado, usando a notao matricial, por: Ax = b onde

    A =

    mnmm

    n

    n

    aaa

    aaa

    aaa

    L

    MMM

    L

    L

    21

    22221

    11211

    a matriz dos coeficientes

    x =

    nx

    x

    x

    M

    2

    1

    a matriz coluna (vetor) das variveis

    b =

    mb

    b

    b

    M

    2

    1

    a matriz coluna (vetor) constante.

  • 2

    Vamos chamar de *x de vetor soluo e x uma soluo aproximada do sistema linear Ax = b. As situaes que podem ocorrer com relao ao nmero de solues de um sistema linear so:

    i) Soluo nica (sistema determinado); ii) Infinitas solues (sistema indeterminado); iii) No admite solues (sistema incompatvel);

    Vamos aprender mtodos numricos para encontrar a soluo nica de sistemas lineares

    n x n. Os mtodos numricos so divididos em dois grupos: mtodos diretos e mtodos iterativos.

    Mtodos diretos fornecem a soluo exata *x , no considerando erros de

    arredondamento, do sistema linear, aps um nmero determinado de operaes. Mtodos iterativos geram uma seqncia de vetor x(k), a partir de uma aproximao

    inicial x(0). Sob determinadas condies, esta seqncia converge para a soluo *x . 2-1 Mtodos diretos

    Todos os mtodos estudados nos 1 e 2 graus so diretos. A Regra de Cramer aplicada

    a resoluo de um sistema n x n envolve o clculo de (n+1) determinantes de ordem n. Se n for igual a 30 pode-se mostrar que sero efetuadas 31x30!x29 multiplicaes mais um nmero semelhante de adies. Assim um computador que efetuar um bilho de multiplicaes por segundo (109 ) levaria 7,667 . 1018 anos para efetuar as multiplicaes necessrias.

    Mtodos mais eficientes so necessrios, pois problemas prticos exigem a resoluo de sistemas lineares de grande porte. Os mtodos de eliminao de Gaus e Jordan sero estudados mais adiante.

    2-1-1 Resoluo de sistemas triangulares por substituio retroativa

    O sistema de equaes Tx = b, onde T uma matriz triangular superior, com elementos da diagonal diferentes de zero, escrito como:

    =

    =+

    =+++

    =+++

    nnnn

    nn

    nn

    bxa

    bxaxaxa

    bxaxaxaxa

    MMO

    L

    L

    22323222

    11313212111

  • 3

    Da ltima equao obtemos:

    nn

    n

    na

    bx =

    Da penltima equao obtemos:

    1,1

    ,111

    =

    nn

    nnnn

    na

    xabx

    Da equao n-k ; k = 2 ... n-2 obtemos:

    knkn

    nnknknknknknknknkn

    kna

    xaxaxabx

    ++++

    =

    ,

    ,22,11, L

    Finalmente

    11

    131321211

    a

    xaxaxabx nn

    =

    L

    Exemplo 1: Resolver o sistema:

    =

    =+

    =+

    =+

    3

    5

    35

    83

    w

    wz

    wzy

    wzyx

    Da ltima equao: w = -3; Substituindo na penltima equao w = -3; z-3 = -5 z = -5 +3 z = -2 Substituindo na 2 equao w = -3, z = -2; 5y (-2) + (-3) = 3 5y = 3+(-2)-(-3) = 4 y = 4/5

  • 4

    Substituindo na 1 equao w = -3, z = -2 e y= 4/5; 3x (4/5) + (-2) (-3) = 8 3x = 8 + (4/5) (-2) + (-3) 3x = 7+ 4/5 = 39/5 x = 39/15 = 13/5

    2-1-2 Mtodo da Eliminao de Gauss Triangularizao

    O mtodo da Eliminao de Gauss consiste em transformar o sistema de equaes lineares original num sistema triangular superior equivalente que tem soluo imediata, atravs do mtodo da substituio retroativa, como vimos acima. Operaes elementares produzem sistemas lineares equivalentes- que possuem a mesma soluo do sistema original. Operaes Elementares sobre um Sistema de Equaes Lineares:

    a) Trocar a posio das equaes; b) Multiplicar uma equao por uma constante no nula; c) Multiplicar uma equao por uma constante e adicionar a outra equao e, ento,

    substituir esta nova equao por uma das existentes. Descreveremos a seguir como o mtodo de eliminao de Gauss usa as operaes

    elementares para triangularizar um sistema de equaes lineares. Para que isto ocorra preciso supor que det A # 0, onde A a matriz dos coeficientes.

    Considerando que det A # o sempre possvel reescrever o sistema linear de forma que o elemento da posio a11 seja diferente de zero, usando somente a operao elementar de troca de linha.

    Seja a representao do sistema, com a11 # 0, pela matriz aumentada abaixo:

    )0(

    )0(2

    )0(1

    )0(11

    )0(2

    )0(1

    )0(11

    )0(21

    )0(21

    )0(1

    )0(12

    )0(11

    nnn

    n

    b

    b

    b

    aaa

    aaa

    aaa

    M

    L

    MMMM

    L

    L

    Vamos realizar a triangularizao por etapas: 1 ETAPA Colocar zero abaixo do elemento da diagonal )0(11a . Ao final da 1 etapa

    teremos a matriz aumentada abaixo:

  • 5

    )1(

    )1(2

    )0(1

    )1(11

    )1(2

    )1(11

    )1(21

    )0(1

    )0(12

    )0(11

    0

    0

    nn

    n

    b

    b

    b

    aa

    aa

    aaa

    M

    L

    MMMM

    L

    L

    Para isto subtramos da i-sima equao da 1 equao multiplicada por

    nia

    am ii L2,)0(

    11

    )0(1

    1 == . Os 1im so os multiplicadores e o elemento )0(

    11a chamado de piv

    da primeira etapa. Sendo assim, niLmLL iii L2,11 == , sero as linhas que substituiro

    as linhas antes do processo de eliminao da 1 etapa. 2 ETAPA Colocar zero abaixo do elemento da diagonal )1(22a . Ao final da 2 etapa

    teremos a matriz aumentada abaixo:

    )2(

    )2(3

    )1(2

    )0(1

    )2()2(3

    )2(3

    )2(33

    )1(2

    )1(23

    )1(22

    )0(1

    )0(13

    )0(12

    )0(11

    00

    00

    0

    nnnn

    n

    n

    n

    b

    b

    b

    b

    aa

    aa

    aaa

    aaaa

    M

    L

    MMMMM

    L

    L

    L

    Para isto subtramos da i-sima equao da 2 equao multiplicada por

    nia

    am ii L3,)1(

    22

    )1(2

    2 == . Os 2im so os multiplicadores e o elemento )1(

    22a chamado de piv

    da segunda etapa. Sendo assim, niLmLL iii L3,22 == , sero as linhas que

    substituiro as linhas antes do processo de eliminao da 2 etapa. (n-1) ETAPA Colocar zero abaixo do elemento da diagonal )1( 1,1

    n

    nna concluindo o

    processo de triangularizao. Ao final da (n-1) etapa, da ltima etapa, teremos a matriz aumentada abaixo:

    )1(

    )2(3

    )1(2

    )0(1

    )1(

    )2(3

    )2(33

    )1(2

    )1(23

    )1(22

    )0(1

    )0(13

    )0(12

    )0(11

    000

    00

    0

    n

    n

    n

    nn

    n

    n

    n

    b

    b

    b

    b

    a

    aa

    aaa

    aaaa

    M

    L

    MMMMM

    L

    L

    L

    Agora o sistema triangular superior e equivalente ao sistema de equaes lineares

    original.

  • 6

    O mtodo de eliminao efetua 3 2(4 3 7 )

    6

    n n n+ operaes. Para resolver o sistema

    triangular superior so efetuadas n2 operaes. Ento o total de operaes para se resolver

    um sistema linear pelo mtodo de Eliminao de Gauss 3 2(4 9 7 )

    6

    n n n+ . Assim um

    computador que efetuar um bilho de operaes por segundo (109 ) levaria 5.334.103 segundos = 1.482 horas para resolver um sistema de equaes lineares 20000x20000.

    Exemplo 2: Resolver o sistema de equaes lineares abaixo pelo mtodo de eliminao de

    Gauss:

    =+

    =+

    =++

    2234

    02

    1423

    zyx

    zyx

    zyx

    Trabalharemos com a matriz de coeficientes ampliada com o vetor constante

    2

    0

    1

    234

    211

    423

    1 ETAPA: Piv: )0(11a = 3

    31

    21 =m

    34

    31 =m

    12122 LmLL 13133 LmLL

    Assim teremos aps a 1 ETAPA

    32

    311

    322

    310

    310

    310

    423

  • 7

    2 ETAPA:

    Piv: 31)1(

    22 =a

    1

    31

    31

    32 ==m

    23233 LmLL

    Assim teremos aps a 2 ETAPA

    13

    11

    4003

    103

    10

    423

    Agora resolver bAx = equivalente a resolver :)2()2( bxA =

    14

    3131031

    1423

    =

    =

    =++

    z

    zy

    zyx

    Logo

    41=z

    274144101101 ===+= yzy

    39171)41(4)2

    7(213 ==++== xx

    {R.: x=3, y=-7/2, z=-1/4}

    2-1-2 Mtodo da Eliminao de Jordan Diagonalizao

    O mtodo da Eliminao de Jordan consiste em transformar o sistema de equaes

    lineares original num sistema diagonal equivalente que tem soluo imediata. Ele uma extenso do mtodo de eliminao gaussiana. O mtodo de eliminao de Jordan usado para reduzir a matriz aumentada para a forma

  • 8

    )1(

    )(2

    )(1

    )1(

    )1(21

    )0(11

    000

    00

    00

    n

    n

    n

    n

    n

    nn b

    b

    b

    a

    a

    a

    MMMMM

    L

    L

    O mtodo de eliminao de Jordan para diagonalizar um sistema de equaes

    lineares ser realizado de modo anlogo ao da eliminao gaussina.. Considerando que det A # o sempre possvel reescrever o sistema linear de forma

    que o elemento da