Система линейных уравнений с целыми коэффициентами

VMath

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

Основное

Информация

Действия

Указатель — Разделы — Обозначения — Автор — О проекте

Вспомогательная страница к разделу ☞ МОДУЛЯРНАЯ АРИФМЕТИКА. Плохо обработанные заметки, и не уверен, что скоро вернусь к ним…

Найти двузначные натуральные числа, удовлетворяющие уравнению $ 17\, x+ 20\, y+45\, z =4111 $.

Решение. Выражаем $ x_<> $: $$ x=241-y-2\,z+\frac<14-3\,y-11\,z> <17>\ . $$ Полагаем $$ 17\, t_1 =14-3\,y-11\,z \quad \iff \quad 17\, t_1 + 3\,y+11\,z=14 \ . $$ Выражаем $ y_<> $: $$ y=4-3\,z-5\,t_1+\frac<2-2\,z-2\,t_1> <3>\ . $$ Полагаем $$ 3\, t_2=2-2\,z-2\,t_1 \quad \iff \quad 3\, t_2+2\,z+2\,t_1=2 \ . $$ Выражаем $ z_<> $: $$ z=1-t_1-t_2-\frac <2>\ . $$ Полагаем $$ t_2=2\,t_3 \ . $$ Теперь выражаем неизвестные $ x,y,z_<> $: $$ z=1-t_1-3\,t_3,\ y=1-2\, t_1 +11\, t_3, x=238+5\, t_1- 5\, t_3 \ . $$ При любых значениях параметров $ \ \subset \mathbb Z $ последние формулы дадут решение уравнения. Для того, чтобы удовлетворить дополнительным ограничениям на решения, параметры должны подчиняться условиям: $$ 9 t_3>-18 \ , $$ (здесь мы снова воспользовались целочисленностью параметра). Умножим теперь первое неравенство на $ 2_<> $ и прибавим ко второму: $$-84 ☞ ЗДЕСЬ схеме. Если это уравнение разрешимо в целых числах, то множество его решений записывается в виде соотношений $$ x_1=\beta_<11>t_1+\dots+\beta_<1,n-1>t_ + \gamma_1,\dots x_n=\beta_t_1+\dots+\beta_t_ + \gamma_n, $$ при некоторых фиксированных целочисленных $ \ <\beta_\>, \ <\gamma_j\>$ и произвольном выборе целочисленных параметров $ t_1,\dots,t_ $. Подставляем полученные соотношения в оставшиеся уравнения системы, переписываем их в новую систему — относительно новых неизвестных $ t_1,\dots,t_ $. Число уравнений и число неизвестных уменьшились на единицу. Продолжаем процесс.

Пример. Решить систему линейных уравнений в целых числах $$ \left\< \begin x_1& & — x_3 & +4\,x_4 &=3, \\ 2\,x_1 &- x_2 & & & =3, \\ 3\,x_1 &-2\,x_2 & & -x_4 & =1. \end \right. $$

Решение. Из второго уравнения выражаем $ x_ <2>$: $$x_2=-3+2\, x_1=t_1 \quad \Rightarrow \quad x_1=\frac<3+t_1>2=1+\frac2 \ . $$ Обозначим $$t_2=\frac2 \quad \Rightarrow \quad x_1=1+t_2,\ \quad \Rightarrow \quad x_2=-1+2\,t_2 \ . $$ Подставляем в третье: $$ x_4=4-t_2 \ , $$ теперь все получившиеся выражения для $ x_1,x_2,x_4 $ подставляем в первое уравнение: $$ x_3=14-3\,t_2 \ . $$

Ответ. $ x_1 = 1+t_2,\ x_2 =-1+2\,t_2,\ x_3=14-3\,t_2,\ x_4=4-t_2 $ при $ t_2 \in \mathbb Z $.

Решим теперь более сложный пример.

Пример. Решить систему линейных уравнений в целых числах $$ \left\< \begin 5\,x_1& + 7\, x_2 & +8\,x_3 &=11, \\ 2\,x_1 &- 3\,x_2 & +6\,x_3 & =5. \end \right. $$

Решение. Имеем из первого уравнения: $$ x_1=\frac<11-7\,x_2-8\,x_3><5>=2-x_2-x_3+\frac<1-2\,x_2-3\,x_3> <5>\quad \Rightarrow \quad t_1=\frac<1-2\,x_2-3\,x_3> <5>\ . $$ Далее, $$ 2\,x_2+3\,x_3+5\,t_1=1 \quad \Rightarrow \quad x_2=\frac<1-3\,x_3-5\,t_1><2>=-x_3-2\,t_1+ \frac<1-x_3-t_1> <2>\quad \Rightarrow \quad t_2=\frac<1-x_3-t_1> <2>\ . $$ Получаем выражение для $ x_ <3>$: $$ x_3=1-t_1-2\,t_2 \ , $$ подставляем его в выражение для $ x_ <2>$: $$ x_2=-x_3-2\,t_1+t_2=-t_1=3\,t_2-1 \ . $$ Теперь $$ x_1=2-x_2-x_3+t_1=2+3\,t_1-t_2 \ . $$ Все три получившиеся формулы подставляем во второе уравнение системы: $$ 3\,t_1-23\,t_2=-8 \ . $$ Решаем это уравнение в той же технике, получаем: $$t_1=23\,u_2+5,\ t_2=3\, u_2+1 \ . $$ И возвращаемся к выражениям для $ x_1,x_2,x_3 $.

Ответ. $ x_1=16+66\, u_2,\ x_2=-3-14\, u_2,\ x_3=-6-29\, u_2 $ при $ u_2 \in \mathbb Z $.

Если бы мы решали предыдущую систему в рациональных или вещественных числах, то получили бы аналогичный вид решения: $$ x_1=x_<10>+66\, t,\ x_2=x_<20>-14\, t,\ x_3=x_<30>-29\, t \quad npu \quad t \in \mathbb R \ . $$ Можно проверить, что сомножители при $ t_<> $ — это величины миноров системы уравнений, т.е. $$ \left| \begin a_ <12>& a_ <13>\\ a_ <22>& a_ <23>\end \right| , \quad -\left| \begin a_ <11>& a_ <13>\\ a_ <21>& a_ <23>\end \right| , \quad \left| \begin a_ <11>& a_ <12>\\ a_ <21>& a_ <22>\end \right| $$ соответственно. См. упражнение ☞ ЗДЕСЬ. Геометрически: направляющий вектор прямой, соответствующей пересечению двух плоскостей, всегда можно выбрать целочисленным. Таким образом, если система имеет целочисленное решение, то вхождения параметра в формулы, описывающие все множество этих решений, можно оценить с помощью методов линейной алгебры (см. теорию ☞ ЗДЕСЬ ). Проблема заключается в поиске хотя бы одного частного целочисленного решения $ x_<10>,x_<20>,x_ <30>$. Вот оно может и не существовать. К примеру, система $$ \left\< \begin 2\,x_1& + x_2 & -x_3 &=1, \\ x_1 &+ 2\,x_2 & + x_3 & =1 \end \right. $$ не имеет решений в $ \mathbb Z_<> $.

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

Теорема [Минковский]. Рассмотрим систему вещественных линейных неравенств относительно неизвестных $ x_<1>,\dots,x_n $ $$ \left\< \begin a_<11>x_1 &+a_<12>x_2&+ \ldots&+a_<1n>x_n &\le b_1,\\ a_<21>x_1 &+a_<22>x_2&+ \ldots&+a_<2n>x_n &\le b_2,\\ \dots & & & \dots & \\ a_x_1 &+a_x_2&+ \ldots&+a_x_n & \le b_n. \end \right. $$ при $ b_1>0,b_2>0,\dots,b_n>0 $. Пусть определитель коэффициентов левых ее частей отличен от нуля: $$ \det [a_]_^n \ne 0 \ . $$ Тогда система имеет целочисленное решение если произведение правых ее частей не меньше абсолютной величины этого определителя: $$ \prod_^n b_j \ge \left| \det [a_]_^n \right| \ . $$

Решение систем линейных уравнений

Эта страничка поможет решить Системы Линейных Алгебраических Уравнений (СЛАУ) методом Гаусса, матричным методом или методом Крамера, исследовать их на совместность (теорема Кронекера-Капелли), определить количество решений, найти общее, частное и базисные решения.

Введите коэффициенты при неизвестных в поля. Если Ваше уравнение имеет меньшее количество неизвестных, то оставьте пустыми поля при переменных, не входящих в ваше уравнение. Можно использовать дроби ( 13/31 ).

Метод Гаусса онлайн

Данный онлайн калькулятор находит решение системы линейных уравнений (СЛУ) методом Гаусса. Дается подробное решение. Для вычисления выбирайте количество переменных и количество уравнений. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить.»

Предупреждение

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Метод Гаусса

Метод Гаусса − это метод перехода от исходной системы линейных уравнений (при помощи эквивалентных преобразований) к системе, которая решается проще, чем исходная система.

Эквивалентными преобразованиями системы линейных уравнений являются:

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

Рассмотрим систему линейных уравнений:

(1)

Запишем систему (1) в матричном виде:

Ax=b

(2)

(3)

A-называется матрица коэффициентов системы, b − правая часть ограничений, x− вектор переменных, которую нужно найти. Пусть rang(A)=p.

Эквивалентные преобразования не меняют ранг матрицы коэффициентов и ранг расширеннной матрицы системы. Не меняется также множество решений системы при эквивалентных преобразованиях. Суть метода Гаусса заключается в приведении матрцы коэффициентов A к диагональному или ступенчатому.

Построим расшренную матрицу системы:

(4)

Предположим a₁₁≠0. Если это не так, то можно поменять местами эту строку со строкой с ненулевым элементом в столбце 1 (если нет таких строк, то переходим к следующему столбцу). Обнуляем все элементы столбца 1 ниже ведущего элемента a₁₁. Для этого сложим строки 2,3, . m со строкой 1, умноженной на −a₂₁/a₁₁, −a₃₁/a₁₁, . −a_m1/a₁₁, соответственно. Тогда (4) примет следующий вид:

(5)

На следующем этапе обнуляем все элементы столбца 2, ниже элемента . Если данный элемент нулевой, то эту строку меняем местами со строкой, лежащий ниже данной строки и имеющий ненулевой элемент во втором столбце. Далее обнуляем все элементы столбца 2 ниже ведущего элемента a₂₂. Для этого сложим строки 3, . m со строкой 2, умноженной на −a₃₂/a₂₂, . −a_m2/a₂₂, соответственно. Продолжая процедуру, получим матрицу диагонального или ступенчатого вида. Пусть полученная расширенная матрица имеет вид:

(6)

Обратим внимание на последние строки. Если . равны нулю, то система линейных уравнений имеет решение, если же хотя бы один из этих чисел отлично от нуля, то система несовместна. Иными словами, система (2) совместна тогда и только тогда, когда ранг матрицы A навен рангу расширенной матрицы (A|b).

Пусть . Тогда

(7)

Так как rangA=rang(A|b), то множество решений (7) есть (n−p)− многообразие. Следовательно n−p неизвестных можно выбрать произвольно. Остальные неизвестные из системы (7) вычисляются так. Из последнего уравнения выражаем x_p через остальные переменные и вставляем в предыдущие выражения. Далее из предпоследнего уравнения выражаем x_p−1 через остальные переменные и вставляем в предыдущие выражения и т.д. Рассмотрим метод Гаусса на конкретных примерах.