==Суммы Ньютона==
~~TOC~~
Для ((:polynomial полинома)) $ f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n, (a_0\ne 0) $ его $ k_{} $**-й суммой Ньютона** называется сумма $ k_{} $-х степеней его ((:polynomial#корни корней)) $ \lambda_1,\dots, \lambda_{n} $:
$$
s_k=\sum_{j=1}^n\lambda_j^k \ .
$$
При этом обычно считают $ k_{} \in {\mathbb N} $ (хотя формально можно определить суммы Ньютона и для отрицательных индексов $ k_{} $ при условии $ a_{n} \ne 0 $). Для однообразия полагают также[[Даже в случае, когда один из корней полинома равен нулю.]] $ s_{0}=n $.
Суммы Ньютона являются примером симметрических полиномов, вычисляемых на корнях полинома $ f_{}(x) $. Подробнее
☞
((:polynomial#симметрические_функции_корней ЗДЕСЬ)).
!!T!! **Теорема.** //Суммы Ньютона выражаются рационально через коэффициенты полинома// $ f_{}(x) $ //посредством следующих// **формул Ньютона**:
$$
s_k=\left\{\begin{array}{lr}
-(a_1s_{k-1}+a_2s_{k-2}+\dots+a_{k-1}s_1+a_kk)/a_0,
&npu \ k\le n ;\\
-(a_1s_{k-1}+a_2s_{k-2}+\dots+a_ns_{k-n})/a_0,
& npu \ k > n
\end{array}
\right.
$$
**Доказательство** второй части формулы тривиально получается суммированием равенств
$$
a_0\lambda_j^k+a_1\lambda_j^{k-1}+\dots+ a_n \lambda_j^{k-n} =0
$$
по $ j \in \{1,\dots,n\} $. Доказательство первой части посложнее и приводится
☞
((:fraction#лорана ЗДЕСЬ)).
♦
!!П!! **Пример.** При $ a_{0}=1 $ имеем:
$$
s_1=-a_1, s_2=-(s_1a_1+2\,a_2)=a_1^2-2\, a_2 \ ,
$$
$$
s_3=-(a_1s_2+a_2s_1+3\,a_3)=-a_1^3+3\,a_1a_2-3\,a_3 \ ,
$$
$$
s_4=-\left(a_1s_3+a_2s_2+a_3s_1+4\,a_4\right)=
a_1^4-4\,a_1^2a_2+4\,a_1a_3+2\,a_2^2-4\,a_4 \ ,
$$
$$
s_5=-\left(a_1s_4+a_2s_3+a_3s_2+a_4s_1+5\,a_5\right)= -a_1^5+5(a_1^3a_2+a_1a_4-a_1^2a_3-a_1a_2^2+a_2a_3-a_5) \ .
$$
Полученные формулы универсальны --- они не зависят от степени полинома $ f_{}(x) $; при $ j_{}>n $ полагаем $ a_{j}=0 $. Для вычислений можно использовать только первую из указанных в теореме формул Ньютона; вторая получается из нее автоматически когда индекс суммы Ньютона превосходит степень полинома.
♦
Последовательность $ \{ s_k \}_{k=1}^{\infty} $, вычисленная для заданного полинома степени $ n_{} $, является ((:recurr#линейное_уравнение линейной рекуррентной последовательностью)) $ n_{} $-го порядка: при задании чисел $ s_0,\dots,s_{n-1} $ каждое следующее число последовательности определяется через $ n_{} $ предшествующих по одному и тому же закону.
!!?!! Вычислить суммы Ньютона полинома $ z^{n}-1 $.
**Ответ**
☞
((:complex_num:vspom3 ЗДЕСЬ)).
===Формула Варинга==
!!Т!! **Теорема.** //Имеет место// **формула Варинга**:
$$
s_k=\frac{k}{a_0^k}\sum \frac{(j_1+j_2+\ldots+j_n-1)!}{j_1!j_2! \times \ldots \times
j_n!}(-1)^{j_1+j_2+\ldots+j_n}a_1^{j_1}a_2^{j_2}\times \ldots \times a_n^{j_n},
$$
//где суммирование проводится по всем неотрицательным наборам индексов// $ (j_{1},\dots,j_n) $,
//удовлетворяющим условию// $ j_{1}+2j_2+3j_3+\ldots+nj_n=k $.
!!=>!! При $ a_{0}=1 $ и при $ j\in \{ 1,\dots,n\} $ выражение для $ s_{j} $ является ((:polynomialm полиномом)) степени $ j_{} $ от $ a_{1},\dots, a_j $; этот полином является линейным полиномом по $ a_{j} $:
$$ s_j \equiv \Psi (a_1,\dots,a_{j-1}) - j a_j \ . $$
===Обращение формул Ньютона==
В некоторых задачах возникает необходимость обратить формулы Ньютона: по заданным $ s_{1},\dots, s_n $ требуется восстановить коэффициенты полинома $ f_{}(x) $ степени $ n_{} $, для которого эти числа являются суммами Ньютона. Эта задача будет однозначно разрешима, если мы зафиксируем величину одного из коэффициентов искомого полинома. Обычно требуют, чтобы $ a_{0}=1 $, т.е. разыскивают нормализованный полином.
Соответствующие формулы тоже оказываются рекуррентными и также называются **формулами Ньютона**:
$$
a_1=-s_1, a_2=-(s_2+a_1s_1)/2,
$$
$$
a_k=-(s_{k}+a_1s_{k-1}+a_2s_{k-2}+\dots+a_{k-1}s_1)/k \ npu \ k \le n.
$$
!!Т!! **Теорема.** //Имеет место обращение формулы Варинга//:
$$
a_k=\sum \frac{(-1)^{j_1+j_2+\ldots+j_n}}{j_1!j_2! \times \ldots \times
j_n!}\left(\frac{s_1}{1}\right)^{j_1}\left(\frac{s_2}{2}\right)^{j_2} \times \dots \times \left(\frac{s_n}{n}\right)^{j_n}
$$
//где суммирование проводится по всем неотрицательным наборам индексов// $ (j_{1},\dots,j_n) $,
//удовлетворяющим условию// $ j_{1}+2j_2+3j_3+\ldots+nj_n=k $.
!!?!! Показать, что справедливо следующее детерминантное представление полинома $ f_{}(x) $
$$
f(x)\equiv\frac{1}{n!}\left|
\begin{array}{llllll}
s_1 &1 & & & &\\
s_2&s_1& 2 & &{\mathbb O} & \\
s_3&s_2&s_1&3& & \\
\dots& & & \ddots &\ddots & \\
s_n&s_{n-1}&\dots& &s_1&n \\
x^n&x^{n-1}&\dots& &x&1
\end{array}
\right|_{(n+1)\times (n+1)} \ .
$$
===Суммы Ньютона и квадратные матрицы==
Суммы Ньютона возникают в ((:algebra2:charpoly#собственные_числа дном из разделов)) теории матриц.
!!Т!! **Теорема.** //Пусть// $ \operatorname{Sp}_{} $ //означает ((algebra2:#след)), а// $ f_{}(x)=\det (A-xE) $ -- //характеристический полином// __//квадратной//__ //матрицы// $ A_{} $. //Тогда сумма Ньютона полинома// $ f_{}(x) $ //вычисляется по формуле//
$$
s_k= \operatorname{Sp}(A^k)
$$
Формула остается верной и для отрицательных $ k_{} $ если только матрица $ A_{} $ ((algebra2:#обращение_матрицы неособенная)).
===Применения сумм Ньютона==
====Для локализации (отделения) корней полинома==
☞
((:polynomial:zero_local#ганкелевы_матрицы_в_теории_локализации_корней ЗДЕСЬ))
====В кодах, исправляющих ошибки==
☞
((:codes:cyclic:bch#двоичные_бчх-коды ЗДЕСЬ))
==Обобщенные суммы Ньютона==
Если $ \{(\alpha_j, \beta_j)\}_{j=1}^N \subset \mathbb C^2 $ набор решений системы алгебраических уравнений (с учетом кратностей)
$$
f_1(x,y)=0,\, f_2(x,y)=0 \ ,
$$
то выражения
$$
s_{k\ell}=\sum_{j=1}^N \alpha_j^k \beta_j^{\ell} , \quad \mbox{ при } \ \{k,\ell\} \subset \{0,1,2,\dots \} \, .
$$
называются **обобщенными суммами Ньютона** для данной системы уравнений. При достаточно общих предположениях относительно полиномов $ f_1, f_2 $ это определение корректно (число решений конечно). Тогда величина $ s_{k\ell} $ может быть выражена в виде рациональной функции от коэффициентов полиномов $ f_1,f_2 $. См.
☞
((:elimination_theory/symm_fun_jacobi ЗДЕСЬ)).
==Задачи==
☞
((:dets:discrim:waring:problems ЗДЕСЬ)).