Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2.5. Решение систем линейных уравненийВ последних главах мы видели, что некоторые задачи, возникающие в теории кодирования, могут быть сведены к решению систем линейных уравнений. Часто эти системы рассматриваются над двоичным полем. Однако в некоторых случаях приходится рассматривать другие поля, как, например,
Рассматриваемые системы линейных уравнений могут быть записаны в виде
где
Уравнение С помощью подходящих операций над столбцами матрица X может быть приведена к одной из известных канонических форм. Для наших целей наиболее подходящей является приведенная треугольная идемпотентная форма, обозначаемая через 2.51. Определение, Следующая матрица является примером треугольной идемпотентной матрицы над
В символической записи это означает, что
2.52. Теорема. Всякая квадратная матрица в приведенной треугольной идемпотентной форме удовлетворяет уравнению Доказательство. Элемент Следовательно,
Если
Это эквивалентно матричному уравнению Из этого результата следует простая характеристика вектор-строк 2.53. Теорема. Если X — приведенная треугольная идемпотентная матрица, то Доказательство. Если линейная комбинация строк матрицы X, то Так как только ненулевые столбцы матрицы Произведение каждой координаты вектора Наконец, докажем теорему 2.54. 2.54. Теорема. Любая квадратная матрица с помощью операций над столбцами может быть приведена к треугольной идемпотентной форме. Хотя существует несколько способов такого приведения, мы остановимся не на самом простом, а на наиболее просто реализуемом.
Рис. 2.20. Циклический сдвиг столбцов влево.
Рис. 2.21. Циклический сдвиг строк вверх. Так как допустима перемена мест для любой пары столбцов, то столбцы можно переставлять в любом необходимом порядке. Соответственно определим операцию «циклического сдвига столбцов влево» с помощью диаграммы, приведенной на рис. 2.20. Аналогично с помощью диаграммы на рис. 2.21 определим операцию «циклического сдвига строк вверх». Бдительный читатель в этом месте должен насторожиться: допустимой является операция перестановки столбцов, а не строк. Однако рассматриваемая процедура использует операцию сдвига строк траз, так что в итоге строки располагаются в первоначальном порядке. А так как операция сдвига строк перестановочна со всеми операциями над столбцами, то 2.55. Алгоритм приведения матрицы (к треугольной идемпотентной форме). Процедура состоит из следующего базисного множества шагов, повторяющегося 1. Не делать ничего, если верхний член первого столбца матрицы отличен от нуля. Если верхний член первого столбца равен нулю, то поменять местами первый столбец с самым левым столбцом, в котором верхний элемент отличен от нуля, а элемент главной диагонали равен нулю. Если такого столбца нет, то поменять местами первый столбец с самым левым столбцом, в котором верхний элемент и элемент главной диагонали отличны от нуля. Если и такого столбца нет (в этом случае верхняя строка является нулевой), то не делать ничего. 2. Разделить все члены первого стобца на верхний элемент. (Если этот элемент равен нулю, не делать ничего.) 3. Аннулировать верхние элементы всех столбцов, кроме первого, с помощью вычитания подходящего кратного первого столбца. 4. Сдвинуть циклически строки вверх, а столбцы влево. В двоичном случае шаг 2 можно опустить. Каждый из остальных шагов выполняется в один временной цикл. Блок-схема для выполнения операции 1 объяснена на рис. 2.22 и 2.23, а для операции 3 — на рис. 2.24. В общем случае после имеет вид
Рис. 2.22. Подробная блок-схема одной ячейки из рис. 2.23. Вход Если любой из сигналов А или В изменяет свое значение с 0 на 1, то в точках Связи между столбцами показаны на рис. 2.23. Заметим, что распространение сигнала вдоль линий Реализация перестановки столбцов требует многих элементов, не показанных на схеме. Ее можно осуществить хотя и громоздким, но прямым способом, использующим сигналы (кликните для просмотра скана) Проведем теперь следующий цикл основных преобразований. Во-первых, переставим первый и пятый столбцы:
Во-вторых, пронормируем первый столбец:
В-третьих, вычтем соответствующее кратное первого столбца из остальных столбцов:
Наконец, сдвинем строки вверх, а столбцы влево:
В рассмотренном примере первые три шага процедуры не затронули к нижних строк. В общем случае это не так. Проиллюстрируем это другим примером. Начнем с матрицы
Переставим первый и шестой столбцы и пронормируем затем первый столбец:
Прибавляя затем первый столбец к седьмому и сдвигая строки и столбцы получаем
Таким образом, любая квадратная матрица может быть приведена к треугольной идемпотентной форме с помощью подходящих операций над столбцами, которые можно легко реализовать. Для двоичных Во многих интересных случаях приходится рассматривать систему
или
Применяя соответствующие операции над столбцами, приведем расширенную матрицу к треугольному идемпотентному виду. Каждая операция над столбцами матрицы X затрагивает, конечно, и присоединенную строку. (При использовании описанной выше процедуры приведения циклический сдвиг строк относится лишь только к строкам матрицы Если строка
Это уравнение противоречиво. Ясно, что в этом случае исходная система уравнений Однако, если приведенная присоединенная строка 2.56. Теорема. Пусть X — некоторая 1) С помощью подходящих операций над столбцами расширенной матрицы X приводим ее к треугольному идемпотентному виду 2) Образуем матрицу 3) Каждую координату 2.57. Пример. Рассмотрим систему пяти двоичных уравнений с пятью неизвестными
Расширенная матрица равна
Для приведения этой матрицы к треугольной идемпотентной форме прибавим третий столбец ко всем остальным столбцам, а затем пятый столбец к третьему:
Интересно проиллюстрировать такой способ приведения с помощью схем, изображенных на рис. 2.22-2.24. Проведем более детальное вычисление: (см. скан)
Ясно, что одним решением этой системы является 00101, а остальные семь решений получаются путем прибавления к нему любой линейной комбинации строк
|
1 |
Оглавление
|