Critérios de parada

Cálculo Numérico - Versão Python

3.6 Critérios de parada

Quando usamos métodos iterativos precisamos determinar um critério de parada. A Tabela 3.4 indica critérios de parada usuais para os métodos que estudamos neste capítulo.

Tabela 3.4: Quadro comparativo.


Método	Convergência	Erro	Critério de parada

Bisseção	Linear	$ϵ_{n + 1} = \frac{1}{2} ϵ$	$\frac{b_{n} - a_{n}}{2} < erro$
	( $p = 1$ )

Iteração	Linear	$ϵ_{n + 1} \approx \| ϕ^{'} (x^{*}) \| ε_{n}$	$\begin{matrix} \frac{\| Δ_{n} \|}{1 - \frac{Δ_{n}}{Δ_{n - 1}}} < erro \\ Δ_{n} < Δ_{n - 1} \end{matrix}$
linear	( $p = 1$ )

Newton	Quadrática	$ϵ_{n + 1} \approx \frac{1}{2} \|\frac{f^{″} (x^{})}{f^{'} (x^{})}\| ε_{n}^{2}$	$\| Δ_{n} \| < erro$
	( $p = 2$ )

Secante	$\begin{matrix} p & = \frac{\sqrt{5} + 1}{2} \\ \approx 1, 618 \end{matrix}$	$\begin{matrix} ε_{n + 1} & \approx \|\frac{f^{″} (x^{})}{f^{'} (x^{})}\| ε_{n} ε_{n - 1} \\ \approx M ε_{n}^{ϕ} \end{matrix}$	$\| Δ_{n} \| < erro$

Observação 3.6.1. O erro na tabela sempre se refere ao erro absoluto esperado. Nos três últimos métodos, é comum que se exija como critério de parada que a condição seja satisfeita por alguns poucos passos consecutivos. Outros critérios podem ser usados. No métodos das secantes, deve-se ter o cuidado de evitar divisões por zero quando $x_{n + 1} - x_{n}$ muito pequeno em relação à resolução do sistema de numeração.

Exercícios

E 3.6.1. Refaça as questões 3.4.3, 3.4.4, 3.4.5 e 3.4.6, usando o método das secantes.

E 3.6.2. Dê uma interpretação geométrica ao método das secantes. Qual a vantagem do método das secantes sobre o método de Newton?

E 3.6.3. Aplique o método das secantes para resolver a equação

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

(3.199)

E 3.6.4. Refaça o Problema 3.2.8 usando o método de Newton e das secantes.

E 3.6.5. Seja uma função $f (x)$ dada duas vezes continuamente diferenciável. Faça uma análise assintótica para mostrar que as iterações do método das secantes satisfazem:

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

(3.200)

para aproximações iniciais $x^{(1)}$ e $x^{(2)}$ suficientemente próximas de $x^{*}$ , onde $f (x^{*}) = 0$ .

Resposta. Seja

f (x) \in C^{2}

um função tal que

f (x^{*}) = 0

f^{'} (x^{*}) \neq 0

. Considere o processo iterativo do método das secantes:

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

(3.201)

Esta expressão pode ser escrita como: $\begin{array}{rcl} x^{(n + 1)} & = & x^{(n)} - \frac{f (x^{(n)}) (x^{(n)} - x^{(n - 1)})}{f (x^{(n)}) - f (x^{(n - 1)})} & (3.202) \\ (3.203) \\ = & \frac{x^{(n)} (f (x^{(n)}) - f (x^{(n - 1)})) - f (x^{(n)}) (x^{(n)} - x^{(n - 1)})}{f (x^{(n)}) - f (x^{(n - 1)})} & (3.204) \\ = & \frac{x^{(n)} f (x^{(n - 1)}) - x^{(n - 1)} f (x^{(n)})}{f (x^{(n)}) - f (x^{(n - 1)})} & (3.205) \end{array}$

Subtraindo $x^{*}$ de ambos os lados temos: $\begin{array}{rcl} x^{(n + 1)} - x^{*} & = & \frac{x^{(n)} f (x^{(n - 1)}) - x^{(n - 1)} f (x^{(n)})}{f (x^{(n)}) - f (x^{(n - 1)})} - x^{*} & (3.206) \\ = & \frac{x^{(n)} f (x^{(n - 1)}) - x^{(n - 1)} f (x^{(n)}) - x^{*} (f (x^{(n)}) - f (x^{(n - 1)}))}{f (x^{(n)}) - f (x^{(n - 1)})} & (3.207) \\ = & \frac{(x^{(n)} - x^{*}) f (x^{(n - 1)}) - (x^{(n - 1)} - x^{*}) f (x^{(n)})}{f (x^{(n)}) - f (x^{(n - 1)})} & (3.208) \end{array}$

Definimos $ϵ_{n} = x_{n} - x^{*}$ , equivalente a $x_{n} = x^{*} + ϵ_{n}$ $\begin{array}{rcl} ϵ_{n + 1} & = & \frac{ϵ_{n} f (x^{*} + ϵ_{n - 1}) - ϵ_{n - 1} f (x^{*} + ϵ_{n})}{f (x^{*} + ϵ_{n}) - f (x^{*} + ϵ_{n - 1})} & (3.209) \end{array}$

Aproximamos a função $f (x)$ no numerador por $\begin{array}{rcl} f (x^{*} + ϵ) & \approx & f (x^{*}) + ϵ f^{'} (x^{*}) + ϵ^{2} \frac{f^{″} (x^{*})}{2} & (3.210) \\ f (x^{*} + ϵ) & \approx & ϵ f^{'} (x^{*}) + ϵ^{2} \frac{f^{″} (x^{*})}{2} & (3.211) \end{array}$

$\begin{array}{rcl} ϵ_{n + 1} & \approx & \frac{ϵ_{n} [ϵ_{n - 1} f^{'} (x^{*}) + ϵ_{n - 1}^{2} \frac{f^{″} (x^{*})}{2}] - ϵ_{n - 1} [ϵ_{n} f^{'} (x^{*}) + ϵ_{n}^{2} \frac{f^{″} (x^{*})}{2}]}{f (x^{*} + ϵ_{n}) - f (x^{*} + ϵ_{n - 1})} & (3.212) \\ = & \frac{\frac{f^{″} (x^{*})}{2} (ϵ_{n} ϵ_{n - 1}^{2} - ϵ_{n - 1} ϵ_{n}^{2})}{f (x^{*} + ϵ_{n}) - f (x^{*} + ϵ_{n - 1})} & (3.213) \\ = & \frac{1}{2} f^{″} (x^{*}) \frac{ϵ_{n} ϵ_{n - 1} (ϵ_{n - 1} - ϵ_{n})}{f (x^{*} + ϵ_{n}) - f (x^{*} + ϵ_{n - 1})} & (3.214) \end{array}$