Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão Python

3.4 Método de Newton-Raphson


Nesta seção, apresentamos o método de Newton-Raphson5 6 para calcular o zero de funções reais de uma variável real.

Consideramos que x* seja um zero de uma dada função y = f(x) continuamente diferenciável, isto é, f(x*) = 0. A fim de usar a iteração do ponto fixo, observamos que, equivalentemente, x* é um ponto fixo da função:

g(x) = x + α(x)f(x),α(x)0, (3.109)

onde α(x) é uma função arbitrária, a qual escolheremos de forma que a iteração do ponto fixo tenha ótima taxa de convergência.

Do teorema do ponto fixo, a taxa de convergência é dada em função do valor absoluto da derivada de g(x). Calculando a derivada temos:

g(x) = 1 + α(x)f(x) + α(x)f(x). (3.110)

No ponto x = x*, temos:

g(x*) = 1 + α(x*)f(x*) + α(x*)f(x*). (3.111)

Como f(x*) = 0, temos:

g(x*) = 1 + α(x*)f(x*). (3.112)

Sabemos que o processo iterativo converge tão mais rápido quanto menor for |g(x)| nas vizinhanças de x*. Isto nos leva a escolher:

g(x*) = 0, (3.113)

e, então, temos:

α(x*) = - 1 f(x*), (3.114)

se f(x*)0.

A discussão acima nos motiva a introduzir o método de Newton, cujas iterações são dada por:

x(n+1) = x(n) - f x(n) f xn ,n 1, (3.115)

sendo x(1) uma aproximação inicial dada.

3.4.1 Interpretação geométrica


Seja uma dada função f(x) conforme na Figura 3.6. Para tanto, escolhemos uma aproximação inicial x(1) e computamos:

x(2) = x(1) - f(x(1)) f(x(1)). (3.116)

Geometricamente, o ponto x(2) é a interseção da reta tangente ao gráfico da função f(x) no ponto x = x(1) com o eixo das abscissas. Com efeito, a equação desta reta é:

y = f(x(1))(x - x(1)) + f(x(1)). (3.117)

Assim, a interseção desta reta com o eixo das abscissas (y = 0) ocorre quando:

f(x(1))(x - x(1)) + f(x(1)) = 0 x = x(1) - f(x(1)) f(x(1)). (3.118)


PIC

Figura 3.6: Interpretação do método de Newton.


Ou seja, dada aproximação x(n), a próxima aproximação x(n+1) é o ponto de interseção entre o eixo das abscissas e a reta tangente ao gráfico da função no ponto x = x(n). Observe a Figura 3.6.

3.4.2 Análise de convergência


Seja y = f(x) uma função com derivadas primeira e segunda contínuas tal que f(x*) = 0 e f(x*)0. Seja também a função g(x) definida como:

g(x) = x - f(x) f(x). (3.119)

Expandindo em série de Taylor em torno de x = x*, obtemos:

g(x) = g(x*) + g(x*)(x - x*) + g(x*) 2 (x - x*)2 + O (x - x*)3 . (3.120)

Observamos que: g(x*) = x* (3.121) g(x*) = 1 - f(x*)f(x*) - f(x*)f(x*) f(x*) 2 = 0 (3.122)

Portanto:

g(x) = x* + g(x*) 2 (x - x*)2 + O (x - x*)3 (3.123)

Com isso, temos:

x(n+1) = g(x(n)) = x* + g(x*) 2 (x(n) - x*)2 + O (x(n) - x*)3 , (3.124)

ou seja, para n suficientemente grande,

x(n+1) - x* C x(n) - x*2, (3.125)

com constante C = g(x*)2. Isto mostra que o método de Newton tem taxa de convergência quadrática. Mais precisamente, temos o seguinte teorema.

Teorema 3.4.1 (Método de Newton). Sejam f C2([a,b]) com x* (a,b) tal que f(x*) = 0 e:

m := min x[a,b]|f(x)| > 0eM := max x[a,b]|f(x)|. (3.126)

Escolhendo ρ > 0 tal que:

q := M 2mρ < 1, (3.127)

definimos a bacia de atração do método de Newton pelo conjunto:

Kρ(x*) := x ; |x - x*| ρ [a,b]. (3.128)

Então, para qualquer x(1) K ρ(x*) a iteração do método de Newton:

x(n+1) = x(n) - f(x(n)) f(x(n)), (3.129)

fornece uma sequência x(n) que converge para x*, isto é, x(n) x* quando n . Além disso, temos a seguinte estimativa de erro a priori:

|x(n) - x*| 2m M q(2n-1),n 2, (3.130)

e a seguinte estimativa de erro a posteriori:

|x(n) - x*| M 2m|x(n) - x(n-1)|2,n 2. (3.131)

Demonstração. Para n , n 2, temos:
xn+1 - x* = x(n) - f(x(n)) f(x(n)) - x* = - 1 f(x(n)) f(x(n)) + (x* - x(n))f(x(n)) . (3.132)

Agora, para estimar o lado direito desta equação, usamos o polinômio de Taylor de grau 1 da função f(x) em torno de x = x(n), isto é:

f(x*) = f(x(n)) + (x* - x(n))f(x(n)) +x(n)x* f(t)(x* - t)dt. (3.133)

Pela mudança de variável t = x(n) + s(x(n) - x*), observamos que o resto deste polinômio de Taylor na forma integral é igual a:

R(x*,x(n)) := (x* - x(n))201f x(n) + s(x* - x(n)) (1 - s)ds. (3.134)

Assim, da cota da segunda derivada de f(x), temos:

|R(x*,x(n))| M|x* - x(n)|201(1 - s)ds = M 2 |x* - x(n)|2. (3.135)

Se x(n) K ρ(x*), então de (3.132) e (3.135) temos:

|x(n+1) - x*| M 2m|x(n) - x*|2 M 2mρ2 < ρ. (3.136)

Isto mostra que se x(n) K ρ(x*), então x(n+1) K ρ(x*), isto é, x(n) K ρ(x*) para todo n .

Agora, obtemos a estimativa a priori de (3.4.2), pois:

|x(n) - x*| 2m M M 2m|x(n-1) - x*|2 2m M M 2m|x(1) - x*|2n-1 . (3.137)

Logo:

|x(n) - x*| 2m M q2n-1 , (3.138)

donde também vemos que x(n) x* quando n , pois q < 1.

Por fim, para provarmos a estimativa a posteriori tomamos a seguinte expansão em polinômio de Taylor:

f(x(n)) = f(x(n-1)) + (x(n) - x(n-1))f(x(n-1)) + R(x(n),x(n-1)). (3.139)

Aqui, temos:

f(x(n-1)) + (x(n) - x(n-1))f(x(n-1)) = 0 (3.140)

e, então, conforme acima:

|f(x(n))| = |R(x(n),x(n-1))| M 2 |x(n) - x(n-1)|2. (3.141)

Com isso e do teorema do valor médio, concluímos:

|x(n) - x*| 1 m|f(x(n)) - f(x*)| M 2m|x(n) - x(n-1)|2. (3.142)

Exemplo 3.4.1. Estime o raio ρ da bacia de atração Kρ(x*) para a função f(x) = cos(x) - x restrita ao intervalo [0,π2].

Solução. O raio da bacia de atração é tal que:

ρ < 2m M (3.143)

onde m := min |f(x)| e M := max |f(x)| com o mínimo e o máximo tomados em um intervalo [a,b] que contenha o zero da função f(x). Aqui, por exemplo, podemos tomar [a,b] = [0,π2]. Como, neste caso, f(x) = - sen (x) - 1, temos que m = 1. Também, como f(x) = - cos x, temos M = 1. Assim, concluímos que ρ < 2 (lembrando que Kρ(x*) [0,π2]). Ou seja, neste caso as iterações de Newton convergem para o zero de f(x) para qualquer escolha da aproximação inicial x(1) [0,π2].

Exercícios


E 3.4.1. Encontre a raiz positiva da função f(x) = cos(x) - x2 pelo método de Newton inicializando-o com x(0) = 1. Realize a iteração até obter estabilidade no quinto dígito significativo.

Resposta. raiz:0,82413, processo iterativo: x(n+1) = x(n) + cos(x)-x2 sen (x)+2x

E 3.4.2. Considere o problema de calcular as soluções positivas da equação:

tg (x) = 2x2. (3.144)
  • Use o método gráfico para isolar as duas primeiras raízes positivas em pequenos intervalos. Use a teoria para argumentar quanto à existência e unicidade das raízes dentro intervalos escolhidos.
  • Calcule cada uma das raízes pelo método de Newton com oito dígitos significativos e discuta a convergência.

E 3.4.3. Considere a equação

e-x2 = x (3.145)

trace o gráfico com auxílio do computador e verifique que ela possui uma raiz positiva. Encontre uma aproximação para esta raiz pelo gráfico e use este valor para inicializar o método de Newton e obtenha uma aproximação para a raiz com 8 dígitos significativos.

Resposta. 0,65291864

E 3.4.4. Isole e encontre as cinco primeiras raízes positivas da equação com 6 dígitos corretos através de traçado de gráfico e do método de Newton.

cos(10x) = e-x. (3.146)

Dica: a primeira raiz positiva está no intervalo (0, 0,02). Fique atento.

Resposta. 0,0198679; 0,533890; 0,735412; 1,13237 e 1,38851.

E 3.4.5. Encontre as raízes do polinômio f(x) = x4 - 4x2 + 4 através do método de Newton. O que você observa em relação ao erro obtido? Compare com a situação do Problema 3.2.4.

E 3.4.6. Encontre as raízes reais do polinômio f(x) = x5 100 + x4 + 3x + 1 isolando-as pelo método do gráfico e depois usando o método de Newton. Expresse a solução com 7 dígitos significativos.

Resposta. - 99.99970, - 0.3376513; - 1.314006.

E 3.4.7. Considere o método de Newton aplicado para encontrar a raiz de f(x) = x3 - 2x + 2. O que acontece quando x(0) = 0? Escolha um valor adequado para inicializar o método e obter a única raiz real desta equação.

E 3.4.8. Justifique a construção do processo iterativo do método de Newton através do conceito de estabilidade de ponto fixo e convergência do método da iteração. Dica: Considere os problemas 3.3.17 e 3.3.18.

E 3.4.9. Entenda a interpretação geométrica ao método de Newton. Encontre uma valor para iniciar o método de Newton aplicado ao problema f(x) = xe-x = 0 tal que o esquema iterativo divirja.

Resposta.

x0 > 1.

E 3.4.10. (Computação) Aplique o método de Newton à função f(x) = 1 x - A e construa um esquema computacional para calcular a inversa de A com base em operações de multiplicação e soma/subtração.

Resposta. x(0) = C.I. (3.147) x(n+1) = x(n) 2 - Ax(n) (3.148) (3.149)

E 3.4.11. (Computação) Aplique o método de Newton à função f(x) = xn - A e construa um esquema computacional para calcular An para A > 0 com base em operações de multiplicação e soma/subtração.

Resposta. x0 = C.I. (3.150) x(n+1) = x(n) 1 - 1 n + A nx(n) (3.151)

E 3.4.12. (Computação) Aplique o método de Newton à função f(x) = 1 x2 - A e construa um esquema computacional para calcular 1 A para A > 0 com base em operações de multiplicação e soma/subtração.

Resposta. x0 = C.I. (3.152) x(n+1) = x(n) + x(n) - Ax(n) 2 = (3 - A)x(n) 2 (3.153) (3.154)

E 3.4.13. Considere a função dada por ψ(x) = ln 15 - ln(x) (3.155)

definida para x 0,e15

  • Use o teorema do ponto fixo para provar que se x(0) pertence ao intervalo [1,3], então a sequência dada iterativamente por
    x(n+1) = ψ(x(n)),n 0 (3.156)

    converge para o único ponto fixo, x*, de ψ. Construa a iteração x(n+1) = ψ(x(n)) e obtenha numericamente o valor do ponto fixo x*. Expresse a resposta com 5 algarismos significativos corretos.

  • Construa a iteração do método de Newton para encontrar x*, explicitando a relação de recorrência e iniciando com x0 = 2. Use o computador para obter a raiz e expresse a resposta com oito dígitos significativos corretos.

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 15/5/2019 às 15:24:50.

Informe erros ou edite você mesmo!