Преобразование матрицы к блочно-диагональному виду

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

Преобразование матрицы к блочно-диагональному виду

Сообщение Naeel Maqsudov » 29 ноя 2008, 22:41

Нужен алгоритм преобразования разреженной (относительно много нулей) матрицы к блочно-диагональному виду, чтобы все ненулевые элементы "прилипли" к главной диагонали, а нули вытеснились соответственно в 2 угла.
Преобразование должно выполняться перестрановками строк и столбцов, и линейными преобразованиями строк. (Т.е. можно умножить строку на коэффициент и сложить с другой строкой)
Наверняка есть уже готовый велосипед!

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 16:14
Откуда: 71 RUS
Контактная информация:

Re: Преобразование матрицы к блочно-диагональному виду

Сообщение somewhere » 01 дек 2008, 09:17

Могу помочь с алгоритмом приведения к треугольному виду, собственно манипуляции те же самые
It's a long way to the top if you wanna rock'n'roll

МарияБорисовна
Сообщения: 1
Зарегистрирован: 19 сен 2013, 22:35

Re: Преобразование матрицы к блочно-диагональному виду

Сообщение МарияБорисовна » 19 сен 2013, 22:38

Naeel Maqsudov писал(а):Нужен алгоритм преобразования разреженной (относительно много нулей) матрицы к блочно-диагональному виду, чтобы все ненулевые элементы "прилипли" к главной диагонали, а нули вытеснились соответственно в 2 угла.
Преобразование должно выполняться перестрановками строк и столбцов, и линейными преобразованиями строк. (Т.е. можно умножить строку на коэффициент и сложить с другой строкой)
Наверняка есть уже готовый велосипед!
1) Начнем с первой строки искать первый ненулевой элемент и обозначим эту сточку (1). После того, как нашелся первый ненулевой элемент, столбец, в котором он находится тоже обозначим (1) и уже в нем ищем ненулевые элементы.
Если такой есть, то строчку в которой он находится(этот ненулевой элемент) так же обозначаем (1). Затем дальше просматриваем исходную строчку и повторяем такие действия до ее конца.

2) Затем смотрим, есть ли у нас строчки, которые мы еще не рассмотрели. Если такие есть, то наивысшую из них обозначаем за (2) и повторяем алгоритм, описанный выше.
Все это следует повторять, пока не будут просмотрены все строки и столбцы.
3) Итак, все строки обозначены. Теперь переставляем строки так, чтобы их обозначения были в порядке возрастания. То есть, сначала идут строчки под номером (1), потом под номером (2) и т.д.
4) Переставляем столбцы по тому же принципу.
Получаем матрицу а исходную, приведенную к блочно-диагональному виду.

Ответить