Устройство для операций над матрицами

 

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

СОК)3 СОВЕТСКИХ сОциАлистиче ских

РЕСГ1УБЛИК (я)5 G 06 F 15/347

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4774510/24 (22) 26.12.89 (46) 23.11.92. Бюл. N. 43 (72) В.С.Попенко и С.А.Турко (56) Авторское свидетельство СССР

No 1443004, кл. G 06 F 15/347, 1987, Авторское свидетельство СССР

М 1348855, кл. 6 06 F 15/347, 1986. (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ (57) Изобретение относится к вычислительной технике и можзт быть использовано в автоматизированных системах для вычисления собственных значений и собственных векторов положительно определенных симИзобретение относится к вычислительной технике и может быть использовано в автоматизированных системах для вычисления собственных значений и собственных векторов положительно определенных симметрических матриц.

Известно устройство для операций над матрицами. содержащее N операционг ных блоков. N-1 элементов задержки и распределитель импульсов (авт.св. СССР

М 1443003, кл. G 06 F 15/347. 1987).

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

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

„„« Ы„„1777153 А1 метрических матриц. Цель изобретения— расширение функциональных воэможностей устройства за счет вычисления всех собственных значений и всех собственных векторов положительно определенных симметрических матриц. Устройство для операций над матрицами содержит матрицу из P х P вычислителей. где P — порядок квадратной матрицы, первую группу блоков деления, регистр сдвига, (P-1) групп блоков умножения, (Р-2) грУпп блоков деления, два блока памяти, (P-1) операционных блоков. (P-2) элементов задержки и распределитель импульсов, причем каждый вычислитель матрицы содержит сумматор-накопитель, сумматор и блок умножения. 9 ил. матрицу из Р x P вычислителей (где P— порядок квадратной матрицы) и группы иэ (P-1) блоков деления. причем каждый вычислитель матрицы содержит сумматор и блок умножения, выход которого подключен к входу первого слагаемого сумматора того же вычислителя матрицы, вход задания числового компонента К-ro элемента M-й строки матрицы устройства (К =- 1,, P; M =- 1„... P) подключен к входу первого сомножителя блока умножения К-го вычислителя М-й строки матрицы. выход сумматора К-ro вычислителя (К 6 Р) М-й строки матрицы подключен к входу второго слагаемого сумматора (К+1)-го вычислителя М-й строки матрицы, выход сумматора P-го вычислителя Р-го столбца матрицы является выходом собственного числа уст ройства и подключен к входу делителя всех блоков деления группы, выход сумматора М-го вычислителя (М Р

P) Р-го столбца матрицы подключен к входу делимого М-ro блока деления группы, выход

1777153 которого подключен к входам вторых сомножителей блоков умножения всех вычислителей M-ro столбца матрицы и является выходом М-й компоненты собственного вектора числа устройства, входы вторых слага- 5 .емых сумматоров всех вычислителей первого столбца матрицы являются входами задания кода единицы устройства (авт.св, СССР N 1348855, кл, G 06 F 15/347, I 986). 10

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

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

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

Поставленная цель достигается тем, что устройство для операций над матрицами, содержащее матрицу из P x P вычислителей

{где P — порядок квадратной матрицы) и первую группу из (Р - 1) блоков деления, 30 причем каждый вычислитель матрицы содержит сумматор-накопитель, сумматор и блок умножения, выход которого подключен к входу первого слагаемого сумматора того же вычислителя матрицы, вход задания чис- 35 лового компонента К-го элемента М-й строки матрицы устройства (К = 1....,Р: М = 1,...,P) подключен через сумматор-накопитель к входу первого сомножителя блока умножения К-го вычислителя М-й строки матрицы, 40 выход сумматора К-ro вычислителя (К = P)

M-й строки матрицы подключен к входу второго слагаемого сумматора (K+ 1)-го вычислителя IVI-й строки матрицы, введены (Р— 1) разрядный регистр сдвига, (P — 1) групп 45 блоков умножения по (P — i) блоков умножения в каждой группе(где i =- 1....,P — 1), (Р - 2)

rpyrlrl блоков деления по (P - i) блоков деления в каждой группе, первый блок памяти, ) второй блок памяти, (Р - 1) операционных 50 блоков,(Р-2) элементов задержки и распределитель импульсов, причем выход сумматора. К-ro вычислителя К-ro столбца матрицы, кроме выхода сумматора первого вычислителя первого столбца, подключен к 55 входу делителя всех блоков деления (Р - К+

1)-й группы, вход делимого j-го блока деления (где j = 1,...,P - i) i-й группы подключен к . выходу сумматора j-ro вычислителя (Р— i

1)-го столбца. выход J rî блока деления l é группы подключен к входу первого сомножителя J-lo блока умножения I-й группы. нходы вторых сомножителей блоков умножения 1-й группы подключены к выходу I-ro разряда регистра сдвига, тактовый вход которого подключен к выходу распределителя импульсов, выходы которого подключены также к синхронходам операционных блоков, элементов задержки, первого и второго блоков памяти. выходы j-x блоков умножения подключены к входам вторых сомножителей блоков умножения всех вычислителей

j-ro столбца матрицы, выход j-го блока деления i-й группы является выходом j-и компоненты I-ro собственного вектора и подключен к j-му информационному нходу второго блока памяти, первый вход i.1-го операционного блока подключен к I-му выходу второго блока памяти (i =- 1, Р-1), первый выход i.S-ro операционного блока подключен к (Р— i + 1)-му информационному входу второго блока памлги (S = 1, Р - 1), первый вход i,S-ro операционного блока подключен к первому выходу (i - - 1) (S — 1)-ro операционного блока (i =- 1, Р— 2, S = 2, Р =1), первый вход операционного блока Р -1,S подключен к выходу (S - 1)-ro элемента задержки (S = 2, Р— 1), вход которого подклю-. чен к второму входу (Р - 1) {S - 1)-го операционного блока, второй вход 1.S-ro операционного блока подключен к второму выходу (i - 1).S-го операционного блока (I =

2, Р - 1, S == 1, Р— 1), значения компонент исходной положительнo определенной симметрической матрицы хранятся н первом блоке памяти, информационные выходы которого подключены к соотнетстну ощип входам задания числового компонента

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

aslxog второго QnoKa navislTv (rye 1 = 1,...,P2) подключен к дополнительному инфор лационному входу первого блока памяти, Bbl ход сумматора К-го вычислителя К-го столбца матрицы вычислителей, кроме первого вычислителя первого столбца, является выходом значения (Р— К - 1)-ro собственного числа устройства, (Р > 1)-й выход второго блока памяти является выходом значения

Р-ro собственного числа устройства. вычисленные компоненты собственных векторов хранятся но втором блоке памяти.

На фиг.1 представлена функциональная схема предлагаемого устройства для операций над матрицами размерности 3 х 3; на фиг.2 — функциональная схема вычислителя 1; на фиг.3 — функциональная схема блока 8 памяти; на фиг.4 функциональная схема

1777153 блока 9 памяти; на фиг.5 — функциональная схема блока 14 формирования коэффициентов системы линейных уравнений, на фиг.6 — функциональная схема операционного блока 4.1.S (S = 1. 2); на фиг.7 — функциональная схема операционного блока 4.I,S (1= 2;

S = 1,2); на фиг.8 — функциональная схема элемента 5.К (К =; xa фиг.9— функциональная схема распределителя 6 импульсов.

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

Вычислитель 1 содержит сумматор-накопитель 10 блок 11 умножения, сумматор

12, блок 8 памяти содержит элементы 13 памяти, блоки 14 формирования коэффициентов системы линейных уравнений, информационные входы 15, шины 16 управления записью соответствующих строк, дополнительный информационный вход 17. входы

18 управления считыванием, информационные выходы 19 элементов 13 памяти. синхровходы 20 — 23 блока 14 формирования, информационные выходы 24 блока 8 памяти.

Блок 9 памяти содержит элементы 25 памяти, блоки 14 формирования коэффициентов системы линейных уравнений, блок

3.3.1 деления, информационные входы 26, шины 27 — 29 управления записью соответствующих строк, дополнительный информационный вход 30. входы 31 управления записью соответствующих элементов последней строки, входы 32 управления считыванием, информационные выходы 33 элементов 25 памяти, информационные выходы 34 блока 9 памяти.

Блок 14 формирования коэффициентов системы линейных уравнений содержит регистр 35. памяти, блок 36 умножения, управляемый инвертор 37, сумматор-накопитель

38, си нх ро в ходы 20 — 23, Операционный блок 4.1.S содержит входной регистр 39, блок 40 деления, синхровход 41.

Операционный блок 1Л.S содержит регистр 42 первого сомножителя, умножитель

43, вычитатель 44, регистр 45 второго сомножителя, выходной регистр 46, синхровходы 47 — 49. Элемент 5 задержки содержит регистры 50, 51,синхровходы 52. 53.

Распределитель 6 импульсов содержит генератор 54 синхроимпульсов, элемент И

55, счетчик 56 тактов, блок 57 памяти микрокоманд. Bbl <оды 58 — 123 расп . JjE!. Hi l. l, Выход 58 подключен к управляющему входу 6 блока 4.1,1; выход 59 — к управляю5 щему входу 47 блока 4.2.1; выход 60 — к входу 6 блока 4.1.2; выход 61 — к входу 47 блока 4.2.2; выход 62 — к управляющим входам 48 блоков 4.2.1, 4.2.2„к управляющим входам 49 блоков 4.2.1, 4,2,2, к синхровходу

10 52 и синхровходу 53 блока 5.1 задержки; выход 63 — к тактовому входу регистра 7 сдвига; выход 64 — к управляющей шине

16.1; выход 65 — к управляющей шине 16.2; выход 66 — к управляющей шине 16.3; выход

15 67 — к управляющей шине 27.1; выход 68 — к шине 28,1; выход 69 — к шине 28.2; выход 70 — к шине 29,1; выход 71 — к шине 29.2; выход

72 — к шине 31.1; выход 73 — к шине 31.2; выход 74 — к шине 31.3; выходы 75 — 78 — к

20 управляющим входам блока 14.1; выходы 79 — 82 — к управляющим входам блока 14.2; выходы 83 — 86 — к управляющим входам блока 14.3; выходы 87 — 90 — к управляющим входам блока 14.4; выходы 91 — 94 — к управ25 ляющим входам блока 14.5; выходы 95 — 98 — к управляющим входам блока 14.6; выходы

99 — 102 — к управляющим входам блока

14.7; выходы 103 — 111 — к управляющим входам 18 считывания элементов 13 памяти;

30 выходы 112 — 123 — к управляющим входам

32 считывания элементов 25 памяти, Распределитель 6 импульсов реализован на базе ПЗУ согласно известным правилам (авт, св. СССР N1443003,,кл. G 06 F

35 15/347, 1987;авт.св. СССР N1401478,,кл. G

06 F 15/347, 1986).

Известно, если действительная матрица А = (а 1) — симметрическая и положительно определенная, то

40 1) корни 4, Аг,..., Я, ее характеристического уравнения а11 Я- а12".а3п а21 а22 3 "а2п

45

Bnl Bn2."а n-g действительны и положительны;

2) собст вен н ые ве кто ры

„110) (} = 1, 2,..., и) 55 хп могут быть взяты действительными и удовлетворяют условиям ортогональности

1777153

:1, > х (<) х<() = 0 при 1 -г К (2) (см. Демидович Б.П., Марон И,А. Основы вычислительной математики. М,: Наука, 1970, с.437).

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

Известное устройство для операций над матрицами (авт.св, СССР N 1348855, кл.

G 06 F 15/347. 1986) способно вычислять только одно собственное число, являющееся доминирующим, и один собственный вектор, соответствующий этому собственному числу. Это известное устройства не может вычислять компоненты остальных п-1 собственных векторов положительно определенной симметрической латрицы.

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

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

Пусть исходная действительная симметрическая положительно определенная матрица имеет вид

40,(<.о) (х (< o) (< o) д11 а<2...а1» а21 а22 <2<< (3) (1) с,,(1,1) — ап)х) +а,, (5) ал-1 ап2:."алл

45 (см.Демидович Б.П., Марон И.А. Основы вычислительной математики. — Ы.: Наука.

1970, с. 438, соотношение 3), который является первым приближением собственного

50 ч <

На выходе сумматора 12 последнего вычислителя 1 i-й строки (i = 1,...,п-1) образуется сигнал

xl = g а;)х; +а;,. (6) (>,>) ", (<,о) „

) — — 1

Например, для рассматриваемого случая она имеет следующие элементы:

4221

А=- 2 51 (4)

216

В исходном состоянии элементы матрицы А (соотношение 2) записаны в элементах 13 памяти блока 8. в регистре 7 сдвига записан код вида" 10 ... 0" (для рассматриваемого случая — "10"), при <е л "1" записана в первом разряде регистра 7 сдвига. Вы <исление i-го собственного значения и соответствующего ему собственно< о r

3.2.1 поступает с "0 с выхода второго разряда регистра 7 сдвига, в результате на выходе блока 3.2.1 формируется "0".

С поступлением последовательности синхроимпульсов с выходов 103 — 111 на управляющие входы 18 считывания элементов 13 памяти значения элементов матрицы

А (соотношение 4) последовательно поступают на входы сумматоров-накопителей 10 вычислителей 1 и запоминаются в них.

На входы вторых сомножителей блоков

11 умножения всех столбцов матрицы вычислителей 1, кроме последонег<<, подаются произвольные сигналы х1, х2 . На вхо(<, ) i.о) дах вторых сомножителей блоков 11 умножения вычислителей 1 последнего столбца присутствует сигнал " 1", Следовательно, для реализации итерационной процедуры отыскания собственного числа k> матрицы А (соотношение 4) в качестве «ачального приближения выбирается вектор

На выходе сумматора 12 последнего вычислителя 1 последней строки матрицы при этом образуется сигнал (где i = 1, 2...„п-1). Этот сигнал является i-й компонентой первого ненормированного

1777153 приближения первого собственного вектора матрицы А (соотношение 4): х = (x> ), xz ) il> (1)) Нормирование первого приближения первого вектора осуществляется путем деления всех его компонент на величину последней компоненты

il> . Так как в результате нормирования ,1) последняя компонента равна 1, то ее деления не производится и "1" поступает на входы вторых сомножителей всех блоков 11 умножения последнего столбца матрицы вычислителей 1. Нормирование остальных компонент осуществляется при помощи блоков 2.1.1 и 2.1.2 путем деления компонент на величину последней компоненты,.

Сигнал с выхода блока 2.1 1 деления через блок 3.1.1 умножения поступает на входы вторых сомножителей блоков 11 умножения вычислителей 1.2.1 и 1.3.1, т.е, вычислителей 1 первого столбца матрицы. Сигнал с выхода блока 2.1.2 деления через блок 3.1.2 умножения поступает на вход второго сомножителя блока 11 умножения вычислителя 1.3.2, т.е. вычислителя 1 второго столбца матрицы.

Таким образом. в соответствии с соотношением х(= - - (, Р а;;х + а;и), (7) (1.1) 1 " (1,0)

Ж ), (где i = 1, 2,...,п-1} (см. Демидович Б.П., Марон И.А. Основы вычислительной математики. — М.: Наука, 1970, с.439, соотношение 3) после окончания первой итерации на выходах вычислителей1.3.1, 1.3.2, 1,3.3 присутствуют сигналы, соответствующие компонентам первого нормированного приближения первого собственного вектора: х ) = (х1, хр, 1).

Затем итерационный процесс повторяется и после окончания второй итерации на выходах вычислителей 1.3.1, 1.3.2, 1.3.3 присутствуют сигналы, соответствующие компонентам второго нормированного приближения первого собственного вектора:

x(>) = (х (1 ) x (.2) 1)

Повторение итерационных процессов будет осуществляться до полной сходимости итерационного процесса. В результате на выходах вычислителей 1.3.1, 1.3.2, 1.3.3 присутствуют сигналы. соответствующие компонентам нормированного первого Собствено(ого вектора:

x =(x>, хг, 1), а на выходе сумматора

12 вычислителя 1.3.3 присутствует сигнал, соответствую ..в:1 собс1э".íí0:. „3 .евою (ь

Таким образом, для матрицы А (соотношение 4) система уравнений решается мето5 дом итерации в соответствии с соотношением (5) и (7): х1() = - (4х1 + 2х2И+ 2) л хз(= - — (2х 1() + 5х2() + 1)

Л1=2х()+ x)") 6

10 (8) )1ЖЧ 2 2,.> дп-1, )х) х

55 (см. Демидович Б.П., Марон И.А. Основы вычислительной математики. — M. Íàóêà.

1970, с.439. соотношение 7). (см.Демидович Б.П., Мгрон И.А. Основы вычислительной математики. — М,: Наука,1970, с.439, соотношение 9). После реализации сходимости итерационного процесса нэ выходах вычислителей 1.3. ., 1.3.2, 1.3.3 будут получены значения компонент первого собственного вектора: х)() = 0,8077; х2 = 0,7720, хз(== 1, а на выходе сумма,11 (и тора 12 вычислителя 1.3.3 будет получено значение 1i=- 8,3874.

По окон сании времени, необходимого для реализации сходимости итерационного процесса, импульс с выхода 67 поступит на вход 27.1 блока 9 памяти и компоненты первого собственного вектора окажутся записанными в элементах 25.1,1, 25.1.2, 25.1.3 памяти. В следующий момент времени на тактовый вход регистра 7 сдвига поступает тактовый импульс с выхода 63, под воздействием которого "1" из первого разряда регистра 7 сдвига сдвигается во второй разряд.

Таким образом "1" с выхода в1орого разряда регистра 7 сдвига поступает на вход второго сомножителя блока 3.2.1 умножения. На входы вторых сомножителей бло40 ков 3.1.1 и 3.1.2 умножения поступает "0" с выхода первого разряда регистра 7 сдвига,, в результате на выходах блоков 3.1.1. и 3.1.2 ° формируются "0".

Для определения второго Чобственного

45 значения и компонент х1Р), х2(2) второго собственного вектора необходимо методом итерации решать систему уравнений

1777153

10 (j= 1,2,3) (11) В = Ь11Ь<2 Ь13

Ь21 Ь 22 Ь23 (13) 40

Для матрицы А (соотношение 4) вторая система уравнений, решаемая методом итерации, определяется из условия ортогональности векторов х и х (соотношение

2). Так как

0,8077х1() + 0,7720х2() + хз() = О, то хР = -0,8077х1() - 0,7720х2() (10)

Подставляя это выражение в систему вида

Л )х <() = 4х1(<) + 2хф) + 2хз())

Л l хг") = 2x ) + 5x2 ) + хЗ()

Л)хз ) =- 2x0)+ x20)+ бхз(<) (см. Демидович Б.П., Марон И.А. Основы вычислительной математики. — М.: Наука.

1970, с.439. соотношение 8), получают х1() = --Л вЂ” (2,384 бх <() + 0,4560) (12)

Л2=. 1,1923x () + 4,2280 (см. Демидович Б.П., Марон И.А. Основы вычислительной математики. — М.: Наука, 1970, с.440, соотношение 11).

Систему (12) необходимо решать методом итерации, но для этого нужно предвэ. (2) рительно сформировать коэффициенты а<) (соотношение 9). Для этого используются коэффициенты aij, записанные в блоке 8 памяти, При формировании коэффициента а11() с выхода 112 нэ вход 32 считывания элемента 25.",.1 поступает импульс и значение

"0,8077" через сумматор 38 блока 14.4 поступает на дополнительный информационный вход 17 блока 8 памяти и после поступления импульса с выхода 79 на вход

20 блока 14.1 записывается в регистре 35 памяти. Затем импульс с выхода 105 поступает на вход 18 считывания элемента 13.1.3 и значение "2" после поступления импульса с выхода 80 на вход 21 блока 14,1 перемножается в блоке 36 умножения со значением

"0,8077". После поступления импульсов с выхода 81 на вход 22, с выхода 82 на вход

23 блока 14.1 с его выхода значение—

"1,6154" поступает на вход сумматора-накопителя 10 вычислителя 1.1.1, в котором до этого хранилось значение "4", в результате чего в нем станет храниться значение а)) -.— (2

-- 2,3846.

Аналогичным образом формируются з><ачения а <2() — 0,4560 а2« -- 1,1923, а >2() = 4,2280, которые будут храниться в сумматорах-накопителях 10 вычислителей

1.1.2, 1,2.1 и 1.2,2 соответственно.

После подачи на входы BTopblx сомножителей блоков 11 умножения вычислите15

35 лей 1.1.1 и 1.2.1 произвольного сигнала х1(2 о), а на выходы вторых сомножителей блоков 11 умножения вычислителей 1.1.2 и

1.2.2. сигнала "1" начнется реализация итерационного процесса. После достижения сходимости итерационного процесса на выходе делителя 3.2.1 и, соответственно, на выходе вычислителя 1,2.1 будет получено значение х1 =- 0,2170, на выходе вычисли(2) те/<я 1.2.2 будет присутствовать сигнал

x2 = 1, а на выходе сумматора 12 — зна2 чение Л2 =- 4.4<867, Компонента х2 определяется из соот(з) ношения (10), т.е. уравнения с одним неизвестным, с использованием известного устройства для операций над матрицами, способного решать уравнения с одним неизвестным или системы из и уравнений с и неизвестными по методу Гаусса-Жордана (см. авт.св. СССР ¹ 1443003, кл, G 06 F

15/347, 1987). В его состав входят операционные блоки 4.1.1, 4.1,2, 4.1.3. 4.1.4, элемент

5.1 задержки, распределитель 6 импульсов.

В нем выполняется обработка матрицы размерности N X M (N =- 1,2), которая представляет собой матрицу коэффициентов при неизвестных системы линейных уравнений, к которой справа дописана матрица размерности N х 1 свободных членов.

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

В вида где Ь11, Ь12, Ь21, Ь22 коэффициенты при неизвестных;

Ь1з. Ь2з — свободные члены, В соответствии в описанием по авт.св.

СССР ¹ 1443003, кл.G 06 F 15/347, 1987, элементы матрицы В поступают на входы операционных блоков 4 построчно со сдвигом на один такт под воздействием синхроимпульсов с выходов распределителя 6 импульсов, т.е. первая строка поступает на первый вход операционного блока 4.1.1, начиная с первого такта, вторая строка поступает на первый вход операционного блока

4,2.1, начиная с второго такта и т.д. На выходах операционных блоков 4.Ц (j =. и, i =

1„„,n) получается семейство решений системы линейных уравнений.

Таким образом, решения системы из двух уравнений получатся на выходах операционных блоков 4.1.2 и 4.2.2, решение уравнения с одним неизвестным — на выходе операционного блока 4,1,1, 13

1777153

Следовательно при вычислении значения хз(будет задействован только операционный блок 4.1.1 Коэффициент при неизвестном и свободный член будут вычислены блоком 14.4 блока 3 памяти.

В соответствии с выражением (10) коэффициент при неизвестном будет сформирован следующим образом. С выхода 90 на вход 23 блока 14.4 и на информационный вход 17 блока 9 памяти поступает "1", в результате чего через сумматор 38 блока

14,4 она поступает на вход операционного блока 4.1.1.

Затем вычисляется свободный член в соответствии с выражением (10). Синхроимпульс с выхода 112 поступает на вход 32 считывания элемента 25.1.1. памяти, с выхода 87 — на синхровход 20 блока 14,4, и значение х1 записывается в регистр 35 (1 памяти блока 14.4. Синхроимпульс с выхода

115 поступает на вход 32 считывания элемента 25.2,1 памяти. с выхода 88- на синхровход 21 блока 14.4. и значение x1() (г) перемно>кается с х1 в блоке 36 перемно(1) жения блока 14.4. Синхроимпульс с выхода

89 поступает на синхровход 22 блока 14,4, и (1) (2) результат перемножения х1() х1() инвертируется в управляемом инверторе 37 блока

14.4, после чего значение -x1 х1 поступа(1) (2) ет на вход сумматора-накопителя 38 блока

14,4. Синхроимпульс с выхода 113 поступает на вход 32 считывания элемента 25.1.2, с выхода 87 — на синхровход 20 блока 14,4, и значение х2(-) записывается в регистр 35 (1) памяти блока 14,4. Синхроимпульс с выхода

116 поступает на вход 32 считывания элемента 25.2.2 памяти, с выхода 88 — на синхровход 21 блока 14.4, и значение х2( перемножается с х2 в блоке 36 перемно(1) жения блока 14.4. Синхроимпульс с выхода

89 поступает на синхровход 22 блока 14,4, и, (1) (2). результат перемножения х2, х2 инвертируется в управляемом инверторе 37 блока

14,4, после чего значение -х2 х2 поступа(1) (г) ет на вход сумматора-накопителя 38 блока

14.4. Синхроимпульс с выхода 90 поступает на вход 23 блока 14.4, и значение, находящееся в сумматоре-накопителе 38 блока

14,4,поступает на вход операционного блока 4.1.1.

Значение хз = -0,9473 с выхода опера(2) ционного блока 4.1.1 поступает на информационный вход 26.3 блока 9 памяти и с поступлением синхроимпульса с выхода 69 на вход 28.2 оказывается записанным в элементе 25.2.3 блока 9 памяти.

Таким образом, в элементах 25.2.1, 25.2,2. 25.2.3 будут записаны компоненты второго собственного вектора матрицы А (соотношение 4).

По окончании времени, необходимого для вычисления компонент второго собственного вектора. с выхода 63 на тактовый вход регистра 7 сдвига поступает тактовый импульс, в результате чего второй разряд регистра 7 сдвига обнуляется. Так как на вход второго сомножителя блока 3.2.1 умножения поступает "0" с выхода второго разряда регистра 7, то на выходе блока 3.2. 1 формируется "0".

Вычисление компонент третьего собственного вектора производится следующим образом. На входы вторых сомножителей блоков 11 умножения вычислителей 1.1,1, 1.2.1, 1,3.1 подается сигнал "1". С выхода блока 1.3,1 значение хз(= 1 поступает на, (1) информационный вход элемента 25.3.1 памяти блока 9, С поступлением синхроимпульса с выхода 70 на вход 29.1 блока 9 памяти значение хз() = 1 записывается в (1) элемент 25.3,1 памяти, После этого осуществляется вычисление компонент х2Р) и хэви с использованием соотношений ортогональности:

0,8077 х1() + 0,7720 х2() + хз() = 0

0,2170 x1()+ х2()-0,9473 хЗ(= 0 I (14) (см.Демидович Б.П., Марон И,А. Основы вычислительной математики. — M.: Наука, 1970, с.441).

Так как значение x1() = 1 вычислено и, (з) записано в элементе 25.3.1 памяти, то систему уравнений (14) можно представить в виде

0,7720 х2() + хз() = -0,8077 х2 ) - 0,9473 хз(з) = -0,2170 (15) Эта система линейных уравнений легко решается методом Гаусса-Жордана. Поскольку коэффициенты при неизвестных и свободные члены записаны в блоке 9 памяти, то уравнение (15) решается следующим образом. При поступлении синхроимпульса с выхода 113 на вход 32 считывания элемента 25,1.2 памяти значение "0.7720" считывается с него, и при поступлении синхроимпульса с выхода 90 на вход 23 блока 14.4 через сумматор 38 блока 14.4 значение "0,7720" поступает на вход операционного блока 4.1,1.

При поступлении синхроимпульса с выхода 116 ча вход 32 считывания элемента

25.2.2 памяти значение "1" считывается с него, и при поступлении синхроимпульса с выхода 94 на вход 23 блока 14.5 через сумматор 38 блока 14.5 значение "1" поступает на вход операционного блока 4.2.1, 15

1777153

Аналогичным образом считываются значения "1" из блока 25.1,3 памяти и значение "-0,9473" из блока 25.2,3 памяти и поступают на входы операционных блоков

4,1,1 и 4,2.1, Аналогично считываются значения "0.8077" и "0,2170" и после инвертирования в управляемых инверторах 37 блоков

14.4 и 14,5 поступают на входы операционных блоков 4.1,1 и 4,2,1 соответственно, В соответствии с алгоритмом работы операционных блоков 4 на выходах блоков

4.1,2 и 4.2.2 будут сформиоованы соответственно значения хг = -0,5673 и х.з() = -0,3698, поступающие на входы 26,2 и 26.3 соответственно блока 9 памяти.

С поступлением синхроимпульса с выхода 71 на вход 29.2 блока 9 памяти значение "-5673" окажется записанным в элементе 25.3.2, а значение "-3698" — в элементе 25.3.3 памяти.

Таким образом, в элементах 25.3.1, 25.3,2 и 25.3.3 будут записаны компоненты третьего собственного вектора матрицы А (соотношение 4).

Третье собственное значение матрицы

A (соотношение 4) вычисляется с использованием последнего уравнения системы (11) при j = 3. Согласно ему

Яз = — т — с — (2 x i + х2 + 6хз )) . (16) Для вычисления 1з с выходов 109 — 111 последовательно подаются синхроимпульсы на входы 18. считывания элементов

13.3.1, 13.3,2, 13.3.3, в которых записаны соответственно значения "2", "1", "6" матрицы А (соотношение 4), Эти значения с выхода 24,3 последовательно поступают на дополнительный информационный вход 30 блока 9 памяти и с поступлением с выходов

72 — 74 на управляющие входы 31.1, 31,2, 31.3 записи последовательности импульсов записываются в элементах 25,4.1, 25.4,2 и

25,4.3 соответст вен но, Затем с выхода 121 на вход 32 считывания элемента 25.4.1 поступает синхроимпульс и значение "2" под воздействием импульса, поступающего с выхода 99 на вход 20 блока 14.7, записывается в регистр

35 памяти блока 14.7. После этого под воздействием синхроимпульса, поступающего с выхода 118 на вход 32 считывания элемента 25.3.1, значение x> = 1 поступает на вход (з) блока 36 умножения, и после поступления синхроимпульса с выхода 100 на.вход 21 блока 14.7 результат произведения с выхода блока 36 умножения записывается через управляемый инвертор 37 в сумматор-накопи20

55 тель 38, Значение произведения не инвертируется, так как на синхровход 22 блока

14.7.синхроимпульс не поступает, Аналогичным образом вычисляются остальные слагаемые уравнения (16), После этого с выхода 102 на синхровход 23 поступает импульс и значение суммы "-0,7861" с выхода сумматора-накопителя 38 блока 14.7 поступает на вход делимого блока 3.3.1 деления. В это же время на вход 32 управления считыванием блока 25.3,3, в котором записано значение хз = -0,3698. с выхода 120 (3 поступает синхроимпульс и с выхода 33 элемента 25.3,3 памяти значение "-0.3698" поступает на вход делителя блока 3.3.1 деления, на выходе которого появляется значение ib-- 2,1260. На этом процесс вычисления собственных значений и собственных векторов матрицы А (соотношение 4) заканчивается, Значение компонент всех собственных векторов хранится в блоке 9 памяти.

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

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

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

= 1....,Р; M = 1,.„,Р) подключен к входу сумматора-накопителя, выход которого подключен к входу первого сомножителя блока умножения (К-го вычислителя М-й строки матрицы, выход сумматора К-ro вычислителя (К = Р) М-й строки матрицы подключен к входу второго слагаемого сумматора (К +

1)-ro вычислителя М-й строки матрицы, о т17

1777153 л и ч а ю щ е е с я тем. òï, с целью расширения функциональных возможностей за счет вычисления всех собственных значений и всех собственных векторов положительно определенных симметрических 5 матриц, в него введены (P - 1)-разрядный регистр сдвига, P - 1 групп блоков умножения по P - i блоков в каждой группе (i = 1,...,Р

-1), Р -2 групп блоков деления по P - i блоков в каждой группе,два блока памяти, (P - 1) 10 операционных блоков, P - 2 элементов задержки и распределитель импульсов, причем выход сумматора К-го вычислителя К-го столбца матрицы, кроме первого вычислителя первого столбца, подключен к входу де- 15 лителя всех блоков деления (P - К + 1)-й группы. вход делимого j-ro блока деления (j

= 1„...P - i) i-.é группы подключен к выходу

"умматора j-ro вычислителя (P - i - 1)-го столбца, выход j-го блока деления i-й группы 20 подключен к входу первого сомножителя jro блока умножения i-й группы, входы вторых сомножителей блоков умножения i-й группы подключены к выходу i-ro разряда регистра сдвига, тактовый вход которого 25 подключен к выходу распределителя им- . пульсов, выходы которого подключены к синхровходам операционных блоков. элементов задержки, первого и второго блоков памяти, выходы j-x блоков умножения под- 30 ключены к входам вторых сомножителей блоков умножения всех вычислителей j-го столбца матрицы, выход j-го блока деления

i-й группы является выходом j-й

K0Mr1oH8HTbl <-го собственного вектор.". и подключен к )-му информацион -.ому входу второго блока памяти, первый вход I.1-го операционного блока подключен к i-vy выходу второго блока памяти (I = 1, Р - 1), первый выход 1.S-го операционного блока подключен к (Р - i + 1)-му информационному входу второго блока памяти (5 -= 1, Р - 1), первый вход i: S-го операционного блока подключен к первому выходу (i - 1) (S — 1}-го операционного блока(i --- 1, Р -2; S = 2, Р -1), первый вход операционного блока (Р == 1, S) подключен к выходу (S - 1)-ro злемента задержки (S = 2, Р - 1), вход которого подключен к второму входу (P - 1) (S — 1)-го операционного блока. второй вход i,S-го операционного блока подключен к второму выходу (i - 1). S-го операционного блока (i =2, P-1, S= 1, P 1), информационные выходы первого блока памяти подключены к соответствующим входам задания числового компонента вычислителей. P-й информационный выход первого блока памяти подключен к информационному входу второго блока памяти i-й информационный выход которого (i =- 1, P - 2) подключен к информационному входу первого блока памяти, выход сумматора К-ro вычислителя К-го столбца матрицы вычислителей, кроме первого вычислителя первого столбца, является выходом значения (Р - К+ 1)-ro собственного числа устройства, (P + 1)-й выход второго блока памяти является выходом значения

Р-го собственного числа устройства.

1777153

1777353

1 (»

1a{

С,1Л

) 1

l.-с ...

2U() — — (.(!!!!

k (1 / - 1 ! !

1

Ф г. 5 с 2 1<: Л

1;. j

ПП

-1 .1

1П гпг..I

"1 4

Олг ((:10

T — — 11 . Ч

11! 1

l Г,h

2011г 11! j

ti г) / -.".У .92

211 ганг!

1 I 3I 1 3I.>

56аГ Г

:4С

0 — - — — — - (Q(« )

Ф !

„„!

jI l

i ( (Г

1777153

1777153 г

1777153

Составитель В. Попенко

Техред М.Моргентал Корректор Н.Тупица

Редактор Г. Бельская

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

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

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

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