Suponha conhecidos (n+1) pontos \left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right) \ldots,\left(x_{n}, y_{n}\right) do plano e um ponto z em D=\left[x_{0}, x_{n}\right]. Suponha que estes pontos sejam dados em 2 vetores X e Y com (n+1) posições cada, sendo que na posição 0 de X se tem gravado x_{0} e posição 0 de Y se tem gravado y_{0}, na posição 1 de X está x_{1} e na posição 1 de Y está y_{1} e assim por diante. Usando estes vetores, escreva um algoritmo (em pseudocódigo ou em uma linguagem de programação) que gere uma matriz contendo todas as diferenças divididas ascendentes (também chamadas de progressivas) possíveis de serem obtidas com estes pontos. A matriz deve conter na coluna de índice 1 as diferenças divididas de ordem 1, na coluna de índice 2 as diferenças divididas de ordem 2, e assim por diante.

Passo 1

Resumindo, temos n+1 pontos \bigl(x_{0},y_{0}\bigr),\dots,\bigl(x_{n},y_{n}\bigr) armazenados em dois vetores X e Y, e queremos montar uma tabela (matriz) de diferenças divididas progressivas de ordem 1 até n. Vamos usar a fórmula de Newton para diferenças divididas:
f[x_i,\dots,x_{i+k}] =\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i}.

Passo 2

Para organizar isso em algoritmo, criamos uma matriz D de dimensão (n+1)\times(n+1). Na coluna 0 (ordem zero) colocamos os valores de Y. Depois, para cada ordem j=1,\dots,n, calculamos
D[i][j] =\frac{D[i+1][j-1]-D[i][j-1]}{X[i+j]-X[i]}, \quad i=0,\dots,n-j.

Passo 3

Segue o pseudocódigo que gera essa matriz de diferenças divididas:
function DividedDifferences(X, Y):
 n ← length(X) − 1
 criar matriz D de dimensão (n\(+1\))×(n\(+1\)) inicializada com zeros

 // ordem zero: valores de Y
 for i from 0 to n do
 D[i][0] ← Y[i]

 // diferenças divididas de ordem j \(=1\)..n
 for j from 1 to n do
 for i from 0 to n−j do
 D[i][j] ← (D[i\(+1\)][j−1] − D[i][j−1]) / (X[\(i+j\)] − X[i])

 return D

Resposta

function DividedDifferences(X, Y):
 n ← length(X) − 1
 criar matriz D de dimensão (n\(+1\))×(n\(+1\)) inicializada com zeros

 // ordem zero: valores de Y
 for i from 0 to n do
 D[i][0] ← Y[i]

 // diferenças divididas de ordem j \(=1\)..n
 for j from 1 to n do
 for i from 0 to n−j do
 D[i][j] ← (D[i\(+1\)][j−1] − D[i][j−1]) / (X[\(i+j\)] − X[i])

 return D

Exercícios relacionados