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

(п)648988 Свез Советник Социалистических Республик) Заявлено 25.1276 (21) 2435031/18 - 24 Г 15/3 с присоединением заявки Я оеударственныи комитет СССР ао дедам изобретений и открытий(71) Заявитель краинской СС ститут электродинамик 4) ЦИФРОВОЕ УСТФОИСТВО ДЛЯ РЕШЕНИЯ СИСТЕ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ,уравее кений,яютсяинтег- одит- произрвого1 Изобретение относится ктельной технике и может бызовано в аналого-цифровыхтельных системах.Известны устройства для решсистем алгебраических уравненикоторых система. алгебраическихнений решается путем сведениясистеме дифференциальных уравндля реализации которых составлзамкнутые цепочки из цифровыхраторов (1), Решение системы сся к понижению порядка старшейводной, поступающей на вход пеинтегратора. Недостатком этих устройств является громоздкость схем и то, что они не обеспечивают абсолютиую еходимость к решению всех задач данного класса. фНаиболее близким к изобретению по своей технической сущности является устройство для решения .систем линейных алгебраических уравнений, содержащее в блоков умножения на знак, в сумматоров строк, причем первый вход каждого из них соединен с выходом соответствующего блока умножения на знак, сумматор столбца, коммутатор, выход которого соединен с первыми входами всех бло ов ум на знак (21.Цель изобретения - повышение точности работы устройства.Достигается это тем, что в устройство введены блок управления, блок памяти, состоящий из в узлов памяти коэффициентов, узла памяти градиента и узла памяти переменных, блок адресации, в блоков хранения невязок, регистр градиента, дешифратор, счет" чик, элемент И, причем вторые входы каждого блока умножения на знак соединены с первыми выходами в блоков хранения невязок, вторые выходы которых подключены к вторым входам в сумматоров строк, первые выходы каждого 1-го из в сумматоров строк соединены с третьими входами (1+1) сумматора строк, а также с первыми входами в блоков хранения невязок, первый выход в-го сумматора строк подключен к первому входу сумматора столбца, второй выход - к пЕРвомУ входу дешифратора; первый выход блока управления соединен с первым входом узла памяти переменных, второй выход - с первым входом коммутатора и через блок адресации с входом блока памяти, третий выход - с первымвходом регистра градиента, четвертыйвыход - с первым входом узла памятиградиента, пятый выход подсоединенк четвертому входу щ-го сумматорастрок, шестой выход - к третьим входам (щ - 1) сумматоров строк и к пятому входу щ-го сумматора строкседьмой и восьмой выходы - соответственно к третьим и четвертым входамщ блоков умножения на знак, щ выходов блока управления соединены соответственно с вторыми входами щ бло Оков хранения невязок, причем первыйвыход из щ выходов блока управленияподключен к первому входу элемента И,выход коммутатора подключен к второму входу элемента И, выход которого цсоединен с первым входом счетчика,а его выход через узел памяти градиента соединен : вторым входом счет -чика; первый и второй выходы регистра градиента подключены соответственно к вторым входам узла памяти градиента и дешифратора, первый и второйвыходы дешифратора соединены соответственно с вторыми входами коммутатораи сумматора столбца выход узла пармяти градиента соединен с третьим вхо-.дом сумматора столбца, выход которогоподключен к второму входу регистраградиента, выходы щ узлов памятикоэффициентов соединены соответственно с пятыми входами щ блоков умножения на знак, вход блока управленияявляется управляющим входом устройства,На чертеже дана блок-схема устройства. ЯЦиФровое устройство для решениясистем линейных алгебраических уравнений состоит из щ блоков 1 умноженияна знак, щ сумматоров 2 строк, сумматора 3 столбца, коммутатора З, блока 5 управления, блока б памяти, содержащего щ узлов 7 памяти коэффициентов, узел 8 памяти градиента, узел9 памяти переменных, блока 10 адресации, щ блоков 11 хранения невязок,регистра 12 градиен;а, дешифратора13,. счетчика 14, элемента И 15.Устройство работает следующим образом.Решение систем линейных алгебраических уравнений вида Яи7:сх, =о,13 3где 1 = 1 - , щ;а. - коэффициенты при переменных; 55Х - переменные,можнополучить путем минимизации,.-(6 Огде Е - величина невязок.Значения переменных, обеспечивающих минимум этой Функции, будутявляться решением системы.Перед началом решения значениявеличин коэффициентов при переменных начальные значения переменных заносятся в соответствующие узлы памяти, а начальные значения невязоквычисляемые по Формулам.,- " д Х,где инцекс в круглых скобках указывает номер шага вычисленцй, заносятся в каждый из блоков 11.После поступления первого тактового импульса на соответствующихвыходах блока 5 управления появляются управляющие сигналы, разрешающие выборку из блока б памяти первого столбца коэффициентов и первойпеременной х , и сигналы, блокирую-щие поступлейие на блоки 1 сигналовс выхода коммутатора 4, разрешающиепрохождение через блоки 1 сигналовс выхода каждого из блоков 11 навход соответствующих сумматоров 2строк и блокирующие прохождение сигналов с выходов каждого блока 11 навход соответствующего сумматорастрок.После прохождения сигналами цепочки сумматоров 2, представляющих собой комбинационные сумматорь:, навыходе и-го сумматора 2 появляетсязначение первой составляющей вектораградиента минимизируемой функции наданном шаге решения, равное= зйл (в 1 ди (Е+а.Сигнал другого из выходов щ-го Сумматора(выхода знакового разряда)поступает на вход дешифратора 13,На выходе дешифратора 13 формируется значение компонент вектора пеОеменных Ь Х = ч,х-.з 1 рд(Мрл(,о). а ). Кроме того дешифратор 13 производит сравнение знака градиента минимизируемой функциина Панно ", Ан ц предыдущем ч,б шагах решения, причем сравнение знаков градиентов производится как дляотдельных компонент вектора градиента, так и для всего вектора градиента Б целом (значение ч,О поступаетна вход дешифратора 13 с выхода знакового разряда регистра 12),,Цешифратор 13 на своих выходахформирует управляющие сигналы, дающие возможность организовать следующие логические пересылки в устройстве,В случае, если знаки компоненты вектора ч,он, иЮ совпадают, то ца одном выходе дешифратора 13 Формируется сигнал, блокирующий поступление с выхода узла 8 памяти градиента сигнала ч,о на второй вход сумматора 3. Таким образом на выходе сумматора 3, представляющего собой комб 1 национный сумматор, образуется значение текущего значения величиныградиента минимизируемой функции, ранное значению градиента минимизируемой функции на данном шаге решения, т.е.е = ан:(В случае, если знаки компоненты вектора(ди р З не совпадают, то на входе сумматора 3 блокирующий сигнал отсутствует, и на входе сумматора 3 образуется значение текущего значения величины градиента минимизируемой функции, равное 1 А ч 1 чФнТаким образом, на выходе сумматора 3 формируется значение первой составляющей текущего значения ч,о 4 вектора градиента минимизируемой функции,5которое после поступления от блока 5разрешающего сигнала на вход регистра 12 переписывается в регистр 12.Знак первой составляющей вектора градиента минимизируемой функции запоминается в дешифратаре 13, а величинаИвектора градиента по следующему сигналу с выхода блока 5 заносится вузел 8 памяти градиента,Далее от блока 5 на вход блока 10и вход коммутатора 4 поступает спе- Йдующий сигнал с соответствующего выхода блока 5 и из блока б памяти второго столбца коэффициента и второйпеременной, и описанный путь прохождения сигналов повторяется. ЮПодциклы повторяются до тех пор,пока из памяти не будут последовательна выданы все столбцы кахффициентов и все переменные.После окончания 3-го падцикла в дешифраторе 13 образуются все знаки градиента на данном шаге решения и знаки текущего значения градиента.В случае неравенства всех знаков обоих векторов градиентов описанные подциклы повторяются до тех пор пока не произойдет полное или частичное совпадение их знаков. В случае совпадения знаков всех или части составляющих векторов градиентов на выходах блока 5 формируется последовательность сигналон, которая дает возможность организовать в устройстве процесс образования вектора невязок и вектора переменных следующим образом.С соответствующего выхода блока 5 управляющий сигнал поступает на вход всех блокон 1, блокируя прохождение сигнала с ныхода знакового разряда соответствующих блоков 11, разрешая прохождение сигналов с выходов блокон 11 невязок на входы соответствующих сумматоров 2 и блокируя передачи между сумматорами 2 и и-ным сумматором 2 и сумматором 3.Далее с выходов блока 5 на вход блока б памяти поступает управляющийсигнал и из блока б памяти считываются перный столбец коэффициентов ипервая переменная. Нп другой из вхоДОВ Всех блакОВ 1 Г(с;.тупай. си Налы с выхода коммутатора 4, пред(;тавляющие собой приращение первой переменной, этот же сигнал приращения переменной ь Х, поступает на один иэ входов элемента И 15.На выходах каждого из блоков 1 образуются значения приращений составляющих вектора ненязок, равные(ЬЕ =О,ЬХкоторые, поступая на входы соответствующих сумматоров 2 суммируются с предыдущими значениямй составляющих векторов невязок, накопленными в каждом из блоков 11(а (о)Далее от блока 5 поступает управляющий сигнал на вход блока 11 ненязок и на вход элемента И 15, разрешающий перепись значения ненязок в блок 11 и величины приращения первой переменной Ь Х, в счетчик 14, где образуется неличина первой переменнойХ + Х( ,которая по сигналу соответствующего выхода блока 5 заносится в узел 9.Описанный подцикл образования величин слагаемых ненязок, величии невязак и величин переменных повторяется да тех пар, пока н блоках 11 не образуется новое значение величин невязок на данном шаге решения, а в узел 9 памяти переменных не будут занесены новые значения всех переменных на данном шаге решения. На этом первый шаг вычислений заканчивается.На выходах блока 5 нновь появляется описанная выме последовательность импульсов и последовательность операций повторяется.Таким образом, на любом к-ом шаге вычислений рабата основных блоков устройства может быть описана следующими математическими зависимостями:ч,1 -" :О б(к- вектор прира 3щения минимизируемой функции, формируемый в сумматоре 3 столбца;х =х +ах(к)4 Е : . ("1 - вектор приращения невязок, формируемый на выходах каждого из блоков 1 умножения на знак.Рассмотренное устройство, как показало моделирование большого числа задач, обеспечивает абсолютную сход- ность к решению всех задач данного класса, поэтому она является более эФФективным по сравнению с известными устройствами того же назначения, что Особенно важна при использон,линирассмотренного устройства в составе гибридных вычислительных систем, так как дает возможность значительно повысить эффективность последних.Формула изобретенияЦифровое устройство для решения систем линейных алгебраических уравнений, содержащее ш блоков умножения на знак, щ сумматоров строк, причем 1 О первый вход каждого из них соединен с выходом соответствующего блока умножения на знак, сумматор столбца, коммутатор выход которого соединен с первыми входами всех блоков умножения на знак, о т л и ч а ю щ е е с я. тем, что,. с целью повышения точности, в него введены блок управления, блок памяти, состоящий из ш узлов памяти коэффициентов, узла памяти градиента и узла памяти переменных, блок адресации, щ блоков хранения невязок, регистр градиента, дешифратор, счетчик, элемент и, причем вторые входы каждого блока умножения на знак соеди" иены с первыми выходами ш блоков хра- ф нения невязок, вторые выходы которых подключены к вторым входам ш сумматоров строк, первые выходы каждого 1-го из ш сумматоров строк соединены с третьими входами (1+1) сумматора ЗО строк, а также с первыми входами щ блоков хранения невязок, первый выход щ-го сумматора строк подключен н первому входу сумматора столбцасвторой выход - к первому входу дешифратора; первый выход блока управления соединен с первым входом узла памяти переменных, второй выход - с первым входом коммутатора и через блок адресации со входом блока памяти, третий выход - с первым входом регистра градиента, четвертый выход - с первымвходом узла памяти градиента, пятыйвыход - к четвертому входу щ-го сумматора строк, шестой выход - к третьим входам (щ) сумматоров строки к пятому входу щ-го сумматора строк,седьмой и восьмой выходы - соответственно к третьим и четвертым входам щ блоков умножения на знак, щ выходов блока управления соединенысоответственно со вторыми входами щблоков хранения невязок, причем первый выход из щ выходов блока управ-.ления подключен к первому входу элемента И, выход коммутатора подключенко второму входу элемента И, выходкоторого соединен с первым входомсчетчика, выход которого через узелпамяти градиента соединен со вторымвходом счетчика, первый и второйвыходы регистра градиента подключенысоответственно ко вторым входам узлапамяти градиента и дешифратора, первый и второй выходы дешифратора сое-,динены соответственно с вторыми входами коммутатора и сумматора столбца,.выход узла памяти градиента соединенс третьим входом сумматора столбца,выход которого подключен к второмувходу регистра градиента, выходы щузлов памяти коэффициентов соединенысоответственно с пятыми входами щблоков умножения на .знак, вход блокауправления является управляющим входом устройстваИсточники информации, принятыево взимание при экспертизе:Неслуховский Н.С. Цифровые дифференциальные анализаторы, И., Ма- .шиностроение, 19 б 8,2. Эаявка 9 2124267/18-24,08.04.75, по которой принято положительное решение о выдаче авторскогосвидетельства.Составитель Н. ПалееваРедактор Е, Гончар Техоед Н БабУРка Корректор Л. ВасилинаЭакав 559/4 б Тираж 779 ПодписноеЦИИИПИ ГосУдарственного комитета СССРпо делам изобретений и открытий113035 д Москва ЖРаушская наб. д. 45Филиал ППП Патент г. Ужгород, ул. Проектная, 4