迭代由 JavaScript 中的字符串构造的多项式的系数

Question

TL;DR：我需要一种方法从某些给定坐标创建多项式，以允许迭代其系数，甚至可以选择允许在任何给定点评估多项式

我正在努力在 JavaScript/TypeScript 中为 KZG 承诺创建一个粗略算法，该算法的步骤之一包括将为某些给定字符串构造的多项式的系数与结构化参考字符串 (SRS) 的适当幂相乘。

无论如何，这基本上意味着我需要迭代这个新构造的多项式的所有系数（至少这是我认为我需要做的，我愿意在这里接受建议）。

我正在努力实现以下目标：

1. 获取输入字符串
2. 将字符串转换为 XY 坐标平面上的坐标
3. 计算通过这些坐标的多项式
4. **迭代该多项式的系数**<-- this is where I am stuck
5. （可选）计算给定点 Z 处的多项式 <-- it would be awesome if this could still be possible alongside the previous requirement

我卡在第 4 步）。

我知道如何使用拉格朗日插值从 JS/TS 中的给定字符串构造多项式，但我在提取其系数时遇到困难，我需要能够将它们与 SRS 相乘。

下面是我的拉格朗日插值算法 - 请注意，它可以为我解决 5），但我没有看到从中获得精确系数的明显方法：

type Point = { x: number; y: number };

// The function basically reconstructs the whole Lagrange Polynomial each time
// it needs to evaluate it at some given point `newX`, which is a problem as
// there is no way to extract the coefficients.
function lagrangeInterpolation(points: Point[], newX: number) {
  const n = points.length;
  let newY = 0;

  for (let i = 0; i < n; i++) {
    let { x, y } = points[i];

    let term = y;
    for (let j = 0; j < n; j++) {
      if (i !== j) {
        let { x: xj } = points[j];
        term = (term * (newX - xj)) / (x - xj);
      }
    }
    newY = newY + term;
  }

  return newY;
}

也许另一种插值算法可以计算精确的系数？

我找不到任何可以解决这个问题的 JS 库。我能找到的最接近的如下，但它们仍然不适用于解决这个问题：

• 多项式 -> 问题：该库既没有内置的方法来返回系数，也不能将类似拉格朗日的多项式作为输入并缩短它以允许使用正则表达式提取系数。
• nerdamer-prime -> 问题：该库可以采用任何多项式并缩短它，但它不能保证项的顺序（按 x 的幂排序），这使得使用正则表达式提取系数变得困难（无法确定哪个系数与 x) 的哪个次方相关；它也没有内置的方法来获取系数。

Answer 1

您可以使用@guest 在拉格朗日多项式的系数中描述的基于矩阵的方法。

为此，您需要一个计算矩阵行列式的函数。为此，您可以使用高斯消除法。

这是一个实现：

function determinant(mat) { // Gaussian elimination method
    const n = mat.length;
    let det = 1;
    for (let r = 0; r < n; r++) {
        let r2 = r;
        while (!mat[r2][r]) {
            r2++;
            if (r2 >= mat.length) return 0;
        }
        const row = mat[r2];
        if (r2 !== r) { // Swap rows
            mat[r2] = mat[r];
            mat[r] = row;
            det = -det;
        }
        let div = row[r];
        if (!div) return 0;
        det *= div;
        for (let c = r; c < n; c++) row[c] /= div;
        for (let r2 = r+1; r2 < n; r2++) {
            const row2 = mat[r2];
            const mul = row2[r];
            for (let c = r; c < n; c++) {
                row2[c] -= mul * row[c]; 
            }
        }
    }
    return det;
}

// Similar to https://math.stackexchange.com/a/3253643/341715
function lagrangeInterpolationCoefficients(points) {
    const lagrangeDet = (j) => determinant(points.map((_, i) => 
        points.map(([a, b]) => i == j ? b : a ** i)
    ));
    const denom = lagrangeDet(-1);
    return points.map((_, j) => lagrangeDet(j) / denom);
}

const coefficientsToFunction = (coefficients) =>
    x => coefficients.reduce((sum, coeff, i) => sum + coeff * x**i, 0);

// Simple (imperfect) rendering of the polynomial:
const coefficientsToString = (coefficients) =>
    coefficients.map((coeff, i) => `${coeff}x^${i}`)
                .reverse().join(" + ")
                .replace(/x\^0|\^1\b|\b0x^\d+/g, "")
                .replaceAll("+ -", "- ");

// Demo
const points = [[0, -1], [1, 1], [3, 8], [4, 10]];
const coefficients = lagrangeInterpolationCoefficients(points);
console.log("f(x) =", coefficientsToString(coefficients));
const f = coefficientsToFunction(coefficients);

// Verify that the created function returns 
//    the correct results for the given points
for (const [x, y] of points) {
    console.log({x, y, "f(x)": f(x)});
}