Interpolación de Newton

01 · Misma solución, nueva forma

Un polinomio preparado para crecer

Vandermonde, Lagrange y Newton representan el mismo polinomio cuando utilizan los mismos nodos. La diferencia está en la base y en cómo se calculan sus coeficientes.

Newton organiza el interpolante como una suma de productos acumulativos:

Al agregar un nodo, los términos anteriores se conservan y solo se añade uno nuevo.

02 · Productos acumulativos

La base polinómica de Newton

En lugar de 1,x,x²,…, usamos:

Cada Nₖ tiene grado k y vale cero en los nodos x₀,…,xₖ₋₁. Por eso sumar aₖNₖ(x) no altera los valores ya interpolados.

03 · Coeficientes

Diferencias divididas

Los coeficientes de Newton se obtienen mediante diferencias divididas. El orden cero contiene los datos:

La diferencia dividida de primer orden es una pendiente entre dos nodos:

Para órdenes superiores usamos la definición recursiva:

Los coeficientes son la primera entrada de cada orden:

04 · Organización

La tabla triangular

Para los puntos (0,1), (1,2) y (2,5):

Los valores de primer orden son (2−1)/(1−0)=1 y (5−2)/(2−1)=3. El segundo orden es (3−1)/(2−0)=1. La fila superior proporciona a₀=1, a₁=1 y a₂=1.

05 · Construcción manual

Recuperar p(x)=1+x²

Con los coeficientes de la tabla:

Al simplificar:

Para x=1.5:

Es exactamente el mismo resultado obtenido mediante Vandermonde y Lagrange.

06 · Preprocesamiento

Calcular coeficientes en un solo arreglo

No es necesario almacenar toda la tabla. Podemos actualizar un arreglo desde la derecha para no sobrescribir valores que todavía necesitamos:

function coeficientesNewton(puntos) {
  const n = puntos.length;
  if (n === 0) throw new Error("Faltan puntos");
  const nodos = puntos.map(([x]) => x);
  const coeficientes = puntos.map(([, y]) => y);

  for (let orden = 1; orden < n; orden++) {
    for (let i = n - 1; i >= orden; i--) {
      const denominador = nodos[i] - nodos[i - orden];
      if (denominador === 0) throw new Error("Nodo duplicado");
      coeficientes[i] = (coeficientes[i] - coeficientes[i - 1])
        / denominador;
    }
  }
  return { nodos, coeficientes };
}

console.log(coeficientesNewton([[0, 1], [1, 2], [2, 5]]));
// nodos: [0,1,2], coeficientes: [1,1,1]

El recorrido descendente es esencial. Si avanzáramos desde la izquierda, utilizaríamos valores ya modificados de la misma etapa.

07 · Forma anidada

Evaluar como una generalización de Horner

La forma de Newton puede anidarse:

La evaluación comienza en el coeficiente de mayor orden:

function evaluarNewton(nodos, coeficientes, x) {
  if (nodos.length !== coeficientes.length || nodos.length === 0) {
    throw new Error("Datos incompatibles");
  }
  let valor = coeficientes.at(-1);
  for (let i = coeficientes.length - 2; i >= 0; i--) {
    valor = coeficientes[i] + (x - nodos[i]) * valor;
  }
  return valor;
}

console.log(evaluarNewton([0, 1, 2], [1, 1, 1], 1.5)); // 3.25

Después del preprocesamiento de costo O(n²), cada consulta necesita O(n) operaciones y O(1) memoria adicional.

08 · Ventaja incremental

Agregar un nodo sin reconstruir todo

Supongamos que ya tenemos pₙ₋₁ para los primeros n puntos y llega (xₙ,yₙ). Extendemos:

Al imponer pₙ(xₙ)=yₙ obtenemos:

Solo debemos evaluar el polinomio anterior y el producto en el nuevo nodo. El costo es O(n).

09 · Cuarto dato

Extender el ejemplo

Agregamos (3,11) al polinomio p₂(x)=1+x². En el nuevo nodo:

Por lo tanto, a₃=1/6 y:

El término nuevo vale cero en x=0,1,2 y vale uno en x=3, corrigiendo exactamente la diferencia que faltaba.

10 · Modelo actualizable

Incorporar una muestra en JavaScript

function evaluar(modelo, x) {
  let valor = modelo.coeficientes.at(-1);
  for (let i = modelo.coeficientes.length - 2; i >= 0; i--) {
    valor = modelo.coeficientes[i] + (x - modelo.nodos[i]) * valor;
  }
  return valor;
}

function agregarNodo(modelo, xNuevo, yNuevo) {
  if (modelo.nodos.includes(xNuevo)) throw new Error("Nodo duplicado");
  const estimado = evaluar(modelo, xNuevo);
  const producto = modelo.nodos.reduce((valor, x) =>
    valor * (xNuevo - x), 1);
  modelo.coeficientes.push((yNuevo - estimado) / producto);
  modelo.nodos.push(xNuevo);
}

const modelo = { nodos: [0, 1, 2], coeficientes: [1, 1, 1] };
agregarNodo(modelo, 3, 11);
console.log(modelo.coeficientes, evaluar(modelo, 3)); // [1,1,1,1/6], 11

El ejemplo modifica el modelo recibido. Una interfaz inmutable podría devolver copias nuevas para evitar efectos laterales.

11 · Orden y significado

Los coeficientes cambian si reordenamos los nodos

Las diferencias divididas son simétricas respecto de sus argumentos, pero la lista de coeficientes y los productos anidados dependen del orden elegido para construir la base.

Con aritmética exacta, cualquier orden de los mismos pares produce el mismo polinomio final. En coma flotante, el orden puede modificar los errores de redondeo.

• Ordenar por x facilita interpretar la tabla.
• Para evaluar cerca de una región, un orden equilibrado puede mejorar el comportamiento numérico.
• Al agregar datos en línea, el orden de llegada determina naturalmente la base incremental.

Reordenar solamente los nodos sin reordenar sus valores o coeficientes cambia el problema y produce un resultado incorrecto.

12 · Nodos uniformes

Relación con diferencias finitas

Cuando los nodos están igualmente espaciados, xᵢ=x₀+ih, las diferencias divididas se relacionan con diferencias finitas:

Esta relación conduce a fórmulas progresivas y regresivas de Newton para tablas uniformes. Las diferencias divididas generales no requieren separación constante y por eso resultan más flexibles.

13 · Precisión

Error, nodos cercanos y oscilaciones

Newton representa el mismo polinomio global, por lo que conserva el resto:

La forma de Newton evita resolver Vandermonde y permite una evaluación eficiente, pero no elimina:

• el fenómeno de Runge con nodos uniformes y grado alto;
• la sensibilidad a datos ruidosos;
• la extrapolación peligrosa;
• divisiones problemáticas cuando nodos distintos están extremadamente próximos;
• errores acumulados al construir órdenes altos.

Escalar los nodos, usar distribuciones adecuadas o preferir interpolación por tramos son decisiones complementarias.

14 · Exploración interactiva

Laboratorio: agregar términos uno por uno

Elegí una función, la cantidad de nodos incorporados y una consulta. La curva dorada muestra el polinomio anterior; la turquesa incluye el nodo nuevo.

Preguntas para explorar

1. En la cuadrática, observá qué ocurre con los coeficientes a partir del cuarto nodo.
2. Mové la consulta sobre un nodo anterior: la corrección nueva debe ser cero.
3. En Runge, agregá nodos hasta grado ocho y examiná los extremos.
4. Compará el polinomio anterior con el actual cerca del último nodo incorporado.

15 · Comprensión

Confusiones frecuentes

16 · Práctica guiada

Ejercicios

Ejercicio 1: primer orden

Calculá f[1,3] para los puntos (1,2) y (3,10).

Ejercicio 2: segundo orden

Si f[x₀,x₁]=1, f[x₁,x₂]=3, x₀=0 y x₂=2, calculá f[x₀,x₁,x₂].

Ejercicio 3: forma anidada

Evaluá en x=1.5 el modelo con nodos [0,1,2] y coeficientes [1,1,1].

Ejercicio 4: término incremental

¿Por qué aₙ∏(x−xⱼ) no altera los primeros n datos?

Ejercicio 5: tabla completa

Implementá una función que devuelva todas las columnas de diferencias divididas.

function tablaDiferencias(puntos) {
  const columnas = [puntos.map(([, y]) => y)];
  for (let orden = 1; orden < puntos.length; orden++) {
    const anterior = columnas[orden - 1];
    const actual = [];
    for (let i = 0; i < puntos.length - orden; i++) {
      const denominador = puntos[i + orden][0] - puntos[i][0];
      if (denominador === 0) throw new Error("Nodo duplicado");
      actual.push((anterior[i + 1] - anterior[i]) / denominador);
    }
    columnas.push(actual);
  }
  return columnas;
}

console.log(tablaDiferencias([[0, 1], [1, 2], [2, 5]]));
// [[1,2,5], [1,3], [1]]

17 · Síntesis

Ideas para recordar

En el próximo tema reemplazaremos el polinomio global por splines cúbicos: polinomios locales unidos con continuidad y suavidad.