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

 

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

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

РЕСПУБЛИК (19) (И) yg y С 06 F 15/347 (21) 3770862/24-24 (22) 09.07 ° 84 (46} 15.02.86. Бюл. ¹ 6 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.Ф. Арсенц, М.Е. Бородянский, И.Ф. Сурженко и 3.M. Саак (53) 681.365(088.8) (56) Авторское свидетельство СССР № 404090, кл. G 06 F 15/347, 1971.

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

¹ 595726, кл. Г. 06 F 15/347, 1976. (54) (57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ОБРАТНОЙ МАТРИЦЫ, содержащее первый и второй сумматоры, первый и второй блоки умножения, о т л и ч а ю щ е/ е,с я тем, что, с целью расширения класса решаемых задач за счет обеспечения нахождения обратной матрицы для матрицы со свойством КеА > О, ReA - =/А + А / — при увеличении быт

2 стродействия, в него введены счетчик, схема сравнения, пять элементов ИЛИ, . кольцевой регистр, распределитель импульсов, элемент И, генератор импульсов, два блока вычисления скалярного произведения, шесть коммутаторов и восемь блоков памяти, причем первый сумматор выполнен накапливающим и информационный вход устройства соединен с первым информационным входом первого блока умножения и входом записи перьвого блока памяти, выход которого соединен с первыми информационными входами первого и второго коммутаторов, выходы которых соединены с первым и вторым информационными входами первого блока вычисления скалярного произведения, выход которого соединен с информационным входом третьего коммутатора, первый и второй выходы которого соединены со входами записи соответственно второго и третьего блоков памяти, вы— ходы которых соединены соответственно с первым и вторым информационными входами четвертого коммутатора и вторыми информационными входами соответственно первого и второго коммутаторов, выход третьего блока памяти соединен с третьим информационным входом второго коммутатора, выход четвертого коммутатора соединен с первым информационным входом второго бло- ка вычисления скалярного произведения, выход которого соединен с первым информационным входом пятого коммутатора, второй информационный вход которого соединен с выходом четвертого блока памяти и вторым информа- е . ционным входом второго блока вычисления скалярного произведения, вход стробирования которого соединен с выходом первого элемента ИЛИ, первым входом второго элемента ИЛИ и управляющим входом пятого коммутатора, выход которого соединен с информационным входом первого накапливающего сумматора, тактовый вход которого соединен с выходом второго элемента ИЛИ, выход первого накапливающего сумматора соединен с входом записи пятого блока памяти, вход разрешения чтения которого соединен с выходом схемы сравнения и входом останова генератора импульсов, вход запуска которого соединен с входом пуска устройства, выход генератора импульсов соединен с так12»754

10

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

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

ReA > 0, ReA = /А + А / < (1) при увеличении быстродействия.

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

Устройство содержит вход матрицы

А 1, блок памяти 2, коммутаторы 3 и

4, блок 5 вычисления скалярного произведения 5, коммутатор 6, блоки памяти 7 и 8, коммутатор 9, блок 10 вычисления скалярного произведения, коммутатор 11, сумматор 12, блок памяти 13, выход 14, блок памяти 15, коммутатор 16, блоки умножения 17 и 18, входы задания единичной 19 и исходной 20 матриц, блоки памяти 21 и 22, сумматор 23, блок памяти 24, генератор импульсов 25, элемент И

754

10 д-, и : (г) о

20 чество циклов, ю — число членов ряда (3), а на вход 19 поступает единичная матрица Е. В блоке памяти 15 записаны значения коэффициентов а а,,а ....а

По команде Пуск", поступающей на вход 37, происходит запуск генератора 25 импульсов, которым осуществляется продвижение "единицы" на выходах распределителя 27. По первому такту осуществляется подключение к первым входам блоков умножения 17 и 18 коэффициентов а и а, из блока памяти 15. Производится вычисление мат— риц а, E и а, А, которые заносятся в блоки памяти 21 и 22 соответственно.

По второму такту в сумматоре 23 вычисляется матрица 5, =а, Е + а, А, которая заносится в блок памяти 24. По третье— му такту осуществляется занесение матрицы 5 в сумматор 12. По четвертому такту заносится в блок памяти 2 матрица А, коммутатор 16 подключает к входам блоков умножения 17 и 18 коэффициенты а, а,. Осуществляется вычисление матриц a„ E и а,А, кото— рые заносятся соответственно в блоки памяти 21 и 22. По пятому такту в блоке 5 осуществляется умножение мат2 риц -АА и результат умножения А заносится в блок памяти 8, также вычисляется в сумматоре 23 значение -" =

=а,Е +а,A и заносится в память блока

24. По шестому такту коммутатор 11 подключает выход блока 10 к входу сумматора 12, в блоке in осуществляется умножение матриц А 61, результат суммируется в сумматоре 12. JIn седьмому такту коммутаторы 3 и 4 к+1 N щ 1 к+1 о

30

Bl A ll N) e (т12) 40

6 G IIA11 (4) 45 где под //-// понимается любая из общепринятых норм матриц., Найденные а (4) т и N вводятся в устройство.

Преобразуем (3) к виду, удобному

50 для реализации в устройстве

Ф К+1 к кй

2 W

4 =.> (-1) А =a Е.ia,41a A1...+а А

К*О (К+1), > 55 (5) 3 1211

26, распределитель импульсов 27, элементы ИЛИ 28-32, кольцевой регистр

33, счетчик 34, схему сравнения 35, вход задания числа циклов 36,. вход запуска 37, вход задания адреса коэффициентов 38.

В основу предлагаемого вычислительного устройства положен алгоритм вычисления обратной матрицы где матрица А удовлетворяет условию (1) .

Численный аналог (2) имеет вид

00 Н

-1 (-At (Я, К кФ, A = e Jt"-))E-А1 А - — +„, (-<) A —, „, Jt=

2 " К! где E — единичная матрица того же размера, что и заданная матрица А, A = Em — нечетное число.

Длина интервала интегрирования а и число членов ряда 1п при заданной точности вычисления 6 для проектируемого вычислительного устройства предварительно могут быть определены из соотношений

n1 r— (1 1) 2ï (m+2-llAll н)

r+2-IlAllN О, К+1 где а„N /(К+1)! (К=0,1,2 „,т).

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

В исходном "îñòîÿíèè генератор импульсов 25 не вырабатывает импульсов, коммутатор 3 подключает выход блока памяти 2 к первому входу блока 5, коммутатор 4 подключает выход блока памяти 2 к второму входу блока 5, коммутатор 6 соединяет выход блока 5 с блоком памяти 8, коммутатор 16 отключает блок памяти 15 от входов блоков умножения 17 и 18, коммутатор 9 соединяет выход блока памяти 3 с входом блока 10, а коммутатор 11 соединяет выход блока памяти 24 и вход сумматора 12.

На входы 1 и 20 поступает данная матрица A на вход 30 — число М причем М = — 30, где М вЂ” коли— я+1

1211754

ВНИИПИ Заказ 642/54 Тираж 673 Подписное

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная, 4 подключают выход блока памяти 8 к первому и второму входам блока 5, коммутатор 16 подКлючает коэффициенты.0, с1, а блоки 17 и 18 вычисляют матрицыа E иабА, которые заносятся в память. Коммутатор 6 подключает выход блока 5 к входу блока памяти 7, а коммутатор 9 выход блока

7 — к блоку 10. По восьмому такту 10 в блок 5 вычисляется матрица А А .

2 2

В сумматоре 23 вычисляется матрица

Б =a> E +ao A. В девятом такте происходит вычисление матрицы А 5, кото4 рая суммируется в сумматоре 12 с мат- 15 рицей 4 5, . По десятому такту происходит включение кольцевого регистра 33 импульсов,с первого выхода которого подключается очередная пара коэффициентов a, ца и вычисляются соответ- 20 ствующие матрицы Sq =a,f+as A, которые заносятся в память. По импульсу с второго входа блок 5 вычисляет матрицу А А, которая заносится в

4 блок 7, а сумматор 23 вычисляет матрицу 5 =а, E +о А . По импульсу с третьего выхода в блоке. 10 вычисляется матрица А 5, которая в сумматоре 12 складывается с матрицей

А 5 + A5< +5О, а в счетчик 34 заносится "единица

В дальнейшем импульсы с выходов кольцевого регистра 33 появляются в той же очередности, что и раньше, осуществляя последовательное получение соответствующих промежуточных сумм в сумматоре 12. Количество циклов кольцевого распределителя 33 подсчитывается счетчиком 34. Когда число циклов счетчика. совпадает с величиной М, сигналом с выхода схемы сравнения происходит "Останов" генератора 25, коммутаторы приходят в первоначальное состояние, а результат A (2) из блока памяти 13 поступает на выход.