Устройство для обращения матриц

 

Изобретение относится к вычислительной технике и может быть использовано при обработке информации в информационно-измерительных системах и комплексах. Цель изобретения С5рос и состоит в повышении быстродействия устройства за счет того, что процедура обращения организована рекуррентно. Это достигается тем, что устройство содержит два блока хранения матриц 1, 4, два блока формирования матриц 2, 5, блок формирования обратной матрицы 6, блок управления 3. Рекуррентная процедура организуется с использованием вспомогательной матрицы и обратной к ней матрицы. Обращение осуществляется путем последовательной .замены во вспомогательной матрице ее строк строками матрицы , подлежащей обрап ению, и нахождения на каждом шаге обратной для нее матрицы. 4 ил. «е (Л Начало Ф -/ 00 00 со ел 00 СП Фиг.1

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1 (19) (11) (51) 4 6

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР пО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ф ) " й

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 13,, Н АBTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3955166/24-24 (22) 20.09 ° 85 (46) 23.09.87. Вюл. М 35 (72) В.И.Кривоцюк и В.Н.Попов (53) 681.325(088,8) (56) Авторское свидетельство СССР

)Ф 1201836, кл, G 06 Р 15/347, 1984.

Авторское свидетельство СССР

N --595726, кл. G 06 F 15/347, 1975. (54) УСТРОЙСТВО Д)И ОБРА)ЦЕНИЯ МАТРИЦ (57) Изобретение относится к вычислительной технике и может быть использовано при обработке информации в информационно-измерительных системах и комплексах. Цель изобретения состоит в повышении быстродействия устройства за счет того, что процедура обращения организована рекуррентно, Это достигается тем, что устройство содержит два блока хранения матриц 1, 4, два блока формирования матриц 2, 5, блок формирования обратной матрицы 6, блок управления 3.

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

1339585 2 ется генератор 14 импульсов (фиг. 4) и начинает работать кольцевой счетчик 15. Сиги ы С с выхода кольцевого счетчика 15 (фиг, 4) поступает на входы перного 1 и второго 4 (фиг.l) блока хранения матриц, В блоке происходит вытеснение верхней вектор-строки Х (на 1-м такте X ) матрицы Х, в блоке 4 — вытеснение векторстолбца й! и 1 ) матрицы P . Начинается формирование обратной матрицы

Q вида

g. =(В,:Ъ; ), =1...n, 1

1 р- где Ъ; =(Х, й) й; В; =(I-b,: X; )D, для матрицы Ц, которая получается из матрицы Р (на первом шаге единичной), при замене в ней последней строки вектор-строкой Х (при этом

1 первая строка матрицы P описывается) А

q,- =(— ) Х

Х, Х

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

Целью изобретения является повышение быстродействия, На фиг. i изображена блок-схема предлагаемого устройства; на фиг, 2 и 3 — примеры выполнения первого и второго блоков формирования матриц; на Фиг, 4 — пример выполнения блока управления.

Устройство содержит первый блок хранения матриц, первый блок 2 фо миронания матриц, блок 3 управления, второй блок 4 хранения матриц, второй блок 5 формирования матриц, блок

6 формирования обратной матрицы, Первый блок 1 формирования матриц (фиг. 2) содержит блок 7 умножения, блок 8 деления и блок 9 умножения„

Второй блок 5 формирования матриц (фиг. 3) содержит блок 10 умножения, блок 11 суммирования, блок 12 хранения единичной матрицы и блок 13 умножения ° Блок умножения (фиг. 4) содержит генератор 14 импульсов и кольце» ной счетчик 15.

Устройство обращения матриц работает следующим образом.

Первый блок,l хранения матриц хра. нит матрицу, подлежащую обращению размера Eп ° п 1, которая может быть

35 представлена в виде

Сигналы, соответствующие элементам векторов X и й, поступают на входы первого блока 2 формирования матриц. В этом блоке происходит формирование вектора-столбца В . по фор1 1 муле Ь; =(Х d.) d.. Для этого сигналы, соответствующие элементам векторов

Х, и d поступают на входы блока 7

1 умножения (фиг. 2), с выхода которого сигнал (X d) поступает на вход

1 блока 8 деления, на выходе которого получается обратная величина 1 (Х й)=

-1 1

=(Х.d) . Этот сигнал умножается в

1 блоке 9 умножения на сигналы, соответствующие элементам вектора d. В ре-. зультате на выходе блока 2 будут сиг40

Х=

° ° °

Х; где X — вектор-строка размера (. 1 n), 45

Второй блок 4 хранения матриц перед началом работы содержит известную для вспомогательной (обычно единичной) матрицыР обратнуюматрицу р вида

Р =(й:D)

РазмеРа 1 п х и 1, где d — столбец раз- 50 мера (п 1), à D — матрица размера

j n к и-1). Обратная матрица получается перед началом работы и известной единичной вспомогательной матрицы P и тоже является единичной, 55

Работа устройства начинается по команде "Пуск", поступающей на блок

3 управления. В этом случае запусканалы, соответствующие элементам вектор-столбца В;, размера (n 1).

После этого по сигналу С кольцевого .1 счетчика 15 (блока 3 на фиг. 1) происходит считывание информации о параметрах матрицы D размерà n хи-1 ) из блока 4 хранения матрицы P, о параметрах вектора Х . из блока 1 и

1 о параметрах вектора В из первого

1 блока 2 формирования матриц Во вто-. рой блок 5 формирования матриц. В блоке 5 происходит формирование матрицы В. по формуле I

В =(1-Ь, Х, )D.

Для этого на нходы блока 10 умножения (фиг. 3) поступают сигналы

Х (1 х п) .и В,(п 1 . На выходе полу 1 чают ся сигналы, соответствующие па1339585

25 раметрам матрицы В X размера (и х и) .

1 1

Эти сигналы поступают на одни входы блока 11 суммирования, на вторые входы которого поступает информация, 5 считанная сигналом С с блока 12 хранения единичной матрицы I (фиг. 3).

На выходах блока 11 суммирования получаются сигналы, соответствующие элементам матрицы (I-В Х ). Эти сигналы поступают на входы блока 13 умножения, на вторые входы которого поступают сигналы, соответствующие элементам матрицы D(п хи-1 . Ha выходе получаются сигналы, соответствующие элементам матрицы В.(п к и-13.

Сигналы, соответствующие элементам вектора-столбца В и матрицы В с выходов первого 2 и второго 5 блоков формирования матриц поступают

20 на входы блока 6 формирования обрат— 1 ной матрицы ц,. = В:: D J выходы ко1 1 торого являются выходами устройства.

На этом заканчивается первый такт обращения матриц. Для продолжения процедуры обращения необходимо считать матрицей P матрицу Q и матри- I 1 цей Р матрицу Q. т.е. использовать

1 их как вспомогательные матрицы. Для этого по сигналам С блока 3 управления в блоке 4 хранения матриц происходит стирание информации об элементах матрицы Р, используемой на предыдущем шаге. Затем по сигналам

С того же блока 3 управления происходит перезапись обратной матрицы из З5 блока 6 в блок 4. Перед началом следующего такта по сигналам блока 3 происходит сброс блоков 2 и 5 формирования матриц, После этого начинается следующий такт обращения. Снова из блока 1 вытесняется следующая вектор-строка X и для матрицы Й . ищет1 "1 ся обратная матрица. В этом случае на первом такте матрица Q получает.1 ся из единичной матрицы Р, в которой 45 первая строка списывается и вместо нее снйзу записывается -вектор-строка

Х.,; матрица Я на втором шаге получается из матрицы Ц, в которой первая строка списывается,. а вместо нее 50 записывается вектор-строка Х и т.д. пока на и-м такте матрица не будет представлять собой искомую матрицу

Х, которую и необходимо обратить. В конце п-го такта в блоке 6 образует- 55 ся искомая обратная матрица.

Формула и з о б р е т е н и я

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

5 .133 формирования обратной матрицы, второй выход второго блока хранения матриц соединен с входом второго сомножителя второго умножителя второго блока формирования матриц, выход которого соединен с вторым информационным входом блока формирования обратной матрицы, первый выход которого соединен с вторым информационным входом блока формирования обратной матрицы, первый выход которого сое9585 в динен с информационным входом второго блока хранения матриц, вход сброса блока управления соединен с соответствуюц1ими входами первого, второго блоков умножения и блока деления первого блока формирования матриц и первого, второго блоков умножения и блока суммирования второго блока формирования матриц, второй выход блока формирования обратной матрицы является выходом устройства.

1339585

ЩОГ

Гц Г Г Су

Рив. Ф

Составитель 3.1 1ершнева

Редактор А.Ворович Техред М.Дидык Корректор М.Демчик

Заказ 4224/40

Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

Устройство для обращения матриц Устройство для обращения матриц Устройство для обращения матриц Устройство для обращения матриц Устройство для обращения матриц 

 

Похожие патенты:

Изобретение относится к вычислительной технике, может быть использовано для решения линейных матричных уравнений и позволяет исследовать матричное представление сетей Петри на достижимость

Изобретение относится к электротехнике и может быть использовано в системах питания индуктивных накопителей энергии

Изобретение относится к области вычислительной техники и предназначено для решения систем линейных уравнений, определения коэффициентов линейного однородного разностного уравнения, определения кода М-последовательностей

Изобретение относится к области вычислительной техники и позволяет вычислять значения функции.вида Х;У( , где та - количество аргументов Xj и у

Изобретение относится к области вычислительной техники и может быть использовано в специализированных устройствах цифровой обработки информации

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

Изобретение относится к вычислительной технике, средствам обработки информации и может быть использовано для быстрой цифровой обработки сигналов, представленных в функции времени

Изобретение относится к вычислительной технике и может быть использовано для управления технологическим оборудованием, алгоритм функционирования которого описы вается логическими функциями, а также для моделирования цифровых устройств с целью их проверки и диагносМ ..Л./1 тики

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления сверстки

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных системах для вычисления двумерной свертки

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных системах для вычисления собственных значений матрицы (n n)

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

Изобретение относится к области спектрального анализа и может быть использовано при классификации квазипериодических сигналов

Изобретение относится к вычислительной технике и может быть использовано в системах интеллектуального анализа данных, в том числе при обработке и анализе геолого-геофизической информации и других данных, полученных при исследовании природных или социально-экономических объектов или явлений

Изобретение относится к вычислительной технике, а именно к устройствам обработки числовых массивов информации, предназначенным для перестановки строк и столбцов двумерного массива данных, представленного в виде матрицы
Наверх