Формулы Виета

[Odysseus]

EminentVictorians
А бином Ньютона вы когда-то выводили? Там похожая логика сборки членов с одинаковыми степенями.

[nnosipov]

EminentVictorians в сообщении #1499891 писал(а):

Если расскажете, с удовольствием послушаю))

Пусть, к примеру, у нас три скобки: в первой 2 слагаемых, во второй --- 4, а в третьей --- 7. Правило такое: нужно в каждой скобке выбрать по одному слагаемому и все выбранные слагаемые перемножить; затем все так полученные произведения следует сложить. В нашем примере будет ровно $2 \cdot 4 \cdot 7$ таких произведений (понятно ли, почему?). Их сумма и будет произведение наших трех скобок в так называемом раскрытом виде (намекаю на известно выражение "раскрыть скобки в произведении").

[v_n]

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

[Odysseus]

Мне, кстати, в свое время для понимания стандартного комбинаторного рассуждения типа "Если можно некий $A$ выбрать или сделать $a$ способами, и при этом $B$ независимо $b$ способами, а $C$ - $c$ способами, то количество всех вариантов равно $a\cdot b\cdot c$" помогла аналогия с тем, сколькими способами можно приехать из города $A$ в город $D$, проехав также города $B$ и $C$, если количество дорог из $A$ в $B$ равно $a$, из $B$ в $C$ равно $b$, и из $C$ в $D$ равно $c$.

В последней задаче, если представлять пути последовательно, а не одновременно, то весьма очевидно, что всего их $a\cdot b\cdot c$. В общем комбинаторном рассуждении с подобными вариантами тоже удобно представлять их "последовательно" как "дороги, которые мы выбираем".

[nnosipov]

Вообще, умение перемножать конечные суммы (и даже ряды) затем пригодится в методе производящих функций, который широко используется в комбинаторике. Хороший пример содержательной комбинаторной задачи на эту тему: подсчитать число счастливых билетов (в диапазоне от 000000 до 999999).

[EminentVictorians]

nnosipov в сообщении #1499896 писал(а):

Пусть, к примеру, у нас три скобки: в первой 2 слагаемых, во второй --- 4, а в третьей --- 7. Правило такое: нужно в каждой скобке выбрать по одному слагаемому и все выбранные слагаемые перемножить; затем все так полученные произведения следует сложить.

Кажется, до меня дошло. Пусть есть произведение $n$ скобок $(a_{11}\cdot ... \cdot a_{1k_1}) \cdot ... \cdot(a_{n1} \cdot ... \cdot a_{nk_n})$. Тогда это произведение равно сумме всевозможных произведений $a_{1s_1} \cdot ... \cdot a_{ns_n}$ по всем перестановкам $s_1, ... , s_n$ таким, что $s_i \in \overline{1, k_i}$. Я не понимаю, как этот факт прошел мимо меня. В очередной раз благодарю Вас! Теперь со стандартным доказательством формул Виета я справлюсь.

v_n в сообщении #1499916 писал(а):

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

Понимаете, у меня все очень плохо с неформальными объяснениями.

1. Я понимаю так, что определитель - это определитель матрицы, а матрица состоит из элементов некоторого поля $K$. Как в определителе может быть $x$?
2. Как определитель может быть многочленом? Это же просто элемент поля.

Вы не подумайте, что я пытаюсь придираться - это совершенно не так. Я когда эти формулы Виета доказывал, мне первое, что пришло в голову - это интерполяционный многочлен Лагранжа. А где этот многочлен, там и определитель Вандермонда. Теперь оказывается, что произведение сумм является суммой произведений по всем перестановкам (что намекает на связь с определителем). А учитывая, что в формулах Виета еще и $(-1)^k$ фигурирует... Короче, тут точно есть связь. Поэтому я Ваше доказательство просто обязан понять. Но без подробностей с Вашей стороны у меня не получится.

[nnosipov]

EminentVictorians в сообщении #1499932 писал(а):

по всем перестановкам $s_1, ... , s_n$

Слово "перестановки" здесь не совсем уместно (оно было бы уместно в частном случае, когда $k_1=\ldots=k_n$, и то в виде так называемых "перестановок с повторениями"). Лучше употреблять термин "упорядоченный набор" (элемент декартова произведения).

[EminentVictorians]

Не знаю, об этом говорил v_n или не об этом, но кажется я смог сделать набросок другого доказательства формул Виета.

Итак, пусть есть многочлен $f = a_nx^n + ... +a_1x + a_0$, который разлагается на линейные множители: $f = a_n(x - c_1)\cdot ... \cdot (x - c_n)$. Тогда каждый из элементов $c_i$ является корнем многочлена $f$ (среди $c_i$ могут быть одинаковые) и никаких других корней, отличных от $c_i$, у $f$ нету.

Знание одних лишь корней не позволяет однозначно восстановить многочлен $f$. Но если известен еще и коэффициент $a_n$, то тогда однозначно восстановить многочлен можно. Собственно, насколько я понял, формулы Виета ровно об этом: зная корни $c_1, ... , c_n$ и старший коэффициент $a_n$ найти все коэффициенты $a_i, (i \ne n)$ многочлена $f$ в его каноническом представлении $f = a_nx^n + ... +a_1x + a_0$.

Тогда, справедлив следующий набор равенств:

$$a_nc_1^n + ... + a_1c_1 + a_0 = 0$$

$$..........$$

$$a_nc_n^n + ... + a_1c_n + a_0 = 0$$

Наша цель - найти все $a_i ,i \ne n$ (т.к. $a_n$ нам дан по условию). А это значит, что надо решить систему

$$\begin{cases} 1x_0 + c_1x_1 ... + c_1^{n - 1}x_{n - 1}= -a_nc_1^n&\\ ....&\\ 1x_0 + c_nx_1 ... + c_n^{n-1}x_{n-1} = -a_nc_n^n&\\ \end{cases}$$

Здесь я сталкиваюсь с очень странным и непонятным мне моментом. Матрица коэффициентов этой СЛАУ является матрицей Вандермонда. Но ведь среди $c_i$ могут быть одинаковые, а это приведет к тому, что определитель Вандермонда станет равным нулю. А значит эта СЛАУ будет либо несовместна, либо неопределенна. Но формулы Виета из учебника определяют $a_i, i \ne n$ через $a_n$ и $c_i$ однозначно. А здесь получается, что если среди $c_i$ найдутся одинаковые, то однозначного определения $a_i, i \ne n$ не будет. Где ошибка?


Если же все $c_i$ разные, то определитель Вандермонда не равен нулю, а значит данная СЛАУ определенна. Перепишем ее в матричном виде: $AX=B$, где $A$ - матрица коэффициентов, $X = \begin{pmatrix} x_0 \\ ... \\ x_{n-1} \end{pmatrix}$, $B$ - столбец свободных членов. Раз $\det A \ne 0$, значит $A$ обратима. Умножим обе части матричного равенства на $A^{-1}$ слева и получим $X = A^{-1}B$.

С помощью формул Крамера получим явные формулы для элементов обратной матрицы:

$$A^{-1} = \begin{pmatrix} \frac{A_{11}}{\det A} & ... & \frac{A_{n1}}{\det A}\\ ... & & ... \\ \frac{A_{1n}}{\det A} & ... & \frac{A_{nn}}{\det A} \end{pmatrix}$$

где $A_{ij}$ - алгебраические дополнения соответствующих элементов в матрице $A$.

Осталось найти $x_i, i \ne n$. Найдем, для простоты, $x_0$ (т.е. коэффициент $a_0$ в каноническом представлении многочлена $f$). $a_0 = \frac{A_{11}}{\det A} \cdot (-a_nc_1^n) + ... + \frac{A_{n1}}{\det A} \cdot (-a_nc_n^n)$ Я на 100% уверен, что это и есть первая формула Виета. Вот только упростить ее у меня не получается. Все дело в выражениях вида $\frac{A_{i1}}{\det A}$. Учитывая, что искать надо не только первую формулу Виета, то понятно, что надо научиться упрощать выражения вида $\frac{A_{ij}}{\det A}$. И это второе место в доказательстве, которое я не осилил. Видно, что такое выражение должно нормально упроститься: внизу стоит определитель Вандермонда, т.е. $\prod\limits_{i > j}(x_i - x_j)$. В числителе должно стоять нечто подобное, но что именно, я не могу сказать.

Таким образом, у меня 2 основных вопроса:

1. Где ошибка в рассуждении о неопределенности/несовместности той СЛАУ с нулевым определителем матрицы коэффициентов?
2. Как упростить полученную формулу Виета с алгебраическими дополнениями (ну и вообще, как упрощать выражения вида $\frac{A_{ij}}{\det A}$)?

[lel0lel]

Если умеете дифференцировать и знакомы с формулой Лейбница, то сможете доказать следующую формулу:
$f^{(m)}(z)=m! \, e_{n-m}(z-\lambda_1,\ldots,z-\lambda_n).$
Из неё следует теорема Виета.

[nnosipov]

EminentVictorians в сообщении #1500054 писал(а):

Где ошибка?

Ошибка в том, что, помимо тех уравнений, что Вы написали, есть еще и другие уравнения (подумайте, какие). Одно дело быть простым корнем, другое дело --- быть корнем кратности 2 (например). Если написать все необходимые уравнения, однозначность будет.

[EminentVictorians]

nnosipov в сообщении #1500080 писал(а):

Одно дело быть простым корнем, другое дело --- быть корнем кратности 2 (например).

Не вижу, на что здесь кратность влияет.

nnosipov в сообщении #1500080 писал(а):

Если написать все необходимые уравнения, однозначность будет.

Тогда же система квадратной не будет и определителя Вандермонда не будет.

[nnosipov]

EminentVictorians в сообщении #1500100 писал(а):

Не вижу, на что здесь кратность влияет.

Ну как же: если $c$ --- корень кратности 2 многочлена $f(x)$, то $f(x)$ делится на $(x-c)^2$. Это более жесткое (ограничительное) требование, чем просто делимость $f(x)$ на $x-c$.

EminentVictorians в сообщении #1500100 писал(а):

Тогда же система квадратной не будет и определителя Вандермонда не будет.

Пардон, я хотел сказать примерно следующее: из каждой группы одинаковых уравнений в Вашей системе надо оставить только одно, а остальные уравнения заменить на другие уравнения. Например, если считать $c_1=c_2$, то 1-е и 2-е уравнения в системе будут совпадать; из них нужно оставить одно, а второе заменить другим уравнением (каким, Вы должны догадаться).

[EminentVictorians]

nnosipov в сообщении #1500104 писал(а):

Ну как же: если $c$ --- корень кратности 2 многочлена $f(x)$, то $f(x)$ делится на $(x-c)^2$. Это более жесткое (ограничительное) требование, чем просто делимость $f(x)$ на $x-c$.

Это я понимаю. Но уравнения системы таковы, что все, что требуется от $c_i$ - это просто быть корнем многочлена. Я не очень понимаю, на что его кратность влияет.

nnosipov в сообщении #1500104 писал(а):

из каждой группы одинаковых уравнений в Вашей системе надо оставить только одно, а остальные уравнения заменить на другие уравнения.

Тогда система перестанет быть квадратной. А что делать с такой неквадратной системой я даже не представляю.

-- 10.01.2021, 19:04 --

А, извиняюсь. Вы написали "заменить", а я прочитал "убрать". Сейчас подумаю над этим.

[nnosipov]

EminentVictorians в сообщении #1500108 писал(а):

Я не очень понимаю, на что его кратность влияет.

Если на кратность не обращать внимание, то часть информации о корнях многочлена будет потеряна. Поэтому неудивительно, что многочлен не удастся найти однозначно.

[EminentVictorians]

nnosipov в сообщении #1500114 писал(а):

Если на кратность не обращать внимание, то часть информации о корнях многочлена будет потеряна. Поэтому неудивительно, что многочлен не удастся найти однозначно.

Я не точно выразился. Мы же знаем $c_1, ... , c_n$. И знаем, что среди них некоторые могут повторяться. Иными словами, я смотрю на список $c_i$ и там, допустим, где-то в середине написано что-то из разряда ... $c_{101} = 14,5$, $c_{102} = 14,5$, $c_{103} = 14,5$, ... . Этой информации (знание точной строки $c_i$) должно быть достаточно, чтобы однозначно восстановить многочлен. Другое дело, что зная эту информацию, можно с каждым корнем связать его кратность. Т.е. посчитать, сколько повторяющихся цэшек имеют какое-то выбранное значение. Но очевидно, что эта информация уже заложена в первоначально данную строку $c_1, ... , c_n$. Поэтому, зная строку $c_1, ... , c_n$ (а мы ее знаем, т.к. она нам дана), информация о кратности не теряется.