Baixe o app para aproveitar ainda mais
Prévia do material em texto
Estudo da Convergência do Método de Newton-Raphson Considere a equação f x( ) 0= onde x pertence ao intervalo [a,b] que contém uma única raiz isolada de f. Para saber a priori se a seqüência gerada pelas iteradas φk do método de Newton converge para a raiz, usamos o teorema da convexidade, que garante condições necessárias para a convergência. Nos exemplos seguintes mostramos 3 situações onde a convergência é observada, para a função f(x) que possui 3 raízes reais simples. f x( ) x pi−( ) x 2+( )⋅ x 1−( )⋅:= 0 50 50 f x( ) x A função φ do método de Newton é dada pela equação φ x( ) x f x( ) x f x( )d d −= para função f(x), f x( ) x3 1 pi−( ) x2⋅+ 2 pi+( ) x⋅− 2 pi⋅+:= x f x( )d d 3 x2⋅ 2 1 pi−( ) x⋅⋅ 2− pi−+→ portanto φ x( ) x x 3 1 pi−( ) x2⋅+ 2 pi+( ) x⋅− 2 pi⋅+ 3 x2⋅ 2 1 pi−( ) x⋅⋅ 2− pi−+ − := 4 2 0 2 4 10 5 5 10 Função Fi_Newton φ x( ) y y y x pi, 1, 2−, 4 2 0 2 4 1 0.5 0.5 1 Derivada da Fi_Newton x φ x( )d d y y y x pi, 1, 2−, Estudo 1: tipo de seqüência crescente, decrescente, oscilante A expressão da função φ que gera as iteradas do método de Newton é única, mas a convergência para cada uma das raízes pode ser diferente, pois depende do sinal da derivada de φ(x). CASO 1: Seqüência crescente ou decrescente: se o chute inicial e os demais valores de xk obtidos estiverem contidos num intervalo onde x φd d é POSITIVA. CASO 1: Seqüência oscilante ou alternada: se o chute inicial e os demais valores de xk obtidos estiverem contidos num intervalo onde x φd d é NEGATIVA. Exemplificando os CASOS 1 e 2 CASO 1: seqüência decrescente para a raiz z1 = pi chute inicial: x0 5.0:= k 0 6..:= xk 1+ xk xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+ 3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )− −:= Neste caso a derivada da função φ é POSITIVA e a seqüência gerada é DECRESCENTE. x 5 3.92583111 3.36581355 3.16853365 3.14205955 3.1415928 3.14159265 3.14159265 = CASO 2: seqüência alternada ou oscilante para a raiz z1 = pi chute inicial: x0 2.5:= k 0 6..:= xk 1+ xk xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+ 3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )− −:= Neste caso a derivada da função φ é NEGATIVA e a seqüência gerada é OSCILANTE. x 2.5 3.99313357 3.3962246 3.17546795 3.14232566 3.14159301 3.14159265 3.14159265 = CASO 2: seqüência alternada ou oscilante para a raiz z2 = 1 chute inicial: x0 1.8:= k 0 6..:= xk 1+ xk xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+ 3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )− −:= Neste caso a derivada da função φ é NEGATIVA e a seqüência gerada é OSCILANTE. x 1.8 0.49753536 1.005665 0.99999565 1 1 1 1 = CASO ?: seqüência oscilante e depois crescente para a raiz z2 = 1 chute inicial: x0 1.6:= k 0 6..:= xk 1+ xk xk( )3 1 pi−( ) xk( )2⋅+ 2 pi+( ) xk⋅− 2 pi⋅+ 3 xk( )2⋅ 2 1 pi−( )⋅ xk⋅+ 2 pi+( )− −:= Neste caso a derivada da função φ é NEGATIVA no chute inicial, o que implica no valor x1 menor que a raiz, mas para valores menores que a raiz, a derivada da φ é positiva, o que torna a seqüência crescente para or valores xk, com k>1, até a convergência. Neste caso deve se dizer que a seqüência é crescente! x 1.6 0.82825492 0.99770957 0.9999993 1 1 1 1 = Estas observações servem como base para definir como fazer a aceleração da convergência do método de Newton ou de qualquer método cujas iterações sejam construídas a partir de uma função de iteração, da qual sabemos a priori que a seqüência gerada converge para a raiz. Cálculo de zeros de uma função com PRECISÃO PRÉ-FIXADA δδδδ. Seja f(x) = 0 e φ(xk)= xk+1, k = 0,1,2,3 a seqüência das iteradas pelo método das aproximações sucessivas obtidas a partir do chute inicial x0.Apenas observando os valores de xk, para k = 1,2,3, é possível identificar se a seqüência é crescente/decrescente ou oscilante. É obvio que o ideal é determinar o sinal de x φ x( )d d para identificar o tipo de seqüência, como foi mostrado no início desse Capítulo, mas calcular a derivada da função φ não é uma tarefa fácil e em geral, os valores calculados das 3 primeiras iteradas definem de forma adequada o tipo de seqüência. Portanto, depois de indetificar o tipo de seqüência é possível introduzir a aceleração da convergência seqüência oscilante ⇔ a raiz α está contida nos intervalos definidos por duas iteradas consecutivas (Figura 1) Figura 1 seqüência monótona crescente ⇔ a raiz α está sempre à direita das iteradas (Figura 2) Figura 2 seqüência monótona decrescente ⇔ a raiz α está sempre à esquerda das iteradas (Figura 3) Figura 3 Aceleração da convergência para seqüências oscilantes seqüência oscilante ⇔ a raiz α está contida nos intervalos definidos por duas iteradas consecutivas Neste caso a raiz aproximada ξn pode ser escolhida como o ponto médio entre duas iteradas consecutivas ξn x n x n 1−+ 2 = E o erro εn será no máximo εn x n x n 1−− 2 = LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO εn δ≤ Aceleração da convergência para seqüências crescentes seqüência monótona crescente ⇔ a raiz α está sempre à direita das iteradas Como a seqüência é crescente, se α é o valor exato, então x n 1− xn≤ α≤ conseqüentemente, x n φ x n( )≤ α≤ então, calculando φ no ponto (x n +2δ) teremos x n 2δ+ φ x n 2δ+( )≤ , enquanto xn 2δ+ α≤ LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO x n 2δ+ α≤ . QUANDO x n 2δ+ α> SABEMOS QUE A RAIZ α ESTÁ CONTIDA NO INTERVALO [x n , x n +2δ]. Neste caso a raiz aproximada ξn pode ser escolhida como ξn xn δ+= E o erro εn será certamente εn xn α− δ≤= Aceleração da convergência para seqüências decrescentes seqüência monótona decrescente ⇔ a raiz α está sempre à esquerda das iteradas Como a seqüência é crescente, se α é o valor exato, então x n 1− xn≥ α≥ conseqüentemente, x n φ x n( )≥ α≥ então, calculando φ no ponto (x n - 2δ) teremos x n 2δ− φ x n 2δ−( )≥ , enquanto x n 2δ− α≥ LOGO, O PROCESSO ITERATIVO DEVE SER REPETIDO ENQUANTO x n 2δ− α≥ . QUANDO x n 2δ− α< SABEMOS QUE A RAIZ α ESTÁ CONTIDA NO INTERVALO [x n -2δ, x n ]. Neste caso a raiz aproximada ξn pode ser escolhida como ξn xn δ−= E o erro εn será certamente εn xn α− δ≤=
Compartilhar