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

 

Изобретение относится к вычислительной технике и может быть использовано автономно или в комплексе с ЦВМ для решения систем линейJT ных алгебраических уравнений. Цель изобретения - увеличение точности решения. Поставленная цель достигается тем, что устройство содержит вход 1 запуска устройства, блок 2 формирования начальных значений матрицы, блок 3 коммутации, блок 4 формирования промежуточных результатов , регистры 5-7 хранения промежуточных результатов, блок 8 памяти констант, арифметический блок 9, блок 10 управления, вход 11 матрицы значений коэффициентов, вход 12 вектора значений правой, части системы уравнений, выход 13 результата устройства. Увеличение тофюсти обеспечивается для случаев, когда элементы матрицы уравнения имеют величины различного порядка. 11 ил. с S (Л оо ю ел СП

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

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

РЕСПУБЛИК

„.90„„1325507 A 1 (511 4 G 06 Р 15/324

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

Il0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Ф °

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3816277/24-24 (22) 22.11.84 (46) 23.07.87. Бюл. К 27 (71) Харьковский авиационный институт им. Н. Е. Жуковского (72) В. М. Момот, А. А. Жалило и С. А. Безверхий (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 805336, кл. G 06 Р )5/324, 1979.

Авторское свидетельство СССР

Р 624234, кл. G 06 F 15/324, 1977. ных алгебраических уравнений. Цель изобретения — увеличение точности решения. Поставленная цель достигается тем, что устройство содержит вход 1 запуска устройства, блок 2 формирования начальных значений матрицы, блок 3 коммутации, блок 4 формирования промежуточных результатов, регистры 5 — 7 хранения промежуточных результатов, блок 8 памяти констант, арифметический блок

9, блок 10 управления, вход 11 матрицы значений коэффициентов, вход 12 вектора значений правой, части систе" мы уравнений, выход 13 результата устройства, Увеличение тоФности обеспечивается для случаев, когда элементы матрицы уравнения имеют величины различного порядка. 11 ил. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано автономно или в комплексе с ЦВМ для решения систем линей0ПИСАНИК ИЗОВГЕтКНиЯ "

l 325507

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

На фиг. 1 представлена структурная схема устройства; на фиг, 2 блок формирования начальных значений матрицы; на фиг. 3 — блок комму" тации; на фиг. 4 — блок формирования промежуточных результатов„ на фиг. 5 — 15 блок управления; на фиг. 6 — узел формирования уменьшаемых; на фиг, 7 " узел формирования первых сомножителей; на фиг, 8 " узел формирования вторых сомножителей; на фиг ° 9 — y0 узел формирования признака режима; на фиг. 10 — арифметический блок; на фиг. 11 - временная диаграмма работы блока управления.

Устройство содержит вход 1 запус- 25 ка устройства, блок 2 формирования начальных значений матрицы, блок 3 коммутации, блок 4 формирования промежуточных результатов, с первого по третий регистры 5-7 хранения промежу- 30 точных результатов, блок 8 памяти констант, арифметический блок 9, блок

10 управления, вход ll матрицы значений коэффициентов системы линейных алгебраических уравнений, вход 12 вектора значений правой части системы линейных алгебраических уравнений, выход 13 результата устройства, внутренние информационные шины 14-27, выходы 28-31 блока управления, Бпок 2 формирования начальных значений содержит элементы 32 задержки и сумматоры 33„-33,, Блок 3 коммута.ции содержит коммутатор 34, мультиплексор 35, узел 36 формирования уменьшаемых, узел 37 формирования первых сомножителей, узел 38 формирования вторых сомножителей, внутреннюю информационную шину 39. Блок 4 формирования промежуточных результатов содержит два сумматора 40 и 41, два умножителя 42 и 43, делитель 44, Блок

10 управления содержит генератор 45 тактовых импульсов, ждущий мультивибратор 46, с первого по третий триггера 47-49, элемент И 50, элемент НЕ 51, счетчик 52, узел 53 элементов сравнения, узел 54 формирования признака режима, Узел 36 формирования уменьгде А " матрица коэффициентов размерности пхп, состоящая из элементов а; (i=1 и, j=1, и);

 — вектор-столбец размерности и, составленный из элементов правых частей Ь;;

Х вЂ” вектор-столбец решения размерности и составленный иэ элементов х„, Эта система при det А ф 0 имеет для любых правых частей уравнений однозначно определенное решение

Х=(х„, ° ...х„) . Для отыскания этого . т вектор-решения воспользуемся обратной матрицей А, В этом случае векторI решение Х=А Б вычисляется простым перемножением матриц, 1

Для отыскания обратной матрицы А реализован алгоритм обращения матрицы, согласно которому для вычисления матрицы А необходимо провести выА (о1 А(1l Aé) (a1 ...,А 1, где А (= А-Е, а Š— единичная матрица и (ln-1) (m-1)

;щ е 1п1 (в-11 а ) ) 1 ф ш (т- 1

1+ а,„ (m-1 ) а (Д

М1 (11 9

+ a

* m, rpe d = 0 . (i, j, m = l n). (1,m= j т

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

Пусть исходная система имеет вид шаемых содержит и< мультиплексоров

55. Узел 37 формирования первых сомножителей содержит и мультиплексоров 55. Узел формирования вторых сомножителей содержит п мультиплексоров 55, Узел 54формирования приэнакарережима содержит Р элементов НЕ 56, где Р=

= Г1од п ), элемент И-НЕ 57. Арифметический блок 9 содержит умножитель 58 и сумматоры 59, Устройство предназначено для решения системы линейных алгебраических уравнений вида

1325507

021203110, 10 которая по шине 39 поступает на входы мультиплексора 35 и блоков 36 — 38.

К выходу блока 35 подключена шина, номер диагонального элемента которой совпадает с номером шага вычислений переданного по шине 19 управления из блока 10 управления, На первом шаге на шину 22 передано число О. Последовательность чисел по шине 39 поступает на вход блока 36, на выходе которого сформирована на первом шаге последовательность чисел

00203 1 10.

25 Последовательность чисел с выхода коммутатора 34 поступает на вход блока 37, на выходе которого на первом шаге сформирована следующая последовательность чисел

021203110, которая по шине 18 поступает на информационные входы блока 3, в частности на входы коммутатора 34.

Работа устройства синхронизиру- 30 ется блоком 10 управления и начинается подачей сигнала на вход 1 устройства. При этом устанавливается в нуль счетчик 52, устанавливаются в нулевое состояние RS-триггер 49, а в единичное состояние RS-триггер 47.

Перевод RS-триггера 48 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора.45 тактовых 40 импульсов. В результате с выхода RS,триггера 48 единица поступает на один из входов элемента И 50, обеспечивая прохождение синхроимпульсов, поступающих на второй ее вход от ждущего 4б мультивибратора 46. С выхода элемента И 50 синхроимпульсы поступают на счетный вход счетчика 52. Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений.

На первом шаге вычисления с выхода счетчика 52 поступает в двоичном коде "1" на шину 19 управления и на вход блока 54, в соответствии с законом ра-55 боты которого на его выходе на первом шаге сформирован "0" ° На всех последующих шагах на выходе 28 присутствует

"!". С выхода коммутатора 34 передана з

2х, + х +Зх = 2Ь х + х + х = 2Ь, т.е. АХ = В, 1 2 1 где А = 2 1 3 — матрица коэффици1 1 1 ентов системы;

В = (1 2 2) — вектор-столбец правых частей сис-. темы.

Исходный вектор-столбец поступает через вход 12 в арифметический блок

9, а исходная матрица в виду последовательности ее элементов, полученная разложением по строкам:

1 2 1 2 1 3 1 1 1 поступает на вход блока 2 где из диагональных .элементов матрицы вычитается единица, поступающая по шине

16 первой константы из блока 8 памяти констант. На выходе блока 2 сформирована последовательность чисел последовательность чисел о шины 18 при сигнале на выводе 28, равном "0" (первый шаг вычислений), или последовательность чисел с шины 17 при сигнале на выводе 28, равном "1", т,е. на первом шаге на выходе коммутатора

34 выдается последовательность чисел

Кроме того, последовательность чисел по шине 39 также поступает на вход блока 38, на выходе которого на первом шаге вычислений появляется последовательность чисел

0 2 1.

По шине 22 с выхода мультиплексора

35 число 0 на первом шаге поступает на вход сумматора 40, где складывается с единицей, поступающей по шине

14 второй константы блока 8, преобразуя в обратную величину, и умножается на "1", поступающую по шине 16 первой константы, В итоге на первом шаге с выхода блока 44 поступает число -1. !

С выходов блока 37 и блока 38 по шинам 24 и 25 последовательность чисел поступает на входы блока 2, где произвЬдится их взаимное перемножение, в результате чего на выходе на первом шаге сформирована последовательность чисел

021042021, которая с выхода блока 42 поступает на вход блока 3, в котором все числа последовательности умножаются на

5 1325507 число, поступающее с выхода блока 44, в в результате этого на первом шаге с 6 выхода блока 43 выдана последователь- р ность чисел э то время как по входу 30 на регистр поступает управляющий сигнал "1", азрешающий чтение информации из того регистра. Период следования синхроимпульсов с выхода ждущего муль тивибратора 46 выбирается таким образом, что за время существования низкого перепада напряжения на его выходе полностью завершаются вычисления на данном шаге и запись результата в регистр 5. При появлении высокого потенциала на выходе элемента И 50 на вход регистра 5 поступает "1", а на второй - "0", т.е. происходит перезапись информации из первого регистра во второй, При появлении следующего синхроимпульса выдается разрешение на чтение результата из регистра 6 и на запись результата следующего шага вычисления в регистр 5, Количество шагов вычислений равно порядку обращаемой матрицы.

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

Влок

° » аб бм

Ш

021203110

l "2 l 2-4! I" 1-1

2 021203110

34 021203110

2 52 1111 4

ЭЗ 3333 3

52 11

33 33

1 2

12-IOliOI-1"I

36 100203110

3 3

5 а 1

3 3

"21-1

t 2

1 l

3 3

021

1

42 02 !04202 I

"48"22-4 1-24" i

2 2 4 1 2 4 !

5 52011 4

3 3 3 3 3 311"4

4 8

3 3

43 0-2"19-4"20"2-1

3 3 3 3 3 3 3

52. 11 а

33 ЗЗ

1 2

41 1-2-12" 41! -1-1

-2"1510-Ill-3

3 3 3

I 1 4

52 l!

1 2

В Ь Ф

3 3

5 1-2-12-4!1-I-I

-2-1510-111-3

33 3333 3.

-2-I!5!0""111-3

0- 2 — 1 0 — 4- 2 0 — 2 - I которая складывается в соответствии с номерами с последовательностью чисел, поступающей по шине 23, в сумматоре 41, на выходе которого на первом шаге сформирована последовательность чисел

1 - 2 - I 2 - 4 1 1 - 1 - 1, Данная последовательность чисел с !5 шины 26 поступает на входы регистра 5 хранения промежуточных результатов, который служит для хранения развязки между собой шагов вычислений и устранения эффекта "гонок". Во время вы- 20 числения на каком-либо шаге на регистр 5 по выводу 29 поступает управляющий сигнал "0" с выхода элемента

И 50 блока управления, разрешающий запись информации в данный регистр, 5 520 l 411 4

9 9 9 9 9 9 3 3 3

1325507

На каждом шаге вычислений в узле

53 происходит сравнение номера шага вычисления, поступающего с выхода счетчика 52 и числа "4" (в общем слу5 чае и+1, где n — порядок матрицы), поступающего по шине 20 четвертой константы иэ блока 8 памяти.

В результате окончания последнего третьего шага вычисления в ре- 10 гистр 6 записана последовательность чисел

- 2 - 1 5 1 0 - 1 1 1 - 3

1 представляющая элементы обращенной матрицы А . В момент появления следующего четвертого синхроимпульса на выходе элемента И 50 на управляющий вход регистра 6 поступает сигнал чтения. Номер четвертого синхроимпульса поступает также на вход узла 53, в результате чего на выходе сформирован управляющий импульс, который переводит триггер 49 в единичное состояние, а также переводит в нулевое 25 состояние триггеры 47 и 48, что соответствует запиранию блока 10 управления.

Сигнал "1" на разрешение чтения с выхода RS-триггера 49 по шине 31 30 поступает на управляющий вход регистра 7. Происходит перезапись информации с регистра 6 в регистр 7.

Информация из регистра 7 поступает по шине 27 на входы умножителей

58 арифметического блока, на другие входы которых поступает с входа 12 информация о вектор-столбце правых частей уравнения с выходов перемножителей поступают на входы соответству- 40 ющих сумматоров 59, сигнал на выходе которых и представляет искомый вектор решения, который поступает на выход 13 результата устройства.

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

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

i-му входу второй группы блока формирования начальных значений матрицы и к i-му входу первой группы блока формирования промежуточных результатов, ;i-й выход третьей группы блока памяти констант подключен к i-му информационному входу первой группы блока коммутации и к i-му входу второй группы блока формирования промежуточных значений, i-й выход четвертой группы блока памяти констант подключен к i-му информационному входу второй группы блока коммутации, первый, второй и третий выходы блока управления подключены к входам считывания соответственно первого, второго и третьего регистров хранения промежуточных результатов, четвертый выход блока управления подключен к управляющему входу блока коммутации, i-й выход группы блока управления подключен к i-му информационному входу третьей группы блока коммутации, j-й выход; где j=l,„,n, блока формирования . начальных значений матрицы подключен к j-му информационному входу четвертой группы блока коммутации, j-й вы- ход блока формирования промежуточных результатов подключен к информационному входу j-го разряда первого регистра хранения промежуточных результатов, выход j-го разряда первого регистра хранения промежуточных резуль" татов подключен к j-му информационному входу 1-го разряда второго регистра хранения промежуточных результатов, выход j-го разряда второго регистра хранения промежуточных результа тов подключен к j-му информационному входу пятой группы блока коммутации и к информационному входу j-ro

1 32550 7 разряда третьего регистра хранения промежуточных результатов, выход 1 -rо разряда третьего регистра хранения промежуточных результатов подключен к j-му информационному входу второй группы арифметического блока, j-й выход групп с первой по четвертую выходов блока коммутации подключен к

j-му входу соответственно групп с третьей по шестую входов блока формирования промежуточных результатов, выходы арифметического блока подключены к выходам результата устройства, при этом блок формирования начальных значений матрицы содержит п сумматоров и п -и элементов задержки, первый информационный вход i-го сумматора подключен к ((— 1}n+ij-м входам первой группы блока формирования начальных значений матрнцы, второй информационный вход i-ra сумматора подключен к i-му входу второй группы блока формирования начальных значений матрицы, входы элементов с (kn+

+1)-ro no (k+1}n-и, rye k=6,1,... ...,п, задержки подключены соответственно к входам с (1п+! +2)-го по ((k+1)n+k+I)-й первой группы блока формирования начальных значений мат-рицы, выход i-ro сумматора подключен . к I.(i-l)n+i)-му выходу блока формирования начальных значений матрицы, а выходы с (kn+k+2)-ro по f(k+1)n+

+k+1J-й блока формирования начальных значений матрицы подключены к выходам элементов задержки соответственно с (kn+1)-го по (k+1)n-й, при этом блок коммутации содержит коммутатор, мультиплексор, узел формирования уменьшаемых, узел формирования первых сомножителей, узел формирования вторых сомножителей, управляющий вход блока коммутации подключен к управляюще— му входу коммутатора, i-й информационный вход первой группы блока коммутации подключен к i-му входу первой группы узла формирования уменьшаемых и к i-му входу первой группы узла формирования первого сомножителя, х-й информационный вход второй группы блока коммутации подключен к i-му входу второй группы узла формирования уменьшаемых, х-й информационный вход третьей группы блока коммутации подключен к i-му управляющему входу мультиплексора блока коммутации, к х-му входу третьей группы узла формирования уменьшаемого, к i-му входу

55 второй группы узла формирования уменьшаемых подключен к первому информационному входу мультиплексоров с ((1-1)и+1)-го по ((i-1)n+i-1) -й и с ((1-l)n+i+ lf -го по in-й узла формирования уменьшаемых, j-й вход третьей группы входов узла формирования уменьшаемых подключен к управляющему входу j-ro мультиплексора узла формирования уменьшаемых, 1-й вход четвертой группы узла формирования уменьшаемых подключен к второму информационному входу j-го мультиплексора узла формирования уменьшаемых, выход j-го мультиплексора узла формирования уменьшаемого подключен к j-му выходу узла формирования уменьшаемых, при этом узел формирования первых сомножителей содержит п мультиплексоров, i-й вход первой группы узла формирования первых сомножителей подключен к первому информационному входу i-го мультиплексора узла формирования первых сомножителей, 1-й вход второй группы узла формирования первых сомножителей и к 1.-му входу первой группы узла формирования вторых сомножителей, j-e информационные входы четвертой и пятой групп блока коммутации подключены к j ì информационным входам соответственно первой и второй групп коммутатора блока коммутации, 1-й выход коммутатора блока коммутации подключен к 1-му информационному входу мультиплексора, блока коммутации, к j-му входу четвертой группы узла формирования уменьшаемых, к 1-му входу третьей группы узла фор-, мирования первых сомножителей, к j-му входу второй группы узла формирования вторых сомножителей, выходы мультиплексора блока коммутации подключены к выходам первой группы блока коммутации, выходы узла формирования уменьшаемых подключены к выходам второй группы блока коммутации, выходы узла формирования первых сомножителей подключены к выходам третьей группы блока коммутации, выходы узла формирования вторых сомножителей подключены к выходам четвертой группы блока коммутации, при этом узел формирования уменьшаемых содержит и мультиплексоров, 1-и вход первой группы узла формирования уменьшаемых подключен к первому информационному входу

f(i-l)n+i)-ro мультиплексора узла формирования уменьшаемых, i-й вход

1325507! 2 второй группы узла формирования пер" вых сомножителей подключен к управляющему входу i-го мультиплексора узла формирования первых сомножителей, 1-й

5 информационный вход i-го мультиплексора, где 5=2,...,n+1, узла формирования первых сомножителей подключен к ((i-1)и+3-1)-му входу третьей группы узла формирования первых сомножителей, выход 1-го мультиплексора узла формирования первых сомножителей подключен к i-му выходу узла формирования первых сомножителей, при этом узел формирования вторых сомножителей содержит и мультиплексоров, i-й вход первой группы узла формирования вторых сомножителей подключен к управляющему входу i-го мультиплексора узла формирования вторых сомножителей, i-й информационный вход r-го, где r=l,...n, мультиплексора узла . формирования вторых сомножителей подключен к ((х-1)п+г1-му входу второй группы узла формирования вторых со- 25 множителей„ выход i-го мультиплексора узла формирования вторых сомножителей подключен к i-му выходу узла формирования вторых сомножителей, при этом блок формирования промежуточных З0 результатов содержит два сумматора, два умножителя, делитель, входы пер- вой группы, входы второй группы, входы третьей группы, входы четвертой группы, входы пятой группы и входы шестой группы блока формирования промежуточных результатов подключены к одноименным информационным входам соответственно первой группы делителя, первой группы первого сумматора, вто- 40 рой группы первого сумматора, первой группы второго сумматора, первой группы первого умножителя и второй группы первого умножителя блока формирования промежуточных результатов, выхо- 45 ды первого сумматора подключены к одноименным информационным входам второй группы делителя, выходы которого подключены к одноименным информационным входам первой группы второго умножителя блока формирования промежуточных результатов, выходы первого умножителя блока формирования промежуточных результатов подключены к одноименным информационным входам второй группы второго умножителя, выходы которого подключены к одноименным информационным входам второй группы второго сумматора блока формирования промежуточных результатов, выходы второго сумматора блока формирования проме-. жуточных результатов подключены к одноименным выходам блока формирования промежуточных результатов, при этом блок управления содержит генератор тактовых импульсов, три триггера, ждущий мультивибратор, узел формирования признака режима, узел элементов сравнения, счетчик, элемент И, элемент НЕ, вход запуска блока управления подключен к входу установки в "l" первого триггера блока управления, к входу установки в "0" второго триггера блока управления и к входу установки в "0" счетчика блока управления, i-й вход режима блока управления подключен к 1-му входу первой группы узла элементов сравнения блока управления, q-й выход, где q=l

tlog и|, счетчика блока управления подключен к q-му входу второй группы узла элементов сравнения, к q-му входу узла форьырования признака режима блока управления и к q-му выходу группы блока управления, выход первого триггера блока управления подключен к входу установки в "1" третьего триггера блока управления, выход генератора тактовых импульсов блока управления подключен к входу ждущего мультивибратора блока управления и к счет- ному входу третьего триггера блока управления, выход узла элементов сравнения блока управления подключен к входу установки в "0" первого триггера блока управления, к входу установки в "1" второго триггера блока управления и к входу установки в "0" третьего триггера блока управления,выход ждущего мультивибратора блока управления подключен к первому входу элемента И блока управления, выход третьего триггера блока управления подключен к второму входу элемента И блока управления, выход элемента И блока управления подключен к счетному входу счетчика блока управления, к входу элемента НЕ блока управления, выход элемента НЕ блока управления подключен к первому выходу блока управления, выход элемента И блока управления подключен к второму выходу блока управления, выход второго триг" гера блока управления подключен к третьему выходу блока управления, выход узла формирования признака режима блока управления подключен к

1З четвертому выходу блока управления, при этом узел формирования признака режима содержит (log,п)-1 элементов

НЕ, элемент И-НЕ, первый вход узла формирования признака режима подключен к первому входу элемента И-НЕ узла формирования признака режима, s-й вход, где s 2 flog и ), узла

3 формирования признака режима подклю325507

14 чен к входу {s 1) — го элемента НЕ узла формирования признака режима, выход {s l) ro элемента НЕ узла формирования признака режима подключен к

s-му входу элемента И-НЕ узла формирования признака режима, выход элемента И-НЕ узла формирования признака режима подключен к выходу узла

1ð формирования признака режима.

1325507

22

29

ЗР

Фиа б

I 325507

25, 1325507

12

52, 20

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

Редактор Н. Бобкова Техред И.Попович

Корректор Т. Колб

Заказ 3112!46 Тираж 672

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

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

Подписное

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