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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ он 648988

Союз Совет ник

Социалистических

Республик ф.,l"!„ д (51) М. Кл.

G 06 F 15/32 (6l) Дополнительное к авт. свид-ву (22) Заявлено 25.1276 (2l) 2435031/18 — 24 с присоединением заявки ¹ (23) Приоритет! оеударственный комитет

СССР ао делам изобретений и открытий (53) УДК 681.14 (088 ° 8) Опублнковано250279. Бюллетень № 7

Дата опубликования описания 250279 (72) Авторы изобретения

В.Д. Самойлов, А.A. Бальва и Т.Д. Марчук

Институт электродинамики AH Украинской ССР (71) Заявитель (54) Ц ИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

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

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

Недостатком этих устройств является громоздкость схем и то, что они не обеспечивают абсолютиую еходимость

-к решению всех задач данного класса.

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

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

Достигается это тем, что в устройство введены блок управления, блок памяти, состоящий из m узлов памяти коэффициентов, узла памяти градиента и узла памяти переменных, блок адресации, m блоков хранения невязок, регистр градиента, дешифратор, счетчик, элемент И, причем вторые входы каждого блока умножения на знак соединены с первыми выходами m блоков хранения невязок, вторые выходы которых подключены к вторым входам m сумматоров строк, первые выходы каждого i-го из m сумматоров строк соединены с третьими входами (1+1) сумматора строк, а также с первыми входами m блоков хранения невязок, первый выход m-ro сумматора строк подключен к первому входу сумматора столбца, второй выход — к пЕРвомУ входу дешифратора; первый выход блока управления соединен с первым входом узла памяти переменных, второй выход — с первым входом коммутатора и через блок адресации с входом блока памяти, третий выход — с первым входом регистра градиента, четвертый выход — c первым входом узла памяти градиента, пятый выход подсоединен к четвертому входу m-го сумматора строк, шестой выход — к третьим входам (m†- 1) сумматоров строк и к пя-= тому входу m-го сумматора строк седьмой и восьмой выходы — соответственно к третьим и четвертым входам т блокОв умножения на знак, ю выходов блока управления соединены соответственно с вторыми входами в бло- 19 ков хранения невязок, причем первый выход из m выходов блока управления подключен к первому входу элемента И, выход коммутатора подключен к второму входу элемента И, выход которого д соединен с первым входом счетчика, а его выход через узел памяти градиента соединен = вторым входом счет.— чика1 первый и второй выходы регистра градиента подключены соответственно к вторым входам узла памяти градиента и дешифратора, первый и второй выходы дешифратора соединены соответственно с вторыми входами коммутатора и сумматора столбца зыход узла паФ мяти градиента соединен с третьим вхо- - дом сумматора столбца, выход которого подключен к втОрОму входу ре "HcTpa градиента, выходы т узлов памяти коэффициентов соединены соответственно с пятыми входами щ блоков умноже- 36 ния на знак, вход блока управления является управляющим входом устройства.

На чертеже дана блок-схема усттзойстна. Я

Цифровое устройство для решения систем линейных алгебраических уравнений состоит из тп блоков 1 умножения на знак, ю сумматоров 2 строк, сумматора 3 столбца, коммутатора 4, бло- +3 ка 5 управления, блока б памяти, содержащего m узлов 7 памяти коэффициентов, узел 8 памяти градиента, узел

9 памяти переменных, блока 10 адресации, т блоков 11 хранения невязок, регистра 12 градиен;а, дешифратора

13,. счетчика 14, эле, Н 15.

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

Решение систем линейных алгебраических уравнений вида 9) и

Х a" x9=Q

11 13 3 где i = 1 —, m; а. — коэффициенты при переменим; 3

Х„ — переменные, можно получить путем минимизации . вспомогательной функции

/О= Z (81!)

1: 6О где Е„ — величина невязок.

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

Перед началом решения значения

BeJIH÷èH коэффициентов при переменных 65 начали. -1ЫЕ Значеиия пЕРеменных носятся в соответствующие узлы памяти, а начальные значения невязок

> вычисляемые по формулам (с)

<О) ", (О) —. " " с(„Х .

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

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

После прохождения сигналами цепочки сумматоров 2, представляющих собой комбинационные сумматорь:, на выходе щ-го ".óììàòîðà 2 появляется значение первой составляющей вектора градиента минимизируемой функции на данном шаге решения, равное (11 и1 (о)

9н -" 1Ä L1 3

1-.1 где 1 = ) —; m

J ) — 1 —: n (O1

= з14" (в1Д t (Г„+а )).

Сигнал другого из выходов т-го Сумматора ? (выхода знакового разряда) поступает на вход дешифратора 13.

На выходе дешифратора 13 формируется значение компонент вектора пере."1е нных Г1 Х = v Х)1

1 ) У 1. З где vp 2

-"зуд(Мрл(а ) - О ). Кроме того дешифра Ор ." 3 производит сравнение знака градиента минимизируемой функции 1а данно ™,,Г н и предыдущем чФ шагах решения, причем сравнение знаков градиентов производится как для отдельных компонент вектора градиента, так и для всего вектора градиента в целом (значение,о поступает на вход дешифратора 13 с выхода знакового разряда регистра 12). ,Цешифратор 13 на своих выходах формирует управляющие сигналы, дающие возможность организовать следующие логические пересылки в устройстве.

В случае, если знаки компоненты

ВЕКтОРаЧ,Он; И Х СОВПаДаЮт, та на одном выходе дешифратора 13 формируется сигнал, блокирующий поступление с выхода узла 8 памяти градиента сигнала ч,о на вгорой вход сумматора 3. Таким образом на выходе сумматора 3, представляющего собой комб национный сумматор, образуется значение текущего значения величины

648988 градиен=а минимиэируемой функции, ранное значению градиента минимизируемой функции на данном шаге решения, т.е. vе = яа

Н1.

В случае, если знаки компоненты вектора чд.„и чЯ не совпадают, то на входе сумматора 3 блокирующий сигнал отсутствует, и на входе сумматора 3 образуется значение текущего значения величины градиента минимизируемой функции, равное 143 ч "1

Таким образом, на выходе сумматора 3 формируется значение первой составляющей текущего значения ч а вектора градиента минимизируемой функции, которое после поступления от блока 5 разрешающего сигнала на вход регистра 12 переписывается в регистр 12.

Знак первой составляющей вектора градиента минимизируемой функции запоминается в дешифратаре 13, а величина

И вектора градиента по следующему сигналу с выхода блока 5 заносится в узел 8 памяти градиента.

Далее от блока 5 на вход блока 10 и вход коммутатора 4 поступает спе- 25 дующий сигнал с соответстнующегG выхода блока 5 и из блока б памяти второго столбца коэффициента и нторой переменной, и описанный путь прохождения сигналов повторяется. 30

Подциклы повторяются до тех пор, пока иэ памяти не будут последовательна выданы все столбцы кахффициентов и все переменные.

После окончания j-го падцикла в дешифраторе 13 образуются все знаки градиента на данном шаге решения и знаки текущего значения градиента.

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

С соответствующего выхода блока 5 управляющий сигнал поступает на вход всех блокон 1, блокируя прохождение сигнала с ныхода знакового разряда соответствующих блоков 11, разрешая прохождение сигналов с выходов блокон 11 невязок на входы соответствующих сумматоров 2 и блокируя передачи между сумматорами 2 и m-ным сумматором 2 и сумматором 3.

Далее с выходов блока 5 на вход блока б памяти поступает управляющий сигнал и из блока 6 памяти считываются перный столбец коэффициентов и первая переменная. Нп другой из вхоДОВ Bceõ блакОн 1 ii<: 1/ аю. <и. налы с выхода коммутатора 4, пред(.тавляющие собой приращение первой переменной, этот же сигнал приращения переменной ь Х 1 поступает на один иэ входов элемента И 15.

На выходах каждого из блоков 1 образуются значения приращений составляющих вектора ненязок, равные (1) (i) а Е „=a,„ üõ„ которые, поступая на входы соответствующих сумматоров 2 суммируются с предыдущими значениямй составляющих векторов невязок, накопленными в каждом из блоков 11 (а (о)

1- 1 E1

Далее от блока 5 поступает управляющий сигнал на вход блока 11 ненязок и на вход элемента И 15, разрешающий перепись значения ненязок в блок 11 и величины приращения первой переменной Х1 в счетчик 14, где образуется неличина первой переменной

Х „ + Х„,которая по сигналу соответствующего выхода блока 5 заносится в узел 9.

Описанный подцикл образования величин слагаемых ненязок, величии невязак и величин переменных повторяется да тех пар, пока н блоках 11 не образуется новое значение величин невязок на данном шаге решения, а в узел 9 памяти переменных не будут занесены новые значения всех переменных на данном шаге решения. На этом первый шаг вычислений заканчивается.

На выходах блока 5 нновь появляется описанная ныше последовательность импульсов и последовательность операций повторяется.

Таким образом, на любом к-оМ шаге вычислений рабата основных блоков устройства может быть описана следующими математическими зависимостями: вектор прираО11 1

1„1 —— щения минимизируемой функции, формируемый в сумматоре 3 столбца;

Х = Х +< К (к) — вектор переменных, формируемый,в счетчике 14; вектор невязок, формируемый в сумматорах 2 строк; ((

Рассмотренное устройство, как показало моделирование большого числа задач, обеспечивает абсолютную сходность к решению всех задач данного класса, поэтому она является более эффективным по сравнению с известны:ли устройствами того же назначения, ч "o ocooåíío важна при исполь зон,.(иии б48988 рассмотренного устройства в составе гибридных вычислительных систем, так как дает возможность значительно повысить эффективность последних.

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

Цифровое устройство для решения систем линейных алгебраических уравнений, содержащее ж блоков умножения на знак, m сумматоров строк, причем ц) первый вход каждого иэ них соединен с выходом соответствующего блока умножения на знак, сумматор столбца, коммутатор„ выход которого соединен с первыми входами всех блоков умножения на знак, о т л и ч а ю щ е е с я. тем, что,. с целью повышения точности, в него введены блок управления, блок памяти, состоящий из в узлов памяти коэффициентов, узла памяти градиента и узла памяти переменных, блок адресации, m блоков хранения невязок, регистр градиента, дешифратор, счетчик, элемент и, причем вторые входы каждого блока умножения на знак соеди" иены с первыми выходами m блоков хра- + иения невязок, вторые выходы которых подключены к вторым входам m сумматоров строк, первые выходы каждого

i-ro из m сумматоров строк соединены с третьими входами (1+1) сумматора ЗО строк, а также с первыми входами m блоков хранения невязок, первый вы« ход ш-го сумматора строк подключен н первому входу сумматора столбца, второй выход — к первому входу дешифратора; Э » первый выход блока управления соединен с первым входом узла памяти переменных, второй выход — с первым входом коммутатора и через блок адресации со входом блока памяти, третий „О выход — с первым входом регистра градиента, четвертый выход — с первым входом узла памяти градиента, пятый выход — к четвертому входу m-го сумматора строк, шестой выход — к третьим входам (ш-1) сумматоров строк и к пятому входу m-го сумматора строк, седьмой и восьмой выходы — соответственно к третьим и четвертым входам m блоков умножения на знак, m выходов блока управления соединены соответственно со вторыми входами m блоков хранения невязок, причем первый выход из m выходов блока управ-. ления подключен к первому входу элемента И, выход коммутатора подключен ко второму входу элемента И, выход которого соединен с первым входом счетчика, выход которого через узел памяти градиента соединен со вторым входом счетчика, первый и второй выходы регистра градиента подключены соответственно ко вторым входам узла памяти градиента и дешифратора, первый и второй выходы дешифратора соединены соответственно с вторыми входами коммутатора и сумматора столбца,. выход узла памяти градиента соединен с третьим входом сумматора столбца, выход которого подключен к второму входу регистра градиента, выходы m узлов памяти коэффициентов соединены соответственно с пятыми входами m блоков умножения на .знак, вход блока управления является управляющим входом устройства.

Источники информации, принятые во внимание при экспертизе:

Неслуховский Н.С. Цифровые дифференциальные анализаторы, И., Ма- . шиностроение, 19б8.

2. Эаявка Р 2124267/18-24, 08.04.75, по которой принято положительное решение о выдаче авторского свидетельства.

648988

Составитель Н. Палеева

Редактор Е.Гончар Техоед И. 8>© > Корректор Л. Василина

Эакав 559/46 Тираж 779 Подписное

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

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

Филиал ППП Патент,, г. Ужгород, ул. Проектная, 4