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

 

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

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

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

РЕСОУБЛИН ((9) . (11) (Sl)4 G 06 G 7/34

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

00 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К ABTOPCHOIVlY СВИДЕТЕЛЬСТБУ д,, „Q

kgö", l (21) 3741306/24-24 (22) 15.05.84 (46) 23. 10.85. Бюл. ¹ 39 (72) Б,В. Семагин (53) 681.333(088.8). (56) Авторское свидетельство СССР № 579633, кл. С 06 G 7/34.

Авторское свидетельство СССР № 612253, кл, G 06 Г 7/34. цательного и положительного опорных напряжений которого подключены соответственно к информационным, входам первого и второго коммутаторов, вход задания погрешности свободного члена устройства соединен с входом преобразователя код-напряжение, выход которого подключен к информационным входам е блоков формирования пороговых напряжений, инверсные выходы которых соединены с В входами третьего коммутатора, (и выходов которого соединены соответственно с rn выходами первого коммутатора и инверсными входами и компараторов, rn выходов блока вычитателей соединены соответственно с опорными входами rn блоков фор(54)(57) УстРойство для Решения сисTEM ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНГНИЙ, содержащее блок управления, блок вычитателей, блок формирования невязки решения, выполненный в виде

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

N аналого-цифровых преобразователей, каждый из которых состоит из ключа, преобразователя напряжения в код реверсивного счетчика, элемента

Ф

И и формирователя длительности импульса, блок моделирования матрицы членов уравнения, выполненный в вице матрицы цифроаналоговых преобразователей, и блок сумматоров, причем блок управления содержит преобразователь код-напряжение, m блоков формирования пороговых напряжений, четыре коммутатора, m компараторов, п формирователей прямоугольных импульсов, инвертор и блок синхронизации, вход запуска которого является входом запуска устройства, Ю групп входов задания постоянных коэффициентов уравнений которого подключены к соответствующим группам входов задания опорного сигнала цифроаналоговых преобразователей строк матрицы, группы выходов цифроаналоговых преобразователей строк матрицы соединены с соответствующей группой входов блока сумматоров m выходов которого подключены к соответствующим информационным входам ключей и) аналогоцифровых преобразователей и к первым входам соответствующих ф вычитателей, вторые входы которых являются входами задания свободных членов уравнения устройства, входы задания отри7157

118 мирования пороговых напряжений, прямые выходы которых подключены соответственно к rn входам четвертого коммутатора, в выходов которого соединены соответственно с rn выходами второго коммутатора и с прямыми входами rnêoìïàðàòîðîâ, прямые выходы которых подключены соответственно к суммирующим входам реверсивных счетчиков а аналого-цифровых преобразователей и к первым тактовым входам rnid формирователей прямоугольных импульсов,инверсные выходы компараторов сое-, динены соответственно с вычитающими

1 входами реверсивных счетчиков rn аналого-цифровых преобразователей и к вторым тактовым входам m формирователей прямоугольных импульсов, первый выход блока синхронизации подключен к входам сбросавформирорователей прямоугольных импульсов, <С второй выход блока синхронизации непосредственно подключен к управляющим входам третьего и четвертого коммутаторов и через инвертор — к управляющим входам первого и второго коммутатора и к управляющим входам ключей п1аналого-цифровых преобразователей, третий выход блока синхронизации соединен со стробирующими входами rn формирователей прямоугольных импульсов, выходы которых подключены к входу формирователя . длительности импульса и к первому входу элемента И соответствующего из Ф аналого-цифровых преобразователей, выходы элементов И которых соединены с входами задания кода цифроаналоговых преобразователей соответствующих столбцов матрицы, вход задания погрешности постоянных коэффициентов устройства подключен к входам задания кода п блоков формирования пороговых напряжений в каждом из п1аналого-цифровых преобразователей, выход ключа через преобразователь напряжения в код соединен с установочным входом реверсивного счетчика, выход и вход сброса которого соединенысоответственно с вторым входом элемента И и с выходом формирователя длительностиимпульса.

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

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

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

Устройство содержит блок формирования невязки решения, выполненный в виде tn вычитателей 1, блок 2 вычитателей, блок 3 управления, блок

4 суммирующих интеграторов, блок 5 моделирования матрицы членов уравнения, выполненный в виде матрицы цифроаналоговых преобразователей б, блок 7 моделирования неизвестных уравнения, выполненный в виде Ж ана2 лого-цифровых преобразователей 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 длительности импульса.

Предлагаемое устройство автоматически моделирует и решает систему линейных алгебраических уравнений вида: (нх, ф„х, „. i(,„x„= i,;

1187157

В к 62 2 " 420 xn - )

6,х,Ф6„, 2+".+к „х„= э причем n = m.

Краткая запись системы уравнений

С х() = F.

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

Устройство состоит из двух основных цепей преобразования сигналов.

Первая цепь включает матрицу .ЦАП 6, блок 9 сумматоров 10, АЦП 8, вычитателей 1, компараторов

13 и представляет собой цепь уравновешивания, осуществляющей решение системы уравнений

С Х (e) — F -6, (2) где G — - матрица постоянных коэффициентов; X(t) — матрица неизвестных;

F — матрицы свободных членов; Я— величина невязки.

Величина невязки Я подается на блок 13 компараторов. Решение достигается при таких величинах неизвестных X(t), при которых величина невязки Я сводится к минимуму.

Вторая цепь содержит блок 4 интегг раторов, блок 2 вычитателей, блоки

11, коммутаторы 12 и служит для получения пороговых уровней

IIMð (ЗПх 1 >*II+$$ > где j u g — коэффициенты, определяемые из условийЕС j и дР g

Ь С и Ь Г вЂ” погрешности определения коэффициентов я„ и f; ; Х„ - минимальная норма решения, определяемая дискретностью AIJII и уровнем шумов.

Пороговые уровни + V„»> подаются на вторые входы компараторов 13, которые предназначены для оценки величины невязки Я и коррекции, исходя из этого — значений неизвестных Х записанных в реверсивных

У счетчиках 26.

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

Каждый шаг итерации (цикла) процесса уравновешивания разделяется на два подцикла.

Работу каждого подцикла определяют управляющие сигналы f „ и ft (фиг,2) .блока 16, которые управляют четырьмя коммутаторами 12, разре. татора 12 открыты и пропускают . например сигналы +Ч»ор- с блоков 11, то в это время вторая пара коммутаторов 12 закрыта и не пропускает " + V „, ", и наоборот.

10 - В первом подцикле сигнал управ15

45

50 происходит при действии ноложительного уровня сигнала f< (фиг.2).

Вначале по сигналу f< (Лиг.2), сигнала f производится перепись

55 кодов реверсивных счетчиков 26 каж25

40 шающими прохождение сигналов пороговых уровней + Ч» » или напряжений запирания + V> » на компараторы 13. Причем, если два коммуления fö пропускает через два коммутатора 12 запирающее напряжение

+ Ч. „ от внешнего источника, прекращая, тем самым, работу компаратора 13. В это время в матрице ЦАП 6 производится перемножение неизвестных Х, задаваемых с АЦП 8, с величинами сигналов 8" и устанавлива 5 ются величины невязки G ° X(t) - F по каждой строке (I), которые подаются на компараторы 13.

В это же время во второй цепи осуществляется получение с помощью интеграторов блока 4 и блока 2 величин сигналов, пропорциональных норме решения // Х (e) — Х //, а затем формирование с блоках 11 сигналов, пропорциональных j //(t) — Х // + (, т.е. формирование сигналов пороговых уровней (3).

Во втором подцикле при воздействии управляющего сигнала Е„ (фиг.2) вторая пара коммутаторов 12 пропускает сигналы пороговых уровней (3) на компараторы 13, которые срабатывают, если величина невязки Е больше пороговых уровней, и корректируют значения неизвестных Х;, записанных в реверсивном счетчике

26 АЦП 8.

Решение системы уравнений (1) достигается, когда величина невязки E (2) меньше задаваемых пороговых уровней (3), при выполнении условия:

Рассмотрим работу первого подцикла преобразования сигналов, которое соответствующему переднему фронту даго АЦП 8 через элементы И 27 в соответствующие ЦАП 6, Эти коды прелставляют собой эквиваленты неизвест1187157 ных Х, Х,..., Х системы уравнений (1). В качестве опорных напряжений

ЦАП 6 служат аналоговые сигналы (постоянные напряжения), представляющие собой постоянные коэффициенты

g„> системы линейных алгебраических уравнений (1), которые подаются через группу и х m входов блока 5.

ЦАП 6 выполняют роль перемножителей 10 коэффициентов я; на цифровые эквиваленты неизвестных Х, Х .. ., Х„, задаваемые блоком 7. Результаты перемножения суммируются по каждой строке на сумматорах 10 блока 9 15 и полученные суммы поступают на вычиI татели 1 и на блок 7.

В вычитателях 1 осуществляется вычитание сигналов свободных членов Ю; уравнений (1) и выходных 2О сигналов соответствующих сумматоров 10.. Образуемые сигналы невязки С X(t) - F поступают на компараторы 13, содержащие компаратор с плюсовым К и компаратор с мину- 25 совым К значением порога.

В блоке 7 входные сигналы поступают на АЦП 8, где, пройдя через ключ 24, оцениваются по величине преобразователем 25. Установленные коды сигналов по каждой сумме записываются в реверсивные счетчики 26 каждого АЦП 8. Причем ключ 24 управляется сигналом f > а реверсивный счетчик 26 устанавливается в нулевое состояние сигналом Х,> (фиг.2), сформированным формирователем 28 по заднему фронту сигнала переписи

Г! °

В первом подцикле KQMIIBpGTopbl 4p

K M K компараторов 13 заперты больII II шим уровнем сигналов +Ч дд и — V зц, соответственно, поступающих через пару коммутаторов 12 (ключи управляются сигналом йц). 45

В первом подцикле работы производится также формирование сигналов пороговых уровней. Для этого выходные сигналы вычитателей 1 подаются на блок 4 интеграторов, где выполняется интегрирование сигналов невязки GX(t) - F, и, далее в блоке 2 формируются сигналы нормы решения //X(t) — Х //, поступающие на ЦАП 18 блоков 11. Блок 3 управления содержит teal блоков 11, Входные сигналы //Х;(С) — Х // служат опорными напряжениями ЦАП 18, с помощью которых выполняется операция умножения этих сигналов на входной код j устройства. Таким образом на выходе ЦАП 18 получаем сигнал, определяемый выражением: l(x;()-x, (. (5)

Этот сигнал (5) подается на сумматор 19 блока 11 для сУммирования с сигналом, поступающим с ЦАП 15.

Аналоговый сигнал в формуле (4) вырабатывается ЦАП 15 на основе кода (, подаваемого на вход предлагаемого устройства.

На выходе сумматора 19 имеем а на выходах инверторов 20 будет сигнал (6) обратной полярности.Таким образом выходные сигналы блоков

11 являются пороговыми напряжениями (3) и подаются на два коммутатора 12.

Управление работой устройства осуществляется в два подцикла сигналами fö и блока 16 и К„ инвартора

17 с помощью четырех коммутаторов

12, выполняющих коммутацию напряжений пороговых уровней: два коммутатора 12 — для передачи пороговых

tl и и 1Л. уров неи — V p„F H + Ч со (. поступающих с блоков 11, а два других коммутатора 12 — для передачи напряжений запирания — Ч„„и + Ч „ поступающих с входов устройства. Длительность первого и второго подциклов определяется требуемым временем для выполнения операции интегрирования, цифроаналогового и аналого-цифрового преобразования сигналов, а также временем срабатывания компараторов и коррекции кодов реверсивных счетчиков соответственно. Причем время вто" рого подцикла значительно меньше времени первого подцикла (фиг.2).

Во втором подцикле работы предлагаемого устройства сигнал управления f< разрешает прохождение пороговых уровней — Ч„ и + V„ с блоков 11 через два коммутатора 12 на компараторы 13 (конкретно на К" и К ). В это время на вторых вхоФ

+ дах компараторов К и К присутствует сигнал невязки GX(t) — F.

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

7 1187

К+ или К . Срабатывание происходит при превышении сигналом невязки заданного порогового уровня +V„o или величине сигнала невязки нйже порогового уровня -V .При этом с выхода сработавшего компаратора

13 следует импульс, корректирующий значения неизвестного X.„, записанного в реверсивном счетчике 26 соответствующего АЦП 8, т.е. уменьшает 1О или увеличивает величину кода Х;.

Таким образом, компараторы являются чувствительным органом (регулятором) цепи уравновешивания и служат для периодического уточне- 15 ния значений Х„ ° Они определяют необходимость коррекции Х, ее знак

11 и выдают корректирующие (приводящие к равновесию системы) импульсы.

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

1t 11 И 11 tt 11

Ч1 а,>р t Vz no(Чъ 11О11 по казывающие, как с каждым Циклом уравновешивания Онижаются задаваемые пороговые уровни.

В течение второго подцикла рабо- 25 ты устройства выходные сигналы компараторов подаются также на в формирователей 14. При этом сигнал срабатывания одного из компараторов

13 вызывает изменение состояния 30

1связанного с ним триггера 21 формирователя 14 для управления АЦП 8.

Выходной сигнал сработавшего триггера 21, пройдя через элемент ИЛИ 22, разрешает прохождение сигнала переписи Я1 с блока 16 через элемент

И 23 на соответствующий АЦП 8 блока 7 (сигнал переписи Е4 поступает на элемент И 23 в первом подцикле работы устройства (фиг.2), 40

Статические триггеры 21 возвращают157 ся в исходное состояние сигналом

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

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

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

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

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

Х; в реверсивных счетчиках 26

АЦП 8 являются искомыми неизвестными Х, Х,..., X„, т.е. определяют результат решения системы линейных алгебраических уравнений. Кроме того, на выходе блока 4 интеграторов имеет аналоговые значения вектора корней Х1, Х,, Х .

1187 157

1187157

+Ьи

И! NP и р

43mp

lgtmp

Составитель В.Рыбин

Редактор Н.Данкулич ТехредМ.Гергель Корректор 0.Луговая

Заказ 6551/54 Тираж 709 Подписное

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

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

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