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

 

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

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

СОЩЕЛИСТИЧЕСНИХ

РЕС 1УЬЛИК

„.ЯО„„ (gg)g G 06 F 15/347

А1 (3) ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ .ГКНТ СССР (21) 4620124/24 (22) 12,12.88 (46) 07.05.91. Бюл. № 17 (71) Таганрогский радиотехнический институт им. В.Д.Каль!кова (72) В.Ф.Арсени, М.Е. Бородянский, А.Н.Целых, В.Я.Пекарь, А.С.Кузьмин и Л.Л,Михайлов (53) 681 . 3 (008 ° 8) (56) Авторское свидетельство СССР № 813444, кл. G 06 Г 15/324, !981.

Авторское свидетельство СССР № 595726, кл. G 06 F 7/38, 1978. (54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ (57) Изобретение относится к области вычислительной техники и может быть

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

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

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

-! !

А = — --Е+А В !!+! lV

К (1)

2 гдеВ=Е- — — А" 11 ъ (2)

Yl 11 и — а„,;

К-1 вп .;.! а

А — исходная матрица;

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

-! -!

А =(2ф1)Е 4- А В, где В=Е -(2 p)A;

ma„- И

-> а ; A — исходная

К1,n -,- К! ° матрица размерности и; А„- начальное приближение, Š— единичная матрица, Структура и работа устройства являются адекватным отражением приве- денного алгоритма, 5 ил. ф

Š— единичная матрица;

n — размерность матрицы А.

Скорость сходимости алгоритма определяется выражением

1в — в а — — — — — - ((в(!.

-(Il E — А Ao ll — Ц А!! 1(В качестве начального приближения, если оно не известно, можно выбрать единичную матрицу.

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

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

1647591 блок 2 памяти, блок 3 вычисления коэффициента 1Ц, блок 4 деления, 6пок

5 вычисления итераций, - блок 6 умножения, блок 7 вычисления элементов матрицы В, группу 8 информационных входов, элементы ИЛИ 9, второй.

10 и третий 11 блоки памяти, информационный выход 12, блок 1 3 вычитания, регистр 14„ схему 15 сравнения, триг- 10 гер 16, первый дешифратор 17, элемент И 18, второй дешифратор 19, выход 20 признака окончания вычислений, блок 21 управления, вход 22 запуска устройства, первый 23 и вто- 15 рой 24 6поки формирования адреса, третий 25 и второй 26 информационные входы устройства.

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

Блок работает следующим образом. 25

По сигналу от внешнего источника происходит запуск генератора 27, вырабатывающего две серии импульсов: прямую и инверсную. Но каждому импульсу на вход сумматора 29 поступа- 30 ет элемент строки обрабатываемой матрицы, на выходе сумматора 29 формируется результат сложения этого элемента с текущим значением промежуточной суммы, хранящейся в буферном регистре 30, Через и импульсов на (и+1)-м,. выходе сдвигового регистра 28 появляется единичный потенциал (результат продвижения единицы, занесенной в первый разряд сдвигового регистра 28), по которому триггер

33 переходит в единичное состояние и запрещает перезапись информации в буферный регистр 30. Одновременно происходит срааНеННе чисел а буфер 45 ном регистре 30 и регистре 31 максимума. Если число в буферном регистре больше числа в регистре максимума, схема 32 сравнения устанавливает триггер 34 в единичное состояние и тем самым разрешает прохождение (n+2)-rо импульса перезаписи информации из буферного регистра в регистр максимума, В противном случае содержимое регистра максимума не обновляется, По (и+3)-му импульсу

55 буферный регистр и триггер 34 обиуляются, по (и+4)-му импульсу обнуляется триггер1 33 и в первом разряде сдвигового регистра устанавливается единица. Блок готов к вычислению очередного значения суммы элементов строки матрицы н определению текущего максимального значения, Через и циклов и регистра максимума хранится значение (М

Блок вычисления элементов матрицы

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

40.

Блок работает следующим образом, В исходном состоянии в первый разряд сдвигового регистра 38 занесена единица, остапьные разряды обнулены.

По единичному сигналу с первого разряда сдвигового регистра коммутатор

39 подклкяает вычитатель к второму и третьему информационным входам блока вычисления элементов матрицы

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

"О" на вход вычитателя. На второй вход вычитателя поступает текущий элемент матрицы 2l P А. Процесс вычисления прекращается по появлению запрещаюшего сигнала на входе генератора 37.

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

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

В результате на выходе блока формируется элемент матрицы очередного приближения А;, По сигналу с выхода признака пятого цикла вычислений блока управления осуществляется по1647591

5 элементное чтение матрицы А „(., с одновременным занесением в те же ячейки узла 45 памяти значений но-( вой матрицы А(, .

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

В первый блок памяти заносятся элементы обращаемой матрицы, а в блок вычисления итераций — элементы матрицы начального приближения. По сигналу запуска блок управления вырабатывает сигнал признака первого цикла вычислений, по которому первый блок памяти переходит к режиму чтения, а блок вычисления коэффициента 1- к вычислению (М . С первого блока Формирования адреса на адресный вход первого блока памяти поочередно поступают адреса упорядоченного множества элементов матрицы, которое синхронизируется признаком чтения.

В блоке вычисления коэффициента каждый поступающий элемент матрицы обрабатывается в соответствии с формулой (3). По истечении (и+4) так2 то в на выходе блока формируется значение М . Затем по сигналу с выхода признака второго цикла вычислений блока управления в блоке деления вы2 числяется значейие — — . Блок управГ ления вырабатывает сигнал признака третьего цикла вычислений, по которому первый блок памяти переходит в режим чтения и запускаются блоки умножения и блок вычисления элементов матрицы В. Одновременно упорядоченные адреса элементов матрицы

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

-( элементов матрицы А, +, . Полученные значения заносятся в третий блок

11 памяти, в котором по завершении четвертого цикла вычислений оказываются занесенными все элементы матрицы

«»

А к+ °

По сигналу с выхода признака пятого цикла вычислений блока управления происходит перезапись элемен« I тов матрицы А„+(из третьего блока памяти в блок вычисления итераций.

Одновременно в блоке 13 вычисляется разность соответствующих

1 -( элементов матриц А „»(и А, которая сравнивается в схеме сравнения 15 с заранее заданным допуском

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

I7 триггер 16 обнуляется. Дешифратор

20 17 селектирует адрес первого элемента матрицы. Когда в блоке 23 -Формирования адреса сфоРмируется адрес последнего элемента матрицы, на выходе дешифратора 19, селектирующего адрес последнего элемента вырабатывается сигнал окончания вычислений, который в случае выполнения- условия А(,- Ак (Я(триггер 16 остается в ну1левом состоянии) поступает через

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

А „ и А „+, триггер,16 перейдет и единичное состояние, то сигнал с

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

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

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

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

164759I подключен к информационному входу первого блока памяти, первый выход которого соединен с информационным входом блока вычисления коэффициента р, выход которого подключен к первому входу блока деления, выход которого подключен к первый информационным входам блока вычисления итераций и бло-, ка умножения, второй информационный щ вход и выход которого подключены соответственно к второму выходу первого блока памяти и первому информационному входу блока вычисления элементов матрицы В, второй и третий информационные входы которого подключены соответственно к перввму и второму информационным входам группы устройства, выход блока вычисления элементов матрицы В подключен к информационному входу второго блока памяти, выход которого подключен к второму информационному входу блока вычисления итераций, первый информационный выход которого соединен 25 с информационным входом третьего блока памяти, выход которого подключен к третьему информационному входу блока вычисления итераций, информационному выходу устройства и перво- gg му входу вычитателя, выход и второй вход которого соединены соответственно с первым входом схемы сравнения и выходом регистра, вход которого подключен K второму информационному Bbl 35 ходу блока вычисления итераций, второй вход и выход схемы сравнения подключены соответственно к второму информационному входу устройства и входу установки триггера, вход обнуления и выход которого подключены соответственно к выходу первого дешифратора и первому входу элемента И, второй вход и выход которого подключены соответственно к выходу второго 45 дешифратора и выходу признака окончания вычислений устройства, объединенному с одноименным входом блока управления, вход запуска и выход признака первого цикла вычислении котб Я>ro подключены соответственно к входу запуска устройства и входу запуска блока вычисления коэффициента ф, объединенному с входом признака первого цикла вычислений первого блока формирования адреса и первым входом элемента ИЛИ, выход которого подключен к входу управления записью-считыванием первого блока памяти, вход адреса которого соединен с первым входом адреса второго блока памяти и первым выходом первого блока формирования адреса, вход признака третьего цикла вычислений которого подключен к выходу признака третьего цикла вычислений блока управления, второму входу элемента ИЛИ, входам запуска блока умножения, блока вычисления элементов матрицы В и второго блока памяти, второй вход адреса которого подключен к первому выходу второго блока формирования адреса, вход запуска которого подключен к выходу признака четвертого цикла вычислений блока управления, входу запуска третьего блока памяти и первому входу запуска блока вычисления итераций, первый вход адреса которого подключен к второму выходу второго блока формирования адреса, выход признака пятого цикла вычислений блока управления подключен к входу запуска первого блока формирования адреса, третьему входу элемента И, второму входу запуска блока вычисления итераций, второй вход адреса которого подключен к второму выходу первого блока формирования адреса, входам первого и второго дешифраторов и входу адреса третьего блока памяти, выход признака второго цикла вычислений блока управления подключен к входу запуска блока деления, вход установки начальных данных блока вьлйсления итераций является третьим информационным входом устройства.

1647591

1047591

1647591

1647591

Ил

Редактор Н.Гунько

Производственно-издательский комбинат "Патент", r. ужгород, ул. Гагарина, 101

Заказ 1401

ВНИИПИ Государственного

113035, Составитель К.Кухаренко

Техред М.Дидык Корректор Л.Патай, Тираж. 421 Подписное комитета по изобретениям и открытиям при ГКНТ СССР

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