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

 

Изобретение относится к вычислительной технике и позволяет повысить быстродействие устройства. Устройство содержит блоки памяти 1,2, счетчики 3,4, дешифратор 5, триггеры 6,7 сумматор 8, блок 9 вычитания, блок 10 сравнения, N блоков умножения 11, где N- порядок системы линейных алгебраических уравнений /СЛАУ/, N регистров 12, элементы ИЛИ 13-15, элемент НЕ 16, элементы И 17-19, группы 20-23 по N элементов И. Устройство работает на основе метода Зейделя. 1 ил.

СОЮЗ СОВЕТСКИХ.

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

РЕСПУБЛИК (59 4 С 06 F 15/324

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4310273/24-24 (22) 06.07.87 (46) 23.05.89. Бнл. N - 19 (72) II.À. Сависько, С,А. Шеметов и А.Н. Башкиров (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 813445, кл. С 06 F 15/324, 1978, Авторское свидетельство СССР

У 1024932, кл. С 06 F 15/324, 1983. (54,) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕИ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

„„SU„„1481794 А 1

2 (57) Изобретение относится к вычислительной технике и позволяет повысить быстродействие устройства. Устройство содержит блоки памяти 1,2, счетчики 3,4, дешифратор 5, триггеры 6, 7, сумматор 8, блок 9 вычитания, блок

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

12, элементы ИЛИ 13-15, элемент НЕ

16, элементы И 17-19, группы 20-23

no n элементов И. Устройство работает на основе метода Зейделя. 1 ил .

1481794

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

Цель изобретения - повышение быст5 родействия, достигаемое за счет параллельного вычисления для каждой итерации произведения коэффициентов неизвестных на.значения самих неизвестных при использовании итерационального. метода Зейделя +(м н х„= pn + w а(„x1 +Ф„„х„,k=1,п, j-Т а также за счет ускорения итерационального процесса за счет исключения из дальнейших вычислений неизвестных, найденных с требуемой точностью и переходе на .(k+1)-й итерации к нахождению п-й неизвестной, если (n-1)-е неизвестные найдены в предыдущих k-x итерациях.

На чертеже представлена схема устройства.

Устройство содержит первый 1 и второй 2 блоки памяти, первый и второй счетчики 3 и 4, дешифратор 5,первый и второй RS-триггеры 6 и 7,сумматор 8, блок 9 вычитания, блок 10 сравнения, и блоков 11 -11" умножения, и регистров 12 -12, первый,втои рой и третий элементы ИЛИ l3-15,эле" мент HE 16, первый, второй и третий элементы И 17-19, первую 20 -20", вторую 21" -21", третью 22 -22", чет- 35 вертую 23 -23" группы элементов И, вход 24 запуска устройства, вход 25 коэффициентов и правых частей системы уравнений устройства, вход 26 значения точности решения системы урав- 40 нений устройства, выход 27 результата решения устройства.

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

Нулевое приближение. Так как блок 45

9 вычитания установлен в состоянии

00...0, а на второй вход блока 10 . сравнения подано значение Ь а, то на выходе блока 10 вырабатывается высокий потенциал, который через элементы ИЛИ 15 и 13 подается на первый вход элемента И 17, разрешая прохождение перепада потенциалов с прямого выхода триггера 6, возникающего при поступлении на его вход S управляющего сигнала, на счетный вход счетчика 3, одновременно триггер 7 устанавливается в единичное состояние. Так как в блаке 1 памяти (ЗУ1) информация записана во все ячейки 1, то по адресу 00...01 из нее считывается "1" и разрешит через элемент И 18 прохождение кода 00...01 на адресный вход блока 2 памяти (ЗУ2) и вход дешифратора 5. Из ЗУ2 по адресу 00...01, что соответствует выбору коэффициентов первого уравнения системы линейных алгебраических уравнений, считываются и подаются значения, на первый вход сумматора 8. На другие (2,:,и+1) входы сумматора подаются значения 00...00, так как в блоках t1 -11 умножения п коэффициенты ; умножаются на код

00...00. Таким образом, на выходе сумматора имеем хо =, + K of; > 0 = ».

Это значение через элемент И 19 переписывается в регистр 12 . Анало1 гичным образом проводятся итерации

2,...,n.После и-й интерации в регии страх 12 -12 записываются соответствующие значения начальных приблий « » о

Первое приближение. Из ЗУ2 trocneдовательно выбираются коэффициенты соответствующих уравнений СЛАУ и поданы соответственно: ; — на первый вход сумматора 8, с 11 — на первый вход соответствующего блока 11 умножения, в котором производится перемножение значений этих коэффициентов на значения нулевых приближений

si> ° х,. Эти значения суммируются в сумматоре 8 и подаются на первый вход блока 9 вычитания, на второй

его вход подается значение нулевого приближения j-й неизвестной х из

; 1 соответствующего регистра 12 через соответствующий элемент И 22 и элемент ИЛИ 14, Выбор соответствующего регистра 12" осуществляет дешифратор

15 путем возбуждения соответствующей выходной шины. Таким образом, в блоке 9 вычитания определяется разность между значениями 3 неизвестной СЛАУ нулевого и первого приближений.Далее, если эта разность меньше или равна допустимой ошибке, то по адресу j в ЗУ 1 записывается "0", одновременно значение j-й неизвестной первого приближения переписывается в соответствующий j-й регистр, а так" же записывается "1" в счетчик 4.

Аналогично проводят п итераций, в н ,результате чего в регистрах 12 -12 записываются значения неизвестных первого приближения.

5 1481 794

Подобным образом производят второе, третье и т.д. приближения. Окончание работы происходит при достижении счетчиком 4 с ос тоя ния и.

Повыше ни е быс тр одейс тв ия работы

5 устройства достигается за счет исключения из дальнейших вычислений значений неизвестных, вычисленных при предыдущих приближениях, так что если j ÿ неизвестная вычислена с заa+i данной точностью (т. е. х — х с

X A»>), то в соответствующую j-ю ячейку ЗУ1 записывается "О". Тогда на следующем приближении при считывании по адресу j из ЗУ1 на выходе

ЗУ1 появляется "О" означающий, что по адресу j из ЗУ2 информация не выбрана. Одновременно после прохождения через элемент НЕ этот сигнал изменяет состояние счетчика 4 на "1", т.е. производится ускоренный переход к следующей (j+1)-й итерации.

При достижении счетчиком 4 состояния и на его выходе вырабатывается 25 сиrнал, устанавливающий первый триггер в нулевое состояние и разрешающий выдачу содержимых регистров

12 -12" через элементы И 23 -23 на выходе 27 устройства.

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

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

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

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

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

ИЛИ и подключены к первому входу второго элемента ИЛИ и к счетному вхо- . ду второго счетчика, выход перепол- °

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

14Я1 94

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

Техред M.Õîäàíè÷ КорректорВ. Гирняк

Редактор В. Данко

Заказ 2692/51 Тираж 669 . Подписное

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 ны соответственно к вторым входам блоков умножения с первого по п-й, (n+t)-й выход первого блока памяти подключен к (n+1)-му входу суммато5 ра, выход которого подключен к второму входу блока вычитания и к первому входу третьего элемента И, выход которого подключен к третьим входам элементов И первой группы,тре; тий выход блока сравнения подключен к второму входу второго элемента

ИЛИ, выход которого подключен к второму входу третьего элемента И, к входу установки в "0" второго триггера и к второму входу третьего элемента ИЛИ, выход переполнения второго счетчика подключен к входу установки в "0" первого триггера, к вторым входам элементов И четвертой группы, выходы которых подключены к вьходам результата решения устройства.