Suponha conhecidos
pontos
do plano e um ponto
em
. Suponha que estes pontos sejam dados em 2 vetores X e Y com
posições cada, sendo que na posição 0 de X se tem gravado
e posição 0 de Y se tem gravado
, na posição 1 de X está
e na posição 1 de Y está
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
pontos
armazenados em dois vetores
e
, e queremos montar uma tabela (matriz) de diferenças divididas progressivas de ordem 1 até
. Vamos usar a fórmula de Newton para diferenças divididas:
Passo 2
Para organizar isso em algoritmo, criamos uma matriz
de dimensão
. Na coluna 0 (ordem zero) colocamos os valores de
. Depois, para cada ordem
, calculamos
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