Устройство для обращения матриц Советский патент 1991 года по МПК G06F15/347 

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

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

Цель достигается использованием оригинального алгоритма обращения матриц, который имеет вид

,

АК+Г (ОТ,

Е + А„ В,

где В

Е-Т

А;

и

(Ч

V

max

,n А - исходная матрица; - начальное приближение;

О)

2) (3)

Е - единичная матрица; п - размерность матрицы А. Скорость сходимости алгоритма определяется выражением

,1 -1 -(,, НЕ - А АО II |iu и

||А - АК||Ј ||B|v

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

На фиг.1 приведена структурная схема устройства для обращения матриц; на фиг. 2 - блок вычисления коэффициента О| ; на фиг.З - блок вычисления элементов матрицы В; на фиг.4 - блок вычисления итераций; на фиг.5 - временная диаграмма работы блока вычисления коэффициента fU .

Устройство (фиг.1) содержит первый информационный вход 1, первый

05 Ј

ел

CD

блок 2 памяти, блок 3 вычисления коэффициента (Ц , блок 4 деления, бло 5 вычисления итераций, блок 6 умножения, блок 7 вычисления элементов матрицы В, групту 8 информационных входов, элементы ИЛИ 9, второй. 10 и третий И блоки памяти, информационный выход 12, блок I3 вычитания, регистр 14, схему 15 сравнения, триг гер 16, первый дешифратор 17, элемент И 18, второй дешифратор 19, выход 20 признака окончания вычислений, блок 21 управления, вход 22 запуска устройства, первый 23 и вто- рой 24 блоки формирования адреса, третий 25 и второй 26 информационные входы устройства.

Блок вычисления коэффициента /Ц (фиг,2) содержит генератор 27, сдви говый регистр 28, сумматор 29, буферный регистр 30, регистр 31 максимума, схему 32 сравнения, триггеры 33 и 34, элементы И 35 и 36.

Блок работает следующим образом. По сигналу от внешнего источника происходит запуск генератора 27, вырабатывающего две серии импульсов; прямую и инверсную. По каждому импульсу на вход сумматора 29 поступа- ет элемент строки обрабатываемой матрицы, на выходе сумматора 29 формируется результат сложения; этого элемента с текущим значением промежуточной суммы, хранящейся в буферном регистре 30. Через п импульсов на (n-HJ-M выходе сдвигового регистра 28 появляется единичный потенциал (результат продвижения единицы, занесенной в первый разряд сдвигового регистра 28), по которому триггер 33 переходит в единичное состояние и запрещает перезапись информации в буферный регистр 30. Одновременно происходит сравнение чисел в буфер- ном регистре 30 и регистре 31 максимума. Если число в буферном регистре больше числа в регистре максимума, схема 32 сравнения устанавливает триггер 34 в единичное состояние к тем самым разрешает прохождение (п+2)-го импульса перезаписи информации из буферного регистра в регистр максимума. В противном случае содержимое регистра максимума не обновляется. По (п+3)-му импульсу буферный регистр и триггер 34 обнуляются, по ()-му импульсу обнуляется триггер1 33 к в первом разряде

0

5 0 Q 5

0

сдвигового регистра устанавливается единица.Блок готов к вычислению очередного значения суммы элементов строки матрицы и определению текущего максимального значения. Через п циклов и регистра максимума хранится значение Ш ,

Блок вычисления элементов матрицы В (фиг.З) содержит управляемый генератор 37, кольцевой сдвиговый регистр 38, коммутатор 39, вычитатель 40.

Блок работает следующим образом. В исходном состоянии в первый разряд сдвигового регистра 38 занесена единица, остальные разряды обнулены. По единичному сигналу с первого разряда сдвигового регистра коммутатор 39 подключает вычитатель к второму и третьему информационным входам блока вычисления элементов матрицы В, на которые подаются соответственно числа I и О. По сигналу запуска с блока управления генератор переходит в автоколебательный режим. По каждому импульсу генератора единица, занесенная в первый разряд сдвигового регистра, продвигается в соседний старший разряд. Через каждые п тактов коммутатор подает числа 1 и О на вход вычитателя. На второй вход вычитателя поступает текущий элемент матрицы 2/(Ц А. Процесс вычисления прекращается по появлению запрещающего сигнала на входе генератора 37.

Блок вычисления итерации (фиг.4) содержит узлы 41 и 42 задержки, элементы ИЛИ 43 и 44, узел 45 памяти, регистры 46 и 47, скалятор 48, коммутатор 49, кольцевой регистр 50 и сумматор 51 ,

Блок работает следующим образом. По команде запуска управления из блока 10 памяти через узел 45 памяти в регистры 46 и 47 заносятся соответственно столбец матрицы В и строка матрицы А. В скаляторе 48 вычисляется элемент матрицы, который в случае необходимости в соответствии с алгоритмом (1) складывается с 2//Ц, что обеспечивается кольцевым сдвиговым регистром 50 и коммутатором 49. В результате на выходе блока формируется элемент матрицы очередного приближения А И . По сигналу с выхода признака пятого цикла вычислений блока управления осуществляется поэлементное чтение матрицы А одновременным занесением в те же

-I к-

ячейки узла 45 памяти значений новой матрицы .

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

В первый блок памяти заносятся элементы обращаемой матрицы, а в блок вычисления итераций - элементы матрицы начального приближения. По сигналу запуска блок управления вырабатывает сигнал признака первого цикла вычислений, по которому первый блок памяти переходит к режиму чтения, а блок вычисления коэффициента (U - к вычислению /К . С первого блока формирования адреса на адресный вход первого блока памяти поочередно поступают адреса упорядоченного множества элементов матрицы, которое синхронизируется признаком чтения. В блоке вычисления коэффициента кажбатывается в соответствии с формулой (3). По истечении (п+4) такдый поступающий элемент матрицы обра- 25 последнего элемента, вырабатывается

сигнал окончания вычислений, который в случае выполнения- условия JAjj- Ац.| (триггер }6 остается в ну- лёвом состоянии) поступает через 30

тов на выходе блока формируется значение Ш . Затем по сигналу с выхода признака второго цикла вычислений блока управления в блоке деления вы- 2

числяется значение -г- . Блок управления вырабатывает сигнал признака третьего цикла вычислений, по которому первый блок памяти переходит в режим чтения и запускаются блоки умножения и блок вычисления элементов матрицы В. Одновременно упорядоченные адреса элементов матрицы А формируются в блоке 23, Элементы матрицы В, вычисленные в блоке 7, заносятся в соответствующие ячейки второго блока 10 памяти, В блоке управления формируется циклически серия импульсов то на вых.оде признака четвертого цикла вычислений, то на выходе признака пятого цикла вычислений. На втором выходе второго блока 24 формирования адреса формируются адреса элементов столбцов матрицы и строк матрицы В, которые поступают в блок 5 для вычисления элементов матрицы . Полученные значения заносятся в третий блок 11 памяти, в котором по завершении четвертого цикла вычислений оказываются занесенными все элементы матрицы

А к-И

элемент И 18 на выход признака окончания вычислений устройства и на одноименный вход блока управления. Бели в процессе сравнения элементов матриц и триггер 16 перейдет в

эс единичное состояние, то сигнал с его выхода запретит прохождение сигнала окончания вычислений на вход блока управления, произойдет повторение четвертого и пятого циклов вычис40 лений.

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

45 Устройство для обращения матриц, содержащее блок деления, блок вычитания, блок управления, регистр, триггер, элемент И и элемент ИЛИ, отличающееся тем, что, с

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

16475916

По сигналу с выхода признака пятого цикла вычислений блока управления происходит перезапись элементов матрицы ., из третьего блока памяти в блок вычисления итераций. Одновременно в блоке 13 вычисляется разность соответствующих . элементов матриц А + и А к ,

которая сравнивается в схеме сравнения 15с заранее заданным допуском 6 , поданным на второй информационный вход устройства 26. В случае, если разность превысит допустимую,

импульс с выхода схемы сравнения переведет триггер 16 в единичное состояние. В начале пятого цикла вычислений сигналом с выхода дешифратора 17 триггер 16 обнуляется. Дешифратор

17 селектирует адрес первого элемента матрицы Когда в блоке 23 формирования адреса сформируется адрес последнего элемента матрицы, на выходе дешифратора 19, селектирующего адрес

последнего элемента, вырабатывается

сигнал окончания вычислений, который в случае выполнения- условия JAjj- Ац.| (триггер }6 остается в ну- лёвом состоянии) поступает через

элемент И 18 на выход признака окончания вычислений устройства и на одноименный вход блока управления. Бели в процессе сравнения элементов матриц и триггер 16 перейдет в

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

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

Устройство для обращения матриц, содержащее блок деления, блок вычитания, блок управления, регистр, триггер, элемент И и элемент ИЛИ, отличающееся тем, что, с

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

71

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

8

JQ о 45 0

5

35

40

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

I6Јmi

Изобретение относится к области вычислительной техники и может быть использовано в цифровых вычислительных системах для обращения матриц. Цель изобретения - расширение функциональных возможностей устройства за счет обращения положительно определенных матриц. Цель достигается применением оригинального итерационного алгоритма обращения матриц A (2/(U)-E , где -( „ max J5|Ч к -akj i A исходная матрица размерности п; ное приближение; Е - ца. Структура и работа устройства являются адекватным отражением приведенного алгоритма, 5 ил. Ао - началь- единичная матри