Нахождение корней многочлена. Известен ли этот способ?

[serval]

Мое увлечение ВТФ иногда дает результаты лежащие в стороне от главной темы, но интересные сами по себе. Одна из таких ветвей - комбинаторно-геометрический подход к нахождению корней многочленов. Долго у меня ничего не получалось, да и сейчас это лишь первый набросок, но мне он кажется любопытным. Возможно, из него удастся извлечь практическую пользу, например, улучшить соответствующие алгоритмы. Основа представляемого мной способа давно известна, но я не встречал такого ее приложения. Коротко напомню суть дела.
Натуральное число в натуральной степени можно представить в виде суммы

$x^n=\sum\limits_{k=0}^n k!S(n,k)\binom{x}{k}$

где $S(n,k)$ - числа Стирлинга второго рода, а $\binom{x}{k}$ - биномиальные коэффициенты.

Оказалось, что произведения факториалов на числа Стирлинга в этой формуле можно заменить специальными числами, которых я не нашел в литературе, вычисляемые по рекуррентному правилу (но можно вычислять и другим способом)

$A_2(n,k)=(k-1)A_2(n-1,k-1)+kA_2(n-1,k)$

Тогда формула для степени числа примет вид скалярного произведения

$x^y=\sum\limits_{k=0}^n \binom{x}{k}A_2(y,k)$

где векторами будут строки треугольников - Паскаля и $A_2$-треугольника.
Приведу первые строки каждого из них

$\begin{array}{cccccc} &\multicolumn{1}{|c}{1}&2&3&4&5\\ \hline 1&\multicolumn{1}{|c}{1}&0&0&0&0\\ 2&\multicolumn{1}{|c}{1}&1&0&0&0\\ 3&\multicolumn{1}{|c}{1}&2&1&0&0\\ 4&\multicolumn{1}{|c}{1}&3&3&1&0\\ 5&\multicolumn{1}{|c}{1}&4&6&4&1 \end{array}$

$\begin{array}{cccccc} &\multicolumn{1}{|c}{1}&2&3&4&5\\ \hline 0&\multicolumn{1}{|c}{1}&0&0&0&0\\ 1&\multicolumn{1}{|c}{1}&1&0&0&0\\ 2&\multicolumn{1}{|c}{1}&3&2&0&0\\ 3&\multicolumn{1}{|c}{1}&7&12&6&0\\ 4&\multicolumn{1}{|c}{1}&15&50&60&24 \end{array}$

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

$\sum\limits_i c_i x^i=0$

Используя эти два условия - представление числа в степени как скалярного произведения и представление многочлена как скалярного произведения - можно переписать многочлен как новое скалярное произведение с коэффициентами при элементах строки треугольника Паскаля.
Покажу на примере.
Рассмотрим квадратное уравнение

$x^2-11x +24=0$

Преобразуем его к скалярному произведению со строкой треугольника Паскаля. Для этого вычислим новый вектор коэффициентов

$\left(1,-11,24\right) \left (\begin{array}{ccc} 1&3&2\\ 1&1&0\\ 1&0&0 \end{array}\right)= \left(14,-8,2\right)$

и далее получим необходимое нам скалярное произведение

$14 -8(x-1)+2\frac{(x-1)(x-2)}{2}=0$ или $(x-1)(x-10)=-14$

но $14=2\cdot 7$ откуда $x-1=2$ или $x-1=7$ и значит $x=3$ или $x=8$ что проверяется подстановкой в исходное уравнение.

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

[Urnwestek]

serval в сообщении #784212 писал(а):

корни которого натуральны и различны

Казалось бы, коль корни натуральны значит искать их стоит среди делителей свободного члена. К чему такие сложности?

[serval]

Возможно, что ни к чему. Корни могут не быть взаимно простыми. Дает ли этот способ какой-то выигрыш я не знаю. Конечно, нужно рассмотреть и кратные корни, но пока я хочу просто посмотреть работает ли схема вообще.

[arseniiv]

Раз вы себе не можете сконструировать многочлен, вот:

$$216972 + 69615 x - 4164 x^2 - 886 x^3 + 64 x^4 - x^5.$$

[serval]

А его корни точно натуральные? Знаки странно чередуются. Я попробую.

[nnosipov]

serval в сообщении #784226 писал(а):

Дает ли этот способ какой-то выигрыш я не знаю.

Вряд ли. Чтобы найти целые корни многочлена $f(x)$ с целыми коэффициентами, можно решить сравнение $f(x) \equiv 0 \pmod{p}$, где $p$ --- достаточно большое простое число. Это делается быстро, если степень многочлена $f(x)$ не слишком велика (при этом коэффициенты могут быть настолько большими, что школьный способ, основанный на поиске делителей свободного члена, не сработает).

[arseniiv]

serval в сообщении #784387 писал(а):

А его корни точно натуральные? Знаки странно чередуются.

Разумеется. Он получен раскрытием $-(x-a)(x-b)(x-c)(x-d)(x-e)$.

[serval]

Извиняюсь за долгое молчание. Запутался и чтобы разобраться пришлось вернуться к квадратному уравнению. Решение получилось забавным.
Алгоритм такой:

1. Возьмем из первого поста темы вектор нормали плоскости которой принадлежат вектор-корни

$\vec n=\left(7,-4,1 \right)$

2. По нему построим два вектора принадлежащие той же плоскости что и вектор-корни

$\vec x_1=\left(-1,0,7 \right)$ и $\vec x_2=\left(0,1,4 \right)$

3. Через концы этих векторов проведем прямую

$\frac{x+1}{1}=\frac{y}{1}=\frac{z-7}{-3}$

4. Пересечем эту прямую с плоскостью

$x=1$

5. Получим первый вектор-корень

$\vec a=\left(1,2,1 \right)$

Из треугольника Паскаля видим, что корень (номер строки) равен второму компоненту вектор-корня (строки треугольника) увеличенному на 1.
Таким образом, первый корень исходного уравнения имеет значение $a=2+1=3$ .

Всё

[serval]

Не всё. Второй корень тоже можно найти этим способом

[serval]

Неужели совсем не интересно? Ведь никаких степеней и радикалов.

[Aritaborian]

serval в сообщении #793186 писал(а):

Таким образом, первый корень исходного уравнения имеет значение $a=2+1=3$ .

Вот только это не так.

[serval]

Почему?

[Aritaborian]

Потому что не $3$, а $-3$. Ах ты ж чёрт, я думал, вы о многочлене пятой степени, который предложил arseniiv. Прошу прощения за невнимательность.

[serval]

Я опять заблудился. Блуждал пока не выбрел на (трехмерные) векторы $b, d, p, q$ такие, что

$ \left\{ \begin{array}{lll} (b,p)=(d,q) \\ (b,q)=(d,p) \\ \end{array} \right. $

При этом, первые компоненты всех векторов равны $1$ , что намекает на проективность конструкции.
Можно ли из этого соотношения векторов сделать какие-нибудь полезные выводы?

P.S. К тому же, два из них (скажем, $b,d$) являются усеченными до трех элементов строками треугольника Паскаля.

[serval]

Вдогонку.
Такую систему из четырех трехмерных векторов можно выписать, по крайней мере, для любого квадратного уравнения имеющего натуральные различные корни. При этом векторы $b,d$ (строки треугольника Паскаля) будут отвечать корням уравнения. Каков смысл двух других векторов я не знаю.