如何找到多项式方程的系数? [英] How to find coefficients of polynomial equation?

问题描述

给定 x, y 平面上的两个点:

Given two points in the x, y plane:

x, f(x)
1, 3
2, 5

我可以使用拉格朗日对它们进行插值并找到 f(1.5)，从而得到 4.稍微思考一下，我设法找到了一种方法来发现方程的系数:

I can interpolate them using Lagrange and find f(1.5), which result in 4. Thinking a little I managed to find a way to discover the coefficients of the equation:

void l1Coefficients(const vector<double> &x, const vector<double> &y) {

    double a0 = y[0]/(x[0]-x[1]);
    double a1 = y[1]/(x[1]-x[0]);

    double b0 = (-x[1]*y[0])/(x[0]-x[1]);
    double b1 = (-x[0]*y[1])/(x[1]-x[0]);

    double a = a0 + a1;
    double b = b0 + b1;

    cout << "P1(x) = " << a << "x +" << b << endl;
}

这给了我 P1(x) = 2x +1.

多想一点，我能够将其扩展到 2nd 阶方程.因此，鉴于要点:

Thinking a little more I was able to extend that to 2nd order equations. So, given the points:

1, 1
2, 4
3, 9

我发现方程 P2(x) = 1x^2 +0x +0 如下:

void l2Coefficients(const vector<double> &x, const vector<double> &y) {

    double a0 =              y[0] / ((x[0]-x[1])*(x[0]-x[2]));
    double a1 =              y[1] / ((x[1]-x[0])*(x[1]-x[2]));
    double a2 =              y[2] / ((x[2]-x[0])*(x[2]-x[1]));

    double b0 = -(x[1]+x[2])*y[0] / ((x[0]-x[1])*(x[0]-x[2]));
    double b1 = -(x[0]+x[2])*y[1] / ((x[1]-x[0])*(x[1]-x[2]));
    double b2 = -(x[0]+x[1])*y[2] / ((x[2]-x[0])*(x[2]-x[1]));

    double c0 =  (x[1]*x[2])*y[0] / ((x[0]-x[1])*(x[0]-x[2]));
    double c1 =  (x[0]*x[2])*y[1] / ((x[1]-x[0])*(x[1]-x[2]));
    double c2 =  (x[0]*x[1])*y[2] / ((x[2]-x[0])*(x[2]-x[1]));

    double a = a0 + a1 + a2;
    double b = b0 + b1 + b2;
    double c = c0 + c1 + c2;

    cout << "P2(x) = " << a << "x^2 +" << b << "x +" << c << endl;
}

努力工作，我实际上能够找到高达 4 阶的方程的系数.

Working hard I actually was able to find the coefficients for equations of order up to 4th.

如何求n阶方程的系数?哪里

How to find the coefficients of order n equations? Where

Pn(x) = c_2x^2 + c_1x^1 + c_0x^0 + ...

推荐答案

这是一个简单的线性代数问题.

It's a simple linear algebra problem.

我们有一组 N 个样本，形式为 x_k -> f(x_k) 并且我们知道函数 f(x) 的一般形式，其中是:

We have a set of N samples of the form x_k -> f(x_k) and we know the general form of function f(x), which is:

f(x) = c₀x⁰ + c₁x¹ + ... +c_N-1x^N-1

f(x) = c₀x⁰ + c₁x¹ + ... + c_N-1x^N-1

我们想要找到系数 c₀ ... c_N-1.为了实现这一点，我们构建了一个由 N 个方程组成的系统，形式如下:

We want to find the coefficients c₀ ... c_N-1. To achieve that, we build a system of N equations of the form:

c₀x_k⁰ + c₁x_k¹ + ... + c_N-1x_k^N-1 = f(x_k)

c₀x_k⁰ + c₁x_k¹ + ... + c_N-1x_k^N-1 = f(x_k)

其中 k 是样本编号.由于 x_k 和 f(x_k) 是常数而不是变量，我们有一个线性方程组.

where k is the sample number. Since x_k and f(x_k) are constants rather than variables, we have a linear system of equations.

用线性代数表示，我们必须解决:

Expressed in terms of linear algebra, we have to solve:

Ac = b

其中 A 是 Vandermonde 矩阵 x 和 b 是 f(x_k) 值的向量.

where A is a Vandermonde matrix of powers of x and b is a vector of f(x_k) values.

要解决这样的系统，您需要一个线性代数库，例如 Eigen.请参阅此处示例代码.

To solve such a system, you need a linear algebra library, such as Eigen. See here for example code.

这种方法唯一可能出错的是线性方程组未确定，如果您的 N 个样本可以用小于 N-1 的多项式拟合，就会发生这种情况.在这种情况下，您仍然可以像这样使用 Moore-Penrose 伪逆求解该系统:

The only thing that can go wrong with such an approach is the system of linear equations being under-determined, which will happen if your N samples can be fit with with a polynomial of degree less than N-1. In such a case you can still solve this system with Moore-Penrose pseudo inverse like this:

c = pinv(A)*b

c = pinv(A)*b

不幸的是，Eigen 没有 pinv() 实现，尽管根据奇异值分解 (SVD) 自己编写代码很容易.

Unfortunately, Eigen doesn't have a pinv() implementation, though it's pretty easy to code it by yourself in terms of Singular Value Decomposition (SVD).

这篇关于如何找到多项式方程的系数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！