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

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

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

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

Устройство содержит первый и второй регистры 1.1 и 1.2, умножители 2.1.1, 2.1.2, 2.2.1, 2.2,2 матршды умножителей, первый и второй сумма-. торЫ 3.1 и 3.2, перврлй и второй блоки 4.1 и 4.2 приоритетного формирования нулей, первый и второй элементы 5.1 и 5.2 задержки, первый и второй элементы 6.1 и 6.2 сравнения, элемент ИЛИ 7 первьй и второй одно- вибратор 8, элемент НЕ 9., элемент И 10, одновибратор 11, входы 12-15 задания коэффиц 1ентов уравнений, входы 16 1 17 за/чания величин правых частей уравнений, вход 18 запуска, устройства, выходы 19 и 20 результата устройства, выход 21 сигнала окончания решения Блок приоритетного формирования нулей содержит та идентичных схем, где m - разрядность устройства, калсдая из которых содер- Ж1Т одковибратор 22; элемент 23 задержки, элемент И 24, вход 25, выход 26,

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

I В блоке приоритетного формирования нулей в стационарном режиме О или 1 на входе 25 повторяется на его выходе 26. При переключении 1 в О йа входе 25 одновибратора 22 последний запускается и на его выходе имеет место 1, на выходе 26 формируется : О . При переключении О в 1 на входе 25 одновибратор 22 запускается. На его выходе формируется отрицательный импульс длительностью i , после окончания которого на выходе 26 формируется значение 1. Таким образок, значение 1 на выходе устройства формируется с задержкой на регулируемое время Т , в то время, как значение О сразу же поступает на выход.

Перед началом решения в исходной СЛАУ осуществляется замена переменной

X Z - X

1ПЛХ

где X - вектор, компоненты которого положительные и не меньше максимального по модулю решения х. СЛАУ Ах Ь, такой, что выполняются неравенства

О if Ах А f

VnCkX

В результате приходим к СЛАУ вида

AZ f,

решение которой неотрицательное, так как Z X +х ,0.

Указанное преобразование осуществляется, если компоненты матрицы А удовлетворяют условиям

l,j

в этом случае значение х . должt 0, 1

но удовлетворять неравенству

b,l

,,1}

- X

: i ; t -1, п

J--1

где наибольшая по модулю компонента вектора b.

Из неравенств

.. t1, а.. О, а. .

11 и 11

i,j Vn

.,jii

имеем

n

ну,п |l I-. l -- r-ln{q i- la, jl) X -. .|}.0

Поскольку 0 a.. 1, а..0,то

,

(A-E) И, следовательно

tt)f +b)

(A-E)Z(A-E)(x +x)Ax +b-(x .iTiax

-t-.x ), откуда

f Ax +b x +x (Ax A f

Далее СЛАУ преобразуется к виду

Z Z - H(AZ - f), , k - целое число, так, чтобы при Z , Z выполнялось Z,j- f) PCAZ f). Ha входы 12-17 задаются соответственно значения компонент

(1-f «,,), Ра„, ,-, (,а), Р f,.-, pf На вход 18 поступает сигнал пуска устройства, по которому запускается одновибратор 11, на выходе кото3

рого формируется короткий отрицател

ный импульс, поступающий на R-входы регистров 1. В результате значения на выходах регистров обнуляются, на выходах сумматоров 3 формируются значения pf. , и juf , которые .через устройства приоритетного формирования нулей и элементы задержки поступают на D-входы регистров 1 и по синалу от элемента сравнения записываются в регистры. Таким образом устанавливаются значения.компонент вектора начального приближения Z

rf.

В дальнейшем на выходе сумматора 3.1 будет формироваться значение

-Ka,,Z: -fj.

Z Z° 11

a на выходе сумматора второй строки - значение

z; z;-Ma,,Z° f, )- Время задержки включения 1 в i-M (,2) устройстве приоритетного формирования нулей не меньше значения , t; max (lo)ii (oi)i, (10)12 01)12 гдеТ/ д,., 1 ,..- наибольшее и наименьшее время переключения значения разрядов из 1 в О и из О в 1 на выходе умножителя i-й строки j-ro столбца.

Это обеспечивает формирование на выходе i-ro устройства приоритетного формирования нулей значения у. , удовлетворяющего неравенству

У,,(а, ,, Z - f ) , i 1,2.

Поступление информации с выхода устройств приоритетного формирования нулей на D-входы регистров через линии задержки исключает возможность записи значений, которые меньше значений, хранимых регистрами, во время отключения сигналов записи в регистр формируемых элементами сравнения. В последующие моменты времени Т., Т ,.. . , Т в силу изотонности отоб-. ражения Z - (AZ-f) в регистры будут записываться значения последовательных приближений

Z Z - ((AzW), Z i Z -M()

z ( откуда Z . Запись значения 2(N4i) 2 невозможна.

f),

так как

Z ( -/u(AZ -O Z .

1

ь

г

i.:)л

10

15

яе

,

20

25

30

35

40

45

50

55

5U44

Таким образом, в устройстве имеет место вычислительный процесс, обеспечивающий монотонную сходимость последовательности { Z I}K решению Z вида гТ

Сигнал готовности на выходе 21 формируется следующим образом. При запуске одновибратора 8 на его выходе формируется импульс, длительность которого не меньшая, чем максимальное время задержки информации в каждой строке от входа регистра до выхода элемента сравнения. При записи любого последовательного г приближения в регистры 1 по сигналу от элемента сравнения одновременно повторно запускается одновибратор 8, импульс на выходе которого длится до тех -пор, пока в регистрах не устанавливается решение (повторные запуски прекращаются и на выходе 21 формируется единичный сигнал, указывающий на то, что решение найдено). Элемент НЕ 9 необходим для того, чтобы блокировать сигнал готовности н время запуска од ювиб- рйтора. После формирования сигнала готовности определяется решение X системы Ах b по формуле х X

KiuXУвеличение производительности устройства обеспечивается в результате уменьшения интервала времени двумя последовательными з апйсямк приближений в регистр за счет определения с помощью элементов сравнения моментов окончания формирования результатов.

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

Устройство для решения систем линейных алгебраических уравнений, содержащее п регистров, матрицу п X п умножителей, п сумматоров, выход i-ro регистра (,...п) подключен к входу первого сомножителя умножителей i-ro столбца матрицы, входы второго сомножителя умножителей матрицы подключены к входам задания козффициен тов уравнений устройства, выходы jrx (,..., п) умножителей i-й строки матрицы умножителей подключены.к j-M информационным входам i-ro сумматора, (п+1)-е информационные входы сумматоров подключены к входам задания величин правых частей уравнений устройства, отличающееся тем, что, с целью увеличения произво5

дительности устройства, оно содержит п блоков приоритетного формирования нулей, п элементов задержки, п элементов сравнения, элемент ИЛИ, элемент И, элемент НЕ, первый и второй одновибраторы, выход i-ro сумматора подключен к информационному входу i-ro блока приоритетного формирования нулей, выход которого подключен к первому входу i-ro элемента сравнения и входу i-ro элемента задержки, второй вход i-ro элемента сравнения подключен к выходу i-ro регистра, выход i-ro элемента сравнения подключен к входу считывания i-ro регистра и к i-му входу элемента ИЛИ, выход i-ro элемента задержки подключен к информационному входу i-ro регистра, выход элемента ИЛИ подключен к входу первого одновибра- тора и йходу элемента НЕ, выходы первого одновибратора и элемента НЕ подключены соответственно к первому

545044

и второму входам элемента И, выход которого подключен к выходу сигнала окончания решения уравнения устройства, вход запуска устройства подключен к входу второго одновибратора, выход которого подключен к входам установки в О п регистров, выходы которых подключены к выходам результата устройства, при этом блок при)0 оритетного формирования нулей содержит га рдновибраторов (т - разрядность устройства), m элементов И, . m элементов задержки, вход k-ro (,...,m) разряда блока приори15 тетного формирования нулей подключен к информационному входу k-ro одно- вибратора и входу k-ro элемента задержки, выходы k-x одновибратора и элемента задержки подключены соот0 ветственно к первому и второму входам k-ro элемента И, выход которого подключен к выходу k-ro разряда блока приоритетного формирования нулей.

R

25

2S

lpui.2

Составитель В. Смирнов Редактор И. Касарда Техред И.Попович

Заказ 4723/54 . Тираж 671

ВНИШШ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

КорректорЕ. Сирохман

Подписное

Изобретение относится к цифровой вычислительной технике и может быть использовано для быстрого решения систем линейных алгебраических уравнений. Цель изобретения - повьшение производительности устройства. Устройство содержит матрицу пхп умножителей, п регистров, п сумматоров, п блоков приоритетного формирования нулей и элементов задержки, п элементов сравнения, элемент И, элемент ИЛИ, элемент НЕ, два одновибратора. Увеличение производительности устройства обеспечивается в результате уменьшения интервала времени между двумя последовательными записями приближений в регистр за счет определения моментов окончания формирова- 1НИЯ результатов. 2 ил. i (Л tc СП 4 сл