Устройство для решения систем линейных алгебраических уравнений Советский патент 1985 года по МПК G06G7/34 

мирования пороговых напряжений, прямые выходы которых подключены соответственно к m входам четвертого коммутатора, п выходов которого соединены соответственно с m выходами второго коммутатора и с прямыми входами m компараторов, прямые выходы которых подключены соответственно к суммирующим входам реверсивных счетчиков m аналого-цифровых преобразователей и к первым тактовым входам формирователей прямоугольных импульсов, инверсные выходы компараторов соединены соответственно с вычитающими входами реверсивных счетчиков таналого-цифровых преобразователей и к вторым тактовым входам m формирователей пpямoyгoльJ ыx импульсов, первый выход блока синхронизации ; подключен к входам сбросатформирорователей прямоугольных импульсов, второй выход блока синхронизации непосредственно подключен к управля ющим входам третьего и четвертого коммутаторов и через инвертор - к управляющим входам первого и второго

коммутатора и к управляющим входам ключей m аналого-цифровых преобразователей, третий выход блока синхронизации соединен со стробирующими входами W формирователей прямоугольных импульсов, выходы которых подключены к входу формирователя длительности импульса и к первому входу элемента И соответствующего из Иг) аналого-цифровых преобразователей, выходы элементов И которых соединены с входами задания кода цифроаналоговых преобразователей соответствующих столбцов матрицы, вход задания погрешности постоянных коэффициентов устройства подключен к входам задания кода m блоков формирования пороговых напряжений в каждом из таналого-цифровых преобразователей, ВЫХОД ключа через преобразователь напряжения в код соединен с установочным входом реверсивного счетчика,выходи входсбро которого соединенысоответственно с вторым входом элемента И и с выходом фомирователя длительностиимпульса.

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее блок управления, блок вычитателей, блок формирования невязки решения, выполненный в виде m вычитателей, выходы которых подключены к первой группе входов блока суммирующих интеграторов, группа выходов которого соединена с первой группой входов блока вычитателей, вторая группа входов которого подключена к второй группе входов блока суммирующих интеграторов и является входом задания минимальной нормы решения устройства, отличающееся тем, что, с целью повьпцения точности, в него введены блок моделирования неизвестных уравнения выполненный в виде т ai ало го-цифровых преобразователей, каждый из которых состоит из ключа, преобразователя напряжения в код.реверсивного счетчика элемента И и формирователя длительности импульса, блок моделирования матрицы членов уравнения, выполненный в виде матрицы цифроаналоговых преобразователей, и блок сумматоров, причем блок управления содержит преобразователь код-напряжение, m блоков формирования пороговых напряжений, четыре коммутатора, m компараторов, m формирователей прямоугольных импульсов инвертор и блок синхронизации, вход запуска которого является входом запуска устройства, m групп входов задания постоянных коэффициентов уравнений которого подключены к соответствующим группам входов задания опорного сигнала цифроаналоговых преобразователей строк матрицы, группы выходов цифроаналоговых преобразователей строк матрицы соединены с соответствующей группой входов блока сумматоров m выходов которого подключены к соответствующим инфор(Л мационным входам ключей m аналогоцифровых преобразователей и к первым с входам соответствующих 1Т) вычитателей, вторые входы которых являются входами задания свободных членов уравнения устройства, входы задания отри- цательного и положительного опор00 ных напряжений которого подключены vj соответственно к информационным входам nepBorq и второго коммутато н| ров, вход задания погрешности свободного члена устройства соединен с входом преобразователя код-напряжение, выход которого подключен к информационным входам m блоков формирования пороговых напряжений, инверсные выходы которых соединены с ш входами третьего коммутатора m выходов которого соединены соответственно с m выходами первого коммутатора и инверсными входами m компараторов, in выходов блока вычитателей соединены соответственно с опорными входами m блоков фор

1

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

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

На фиг.1-представлена блок-схема устройства для решения систем линейных алгебраических уравнений; на фиг.2 - временные диаграммы, поясняющие работу блока управления.

.

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

Блок 3 управления содержит блок 11 формирования пороговых напряжений, коммутаторы 12, компараторы 13, формирователи 14 прямоугольных импульсов, преобразователь 15 код-напряжение, блок 16 синхронизации, инвертор 17. Блок 11 содержит цифроаналоговый преобразователь 18, сумматор 19 и инвертор 20. Формирователь 14 импульсов содержит два триггера 21, элемент ИЛИ 22 и элемент И 23. Аналого-цифровой преобразователь 8 содержит ключ 24, преобразователь 25 напряжения в код, реверсивный счетчик 26, элемент И 27 к формирователь 28 длительности импульса.

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

g«x.g.., (О 3 В1,(7,Х, + ...2„.х„ ii-, rv,,X,..., причем n m. Краткая запись системы уравнени G x(t) F. Устройство работает следукнциг образом. Устройство состоит из двух основных цепей преобразования сигналов . Первая цепь включает матрицу ДАЛ 6, блок 9 сумматоров Ю, А1Щ 8, вычитателей 1, компараторов 13 и представляет собой цепь уравI новешивания, осуществляющей решение системы уравнений G -Х (t) - F е, (2) где G - матрица постоянных коэффициентов; X(t) - матрица неизвестны F - матрицы свободных членов; Е величина невязки. Величина невязки f подается на блок 13 компараторов. Решение дост гается при таких величинах неизвестных X(t), при которых величина невязки сводится к минимуму. Вторая цепь содержит блок 4 инт раторов, блок 2 вычитателей, блоки 11, коммутаторы 12 и служит для получения пороговых уровней Unop - iiiXiW- oii, где j и - коэффициенты, определяемые из условий и uFi Л G и & F - погрешности определени коэффициентов g;; и f; ; Хд - минимальная норма решения,- определяе мая дискретностью АЦП и уровнем щу мов. Пороговые уровни + подают ся на вторые входы компараторов 13 1$оторые предназначены для оценки величины невязки и коррекции, исходя из этого - значенш неизвес ных Х-, записанньк в реверсивных счетчиках 26. Приближение . к решению исходной системы уравнений (1) строится на основе последовательных итераций. Каждый шаг итерации (цикла) процес уравновешивания раз/ еляется на два подцикла. Работу каждого подцикла определ ют управляющие сигналы f ц и f (фиг.2).блока 16, которые управляют четырьмя коммутаторами 12, разр 574 тающими прохождение сигналов пороговых уровней + Vflop или напряжений запирания + V,(,,, на компараторы 13. Причем, если два коммутатора 12 от1$рыты и пропускают, например, сигналы +Vnop. с блоков 11, то в это время вторая пара коммутаторов 12 закрыта и не пропускает + ,д„ , и наоборот. В первом подцикле сигнал управления ч пропускает через два коммутатора 12 запирающее напряжение + V«4 от внешнего источника, прекращая, тем самым, работу компарато- ра 13. В это время в матрице ЦАП 6 производится перемножение неизвестных Х| , задаваемых с АЦП 8, с величинами сигналов g и устанавливаются величины невязки (t) - F по каждой строке (1), которые подаются на компараторы 13. В это же время во второй цепи осуществляется получение с помощью интеграторов блока 4 и блока 2 величин сигналов, пропорциональных норме решения // X (t) - Х, //, а затем формирование с блоках 11 сигналов, пропорциональных j //(t) -.Хд//+,т.е. формирование сигналов пороговых уровней (З). Во втором подцикле при воздействии управляющего сигнала ц (фиг.2) вторая пара коммутаторов 12 пропускает сигналы пороговых уровней (3) на компараторы 13, которые срабатывают, если величина невязки больше пороговых уровней, и корректируют значения неизвестных X, записанных в реверсивном счетчике 26 АЦП 8. Решение системы уравнений (1) достигается, когда величина невязки Е (2) меньше задаваемых пороговых уровней (3), при выполнении условия: | Qxtt -FlHSllxltVXolh. (4) Рассмотрим работу первого подцикла преобразования сигналов, которое происходит при действии положительного уровня сигнала f (фиг.2). Вначале по сигналу f (фиг,2), оответствующему переднему фронту сигнала ц, производится перепись кодов реверсивных счетчиков 26 каждого АЦП 8 через элементы И 27 в соответствующие ЦАП 6. Эти коды представляют собой эквиваленты неизвестных Xj, Х,..., Х системы уравнени (1), В качестве опорных напряжений 1Щ1 6 служат аналоговые сигналы (постоянные напряжения), представля ющие собой постоянные коэффициенты системы линейных алгебраических уравнений (1), которые подаются через группу п X m входов блока 5. ЦАП .6 выполняют роль перемножителей коэффициентов на цифровые эквиваленты неизвестных Х, Х,..., Х задаваемые блоком 7. Результаты перемножения суммируются по каждой строке на сумматорах 10 блока 9 и полученные суммы поступают на выч татели 1 и на блок 7. В вычитателях 1 осуществляется вычитание сигналов свободных членов f уравнений (1) и выходных сигналов соответствзпощих сумматоров 10.. Образуемые сигналы невязки G X(t) - F поступают на компараторы 13, содержащие компаратор с плюсовым К и компаратор с минусовьм К значением порога. В блоке 7 входные сигналы поступают на АЦП 8, где, пройдя через ключ 24, оцениваются по величине преобразователем 25. Установленные коды сигналов по каждой сумме зап сываются в реверсивные счетчики 26 каждого АЦП 8. Причем ключ 24 упра ляется сигналом fу, а реверсивный счетчик 26 устанавливается в нулевое состояние сигналом-f (фиг.2), сформированным формирователем 28 по заднему фронту сигнала переписи В первом подцикле компараторы К компараторов 13 заперты бол шим уровнем сигналов - соответственно, поступающих через пару коммутаторов 12 (ключи управляются сигналом ц). В первом подцикле работы производится также формирование сигналов пороговых уровней. Для этого выходные сигналы вычитателей 1 пода ются на блок 4 интеграторов, где выполняется интегрирование сигналов невязки GX(t) - F, и, далее в блоке 2 формируются сигналы нормы решения //X(t) - , поступающие на ПАИ 18 блоков 11. Блок 3 управления содержит П1 блоков 11. Входные сигналы //X(t) - Хд// служат опорными напряжениями ПАП 18, с помощью которых вьтолняется операция умножения этих сигналов на входной код j устройства. Таким образом на выходе ЦАП 18 получаем сигнал, определяемый выражением: il(xai)-x,|i.; Этот сигнал (5) подается на сумматор 19 блока 11 для суммирования с сигналом, поступакнцим с ЦАП 15. Аналоговый сигнал в формуле (4) вырабатывается ЦАП 15 на основе кода , подаваемого на вход предлагаемого устройства. На выходе сумматора 19 имеем illXi{t)-x,ih а на выходах инверторов 20 будет сигнал (6) обратной полярности.Таким образом выходные сигналы блоков 11 являются пороговыми напряжениями (3) и подаются на два коммутатора 12. Управление работой устройства осур5ествляется в два подцикла сигналами ц и блока 16 и fjj инвертора 17 с помрщью четырех коммутаторов 12, выполняющих коммутацию напряжений пороговых уровней: два коммутатора 12 - для передачи пороговых уровней - У„„р и + i поступающих с блоков 11, а два других коммутатора 12 - для передачи напряжений запирания - Vj jH+V- n , поступающих с входов устройства. Длительность первого и второго подциклов определяется требуемым временем для выполнения операции интегрирования, цифроаналогового и аналого-цифрового преобразования сигналов, а также временем срабатывания компараторов и коррекции кодов реверсивных счетчиков соответственно.Причем время второго подцикла значительно меньше времени первого подцикла (фиг.2). Во втором подцикле работы предлагаемого устройства сигнал управления f разрешает прохождение пороговых уровней - У„ к + V„ с блоков 11 через два коммутатора 12 на компараторы 13 (конкретно на К и К ). В это время на вторых входах компараторов К и К присутствует сигнал невязки GX(t) - F. В зависимости от полярности сигнала невязки срабатывает компаратор

7

К или К. Срабатьшание происходит при превышении сигналом невязки заданного порогового уровня +Vnop

или величине сигнала невязки ниже порогового уровня «При этом с выхода сработавшего компаратора 13 следует импульс, корректирующш значения неизвестного Xj, записанного в реверсивном счетчике 26 соответствующего АЦП 8, т.е. уменьшает или увеличивает величину кода Х. Таким образом, компараторы являются чувствительным органом (регулятором) цепи уравновешивания и служат для периодического уточнения значений . Они определяют необходимость коррекции Х-, ее знак и вьщают корректирующие (приводящие к равновесию системы) импульсы.

На фиг.2 приведены сигналь

тг тг tr

(of f Vx пор V пор показывающие , как с каждым Диклом уравновешивания снижаются задаваеко,1 пороговые уровни.

В течение второго подцикла работы устройства выходные сигналы компараторов подаются также на w формирователей 14. При этом сигнал срабатывания одного из компараторов 13 вызывает изменение состояния I связанного с ним триггера 21 формирователя 14 для управления АЦП 8. Выходной сигнал сработавшего триггера 21, пройдя через элемент ШШ 22 разрешает прохождение сигнала переписи f.j| с блока 16 через элемент И 23 на соответствующий АЦП 8 блока 7 (сигнал переписи поступает на элемент И 23 в первом подцикле работы устройства (фиг.2). Статические триггеры 21 возвращают578

ся в исходное состояние сигналом ЧП.о. (фиг.2) блока 16, т.е. в первом подцикле после прохождения сигнала переписи через элемент И 23.

Таким образом, один цикл работы устройства закончен.

Если не сработал ни один из компараторов К и К какого-либо из компараторов 13, то, следовательно, код соответствующего реверсивного счетчика 26 равен значению искомого неизвестного. Связанные с этими компараторами триггеры 21 не опро-. кинутся и, тем самым, -они запретят прохождение импульсов переписи f.

через элемент И 23. t

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

Окончание решения системы линейных алгебраических уравнений наступит при условии (4), т.е. когда в процессе уравновешивания величина невязки GX(t) - F по каждой строке системы (1) будет меньше задаваемого порогового уровня (3). При этом компараторы 13 не будут срабатывать коррекция отсутствует, система будет находиться в .равновесии, а установившиеся коды неизвестных Х в реверсивных счетчиках 26 А1Щ 8 являются искомыми неизвестными Х°, Хг,..., Х°, т.е. определяют результат решения системы линейных алгебраических уравнений. Кроме того, на выходе блока 4 интеграторов имеет аналоговые значения вектора корней Х, Х°, .., Х°.