La interpolación es una estimación de un valor dentro de dos valores conocidos en una secuencia de valores.
La fórmula de interpolación de diferencia dividida de Newton es una técnica de interpolación utilizada cuando la diferencia de intervalo no es la misma para todas las secuencias de valores.
Supongamos que f(x 0 ), f(x 1 ), f(x 2 )………f(x n ) sean los (n+1) valores de la función y=f(x) correspondientes a los argumentos x=x 0 , x 1 , x 2 …x n , donde las diferencias de intervalo no son iguales
Entonces la primera diferencia dividida está dada por
![f[x_0, x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-3794e0adb7c1a1d3b0b863eb8a27e97c_l3.png "Rendered by QuickLaTeX.com")
La segunda diferencia dividida está dada por
![f[x_0, x_1, x_2]=\frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-78f5a99f2a3530bf540642cd0a999194_l3.png "Rendered by QuickLaTeX.com")
y así sucesivamente…
Las diferencias divididas son simétricas con respecto a los argumentos, es decir, independientes del orden de los argumentos.
entonces,
f[x 0 , x 1 ]=f[x 1 , x 0 ]
f[x 0 , x 1 , x 2 ]=f[x 2 , x 1 , x 0 ]=f[x 1 , x 2 , x 0 ]
Usando la primera diferencia dividida, la segunda diferencia dividida y así sucesivamente. Se forma una tabla que se llama tabla de diferencias divididas.
Tabla de diferencia dividida:
Ventajas de la FÓRMULA DE INTERPOLACIÓN EN DIFERENCIA DIVIDIDA DE NEWTON
- Estos son útiles para la interpolación.
- A través de la tabla de diferencias, podemos encontrar las diferencias en orden superior.
- Las diferencias en cada etapa en cada una de las columnas se miden fácilmente restando el valor anterior de su valor inmediatamente posterior.
- Las diferencias se encuentran sucesivamente entre los dos valores adyacentes de la variable y hasta que la última diferencia desaparece o se convierte en una constante.
FÓRMULA DE INTERPOLACIÓN EN DIFERENCIA DIVIDIDA DE NEWTON
![f(x)=f(x_0)+(x-x_0)f[x_0, x_1]+(x-x_0)(x-x_1)f[x_0, x_1, x_2]+..........................+(x-x_0)(x-x_1)...(x-x_k_-_1)f[x_0, x_1, x_2...x_k]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-2431867c1ae3be30705d2832160f3b3e_l3.png "Rendered by QuickLaTeX.com")
Ejemplos:
Input : Value at 7
Output :
Value at 7 is 13.47
A continuación se muestra la implementación del método de interpolación de diferencias divididas de Newton.
C++
// CPP program for implementing
// Newton divided difference formula
#include <bits/stdc++.h>
using namespace std;
// Function to find the product term
float proterm(int i, float value, float x[])
{
float pro = 1;
for (int j = 0; j < i; j++) {
pro = pro * (value - x[j]);
}
return pro;
}
// Function for calculating
// divided difference table
void dividedDiffTable(float x[], float y[][10], int n)
{
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
y[j][i] = (y[j][i - 1] - y[j + 1]
[i - 1]) / (x[j] - x[i + j]);
}
}
}
// Function for applying Newton's
// divided difference formula
float applyFormula(float value, float x[],
float y[][10], int n)
{
float sum = y[0][0];
for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[0][i]);
}
return sum;
}
// Function for displaying
// divided difference table
void printDiffTable(float y[][10],int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
cout << setprecision(4) <<
y[i][j] << "\t ";
}
cout << "\n";
}
}
// Driver Function
int main()
{
// number of inputs given
int n = 4;
float value, sum, y[10][10];
float x[] = { 5, 6, 9, 11 };
// y[][] is used for divided difference
// table where y[][0] is used for input
y[0][0] = 12;
y[1][0] = 13;
y[2][0] = 14;
y[3][0] = 16;
// calculating divided difference table
dividedDiffTable(x, y, n);
// displaying divided difference table
printDiffTable(y,n);
// value to be interpolated
value = 7;
// printing the value
cout << "\nValue at " << value << " is "
<< applyFormula(value, x, y, n) << endl;
return 0;
}
Java
// Java program for implementing
// Newton divided difference formula
import java.text.*;
import java.math.*;
class GFG{
// Function to find the product term
static float proterm(int i, float value, float x[])
{
float pro = 1;
for (int j = 0; j < i; j++) {
pro = pro * (value - x[j]);
}
return pro;
}
// Function for calculating
// divided difference table
static void dividedDiffTable(float x[], float y[][], int n)
{
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
y[j][i] = (y[j][i - 1] - y[j + 1]
[i - 1]) / (x[j] - x[i + j]);
}
}
}
// Function for applying Newton's
// divided difference formula
static float applyFormula(float value, float x[],
float y[][], int n)
{
float sum = y[0][0];
for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[0][i]);
}
return sum;
}
// Function for displaying
// divided difference table
static void printDiffTable(float y[][],int n)
{
DecimalFormat df = new DecimalFormat("#.####");
df.setRoundingMode(RoundingMode.HALF_UP);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
String str1 = df.format(y[i][j]);
System.out.print(str1+"\t ");
}
System.out.println("");
}
}
// Driver Function
public static void main(String[] args)
{
// number of inputs given
int n = 4;
float value, sum;
float y[][]=new float[10][10];
float x[] = { 5, 6, 9, 11 };
// y[][] is used for divided difference
// table where y[][0] is used for input
y[0][0] = 12;
y[1][0] = 13;
y[2][0] = 14;
y[3][0] = 16;
// calculating divided difference table
dividedDiffTable(x, y, n);
// displaying divided difference table
printDiffTable(y,n);
// value to be interpolated
value = 7;
// printing the value
DecimalFormat df = new DecimalFormat("#.##");
df.setRoundingMode(RoundingMode.HALF_UP);
System.out.println("\nValue at "+df.format(value)+" is "
+df.format(applyFormula(value, x, y, n)));
}
}
// This code is contributed by mits
Python3
# Python3 program for implementing
# Newton divided difference formula
# Function to find the product term
def proterm(i, value, x):
pro = 1;
for j in range(i):
pro = pro * (value - x[j]);
return pro;
# Function for calculating
# divided difference table
def dividedDiffTable(x, y, n):
for i in range(1, n):
for j in range(n - i):
y[j][i] = ((y[j][i - 1] - y[j + 1][i - 1]) /
(x[j] - x[i + j]));
return y;
# Function for applying Newton's
# divided difference formula
def applyFormula(value, x, y, n):
sum = y[0][0];
for i in range(1, n):
sum = sum + (proterm(i, value, x) * y[0][i]);
return sum;
# Function for displaying divided
# difference table
def printDiffTable(y, n):
for i in range(n):
for j in range(n - i):
print(round(y[i][j], 4), "\t",
end = " ");
print("");
# Driver Code
# number of inputs given
n = 4;
y = [[0 for i in range(10)]
for j in range(10)];
x = [ 5, 6, 9, 11 ];
# y[][] is used for divided difference
# table where y[][0] is used for input
y[0][0] = 12;
y[1][0] = 13;
y[2][0] = 14;
y[3][0] = 16;
# calculating divided difference table
y=dividedDiffTable(x, y, n);
# displaying divided difference table
printDiffTable(y, n);
# value to be interpolated
value = 7;
# printing the value
print("\nValue at", value, "is",
round(applyFormula(value, x, y, n), 2))
# This code is contributed by mits
C#
// C# program for implementing
// Newton divided difference formula
using System;
class GFG{
// Function to find the product term
static float proterm(int i, float value, float[] x)
{
float pro = 1;
for (int j = 0; j < i; j++) {
pro = pro * (value - x[j]);
}
return pro;
}
// Function for calculating
// divided difference table
static void dividedDiffTable(float[] x, float[,] y, int n)
{
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
y[j,i] = (y[j,i - 1] - y[j + 1,i - 1]) / (x[j] - x[i + j]);
}
}
}
// Function for applying Newton's
// divided difference formula
static float applyFormula(float value, float[] x,
float[,] y, int n)
{
float sum = y[0,0];
for (int i = 1; i < n; i++) {
sum = sum + (proterm(i, value, x) * y[0,i]);
}
return sum;
}
// Function for displaying
// divided difference table
static void printDiffTable(float[,] y,int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) {
Console.Write(Math.Round(y[i,j],4)+"\t ");
}
Console.WriteLine("");
}
}
// Driver Function
public static void Main()
{
// number of inputs given
int n = 4;
float value;
float[,] y=new float[10,10];
float[] x = { 5, 6, 9, 11 };
// y[][] is used for divided difference
// table where y[][0] is used for input
y[0,0] = 12;
y[1,0] = 13;
y[2,0] = 14;
y[3,0] = 16;
// calculating divided difference table
dividedDiffTable(x, y, n);
// displaying divided difference table
printDiffTable(y,n);
// value to be interpolated
value = 7;
// printing the value
Console.WriteLine("\nValue at "+(value)+" is "
+Math.Round(applyFormula(value, x, y, n),2));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program for implementing
// Newton divided difference formula
// Function to find the product term
function proterm($i, $value, $x)
{
$pro = 1;
for ($j = 0; $j < $i; $j++)
{
$pro = $pro * ($value - $x[$j]);
}
return $pro;
}
// Function for calculating
// divided difference table
function dividedDiffTable($x, &$y, $n)
{
for ($i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $n - $i; $j++)
{
$y[$j][$i] = ($y[$j][$i - 1] -
$y[$j + 1][$i - 1]) /
($x[$j] - $x[$i + $j]);
}
}
}
// Function for applying Newton's
// divided difference formula
function applyFormula($value, $x, $y,$n)
{
$sum = $y[0][0];
for ($i = 1; $i < $n; $i++)
{
$sum = $sum + (proterm($i, $value, $x) *
$y[0][$i]);
}
return $sum;
}
// Function for displaying
// divided difference table
function printDiffTable($y, $n)
{
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n - $i; $j++)
{
echo round($y[$i][$j], 4) . "\t ";
}
echo "\n";
}
}
// Driver Code
// number of inputs given
$n = 4;
$y = array_fill(0, 10, array_fill(0, 10, 0));
$x = array( 5, 6, 9, 11 );
// y[][] is used for divided difference
// table where y[][0] is used for input
$y[0][0] = 12;
$y[1][0] = 13;
$y[2][0] = 14;
$y[3][0] = 16;
// calculating divided difference table
dividedDiffTable($x, $y, $n);
// displaying divided difference table
printDiffTable($y, $n);
// value to be interpolated
$value = 7;
// printing the value
echo "\nValue at " . $value . " is " .
round(applyFormula($value, $x,
$y, $n), 2) . "\n"
// This code is contributed by mits
?>
Producción:
12 1 -0.1667 0.05 13 0.3333 0.1333 14 1 16 Value at 7 is 13.47
Publicación traducida automáticamente
Artículo escrito por SarthakGarg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA