Начало
Учебные материалы
Полиномы
Представление полиномов
полем `F` называется представление функции `P(x)` в виде суммы
`P(x)=sum_{j=0}^{n-1} a_j*x^j`
Значения `a_0,a_1, ..., a_{n-1}` называются коэффициентами данного полинома, которые
можно представить в виде вектора коэффициентов `a=(a_0,a_1, ..., a_{n-1})`.
--
Основанным *на значениях в точках* представлением полинома `P(x)` степени `n-1` является множество,
состоящее из `n` пар точка-значение: `{(x_0, y_0), (x_1,y_1), ..., (x_{n-1}, y_{n-1})}`,
таких что все `x_k` различны и `y_k=P(x_k)`.
Полином имеет имеет бесконечное количество различных представлений, основанных на значениях в точках,
поскольку в качестве базиса такого представления можно использовать любое множество различных точек
`(x_0, x_1, ..., x_{n-1})`.
--
Получить основанное на значениях в точках представление из полинома, заданного с помощью коэффициентов,
достаточно просто: для этого достаточно выбрать `n` различных точек `(x_0, x_1, ..., x_{n-1})` и вычислить `P(x_k)`.
Рассмотрим задачу вычисления значения полинома
`P(x) =a_{n-1} x^{n-1}+a_{n-1} x^{n-1}+...+ a_1 x+a_0`
в заданной точке `x`. Для вычисления `k`-го слагаемого требуется `k` умножений: `a_k*x*...*x`.
*Схема Горнера* — один из старых, но очень элегантных и эффективных алгоритмов для вычисления полиномов.
Этот алгоритм является хорошим примером использования метода изменения
представления, поскольку он основан на представлении при помощи формулы,
которая получается путем последовательного вынесения `x` за скобки с образованием полиномов с уменьшающимися
степенями:
`P(x) = (... (a_{n-1} x + a_{n-2}) x + ...)x + a_0`.
--
```c++
double Horner(const vector<double> &a, double x)
{ double r=a.back();
for(i=a.size()-2;i>=0;--i)
r=r*x+a[i];
return r;
}
```
Количество умножений в алгоритме определяется формулой:
`M(n)=sum_{i=0}^{n-2} 1=n-1`
а вычисление `y_k` для всех `x_k` можно выполнить за время `O(n^2)`.
--
Обратная процедура — определение коэффициентов полинома, заданного в виде значений в точках, —
называется *интерполяцией*.
Для любого множества, состоящего из `n` пар точка-значение, таких что все значения `x_k` различны,
существует единственный полином `P(x)` степени `n-1`, такой что `y_k = P(x_k)`.
Набор уравнений `y_k = P(x_k)` можно представить как систему линейных уравнений `V*a=y`,
таким образом, можно однозначно вычислить коэффициенты `a=V^{-1}*y`. Эффективность такого алгоритма `O(n^3)`
--
Более быстрый алгоритм интерполяции основан на *формуле Лагранжа*
`P(x)=sum_{k=0}^{n-1} y_k (prod_{j!=k}(x-x_j))/(prod_{j!=k}(x_k-x_j))`
Вычислить коэффициенты полинома `P(x)` можно за время `O(n^2)`.
Если выполнить преобразование полинома Лагранжа в [барицентрическую форму](https://people.maths.ox.ac.uk/trefethen/barycentric.pdf), то можно вычислять значение полинома в новой точке за `O(n)` (как и для коэффициентного представления), но потребуется `O(n)` дополнительной памяти для хранения *барицентрических весов* `w_k=prod_{j!=k}(x_k-x_j)^{-1}`, которые зависят только от значений `x_k` и не зависят от `y_k`.
Обозначим `l(x)=prod_{j=0}^{n-1}(x-x_j)`, тогда формулу интерполяции можно переписать в форме:\
`P(x)=l(x)sum_{k=0}^{n-1} w_k/(x-x_k) * y_k`.
Поделив на аналогичную формулу для полинома `p_1(x)=1` (константа 1), можно избавиться от `l(x)`:\
`P(x)=(sum_{k=0}^{n-1} w_k/(x-x_k) * y_k) // sum_{k=0}^{n-1} w_k/(x-x_k)`.
Для `x=x_k` нужно возвращать `y_k`, так как появляется неопределенность `oo//oo`.
Для вычисления `w_k` требуется в общем случае `O(n^2)` операций, но для равноотстоящих `x_k` этот расчет можно выполнить за `O(n)`, при этом `w_k` не будут зависеть от интервала (из-за сокращения одинаковых значений в числителе и знаменателе формулы):
`w_k=(-1)^k*C_{n-1}^k`.
`w_k` в этом случае можно вычислять не хранить, а вычислять:
```c++
double Barycentric(const vector<double> &y, double x, double x0, double dx)
{ const double eps=1e-9;
int n=y.size();
double i=(x-x0)/dx;
double ri=round(i);
if(ri>=0 && ri<n && fabs(i-ri)<eps) // попадаем близко к точке x+ri*dx
return y[ri];
double wk=1;
double xk=x0;
double ch=0,zn=0; // числитель и знаменатель
for(int k=0; k<n;++k) {
double v=wk/(x-xk);
ch+=v*y[k];
zn+=v;
xk+=dx;
wk=-wk*(n-1-k)/(k+1);
}
return ch/zn;
}
```
Рассмотренные операции позволяют преобразовать коэффициентное представление полинома в представление
в виде точек-значений и наоборот, хотя ошибки округления в ходе вычислений
могут привести к значительным различиям в результатах.
