2.6. Специальныё метод решения систем уравнениё, матрицы которых состоят почти сплошь из нулей

Если большинство из элементов -матрицы X равно нулю, то для решения уравнения более целесообразно использовать специальные прямые методы. В качестве примера рассмотрим систему 10 двоичных уравнений с 10 неизвестными:

Ненулевые элементы каждого столбца матрицы X выделяют подмножество координат вектора сумма которых должна равняться

нулю. В данном случае этими координатами являются

Рассмотрим сначала уравнения, содержащие не более двух неизвестных. Например, согласно уравнению с номером так что Будем теперь координаты с большими значениями индексов заменять их выражением через координаты с меньшими значениями индексов и исключать координаты с большими значениями индексов из всех остальных уравнений. В данном случае, начиная с подстановки индекса 8 вместо индекса 9, получаем

Отметка кружком координаты 9 в уравнении 3 указывает на то, что неизвестное определяется теперь именно этим уравнением.

Продолжая этот процесс, находим следующее уравнение, содержащее только два неизвестных, а именно уравнение с номером Соответственно отмечаем в уравнении 7 координату 7 кружком и подставляем 2 вместо 7 в уравнения 1, 5 и 8. При этом в уравнении 5 координата 2 взаимно уничтожается с ранее уже имевшейся координатой 2.

Следующим уравнением, содержащим только две координаты, является уравнение 9. Отметим в нем кружком координату 5 и заменим ее координатой 0 во всех остальных уравнениях.

Рассмотрим теперь систему сначала, отыскивая уравнения, связывающие не более двух переменных и не содержащие отмеченных кружком неизвестных. Единственным таким уравнением является пятое уравнение, содержащее только координату 0. Отметим ее кружком и вычеркнем из всех остальных уравнений.

Еще раз просмотрим систему и отметим кружками (с соответствующими заменами) координату 8 в уравнении номер 0 и координату 3 в уравнении номер 4.

Теперь мы пришли к системе только из трех уравнений: Уравнение 1: ,

Уравнение 6:

Уравнение 8:

Каждое из этих уравнений содержит три неизвестных, и так как каждая пара уравнений содержит только два общих неизвестных, то дальнейшее уменьшение числа переменных можно осуществлять разными способами. Одним из возможных путей является определение из уравнения 1 в виде и подстановка этого выражения в уравнение 8:

Тогда будет определяться уравнением уравнением 6:

На этом приведение матрицы заканчивается. Каждое за исключением определяется через координаты с меньшими индексами. Значение может быть, очевидно, произвольным. Если выбрать то получим тривиальное решение Выбор приводит к нетривиальному решению. Из уравнения 5 определяем, что Решение получается из уравнения 6. В силу уравнения 4 выполняется равенство и так как то и Аналогичным образом находятся и все остальные координаты к,

Можно проверить, что действительно является решением рассматриваемой системы.

После небольшой практики читатель сможет быстро решать примеры следующего типа.

2.61. Пример. Решить уравнение где

Решение

Если . В любом случае произвольно.

Если очень велико, то оказывается целесообразным составлять дополнительные таблицы с перечислением номеров уравнений, в которые входит каждое данное неизвестное. Это значительно ускоряет операцию подстановки вместо так как для поиска уравнений, содержащих не надо просматривать всю систему, а достаточно просмотреть дополнительную таблицу.

Задачи

(см. скан)

(см. скан)