Инструменты сайта


Теория исключения

§

Для понимания материалов этого раздела желательно просмотреть разделы ПОЛИНОМ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ и РЕЗУЛЬТАНТ.

Страница — в разработке; начало работ — 20.08.2018, окончание — ??.??.????

Постановка задачи

Теория исключения1): так называется раздел классической высшей алгебры, посвященный решению систем уравнений $$ f_1(x_1,\dots,x_n)=0,\dots, f_n(x_1,\dots,x_n)=0 \ , $$ где $ f_1,\dots,f_n $ — полиномы по $ x_1,\dots,x_n $. Основной целью теории исключения ставится сведение задачи решения этой системы к одномерному случаю. Именно, с помощью элементарных преобразований систему как правило удается свести к эквивалентной ей (т.е. имеющей тот же набор решений) системе вида $$ {\mathcal X}(x_1)=0,\, x_2-\theta_2 (x_1)=0, \dots, x_n-\theta_n (x_1)=0 \ . $$ Здесь $ {\mathcal X}(x_1) $ — полином, а $ \theta_2 (x_1),\dots,\theta_n (x_1) $ — рациональные функции по $ x_1 $. Следовательно, в этом случае решение исходной системы сведется к решению уравнения от одной переменной; иными словами, все остальные переменные оказываются исключенными. Каждый корень полинома $ {\mathcal X}(x_1) $ задает первую компоненту (координату) решения системы, а соответствующие ему остальные компоненты выражаются рационально через первую с помощью оставшихся уравнений эквивалентной системы.

Система двух уравнений

Система трех уравнений

П

Пример. Найти значения коэффициентов $ \{{\color{RubineRed} c }_{jk} \} $, при которых система

$$\left\{\begin{array}{l} f_1(x,y)=4\,x^2-7\,xy+y^2+13\,x-2\,y-3=0 \ ,\\ f_2(x,y)=9\,x^2-14\,xy+y^2+28\,x-4\,y-5=0 \ , \\ g(x,y)={\color{Red} c }_{11}xy+{\color{Red} c }_{10}x+{\color{Red} c }_{01}y+{\color{Red} c }_{00} \end{array}\right. $$ имеет решение.

Решение. Из двух первых уравнений можно выразить мономы $ x^2 $ и $ y^2 $ линейно через оставшиеся $ 1,x,y,xy $ (фактически решив эти уравнения как линейные относительно $ x^2, y^2 $) $$ \left\{\begin{array}{l} x^2=\frac{7}{5}xy-3x+\frac{2}{5}y+\frac{2}{5}\, ,\\ y^2=\frac{7}{5}xy-x+\frac{2}{5}y+\frac{7}{5}\, . \end{array}\right. $$ Умножим первое их получившихся соотношений на $ y $, второе — на $ x $: $$ \left\{\begin{array}{l} x^2y=\frac{7}{5}xy^2-3xy+\frac{2}{5}y^2+\frac{2}{5}y\, ,\\ xy^2=\frac{7}{5}x^2y-x^2+\frac{2}{5}xy+\frac{7}{5}x, \end{array}\right. $$ подставим сюда выражения для $ x^2 $ и $ y^2 $ из исходных же соотношений: $$ \left\{\begin{array}{l} -x^2y+\frac{7}{5}xy^2-\frac{61}{25}xy-\frac{2}{5}x+\frac{14}{25}y+\frac{14}{25}=0\, , \\ \frac{7}{5}x^2y-xy^2-xy+\frac{22}{5}x-\frac{2}{5}y-\frac{2}{5}=0 \end{array}\right. $$ Теперь разрешим эти уравнения — как линейные — относительно мономов $ x^2y $ и $ xy^2 $: $$ \left\{\begin{array}{l} x^2y = 4\,xy-6\,x \, , \\ xy^2=\frac{23}{5}xy-4x-\frac{2}{5}y-\frac{2}{5} \, . \end{array}\right. $$ Домножим первое соотношение на $ y $ и подставим в полученное равенство выражение для $ xy^2 $ из второй формулы: $$ x^2y^2 =\frac{62}{5}xy-16\,x-\frac{8}{5}y-\frac{8}{5} \, . $$ Итак, действуя только с двумя первыми уравнениями, мы получили формулы, линейно выражающие мономы высших степеней $ x^2,y^2,x^2y,xy^2, x^2y^2 $ через мономы $ 1,x,y,xy $.

Теперь подключаем третье уравнение системы. Дожножим $ g(x,y)=0 $ на $ x $ и в получившемся уравнении выполним подстановки вместо $ x^2y $ и $ x^2 $: $$ \left(4\,c_{11}+\frac{7}{5}c_{10}+c_{01}\right)xy+(-6\,c_{11}-3\,c_{10}x+c_{00})x+\frac{2}{5}c_{10}y+\frac{2}{5}c_{10}=0 \, . $$ Аналогично, дожножим $ g(x,y)=0 $ на $ y $ и в получившемся уравнении выполним подстановки вместо $ xy^2 $ и $ y^2 $: $$ \left(\frac{23}{5}c_{11}+\frac{7}{5}c_{01}+c_{10} \right)xy+(-4\,c_{11}-c_{01})x+\left(\frac{2}{5}c_{01}-\frac{2}{5}c_{11} +c_{00}\right)y-\frac{2}{5}c_{11}+\frac{7}{5}c_{01}=0 \, . $$ Наконец, домножим $ g(x,y)=0 $ на $ xy $ и в получившемся уравнении выполним подстановки вместо $ x^2y^2, x^2y $ и $ xy^2 $: $$ \left(\frac{62}{5}c_{11}+\frac{23}{5}c_{01}+4\,c_{10}+c_{00} \right)xy+ $$ $$ +(-16\,c_{11}-4\,c_{01}-6c_{10})x+\left(-\frac{2}{5}c_{01}y-\frac{8}{5}c_{11} \right)y-\frac{8}{5}c_{11}-\frac{2}{5}c_{01}=0 \, . $$ Получили $ 4 $ соотношения эквивалентные соотношениям $$ g(x,y)=0,\ xg(x,y)=0, yg(x,y)=0,\ xyg(x,y)=0 \, , $$ которые должны быть выполнены на любом решении системы уравнений $ f_1(x,y)=0,\ f_2(x,y)=0 $. Но эти $ 4 $ уравения можно рассматривать как линейные относительно мономов $ xy, x, y, 1 $. Однородная система линейных уравнений имеет нетривиальное решение тогда и только тогда, когда ее определитель $$ \left|\begin{array}{cccc} c_{11} & c_{10} & c_{01} & c_{00} \\ 4\,c_{11}+\frac{7}{5}c_{10}+c_{01} & -6\,c_{11}-3\,c_{10}x+c_{00} & \frac{2}{5}c_{10} & \frac{2}{5}c_{10} \\ \frac{23}{5}c_{11}+\frac{7}{5}c_{01}+c_{10} & -4\,c_{11}-c_{01} & \frac{2}{5}c_{01}-\frac{2}{5}c_{11} +c_{00} & -\frac{2}{5}c_{11}+\frac{7}{5}c_{01} \\ \frac{62}{5}c_{11}+\frac{23}{5}c_{01}+4\,c_{10}+c_{00} & -16c_{11}-4c_{01}-6c_{10} & -\frac{2}{5}c_{01}-\frac{8}{5}c_{11} & -\frac{8}{5}c_{11}-\frac{2}{5}c_{01} \end{array} \right| $$ равен нулю. Этот определитель является полиномом относительно $ c_{11},c_{10},c_{01},c_{00} $, который факторизуется в произведение линейных множителей: $$ (c_{01}-c_{00})(2\,c_{01}+c_{00}+c_{10}+2\,c_{11})(3\,c_{01}+c_{00}+2\,c_{10}+6\,c_{11})(c_{01}+c_{00}-2\,c_{10}-2c_{11}) \, . $$ Для того, чтобы исходная система была совместной необходимо, чтобы хотя бы один из этих линейных сомножителей обращался в нуль.

Проверка. Система уравений $ f_1(x,y)=0 $ и $ f_2(x,y)=0 $ имеет $ 4 $ решения: $ (0,-1); (1,2) ; (2,3) ; (-2,1) $. Легко проверить, что полученное выражение для определителя представляет собой произведение $$ -g(0,-1)g(1,2)g(2,3)g(-2,1) \, .$$

Очевидно, что предложенный в решении примера алгоритм будет работать и для случая произвольных квадратичных полиномов $ f_1 $ и $ f_2 $ — если только решаемая на каждом шаге система линейных уравнений будет однозначно разрешимой. Понятно, что, как правило, эти системы будут разрешимы, поскольку вероятность того, что соответствующие определители обратятся в нуль при случайном выборе коэффициентов полиномов — нулевая. Также очевидна возможность обобщения алгоритма на случай произвольного квадратичного полинома $ g(x,y) $ с ненулевыми коэффициентами при $ x^2 $ и $ y^2 $: после того как эти мономы выражены линейно через $ xy, x, y, 1 $, производится подстановка в $ g(x,y) $; задача тем самым сводится к уже решенной.

Резюмируя, можно сформулировать гипотезу о существовании некоторой полиномиальной функции коэффициентов полиномов $ f_1(x,y), f_2(x,y) $ и $ g(x,y) $, обращение которой в нуль дает необходимое условие существования решения системы уравнений $$ f_1(x,y)=0, f_2(x,y)=0, g(x,y)=0 \, . $$ Иными словами, мы получаем аналог результанта двух полиномов от одной переменной.

Симметрические полиномы от решений системы уравнений

Функция $$\Phi(x_1,y_1;x_2,y_2;\dots;x_{\ell},y_{\ell}) $$ называется симметрической функцией $ \ell $ пар переменных $ (x_1,y_1), (x_2,y_2),\dots,(x_{\ell},y_{\ell}) $ если ее значение не меняется при произвольной их перестановке: $$\Phi(x_1,y_1;x_2,y_2;\dots;x_{\ell},y_{\ell}) \equiv \Phi(x_{j_1},y_{j_1};x_{j_2},y_{j_2};\dots;x_{j_{\ell}},y_{j_{\ell}}) $$ для различных $ j_1,\dots,j_{\ell} $.

Рассмотрим систему алгебраических уравнений $$ f_1(x,y)=0, \ f_2(x,y)=0 $$ и разложим полиномы из их левых частей в ряды по убывающим степеням $x$ и $y$: $$f_j(x,y)=f_{j,n_j}(x,y)+f_{j,n_j-1}(x,y)+\dots+f_{j,0},$$ здесь $f_{j,k}(x,y)$ означает форму (однородный полином) $k$-й степени. Относительно старших форм $$ f_{j,n_j}(x,y):=a_{j,0}x^{n_j}+a_{j,1}x^{n_j-1}y+\dots+a_{j,n_j}y^{n_j} $$ сделаем следующие предположения.

Предположение 1 . Пусть $a_{j,0}\ne 0, a_{j,n_j}\ne 0$ для $j\in\{1,2\}$. Иными словами $$ \deg_x f_j = \deg_y f_j = n_j \ \mbox{ при } j\in \{1,2\} \, . $$

Предположение 2 . Пусть число решений системы уравнений $ f_1=0, f_2=0 $ определяется теоремой Безу: $$ N:=n_1n_2 \ . $$

В соответствии с доказательством теоремы Безу, это предположение выполняется тогда и только тогда, когда результант $$ \mathcal A_0:=\mathcal R(f_{1,n_1}(x,1),f_{2,n_2}(x,1)) $$ отличен от нуля.

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

Т

Теорема [Шлэфли]. При выполнении предположений 1 и 2 значение любого симметрического полинома от $ N $ наборов переменных на решениях $ \{(\alpha_j,\beta_j)\}_{j=1}^N $ системы $ f_1=0, f_2=0 $ является рациональной функцией коэффициентов полиномов $ f_1 $ и $ f_2 $.

Примером симметрических полиномов на решениях системы уравнений являются обобщенные суммы Ньютона $$ s_{k\ell}=\sum_{j=1}^N \alpha_j^k \beta_j^{\ell} , \ \{k,\ell\} \subset \{0,1,2,\dots \} \, . $$ Справедливость теоремы Шлэфли для этих сумм в случае $ k=0 $ или $ \ell=0 $ проверяется несложными рассуждениями. Действительно, $ \{ \alpha_j\}_{j=1}^N $ являются корнями элиминанты $$ \mathcal X(x):=\mathcal R_y(f_1(x,y),f_2(x,y)) \, , $$ коэффициенты которой полиномиально выражаются через коэффициенты полиномов $ f_1 $ и $ f_2 $. Выражение $$ s_{k0}= \sum_{j=1}^N \alpha_j^k $$ является суммой Ньютона полинома $ \mathcal X(x) $. Она выражается через коэффициенты этого полинома рациональным образом — по формулам Ньютона или Варинга.

Для вычисления $ s_{k\ell} $ в общем случае $ k \ne 0, \ell \ne 0 $ имеются два подхода:

  • и метод Пуассона.

Пусть теперь $ g(x,y) $ — произвольный полином; $ \deg g=m\ge 1$. На основании теоремы Шлэфли, произведение $$ \prod_{j=1}^N g(\alpha_j, \beta_j ) $$ может быть рационально выражено через коэффициенты полиномов $f_1$ и $f_2$ (а также, очевидно, через коэффициенты полинома $ g $). Далее, можно доказать, что выражение $$ \mathcal R(f_1,f_2,g):=\mathcal A_0^m\, \prod_{j=1}^N g(\alpha_j, \beta_j ) $$ будет полиномом с целыми коэффициентами относительно коэффициентов полиномов $f_1(x,y),f_2(x,y)$ и $g(x,y)$; он называется результантом этих полиномов.

Т

Теорема. При выполнении предположений 1 и 2 условие обращения результанта $ \mathcal R(f_1,f_2,g) $ в нуль является необходимым и достаточным для существования решения системы уравнений

$$ f_1(x,y)=0,f_2(x,y)=0, g(x,y)=0 \, . $$

Можно установить ряд свойств результанта полиномов от двух переменных, аналогичных свойствам результанта полиномов от одной переменной. В частности, значение $ \mathcal R(f_1,f_2,g) $ инвариантно — с точностью до знака — относительно перестановки его аргументов, т.е. полиномов $ f_1,f_2,g $.

.

Источники

Netto E. Vorlesungen über Algebra. Teubner, Leipzig, Bd.1.1896, Bd.2.1900

Bikker P.,Uteshev A.Yu. On the Bézout Construction of the Resultant. J.Symbolic Computation, 1999, Vol.28, № 1. P.45-88. Текст ЗДЕСЬ (pdf)

Schläfli L. Über die Resultante eines Systemes mehrerer algebraischer Gleichungen. Gesammelte Math. Abhandlungen. 1953. 2:9–112, Basel, Birkhäuser

1)
(англ.) Elimination Theory
elimination_theory.txt · Последние изменения: 2021/02/12 18:21 — au