Устройство для решения систем линейных алгебраических уравнений

 

Изобретение относится к цифровой вычислительной технике, в частности к специализированным процессорам. Цель изобретения - расширение класса решаемых задач. Устройство содержит матрицу размером гъп регистров 1 для хранения коэффициентов (п - порядок систем), матрицы размером ПУП первых 9 и вторых 10 групп элементов И, п сумматоров 4, п сдвиговых регистров 3 невязок для хранения результатов итераций, г, сумматоров 15 неизвестных и п сдвиговых регистров 2 неизвестных для формирования решения системы, генератор 5 импульсов, счетчик 11, первый 13 и второй 14 элементы И, позволяющие переходить к вычислению очередных цифр неизвестных при уменьшении значений невязок в сдвиговых регистрах 16 на величину, определяемую п первыми 22 и п вторыми 20 группами элементов, п группами 21 элементов ИЛИ, сумматором 17 старших разрядов, регистром 19 старших разрядов и регистром 18 порядка системы. 1 ил.

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

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

РЕСПУБЛИК (я)э. G06 F 15/324

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4756658/24 (22) 04.11.89 (46) 07.11,91. Бюл. М 41 (71) Ленинградский институт авиационного ,. приборостроения (72) M.Á.Ñåðãååâ и И.M.Ãàâðèëü÷èê (53) 681,325 (088.8) (56) Авторское свидетельство СССР

bh 1179367, кл. G 06 F 15/324, 1983.

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

1Ф 1324035, кл. 6 06 F 15/32, 1986. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ

УРАВ Н ЕН ИЙ (57) Изобретение относится к цифровой вычислительной технике, в частности к специализированным процессорам. Цель изобретения — расширение класса решаемых

„„53J „„1689967 А1 задач. Устройство содержит матрицу размером п п регистров 1 для хранения коэффициентов (n — порядок систем), матрицы размером пхп первых 9 и вторых 10 групп элементов И, и сумматоров 4, и сдвиговых регистров 3 невязок для хранения результатов итераций, r, сумматоров 15 неизвестных и и сдвиговых регистров 2 неизвестных для формирования решения системы, генератор

5 импульсов, счетчик 11, первый 13 и второй

14 элементы И, позволяющие переходить к вычислению очередных цифр неизвестных при уменьшении значений невязок в сдвиговых регистрах 16 на величину, определяемую и первыми 22 и и вторыми 20 группами элементов, и группами 21 элементов ИЛИ, сумматором 17 старших разрядов, регистром 19 старших разрядов и регистром 18 порядка системы. 1 ил.

1689967

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

Цель изобретения — расширение класса решаемых систем уравнений.

На чертеже представлена структурная схема устройства.

Устроиство содержит матрицу пкп регистров 1 коэффициентов, и сдвиговых регистров 2 неизвестных, и сдвиговых регистров 3 невяэок, и сумматоров 4, генератор 5. импульсов, вход 6 коэффициентов устройства, вход 7 невязок устройства, выход 8 устройства, первую матрицу пкп групп элементов

И 9, вторую матрицу пкп групп элементов И

10, счетчик 11, вход 12 начальной установки и запуска устройства, первый элемент И 13, второй элемент И 14, и сумматоров 15 неизвестных, и сдвиговых регистров 16, сумматор 17 старших разряд в, регистр 18 порядка системы, регистр 1С старших разрядов, вторую группу элементов И 20; группу п элементов ИЛИ 21, первую группу элементов И 22, вход 23 порядка системы устройства.

Алгоритм работы устройства для решения систем алгебраических уравнений вида

АХ - В порядка п основан на методе минимизации ноомы вектора. невязок

ЛХ " )=-ф )) В аиф )) 2 л

Ь где 9 выбирается так

О,если 0,5 >le(1 I;

1, если 0,5 е " 1 !.

Если 3i lK ) ) h/2, то

l =1

О, если 0 75 > I e f 1 I;

g (к — 1)

1, если 0,75 < I е 1 1

Целое п)к такое, что

2 <г "Ия" И<2o к(к) и, ., к — )). л, (к — 1)))

J — 1 (к) (к) . 2

I 1,n;k-О,1,2...

Начальные условия е fP - -bi: хi - 0, Разряды в сдвиговом регистре обозначены следующим образом;

1,2,3, где 1 — знаковый разряд;

2 — первый разряд;

3 — второй разряд.

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

Перед началом вычислений в регистры

1 коэффициентов по входу 6 коэффициентов записываются коэффициенты системы уравнений, по входу 7 невязок в сдвиговые реги15 стры 3 невязок и сдвиговые регистры 16 записываются свободные члены системы, а в регистр 18 порядка системы по входу 23 порядка записывается число n/ã, где n— порядок системы. После записи по входу 12 начальной установки и запус а в счетчик 11 информации его выход переноса обнуляется, что позволяет запуститься генератору 5 импульсов, Каждым импульсом с прямого выхода генератора 5 импульсов синхрони25 зируется запись в сдвиговые регистры 3 невяэок и сдвиговые регистры 16 значений результатов итераций с выходов соответствующих сумматоров 4, на входы которых подаются со сдвиговых регистров 16 пред30 ыдущие невязки. При помощи сумматора 17 старших разрядов и регистра 19 старших разрядов сравнивается количество сдвиговых регистров 3 невязок, имеющих ненулевые старшие разряды. Если это количество

35 не превосходит и/г, то с помощью схемы, построенной на группах элементов И 20, 22, ИЛИ 21, на сумматоры 4 через группы элементов И 9, 10 поступают коэффициенты при наличии единичных значений в двух

40 старших значащих разрядах сдвиговых регистров 16. Если количество сдвиговых регистров 3 невязок, имеющих ненулевые старшие разряды, превосходит п/г, то на сумматоры 4 коэффициенты поступают та45 ким же образом, но при наличии единичного значения в одном старшем значащем разряде сдвиговых регистров 16. При условии, что все старшие разряды в сдвиговых регистрах

16 обнулены, импульсом с инверсного выхо50 де генератора 5 импульсов через второй элемент И 14 происходит сдвиг в сдвиговых регистрах 3 невязок и сдвиговых регистрах .1 6 и добавление по счетному входу счетчика

11 к его содержимому и1"; а импульсом с

55 прямого выхода через первый элемент И 13 — сдвиг в сдвиговых регистрах 2 неизвестных, При.этом на первые входы сумматоров .15 неизвестных из сдвиговых регистров 2 неизвестных подаются значения предыду1689967 6

20 щих приближений неизвестных, а на вторые входы сумматоров 15 неизвестных подается приращение "1", если число сдвиговых регистров 3 с нулевыми старшими разрядами больше n/ã и два старших значащих разряда сдвиговых регистров 16- единичные, либо один старший разряд единичный, в противном случае. Полученные новые приближения неизвестных записываются в сдвиговые регистры 2 неизвестных и при обнулении первых разрядов всех сдвиговых регистров 16 происходит сдвиг влево на один разряд содержимого сдвиговых регистров 2 неизвестных, После окончания вычислений, когда на выходе переноса счетчика 11 появится единичное значение, блокирующее работу генератора 5 импульсов, решение системы считывается из устройства на выход 8.

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

Устройство для решения систем линейных алгебраических уравнений, содержащее матрицу и;е регистров коэффициентов, и сдвиговых регистров невяэок, и сдвиговых регистров неизвестных, п сумматоров, генератор импульсов, счетчик, первую и вторую матрицы п>а групп элементов И, и сумматоров неизвестных, первый и второй элементы И, причем первые входы элементов И (1, J)-x групп первой и второй матриц соединены соответственно с прямыми и инверсными выходами (1, 1)-го регистра коэффициента матрицы (1, 1 - 1, й) информационный вход

J-го сдвигового регистра невязок соединен с выходом 1-ro (i = J) сумматора, первые входы которого соединены с выходами элементов И групп J-й строки первой и второй матриц, выход 1-ro сумматора неизвестного соединен с информационным входом J-го сдвигового регистра неизвестного. выход которого соединен с первым входом j-го сумматора неизвестного, прямой выход генератора импульсов соединен с входами записи всех сдвиговых регистров невязок и первым входом первого элемента И, выход которого соединен с входами сдвига всех сдвиговых регистров неизвестных, выходы которых являются выходом устройства, ин.версный выход генератора импульсов соединен с первым входом второго элемента И, выход которого соединен с входами сдвига

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

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