Подразделы

Другие разделы

Дата и время

29/03/2025 04:39:27

Авторизация

Зарегистрироваться
Восстановить пароль

Полиномы

Представление полиномов Операции над полиномами Быстрое умножение полиномов

Представление полиномов

Полиномом относительно переменной $x$ над алгебраическим полем $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$ .

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)$ .

Если выполнить преобразование полинома Лагранжа в барицентрическую форму, то можно вычислять значение полинома в новой точке за $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$ в этом случае можно вычислять не хранить, а вычислять:

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;
}

Рассмотренные операции позволяют преобразовать коэффициентное представление полинома в представление в виде точек-значений и наоборот, хотя ошибки округления в ходе вычислений могут привести к значительным различиям в результатах.