Matemática Numérica I

2 Equação com Uma Incógnita 2.3 Iteração de Ponto Fixo 2.5 Método de Newton

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

2.4 Método de Steffensen

O método de Steffensen¹⁸¹⁸endnote: ¹⁸Johan Frederik Steffensen, 1873 - 1961, matemático e estatístico dinamarquês. Fonte: Wikipédia. é uma aplicação do método de aceleração de convergência $\Delta^{2}$ de Aitken¹⁹¹⁹endnote: ¹⁹Alexander Aitken, 1895 - 1967, matemático neozelandês. Fonte: Wikipédia. à iteração de ponto fixo.

2.4.1 Acelerador $\Delta^{2}$ de Aitken

Seja dada uma sequência $(x^{(k)})_{k=1}^{\infty}$ monotonicamente convergente para $x^{*}$ . Assumimos que $k$ seja suficientemente grande tal que

\frac{x^{(k+1)}-x^{*}}{x^{(k)}-x^{*}}\approx\frac{x^{(k+2)}-x^{*}}{x^{(k+1)}-x% ^{*}}.

(2.101)

Então, isolando $x^{*}$ obtemos

x^{*}\approx\frac{x^{(k)}x^{(k+2)}-(x^{(k+1)})^{2}}{x^{(k)}-2x^{(k+1)}+x^{(k+2% )}}.

(2.102)

Ainda, somando e subtraindo $(x^{(k)})^{2}$ e $2x^{(k)}x^{(k+1)}$ no numerador acima e rearranjando os termos, obtemos

x^{*}\approx x^{(k)}-\frac{(x^{(k+1)}-x^{(k)})^{2}}{x^{(k+2)}-2x^{(k+1)}+x^{(k% )}}.

(2.103)

O observado acima, nos motiva a introduzir o acelerador $\Delta^{2}$ de Aitken

{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Delta^{2}\{% x^{(k)},x^{(k+1)},x^{(k+2)}\}:=x^{(k)}-\frac{(x^{(k+1)}-x^{(k)})^{2}}{x^{(k+2)% }-2x^{(k+1)}+x^{(k)}}}.

(2.104)

Exemplo 2.4.1.

Consideremos o problema de encontrar o zero da função

	$\displaystyle f(x)$	$\displaystyle=\operatorname{sen}^{2}\left(x+\frac{\pi}{4}\right)-x^{3}$		(2.105)
		$\displaystyle+\frac{\pi}{4}x^{2}+\frac{5\pi^{2}}{16}x+\frac{3\pi^{3}}{64}.$		(2.105)

no intervalo $[2,3]$ . Para tanto, podemos aplicar a iteração de ponto fixo dada por

	$\displaystyle x^{(k+1)}$	$\displaystyle=g(x^{(k)})$		(2.106)
		$\displaystyle:=x^{(k)}-\alpha f(x^{(k)}),\quad k=1,2,\ldots,$		(2.106)

com $\alpha=-0.05$ e $x^{(0)}=2.6$ . Na Tabela 2.4 temos os valores das iteradas $x^{(k)}$ e das correções $\Delta^{2}=\Delta^{2}\{x^{(k)},x^{(k+1)},x^{(k+2)}\}$ de Aitken. Neste caso, a aceleração de convergência é notável.

Tabela 2.4: Resultados referentes ao Exemplo 2.4.1.

$k$	$x^{(k)}$	$\Delta^{2}$
0	$2.6000$	-x-
1	$2.4632$	-x-
2	$2.4073$	$2.3687$
3	$2.3814$	$2.3590$
4	$2.3688$	$2.3569$
5	$2.3625$	$2.3564$
6	$2.3594$	$2.3562$
7	$2.3578$	$2.3562$

⬇

1import numpy as np

3# fun obj

4f = lambda x: np.sin(x+np.pi/4)**2 \

5 - x**3 + np.pi/4*x**2 + 5*np.pi**2/16*x \

6 + 3*np.pi**3/64

8# fun pto fixo

9alpha = -0.05

10g = lambda x: x - alpha*f(x)

12x0 = 2.6

13print(f'\n1: {x0:.4f}')

14for k in range(7):

15 x1 = g(x0)

16 x2 = g(x1)

17 x = x0 - (x1-x0)**2/(x2-2*x1+x0)

18 print(f'\n{k+2}: {x1:.4f}, {x:.4f}')

19 x0 = x1

2.4.2 Análise Numérica

Definição 2.4.1.

(Diferença Progressiva.) Para uma sequência $\left(x^{(k)}\right)_{k=1}^{\infty}$ , $\Delta x^{(k)}$ denota o operador de diferença progressiva e é definido por

\Delta x^{(k)}:=x^{(k+1)}-x^{(k)}

(2.107)

Potências maiores do operador são definidas recursivamente por

\Delta^{n}x^{(k)}=\Delta\left(\Delta^{n-1}x^{(k)}\right),\quad n\geq 2.

(2.108)

Da definição acima, temos que

$\displaystyle\Delta^{2}x^{(k)}$	$\displaystyle:=\Delta\left(\delta x^{(k)}\right)$	(2.109)
	$\displaystyle=\Delta\left(x^{(k+1)}-x^{(k)}\right)$	(2.110)
	$\displaystyle=\Delta x^{(k+1)}-\Delta x^{(k)}$	(2.111)
	$\displaystyle=\left(x^{(k+2)}-x^{(k+1)}\right)-\left(x^{(k+1)}-x^{(k)}\right)$	(2.112)
	$\displaystyle=x^{(k+2)}-2x^{(k+1)}+x^{(k)}$	(2.113)

Com isso, temos que o acelerador $\Delta^{2}$ de Aitken (2.104) pode ser reescrito como

{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Delta^{2}% \left\{x^{(k)},x^{(k+1)},x^{(k+2)}\right\}:=x^{(k)}-\frac{\left(\Delta x^{(k)}% \right)^{2}}{\Delta^{2}x^{(k)}}}.

(2.114)

Teorema 2.4.1.

Seja $\left(x^{(k)}\right)_{k=1}^{\infty}$ uma sequência linearmente convergente para $x^{*}$ e

\lim_{k\to\infty}\frac{x^{(k+1)}-x^{*}}{x^{(k)}-x^{*}}<1.

(2.115)

Então, a sequência $\Delta^{2}$ de Aitken $\left(\hat{x}^{(k)}\right)_{k=1}^{\infty}$ , com

\hat{x}^{(k)}:=\Delta^{2}\left\{x^{(k)},x^{(k+1)},x^{(k+2)}\right\},

(2.116)

converge para $x^{*}$ mais rápido que $\left(x^{(k)}\right)$ no sentido de que

\lim_{k\to\infty}\frac{\hat{x}^{(k)}-x^{*}}{x^{(k)}-x^{*}}=0.

(2.117)

Demonstração.

Em construção …∎

2.4.3 Algoritmo de Steffensen

O método de Steffensen consiste em aplicar o acelerador $\Delta^{2}$ de Aitken à iteração de ponto fixo. Mais especificamente, sejam uma aproximação inicial $x^{(0)}$ e uma iteração de ponto fixo

x^{(k+1)}=g(x^{(k)}),\quad k=0,1,2,\ldots.

(2.118)

O algoritmo de Steffensen consiste em:

1.

$x\leftarrow x^{(0)}$ .
2.
Para $k=0,1,2,\dotsc,N-1$ :
1. (a)
  
  $x_{1}\leftarrow g(x)$ .
2. (b)
  
  $x_{2}\leftarrow g(x_{1})$ .
3. (c)
  
  $x^{(k+1)}\leftarrow\Delta^{2}\{x,x_{1},x_{2}\}$ .
4. (d)
  
  $x\leftarrow x^{(k+1)}$ .

Exemplo 2.4.2.

Retornamos ao exemplo anterior (Exemplo 2.4.1. Na Tabela 2.5 temos os valores das iteradas de Steffensen $x^{(k)}$ e do indicador de convergência $|x^{(k)}-x^{(k-1)}|$ .

Tabela 2.5: Resultados referentes ao Exemplo 2.4.2.

$k$	$x^{(k)}$	$\|x^{(k)}-x^{(k-1)}\|$
0	$2.6000$	-x-
1	$2.3687$	$2.3\mathrm{e}\!-\!1$
2	$2.3562$	$1.2\mathrm{e}\!-\!2$
3	$2.3562$	$4.2\mathrm{e}\!-\!5$

⬇

1import numpy as np

3# fun obj

4f = lambda x: np.sin(x+np.pi/4)**2 \

5 - x**3 + np.pi/4*x**2 + 5*np.pi**2/16*x \

6 + 3*np.pi**3/64

8# fun pto fixo

9alpha = -0.05

10g = lambda x: x - alpha*f(x)

12x0 = 2.6

13print(f'\n1: {x0:.4f}')

14for k in range(3):

15 x1 = g(x0)

16 x2 = g(x1)

17 x = x0 - (x1-x0)**2/(x2-2*x1+x0)

18 nd = np.fabs(x-x0)

19 print(f'\n{k+2}: {x:.4f}, {nd:.1e}')

20 x0 = x

Exercícios

E. 2.4.1.

Use o método de Steffensen para obter uma aproximação do zero de $f(x)=x^{3}\operatorname{sen}(x)-\cos(x)$ no intervalo $[0.5,1]$ com precisão de $10^{-6}$ .

$9.15811\times 10^{-1}$

E. 2.4.2.

Use o Método da Iteração de Ponto Fixo para aproximar um zero de

f(x)=x^{3}\operatorname{sen}(x)-\cos(x)

(2.119)

no intervalo inicial $[0.5,1]$ .

E. 2.4.3.

Use o Método de Steffensen para computar a(s) solução(ões) das seguintes equações com precisão de 8 dígitos significativos.

a)

$x=2^{-x}$ para $0\leq x\leq 2$ .
b)

$e^{-x^{2}}=3x-x^{2}$ para $-1\leq x\leq 4$ .

a) $6.4118574\times 10^{-1}$ ; b) $3.3536470\times 10^{-1}$ ; $2.9999589$

E. 2.4.4.

Use o Método de Steffensen para encontrar uma aproximação com precisão de $4$ dígitos significativos do zero de

f(x)=(-x^{2}+1.154x-0.332929)\cos(x)+x^{2}-1.154x+0.332929

(2.120)

no intervalo $[-1,0]$ .

$-7.861\times 10^{-1}$

E. 2.4.5.

Use o Método de Steffensen para encontrar uma aproximação com precisão de $10^{-4}$ do zero de

	$\displaystyle f(x)$	$\displaystyle=(-x^{2}+1.154x-0.332929)\cos(x)+x^{2}$		(2.121)
		$\displaystyle-1.154x+0.332929$		(2.121)

no intervalo $(0.55,0.65)$ . Forneça a aproximação computada com $7$ dígitos significativos por arredondamento.

$5.770508\times 10^{-1}$

E. 2.4.6.

Use o Método de Steffensen para encontrar o ponto crítico²⁰²⁰endnote: ²⁰Definimos que $x$ é ponto crítico de uma dada $f$ , quando $f^{\prime}(x)=0$ ou $\nexists f^{\prime}(x)$ . de

f(x)=(1-x^{2})e^{-x^{2}}

(2.122)

no intervalo $(0,2)$ . Obtenha o resultado com precisão de $5$ dígitos significativos por arredondamento.

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados

Política de uso de dados

Matemática Numérica I

2.4 Método de Steffensen

2.4.1 Acelerador $\Delta^{2}$ de Aitken

Exemplo 2.4.1.

2.4.2 Análise Numérica

Definição 2.4.1.

Teorema 2.4.1.

Demonstração.

2.4.3 Algoritmo de Steffensen

Exemplo 2.4.2.

Exercícios

E. 2.4.1.

E. 2.4.2.

E. 2.4.3.

E. 2.4.4.

E. 2.4.5.

E. 2.4.6.

Envie seu comentário

Política de uso de dados

Política de uso de dados

Matemática Numérica I

2.4 Método de Steffensen

2.4.1 Acelerador Δ2 de Aitken

Exemplo 2.4.1.

2.4.2 Análise Numérica

Definição 2.4.1.

Teorema 2.4.1.

Demonstração.

2.4.3 Algoritmo de Steffensen

Exemplo 2.4.2.

Exercícios

E. 2.4.1.

E. 2.4.2.

E. 2.4.3.

E. 2.4.4.

E. 2.4.5.

E. 2.4.6.

Envie seu comentário

2.4.1 Acelerador $\Delta^{2}$ de Aitken