==Теория исключения==
!!§!! Для понимания материалов этого раздела желательно просмотреть разделы
☞
((:polynomialm ПОЛИНОМ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ)) и
☞
((:dets:resultant РЕЗУЛЬТАНТ)).
!!⊗!! Страница --- в разработке; начало работ --- 20.08.2018, окончание --- ??.??.????
==Постановка задачи==
**Теория исключения**[[(//англ.//) Elimination Theory]]: так называется раздел классической высшей алгебры, посвященный решению систем уравнений
$$
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 $ ((:dets:resultant#исключение_переменных_в_системе_полиномиальных_уравнений имеет)) $ 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 \, . $$
Иными словами, мы получаем аналог ((:dets:resultant#результант_в_форме_сильвестра результанта двух полиномов от одной переменной)).
==Симметрические полиномы от решений системы уравнений==
Функция
$$\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 $ определяется ((:dets:resultant#teorema_bezu теоремой Безу)):
$$ N:=n_1n_2 \ . $$
В соответствии с доказательством теоремы Безу, это предположение выполняется тогда и только тогда, когда результант
$$
\mathcal A_0:=\mathcal R(f_{1,n_1}(x,1),f_{2,n_2}(x,1))
$$
отличен от нуля.
Следующая теорема представляет собой аналог ((:polynomial#simmetricheskie_funkcii_kornej теоремы Гаусса)) для значений симметрических функций на корнях полинома одной переменной.
!!Т!! **Теорема [Шлэфли].** //При выполнении//
предположений 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
$$
является ((:dets:discrim:waring#summy_njutona суммой Ньютона)) полинома $ \mathcal X(x) $. Она выражается через коэффициенты этого полинома рациональным образом --- ((:dets:discrim:waring#summy_njutona по формулам Ньютона)) или
((:dets:discrim:waring#formula_varinga Варинга)).
Для вычисления $ s_{k\ell} $ в общем случае $ k \ne 0, \ell \ne 0 $ имеются два подхода:
* изящный
☞
((:elimination_theory:symm_fun_jacobi способ, разработанный К.Якоби));
* и метод Пуассона.
Пусть теперь $ 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 \, . $$
Можно установить ряд свойств результанта полиномов от двух переменных, аналогичных ((:dets:resultant#svojstva свойствам результанта)) полиномов от одной переменной. В частности, значение $ \mathcal R(f_1,f_2,g) $ инвариантно --- с точностью до знака --- относительно перестановки его аргументов, т.е. полиномов $ f_1,f_2,g $.
==Решение системы трех уравнений с тремя неизвестными==
!!П!! **Пример.** Решить систему уравнений
$$
\left\{
\begin{array}{lll}
f_1 &=& x^2+xy+y^2-2xz-4yz+3z^2+x+2y-z-2 =0, \\
f_2 &=& 2x^2-xy+y^2-xz-yz-6z^2+2x-y+z+2=0, \\
g &=& x^2-2xy-y^2-2xz+2yz+3z^2+2x+3y-3z-1=0.
\end{array}
\right.
$$
**Решение.** Исключаем переменные $ x $ и $ y $. Для этого решаем сначала систему уравнений $ f_1=0,f_2=0 $ как линейную относительно $ x^2 $ и $ y^2 $:
$$
\left\{
\begin{array}{llll}
x^2 &=& 2 x y+(-z-1) x+(-3z+3) y+(9 z^2-2z-4), & {\color{Red}{ (1)} } \\
y^2 &=& -3 x y+3 z x+(7z-5) y+(-12 z^2+3z+6) & {\color{Red}{ (2)} } .
\end{array}
\right.
$$
Теперь умножим первое из полученных уравнений на $ y $, второе --- на $ x $, и полученные уравнения снова рассматриваем как линейные относительно $ x^2y $ и $ xy^2 $. Решаем эту систему относительно этих "переменных", а в полученном решении заменяем $ x^2 $ и $ y^2 $ выражениями из системы $ {\color{Red}{ (1)} } - {\color{Red}{ (2)} }$:
$$
\left\{
\begin{array}{llll}
x^2y &=& \frac{1}{7} \left\{(34z-20) x y+(-39z^2+9z+12)x+
(-30z^2+52z-19)y + \right. & \\
& & \quad \left. +(90z^3-57z^2-33z+18)\right\}, & {\color{Red}{ (3)} } \\
xy^2 &=& \frac{1}{7}\left\{(-11z+25)xy+(12z^2-27z+6)x+
(27z^2-93z+57)y + \right. & \\
& & \quad \left. +(-81z^3+129z^2+15z-54)\right\}. & {\color{Red}{ (4)} }
\end{array} \right.
$$
((:elimination_theory:exampleBU .))
==Источники==
**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. Текст
☞
((https://www.sciencedirect.com/science/article/pii/S0747717199902675 ЗДЕСЬ)) (pdf)
**Schläfli L.**
//Über die Resultante eines Systemes mehrerer algebraischer Gleichungen.//
Gesammelte Math. Abhandlungen. 1953. 2:9--112, Basel, Birkhäuser