Método das secantes

Cálculo Numérico - Versão Scilab

3.5 Método das secantes

O método das secantes é uma variação do método de Newton, evitando a necessidade de conhecer-se a derivada analítica de $f (x)$ . Dada uma função $f (x)$ , a ideia é aproximar sua derivada pela razão fundamental:

f^{'} (x) \approx \frac{f (x) - f (x_{0})}{x - x_{0}}, x \approx x_{0} .

(3.166)

Mais precisamente, o método de Newton é uma iteração de ponto fixo da forma:

x^{(n + 1)} = x^{(n)} - α (x^{(n)}) f (x^{(n)}), n \geq 1,

(3.167)

onde $x^{(1)}$ é uma aproximação inicial dada e $α (x^{(n)}) = 1 ∕ f^{'} (x^{(n)})$ . Usando a aproximação da derivada acima, com $x = x^{(n)}$ e $x_{0} = x^{(n - 1)}$ , temos:

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

(3.168)

Isto nos motiva a introduzir a iteração do método das secantes dada por:

x^{(n + 1)} = x^{(n)} - f (x^{(n)}) \frac{x^{(n)} - x^{(n - 1)}}{f (x^{(n)}) - f (x^{(n - 1)})}, n \geq 2 .

(3.169)

Observe que para inicializarmos a iteração acima precisamos de duas aproximações iniciais, a saber, $x^{(1)}$ e $x^{(2)}$ . Maneiras apropriadas de escolher estas aproximações podem ser inferidas da interpretação geométrica do método.

Exemplo 3.5.1. Encontre as raízes de $f (x) = cos (x) - x$ .

Solução. Da inspeção do gráfico das funções $y = cos (x)$ e $y = x$ , sabemos que esta equação possui uma raiz em torno de $x = 0, 8$ . Iniciamos o método com $x_{0} = 0, 7$ e $x_{1} = 0, 8$ .


$x^{(n - 1)}$	$x^{(n)}$	$m$	$x^{(n + 1)}$

		$\frac{f (0, 8) - f (0, 7)}{0, 8 - 0, 7} =$	$0, 8 - \frac{f (0, 8)}{- 1, 6813548} =$
$0, 7$	$0, 8$	$- 1, 6813548$	$0, 7385654$

$0, 8$	$0, 7385654$	$- 1, 6955107$	$0, 7390784$

$0, 7385654$	$0, 7390784$	$- 1, 6734174$	$0, 7390851$

$0, 7390784$	$0, 7390851$	$- 1, 6736095$	$0, 7390851$

$♢$

3.5.1 Interpretação geométrica

Enquanto, o método de Newton está relacionado às retas tangentes ao gráfico da função objetivo $f (x)$ , o método das secantes, como o próprio nome indica, está relacionado às retas secantes.

Figura 3.7: Método das secantes.

Sejam $f (x)$ e as aproximações $x^{(1)}$ e $x^{(2)}$ do zero $x^{*}$ desta função (veja Figura 3.7). A iteração do método das secantes fornece:

x^{(3)} = x^{(2)} - f (x^{(2)}) \frac{x^{(2)} - x^{(1)}}{f (x^{(2)}) - f (x^{(1)})} .

(3.170)

De fato, $x^{(3)}$ é o ponto de interseção da reta secante ao gráfico de $f (x)$ pelos pontos $x^{(1)}$ e $x^{(2)}$ com o eixo das abscissas. Com efeito, a equação desta reta secante é:

y = \frac{f (x^{(2)}) - f (x^{(1)})}{x^{(2)} - x^{(1)}} (x - x^{(2)}) + f (x^{(2)}) .

(3.171)

Esta reta intercepta o eixo das abscissas no ponto $x$ tal que $y = 0$ , isto é:

\frac{f (x^{(2)}) - f (x^{(1)})}{x^{(2)} - x^{(1)}} (x - x^{(2)}) + f (x^{(2)}) \Rightarrow x = x^{(2)} - f (x^{(2)}) \frac{x^{(2)} - x^{(1)}}{f (x^{(2)}) - f (x^{(1)})} .

(3.172)

3.5.2 Análise de convergência

Uma análise assintótica semelhante àquela feita para o método de Newton na subseção 3.4.2 nos indica que, para uma função $f (x)$ duas vezes diferenciável, as iterações do método da secante satisfazem:

| x^{(n + 1)} - x^{*} | \approx C | x^{(n)} - x^{*} | | x^{(n - 1)} - x^{*} |,

(3.173)

para aproximações iniciais suficientemente próximas de $x^{*}$ , onde $f (x^{*}) = 0$ . Além disso, veremos que:

| x^{(n + 1)} - x^{*} | \leq C | x^{(n)} - x^{*} |^{p}, p = \frac{\sqrt{5} + 1}{2} \approx 1, 618

(3.174)

sob certas condições. Ou seja, o método das secantes tem taxa de convergência superlinear.

Teorema 3.5.1 (Método das secantes). Seja $f \in C^{2} ([a, b])$ uma função com $x^{*} \in (a, b)$ tal que $f (x^{*}) = 0$ . Sejam, também:

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

(3.175)

Além disso, seja $ρ > 0$ tal que:

q : = \frac{M}{2 m} ρ < 1, K_{ρ} (x^{*}) : = {x \in ℝ; | x - x^{*} | \leq ρ} \subset [a, b] .

(3.176)

Então, para aproximações iniciais $x^{(1)}, x^{(2)} \in K_{ρ} (x^{*})$ , com $x^{(1)} \neq x^{(2)}$ , temos que as iterações do método das secantes $x^{(n)} \in K_{ρ} (x^{*})$ , $n \geq 1$ , e $x^{(n)} \to x^{*}$ , quando $n \to \infty$ . Além disso, vale a seguinte estimativa de convergência a priori:

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

(3.177)

onde ${γ_{n}}_{n \in ℕ}$ é a sequência de Fibonacci⁷ ⁸ , bem como vale a estimativa a posteriori:

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

(3.178)

Demonstração. Sejam

n \in ℕ

com

n \geq 2

x^{(n)}, x^{(n - 1)} \in K_{ρ} (x^{*})

, tal que

x^{(n)} \neq x^{(n - 1)}

x^{(n)} \neq x^{*}

x^{(n - 1)} \neq x^{*}

. Seja, também:

g (x^{(n)}, x^{(n - 1)}) : = x^{(n)} - f (x^{(n)}) \frac{x^{(n)} - x^{(n - 1)}}{f (x^{(n)}) - f (x^{(n - 1)})} .

(3.179)

Com isso, temos: $\begin{array}{rcl} g (x^{(n)}, x^{(n - 1)}) - x^{*} = x^{(n)} - f (x^{(n)}) \frac{x^{(n)} - x^{(n - 1)}}{f (x^{(n)}) - f (x^{(n - 1)})} - x^{*} & (3.180) \\ = & \frac{x^{(n)} - x^{(n - 1)}}{f (x^{(n)}) - f (x^{(n - 1)})} \{(x^{(n)} - x^{*}) \frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}} - f (x^{(n)}) + f (x^{*})\} . & (3.181) \\ (3.182) \end{array}$

Então, da cota assumida para primeira derivada de $f (x)$ e do teorema do valor médio, temos:

| g (x^{(n)}, x^{(n - 1)}) - x^{*} | \leq \frac{| x^{(n)} - x^{*} |}{m} |\frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}} - \frac{f (x^{(n)}) - f (x^{*})}{x^{(n)} - x^{*}}| .

(3.183)

Agora, iremos estimar este último termo a direita. Para tanto, começamos observando que da expansão em polinômio de Taylor de ordem $0$ da função $f (x)$ com resto na forma integral, temos: $\begin{array}{rcl} \frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}} & = - \int_{0}^{1} \frac{d}{d r} f (x^{(n)} + r (x^{(n - 1)} - x^{(n)})) \frac{d r}{x^{(n)} - x^{(n - 1)}} & (3.184) \\ = \int_{0}^{1} f^{'} (x^{(n)} + r (x^{(n - 1)} - x^{(n)})) d r & (3.185) \end{array}$

De forma análoga, temos:

\frac{f (x^{(n)}) - f (x^{*})}{x^{(n)} - x^{*}} = \int_{0}^{1} f^{'} (x^{(n)} + r (x^{*} - x^{(n)})) d r

(3.186)

Logo, temos:

\begin{matrix} \begin{aligned} \frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}} - \frac{f (x^{(n)}) - f (x^{*})}{x^{(n)} - x^{*}} = \\ \int_{0}^{1} [f^{'} (x^{(n)} + r (x^{(n - 1)} - x^{(n)})) - f^{'} (x^{(n)} + r (x^{*} - x^{(n)}))] d r . \end{aligned} \end{matrix}

(3.187)

Agora, novamente temos:

\begin{matrix} \begin{aligned} f^{'} (x^{(n)} + r (x^{(n - 1)} - x^{(n)})) - f^{'} (x^{(n)} + r (x^{*} - x^{(n)})) \\ = \int_{0}^{r} \frac{d}{d s} f^{'} (x^{(n)} + r (x^{(n - 1)} - x^{(n)}) + s (x^{*} - x^{(n - 1)})) d s \\ = \int_{0}^{r} f^{″} (x^{(n)} + r (x^{(n - 1)} - x^{(n)}) + s (x^{*} - x^{(n - 1)})) d s (x^{*} - x^{(n - 1)}) . \end{aligned} \end{matrix}

(3.188)

Retornando à Equação (3.187) e usando a cota para a segunda derivada, obtemos:

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

(3.189)

Utilizando a Equação (3.183), obtemos:

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

(3.190)

Portanto, concluímos que as iterações do método da secantes $x^{(n)}$ permanecem no conjunto $K_{ρ} (x^{*})$ , se começarem nele. Além disso, temos demonstrado que:

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

(3.191)

Com isso, temos:

ρ_{n} : = \frac{M}{2 m} | x^{(n)} - x^{*} | \Rightarrow ρ_{n + 1} \leq ρ_{n} ρ_{n - 1}, n \geq 2 .

(3.192)

Como $ρ_{1} \leq q$ e $ρ_{2} \leq q$ , temos $ρ_{n} \leq q^{γ_{n - 1}}$ , $n \geq 1$ . Isto mostra a estimativa de convergência a priori:

| x^{n} - x^{*} | \leq \frac{2 m}{M} q^{γ_{n - 1}} .

(3.193)

Além disso, como $γ_{n} \to \infty$ quando $n \to \infty$ e $q < 1$ , temos que as iterações do método das secantes $x^{(n)} \to x^{*}$ quando $n \to \infty$ .

Por fim, mostramos a estimativa de convergência a posteriori. Para tanto, da cota assumida para a primeira derivada e do teorema do valor médio, temos, para $n \geq 3$ : $\begin{array}{rcl} | x^{(n)} - x^{*} | & \leq & \frac{1}{m} | f (x^{(n)} - f (x^{*}) | & (3.194) \\ = & \frac{1}{m} |f (x^{(n - 1)}) + (x^{(n)} - x^{(n - 1)}) \frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}}| & (3.195) \\ = & \frac{1}{m} |x^{(n)} - x^{(n - 1)}| |\frac{f (x^{(n)}) - f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}} + \frac{f (x^{(n - 1)})}{x^{(n)} - x^{(n - 1)}}| . & (3.196) \end{array}$

Agora, a iteração do método das secantes fornece:

x^{(n)} = x^{(n - 1)} - f (x^{(n - 1)}) \frac{x^{(n - 1)} - x^{(n - 2)}}{f (x^{(n - 1)}) - f (x^{(n - 2)})}

(3.197)

e temos:

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

(3.198)

Portanto:

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

(3.199)

Observamos que o último termo pode ser estimado como feito acima para o termo análogo na Inequação (3.183). Com isso, obtemos a estimativa desejada:

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

(3.200)

$■$

Proposição 3.5.1 (Sequência de Fibonacci). A sequência de Fibonacci ${γ_{n}}_{n \in ℕ}$ é assintótica a $γ_{n} \sim λ_{1}^{n + 1} ∕ \sqrt{5}$ e:

lim_{n \to \infty} \frac{γ_{n + 1}}{γ_{n}} = λ_{1},

(3.201)

onde $λ_{1} = (1 + \sqrt{5}) ∕ 2 \approx 1, 618$ é a porção áurea.

Demonstração. A sequência de Fibonacci

{γ_{n}}_{n \in ℕ}

é definida por

γ_{0} = γ_{1} = 1

γ_{n + 1} = γ_{n} + γ_{n - 1}

n \geq 1

. Logo, satisfaz a seguinte equação de diferenças:

γ_{n + 2} - γ_{n + 1} - γ_{n} = 0, n \in ℕ .

(3.202)

Tomando $γ_{n} = λ^{n}$ , $λ \neq 0$ temos:

λ^{n} (λ^{2} - λ - 1) = 0 \Rightarrow λ^{2} - λ - 1 = 0 \Rightarrow λ_{1, 2} = \frac{1 \pm \sqrt{5}}{2} .

(3.203)

Portanto, $γ_{n} = c_{1} λ_{1}^{n} + c_{2} λ_{2}^{n}$ . Como $γ_{0} = γ_{1} = 1$ , as constantes satisfazem:

\begin{matrix} c_{1} + c_{2} = 1 \\ c_{1} λ_{1} + c_{2} λ_{2} = 1 \end{matrix} \Rightarrow c_{1} = \frac{1 + \sqrt{5}}{2 \sqrt{5}}, c_{2} = - \frac{1 - \sqrt{5}}{2 \sqrt{5}} .

(3.204)

Ou seja, obtemos a seguinte forma explícita para os números de Fibonacci:

γ_{n} = \frac{1}{\sqrt{5}} [{(\frac{1 + \sqrt{5}}{2})}^{n + 1} - {(\frac{1 - \sqrt{5}}{2})}^{n + 1}] .

(3.205)

Daí, segue imediatamente o enunciado.

$■$

Observação 3.5.1. Sob as hipóteses do Teorema 3.5.1 e da Proposição 3.5.1, temos: $\begin{array}{rcl} lim_{n \to \infty} \frac{| x^{(n + 1)} - x^{*} |}{| x^{(n)} - x^{*} |^{λ_{1}}} & \leq & lim_{n \to \infty} \frac{M}{2 m} | x^{(n)} - x^{*} |^{1 - λ_{1}} | x^{(n - 1)} - x^{*} | & (3.206) \\ \leq & lim_{n \to \infty} {(\frac{2 m}{M})}^{1 - λ_{1}} q^{(2 - λ_{1}) λ_{1}^{n} ∕ \sqrt{5}} = 0 . & (3.207) \end{array}$

Isto mostra que o método das secantes (nestas hipóteses) tem taxa de convergência superlinear ( $λ_{1} \approx 1, 6$ ).

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!