Método de Newton-Raphson

Cálculo Numérico - Versão Scilab

3.4 Método de Newton-Raphson

Nesta seção, apresentamos o método de Newton-Raphson⁵ ⁶ 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) \neq 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^{*}) = - \frac{1}{f^{'} (x^{*})},

(3.114)

se $f^{'} (x^{*}) \neq 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)} - \frac{f (x^{(n)})}{f^{'} (x^{n})}, n \geq 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)} - \frac{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 \Rightarrow x = x^{(1)} - \frac{f (x^{(1)})}{f^{'} (x^{(1)})} .

(3.118)

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^{*}) \neq 0$ . Seja também a função $g (x)$ definida como:

g (x) = x - \frac{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^{*}) + \frac{g^{″} (x^{*})}{2} {(x - x^{*})}^{2} + O ({(x - x^{*})}^{3}) .

(3.120)

Observamos que: $\begin{array}{rcl} g (x^{*}) & = & x^{*} & (3.121) \\ g^{'} (x^{*}) & = & 1 - \frac{f^{'} (x^{*}) f^{'} (x^{*}) - f (x^{*}) f^{″} (x^{*})}{{(f^{'} (x^{*}))}^{2}} = 0 & (3.122) \end{array}$

Portanto:

g (x) = x^{*} + \frac{g^{″} (x^{*})}{2} {(x - x^{*})}^{2} + O ({(x - x^{*})}^{3})

(3.123)

Com isso, temos:

x^{(n + 1)} = g (x^{(n)}) = x^{*} + \frac{g^{″} (x^{*})}{2} {(x^{(n)} - x^{*})}^{2} + O ({(x - x^{*})}^{3}),

(3.124)

ou seja:

|x^{(n + 1)} - x^{*}| \leq 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 \in C^{2} ([a, b])$ com $x^{*} \in (a, b)$ tal que $f (x^{*}) = 0$ e:

m : = min_{x \in [a, b]} | f^{'} (x) | > 0 e M : = max_{x \in [a, b]} | f^{″} (x) | .

(3.126)

Escolhendo $ρ > 0$ tal que:

q : = \frac{M}{2 m} ρ < 1,

(3.127)

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

K_{ρ} (x^{*}) : = \{x \in ℝ; | x - x^{*} | \leq ρ\} \subset [a, b] .

(3.128)

Então, para qualquer $x^{(1)} \in K_{ρ} (x^{*})$ a iteração do método de Newton:

x^{(n + 1)} = x^{(n)} - \frac{f (x^{(n)})}{f^{'} (x^{(n)})},

(3.129)

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

| x^{(n)} - x^{*} | \leq \frac{2 m}{M} q^{(2^{n - 1})}, n \geq 2,

(3.130)

e a seguinte estimativa de erro a posteriori:

| x^{(n)} - x^{*} | \leq \frac{M}{2 m} | x^{(n)} - x^{(n - 1)} |^{2}, n \geq 2 .

(3.131)

Demonstração. Para

n \in ℕ

n \geq 2

, temos:

x^{n + 1} - x^{*} = x^{(n)} - \frac{f (x^{(n)})}{f^{'} (x^{(n)})} - x^{*} = - \frac{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)}) + \int_{x^{(n)}}^{x^{*}} f^{″} (t) (x^{*} - t) d t .

(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)})}^{2} \int_{0}^{1} f^{″} (x^{(n)} + s (x^{*} - x^{(n)})) (1 - s) d s .

(3.134)

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

| R (x^{*}, x^{(n)}) | \leq M | x^{*} - x^{(n)} |^{2} \int_{0}^{1} (1 - s) d s = \frac{M}{2} | x^{*} - x^{(n)} |^{2} .

(3.135)

Se $x^{(n)} \in K_{ρ} (x^{*})$ , então de (3.132) e (3.135) temos:

| x^{(n + 1)} - x^{*} | \leq \frac{M}{2 m} | x^{(n)} - x^{*} |^{2} \leq \frac{M}{2 m} ρ^{2} < ρ .

(3.136)

Isto mostra que se $x^{(n)} \in K_{ρ} (x^{*})$ , então $x^{(n + 1)} \in K_{ρ} (x^{*})$ , isto é, $x^{(n)} \in K_{ρ} (x^{*})$ para todo $n \in ℝ$ .

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

| x^{(n)} - x^{*} | \leq \frac{2 m}{M} {(\frac{M}{2 m} | x^{(n - 1)} - x^{*} |)}^{2} \leq \dots \leq \frac{2 m}{M} {(\frac{M}{2 m} | x^{(1)} - x^{*} |)}^{2^{n - 1}} .

(3.137)

Logo:

| x^{(n)} - x^{*} | \leq \frac{2 m}{M} q^{2^{n - 1}},

(3.138)

donde também vemos que $x^{(n)} \to x^{*}$ quando $n \to \infty$ , 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)}) | \leq \frac{M}{2} | x^{(n)} - x^{(n - 1)} |^{2} .

(3.141)

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

| x^{(n)} - x^{*} | \leq \frac{1}{m} | f (x^{(n)}) - f (x^{*}) | \leq \frac{M}{2 m} | 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:

ρ < \frac{2 m}{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^{*}) \subset [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)} \in [0, π ∕ 2]$ .

$♢$

Exercícios

E 3.4.1. Encontre a raiz positiva da função $f (x) = cos (x) - x^{2}$ pelo método de Newton inicializando-o com $x^{(0)} = 1$ . Realize a iteração até obter estabilidade no $q u i n t o$ dígito significativo.

Resposta. raiz:0,82413, processo iterativo:

x^{(n + 1)} = x^{(n)} + \frac{cos (x) - x^{2}}{sen (x) + 2 x}

-->x=1
-->x=x+(cos(x)-x^2)/(sin(x)+2*x)
-->x=x+(cos(x)-x^2)/(sin(x)+2*x)
-->x=x+(cos(x)-x^2)/(sin(x)+2*x)
-->x=x+(cos(x)-x^2)/(sin(x)+2*x)

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

tg (x) = 2 x^{2} .

(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.

Resposta.

Primeiramente, deve-se observar que a função $tg (x)$ não está definida quando $x$ é um múltiplo ímpar de $\frac{π}{2}$ , pelo que devemos cuidado nas singularidades. Traçamos o gráfico da função $f (x) = tg (x) - 2 x^{2}$ no Scilab usando os seguintes comandos:
-->deff(’y=f(x)’,’y=tan(x)-2*x^2’)
-->plot([0:.01:1.3],f)

Observamos facilmente uma raiz no intervalo $(0, 5, 0, 6)$ e outra no intervalo $(1, 2, 1, 3)$ . Como a função $f (x)$ é contínua fora dos pontos de singularidade da tangente, é fácil verificar que existe pelo menos uma solução nos intervalos dados pelo teorema de Bolzano 3.1.1: $\begin{array}{rcl} f (0, 5) & \approx & 0, 046302 > 0 & (3.145) \\ f (0, 6) & \approx & - 0, 035863 < 0 & (3.146) \\ f (1, 2) & \approx & - 0, 30784 e - 1 < 0 & (3.147) \\ f (1, 3) & \approx & 0, 22210 e - 1 > 0 & (3.148) \\ (3.149) \end{array}$

Para provar a unicidade da solução em cada intervalo, precisamos mostra que a função é monótona, ou seja, a derivada não muda de sinal em cada intervalo: $\begin{array}{rcl} f^{'} (x) = {sec}^{2} (x) - 4 x = \frac{1}{{cos}^{2} (x)} - 4 x \leq \frac{1}{{cos}^{2} (0, 6)} - 4 * 0, 5 < 0, x \in [0, 5, 0, 6] & (3.150) \\ f^{'} (x) = {sec}^{2} (x) - 4 x = \frac{1}{{cos}^{2} (x)} - 4 x \geq \frac{1}{{cos}^{2} (1, 2)} - 4 * 1, 3 > 0, x \in [1, 2, 1, 3] & (3.151) \\ (3.152) \end{array}$

Para recalcular as raízes pelo método de Newton, basta executar a iteração:

x^{(n + 1)} = x^{(n)} - \frac{f (x^{(n)})}{f^{'} (x^{(n)}} .

(3.153)

Em relação à observação, o erro se deveu à falta de cuidado em compreender o problema antes de tentar resolvê-lo, em especial, à falta de observar que a função é descontínua em múltiplos ímpares de $\frac{π}{2}$ . Nestes pontos, a função $f (x)$ troca de sinal, mas não passa por zero.

E 3.4.3. Considere a equação

e^{- x^{2}} = x

(3.154)

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. (Use o comando format(’v’,16) para alterar a visualização no Scilab.)

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 (10 x) = e^{- x} .

(3.155)

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

Resposta.

0, 0198679

;

0, 533890

;

0, 735412

;

1, 13237

1, 38851

E 3.4.5. Encontre as raízes do polinômio $f (x) = x^{4} - 4 x^{2} + 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) = \frac{x^{5}}{100} + x^{4} + 3 x + 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) = x^{3} - 2 x + 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) = x e^{- x} = 0$ tal que o esquema iterativo divirja.

Resposta.

$x_{0} > 1$ .

E 3.4.10. (Computação) Aplique o método de Newton à função $f (x) = \frac{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.

\begin{array}{rcl} x^{(0)} & = & C.I. & (3.156) \\ x^{(n + 1)} & = & x^{(n)} (2 - A x^{(n)}) & (3.157) \\ (3.158) \end{array}

E 3.4.11. (Computação) Aplique o método de Newton à função $f (x) = x^{n} - A$ e construa um esquema computacional para calcular $\sqrt[n]{A}$ para $A > 0$ com base em operações de multiplicação e soma/subtração.

Resposta.

\begin{array}{rcl} x_{0} & = & C.I. & (3.159) \\ x^{(n + 1)} & = & x^{(n)} (1 - \frac{1}{n}) + \frac{A}{n x^{(n)}} & (3.160) \end{array}

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

Resposta.

\begin{array}{rcl} x_{0} & = & C.I. & (3.161) \\ x^{(n + 1)} & = & x^{(n)} + \frac{x^{(n)} - A x^{(n)}}{2} = \frac{(3 - A) x^{(n)}}{2} & (3.162) \\ (3.163) \end{array}

E 3.4.13. Considere a função dada por $\begin{array}{rcl} ψ (x) & = & ln (15 - ln (x)) & (3.164) \end{array}$

definida para $x \in (0, e^{15})$

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 \geq 0$ (3.165)

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 $x_{0} = 2$ . Use o computador para obter a raiz e expresse a resposta com oito dígitos significativos corretos.

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 19/8/2020 às 17:36:32.

Recursos

Projeto

IME - UFRGS
- Página do IME
- Página da UFRGS

UFRGS - IME - Recursos Educacionais Abertos de Matemática. Contato: reamat@ufrgs.br.

Informe erros ou edite você mesmo!