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

 

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

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

РЕСПУБЛИК (si)s G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4802559/24 (22) 30,01.90 (46) 23.03.92. Бюл. N 11 (71) Особое конструкторское бюро моделирующих и управляющих систем (72) В.Ф.Арсени, М,Е Бородянский, B.È,Áîгачев, М.М.Пцарева и А.Н.Целых (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 813444, кл. G 06 F 15/324, 1979, Авторское свидетельство СССР

N1546994,,кл. G 06 F 15/32, 1986. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ. ЛИНЕЙН ЫХ АЛГЕБРАИЧЕСКИХ

УРАВНЕНИЙ

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

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

„„. Ж„„1721613 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных и моделирующих системах и вычислительных комплексах. Оно решает системы линейных алгебраических уравнений. С целью увеличения быстродействия в устройство введены дополнительно несколько блоков памяти, блок вычисления коэффициента., узел сравнения и логические элементы И и

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

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

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

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

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

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

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

5 управления, выход второго блока памяти соединен с вторым входом накопителя.

Указанное устройство реализует итерационный метод, поэтому точность решения зависит от времени решения. Особые труд10 ности составляет выбор и расчет итерационного параметра г.

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

20 информационному входу второго блока памяти, блок транспонирования матриц, три блока вычисления скалярного произведения, блок вычисления обратной матрицы, два элемента ИЛИ, вход запуска устройства

25 подключен к входу запуска блока синхронизации, выход первого блока памяти — к первому информационному входу первого блока вычисления скалярного произведения и к информационному входу блока

30 транспонирования матриц, выход которого подключен к второму информационному входу первого блока вычисления скалярного произведения и к первому информационному входу второго блока вычисления скаляр35 ного произведения, выход второго блока памяти подключен к второму информационному входу второго блока вычисления скалярного произведения, выход первого блока вычисления скалярного произведе40 ния подключен к информационному входу блока вычисления обратной матрицы, первый и второй информационные входы третьего блока вычисления скалярного произведения подключены соответсвтенно к

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

55 блока вычисления скалярного произведения, к первому входу второго элемента

ИЛИ, к второму синхровходу блока транспонирования матриц, к второму входу первого элемента ИЛИ и к входу чтения второго бло,:а памяти, третий выход блока синхрониза1721613 ции подключен к синхровходу блока вычисления обратной матрицы, четвертый выход — к второму входу второго элемента

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

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

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

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

55 третьего по восьмой блоки памяти, блок вычисления коэффициента, блок деления, блок вычисления разности матриц, блок вычисления суммы матриц, первый и второй коммутаторы, триггер, узел сравнения, элемент И, первый и второй умножители и с первого по шестой элементы ИЛИ, причем выходы первого блока памяти подключены к информационным входам первой группы первого умножителя и информационным входам блока вычисления коэффициента, выходы которого подключены соответственно к информационным входам блока деления, выходы которого подключены к информационным входам второй группы первого умножителя и к информационным входам первой группы второго умножителя, информационные входы второй группы которого подключены соответственно к выходам второго блока памяти, выходы первого и второго умножителей подключены соответственно к информационным входам третьего и четвертого блоков памяти, выходы которых подключены соответственно к информационным входам первой группы блока вычисления разности матриц и перво.го коммутатора, выходы которых подключены соответственно к информационным входам первой группы второго коммутатора и первого блока вычисления скалярных произведений, выходы которых подключены соответственно к информационным входам пятого и шестого блоков памяти, выходы пятого блока памяти подключены к информационным входам второго блока вычисления скалярных произведений и к информационным входам первой группы блока вычисления суммы матриц, выходы которого подключены соответственно к информационным входам седьмого блока памяти, выходы которого подключены соответственно к информационным входам второй группы первого блока вычисления скалярных произведений, выходы второго блока вычисления скалярных произведений подключены к информационным входам .первой группы узла сравнения и к информационным входам первой группы узла сравнения и к информационным входам восьмого блока памяти, выходы которого подключены соответственно к информационным входам второй группы второго коммутатора, выходы шестого блока памяти — к информационным входам второй группы первого коммутатора и к выходам результата устройства, входы элементов единичной матрицы которого подключены к информационным входам второй группы блока вычисления суммы матриц и блока . вычисления разности матриц, входы точности ре1721613 шения устройства подключены соответст- При этом блок управления содержит венно к информационным входам второй генератор тактовых импульсов, первый и группы узла сравнения, выход которого под- второй триггеры, сдвигающий регистр, заключен к входу установки в "1" триггера, кольцованный сдвигающий регистр, с первыход которого подключен к выходу призна- 5 вого по третий элементы И и элемент ИЛИ, ка завершения решения системы линейных причем вход останова блока подключен к алгебраических уравнений устройства и к входу установки в "1" первого триггера, первому входу элемента И, выход которого инверсный выход которого подключен к подключен к входу останова блока управле- первому входу первого элемента И, выход ния, вход признака считывания результата 10 которого подключен к первым входам втоустройства — к первому входу первого эле- рого и третьего элементов И, выходы котомента ИЛИ, выход которого подключен к рых подключены соответственно к входу входу чтения шестого блока памяти, вход сдвига сдвигающего регистра и к первому запускаустройства подключен квходузапу- входу элемента ИЛИ, выход которого подска блока управления и к первому входу 15 ключен к входу сдвига закольцованного ревторогоэлемента ИЛИ,выходкоторогопод- гистра, вход запуска блока подключен к ключен к входу устачовки в "0" триггера, входу установки в "0" первого и второго первый выход блока управления — к управ- триггеров и к информационным установочляющему входу блока вычисления коэф- ным входам сдвигающего регистра и закольфициентов и к первому входу третьего 20 цованного сдвигающего регистра, выход элемента ИЛИ, выход которого подключен к генератора тактовых импульсов подключен входу записи-чтения первого блока памяти, к второму входу первого элемента И, с первторой выход блока управления подключен вого по шестой информационные выходы к управляющему входу блока единиц, тре- сдвигающего регистра подключены сооттий выход — к управляющим входам первого 25 ветственно к выходам с первого по шестой и второго умножителей, к входам чтения блока управления, выход переноса сдвигатретьего и четвертого блоков памяти, к вхо- ющего регистра подключен к второму входу ду записи-чтения второго блока памяти и к элемента ИЛИ, первый информационный второму входу третьего элемента ИЛИ, чет- выход закольцованного сдвигающего регивертый выход — к входу записи третьего бло- 30 стра — к седьмому выходу блока управления ка памяти, к управляющему входу блока и к входу установки в "1" второго триггера, вычисления разности матриц и к первому прямой и инверсный выходы которого подвходу ч ходу четвертого элемента ИЛИ, выход ко- ключены соответственно к вторым входам

И. торого подключен к входу чтения пятого третьего и второго элементов блока памяти, пятый выход блока управле- 35 Блок вычисления коэффициента содерния подключен к первому входу четвертого жит генератор тактовых импульсов, суммаэлемента ИЛИ, выход которого подключен к тор, закольцованный сдвигающий регистр, входу чтения седьмого блока памяти, к уп- первый и второй регистры, первый и второй равляющему входу вычисления суммы мат- триггеры, узел сравнения, первый и второй риц, к входу записи пятого блока памяти, к 40 элементы И, причем информационные вхоуправляющему входу узла сравнения, к ды блока подключены соответственно к управляющему входу второго блока вы- информационным входам первой группы числения скалярных произведений и к вхо- сумматора, выходы которого подключены ду чтения восьмого блока памяти, шестой соответственно к информационным входам выход блока управления подключен к входу 45 первого регистра, выходы которого подклюзаписи четвертого блока памяти, к управля- чены к информационным входам второго ре, ющему входу первого блока вычисления: гистра, к информационным входам второй скалярных произведений и к первому входу группы сумматора и к информационным пятого элемента ИЛИ, выход которого под- входам первой группы узла сравнения, выключен к входам записи шестого и седьмого 50 ход которого подключен к входу установки в блоков памяти, седьмой выход блока управ- "1" первого триггера, выход которого подления подключен к управляющим входам ключен к первому входу первого элемента первого и второго коммутаторов и к второму И, выход которого подключен к входу запивходуэлемента И, восьмой выход-к вторым си-считывания второго регистра, выходы ковходам второго и входу четвертого элемен- 55 торого подключены к информационным тов ИЛИ и к входу записи восьмого блока входам второй группы узла сравнения и к памяти, девятый выход — к второму входу выходам блока, управляющий вход которого четвертого элемента ИЛИ, десятый выход — подключен к входу запуска генератора такк второму входу первого и пятого элементов товых импульсов, инверсный выход которо.о подключен к первому входу второго

1721613 .

Таким образом, и х=(Е+ В )...(Е+ В ) — Ь. (4) р

Оценим скорость сходимости вычислительного процесса. Пусть n = 0: х=(Š— В) — Ь;х =(Е+ В+ В ) — Ь, ре,у где х — приближенное решение СЛАУ.

Имеем

10 î F

IIx-õ" II= . - — Š—  —  — (! Ь|! г 2

IIaIP 2

l ьii:

Пусть и =1: х=(Е-В ) (Е+В) — b; И

20 х = (Е+ В + В )(Е+ В) — Ь; ,И!! В !! 3 2

1Ix х!! — II II II Е+ВII 2 Itbt!

25 !! -В "!!

При любом и (Š— В)й = — Ь, (2) ,И 30 где р — первая норма матрицы А;

В=Š— — А.

2 ,й

Матрица В имеет собственные числа, заключенные в интервале (-1, 1), поэтому 35

IIBiI< 1.

Алгоритм получения первой нормы матрицы А реализуется в блоке вычисления коэффициента.

Умножим левую часть формулы (2) на 40 матрицу (E+B): (Е+ В)(Š— В) х = (Е+ В) — b

/4 или (Š— В ) х=(Е+ В) — Ь. (3) и

Пусть задана точность вычисления е, Если условие

В я, (и =2,3,...)

50 выполняется, то процесс вычисления останавливается, если не выполняется, то снова умножают of å части (3) на Е+В, получают (5) Вычислительный процесс (4) имеет скорость сходимости, выражаемую неравенством (5).

Таким образом, за счет единообразия вычислительных элементов, способности вести параллельные вычисления, отсутствия операции деления (встречается только

2 при — ), и отсутствия необходимости вме,И шательства пользователя предлагаемое устройство оптимально по быстродействию и позволяет решать СЛАУ высокого порядка, Скорость сходимости вычислительного процесса весьма высока, что видно из оценки (5) (II В !1, !! В !! < 1).

На фиг.1 представлена структурная схема устройства для решения систем линейных алгебраических уравнений; на фиг.2— блок вычисления коэффициента (БВК) рс; на фиг.3 — временная диаграмма работы БВК, на фиг.4 — блок вычисления разности матри55 блока управления.

Устройство содержит первую входную шину элементов матрицы А, первый блок 2 памяти, первый умножитель 3, блок 4 вычисления коэффициента,и (БВК), блок 5 делеэлемента И, выход которого подключен к входу записи-считывания первого регистра, прямой выход генератора тактовых импульсов подключен к входу синхронизации сумматора и к входу сдвига закольцованного сдвигающего регистра; первый информационный выход — к входу синхронизации узла сравнения и к входу установки в "1" второго триггера, выход которого подключен к второму входу второго элемента И, второй информационный выход закольцованного сдвигающего регистра подключен к второму входу первого элемента И, третий информационный выход — к входам установки в "0" первого регистра и первого триггера, четвертый информационный выход — к входу установки в "0" второго триггера, Поясним алгоритм работы предлагаемого устройства.

Пусть имеется система линейных алгебраических уравнений (СЛАУ)

Ax= b, . (1) где А — положительно определенная квадратная матрица;

b — заданный вектор; х — искомый вектор решения системы.

Сделав преобразование системы (1), получают (Š— В ) х =(Е+ В )(Е+В) — Ь, р решение имеет вид

x = (Е+ В )(E+ В) — b. ,И

IIx — х I(— „ )!Ь!!, -р !! В!! !! Š— В"!!!!Š— B !!. !! Š— В !!

1721613

12 ния, второй умножитель 6, второй блок 7 памяти, блок 8 вычисления разности матриц (БВР), вторую входную шину 9 матрицы Е, блок 10 вычисления суммы матриц (БВС), коммутатор 11, третий 12 и четвертый 13 блоки памяти, первый блок 14 вычисления скалярных произведений (БВСП), узел 15 сравнения, третью входную шину 16 точности решения устройства е, триггер 17, пятый блок памяти 18, второй блок 19 вычисления скалярных произведений(БВСП), второй шинный коммутатор 20, шестой блок памяти 21, первую выходную шину 22 результата устройства, седьмой 23, восьмой

24 блоки памяти, четвертую входную шину

25 свободных членов системы алгебраических уравнений устройства, блок управления 26, пятую входную шину "Пуск" 27, элемент ИЛИ 28, элемент И 29, элементы

ИЛИ 30 — 34, вторую выходную шину 35 и шестую входную шину 36.

Вход 1 подачи матрицы А соединен с первым входом первого блока, первый выход которого соединен с первым входом первого умножителя 3 и через БВК 4 и блок

5 деления подключен к первому входу второго умножителя 6 и второму входу первого умножителя 3, выход которого подключен через второй блок 7 памяти к первому входу

6ВР 8, второй вход которого соединен с второй входной шиной 9 матрицы Е и первым входом БВС 10.

Выход БВР 8 подключен к первому входу коммутатора 11, второй вход которого соединен с выходом третьего блока 12 памяти, а выход — с первым входом четвертого блока 13 памяти, выход которого подключен к второму входу БВС 10 и к первому входу

БВСП 14, выход которого соединен с первыми входами блока 3 памяти узла 15 сравнения. Второй вход узла 15 сравнения соединен с третьей входной шиной 16, а выход подключен к первому входу триггера

17. Выход БВС 10 через четвертый блок 18 памяти соединен с первым входом БВСП 19, второй вход которого подключен к выходу второго шинного коммутатора 20, а выход— к входу пятого блока 21 памяти, выход которого соединен с первой выходной шиной 22 и первым входом компаратора 20, второй вход которого через шестой блок 23 памяти подключен к выходу умножи геля, вход которого через седьмой блок 24 памяти соединен с четвертой входной шиной 25. Первый вход блока 26 управления соединен с пятой входной шиной "Пуск" 27 и первым входом первого элемента ИЛИ 28, второй вход подключен к выходу элемента И 29, Первый выход блока управления подключен к первому входу второго элемента

ИЛИ 30 и второму входу БВК 4, второй выход — к второму входу блока деления, третий — через элемент ИЛИ 30 к вторым входам блоков 2, 24 и 7 и третьим входам умножи5 телей и 6 и второму входу блока 23, четвертый — к третьему входу блока 7, третьему входу БВР 8 и первому входу элемента ИЛИ

31, пятый — к первому входу элемента ИЛИ

32, шестой — к второму входу блока 23, к

10 третьему входу БВСП 19 и первому входу элемента И ЗЗ, седьмой — к третьим входам коммутаторов 20 и 11 им первому входу элемента И 29, восьмой — через элемент ИЛИ

31 к вторым входам блока 13 и 12, через

15 элемент ИЛИ 28 — к второму входу триггера

17, девятый — через элемент ИЛИ 32 к второму входу блока 18, к третьему входу узла сравнения 15 и третьему входу блока 12, к второму входу БВСП 14, третьему входу

20 БВ С 10 и третьему входу блока 13, а десятый выход через элемент ИЛИ 34 — к второму входу 0лока 21 и через элемент ИЛИ 33 к третьим входам блока 21 и 18. Выход триггера 17 соединен с второй выходной шиной

25 35 и вторым входом элемента И 29. Второй вход элемента ИЛИ 34 подключен к шестому входу 36 чтения результата.

Блок БВК 4 вычисляет коэффициент ,и согласно алгоритму

30 DIMENSION A(N,N), B(N,N)

ЯМАХ = 0

DO1 1=1,N

B(i) =0

D02j=1,N

35 B(i) = B(i)+ ABS(A(i, 2 CONTINUE

IF (SMAX LT B(i)SMAX = B(i)

1 CONTINUE

PRINT *, ЯМАХ

40 END

Блок БВК 4 содержит генератор 37 тактовых импульсов, закольцованный сдвигающий регистр 38, сумматор 39, регистры 40 и

41, узел 42 сравнения, триггеры 43 и 44 и

45 элементы И 45и 46.

Блок 4 работает следующим образом.

По сигналу от внешнего источника происходит запуск генератора 37. вырабатывающего две серии импульсов: прямую и

50 инверсную Q и Q, По каждому импульсу серии генератора 37 на вход сумматора 39 поступает элемент строки обрабатываемой матрицы, и на выходе сумматора формируется результат сложения этого элемента с

55 текущим значением промежуточной суммы, хранящейся в буферном регистре 40. Через и импульсов íà (n+1}M выходе сдвигового регистра 38 появляется единичный потенциал (результата продвижения единицы, занесенной в первый разряд сдвигового

1721613

14 регистра 38), по которому триггер 43 переходит в единичное состояние и через первый элемент И 45 запрещает перепись информации в буферный регистр 40, и по нему также осуществляется сравнение схемой 42 сравнения значения чисел, занесенных в буферный регистр 41 максимума.

Если число в регистре 40 больше числа в регистре 41, то узел 42 сравнения устанавливает триггер 44 в единичное состояние и тем самым разрешает прохождение (и+2)-го импульса переписи информации из регистра 40 в регистр 41. Если число в регистре 40 меньше числа в регистре 41, триггер 44 остается в нулевом состоянии, и информация в регистре максимума не обновляется. По (n+3)-му импульсу регистр 40 и триггер 44 обнуляются, no(n+4)-му импульсутриггер43 переходит в нулевое состояние, и в первом разряде сдвигового регистра устанавливается единица, т.е. блок готов к вычислению очередного значения суммы членов строки матрицы и определению текущего максимального значения. По прошествии и циклов, т,е. вычисления и сумм по модулю строк матрицы, в регистре максимума хранится значение,и.

Блок БВР 8 содержит управляемый генератор 4, кольцевой сдвиговый регистр 48 (n+1-разрядный), шинный коммутатор 49 и блок 50 вычитания.

Блок 8 работает следующим образом.

В исходном состоянии при.отсутствии управляющего сигнала на входе генератора

47 в сдвиговом регистре 48 в первый разряд занесена единица, остальные разряды находятся в нулевом со тоянии. По единичному сигналу с первого разряда сдвигового регистра шинный коммутатор 49 устанавливается в положение, подключающее к выходной шине число "1,0", По сигналу с блока управления генератор переходит в автоколебательный режим. По каждому импульсу с него единица, занесенная в первом разряде сдвигового регистра, перемещается в соседний старший разряд. Шинный коммутатор подключает шину с числом "О, О..;0" к входу вычитателя тогда, когда на управляющем входе имеется нулевой сигнал (на первом разряде сдвигового регистра присутствует нулевой сигнал). Таким образом, через каждые и тактов генератора шинный коммутатор подает число "1,0" на вход вычитателя. При этом по каждому такту генератора на второй вход вычитателя посту2 пает текущий элемент матрицы — А. ,И

Процесс вычисления прекращается по появлению запрещающего сигнала на входе генератора 47.

В состав блока 26 управления входят генератор 51 тактовых импульсов, элементы

И 52 — 54, триггер 55, сдвигающий регистр 56, закольцованный сдвигающий регистр 57, триггер 58 и элемент ИЛИ 59.

Выход генератора 51 через первый вход элемента И 52 соединен с первыми входами элементов И 53 и 54, а второй вход элемента

И 52 соединен с выходом триггера 55, первый вход которого соединен с шиной "Останов", а второй — с шиной "Пуск" и установочными входами регистров 56,57 и триггера 58, первый выход которого соединен с вторым элементом И 53, а второй — с вторым входом элемента И 54, выход которого через первый вход элемента ИЛИ 59 подключен к второму входу регитстра 57, первый выход которого соединен с собственным вторым входом, а второй, третий и четвертый выходы. регистра 57 являются седьмым, восьмым, девятым и десятым выходами блока управления, причем второй выход регистра 57 соединен с вторым входом триггера 58. С первого по шестой выходы блока 26 управления соединены соответственно с первого по шестой выходами регистра 56, второй вход которого подключен к выходу элемента И 53, а седьмой выход — к элементу ИЛИ 59.

Блок управления функционирует по указанному алгоритму.

Блок БВС 10 аналогичен блоку БВР 8, однако вместо блока 50 вычитания используется сумматор, Блоки БВСП 14 и БВСП 19 обеспечивают вычисление произведений матрицы на матрицу и матрицы на вектор по известным правилам.

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

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

В блоки 2 и 24 памяти заносятся значения матрицы А и вектора b, а коммутаторы

11 и 20 установлены в положение, обеспечивающее подключение соответственно БВР

8 и блока 23, По команде "Пуск" триггер 17 устанавливается в исходное положение, блок 26 управления вырабатывает серию тактов, По первому такту в БВК 4 опреде16

1721613

15 ляется число,и, по второму такту в блоке 5 деления определяется величина 2/и, По третьему такту в блоке 3 умножения вычисляется — А, информация из которого реги2

/И стрируется в блоке 4 памяти. Одновременно по третьему такту осуществляется умножение блоком 6 вектора, поступающего из блока 24, на число 2/и, Результат через коммутатор заносится в блок 23. По четвертому такту матрица, хранящаяся в блоке 7, вычитается иэ матрицы Е с помощью блока БВР

8, а результат через коммутатор 11 заносится в блок 13 памяти. По пятому такту в БВСП г

14 вычисляются элементы матрицы В, которые поочередно заносятся в блок 12 памяти и сравниваются одновременно с допуском точности вычисления е в узле 15 сравнения, который равен единице, если член )Ьц! матрицы В меньшее(6), и равен нулю, если 1ЬЦ l е (7). Таким образо, если хотя бы один из членов ЬЦ! > е, то триггер

17 не изменяет своего состояния.

Одновременнго по пятому такту в БВС

10 вычисляется сумма Е+В, которая заносится в блок 18. По шестому такту значение матрицы Е+В в БВСП 19 умножается на век2— тор — Ь, и результирующий вектор заносит,И ся в блок 21, Если триггер 17 остается в нулевом положении, то по седьмому такту элемент И 29 не останавливает блок 26, и коммутаторы 11 и 20 устанавливаются во второе свое состояние, подключая соответственно выход блока 12 к входу блока 13 и выход блока 21 к входу БВСП 19. По восьмому такту матрица В, записанная в блоке 12, 2 переписывается в блок 13, и через элемент

ИЛ И 28 подтверждается установка триггера

17 в исходное положение.

llo девятомУ такту в БВС 10 вычисляется матрица В + Е, которая заносится в блок 18, и одновременно в БВСП 14 вычисляется матрица В, которая заносится в

4 блок 12, одновременно в схеме 15 сравнения все члены ее сравниваются по модулю с е, По десятому такту в БВСП 19 осуществляется умножение Е+В на вектор(Е+В )х

4 2 х (Е + В) — Ь, и результат заносится в блок

/4

21. В зависимости от результата состояния триггера 17, который регистрирует факт окончания вычисления в случае, если выполняется условие (6), на выходной шине 35 вырабатывается признак окончания вычислений, по которому информация, записанная в блок 21, может сниматься с выхода 22 устройства по сигналу с управляющего входа блока 36. Если условие (7) выполняется, то проводится очередная последовательность вычислений до выполнения условия (6).

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

10 десятые выходы блока 26 управления, не произойдет выполнения условия (6).

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

СЛАУ с точностью до е = 10

"2х1+ х2 = 3, 20 1 х1+хг=2.

В известном устройстве потребуется произвести следующие вычисления:

N N А2 2

25 А =уе бт f (Е At+ 2!

О О

А N2

+ ...) dt=(EN "2 -)+ !

ЦЗ - A N4 N5 E А !6

30 (2!3 4.3!) (4!5 6 5!) .,(Е А! )дэ

9 8! 10 9!

Если принять время сложения t (такт), время умножения — 5t, то время вычисления по данной формуле составит примерно 365т.

Чтобы получить решение СЛАУ, надо полученную обратную матрицу умножить на вектор Ь = (3,2}, Следовательно, еще надо произвести четыре умножения и два сложения. Время решения СЛАУ будет Т = 365t+

+ 22т = 387t, Большой факториал может вызвать переполнение разрядной сетки устройства еще до окончания вычислений при заданной точности.

В известном устройстве значительная память для хранения коэффициентов.

Кроме того, необходимо вмешательство пользователя в вычислительный процесс для определения числа N-интервала интегирования и числа членов подынтегрального выражения (1).

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

".flAY (1) при точности вычислений с = 10

-г требуется произвести следующие действия;

1721613

18 г г) з) о г) я:= ( ь:- (Е:= (8:=Š— — А

-0.333 -0.667 в = ( вг= ( вз= (о.ввв о) 81:=82

Â2:= В

83:= В ь:- ()

Х: =(Е+ В) — Ь

3 х= х2 (=(Е+ Вв)(Е+ 84)(Е+ В )(E+ В) — b, /4 что потребует времени примерно Т 256с

Это объясняется черезвичайно быстрой скоростью сходимости вычислительного алгоритма:

X ° Е+8 ) (E+ B) 3 Ь

0.691

X:= Е+В) (E+Â) (Е+В) 3 Ь (о.g)

X:=(Е+ Вв)(Е+ В )(Е+ В ) (Е+ В) — Ь

= 0.%1

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

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

1721613

19 подключены соответственно к информационным входам второй группы второго коммутатора, выходы шестого блока памяти — к информационным входам второй группы первого коммутатора и к выходам результа- 5 та устройства, входы элементов единичной матрицы которого подключены к информационным входам второй группы блока вычисления суммы матриц и блока вычисления разности матриц, входы точности решения 10 устройства подключены соответственно к информационным входам второй группы узла сравнения, выход которого подключен к входу установки в "1" триггера, выход которого подключен к выходу признака завер- 15 шения решения системы линейных алгебраических уравнений устройства и к первому входу элемента И, выход которого подключен к входу останова блока управле20 ния, вход признака считывания результата устройства — к первому входу первого элемента ИЛ И, выход которого — к входу чтения шестого блока памяти, вход запуска устройства подключен к входу запуска блока управления и к первому входу второго эле- 25 мента ИЛИ, выход которого подключен к входу установки в "О" триггера, первый выход блока управления — к управляющему входу блока вычисления коэффициентов и к первому входу третьего элемента ИЛИ, вы- 30 ход которого подключен к входу записи-чтения первого блока памяти, второй выход блока управления — к управляющему входу блока деления, третий выход — к управляющим входам первого и второго умножите- 35 лей, к входам чтения третьего и четвертого блоков памяти, к входу записи-чтения второго блока памяти и второму входу третьего элемента ИЛИ, четвертый выход — к входу записи третьего блока памяти, к управляю- 40 щему входу блока вычисления разности матриц и к первому входу четвертого элемента

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

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

1721613

22 рого — к входу записи-считывания второго регистра, выходы которого подключены к информационным входам второй группы узла сравнения и к выходам блока, управляющий вход которого подключен к входу запуска генератора тактовых импульсов, инверсный выход которого — к первому входу второго элемента И, выход которого подключен к входу записи-считывания первого регистра, прямой выход генератора тактовых импульсов подключен к входу синхронизации сумматора и к входу сдвига закольцованного сдвигающего регистра, первый информационный выход — к входу синхронизации узла сравнения и к входу установки в "1" второго триггера, выход ко5 торого подключен к второму входу второго элемента И, второй информационный выход закольцованного сдвигающего регистра — к второму входу первого элемента И, третий информационный выход — к входам установ10 ки в "0" первого регистра и первого триггера, четвертый информационный выход — к входу установки в "0" второго триггера.

1721613, 1721613

78Я lO

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

Техред M.Ìîðãåí Tàë

Редактор И. Шмакова

Корректор М. Кучерявая

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 954 Тираж Подписное

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

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