УказательРазделыОбозначенияАвторО проекте


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

Для полинома 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_{} неособенная.

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

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

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

Задачи

ЗДЕСЬ.

1) Даже в случае, когда один из корней полинома равен нулю.

2015/11/20 09:16 редактировал au