Русская Википедия:Тождества Ньютона

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

В математике тождества Ньютона, также известные как формулы Ньютона — Жирара, задают соотношения между двумя типами симметрических многочленов, а именно между элементарными симметрическими многочленами и степенными суммами Ньютона. Для произвольного многочлена P они дают возможность выразить сумму k-х степеней всех корней P (с учётом кратности) через коэффициенты P, без фактического нахождения корней. Эти тождества были открыты Исааком Ньютоном около 1666 года, и возможно, в ранних работах (1629) Альберта Жирара. Они находят применение во многих областях математики, в том числе в теории Галуа, теории инвариантов, теории групп, комбинаторике, а также в других науках, в том числе в общей теории относительности.

Формулировка тождеств

Для переменных <math>x_1,\dots,x_n</math> и для <math>k \ge 1</math> рассмотрим суммы <math>k</math>-тых степеней этих переменных:

<math>p_k(x_1,\ldots,x_n)=\sum\nolimits_{i=1}^nx_i^k = x_1^k+\cdots+x_n^k.</math>

Обозначим также через <math>e_k (x_1,\dots,x_n)</math> элементарные симметрические многочлены. Многочлен <math>e_k (x_1,\dots,x_n)</math> представляет собой сумму всех возможных произведений <math>k</math> разных переменных, в частности

<math>\begin{align}

e_0(x_1,\ldots,x_n) &= 1,\\ e_1(x_1,\ldots,x_n) &= x_1+x_2+\cdots+x_n,\\ e_2(x_1,\ldots,x_n) &= \textstyle\sum_{1 \leq i<j\leq n}x_ix_j,\\ 

     & {}\ \ \vdots  \\

e_n(x_1,\ldots,x_n) &= x_1x_2\cdots x_n,\\ e_k(x_1,\ldots,x_n) &= 0, \quad\text{for}\ k>n.\\ \end{align}</math>

Тогда тождества Ньютона могут быть записаны следующим образом:

<math> ke_k(x_1,\ldots,x_n) = \sum_{i=1}^k(-1)^{i-1} e_{k-i} (x_1,\ldots,x_n) p_i(x_1,\ldots,x_n),</math>

для всех <math>k \ge 1</math>. В частности, для <math>k > n \ge 1</math>

<math> 0 = \sum_{i=k-n}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n),</math>

Для нескольких первых значений <math>k</math> получим:

<math>\begin{align}
e_1(x_1,\ldots,x_n) &= p_1(x_1,\ldots,x_n),\\
2e_2(x_1,\ldots,x_n) &= e_1(x_1,\ldots,x_n)p_1(x_1,\ldots,x_n)-p_2(x_1,\ldots,x_n),\\
3e_3(x_1,\ldots,x_n) &= e_2(x_1,\ldots,x_n)p_1(x_1,\ldots,x_n) - e_1(x_1,\ldots,x_n)p_2(x_1,\ldots,x_n) + p_3(x_1,\ldots,x_n).\\

\end{align}</math>

Истинность этих тождеств не зависит от количества переменных, даже когда левая и правая части равны нулю. Эти равенства позволяют рекуррентно выразить <math>p_i</math> через <math>e_i</math>:

<math>\begin{align}
 p_1 &= e_1,\\
 p_2 &= e_1p_1-2e_2,\\
 p_3 &= e_1p_2 - e_2p_1 + 3e_3 ,\\
 p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4, \\
     & {}\ \ \vdots

\end{align}</math>

Способы доказательства

Каждое отдельное из тождеств Ньютона может быть проверено с помощью элементарных алгебраических операций, однако общая формула требует доказательства. Существует несколько различных способов вывода тождеств.

Ниже мы обозначаем количество переменных через <math>n</math>, а номер тождества (количество слагаемых в сумме в правой части) через <math>k</math>.

Через специальный случай <math>k=n</math>

По определению, <math>\prod_{i=1}^k (t - x_i) = \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)t^i</math>

Следовательно, при <math>t=x_j</math> имеем

<math>0= \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k){x_j}^i, \quad 1\leq j\leq k</math>

Суммируя по всем <math>j</math>, получаем

<math>0= (-1)^k k e_k(x_1,\ldots,x_k)+\sum_{i=1}^k(-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)p_i(x_1,\ldots,x_k),</math>

Из этого выражения немедленно следует <math>k</math>-тое тождество Ньютона при <math>k</math> переменных. Поскольку оно является тождеством между симметрическими однородными многочленами.

Далее всё выводится из этого факта. При <math>n < k</math> тождество очевидным образом получается из присваивания <math>x_{n+1}=x_{n+2}=\dots=x_{k}=0</math> в тождестве для <math>n=k</math>

Пусть теперь <math>n=k+1</math>. Обозначим через <math>f(x_1,\dots,x_n)</math> и <math>g(x_1,\dots,x_n)</math> соответственно левую и правую части тождества. Из выполнения тождества при <math>n=k</math> следует, что

<math>\begin{align}
 & f(0, x_2, \dots, x_k, x_{k+1}) = g(0, x_2, \dots, x_k, x_{k+1}) \\
 & f(x_1, 0, \dots, x_k, x_{k+1}) = g(x_1, 0, \dots, x_k, x_{k+1}) \\
 & \dots \\
 & f(x_1, x_2, \dots, 0, x_{k+1}) = g(x_1, x_2, \dots, 0, x_{k+1}) \\
 & f(x_1, x_2, \dots, x_k, 0) = g(x_1, x_2, \dots, x_k, 0)

\end{align}</math>

Однако из этого следует, что разность <math>f-g</math> представима в виде <math>h(x_1,\dots,x_n) x_i</math> для любого <math>i</math> (если бы не была, то при каких-то <math>x_1,\dots,x_{i-1},x_{i+1},\dots,x_{k+1}</math> разность была бы ненулевой и одно из равенств, обозначенных выше, не выполнялось бы). Следовательно, разность <math>f-g</math> представима в виде <math>h(x_1,\dots,x_n) x_1 x_2 \dots x_k x_{k+1}</math>, однако это невозможно так как полная степень и <math>f</math> и <math>g</math> равна <math>k</math>.

Аналогичные рассуждения для <math>n>k+1</math> дают индукционный переход и доказывают тождества для произвольного <math>n</math>.

Через формальные степенные ряды

Прямым раскрытием скобок можно получить, что

<math>\prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} e_k(x_1,\dots,x_n) t^{n-k}</math>
<math>\prod_{i=1}^n (1 - \frac{x_i}{t}) = \sum_{k=0}^n (-1)^{k} e_k(x_1,\dots,x_n) \frac{1}{t^k}</math>

Обозначая <math>s=\frac{1}{t}</math>, получаем <math>\prod_{i=1}^n (1 - x_i s) = \sum_{k=0}^n (-1)^{k} e_k(x_1,\dots,x_n) s^k</math>.

Формально дифференцируя (беря производную) по <math>s</math> и домножая обе части на <math>s</math>, получаем

<math>\begin{align}
 \sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) s^k 
   &=      s \sum_{i=1}^n \left[(-x_i) \prod\nolimits_{j \neq i}(1 - x_js)\right]\\
   &= -\left(\sum_{i=1}^n \frac{x_i s}{1 - x_i s}\right) \prod\nolimits_{j=1}^n (1 - x_j s)\\
   &= -\left[\sum_{i=1}^n \sum_{j=1}^\infty(x_i s)^j\right]\left[\sum_{\ell=0}^n (-1)^\ell e_\ell(x_1,\ldots,x_n) s^\ell\right]\\
   &=  \left[\sum_{j=1}^\infty p_j(x_1, \ldots, x_n)s^j\right] \left[\sum_{\ell=0}^n (-1)^{\ell - 1} e_\ell(x_1, \ldots, x_n) s^\ell\right],\\

\end{align}</math>

Так как тождественное равенство многочленов влечёт равенство всех коэффициентов, то по правилам умножения многочленов из этого напрямую следует, что

<math>(-1)^{k}k e_k(x_1,\ldots,x_n) = \sum_{j=1}^k (-1)^{k-j-1} p_j(x_1,\ldots,x_n)e_{k-j}(x_1,\ldots,x_n),</math>

Через телескопический ряд

Пусть фиксировано некоторое <math>k \ge 1</math>. Обозначим через <math>r^{(k)}_i(x_1,\dots,x_n)</math> сумму всех одночленов, состоящих из <math>k</math> различных переменных, одна из которых входит в одночлен со степенью <math>i</math>, а все другие - со степенью 1. Такие одночлены естественным образом возникают в произведении <math>p_i(x_1,\dots,x_n) e_{k-i}(x_1,\dots,x_n)</math> (переменные со степенью <math>i</math> "приходят" из полинома <math>p_i</math>, а остальные, входящие в одночлен с первой степенью - из <math>e_{k-i}</math>).

Конкретнее, легко проверяются следующие тождества:

<math>\begin{align}
   & p_1 e_{k-1} = k e_k + r^{(k)}_2 \\
   & p_i e_{k-i} = r^{(k)}_i + r^{(k)}_{i+1}, & 1 < i < k \\
   & p_k e_0 = p_k = r^{(k)}_k

\end{align}</math>

Особенность первого из них обусловлена, грубо говоря, тем, что при <math>i \ge 2</math> для одночлена <math>x_0^i x_1 \dots x_{k-i}</math> однозначно понятно, какая переменная взята из <math>p_i</math>, а какие - из <math>e_{k-i}</math>, так что каждый такой многочлен входит в произведение <math>p_i e_{k-i}</math> с коэффициентом <math>1</math>. В случае же <math>i=1</math> многочлен <math>x_1,\dots,x_k</math> встретится в произведении <math>p_1 e_{k-1}</math> ровно <math>k</math> раз - как каждое возможное перемножение одной из переменных с остальной частью одночлена: <math>x_1 x_2 \dots x_{k-1} x_k = x_1 \cdot x_2 x_3 \dots x_{k-1} x_k = x_2 \cdot x_1 x_3 \dots x_{k-1} x_k = \dots = x_k \cdot x_1 x_2 \dots x_{k-2} x_{k-1}</math>. Это даёт коэффициент <math>k</math> при <math>e_k</math>

Из представленных выше тождеств легко получить, что

<math>\begin{align}
   & p_1 e_{k-1} - p_2 e_{k-2} + \dots + (-1)^{k-1} p_k = \\
   & = k e_k + r^{(k)}_2 - \left({r^{(k)}_2 + r^{(k)}_3}\right) + \left({r^{(k)}_3 + r^{(k)}_4}\right) - \dots + (-1)^k r^{(k)}_k = \\
   & = k e_k + r^{(k)}_2 - r^{(k)}_2 - r^{(k)}_3 + r^{(k)}_3 + r^{(k)}_4 - r^{(k)}_4 \dots + (-1)^{k-1} r^{(k)}_k + (-1)^k r^{(k)}_k = \\
   & = k e_k \\

\end{align}</math>

Связанные тождества

Прямые представления элементарных симметрических многочленов степенными суммами

Раскрывая явно выражение <math>e_i</math> через <math>p_i</math>, получим представления

<math>\begin{align}
 e_1 &= p_1,\\
 e_2 &= \textstyle\frac12p_1^2 - \frac12p_2 &&= \textstyle\frac12 ( p_1^2 - p_2 ),\\
 e_3 &= \textstyle\frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\
 e_4 &= \textstyle\frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 
       &&= \textstyle\frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\

&~~\vdots\\ 

 e_n &= (-1)^n  \sum_{m_1 + 2m_2 + \cdots + nm_n = n \atop m_1 \ge 0, \ldots, m_n \ge 0} \prod_{i=1}^n \frac{(-p_i)^{m_i}}{m_i ! i^{m_i}} \\

\end{align}</math>

Общая формула может быть также переписана как

<math>e_n = \frac{(-1)^n}{n!} B_{n}(- p_1, -1! p_2, - 2! p_3, \ldots, - (n-1)! p_n ), </math>

где <math>B_n</math> - многочлен Белла. Такое представление, в частности, приводит к следующему тождеству производящих функций:

<math> \sum_{n=0}^\infty e_n \,X^n = \exp\left(\sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} p_n \,X^n \right). </math>

Прямое представление степенных сумм через элементарные симметрические многочлены

Аналогично, раскрывая напрямую рекуррентные выражения, можно получить, что

<math>\begin{align}
 p_1 &= e_1,\\
 p_2 &= e_1^2 - 2 e_2,\\
 p_3 &= e_1^3 - 3 e_2 e_1 + 3 e_3,\\
 p_4 &= e_1^4 - 4 e_2 e_1^2 + 4 e_3 e_1 + 2 e_2^2 - 4 e_4,\\
 p_5 &= e_1^5 - 5 e_2 e_1^3 + 5 e_3 e_1^2 + 5 e_2^2 e_1 - 5 e_4 e_1 - 5 e_3e_2 + 5 e_5,\\
 p_6 &= e_1^6 - 6 e_2 e_1^4 + 6 e_3 e_1^3 + 9 e_2^2 e_1^2 - 6 e_4 e_1^2 - 12 e_3 e_2 e_1 + 6 e_5 e_1 - 2 e_2^3 + 3 e_3^2 + 6 e_4 e_2 - 6e_6.

\end{align}</math>

Первые четыре формулы были получены Альбером Жираром ещё до Ньютона, в 1629 году. Общая формула имеет следующий вид:

<math>p_m = \sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m\ge 0} (-1)^m \frac{m(r_1 + r_2 + \cdots + r_m - 1)!}{r_1!r_2! \cdots r_m!} \prod_{i=1}^m (-e_i)^{r_i}.</math>

Это может быть переформулировано в терминах многочленов Белла:

<math>p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\dots,-e_{m-k+1}).</math>

Приложения

Приложения к корням многочленов

Многочлен <math>f(x)</math> с корнями <math>x_1, \dots, x_n</math> может быть представлен как

<math> f(x) = \prod_{i=1}^n \left( x - x_i \right) = \sum_{k=0}^n (-1)^{n-k} e_{n-k} x^{k},</math>,

где коэффициенты <math>e_k = e_k (x_1, \dots, x_n)</math> - симметрические многочлены, определённые выше. При известных значениях степенных сумм <math>p_k (x_1, \dots, x_n) = \sum \limits_{i=1}^{n} {{x_i}^k}</math> коэффициенты многочлена <math>f(x)</math> можно найти из рекуррентных формул.

Приложения к характеристическим многочленам матриц

Тождества Ньютона позволяют свести вычисление коэффициентов характеристического многочлена матрицы <math>A</math> к вычислению следа различных её степеней.

Рассмотрим характеристический многочлен некоторой матрицы <math>A</math>. Его корни <math>x_1, \dots, x_n</math> являются собственными числами этой матрицы (каждый корень представлен со своей кратностью). Тогда коэффициенты характеристического многочлена выражаются через симметрические многочлены <math>e_i</math>.

Для любого положительного <math>k</math> собственными числами матрицы <math>A^k</math> являются степени <math>{x_1}^k, \dots, {x_n}^k</math>. Поскольку сумма собственных чисел матрицы равна её следу, то

<math>p_k (x_1, \dots, x_n) = tr(A^k)</math>

Следовательно, и <math>e_1, \dots, e_n</math>, и коэффициенты характеристического многочлена можно выразить линейно из <math>tr(A), \dots, tr(A^n)</math>. Вычисление коэффициентов многочлена, таким образом, сводится к двум этапам:

  • вычисление степеней матрицы <math>A</math> и их следа
  • решение системы линейных уравнений с треугольной матрицей

Оба этапа относятся к классу сложности NC, так что задача нахождения коэффициентов характеристического многочлена тоже относится к классу NC. На этой идее основан Шаблон:Iw (1840).

Поскольку по теореме Гамильтона-Кэли любая матрица является корнем своего характеристического многочлена, то быстрое вычисление коэффициентов этого многочлена даёт быстрый способ нахождения обратной матрицы.

Приложения к тригонометрическим суммам

Тождества Ньютона могут использоваться при оценке рациональных тригонометрических сумм по простому модулю для однозначного нахождения частного случая интеграла Виноградова при равном количестве переменных и уравнений.

Примечания

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Тождества_Ньютона&oldid=10935456