Инструменты сайта


Суммы Ньютона

Для полинома $ f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n, (a_0\ne 0) $ его $ k_{} $-й суммой Ньютона называется сумма $ k_{} $-х степеней его корней $ \lambda_1,\dots, \lambda_{n} $: $$ s_k=\sum_{j=1}^n\lambda_j^k \ . $$ При этом обычно считают $ k_{} \in {\mathbb N} $ (хотя формально можно определить суммы Ньютона и для отрицательных индексов $ k_{} $ при условии $ a_{n} \ne 0 $). Для однообразия полагают также1) $ s_{0}=n $.

Суммы Ньютона являются примером симметрических полиномов, вычисляемых на корнях полинома $ f_{}(x) $. Подробнее ЗДЕСЬ.
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\} $. Доказательство первой части посложнее и приводится ЗДЕСЬ.

П

Пример. При $ 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_{} $, является линейной рекуррентной последовательностью $ n_{} $-го порядка: при задании чисел $ s_0,\dots,s_{n-1} $ каждое следующее число последовательности определяется через $ n_{} $ предшествующих по одному и тому же закону.
?

Вычислить суммы Ньютона полинома $ z^{n}-1 $.

Ответ ЗДЕСЬ.

Формула Варинга

Т

Теорема. Имеет место формула Варинга:

$$ 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} $ является полиномом степени $ 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)} \ . $$

Суммы Ньютона и квадратные матрицы

Суммы Ньютона возникают в дном из разделов теории матриц.

Т

Теорема. Пусть $ \operatorname{Sp}_{} $ означает след, а $ f_{}(x)=\det (A-xE) $ – характеристический полином квадратной матрицы $ A_{} $. Тогда сумма Ньютона полинома $ f_{}(x) $ вычисляется по формуле $$ s_k= \operatorname{Sp}(A^k) $$

Формула остается верной и для отрицательных $ k_{} $ если только матрица $ A_{} $ неособенная.

Применения сумм Ньютона

Для локализации (отделения) корней полинома

В кодах, исправляющих ошибки

Обобщенные суммы Ньютона

Если $ \{(\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 $. См. ЗДЕСЬ.

Задачи

ЗДЕСЬ.

1)
Даже в случае, когда один из корней полинома равен нулю.
dets/discrim/waring.txt · Последние изменения: 2021/02/12 18:52 — au