Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

| | | |

Matemática Numérica I

5 Interpolação 5.2 Interpolação de Lagrange 5.4 Spline Cúbico

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

5.3 Diferenças Divididas de Newton

Dado um conjunto de pontos $\{(x_{i},y_{i})\}_{i=1}^{n}$ , o Método das Diferenças Divididas de Newton⁴⁹⁴⁹endnote: ⁴⁹Isaac Newton, 1642 - 1727, matemático, físico, astrônomo, teólogo e autor inglês. Fonte: Wikipédia: Isaac Newton. busca determinar o polinômio interpolador da forma

$\displaystyle p(x)$	$\displaystyle=a_{1}+a_{2}(x-x_{1})$	(5.28)
	$\displaystyle+a_{3}(x-x_{1})(x-x_{2})$
	$\displaystyle+\cdots+a_{n}(x-x_{1})\cdots(x-x_{n-1}).$

Por uma abordagem direta, temos que $p(x_{i})=y_{i}$ , $i=1,2,\dotsc,n$ , o que nos leva ao seguinte sistema triangular inferior

		$\displaystyle a_{1}=y_{1},$		(5.29)
		$\displaystyle a_{1}+a_{2}(x_{2}-x_{1})=y_{2},$
		$\displaystyle a_{1}+a_{2}(x_{3}-x_{1})+a_{3}(x_{3}-x_{1})(x_{3}-x_{2})=y_{3},$
		$\displaystyle\text{}\qquad\qquad\qquad\vdots$
		$\displaystyle a_{1}+a_{2}(x_{n}-x_{1})+\cdots+a_{n}(x_{n}-x_{1})\cdots(x_{n}-x% _{n-1})=y_{n}.$

Entretanto, existe uma forma mais eficiente de se determinar os coeficientes $a_{i}$ , $i=1,2,\dotsc,n$ .

Denotemos por $p[x_{j},x_{j+1},\dotsc,x_{k}](x)$ o polinômio interpolador do conjunto de pontos $\{(x_{i},y_{i})\}_{i=j}^{k}$ . Então, temos a seguinte recursão

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}p[x_{j}]=y_{j},

(5.30)

para $j=1,2,\dotsc,n$ e

		$\displaystyle p[x_{j},x_{j+1},\ldots,x_{k}](x)$		(5.31)
		$\displaystyle\quad=\frac{(x-x_{j})p[x_{j+1},\dotsc,x_{k}](x)-(x-x_{k})p[x_{j},% \dotsc,x_{k-1}](x)}{x_{k}-x_{j}},$		(5.31)

para todo $n\geq k>j\geq 1$ .

De fato, (5.30) é trivial. Agora, denotando por $r(x)$ o lado direito da equação (5.31), vemos que $r(x)$ tem grau menor ou igual a $k-j$ , o mesmo de $p[x_{j},x_{j+1},\ldots,x_{k}](x)$ . Desta forma, para mostrar (5.31), basta verificarmos que $r(x)$ interpola o conjunto de pontos $\{(x_{i},y_{i})\}_{i=j}^{k}$ . O que de fato ocorre

	$\displaystyle r(x_{j})=\frac{-(x_{j}-x_{k})y_{j}}{x_{k}-x_{j}}=y_{j},$		(5.32a)
	$\displaystyle r(x_{l})=\frac{(x_{l}-x_{j})y_{l}-(x_{l}-x_{k})y_{l}}{x_{k}-x_{j% }}=y_{l},$
	$\displaystyle\qquad\qquad\qquad\qquad l=j+1,\dotsc,k-1,$		(5.32b)
	$\displaystyle r(x_{k})=\frac{(x_{k}-x_{j})y_{k}}{x_{k}-x_{j}}=y_{k}.$		(5.32c)

Logo, pela unicidade do polinômio interpolador⁵⁰⁵⁰endnote: ⁵⁰Consulte o Exercício 5.3.5, temos demonstrado (5.31).

Observando que o polinômio interpolador $p(x)$ é igual a $p[x_{1},\dotsc,x_{n}](x)$ , temos que (5.30)-(5.31) nos fornece uma forma de computar $p(x)$ de forma recursiva. Além disso, observemos que $p[x_{j},\dotsc,x_{k-1}](x)$ e $p[x_{j},\dotsc,x_{k}]$ diferem por um polinômio de grau $k-j$ com zeros $x_{j}$ , $x_{j+1}$ , …, $x_{k-1}$ . Logo, temos

		$\displaystyle p[x_{j},\dotsc,x_{k}](x)=p[x_{j},\dotsc,x_{k-1}](x)$		(5.33)
		$\displaystyle\qquad+f[x_{j},\dotsc,x_{k}](x-x_{j})\cdots(x-x_{k-1}),$		(5.33)

onde $f[x_{j},\dotsc,x_{k}]$ são coeficientes a determinar. Ainda, tomando $p[x_{i}]=f[x_{i}]$ , temos

		$\displaystyle p[x_{j},\dotsc,x_{k}](x)=f[x_{j}]+f[x_{j},x_{j+1}](x-x_{j})$		(5.34)
		$\displaystyle\qquad+f[x_{j},\dotsc,x_{k}](x-x_{j})\cdots(x-x_{k-1}).$		(5.34)

Por fim, a recursão (5.30)-(5.31) nos mostra que as Diferenças Divididas Newton podem ser obtidas de

	$\displaystyle f[x_{j}]=y_{j},\quad j=1,2,\dotsc,n,$		(5.35a)
	$\displaystyle f[x_{j},\dotsc,x_{k}]=\frac{f[x_{j+1},\dotsc,x_{k}]-f[x_{j},% \dotsc,x_{k-1}]}{x_{k}-x_{j}},$		(5.35b)

para todo $n\geq k>j\geq 1$ . E, temos o polinômio interpolador do conjunto de pontos $\{(x_{i},y_{i})\}_{i=1}^{n}$ dado por

		$\displaystyle p[x_{1},\dotsc,x_{n}](x)=f[x_{1}]+f[x_{1},x_{2}](x-x_{1})$		(5.36)
		$\displaystyle\qquad+\cdots+f[x_{1},\dotsc,x_{n}](x-x_{1})\cdots(x-x_{n}).$		(5.36)

Observação 5.3.1.

A recursão (5.3) pode ser adequadamente organizada em uma matriz da forma

\begin{bmatrix}\boldsymbol{f[x_{1}]}&0&\ldots&0\\ f[x_{2}]&\boldsymbol{f[x_{1},x_{2}]}&\ldots&0\\ f[x_{3}]&f[x_{2},x_{3}]&\ldots&0\\ \vdots&\vdots&\ldots&\vdots\\ f[x_{n}]&f[x_{n-1},x_{n}]&\ldots&\boldsymbol{f[x_{1},\dotsc,x_{n}]}\end{bmatrix}

(5.37)

onde os elementos da diagonal correspondem aos coeficientes do polinômio interpolador na forma (5.36).

Exemplo 5.3.1.

Consideramos o problema de encontrar o polinômio interpolador do conjunto de pontos $\{(-1,-1),(0,1),(1,1/2)\}$ . Usando o Método das Diferenças Divididas de Newton, escrevemos o polinômio na forma

p(x)=f[x_{1}]+f[x_{1},x_{2}](x-x_{1})+f[x_{1},x_{2},x_{3}](x-x_{1})(x-x_{2}).

(5.38)

Então, computamos seus coeficientes pela recursão (5.3). Ou seja, temos

	$\displaystyle f[x_{1}]=-1,$		(5.39a)
	$\displaystyle f[x_{2}]=1,$		(5.39b)
	$\displaystyle f[x_{3}]=1/2.$		(5.39c)

Daí, segue

	$\displaystyle f[x_{1},x_{2}]=\frac{f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}=2$		(5.40a)
	$\displaystyle f[x_{2},x_{3}]=\frac{f[x_{3}]-f[x_{2}]}{x_{3}-x_{2}}=-\frac{1}{2}$		(5.40b)

e, por fim, que

	$\displaystyle f[x_{1},x_{2},x_{3}]=\frac{f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-% x_{1}}$		(5.41a)
	$\displaystyle\qquad\quad=-1.25.$		(5.41b)

Logo, o polinômio interpolador é

p(x)=0.5+2(x+1)-1.25(x+1)(x-1),

(5.42)

ou, equivalentemente,

p(x)=-1.25x^{2}+0.75x+1.

(5.43)

⬇

1import numpy as np

3def interpDDF(x, y):

4 n = x.size

5 M = np.empty((n,n))

6 M[:,0] = y

7 for j in range(1,n):

8 for i in range(j,n):

9 M[i,j] = (M[i,j-1] - M[i-1,j-1]) \

10 / (x[i]-x[i-j])

11 return np.diag(M)

13def poliDDF(x, p, xpts):

14 n = p.size

15 pval = p[0]

16 aux = 1.

17 for i in range(1,n):

18 aux *= (x-xpts[i-1])

19 pval += p[i]*aux

20 return pval

22xpts = np.array([-1., 0, 1])

23ypts = np.array([-1., 1, 1/2])

24p = interpDDF(xpts, ypts)

25print(poliDDF(xpts, p, xpts))

5.3.1 Exercícios

E. 5.3.1.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(-0.5,1),(1,2)\}$ .

Resposta.

$-1,\bar{6}x^{2}+1.5x+2.1\bar{6}$

E. 5.3.2.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(0,1),(1,1/2),(2,1)\}$ .

Resposta.

$0.58\bar{3}x^{3}-1.25x^{2}+0.1\bar{6}x+1$ .

E. 5.3.3.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(0,1),(1,1/2),(2,1),(2.5,1)\}$ .

Resposta.

$-0.26190476x^{4}1.10714286x^{3}-0.98809524x^{2}-0.35714286x1$ .

E. 5.3.4.

Use o método das diferenças divididas de Newton para encontrar o polinômio interpolador que aproxima a função $f(x)=e^{x}$ pelos pontos $x_{1}=0$ , $x_{2}=1$ , $x_{3}=1.5$ e $x_{4}=2$ .

Resposta.

$p(x)=0.54x^{3}-0.15x^{2}+1.3x+1$ .

Análise Numérica

E. 5.3.5.

Dado um conjunto de pontos distintos $\{(x_{i},y_{i})\}_{i=1}^{n}$ , mostre que é único o polinômio interpolador do conjunto.

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.

Matemática Numérica I

5 Interpolação 5.2 Interpolação de Lagrange 5.4 Spline Cúbico

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

5.3 Diferenças Divididas de Newton

$\displaystyle p(x)$	$\displaystyle=a_{1}+a_{2}(x-x_{1})$	(5.28)
	$\displaystyle+a_{3}(x-x_{1})(x-x_{2})$
	$\displaystyle+\cdots+a_{n}(x-x_{1})\cdots(x-x_{n-1}).$

Por uma abordagem direta, temos que $p(x_{i})=y_{i}$ , $i=1,2,\dotsc,n$ , o que nos leva ao seguinte sistema triangular inferior

		$\displaystyle a_{1}=y_{1},$		(5.29)
		$\displaystyle a_{1}+a_{2}(x_{2}-x_{1})=y_{2},$
		$\displaystyle a_{1}+a_{2}(x_{3}-x_{1})+a_{3}(x_{3}-x_{1})(x_{3}-x_{2})=y_{3},$
		$\displaystyle\text{}\qquad\qquad\qquad\vdots$
		$\displaystyle a_{1}+a_{2}(x_{n}-x_{1})+\cdots+a_{n}(x_{n}-x_{1})\cdots(x_{n}-x% _{n-1})=y_{n}.$

Entretanto, existe uma forma mais eficiente de se determinar os coeficientes $a_{i}$ , $i=1,2,\dotsc,n$ .

Denotemos por $p[x_{j},x_{j+1},\dotsc,x_{k}](x)$ o polinômio interpolador do conjunto de pontos $\{(x_{i},y_{i})\}_{i=j}^{k}$ . Então, temos a seguinte recursão

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}p[x_{j}]=y_{j},

(5.30)

para $j=1,2,\dotsc,n$ e

		$\displaystyle p[x_{j},x_{j+1},\ldots,x_{k}](x)$		(5.31)
		$\displaystyle\quad=\frac{(x-x_{j})p[x_{j+1},\dotsc,x_{k}](x)-(x-x_{k})p[x_{j},% \dotsc,x_{k-1}](x)}{x_{k}-x_{j}},$		(5.31)

para todo $n\geq k>j\geq 1$ .

	$\displaystyle r(x_{j})=\frac{-(x_{j}-x_{k})y_{j}}{x_{k}-x_{j}}=y_{j},$		(5.32a)
	$\displaystyle r(x_{l})=\frac{(x_{l}-x_{j})y_{l}-(x_{l}-x_{k})y_{l}}{x_{k}-x_{j% }}=y_{l},$
	$\displaystyle\qquad\qquad\qquad\qquad l=j+1,\dotsc,k-1,$		(5.32b)
	$\displaystyle r(x_{k})=\frac{(x_{k}-x_{j})y_{k}}{x_{k}-x_{j}}=y_{k}.$		(5.32c)

Logo, pela unicidade do polinômio interpolador⁵⁰⁵⁰endnote: ⁵⁰Consulte o Exercício 5.3.5, temos demonstrado (5.31).

		$\displaystyle p[x_{j},\dotsc,x_{k}](x)=p[x_{j},\dotsc,x_{k-1}](x)$		(5.33)
		$\displaystyle\qquad+f[x_{j},\dotsc,x_{k}](x-x_{j})\cdots(x-x_{k-1}),$		(5.33)

onde $f[x_{j},\dotsc,x_{k}]$ são coeficientes a determinar. Ainda, tomando $p[x_{i}]=f[x_{i}]$ , temos

		$\displaystyle p[x_{j},\dotsc,x_{k}](x)=f[x_{j}]+f[x_{j},x_{j+1}](x-x_{j})$		(5.34)
		$\displaystyle\qquad+f[x_{j},\dotsc,x_{k}](x-x_{j})\cdots(x-x_{k-1}).$		(5.34)

Por fim, a recursão (5.30)-(5.31) nos mostra que as Diferenças Divididas Newton podem ser obtidas de

	$\displaystyle f[x_{j}]=y_{j},\quad j=1,2,\dotsc,n,$		(5.35a)
	$\displaystyle f[x_{j},\dotsc,x_{k}]=\frac{f[x_{j+1},\dotsc,x_{k}]-f[x_{j},% \dotsc,x_{k-1}]}{x_{k}-x_{j}},$		(5.35b)

para todo $n\geq k>j\geq 1$ . E, temos o polinômio interpolador do conjunto de pontos $\{(x_{i},y_{i})\}_{i=1}^{n}$ dado por

		$\displaystyle p[x_{1},\dotsc,x_{n}](x)=f[x_{1}]+f[x_{1},x_{2}](x-x_{1})$		(5.36)
		$\displaystyle\qquad+\cdots+f[x_{1},\dotsc,x_{n}](x-x_{1})\cdots(x-x_{n}).$		(5.36)

Observação 5.3.1.

A recursão (5.3) pode ser adequadamente organizada em uma matriz da forma

\begin{bmatrix}\boldsymbol{f[x_{1}]}&0&\ldots&0\\ f[x_{2}]&\boldsymbol{f[x_{1},x_{2}]}&\ldots&0\\ f[x_{3}]&f[x_{2},x_{3}]&\ldots&0\\ \vdots&\vdots&\ldots&\vdots\\ f[x_{n}]&f[x_{n-1},x_{n}]&\ldots&\boldsymbol{f[x_{1},\dotsc,x_{n}]}\end{bmatrix}

(5.37)

onde os elementos da diagonal correspondem aos coeficientes do polinômio interpolador na forma (5.36).

Exemplo 5.3.1.

p(x)=f[x_{1}]+f[x_{1},x_{2}](x-x_{1})+f[x_{1},x_{2},x_{3}](x-x_{1})(x-x_{2}).

(5.38)

Então, computamos seus coeficientes pela recursão (5.3). Ou seja, temos

	$\displaystyle f[x_{1}]=-1,$		(5.39a)
	$\displaystyle f[x_{2}]=1,$		(5.39b)
	$\displaystyle f[x_{3}]=1/2.$		(5.39c)

Daí, segue

	$\displaystyle f[x_{1},x_{2}]=\frac{f[x_{2}]-f[x_{1}]}{x_{2}-x_{1}}=2$		(5.40a)
	$\displaystyle f[x_{2},x_{3}]=\frac{f[x_{3}]-f[x_{2}]}{x_{3}-x_{2}}=-\frac{1}{2}$		(5.40b)

e, por fim, que

	$\displaystyle f[x_{1},x_{2},x_{3}]=\frac{f[x_{2},x_{3}]-f[x_{1},x_{2}]}{x_{3}-% x_{1}}$		(5.41a)
	$\displaystyle\qquad\quad=-1.25.$		(5.41b)

Logo, o polinômio interpolador é

p(x)=0.5+2(x+1)-1.25(x+1)(x-1),

(5.42)

ou, equivalentemente,

p(x)=-1.25x^{2}+0.75x+1.

(5.43)

⬇

1import numpy as np

3def interpDDF(x, y):

4 n = x.size

5 M = np.empty((n,n))

6 M[:,0] = y

7 for j in range(1,n):

8 for i in range(j,n):

9 M[i,j] = (M[i,j-1] - M[i-1,j-1]) \

10 / (x[i]-x[i-j])

11 return np.diag(M)

13def poliDDF(x, p, xpts):

14 n = p.size

15 pval = p[0]

16 aux = 1.

17 for i in range(1,n):

18 aux *= (x-xpts[i-1])

19 pval += p[i]*aux

20 return pval

22xpts = np.array([-1., 0, 1])

23ypts = np.array([-1., 1, 1/2])

24p = interpDDF(xpts, ypts)

25print(poliDDF(xpts, p, xpts))

5.3.1 Exercícios

E. 5.3.1.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(-0.5,1),(1,2)\}$ .

Resposta.

$-1,\bar{6}x^{2}+1.5x+2.1\bar{6}$

E. 5.3.2.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(0,1),(1,1/2),(2,1)\}$ .

Resposta.

$0.58\bar{3}x^{3}-1.25x^{2}+0.1\bar{6}x+1$ .

E. 5.3.3.

Use o Método das Diferenças Divididas de Newton para obter o polinômio interpolador do conjunto de pontos $\{(-1,-1),(0,1),(1,1/2),(2,1),(2.5,1)\}$ .

Resposta.

$-0.26190476x^{4}1.10714286x^{3}-0.98809524x^{2}-0.35714286x1$ .

E. 5.3.4.

Use o método das diferenças divididas de Newton para encontrar o polinômio interpolador que aproxima a função $f(x)=e^{x}$ pelos pontos $x_{1}=0$ , $x_{2}=1$ , $x_{3}=1.5$ e $x_{4}=2$ .

Resposta.

$p(x)=0.54x^{3}-0.15x^{2}+1.3x+1$ .

Análise Numérica

E. 5.3.5.

Dado um conjunto de pontos distintos $\{(x_{i},y_{i})\}_{i=1}^{n}$ , mostre que é único o polinômio interpolador do conjunto.

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.

Pedro H A Konzen

| | | |