Меню Главная Случайная статья Настройки Результант Материал из https://ru.wikipedia.org В математике, результантом ${\displaystyle {\mathcal {R}}}$ двух многочленов ${\displaystyle P(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}}$ и ${\displaystyle Q(x)=b_{0}+b_{1}x+b_{2}x^{2}+\dots +b_{m}x^{m}}$ над некоторым полем ${\displaystyle \mathbb {K} }$, называется выражение ${\displaystyle {\mathcal {R}}=\mathrm {res} (P,Q)=a_{n}^{m}b_{m}^{n}\prod _{P(\alpha )=0,\,Q(\beta )=0}(\alpha -\beta )}$, где ${\displaystyle \alpha }$ — корень ${\displaystyle P(x)}$, а ${\displaystyle \beta }$ — корень ${\displaystyle Q(x)}$. Иными словами, это произведение попарных разностей между их корнями. Произведение здесь берётся по всем корням в алгебраическом замыкании поля ${\displaystyle \mathbb {K} }$ с учётом их кратностей; поскольку получающееся выражение является симметрическим многочленом от корней многочленов ${\displaystyle P}$ и ${\displaystyle Q}$ (лежащих, быть может, вне поля ${\displaystyle \mathbb {K} }$), оно тем самым оказывается многочленом от коэффициентов ${\displaystyle P}$ и ${\displaystyle Q}$. Содержание 1 Результант как определитель матрицы Сильвестра 2 Результант как функция корней 3 Алгоритм Евклида для нахождения результанта двух многочленов 4 Свойства и способы вычисления 5 Литература 6 Ссылки Результант как определительматрицы Сильвестра Результант естественным образом возникает в задаче нахождения наименьшего общего кратного многочленов методом неопределённых коэффициентов. Пусть ${\displaystyle n=\deg P,\,m=\deg Q}$ и ${\displaystyle T(x)}$ - наименьшее общее кратное (НОК) многочленов ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$. Если ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$ взаимно просты, тогда ${\displaystyle T(x)=P(x)Q(x)}$ и ${\displaystyle \deg T(x)=\deg P+\deg Q=m+n}$ (полная степень). В противном случае степень многочлена ${\displaystyle T(x)}$ должна быть неполной (меньше ${\displaystyle m+n}$). В этом случае ${\displaystyle T(x)=P(x)u(x)=v(x)Q(x)}$, причём ${\displaystyle \deg u<m,\,\deg v<n}$. Таким образом получено линейное соотношение ${\displaystyle P(x)u(x)-v(x)Q(x)=0}$. Чтобы попытаться найти НОК неполной степени, записывают ${\displaystyle u(x)}$ и ${\displaystyle v(x)}$ в неопределённых коэффициентах ${\displaystyle u(x)=u_{0}+u_{1}x+u_{2}x^{2}+\dots +u_{m-1}x^{m-1}}$ и ${\displaystyle v(x)=v_{0}+v_{1}x+v_{2}x^{2}+\dots +v_{n-1}x^{n-1}}$, после чего полученное выше соотношение приводит к однородной системе линейных уравнений: ${\displaystyle {\begin{pmatrix}a_{n}&0&\cdots &0&b_{m}&0&\cdots &0\\a_{n-1}&a_{n}&\cdots &\cdots &b_{m-1}&b_{m}&\cdots &\cdots \\a_{n-2}&a_{n-1}&\cdots &0&\cdots &\cdots &\cdots &\cdots \\\cdots &a_{n-2}&\cdots &a_{n}&\cdots &\cdots &\cdots &\cdots \\\cdots &\cdots &\cdots &a_{n-1}&b_{0}&b_{1}&\cdots &0\\a_{0}&a_{1}&\cdots &a_{n-2}&0&b_{0}&\cdots &b_{m}\\0&a_{0}&\cdots &\cdots &\cdots &0&\cdots &\cdots \\\cdots &\cdots &\cdots &a_{1}&\cdots &\cdots &\cdots &b_{1}\\0&0&\cdots &a_{0}&0&0&\cdots &b_{0}\\\end{pmatrix}}{\begin{pmatrix}u_{m-1}\\u_{m-2}\\\cdots \\u_{0}\\-v_{n-1}\\-v_{n-2}\\\cdots \\-v_{0}\\\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\0\\\end{pmatrix}}}$ Матрица этой системы и есть матрица Сильвестра ${\displaystyle S_{P,Q}}$, построенная по многочленам ${\displaystyle P}$ и ${\displaystyle Q}$ (также матрицей Сильвестра называют транспонированную к ней матрицу). Поскольку матрица системы получилась квадратная, нетривиальное решение существует тогда и только тогда, когда равен нулю определитель этой системы. По определению, результант многочленов и есть определитель соответствующей матрицы Сильвестра: ${\displaystyle \mathrm {res} (P,Q)=\det S_{P,Q}}$ Основной вывод из вышерассмотренного состоит в том, что результант — это многочлен с целыми коэффициентами от коэффициентов ${\displaystyle P}$ и ${\displaystyle Q}$, равный нулю в том и только том случае, когда у многочленов ${\displaystyle P}$ и ${\displaystyle Q}$ имеется нетривиальный общий делитель (степени 1 или выше), и как следствие, общий корень, возможно, в некотором расширении поля ${\displaystyle \mathbb {K} }$. Результант как функция корней Предположим, полиномы ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$ имеют полную систему корней ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ и ${\displaystyle \{x'_{1},x'_{2},\dots ,x'_{m}\}}$ в некотором расширении основного поля ${\displaystyle \mathbb {K} }$. Тогда они полностью разложимы ${\displaystyle P(x)=a_{n}(x-x_{1})(x-x_{2})\dots (x-x_{n})}$, ${\displaystyle Q(x)=b_{m}(x-x'_{1})(x-x'_{2})\dots (x-x'_{m})}$, и их коэффициенты связаны с корнями формулами Виета: ${\displaystyle a_{n-k}=(-1)^{k}a_{n}\sigma _{k}(x_{1},x_{2},\dots ,x_{n})}$ ${\displaystyle b_{m-k}=(-1)^{k}b_{m}\sigma _{k}(x'_{1},x'_{2},\dots ,x'_{m})}$, где ${\displaystyle \sigma _{k}}$ - элементарные симметрические многочлены. Так как они имеют целые коэффициенты, после подстановки формул Виета в определитель Сильвестра получится выражение ${\displaystyle \mathrm {res} (P,Q)=a_{n}^{m}b_{m}^{n}F(x_{1},x_{2},\dots ,x_{n};x'_{1},x'_{2},\dots ,x'_{m})}$, где ${\displaystyle F\in \mathbb {Z} [x_{1},x_{2},\dots ,x_{n};x'_{1},x'_{2},\dots ,x'_{m}]}$ - полином с целыми коэффициентами от всех своих параметров - корней многочленов ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$. Если какой-нибудь из корней ${\displaystyle x_{i}}$ совпадает с каким-нибудь корнем ${\displaystyle x'_{j}}$, многочлены ${\displaystyle P(x)}$ и ${\displaystyle Q(x)}$ имеют нетривиальный общий делитель (а именно, ${\displaystyle x-x_{i}}$), их результант будет равен 0, и следовательно, многочлен ${\displaystyle F}$ тоже обнулится. Это значит, что он делится на каждую разность ${\displaystyle x_{i}-x'_{j}}$, и, поскольку эти разности взаимно просты в кольце многочленов ${\displaystyle \mathbb {Z} [x_{1},x_{2},\dots ,x_{n};x'_{1},x'_{2},\dots ,x'_{m}]}$, он делится и на их произведение. Следовательно, ${\displaystyle F=G\cdot \prod \limits _{i,j}(x_{i}-x'_{j})}$. Сравнение степеней позволяет убедиться, что для каждого ${\displaystyle x_{i}}$ ${\displaystyle \deg _{x_{i}}G=0}$. В самом деле, по свойству симметрических много членов ${\displaystyle \deg _{x_{i}}a_{n-k}=\deg _{x_{i}}\sigma _{k}(x_{1},x_{2},\dots ,x_{n})=1}$, и так как коэффициенты ${\displaystyle a_{n-k}}$ присутствуют ровно в ${\displaystyle m}$ столбцах матрицы Сильвестра, то ${\displaystyle \deg _{x_{i}}\mathrm {res} (P,Q)\leqslant m=\deg _{x_{i}}\prod \limits _{i,j}(x_{i}-x'_{j})}$, так что ${\displaystyle \deg _{x_{i}}G=\deg _{x_{i}}\mathrm {res} (P,Q)-\deg _{x_{i}}\prod \limits _{i,j}(x_{i}-x'_{j})\leqslant 0}$. Аналогично получается ${\displaystyle \deg _{x'_{j}}G=0}$, так что множитель ${\displaystyle G}$ должен быть константой. Далее сравнение коэффициентов в определителе Сильвестра и в произведении разностей корней даёт, что ${\displaystyle G=1}$. Окончательно получается формула результанта как функции корней: ${\displaystyle \mathrm {res} (P,Q)=a_{n}^{m}b_{m}^{n}\prod _{i,j}(x_{i}-x'_{j})}$. Третья формула результанта получается из предыдущей группировкой множителей: ${\displaystyle \mathrm {res} (P,Q)=a_{n}^{m}b_{m}^{n}\prod _{i,j}(x_{i}-x'_{j})=a_{n}^{m}\prod _{i}(b_{m}\prod _{j}(x_{i}-x'_{j}))=a_{n}^{m}\prod _{i}Q(x_{i})}$, т.е. ${\displaystyle \mathrm {res} (P,Q)=a_{n}^{m}\prod _{i}Q(x_{i})}$. Данная формула работает уже без каких-либо предположений о корнях многочлена ${\displaystyle Q(x)}$. Аналогично этому выводится формула: ${\displaystyle \mathrm {res} (P,Q)=(-1)^{mn}b_{m}^{n}\prod _{j}P(x'_{j})}$. Алгоритм Евклидадля нахождения результанта двух многочленов При нахождении НОД многочленов алгоритмом Евклида получается цепочка многочленов ${\displaystyle f_{0}(x),f_{1}(x),\dots ,f_{m}(x)}$, степени которых убывают: ${\displaystyle d_{0}\geqslant d_{1}>d_{2}\dots >d_{n}}$, а сами они связаны линейными соотношениями: ${\displaystyle f_{k+1}(x)=g_{k}(x)f_{k}(x)+f_{k-1}(x)}$ где ${\displaystyle g_{k}(x)\in K[x]}$ - некоторые многочлены (неполные частные при делении с остатком). Пусть ещё ${\displaystyle a_{0},a_{1},\dots ,a_{m}\in K}$ - коэффициенты при старших степенях переменной ${\displaystyle x}$ в многочленах ${\displaystyle f_{0}(x),f_{1}(x),\dots ,f_{m}(x)}$. Применим третью формулу результанта к паре соседних многочленов ${\displaystyle f_{k+1}(x),f_{k}(x)}$ в данной цепочке: ${\displaystyle \mathrm {res} (f_{k},f_{k+1})=a_{k}^{d_{k+1}}\prod \limits _{x_{i}:f_{k}(x)=0}f_{k+1}(x_{i})=a_{k}^{d_{k+1}}\prod \limits _{x_{i}:f_{k}(x)=0}f_{k-1}(x_{i})}$, так как, очевидно ${\displaystyle f_{k+1}(x_{i})=f_{k-1}(x_{i})}$. Следовательно, получается реуррентное соотношение: ${\displaystyle \mathrm {res} (f_{k},f_{k+1})=a_{k}^{d_{k+1}-d_{k-1}}\mathrm {res} (f_{k},f_{k-1})}$. Если многочлены ${\displaystyle f_{0}(x),f_{1}(x)}$ не взаимно просты, то ${\displaystyle \mathrm {res} (f_{k},f_{k+1})=0}$, в противном случае последний ненулевой многочлен в цепочке - константа, и с точностью до знака ${\displaystyle \mathrm {res} (f_{0},f_{1})=\pm \prod \limits _{k=1}^{m}a_{k}^{d_{k+1}-d_{k-1}}}$. Именно на этой формуле часто основаны алгоритмы расчёта результанта двух многочленов, используемые в системах компьютерной алгебры. Свойства и способы вычисления ${\displaystyle \mathrm {res} (P_{1}P_{2},Q)=\mathrm {res} (P_{1},Q)\mathrm {res} (P_{2},Q)}$ ${\displaystyle \mathrm {res} (P,\operatorname {const} )=\operatorname {const} ^{\deg P}}$ ${\displaystyle \mathrm {res} (AP(x),BQ(x))=A^{\deg Q}B^{\deg P}\mathrm {res} (P(x),Q(x))}$ Если ${\displaystyle A,C\neq 0,\deg(AP(x)+BQ(x))=\deg(CP(x)+DQ(x))=n\geqslant 1}$, то ${\displaystyle \mathrm {res} (AP(x)+BQ(x),CP(x)+DQ(x))=(AD-BC)^{n}\mathrm {res} (P(x),Q(x))}$ ${\displaystyle \mathrm {res} (P,Q)=0\Leftrightarrow \deg \gcd(P,Q)\geqslant 1}$, т.е. результант тогда и только тогда равен нулю, когда НОД многочленов нетривиален. Вообще, вычисление результанта может быть произведено с помощью алгоритма Евклида, и именно так вычисляется результант в различных матпакетах. Для многочленов ${\displaystyle P(x),Q(x)}$ существуют многочлены ${\displaystyle U(x),V(x)}$ с ${\displaystyle \deg {U}\leqslant \deg {P}-1,\deg {V}\leqslant \deg {Q}-1}$ такие, что ${\displaystyle \mathrm {res} (P(x),Q(x))=P(x)V(x)+Q(x)U(x)}$. Многочлены ${\displaystyle U(x),V(x)}$ с ${\displaystyle m=\deg U,n=\deg V}$ могут быть получены из представления результанта определителем в форме Сильвестра, в котором последний столбец заменён на ${\displaystyle (x^{m},...,x,1,0,...,0)^{T}}$ для ${\displaystyle U(x)}$ или на ${\displaystyle (0,...,0,x^{n},...,x,1)^{T}}$ для ${\displaystyle V(x)}$. Для сепарабельного многочлена, в частности, для полей характеристики нуль, результант равен произведению значений одного из многочленов по корням другого, как и раньше, произведение берётся с учётом кратности корней: ${\displaystyle \mathrm {res} (P,Q)=a_{n}^{m}\prod _{P(\alpha )=0}Q(\alpha )=(-1)^{mn}b_{m}^{n}\prod _{Q(\beta )=0}P(\beta )}$ Дискриминант — это, с точностью до знака, результант многочлена и его производной, поделённый на старший коэффициент многочлена; тем самым, дискриминант равен нулю тогда и только тогда, когда у многочлена есть кратные корни. Литература Прасолов В. В. Многочлены. — М.: МЦНМО, 1999, 2001, 2003. Ссылки Статья Weisstein, Eric W. «Resultant» на сайте «MathWorld».