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

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

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

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

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

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

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

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

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

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

5 информационным входам второй группы первого умножителя и к информационным входам первой группы второго умножителя, информационные входы второй группы которого подключены соответственно к выхо0 дам второго блока памяти, выходы первого и второго умножителей подключены соответственно к информационным входам третьего и четвертого блоков памяти, выходы которых подключены соответственно к

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

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

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

5 блока вычисления скалярных произведений подключены к информационным входам .первой группы узла сравнения и к информационным входам первой группы узла сравнения и к информационным входам

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

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

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

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

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

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

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

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

Поясним алгоритм работы предлагаемого устройства.

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

Ах Ь,(1)

где А - положительно определенная квадратная матрица;

b - заданный вектор;

х - искомый вектор решения системы.

Сделав преобразование системы (1), получают

(2)

(Е-В)х -§- Ь ,

А

где/г - первая норма матрицы А; B-E-Jj-А. .

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

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

Умножим левую часть формулы (2) на матрицу (Е+В):

(Е+В)(Е-В}х (Е+В)

или

(Е-В2)х (Е+В).

(3)

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

В2 Ј, (п 2,3,.. .)

выполняется, то процесс вычисления останавливается, если не выполняется, то снова умножают части (3) на Е+В2, получают

(Е-В4)х(Е+В2ХЕ+В), решение имеет вид

х (Е+В2ХЕ+В) -2- Ь.

Таким образом,

х (Е+В2П-1)...(Е+В2)-|-Ь. (4)

г

Оценим скорость сходимости вычисли- тельного процесса. Пусть п 0:

х (Е-В) 1 -Ј- Ь; 3Z (Е+ В+ В2) Ј Ь,

-п

где х - приближенное решение СЛАУ. Имеем

ll-lvlir - Е - В - В2|| b|l

Ц

IIВ IP

-НЕ-ВЦ/г Пусть п 1:

Ь|

j2r1

о тттт

х (Е-ВГ(Е+В) Ь;

xn (E+B/+B4XE+B)-Ј-b;

2 1р

|х-х1

В

3 2

E-BV

При любом п

Е + ВЦ -2-ЦЫ1 . г

Bi

3 -2

IE -В-

р пП || о

,|F|

Е -В

(5)

Вычислительный процесс (4) имеет скорость сходимости, выражаемую неравенст- 5 вом (5).

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

при --), и отсутствия необходимости вме/

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

5 Скорость сходимости вычислительного процесса весьма высока, что видно из оценки (5) (IIВ П 3 2 , || ВII 1).

Ни фиг.1 представлена структурная схеg ма устройства для решения систем линейных алгебраических уравнений; на фиг.2 - блок вычисления коэффициента (БВК)/г; на фиг.З - временная диаграмма работы БВК; на фиг.4 - блок вычисления разности матри5 цы (Е-В); на фиг.5 - пример реализации блока управления.

Устройство содержит первую входную шину элементов матрицы А, первый блок 2 памяти, первый умножитель 3, блок 4 вычисления коэффициента ц (БВК), блок 5 деления, второй умножитель 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 памяти к первому входу БВР 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 и третьим входам умножи- телей и 6 и второму входу блока 23, четвертый - к третьему входу блока 7, третьему входу БВР 8 и первому входу элемента ИЛИ

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

32,шестой - к второму входу блока 23, к 0 третьему входу БВСП 19 и первому входу элемента И 33, седьмой - к третьим входам коммутаторов 20 и 11 им первому входу элемента И 29, восьмой - через элемент ИЛИ 31 к вторым входам блока 13 и 12, через

5 элемент ИЛИ 28 - к второму входу триггера 17, девятый - через элемент ИЛИ 32 к второму входу блока 18, к третьему входу узла сравнения 15 и третьему входу блока 12, к второму входу БВСП 14, третьему входу 0 БВС 10 и третьему входу блока 13,адесятый выход через элемент ИЛИ 34 - к второму входу блока 21 и через элемент ИЛИ 33 к третьим входам блока 21 и 18. Выход триггера 17 соединен с второй выходной шиной 5 35 и вторым входом элемента И 29. Второй вход элемента ИЛИ 34 подключен к шестому входу 36 чтения результата.

Блок БВК 4 вычисляет коэффициент fi согласно алгоритму 0 DIMENSION A(N,N), B(N,N)

SMAX О

D01 i 1,N

B(i) 0

D02.J-1.N 5B(i)B(l) + ABS(A(i,j)

2 CONTINUE

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

1 CONTINUE

PRINT , SMAX 0END

Блок БВК 4 содержит генератор 37 тактовых импульсов, закольцованный сдвигающий регистр 38, сумматор 39, регистры 40 и 41, узел 42 сравнения, триггеры 43 и 44 и 5 элементы И 45 и 46.

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

По сигналу от внешнего источника происходит запуск генератора 37, вырабатывающего две импульсов: прямую и 0 инверсную Q и Q. По каждому импульсу серии генератора 37 на вход сумматора 39 поступает элемент строки обрабатываемой матрицы, и на выходе сумматора формируется результат сложения этого элемента с 5 текущим значением промежуточной суммы, хранящейся в буферном регистре 40. Через п импульсов на (п+1)-м выходе сдвигового регистра 38 появляется единичный потенциал (результата продвижения единицы, занесенной в первый разряд сдвигового

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

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

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

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

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

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

В состав блока 26 управления входят генератор 51 тактовых импульсов, элементы И 52-54, триггер 55, сдвигающий регистр 56, закольцованный сдвигающий регистр 57,

триггер 58 и элемент ИЛИ 59.

Выход генератора 51 через первый вход элемента И 52 соединен с первыми входами элементов И 53 и 54, а второй вход элемента И 52 соединен с выходом триггера 55, пер0 вый вход которого соединен с шиной Останов, а второй - с шиной Пуск и установочными входами регистров 56,57 и триггера 58, первый выход которого соединен с вторым элементом И 53, а второй - с

5 вторым входом элемента И 54, выход которого через первый вход элемента ИЛИ 59 подключен к второму входу регитстра 57, первый выход которого соединен с собственным вторым входом, а второй, третий и

0 четвертый выходы- регистра 57 являются седьмым, восьмым, девятым и десятым выходами блока управления, причем второй выход регистра 57 соединен с вторым входом триггера 58. С первого по шестой выхо5 ды блока 26 управления соединены соответственно с первого по шестой выходами регистра 56, второй вход которого подключен к выходу элемента И 53, а седьмой выход - к элементу ИЛИ 59.

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

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

5 Блоки 5ВСП 4 и БВСП 19 обеспечивают вычисление произведений матрицы на матрицу и матрицы на вектор по известным правилам.

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

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

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

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

5 11 и 20 установлены в положение, обеспечивающее подключение соответственно БВР 8 и блока 23, По команде Пуск триггер 17 устанавливается в исходное положение, блок 26 управления вырабатывает серию тактов. По первому такту в БВК 4 определяется число /, по втэрому такту в блоке 5 деления определяется величина 2/ft. По третьему такту в блоке 3 умножения вычис2ляется - А, информация из которого реги-

стрируется в блоке 4 памяти. Одновременно по третьему такту осуществляется умножение блоком 6 вектора, поступающего из блока 24, на число 2 /ft. Результат через коммутатор заносится в блок 23. По четвертому такту матрица, хранящаяся в блоке 7, вычитается из матрицы Е с помощью блока БВР 8, а результат через коммутатор 11 заносится в блок 13 памяти. По пятому такту в 5ВСП 14 вычисляются элементы матрицы В2, ко- торые поочередно заносятся в блок 12 памяти и сравниваются одновременно с допуском точности вычисления е в узле 15 сравнения, который оавен единице, если член I DI.J I матрицы В меньше е(6), и равен нулю, если I bl,j I е (7). Таким образо, если хотя бы один из членов bi,j I е, то триггер 17 не изменяет своего состояния.

Одновременнго по пятому такту в ВВС 10 вычисляется сумма Е+В, которая заносится в блок 18. По шестому такту значение матрицы Е+В в БВСП 19 умножается на век2 - тор- Ь, и результирующий вектор заноситг

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

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

2 -

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

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

ляющего входа блока 36. Если условие (7) выполняется, то проводится очередная последовательность вычислений до выполнения условия (6).

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

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

Например, пусть требуется решить СЛАУ с точностью до е. 10 :

Г2х1 + х2 3, 1, xi + Х2 2.

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

, NNЛ2 3.

A-1«/e At E-At + гг-А

о

gi+...dt (EN-ANl) +

5

0

5

0

5

0

5

+ (

+ (N3E

N9E

ANT 4 -3

-) + (.

N5E

)A4 + 6 -5)A AN1V.

9-8 10:-9

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

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

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

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

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

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

ы

Vх2)

хХ21)КЕ + В8ХЕ + В4ХЕ + В2ХЕ + В)-|-Ь,

что потребует времени примерно Т - 256t.

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

Ь:

-Г1 °1

ij

+ В2 (Е + В)-|- Ь

у 0.691 Х 0.691 J

X : КБ + В4 Е + В2 (Е + В) Ь

у Г 0.905 х 0.905J

+ + + В2(Е + В)-|-

Y- Х 0.991 J

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

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

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

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

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

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

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

2.Устройство по п.1, о т л и ч а ю щ е е- 0 с я тем, что блок управления содержит

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

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

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

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

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

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

0

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

Фиг. 1

V

W

Фие.2

ФигЛ

723456

703/0

Фиг. 5