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

 

Изобретение относится к вычислительной технике и может быть использовано при построении цифровых специализированных процессоров для решения систем линейных алгебраических уравнений. Цель изобретения - расширение класса решаемых задач. Поставленная цель достигается тем, что устройство содержит матрицы размером пхп гдеппорядок системы линейных алгебраических уравнений, регистров 1., первую группу из п сдвиговых регистров 2, вторую группу из п сдвиговых регистров 3, первую группу из п сумматоров 4, генератор 5 тактовых импульсов, входы 6 коэффициентов матрицы системы уравнений, входы 7 свободных членов, выходы 8 результата , первую матрицу размером п хп групп элементов И9,1 вторую матрицу размером пхп групп элементов И 10, счетчик 11, вход 12 задания режима работы устройства, первый и второй элементы И 13 и 14, вторую группу из п сумматоров 15. Расширение функциональных возможностей обеспечивается тем, что при уменьшении незязок на заданную величину необходимо переходить к вычислению следующих цифр результатов, в противном случае - вычислять корректируюшие цифры неизвестных. 1 ил. с (С (f 00 го 4 О сд

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

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

РЕСПУБЛИН

Ai (19) (10 (51)4 G 06 Р 15/32

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И, ОТНРЫТИЙ (21) 4010675/24-24 (22) 08, 01. 86 (46) 15.07,87, Бюл, и 26 (72) В, Д. Байков и М, Б, Сергеев (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

9 1088007, кл, G 06 Р 15/32, 1982.

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

У 1179367, кл. G 06 Р 15/324, 19 83, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано при построении цифровых специализированных процессоров для решения систем линейных алгебраических уравнений, Цель изобретения— расширение класса решаемых задач, Поставленная цель достигается тем, что устройство содержит матрицы размером n xn, где и порядок системы линейных алгебраических уравнений, регистров 1, первую группу из и сдвиговых регистров 2, вторую группу из и сдвиговых регистров 3, первую группу из и сумматоров 4, генератор 5 тактовых импульсов, входы 6 коэффициентов матрицы системы уравнений, входы 7 свободных членов, выходы 8 результата, первую матрицу размером п х и групп элементов И 9,! вторую матрицу размером п хп групп элементов

И 10, счетчик 11, вход 12 задания режима работы устройства, первый и второй элементы И 13 и 14, вторую группу из п сумматоров 15, Расширение функциональных возможностей обеспечивается тем, что при уменьшении не- с вязок на заданную величину необходима переходить к вычислению следующих цифр результатов, в противном случае — вычислять корректирующие С цифры неизвестных. 1 ил.! 324035

Р-1 х;=. х ;1 2 к=о где i,, j = 1 и;

Ьск(< (О 11

11 9 1 1,) 1 х . Е 1011 I);

k — цифры.

Вычисление цифр неизвестных систем уравнений осуществляется по следующим соотношениям: и

Н () 1 P1 Q

+ а.. х ° 2 Е. (.-

1 (=1

45 (К! (к ., Н

< (-з1- п(с.; p ) ) i

Е, -0 .н

1 =:1; 0, если старший разряд

11, если старший разряд

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

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

На чертеже изображена структурная схема предлагаемого устройства ° l0

Устройство содержит матрицу и х п регистров 1, первую группу из и сдвигоных регистров 2, вторую группу из и сднигоных регистров 3, первую группу из и сумматоров 4 „ генератор 5 !5 тактовых импульсов, входы 6 коэффициентов системы уравнений устройства, входы 7 свободных членов устройства, выходы 8 результата устройства, первую и вторую матрицы, размером п хп 20 каждая групп элементов И соответственно 9 и 10, счетчик 11 вход !2 задания режима работы устройства, первый элемент И 13, второй элемент

И 14, вторую группу из и сумматоров 25

15.

Коэффициенты, свободные члены (невязки) и искомые неизвестные систем алгебраических уравнений можно представить целыми числами н позици- щ онной двоичной системе счисления р-разрядными кодами н виде: (К! Р1 h ) „О )

P-1 P-1 35 (= с Е. 2 )1

"1 " 1

1 1 с = О 1=о

К = О,!... р-1; i = (,п при условии, что на каждой итерации но всех невязках обнуляется старший разряд, т,е.

0„.:. ", ;,,„, I (2) а ноная нормализованная невязка вычисляется как

Е, 1, <-1 =, Е.1 ° (k(Здесь х, p — k-я цифра i-го неизвестного на 1-й итерации! F О

1 нормализованная -я невязка на 1-й итерации.

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

11

l ;Ä! ° Ð .! е 1М

1 =11 14 1 итерационный процесс может оказаться расходящимся (условие (2) не выполнено), что не позволит найти решение. Введение в устройство двух элементов И для организации повторений итераций с целью вычисления корректирующих цифр в результатах позволяет уменьшать ненязки по соотношению (2), а использование дополнительно п сумматоров неиэвестных— формировать их в виде

x. = х. + .х 2 (к1

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

Количестно итераций при этом возрастает (1 р) „но гарантируется уменьшение ненязок до нуля с точностью р.

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

Коэффициенты и свободные члены решаемой системы уравнений перед началом вычислений заносятся соответственно в регистры I через входы 6 и в регистры 2 через входы 7. Переход н состояние "0 1 выхода переполнения счетчика 11 может быть осуществлен следующим образом: обнулением счетчика Il через вход 12, при этом вычисляются р-разрядные неизвестные; записью в счетчик 1! значения S если необходимо вычислить лишь (р-S) цифр результатов.

3 1324О

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

5 тактовых импульсов синхронизируется запись в регистры 2 и осуществля5 ется сцвиг в регистрах 3, а каждым положительным фронтом импульса с инверсного выхода генератора 5 тактовых импульсов осуществляется сдвиг значений в регистрах 2 на один раз в !О ряд влево и увеличение значения счетчика 11 на единицу. При этом информация, поступившая в старший значащий разряд, и в знаковом разряде передается для управления соответствующими 15 группами элементов И и первым и вторым элементами И.

На протяжении всего процесса вычислений за время, которое проходит между появлением положительных фрон- Zp тов с прямого выхода генератора 5, происходит запись в регистры 2, сдвиг в регистрах 3, а.через время, равное длительности положительного импульса с прямого выхода генератора 5 такто- 25 вых импульсов, .сдвиг в регистрах 2.

За время между положительными фронтами с инверсного и прямого выходов появляется результат на выходах сумматоров 4. ЗО

После появления 1 1" на выходе переполнения счетчика 11 работа генератора тактовых импульсов блокируется и результат с выхода регистров 3 поступает на выходы 8 устройства.

При ходе решения по второму варианту на итерациях, не приведших к обнулению старших значащих разрядов хотя бы в одном сдвиговом регистре 2, блокируется сдвиг как в этих регист- 4О рах, так и в регистрах 3, а также не увеличивается значение счетчика 11, Это позволяет определить по вычисленным невязкам (1) корректирующие цифры, скоРРектиРовать значения не- 45 известных и перейти к следующей итерации, Блокировка счетного входа счетчика 11 на корректирующих шагах позволяет вычислять необходимое ко- ° личество цифр в значениях неизвестных (заданное при начальной установ- ке счетчика 11 по шине 12).

Время вычисления неизвестных системы алгебраических уравнений в первом варианте равно

tg.р,. во втором равно где t =tгу„+ tс,д„р„1 ;t. „„„ Is t дз опре деляются выбранной элементной базой, Ф о р м у л а и з о б р е т е н и я

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

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

i-ro столбца 1-й строки первой матрицы элементов И, инверсный выход регистра 1-го столбца j-й строки матрицы регистров подключен к первым информационным входам элементов И группы i-ro столбца j-й строки второй матрицы групп элементов И, информационный выход j-го сумматора первой группы подключен к информационному входу j-го сдвигового регистра первой группы и к j -му входу свободных членов устройства, выходы элементов И групп j-й строки первой матрицы групп элементов И подключены к информационным входам первой группы 1-ro сумматора первой группы, выходы элементов

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

p — разрядность невязки, подключены к информационным входам третьей группы j -го сумматора первой группы, прямой выход р-ro разряда j-го сдвигового регистра первой группы подключен к вторым входам элементов И групп

j-го столбца первой и второй матриц групп элементов И, прямой выход знакового разряда j -Io сдвигового регистра первой группы подключен к третьим входам элементов И групп j-го столбца первой матрицы групп элементов И, инверсный выход знакового разряда j-го сдвигового регистра первой группы подключен к третьим входам элементов И групп j -го столбца второй матрицы групп элементов И, первый выход генератора тактовых импуль13240

Составитель В, Смирнов

Редактор Т, Парфенова Техред И.Попович Корректор Л. Вескид

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 сов подключен к входам записи и сдвиговых регистров первой группы, выход переполнения счетчика подключен к входу останова генератора тактовых импульсов, j-й вход коэффициентов системы уравнения i-й группы устройства подключен к информационному входу регистра j-ro столбца i-й строки матрицы регистров, вход запуска устройства подключен к входу запуска re-!О ратора тактовых импульсов, о т л ич а ю ш е е с я тем, что, с целью расширения класса решаемых задач в него введены вторая группа из и сумматоров, первый и второй элементы И, 15 информационный выход )-го сдвигового регистра второй группы подключен к

j-му выходу результата устройства и к первому информационному вхрду 1-го сумматора второй группы, прямой вы- 20 ход р-го разряда j-го сдвигового регистра первой группы подключен к второму информационному входу j- ro сумматора второй группы, инверсный вы-.

35 6 ход знакового разряда j-ro сдвигового регистра первой группы подключен к знаковому входу j-го сумматора второй группы, выход j-го сумматора второй группы подключен к информационному входу j-rо сдвигового регистра второй группы, входы сдвига сдвиговых регистров второй группы подключены к выходу первого элемента И, второй выход генератора тактовых импульсов подключен к первому входу второго элемента И, выход которого подключен к входам сдвига сдвиговых регистров первой группы и к счетному входу счетчика, первый выход генератора тактовых импульсов подключен к первому входу первого элемента И, инверсные выходы р-го разряда и сдвиговых регистров первой группы подключены к входам с второго по (и+1)"й первого и второго элементов И, вход задания режима работы устройства подключен к входу начальной установки счетчика.