如何使用拉格朗日插值计算多项式系数 [英] How to calculate coefficients of polynomial using Lagrange interpolation
问题描述
我需要使用Lagrange 插值多项式来计算多项式的系数，作为我的作业，我决定在Javascript中执行此操作。
I need to calculate coefficients of polynomial using Lagrange interpolation polynomial, as my homework, I decide to do this in Javascript.
这里是拉格朗日多项式（L（x））的定义
here is definition of Lagrange polynomial (L(x))
拉格朗日基多项式定义如下
Lagrange basis polynomials are defined as follows
计算特定X（W（x）函数）的y值很简单，但我需要计算多项式的系数（数组为[a0] ，a1，...，an]）我需要这样做n< = 10但是拥有任意n会很好，然后我可以将该函数放入horner函数并绘制该多项式。
Calculate y value for specific X (W(x) function) is simple but I need to calculate coefficients of polynomial (array of [a0, a1, ..., an]) I need to do this to n<=10 but it will be nice to have arbitrary n, then I can put that function into horner function and draw that polynomial.
我有在第一个等式中计算分母的函数
I have function that calculate denominator in first equation
function denominator(i, points) {
var result = 1;
var x_i = points[i].x;
for (var j=points.length; j--;) {
if (i != j) {
result *= x_i - points[j].x;
}
}
return result;
}
和使用horner方法返回y的函数（我还使用canvas绘图函数） ）
and function that return y using horner method (I also have drawing function using canvas)
function horner(array, x_scale, y_scale) {
function recur(x, i, array) {
if (i == 0) {
return x*array[0];
} else {
return array[i] + x*recur(x, --i, array);
}
}
return function(x) {
return recur(x*x_scale, array.length-1, array)*y_scale;
};
}
任何人都知道这样做算法，或者想知道如何计算这些系数
anybody know algorithm to do this, or idea how to calculate those coefficients
推荐答案
嗯，你可以用天真的方式做到这一点。通过其系数数组表示多项式，数组
Well, you can do it the naive way. Represent a polynomial by the array of its coefficients, the array
[a_0,a_1,...,a_n]
对应 a_0 + a_1 * X + ... + a_n * X ^ n 。我对JavaScript不好，所以伪代码必须这样做：
corresponding to a_0 + a_1*X + ... + a_n*X^n. I'm no good with JavaScript, so pseudocode will have to do:
interpolation_polynomial(i,points)
coefficients = [1/denominator(i,points)]
for k = 0 to points.length-1
if k == i
next k
new_coefficients = [0,0,...,0] // length k+2 if k < i, k+1 if k > i
if k < i
m = k
else
m = k-1
for j = m downto 0
new_coefficients[j+1] += coefficients[j]
new_coefficients[j] -= points[k]*coefficients[j]
coefficients = new_coefficients
return coefficients
以常数多项式 1 /（（x_1-x_0）* ... *（x_i-x_ {i-1}）*（x_i-x_ {i + 1}开头}）* ... *（x_i-x_n））并与 X - x_k 相乘，所有 k！= I 。因此，给出L i 的系数，然后你只需将它们乘以y i （你可以通过初始化系数到 y_i / denominator（i，points）如果你将y值作为参数传递）并最后将所有系数加在一起。
Start with the constant polynomial 1/((x_1-x_0)* ... *(x_i-x_{i-1})*(x_i-x_{i+1})*...*(x_i-x_n)) and multiply with X - x_k for all k != i. So that gives the coefficients for Li, then you just multiply them with yi (you could do that by initialising coefficients to y_i/denominator(i,points) if you pass the y-values as parameters) and add all the coefficients together finally.
polynomial = [0,0,...,0] // points.length entries
for i = 0 to points.length-1
coefficients = interpolation_polynomial(i,points)
for k = 0 to points.length-1
polynomial[k] += y[i]*coefficients[k]
计算每个L i 是O（n²），所以总计算是O（n³）。
Calculating each Li is O(n²), so the total calculation is O(n³).
更新：在你的jsFiddle中，你在多项式乘法循环中有一个错误（现在更正了）我做的起始指数的错误，它应该是
Update: In your jsFiddle, you had an error in the polynomial multiplication loop in addition to (the now corrected) mistake with the start index I made, it should be
for (var j= (k < i) ? (k+1) : k; j--;) {
new_coefficients[j+1] += coefficients[j];
new_coefficients[j] -= points[k].x*coefficients[j];
}
因为你递减 j 测试时，它需要开始更高。
Since you decrement j when testing, it needs to start one higher.
这还没有产生正确的插值，但它至少比以前更明智。
That doesn't produce a correct interpolation yet, but it's at least more sensible than before.
另外，在你的 horner 函数中，
function horner(array, x_scale, y_scale) {
function recur(x, i, array) {
if (i == 0) {
return x*array[0];
} else {
return array[i] + x*recur(x, --i, array);
}
}
return function(x) {
return recur(x*x_scale, array.length-1, array)*y_scale;
};
}
您将最高系数乘以两次 x ，它应该是
you multiply the highest coefficient twice with x, it should be
if (i == 0) {
return array[0];
}
。但是仍然没有好结果。
instead. Still no good result, though.
Update2：最终错字修正，以下作品：
Update2: Final typo fixes, the following works:
function horner(array, x_scale, y_scale) {
function recur(x, i, array) {
if (i == 0) {
return array[0];
} else {
return array[i] + x*recur(x, --i, array);
}
}
return function(x) {
return recur(x*x_scale, array.length-1, array)*y_scale;
};
}
// initialize array
function zeros(n) {
var array = new Array(n);
for (var i=n; i--;) {
array[i] = 0;
}
return array;
}
function denominator(i, points) {
var result = 1;
var x_i = points[i].x;
for (var j=points.length; j--;) {
if (i != j) {
result *= x_i - points[j].x;
}
}
console.log(result);
return result;
}
// calculate coefficients for Li polynomial
function interpolation_polynomial(i, points) {
var coefficients = zeros(points.length);
// alert("Denominator " + i + ": " + denominator(i,points));
coefficients[0] = 1/denominator(i,points);
console.log(coefficients[0]);
//new Array(points.length);
/*for (var s=points.length; s--;) {
coefficients[s] = 1/denominator(i,points);
}*/
var new_coefficients;
for (var k = 0; k<points.length; k++) {
if (k == i) {
continue;
}
new_coefficients = zeros(points.length);
for (var j= (k < i) ? k+1 : k; j--;) {
new_coefficients[j+1] += coefficients[j];
new_coefficients[j] -= points[k].x*coefficients[j];
}
coefficients = new_coefficients;
}
console.log(coefficients);
return coefficients;
}
// calculate coefficients of polynomial
function Lagrange(points) {
var polynomial = zeros(points.length);
var coefficients;
for (var i=0; i<points.length; ++i) {
coefficients = interpolation_polynomial(i, points);
//console.log(coefficients);
for (var k=0; k<points.length; ++k) {
// console.log(points[k].y*coefficients[k]);
polynomial[k] += points[i].y*coefficients[k];
}
}
return polynomial;
}
这篇关于如何使用拉格朗日插值计算多项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
