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

1

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

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

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

Устройство содержит регистровые блоки 1 коэффициентов матрицы кор- peKiyiH с первой по п-ю, группы 2,- 2 умножителей, первую 3, вторую 4, третью 5, четвертую 6 группы сумматоров, с (п+1)-й по 2 п-ю группы 7,- 7f, умножителей с (2п+1)-й по 3 п-ю группы 8,-8 умножителей, регистровый блок 9 памяти коэффициентов уравнений, регистр 10 невязки, триггер 11, сумматор 12 экстраполированных значений, счетчик 13, дешифратор 14 и первые 15 и вторые 16 элементы И.

Устройство работает след то1цим образом.

Время работы разбито на циклы. Каждьш цикл содержит п тактов. Один такт равен времени прохождения одного разряда, число разрядов равно т. Начало цикла в ви,це сигнала поступает с внешнего входа устройства на счетчик 13 и триггер 11, В результате в счетчике формируется номер шага (в данном случае один шаг), а триггер 11 перебрасывается в 1 состояния и на выходе элемента И 15 формируется приращение длиной m разрядов. Приращение, начиная с младших разрядов, поступает на умножитель 7 , на остальные умножители приращения поступают с выходов в других ячеек. Так как произведение имеет 2т разрядов, то m старших разрядов формируется во втором цикле. Начиная с первого разряда второго цикла, величина с выхода сумматора 5 поступает на умножитель 2 , на выход остальных ут 1ножителей поступает информация с выходов сумматора 5 других ячеек. Получаемые на выходах умножителей 2j (,n) произведения складьшаются на сумматоре 3. Полученная величина затем складывается с рассогласованием, храняишмся в ре264272

гистре 10. Так как сумма произведений на выходе сумматора 3 имеет 2т разрядов, то и регистр 10 имеет 2т разрядов, поэтому m младших разря- 5 дов рассогласования, получающиеся во 2-м цикле, не участвуют в формировании приращений. Это достигается тем, .что по сигналу начала второго цикла триггер 1 перебрасывается в 10 О и закрывает элемент И 15. Одновременно с умножителями 7 в первом цикле начинают работать умножители 8j (,n). Множимые поступают с выходов регистров (j I,n), множи- 15 тели хранятся в регистрах умножителей, которые заносятся туда из регистров . Полученные произведения складываются на сумматоре 6. Во втором цикле, когда на входы сумматора

6 поступают старшие m разрядов произведений, открывается второй элемент И 16 сигналом с дешифратора 14 и поступает на вход сумматора 6 число, равное 1. По этому же сигналу разрешается запись Б регистр l,j величины, получаемой на выходе сумматора 6. Затем все повторяется, за исключением того, что число, равное 1, не добавляется к сумме произведений,формируемой на выходе сумматора 6. На выходе деЕ ифратора 14 формируются сигналы, управляющие записью в регистры l(j в следующей последователь

ности: 1

2

inЧерез

2п циклов счетчик 13 переполняется . Сам он переходит в нулевое состояние, а на выходе переноса появляется сигнал. По сигналу содержимое регистров 11J перезаписывается в ре- Г истры умножителей 7j и . Это допускается, так как через 2п циклов во всех регистрах сформированы нужные величины элементов матрицы Ф.

На выходе сумматора 5 формируется приращение неизвестной величины, которое поступает на накопитель 12, где складьшается с предыдущим значением искомой величины. Если текущее значение искомой переменной обо- значить через X J, эначение, получаемое на выходе сумматора 5 через , то в накопителе 12 формируется величина:

К-Я к -9(14))

X; Х +VX .

1 1

где k - номер шага итерации, ,.., п (для рассматриваемой ячейки ).

VX

э(кн1 ,, .

. , M J где , . . . ,n, V X - приращение получаемое на выходе элемента И 15 в текущем шаге, Ф; элементы матрицы Ф, являющейся некоторым приближением обратной матрицы. На выходе сумматора 3 формируется величина

о„х. -Та- - , о i ,2,..,п.

Полученная величина складьшается с содержимым регистра 10, который хранит текущее рассогласование

- + t

г

5;+аХ . , ,2,...,n

К + 1

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

vxt-.

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

АХ

; . V

,S ) .

где P°(s ) - функция выделения m

разрядов с О по m в переменной S,

Х Х,...,Х - вектор неизвестны

- матрица коэффициентов исходной системы уравнений

А

Ф

- вспомогательная матрицй.

S ь, ,Ь2, ...,Ьп -вектор

свободных чл нов.

За начальное приближение выбирают (). Ф в этом случае равно:

Ф А +А (Е-Л) ,

Х;„(Е-А) (Е+(Е-А) + ...+

+ (Е-А)2-)В , где Хд - начальны; ; вектор невязки.

В регистрах 9; (,п; j l,n) хранится матрица коэффициентов D Е-А. Значения коэффициентов, хранимых в первом столбце, поступают на схемы умножения устройства, реализующего первое уравнение, второго столбца - второго уравнения и т.д. Соответственно на вторые выходы умножителей поступают значения стро матрицы Ф, т.е.

y,,, dj, (j l,n)

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

Ф.

IC+I

.ф,..а-,-и,

1 г 1

Во втором шаге изменяется расположение информации в блоке 9(, второй столбец передвигается на место nepBOi o, третий - второго и т.д. и первый на место п-го.

Во втором шаге, формируется ;м Д. .к

Ф,

0+0,

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

Ф

где

км

fg

(-),

если

51 ) С - v-и о, если

25

Соответственно, во втором устройстве формируется

Z Ф-

djp+S, (Е-2),

40

45

50

30

где Р(2,1)п - означает, что J принимает последовательно значения-2,3, . . . , п, 1 .

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

ф Е+(Е-А)+(Е-А) ; (Е-А)+(Е-А)+(Е-А) ;

(Е -А) + . . . + (Е-А) Формула изобретения

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

5I

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

26427,6

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

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

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

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

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

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

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

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

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

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