Многочлены и формальные ряды

Многочлен над переменной xx — формальное выражение P(x)=a0+a1⋅x+a2⋅x2+⋯+an−1⋅xn−1+an⋅xnP(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dotsb + a_{n-1} \cdot x^{n-1} + a_n \cdot x^n.

Числа aja_j могут быть элементами любого поля. Чаще всего это R,Q,C,GF(q)\RR, \QQ, \CC, \GF(q).

Многочлены можно умножать и складывать

∑k=0nak⋅xk+∑k=0nbk⋅xk=∑k=0n(ak+bk)⋅xkи(∑k=0nak⋅xk)⋅(∑k=0nbk⋅xk)=∑k=0nxk∑i+j=kaibj\sum\limits_{k=0}^n a_k \cdot x^k + \sum\limits_{k=0}^n b_k \cdot x^k = \sum\limits_{k=0}^n (a_k + b_k) \cdot x^k \quad\text{и}\quad \Biggl( \sum\limits_{k=0}^n a_k \cdot x^k \Biggr) \cdot \Biggl( \sum\limits_{k=0}^n b_k \cdot x^k \Biggr) = \sum\limits_{k=0}^n x^k \sum\limits_{i+j=k} a_i b_j

Степенью многочлена A(x)=∑j=0naj⋅xjA(x) = \sum\limits_{j=0}^n a_j \cdot x^j называется наибольшее jj, для которого aj≠0a_j \neq 0. Обозначается deg⁡A\deg A. Почти всегда при записи многочлена в виде суммы мономов подразумевается, что deg⁡A=n\deg A = n.

Схема Горнера

Схема Горнера позволяет быстро вычислять значение многочлена, заданного коэффициентами.