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

 

Изобретение относится к области цифровой вычислительной техники и может быть использовано в специализированных устройствах, предназначенных для решения систем линейных алгебраических уравнений. Цель изобретения - повьш1ение скорости вычислений . Указанная цель достигается тем, что устройство содержит регистровые блоки коэффициентов матрицы коррекции, умножители, группы сумматоров, регистровьм блок памяти коэффициентов уравнений, регистры невязки, триггер, сумматоры экстраполированных значений, счетчик, дешифратор , элементы И, Устройство реализует решение методом приближений с одновременной коррекцией матрицы экстраполяции. 1 ил. i (Л :3

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

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

РЕСПУБЛИК .

42 А (191 (11) (511 4 G 06 Е I/02, !5/32

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГГИЙ

c "-

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

Б1,,":,, f (21) 3680839/24-24 (22) 26.12.83 (46) 23.04.86. Бюл, 9 15 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.Е.Золотовский и P.Â.ÊîðoáêîB (53) 681.32(088.8) (56) Витенберг И.М. Программирование аналоговых вычислительных машин..

М.: Машиностроение, 1972.

Цифровые дифференциальные анализаторы./Сб. пер. под ред. Когана Б.Я. 1963.

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

1(682902, кл. G 06 F 15/32, 1973.

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

9 710044, кл. G 06 F 15/32, 1976. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к области цифровой вычислительной техники и может быть использовано в специализированных устройствах, предназначенных для решения систем линейных алгебраических уравнений. Цель изобретения — повышение скорости вычислений. Указанная цель достигается тем, что устройство содержит регистровые блоки коэффициентов матрицы коррекции, умножители, группы сумматоров, регистровый блок памяти коэффициентов уравнений, регистры невязки, триггер, сумматоры экстраполированных значений, счетчик, дешифратор, элементы И. Устройство реализует решение методом приближений с одновременной коррекцией матрицы экстраполяции. 1 ил.

12?6427

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

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

На чертеже изображена функциональная схема предлагаемого устройства (для упрощения показана реали-. зация лишь одного (первого) уравнения из множества алгебраических уравнений).

Устройство содержит регистровые блоки ) коэффициентов матрицы коррекции с первой по п-ю, группы 2!—

2д умножителей, первую 3, вторую 4, третью 5, четвертую 6 группы сумматоров, с (и+1)-й по 2 и-ю группы 7„7»» умножителей с (2n+1)-й по 3 и-ю группы 8,-8 умножителей, регистровый блок 9 памяти коэффициентов уравнений, регистр 10 невязки, григгер

11, сумматор 12 экстраполированных значений, счетчик 13, дешифратор 14 и первые 15 и вторые 16 элементы И.

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

Время работы разбито на циклы.

Каждый цикл содержит и тактов. Один такт равен времени прохо>кдения одного разряда, число разрядов равно

m. Начало цикла в виде сигнала поступает с внешнего входа устройства на счетчик )3 и триггер 1), В резуль— тате в счетчике формируется номер шага (в данном случае один шаг), а триггер )l перебрасывается в "1" состояния и на выходе элемента И !5 формируется приращение длиной т разрядов. Приращение, начиная с младших разрядов, поступает на умножитель 71, на остальные умножигели приращения поступают с выходов в дру гих ячеек..Так как произведе;-»ие имеет 2m разрядов, то m старших разрядов формируется во втором цикле. Начиная с первого разряда второго никла, величина с выхода сумматора 5 поступает на умно>китель 2», на выходы остальных умножителей поступает информация с выходов сумматора 5 других ячеек. Получаемые на выходах умножителей 2 » (j =1,n) произведения складываются на сумматоре 3. Полученная величина затем складывается рассогласованием, хранящимся в регистре 10. Так как сумма произведений »а выходе сумматора 3 имеет 2m разрядов, то и регистр 10 имеет 2m разрядов, поэтому m младших разрядов рассогласования, получающиеся во 2-м цикле, не участвуют в формировании приращений. Это достигается тем, что по сигналу начала второго цикла триггер )1 перебрасывается в

"0" и закрывает элемент И 15. Одновременно с умножителями 71 в первом пикле начинают работать умножители

8 (=),n). Множимые поступают с выходов регистров 9» (j=-),n), множители хранятся в регистрах умножителей, которые заносятся туда из регистров I« . Полученные произведения складываются на сумматоре б. Во втором цикле, когда на входы сумматора

6 поступают старшие m разрядов произведений, открывается второй элемент

И 16 сигналом с дешифратора 14 и поступает на вход сумматора 6 число, равное 1. По этому же сигналу разрешается запись >з регистр 1»» величины, получаемой на выходе сумматора 6.

Затем все повторяется, за исключением того, что число, равное 1, не добавляется к сумме произведений,формируемой на выходе сумматора 6. На выходе дешифратора 14 формируются сигналы, уг равляющие записью в регистры )»» в следующей последовательности: 1», ),z„)»„,...,1»»,. Через

2п циклов счетчик )3 переполняет35 ся. Сам он переходит в нулевое состояние, а на выходе переноса появляeòñя сигнал . По сигналу содержимое регистров !»» перезаписывается в ре4О ,истры умно>кителей 7 и 8 . Это допускается, так как через 2п циклов во всех регистрах 1»» сформированы нужные величины элементов матрицы Ф.

На выходе сумматора 5 формируетqc ся приращение неизвестной величины, которое поступает на накопитель 12, где складывается с предыдущим значением искомой величи »ы. Если текущее значение искомой переменной обозначить через !, значение, полу . к

1 чаемое на выходе сумматора 5 через ,э»л »)

L» >l, то в накопителе l2 формируется величина; к1» к !»1 1)

Х =Х +сХ

1 1 1 где )с — номер к»ага итерации, i=), п (для рассматриваемой ячейки i=l).

1226427 в

К+1

rpe i=1,...,n, Ч Х вЂ” приращение, получаемое на выходе элемента И 15 в текущем шаге, Ф вЂ” элементы матрицы Ф, являющейся некоторым приближением обратной матрицы. На выходе сумматора 3 формируется величина кь, ". э(ко) Полученная величина складывается с содержимым регистра 10, который хранит текущее рассогласование

К+1

Рассогласование S . используется .для формирования нового приращения ..К,Ф 2

ЧХ„

Этот процесс описывается системой уравнений: к«к

Sxè1 =Sk k=EXkk"

К+i O К а 9 m

ЧХ =P 1$ ) — АХ = ЧХ

Х =Х+ Хз, о . K где Р (S ) — функция выделения m

ТП разрядов с 0 по m в переменной S, Х= (Х1,...,X ) — вектор неизвестных, — матрица коэффициентов исходной системы уравнений.

Фц1Ф 12... Ф1„ вспомогательная n @nz Фпп матрица. в =в,в= (ь,,ь„...,ь.1

Ф=Л +А, Е-,Л)

-1 -1, X;„= (E-A) X + (E+ (Е-A) +... +

+(Š— А) )В где Х„ — начальный вектор невязки.

В регистрах 9; (i=1,n; j=l,п) хранится матрица коэффициентов D=

=Е-А. Значения коэффициентов, хранимых в первом столбце, поступают на схемы умножения устройства, реализующего первое уравнение, второго столбца — второго уравнения и т.д.

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

За начальное приближение выбирают Ф=Е+(Е-А), Ф в этом случае равно:

У =Ф . d (j=l,n)

1 fl j 1

Полученные произведения суммируют с я н а сумматоре и

К+1

5 Ф = Ф d +1, н . ц 11

1=1

Во втором шаге изменяется расположение информации в блоке 91, второй столбец передвигается на место первого, третий — второго и т.д. и первый на место n — го.

Во втором шаге формируется

3=

Этот процесс продолжается и шагов, что позволяет определить все коэффициенты строки матрицы Ф:

1=1

0=1, п

1, 1, если Х=О о (О, если ) Х) 0

Соответственно, во втором устройстве формируется и где 12=(2,1)п — означает, что 7 принимает последовательно значения 2,3, ...,n,1.

На первом шаге происходит корректировка сначала элементов основной диагонали, во втором шаге — ближайшей боковой и первого элемента (n-1) строки, в третьем — следующей боковой диагонали и первого элемента (n-1)-й строки элемента и т.д., т.е. если а

Ф =Е+ E-A) то

Ф =Е+ (Е-Л)+ (Е-Л)

4p + =E+ (Е Л)+ (E A) + (Е-А)

Ф =Е+ (Š— А) +... + (E-A) +

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

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

=1,2,...,n) с первой по п-ю групп подключены к информационным входам

i-го сумматора первой группы, выход

5 IZ которого подключен к первому информационному входу i-го сумматора второй группы, выход которого подключен к входу -го регистра невязки, выход которого подключен к второму информационному входу i-го сумматора второй группы, отличающее с я тем, что, с целью повышения скорости вычислений, оно содержит,.с (и+

+1)-ю по Зп группы по и умножителей, третью и четвертую группы по п сумматоров, п регистровых блоков памяти коэффициентов матрицы коррекции,регистровый блок памяти коэффициентов уравНений, первую и вторую группы элементов И, п триггеров, дешифратор и счетчик, информационные выходы i-го регистрового блока памяти коэффициентов матрицы коррекции подключены к первым информационным входам i-х умножителей с {п+1)-й по

2п-ю групп и к первым информационным входам i-x умножителей с (2п+))-Й по 2п-ю групп, выходы -х умчожителей групп с {и+1)-ю по 2п-ю подключены к информационным входам i-го сумматора третьей группы, выход которого подключен-к второму информационному входу 1-го умножителя -й группы и к информационному входу соответствующего i-го накапливающего сумматора экстраполированных значений, выход i-ro сумматора второй

O группы подключен к первому входу

2642i Ь

i-го элемента И первой группы, второй вход которой подключен к выходу

i-го триггера, вход сигнала начала цикла подключен к информационным входам триггеров и счетчика, выход сигнала переполнения которого подключен к управляющим входам умножителей с jn+I)-ю по Зп-ю групп, информационные .выходы счетчика подключены к !

О входам дешифратора, i-й выход которого подключен к соответствующим управляющим входам i-го регистрового блока памяти коэффициентов матрицы коррекции и к первым .входам 1 го элемента И второй группы, второй вход которого подключен к входу управления режимом коррекции устройства, выход i-ro элемента И второй группы подключен к управляющему вхо20 ду 1-го сумматора четвертой группы, информационные входы которого подключены к выходам i-x умножителей групп с (2п+1) -ю по Зп-ю, а выход к информационным входам i-го регист25 рового блока памяти коэффициентов матрицы коррекции, выход i-го элемента И первой группы подключен к вторым информационным входам 1-х умножителей групп с (n+I)-ю по 2п-ю и к информационным выходам устройства, второй информационный вход i-ro умножителя подключен к -м выходам регистрового блока памяти коэффициентов уравнений.

1226427

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

Редактор Е.Папп Техред И.Верес Корректор M.Ïoæo

Заказ 2133/47 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4