86
Cálculo Numérico Raízes de Equações Não Lineares Professores Marcelo Alves de Barros Bruno C. N. Queiroz J. Antão B. Moura José Eustáquio R. de Queiroz Ulrich Schiel

Calculo Numerico: Raizes UFCG

Embed Size (px)

Citation preview

  • Clculo Numrico

    Razes de Equaes No Lineares

    Professores Marcelo Alves de Barros

    Bruno C. N. Queiroz

    J. Anto B. Moura

    Jos Eustquio R. de Queiroz

    Ulrich Schiel

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodos Iterativos para a Obteno

    de Zeros Reais de Funes

    Bisseco (ou de Bolzano)

    Falsa Posio

    Ponto Fixo

    x1

    Newton-Raphson

    Secante

    2

    x1 = (a+b)/2

    x1 = ( a f(b) - b f(a) ) / (f(b) - f(a))

    xk+1 = g(xk), x = g(x)

    xk+1 = [xk-1 .f(xk) xk . f(xk-1)]/[f(xk) - f(xk-1)]

    xk+1 = xk f(xk)/f(xk)

  • Clculo Numrico

    Razes de Equaes No Lineares

    1. Define-se o intervalo inicial a partir da aplicao do teorema de Bolzano (encontrar a e b tal que f(a)*f(b) < 0

    2. Calcula-se o ponto mdio de a e b x1 = (a+b)/2

    3. Calcula-se um erro absoluto f(x1) ou um erro relativo |(xk xk+1)/xk| para verificar se x1 uma aproximao aceitvel da raiz da equao.

    Mtodo da Bisseco (ou de Bolzano) Dada uma funo f(x) contnua no intervalo [a,b]

    onde existe uma raiz nica , possvel determinar

    tal raiz subdividindo sucessivas vezes o intervalo que

    a contm pelo ponto mdio de a e b.

    4. Compara-se o erro desta aproximao com uma tolerncia dada (se erro de x1 < tol)

    Se verdadeiro x1 a raiz procurada (raz aceitvel)

    Caso contrrio define-se um novo intervalo para calcular x2

    5) Calcula-se o produto f(a)*f(x1) para determinar em qual dos subintervalos - [a, x1] ou [x1 , b] - se encontra a raiz

    Verifica-se se f(a)*f(x1) < 0

    Se verdadeiro (a, x1) (Logo a = a e b = x1)

    Caso contrario (x1 , b) (Logo a = x1 e b = b)

    Volta-se ao passo 2 e repete-se os passos 2 a 5 at que o mtodo atenda condio de parada

    |f(x)| tolerncia |(xk xk+1)/xk| tolerncia

  • Clculo Numrico

    Razes de Equaes No Lineares

    x a = a0

    f(x)

    b = b0

    x1 = (a + b)/2

    x1

    x a = a1

    f(x)

    x1 = b1

    x2 = (a + x1)/2

    x2

    x

    f(x)

    x1 = b2

    x3 = (x2 + x1)/2

    x2 = a2 x3

    Repete-se o processo at que o valor de x

    atenda s condies de parada (tolerncia).

    Tolerncia (aproximao de zero): um nvel

    de preciso exigido pela aplicao do clculo

    numrico. Depende do equipamento de clculo

    e principalmente do cliente do clculo.

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; a0 := a; b0 := b; x0 := a;

    xk+1 := (ak + bk)/2;

    while critrio de convergncia no satisfeito and k L

    if f(ak)f(xk+1) < 0 then /* raiz em [ak , xk+1] */

    ak+1 := ak; bk+1 := xk+1; else /* raiz em [xk+1, bk] */

    ak+1 := xk+1; bk+1 := bk ; endif

    k := k +1; xk+1 := (ak + bk)/2;

    endwhile

    if k > L

    convergncia falhou

    endif

    Mtodo da Bisseco (ou de Bolzano) Dada uma funo f(x) contnua no intervalo [a,b] onde existe uma raiz nica , possvel determinar tal raiz

    subdividindo sucessivas vezes o intervalo que a contm pelo ponto mdio de a e b.

  • Clculo Numrico

    Razes de Equaes No Lineares

    6

    Oficina

    Considere que temos um sistema computacional de aritmtica de

    ponto no flutuante de quatro dgitos, sem circuito arredondador,

    com base decimal e com acumulador de preciso dupla, para

    fazer clculo numrico das razes da funo abaixo:

    1. Encontre uma raiz desta funo com 3 iteraes do mtodo

    da Biseco, usando este computador.

    2. Comente sobre os erros produzidos neste clculo numrico

    f(x) = 1,7 x3 70,85x 1,0934

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 6:

    Resgatando o Exemplo 5, no qual f(x) = xlogx 1

    7

    Verificou-se que [2, 3]

    g(x)

    x 1 2 3 4

    h(x) y

    5 6

    2 3

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 6:

    Considerando o mtodo da bisseco e adotando [2, 3] como intervalo inicial

    8

    x1 = (2 + 3)/2 = 2,5

    f(2) = -0,3979 < 0

    f(3) = 0,4314 > 0

    f(2,5) = -5,15.10-3 < 0

    [2,5 , 3] a1 = x1 = 2,5

    b1 = b0 = 3

    x2 = (2,5 + 3)/2 = 2,75

    f(2,5) = -5,15.10-3 < 0

    f(3) = 0,4314 > 0

    f(2,75) = 0,2082 > 0

    [2,5 , 2,75] a2 = a1 = 2,5

    b2 = x2 = 2,75

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 6:

    9

    x3 = (2,5 + 2,75)/2 = 2,625

    f(2,5) = -5,15.10-3 < 0

    f(2,75) = 0,2082 > 0

    f(2,625) = 0,1002 > 0

    [2,5 , 2,625] a3 = a2 = 2,5

    b3 = x3 = 2,625

    x4 = (2,5 + 2,625)/2 = 2,5625

    f(2,5) = -5,15.10-3 < 0

    f(2,625) = 0,1002 > 0

    f(2,5625) = 0,0472 > 0

    [2,5 , 2,5625] a3 = a2 = 2,5

    b3 = x4 = 2,5625

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 7:

    Considere-se f(x) = x3 x 1

    10

    x 1 2 3 4

    y

    5 0 -1 -2 -3 -4

    1

    2

    3

    4

    -4

    -3

    -2

    -1

    Intervalo inicial atribudo: [1, 2]

    tol = 0,002

    f(a0) = -1

    f(b0) = 5

    f(x) = 3x2 1

    f(a0) * f(b0) = -5 < 0

    Sinal da derivada constante

    (f(a0) = 2 e f(b0) = 11)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 7

    11

    Clculo da 1 aproximao

    x1 = (a0 + b0)/ 2 = (1 + 2)/2 = 1,5

    f(x1) = 1,53 1,5 1 = 0,875

    Teste de Parada

    |f(x1)| =|0,875| = 0,875 > 0,002

    Escolha do novo intervalo

    f(a0).f(x1) = (-1).0,875 = -0,875 logo: a1 = a0 = 1,0 e b1 = x1 = 1,5

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 7

    12

    Clculo da oitava aproximao x8 = (1,32032 + 1,32813) /2 = 1,32423 Teste de parada !f(x8)! = ! 0,002! = 0,002

    k ak bk f(ak) f(bk) xk+1 f(xk+1 )

    0 1,0000000 2,0000000 -1,000000 5,000000 1,50000000 0,875000

    1 1,0000000 1,5000000 -1,000000 0,875000 1,25000000 -0,296875

    2 1,2500000 1,5000000 -0,296875 0,875000 1,37500000 0,224609

    3 1,2500000 1,3750000 -0,296875 0,224609 1,31250000 -0,051514

    4 1,3125000 1,3750000 -0,051514 0,224609 1,34375000 0,082611

    5 1,3125000 1,3437500 -0,051514 0,082611 1,32812500 0,014576

    6 1,3125000 1,3281250 -0,051514 0,014576 1,32031250 -0,018711

    7 1,3203125 1,3281250 -0,018700 0,014576 1,32421875 -0,002128

    tol = 0,002

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo da Falsa Posio

    Dada uma funo f(x) contnua no intervalo [a,b] onde existe

    uma raiz nica, possvel determinar tal raiz a partir de

    subdivises sucessivas do intervalo que a contm,

    substituindo f(x) no intervalo [a,b] de cada iterao por uma

    reta e tomando como aproximao da raiz a interseco da

    reta com o eixo das abscissas.

    MB: calcula a mdia aritmtica entre a e b, e

    MPF: calcula a mdia ponderada entre a e b com pesos

    lf(b)l e lf(a)l, respectivamente.

    13

  • Clculo Numrico

    Razes de Equaes No Lineares

    MPF: calcula a mdia ponderada entre a e b com

    pesos l(b)l e lf(a)l, respectivamente.

    X = ( a lf(b)l + b lf(a)l ) / (lf(b)l + lf(a)l)

    = ( a f(b) - b f(a) ) / (f(b) - f(a))

    Observe que f(a) e f(b) tm sinais opostos.

    14

  • Clculo Numrico

    Razes de Equaes No Lineares

    Definio do intervalo inicial

    Atribui-se [a,b] como intervalo inicial a0 = a

    b0 = b

    Condies de aplicao

    f(a)*f(b) < 0

    Sinal da derivada constante

    15

  • Clculo Numrico

    Razes de Equaes No Lineares

    Definio dos subintervalos

    Subdivide-se o intervalo pelo ponto de interseco da reta que liga f(a) a f(b) e o eixo das abscissas

    Verifica-se se x1 uma aproximao da raiz da

    equao ()

    Se verdadeiro x1 a raiz procurada

    Caso contrrio define-se um novo intervalo

    16

  • Clculo Numrico

    Razes de Equaes No Lineares

    Determina-se em qual dos subintervalos -

    [a0, x1] ou [x1, b0] - se encontra a raiz

    Calcula-se o produto f(a)*f(x1)

    Verifica-se se f(a)*f(x1) < 0

    Se verdadeiro (a0, x1) Logo: a1 = a0 e b1 = x1

    Caso contrario (x1, b0) Logo a1 = x1 e b1 = b0)

    17

    Definio do novo intervalo

    Repete-se o processo at que o valor de x atenda s condies de parada.

  • Clculo Numrico

    Razes de Equaes No Lineares

    18

    Anlise grfica

    x a = a0

    f(x)

    b = b0

    x1 = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|)

    x1

    Repete-se o processo at que o

    valor de x atenda s condies de parada.

    x a = a1

    f(x)

    b1 = x1

    x2 = (a|f(x1)| + x1|f(a)| )/ (|f(x1)| + |f(a)|)

    x2

    x a = a2

    f(x)

    b2 = x1

    x3 = (a|f(x2)| + x2|f(a)| )/ (|f(x2)| + |f(a)|)

    x2

  • Clculo Numrico

    Razes de Equaes No Lineares

    19

    Condies de parada

    Se os valores fossem exatos

    f(x) = 0

    (xk xk+1)/xk = 0

    No o sendo

    |f(x)| tolerncia

    |(xk xk+1)/xk| tolerncia

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; a0 := a; b0 := b; x0 := a; F0 := f(a0); G0 := f(b0);

    xk+1 := ak - Fk(bk ak)/(Gk Fk); ou xk+1 := (akGk- bkFk)/(Gk Fk);

    while critrio de convergncia no satisfeito and k L if f(ak)f(xk+1) 0 then /* raiz em [ak , xk+1] */

    ak+1 := ak; bk+1 := xk+1; else /* raiz em [xk+1, bk] */

    ak+1 := xk+1; bk+1 := bk ; endif

    k := k +1; xk+1 := ak - Fk(bk ak)/(Gk Fk);

    endwhile

    if k > L

    convergncia falhou

    endif

    20

  • Clculo Numrico

    Razes de Equaes No Lineares

    Utilizando o mtodo da falsa posio e adotando [a0, b0] = [2, 3] como intervalo inicial

    21

    1 iterao

    a0 = 2 b0 = 3

    f(a0) = -0,3979 < 0

    f(b0) = 0,4314 > 0

    x1 = [2.0,4314 3.(-0,3979)]/[0,4314 (-0,3979)] =

    = 2,4798

    f(x1) = -0,0219 < 0

    Exemplo 8: Considerando f(x) = xlogx 1 (Exemplo 6)

  • Clculo Numrico

    Razes de Equaes No Lineares

    22

    Exemplo 8:

    2 iterao

    a1 = x1 = 2,4798 b1 = b0 = 3

    f(a1) = -0,0219 < 0

    f(b1) = 0,4314 > 0

    x2 = [2,4798.0,4314 3.(-0,0219)]/[0,4314 (-0,0219)] = = 2,5049

    f(x2) = -0,0011 < 0

  • Clculo Numrico

    Razes de Equaes No Lineares

    23

    Exemplo 8:

    3 iterao

    a2 = x2 = 2,5049 b1 = b0 = 3

    f(a2) = -0,0011 < 0

    f(b2) = 0,4314 > 0

    x3 = [2,5049.0,4314 3.(-0,0011)]/[0,4314 (-0,0011)] = = 2,5061

    f(x3) = -7,0118.10-5 < 0

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 9:

    Resgatando a funo do Exemplo 7, f(x) = x3 x 1

    24

    x 1 2 3 4

    y

    5 0 -1 -2 -3 -4

    1

    2

    3

    4

    -4

    -3

    -2

    -1

    Intervalo inicial atribudo: [1, 2]

    tol = 0,002

    f(a0) = -1

    f(b0) = 5

    f(x) = 3x2 1

    f(a0) * f(b0) = -5 < 0

    Sinal da derivada constante (f(a0) = 2 e f(b0) = 11)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 9

    25

    Clculo da 1 aproximao

    x1 = [(a0.f(b0) - b0.f(a0)] / [f(b0) - f(a0)] = [1.5 2.(-1)]/[5 (-1)] = 1,166667

    f(x1) = 1,1666673 1,166667 1 = -0,578703

    Teste de Parada

    |f(x1)| =|-0,578703| = 0,578703 > 0,002

    Escolha do novo intervalo

    f(a0).f(x1) = (-1).(-0,578703) = 0,578703 logo: a1 = x1 = 1,166667 e b1 = b0 = 2

  • Clculo Numrico

    Razes de Equaes No Lineares

    26

    Clculo da oitava aproximao x8 = (1,32032 + 1,32813) /2 = 1,32423 Teste de parada !f(x8)! = ! 0,002! = 0,002

    k ak bk f(ak) f(bk) xk+1 f(xk+1 )

    0 1,00000000 2,00000000 -1,00000000 5,00000000 1,16666667 -0,57870370

    1 1,16666667 2,00000000 -0,57870370 5,00000000 1,25311203 -0,28536303

    2 1,25311203 2,00000000 -0,28536303 5,00000000 1,29343740 -0,12954209

    3 1,29343740 2,00000000 -0,12954209 5,00000000 1,31128102 -0,05658849

    4 1,31128102 2,00000000 -0,05658849 5,00000000 1,31898850 -0,02430375

    5 1,31898850 2,00000000 -0,02430375 5,00000000 1,32228272 -0,01036185

    6 1,32228272 2,00000000 -0,01036185 5,00000000 1,32368429 -0,00440395

    7 1,32368429 2,00000000 -0,00440395 5,00000000 1,32427946 -0,00186926

    tol = 0,002

  • Clculo Numrico

    Razes de Equaes No Lineares

    Oficina

    1. Crie uma funo Polinomial f(x) de grau maior que 2, encontre

    uma raiz desta funo usando 3 iteraes do mtodo da

    Biseco e determine o erro absoluto e erro relativo deste

    resultado

    2. Faa o mesmo com o mtodo da Falsa Posio.

    27

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo da Falsa Posio Modificado

    Dada uma funo f(x) contnua no intervalo [a,b], o qual contm uma

    raiz nica, possvel determinar tal raiz a partir de subdivises

    sucessivas do intervalo que a contm, evitando, ao mesmo tempo,

    que as aproximaes geradas pela frmula de iterao se

    aproximem da raiz por um nico lado.

    28

  • Clculo Numrico

    Razes de Equaes No Lineares

    Definio do intervalo inicial

    Atribui-se [a,b] como intervalo inicial a0 = a

    b0 = b

    Condies de aplicao

    f(a)*f(b) < 0

    Sinal da derivada constante

    29

  • Clculo Numrico

    Razes de Equaes No Lineares

    Definio dos subintervalos

    Subdivide-se o intervalo pelo ponto de interseco da reta que liga f(a) a f(b) e o eixo das abscissas

    Verifica-se se x1 uma aproximao da raiz da

    equao ()

    Se verdadeiro x1 a raiz procurada

    Caso contrrio define-se um novo intervalo

    30

  • Clculo Numrico

    Razes de Equaes No Lineares

    Determina-se em qual dos subintervalos - [a0, x1]

    ou [x1, b0] - se encontra a raiz

    Calcula-se o produto f(a)*f(x1)

    Verifica-se se f(a)*f(x1) < 0

    Se verdadeiro (a0, x1) Logo: a1 = a0 e b1 = x1

    Caso contrario (x1, b0) Logo a1 = x1 e b1 = b0)

    31

    Definio do novo intervalo

    Repete-se o processo at que o valor de x atenda s condies de parada.

  • Clculo Numrico

    Razes de Equaes No Lineares

    32

    Anlise grfica

    x a = a0

    f(x)

    b = b0

    x1 = (a|f(b)| + b|f(a)| )/ (|f(b)| + |f(a)|)

    x1

    Repete-se o processo at que o

    valor de x atenda s condies de parada.

    x a = a1

    f(x)

    b1 = x1

    x2 = (a|f(x1)| + x1|f(a)| )/ (|f(x1)| + |f(a)|)

    x2

    x2

    f(a1)/2

  • Clculo Numrico

    Razes de Equaes No Lineares

    33

    Condies de parada

    Se os valores fossem exatos

    f(x) = 0

    (xk xk+1)/xk = 0

    No o sendo

    |f(x)| tolerncia

    |(xk xk+1)/xk| tolerncia

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; a0 := a; b0 := b; x0 := a; F0 := f(a0); G0 := f(b0); xk+1 := ak - Fk(bk ak)/(Gk Fk); while critrio de convergncia no satisfeito and k L if f(ak)f(xk+1) 0 then /* raiz em [ak , xk+1] */ ak+1 := ak; bk+1 := xk+1; Gk+1 = f(xk+1) if f(xk)f(xk+1) > 0 then Fk+1 = Fk/2 endif else /* raiz em [xk+1, bk] */ ak+1 := xk+1; bk+1 := bk ; Fk+1 = f(xk+1) if f(xk)f(xk+1) > 0 then Gk+1 = Gk/2 endif endif k := k +1; xk+1 := ak - Fk(bk ak)/(Gk Fk); endwhile if k L xk+1 uma aproximao aceitvel para a raiz endif

    34

  • Clculo Numrico

    Razes de Equaes No Lineares Oficina 3

    Dada a funo :

    A. Determine o intervalo em x que contm pelo menos uma raiz de f(x)

    (graficamente ou aritmeticamente usando o Teorema de Bolzano);

    B. Partindo-se desse intervalo, utilize o mtodo da falsa posio para

    determinar o valor dessa raiz aps 3 iteraes.

    C. Qual o erro no seu resultado final?

    35

    4sen 2 xxxf

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo do Ponto Fixo (MPF)

    Dada uma funo f(x) contnua no intervalo [a,b] onde existe uma

    raiz nica, f(x) = 0, possvel transformar tal equao em uma

    equao equivalente x = g(x) e, a partir de uma aproximao

    inicial x0, gerar uma seqncia {xk} de aproximaes para pela

    relao xk+1 = g(xk), uma vez que g(x) tal que f() = 0 se e

    somente se g() = .

    36

    xk+1 = g(xk), x = g(x)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo do Ponto Fixo (MPF)

    Implicao de tal procedimento:

    37

    Problema de determinao de um zero de f(x)

    Problema de determinao de um ponto fixo de g(x)

    funo de

    iterao

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 9:

    Seja a equao x2 + x 6 = 0 . Funes de iterao possveis:

    g1(x) = 6 - x2

    g2(x) = 6 - x2

    g3(x) = 6/x 1

    g4(x) = 6/(x + 1)

    38

    Dada uma equao do tipo f(x) = 0, h para tal equao mais de uma funo de iterao g(x), tal que:

    f(x) = 0 x = g(x)

  • Clculo Numrico

    Razes de Equaes No Lineares

    39

    Anlise grfica da Convergncia

    x

    {xk} quando k inf

    y

    x1

    g(x)

    x0

    y = x

    x2

    Situao 1

  • Clculo Numrico

    Razes de Equaes No Lineares

    40

    Anlise grfica da Convergncia

    x

    {xk} quando k inf

    y

    x1

    g(x)

    x0

    y = x

    x2

    Situao 2

    x3

  • Clculo Numrico

    Razes de Equaes No Lineares

    41

    Anlise grfica da Convergncia

    x

    y

    x1

    g(x)

    x0

    y = x

    x2

    Situao 3

    {xk}

  • Clculo Numrico

    Razes de Equaes No Lineares

    42

    Anlise grfica da Convergncia

    x

    y

    x1

    g(x)

    x0

    y = x

    x2

    Situao 4

    {xk}

    x3

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 10:

    Resgatando o Exemplo 9, no qual x2 + x 6 = 0 :

    43

    No h necessidade de uso de mtodo numrico

    para a determinao das razes 1 = -3 e 2 = 2

    Aproveitamento do Exemplo 9 puramente para

    demonstrao numrica e grfica da convergncia

    ou no do processo iterativo

    Seja a raiz 2 = 2 e g1 (x) = 6 - x2

    Considere-se x0= 1,5 e g(x) = g1 (x)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 10:

    A partir de x0 = 1,5 e g(x) = g1 (x) :

    44

    x1 = g(x0) = 6 1,52 = 3,75

    x2 = g(x1) = 6 3,752 = -8,0625

    x3 = g(x2) = 6 (-8,0625)2 = -59,003906

    Conclui-se que {xk} no convergir para 2 = 2

    x4 = g(x3) = 6 (-59,003906)2 = -3475,4609

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 10:

    Anlise Grfica:

    45

    x 2

    y

    x1

    g(x)

    x0

    y = x

    {xk} 2

    x2 1

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 10:

    Seja ainda a raiz 2 = 2, g2 (x) = 6 - x e x0 = 1,5

    46

    x1 = g(x0) = 6 1,5 = 2,121320343

    x2 = g(x1) = 6 2,121320343 = 1,969436380

    x3 = g(x2) = 6 1,969436380 = 2,007626364

    Conclui-se que {xk} tende a convergir para 2 = 2

    x4 = g(x3) = 6 2,007626364 = 1,998092499

    x5 = g(x4) = 6 1,998092499 = 2,000476818

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 10: Anlise Grfica

    47

    g(x)

    x

    y y = x

    2

    x1

    x0

    x2 {xk} 2 quando k inf

  • Clculo Numrico

    Razes de Equaes No Lineares

    48

    TEOREMA 2:

    Sendo uma raiz de f(x) = 0, isolada em um intervalo I centrado em e g(x) uma funo de iterao para f(x) = 0. Se

    1. g(x) e g(x) so contnuas em I

    2. |g(x)| M < 1, x I e

    3. x1 I

    ento a seqncia {xk} gerada pelo processo iterativo xk+1 = g(xk) convergir para .

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 11:

    Resgatando o Exemplo 10, verificou-se que:

    g1 (x) gerao de uma seqncia divergente de 2=2

    g2 (x) gerao de uma seqncia convergente p/ 2=2

    49

    g1 (x) = 6 - x2 e g1 (x) = - 2x

    contnuas em I

    |g1 (x)| < 1 |-2x| < 1 - < x <

    No existe um intervalo I centrado em 2=2, tal que |g(x)| < 1, x I g1 (x) no satisfaz a condio 2 do Teorema 2 com relao a 2=2 .

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 11:

    50

    g2 (x) = 6 - x e g2 (x) = - (1/2 ) 6 - x

    g2 (x) contnua em S = {x R | x 6}

    g2 (x) contnua em S = {x R | x < 6}

    |g2 (x)| < 1 |1/2 6 - x | < 1 x < 5,75

    possvel obter um intervalo I centrado em 2=2, tal que todas as condies do Teorema 2 sejam

    satisfeitas.

  • Clculo Numrico

    Razes de Equaes No Lineares

    51

    Critrios de parada

    Se os valores fossem exatos

    f(xk) = 0

    |xk xk-1| = 0

    No o sendo

    |f(xk)| tolerncia

    |xk xk-1| tolerncia

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; x0 := x;

    while critrio de interrupo no satisfeito and k L

    k := k +1;

    xk+1 := g(xk);

    endwhile

    52

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo Completo (1) Seja f(x)= 0 e a equao Equivalente x=g(x)

    Dados: x0 (aprox. inicial) e 1 e 2 (precises) Supor que as hipteses do Teorema 2 foram satisfeitas

    (2) Se: lf(x0)l < 1, Ento: x= x0. FIM (3) Seno: k = 0; NI = 1; (4) xk+1 = g(xk);

    (5) Se ( lf(xk+1)l < 1 ou l xk+1 xk l < 2 ou NI >L ) Ento x= xk+1. FIM (6) Xk = xk+1 ; NI = NI+1 Volta para (4)

    53

    X= raiz aproximada

    (NI = No. de iteraes)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo de Newton-Raphson

    Dada uma funo f(x) contnua no intervalo [a,b] onde

    existe uma raiz nica, possvel determinar uma

    aproximao de tal raiz a partir da interseo da tangente

    curva em um ponto x0 com o eixo das abscissas.

    x0 - atribudo em funo da geometria do mtodo e do

    comportamento da curva da equao nas proximidades da

    raiz.

    54

  • Clculo Numrico

    Razes de Equaes No Lineares

    Consideraes Iniciais

    Mtodo do Ponto Fixo (MPF)

    Uma das condies de convergncia que |g(x)| M < 1, x I , onde I um intervalo centrado na raiz

    A convergncia ser tanto mais rpida quanto menor for |g(x)|

    O mtodo de Newton busca garantir e acelerar a convergncia do MPF

    Escolha de g(x), tal que g() = 0, como funo de iterao

    55

  • Clculo Numrico

    Razes de Equaes No Lineares

    Consideraes Iniciais

    Dada a equao f(x) = 0 e partindo da forma geral para g(x)

    g(x) = x + A(x)f(x)

    busca-se obter a funo A(x) tal que g() = 0

    g(x) = x + A(x)f(x)

    g(x) = 1 + A(x)f(x) + A(x)f(x)

    g() = 1 + A()f() + A()f()

    g() = 1 + A()f() 56

  • Clculo Numrico

    Razes de Equaes No Lineares

    Consideraes Iniciais

    Assim

    g() = 0 1 + A()f() = 0 A() = -1/f()

    donde se toma A(x) = -1/f(x)

    Ento, dada f(x), a funo de iterao g(x) = x - f(x)/f(x) ser tal que g() = 0, posto que

    g(x) = 1 {[f(x)]2 f(x)f(x)}/[f(x)]2

    e, como f() = 0, g() = 0 (desde que f() 0 )

    57

  • Clculo Numrico

    Razes de Equaes No Lineares

    Consideraes Iniciais

    Deste modo, escolhido x0 , a seqncia {xk} ser

    determinada por

    xk+1 = xk f(xk)/f(xk)

    onde k = 0, 1, 2, ...

    58

  • Clculo Numrico

    Razes de Equaes No Lineares

    Motivao Geomtrica

    Dado o ponto (xk , f(xk))

    Traa-se a reta Lk(x) tangente curva neste ponto:

    Lk(x) = f(xk) + f(xk)(x-xk)

    Determina-se o zero de Lk(x), um modelo linear que aproxima f(x) em uma vizinhana xk

    Lk(x) = 0 x = xk - f(xk)/f(xk)

    Faz-se xk +1 = x

    59

  • Clculo Numrico

    Razes de Equaes No Lineares

    Anlise Grfica

    60

    x

    f(x)

    x1 x0

    x2 x3

    1a iterao

    2a iterao

    3a iterao

    4a iterao

    Repete-se o processo at que

    o valor de x atenda s condies de parada.

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 12:

    Resgatando o Exemplo 9, no qual x2 + x 6 = 0 :

    61

    Seja a raiz 2 = 2 e x0 = 1,5 Assim:

    x1 = g(x0) = 1,5 (1,52 + 1,5 6)/(2.1,5 + 1) =

    = 2,062500000

    x2 = g(x1) = 2,000762195

    x3 = g(x2) = 2,000000116

    g(x) = x - f(x)/f(x) = x (x 2 + x 6)/(2x + 1) e

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 12:

    Comentrios:

    62

    A parada poder ocorrer na 3a iterao

    (x = 2,000000116), caso a preciso do clculo com 6 casas decimais for satisfatria para o

    contexto do trabalho

    Observe-se que no Exemplo 10, o MPF com

    g(x) = 6 - x s veio a produzir x = 2,000476818 na 5a iterao

  • Clculo Numrico

    Razes de Equaes No Lineares

    63

    Estudo da Convergncia

    TEOREMA 3:

    Sendo f(x), f(x) e f(x) contnuas em um intervalo I que contm uma raiz x = de f(x) = 0 e supondo f() 0, existir um intervalo I contendo a raiz , tal que se x0 , a seqncia {xk} gerada pela frmula recursiva

    xk+1 = xk - f(xk)/f(xk)

    convergir para a raiz.

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 13:

    Considere-se a funo f(x) = x3 - 9x + 3 , cujos zeros encontram-se nos intervalos:

    64

    1 I1 = (-4, -3), 2 I2 = (0, 1) e 3 I3 = (2, 3)

    Seja x0 = 1,5

    xk+1 = xk - f(xk)/f(xk)

    e g(x) = x (x3 - 9x + 3)/(3x2 9)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 13:

    A seqncia {xk} gerada pelo mtodo de Newton ser:

    65

    f(x)

    13,37037028

    x

    -1,66666667

    18,38888989

    12,36601106

    8,40230714

    5,83533843

    4,23387371

    3,32291104

    2,91733895

    2,82219167

    2,81692988

    Iterao

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    6055,72648668

    1782,69441818

    520,57174528

    149,18208182

    40,79022981

    9,78451301

    1,57303193

    0,07837072

    0,00023432

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 13:

    Comentrios:

    66

    Constata-se nas primeiras iteraes uma

    divergncia da regio em que se encontram as

    razes, a qual revertida a partir da 7a iterao

    Tal divergncia inicial deve-se proximidade de x0 de 3 , que um zero de f(x). Tal proximidade inicial gera x1 = -1,66666667 -3, outro zero de f(x).

  • Clculo Numrico

    Razes de Equaes No Lineares

    Clculo das aproximaes

    As aproximaes subseqentes sero determinadas a partir da equao

    67

    |(f(x0).f(x0))/f(x0) 2)| =

    |(f(xk).f(xk+1))/f(x0)2)|

    onde xk+1 = xk (f(xk)/f(xk+1))

  • Clculo Numrico

    Razes de Equaes No Lineares

    Testes de Parada

    A cada iterao, testa-se se a aproximao encontrada poder ser considerada como a

    soluo do problema.

    |f(xk)| tolerncia

    |((xk+1 xk)/xk+1 )| tolerncia

    68

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; x0 := x;

    while critrio de interrupo no satisfeito and k L

    k := k +1;

    xk+1 := xk f(xk)/f(xk)

    endwhile

    69

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo da Secante

    Dada uma funo f(x) contnua no intervalo [a,b] onde

    existe uma raiz nica, possvel determinar uma

    aproximao de tal raiz a partir da interseo da

    secante curva em dois pontos x0 e x1 com o eixo

    das abscissas.

    x0 e x1 - atribudos em funo da geometria do

    mtodo e do comportamento da curva da equao

    nas proximidades da raiz.

    70

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodo de Newton-Raphson Um grande inconveniente a necessidade da obteno de f(x) e o clculo de seu valor numrico a cada iterao Forma de desvio do inconveniente: Substituio da derivada f(xk) pelo quociente das diferenas

    f(xk) [f(xk) - f(xk-1)]/(xk - xk-1) onde xk-1 e xk so duas aproximaes para a raiz

    71

  • Clculo Numrico

    Razes de Equaes No Lineares

    A funo de iterao ser

    g(x) = xk - f(xk)/[(f(xk) - f(xk-1))/(xk - xk-1)]

    = (xk - xk-1) . f(xk)/[f(xk) - f(xk-1)]

    = [xk-1 .f(xk) xk . f(xk-1)]/[f(xk) - f(xk-1)]

    72

    g(x) = [xk-1 .f(xk) xk . f(xk-1)]/[f(xk) - f(xk-1)]

  • Clculo Numrico

    Razes de Equaes No Lineares

    Interpretao Geomtrica

    73

    A partir de duas aproximaes xk-1 e xk

    Obtm-se o ponto xk+1 como sendo a

    abscissa do ponto de interseco do eixo ox

    e da reta que passa pelos pontos

    (xk-1, f(xk-1)) s (xk, f(xk)) (secante curva

    da funo)

  • Clculo Numrico

    Razes de Equaes No Lineares

    Anlise Grfica

    74

    x

    f(x)

    x1 x0 x2

    x3

    1a iterao

    2a iterao

    3a iterao

    4a iterao

    Repete-se o processo at que

    o valor de x atenda s condies de parada.

    x4 x5

  • Clculo Numrico

    Razes de Equaes No Lineares

    Exemplo 12:

    Resgatando o Exemplo 9, no qual x2 + x 6 = 0 :

    75

    Sejam x0 = 1,5 e x1 = 1,7

    Assim:

    x3 = [x1 .f(x2) x2 . f(x1)]/[f(x2) - f(x1)] = 1,99774

    x2 = [x0 .f(x1) x1 . f(x0)]/[f(x1) - f(x0)] = [1,5.(-1,41) 1,7.(2,25)]/(-1,41 + 2,25) = 2,03571

    x4 = [x2 .f(x3) x3 . f(x2)]/[f(x3) - f(x2)] = 1,99999

  • Clculo Numrico

    Razes de Equaes No Lineares

    Testes de Parada

    A cada iterao, testa-se se a aproximao encontrada

    poder ser considerada como a soluo do problema.

    |f(xk)| tolerncia

    |((xk+1 xk)/xk+1 )| tolerncia

    76

  • Clculo Numrico

    Razes de Equaes No Lineares

    Algoritmo

    k := 0; x0 := X0; x1 := X1

    while critrio de interrupo no satisfeito and k L

    k := k +1;

    xk+1 := (xk-1*f(xk) - xk*f(xk-1))/(f(xk) - f(xk-1)) endwhile

    77

  • Clculo Numrico

    Razes de Equaes No Lineares

    Oficina

    1. Encontre uma raiz da funo 3x2 + 2x 12 = 0

    usando 4 iteraes do mtodo da Biseco e

    determine um erro absoluto e um erro relativo

    deste resultado

    2. Faa o mesmo usando o mtodo de Newton

    Raphson.

    3. Comente as diferenas dos erros dos dois

    clculos numricos.

    78

  • Clculo Numrico

    Razes de Equaes No Lineares

    79

    Critrios de comparao Garantia de convergncia

    Mtodo da Bisseco e Falsa Posio - tm convergncia garantida desde que a funo seja contnua num intervalo [a,b], tal que f(a)f(b)

  • Clculo Numrico

    Razes de Equaes No Lineares

    80

    Esforo Computacional

    difcil tirar concluses gerais sobre a eficincia computacional de um mtodo. Por exemplo:

    Bisseco - efetua clculos mais simples por iterao.

    Newton - requer clculos mais elaborados. Porm, O nmero de iteraes da Bisseco , na grande maioria das vezes, muito maior que o nmero de iteraes efetuadas por Newton.

    Considerando que o mtodo ideal deve satisfazer as condies:

    convergncia assegurada

    ordem de convergncia alta

    clculos por iterao simples

    Deve-se escolher:

    Mtodo de Newton - se for fcil verificar as condies de convergncia e calcular f(x).

    Mtodo da Secante - se for trabalhoso obter e/ou avaliar f(x), pois no preciso obter f(x).

    Deve-se evitar o uso do Mtodo de Newton e da

    Secante quando:

    a curva tende a ser paralela a qualquer um

    dos eixos.

    a funo tangencia o eixo das abscissas em

    um ou mais pontos.

    Concluso

    A escolha do mtodo est diretamente relacionada

    com a equao que se quer resolver, no que diz

    respeito ao comportamento da funo na regio da

    raiz exata, s dificuldades com o clculo de f(x), ao critrio de parada, etc

  • Clculo Numrico

    Razes de Equaes No Lineares

    81

    Exemplo 1

    4

    21

    -x 10 (1,2); ;)(cose)(f2 xx

    Tolerncia para |f(x)|

  • Clculo Numrico

    Razes de Equaes No Lineares

    82

    Exemplo 2

    6

    21

    3 10 (1,2); 1;-x-x)(f x

  • Clculo Numrico

    Razes de Equaes No Lineares

    83

    Exemplo 3

    5

    21

    x 10 (0,1); ;e-4sen(x))(f x

  • Clculo Numrico

    Razes de Equaes No Lineares

    84

    Exemplo 4

    7

    21 10 (2,3); 1;-xlog(x))(fx

  • Clculo Numrico

    Razes de Equaes No Lineares

    Mtodos Iterativos para a Obteno

    de Zeros Reais de Funes

    Bisseco (ou de Bolzano)

    Falsa Posio

    Ponto Fixo

    Newton-Raphson

    Secante

    85

    x1 = (a+b)/2

    x1 = ( a f(b) - b f(a) ) / (f(b) - f(a))

    xk+1 = g(xk), x = g(x)

    xk+1 = [xk-1 .f(xk) xk . f(xk-1)]/[f(xk) - f(xk-1)]

    xk+1 = xk f(xk)/f(xk)

  • Clculo Numrico

    Razes de Equaes No Lineares GRUPO

    1. Descreva um problema (uma questo) da rea de estudo do seu curso em que necessrio um

    clculo de uma raz para encontrar uma soluo (resposta). Deixe claro qual a varivel dependente

    (a questo) e as variveis independentes (os fatores que influenciam direta ou inversamente o

    problema).

    2. Descreva um modelo matemtico para o problema. Use o seu conhecimento do problema para

    propor relaes coerentes de dependncia direta e inversa das variveis. Explicite o significado

    prtico de todas as variveis envolvidas.

    3. Descreva um cenrio (um conjunto de dados) que representa uma situao particular deste

    problema e que permite encontrar sua resposta o modelo matemtico.

    INDIVIDUAL

    4. Encontre 4 respostas para o problema usando 3 iteraes de cada um dos mtodos numricos

    estudados (biseco, falsa posio, newton raphson e secante).

    5. Calcule o erro relativo dos 4 resultados obtidos pelos 4 mtodos.

    6. Comente sobre as diferenas notadas nos 4 resultados, fazendo referncias aos valores dos erros

    calculados e s caractersticas dos 4 mtodos de velocidade de convergncia.