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

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

Целью изобретения является повышение быстродействия.

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

Устройство содержит первый блок 1 хранения матриц, первый блок 2 формирования матриц, блок 3 управления, второй блок 4 хранения матриц, второй блок 5 формирования матриц, блок 6 формирования обратной матрицы. П.ервьй блок 1 формирования матриц (фиг. 2) содержит блок 7 зт ножения, блок 8 деления И блок 9 умножения,, Второй блок 5 формирования матриц (фиг. 3) содержит блок 10 умножения, блок 11 суммирования, блок 12 хранения единичной матрицы и блок 13 умножения. Блок умножения (фиг, 4) содержит генератор 14 импульсов и кольцевой счетчик 15.

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

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

X.

X,

Х

Хп где Х- - вектор-строка размера LUnl.

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

размера п , где d - столбец размера п 1 и, а D - матрица размера пкп-П, Обратная матрица получается перед началом работы и известной единичной вспомогательной матрицы Р и тоже является единичной. Работа устройства начинается по команде Пуск, поступающей на блок 3 управления. В этом случае з.апуска5

ется генератор 14 импульсов (фиг. 4) и начинает работать кольцевой счетчик 5. Сигнгш С с выхода кольцевого счетчика 15 (фиг. 4) поступает

на входы первого 1 и второго 4 (фиг.1) блока хранения матриц. В блоке 2 происходит вытеснение верхней вектор-строки Х (на 1-м такте Х) матРИДЫ X, в блоке 4 - вытеснение вектор- столбца dCn 1 1 матрицы Р I Начинается формирование обратной матрицы

QT/ вида 1

, ...п,

где bj(X,dr d; В, (l-b. X )D, для матрицы Q, которая получается из матрицы Р (на первом щаге единичной) , при замене в ней последней строки вектор-строкой X (при этом первая строка матригда Р описывается)

.

13 Сигналы, соответствующие элементам векторов и d, поступают на входы первого блока 2 формирования матриц. В этом блоке происходит формирование вектора-столбца В - по формуле bj(X-d) d. Для этого сигналы, соответствующие элементам векторов X. и d, поступают на входь блока 7 умножения (фиг. 2), с выхода которого сигнал (Х d) поступает на вход блока 8 деления, на выходе которого

5 получается обратная величина 1 (Х- d)

/ 1Т

(X.d) . Этот сигнал умножается в блоке 9 умножения на сигналы, соответ- ствзтащие элементам вектора d, В per зультате на выходе блока 2 будут сиг0 .

налы, соответствующие элементам

вектор-столбца Ъ- размера f п у 11, После этого по сигналу С. кольцевого счетчика 15 (блока 3 на фиг. 1) происходит считывание информации о па раметрах матрицы D размера пхп-П из блока 4 хранения матрицы Р о параметрах вектора X - из блока 1 и о параметрах вектора В из первого блока 2 формирования матриц во вто-;

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

В, (.)D,

5 Для этого на входы блока 10 умножения (фиг. 3) поступают сигналы X j I ч п .и В, п X 1 , На выходе полу- чаются сигналы, соответствующие па10

15

31339585

аметрам матрицы В Х размера п х п . ти сигналы поступают на одни входы лока 11 суммирования, на вторые вхоы которого поступает информация, читанная сигналом С с блока 12 храения единичной матрицы I (фиг, З). а выходах блока 11 суммирования поучаются сигналы, соответствую1цие элементам матрицы (). Эти сигалы поступают на входы блока 13 уможения, на вторые входы которого оступают сигналы, соответствующие элементам матрицы n-l . Ка выходе получаются сигналы, соответст- вующие элементам матрицы В. Ln п-П.

Сигналы, соответствующие элементам вектора-столбца В j и матрицы Bj , с выходов первого 2 и второго -5 блоков формирования матриц поступают на входы блока 6 формирования обратной матрицы Q , выходы которого являются выходами устройства. На этом заканчивается первый такт обращения матриц. Для продолжения процедуры обращения необходимо считать матрицей Р матрицу Q. и матри I1

цей Р матрицу QV, т,е. использовать

их как вспомогательные матрицы,. Для этого по сигналам С блока 3 управления в блоке 4 хранения матриц происходит стирание информации об эле20

бло фор дел ри о с в н ма ма ван ди ум вх го да бл пе бл хо го вт с вт

2g вы вх бл ро ва до ко ни то бл но

30

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

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

ход второго блока хранения матриц соединен с входом второго сомножите ля первого и второго блоков умножения первого блока формирования мат- 55 риц, выход второго блока умножения которого соединен с входом второго сомножителя первого блока умножения второго блока формирования матрицы и первым информационным входом блок

5

0

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

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

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

0

ход второго блока хранения матриц соединен с входом второго сомножителя первого и второго блоков умножения первого блока формирования мат- 55 риц, выход второго блока умножения которого соединен с входом второго сомножителя первого блока умножения второго блока формирования матрицы и первым информационным входом блока

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

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

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

Фиг 2

Начало

Hi

fpue. tt

Редактор А.Ворович

Составитель З.Шершнева Техред М .Дидык

Заказ 4224/40 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

15

OSpOC

у Y т т т

Со Cj С2 fJ Ctt

Корректор М.Демчик