Устройство для вычисления собственных значений (n x n)- матрицы
Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления всех собственных значений (n n)-матрицы. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит вычислительный модуль 8 первого типа, 2n - 1 вычислительных модулей 9 второго типа и блок 10 анализа. Основу вычислительного модуля первого типа составляет узел вычисления обратной величины числа, а вычислительного модуля второго типа - умножитель и сумматор. В основу устройства положен итерационный треугольный степенной метод вычисления собственных значений для (n n)-матрицы. 7 табл. , 5 ил.
Изобретение относится к вычислительной техике и может быть использовано в высокопроизводительных специализированных машинах и устройствах обработки сигналов для вычисления всех собственных значений (n x n)-матрицы.
Цель изобретения - сокращение аппаратурных затрат. На фиг. 1 представлена структурная схема устройства для вычисления собственных значений (n x n)-матрицы; на фиг. 2 - структурная схема устройства для n= 3; на фиг. 3 - функциональная схема вычислительного модуля первого типа; на фиг. 4 - функциональная схема вычислительного модуля второго типа; на фиг. 5 - функциональная схема блока анализа. Устройство для вычисления собственных значений (n x n)-матрицы (фиг. 1) содержит группу информационных входов 1, первый 2 и второй 3 информационные входы, группу настроечных входов 4, первый 5 и второй 6 настроечные входы, синхровход 7, вычислительный модуль 8 первого типа, вычислительные модули 9i (i= ) второго типа, блок 10 анализа, группу выходов 11 и выход 12 признака окончания вычислений. Вычислительный модуль 8 первого типа (фиг. 3) содержит первый 13 и второй 14 информационные входы, первый 15 и второй 16 настроечные входы, синхровход 17, регистры 18 и 19, узел 20 вычисления обратной величины числа, триггеры 21 и 22, группы элементов И 23-26, группу элементов ИЛИ 27, элементы И 28-31, первый 32 и второй 33 информационные выходы, первый 34 и второй 35 настроечные выходы. Вычислительный модуль 9 второго типа (фиг. 4) содержит первый 36, второй 37 и третий 38 информационные входы, первый 39, второй 40 и третий 41 настроечные входы, синхровход 42, регистры 43-47, сумматор 48, умножитель 49, триггеры 50-52, группы элементов И 53-59, группы элементов ИЛИ 60 и 61, элементы ИЛИ 62 и 63, элементы И 64-69, элемент НЕ 70, первый 71 и второй 72 информационные выходы, первый 73 и второй 74 настроечные выходы. Блок 10 анализа (фиг. 5) содержит первый 75 и второй 76 информационные входы, синхровход 77, регистры 78, вычитатели 79, схемы 80 сравнения, элементы И 81-83, триггер 84, делители 85 и 86, элемент ИЛИ 87, группу выходов 88 и информационный выход 89. В основу работы устройства положен итерационный треугольный степенной метод вычисления собственных значений i(1in)матрицы A= { aij} , 1i, jn, где имеет место распределение >>. . . >. В основе вычислительной схемы треугольного степенного метода лежит последовательное вычисление матриц C= . . Rm= m= 1, 2, . . . по правилу A Cm-1= Bm; Bm= Cm Rm, где Co= { C(o)ij} , 1i, jn- некоторая нижняя треугольная матрица с единицами по главной диагонали. При этом r(m)ii _ i при m _ , 1in , следовательно, при достаточно больших m можно положить irii(m), 1in. Если итерационный процесс прерван на шаге с номером m, то приближенное вычисление собственных векторов xi матрицы A может быть выполненно по правилу RmV(im)= r(mii)V(im) (т. е. сначала находится решение V(m)i треугольной системы линейных алгебраических уравнений), x(im)= CmV(im), xi x(im). Эти соотношения показывают, что если для вычисления собственных значений матрицы A достаточно диагональных элементов r(m)ii, то для нахождения собственных векторов требуются еще и внедиагональные элементы матриц Rm и Cm. На каждом итерационном шаге m перемножения матриц A Cm-1 и LU - разложение матрицы Bm на матрицы Cm и Rm представляются следующими рекуррентными соотношениями: Формируют следующие матрицы, элементы которых подаются на соответствующие входы устройства: матрицу , матрицу n где знак * обозначает любое значение 0 или 1/матрицу элементы dij представляют l-разрядные числа aij и одноразрядное число , принимающее значение 0 или 1,
матрицу , 1
Вычислительные модули и блок анализа работают следующим образом. Вычислительный модуль 8 первого типа обладает возможностью реализации следующих функций:
Vj+1= j;
Wj+1= j, где jиj - значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;
Vj+1 и Wj+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте,
Aj+1=
Bj+1= bj, где aj и bj - значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте;
Aj+1 и Bj+1 - значения соответственно на первом и втором информационных входах вычислительного модуля на (j+1)-м такте,
Вычислительный модуль 9 второго типа обладает возможностью реализации следующих функций:
Vj+1= j;
Wj+1= j, где jиj - значения соответственно на втором и третьем настроечных входах вычислительного модуля на j-м такте;
Vj+1 и Wj+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте;
Aj+1= aj, если j1 j2 j3 j4= 1
= где bj, aj и cj - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на j-м такте;
К - параметр, определяемый алгоритмом;
Aj+1 - значение на первом информационном входе вычислительного модуля на (j+1)-м такте;
Cj+n-1 - значение на втором информационном выходе вычислительного модуля на (j+n-1)-м такте;
j - значение на первом настроечном входе вычислительного модуля на j-м такте. По управляющему сигналу j запись в регистр осуществляется на (j+1)-м такте, а по управляющему сигналу j - на j-м такте. Вычислительный модуль 8 первого типа работает в четырех режимах, которые задаются управляющими сигналами и , подаваемые соответственно на входы 15 и 16. В первом режиме ( j, j)= (1, 1), при этом на выходе элемента И 28 формируется единичный сигнал ( 1j= 1), который открывает группу элементов И 23. На вход 13 подается число aj, которое записывается в регистр 18 и через группы элементов И 23 и ИЛИ 27 выдается на выход 32. Число bj подается на вход 14, записывается в регистр 19 и выдается на выход 33. Во втором режиме ( j, j)= (0, 0). При этом на выходе элемента И 29 формируется сигнал 2j= 1, который открывает группу элементов И 25. Число bj записывается в регистр 19 и выдается на выходы 32 и 33. В третьем режиме ( j, j )= (0, 1). На выходе элемента И 30 формируется сигнал 3j= 1, который открывает группу элементов И 26. На выход 14 подается число bj, которое записывается в регистр 19 и выдается на выход 33. На выход 32 подается через узел 20 вычисления обратной величины числа, группы элементов И 26 и ИЛИ 27 число 1/bj. В четвертом режиме ( j, j)= (1, 0). На выходе элемента И 31 формируется сигнал 4j= 1. Открывается группа элементов И 24. В регистр 19 записывается число bj, которое выдается на выход 33. С инверсного выхода регистра 19 выдается число -bj через группы элементов И 24 и ИЛИ 27 на выход 32. Вычислительный модуль 9 второго типа работает в пяти режимах, которые задаются управляющими сигналами , и , которые подаются соответственно на входы 40, 41 и 39. Во всех режимах осуществляется запись чисел из регистра 47i (i= ) в регистр 47i+1. На выход 72 подается число, записанное в регистр 47n-1. Управляющие сигналы и записываются соответственно в триггеры 51 и 52 и подаются соответственно на выходы 73 и 74. В первом режиме ( j, j, j)= (0, 1, 0), на выходе элемента И 66 формируется сигнал 1j= 1, который открывает группы элементов И 56, 57, 58 и элемент И 64. В регистр 43 записывается число aj, в регистр 45 - число cj. На выходе умножителя 49 число cj. На выходе умножителя 49 формируется произведение aj cj, которое на (j+ 1)-м такте записывается в регистры 46 и 471. Число aj через группу элементов И 57 выдается на выход 71. Во втором режиме ( j, j, j)= (1, 0, 0), на выходе элемента И 67 формируется сигнал 2j= 1, открываются группы элементов И 55, 57 и 59. Число aj записывается в регистр 43 и через группу элементов И 57 выдается на выход 71. На выходе умножителя 49 формируется произведение aj. <содержимое регистра 46> , на выходе сумматора 48 - сумма cj+aj. < содержимое регистра 46>, которая на (j+1)-м такте записывается в регистр 471. В третьем режиме ( j, j)= (0, 0), на выходе элемента И 68 формируется сигнал 3j= 1. Открываются группы элементов И 54, 55 и 57. В регистр 43 записывается число aj, которое выдается на выход 71. На выходе умножителя 49 формируется произведение aj bj (число bjзаписывается в регистр 44), на выходе сумматора 50 - сумма cj+aj bj (в регистр 45 записывается число cj), которая записывается на (j+1)-м такте в регистр 471. В четвертом режиме ( j, j )= (1, 1). На выходе элемента И 69 формируется сигнал 4j= 1. Вчислительный модуль 9 работает как в третьем режиме. В пятом режиме ( j, j, j)= (0, 1, 1). На выходe элемента И 65 формируется сигнал j= 1, который открывает группу элементов И 53. Число bj через группы элементов И 53 и ИЛИ 61 подается на вход регистра 471, которое на j-м такте по заднему фронту тактового импульса записывается в регистр 471. Рассмотрим работу блока 10 анализа (фиг. 5). Приближения к собственным значениям матрицы i(m) (i= ) подаются на вход 75 в моменты времени
t= ( -1)n+i+mn2, где m - номер итерации, m= 1, 2, 3, . . . , (m). Запись приближений к собственным значениям i в регистры 78j(j= ) осуществляется тактовыми импульсами, которые подаются с выхода элемента И 83 в моменты времени t. В табл. 1 приведены состояния делителя 85 по модулю счета (n+1), делителя 86 по модулю счета n2, триггера 84 и регистров 78j (j= ) для n= 3. На (n2-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на n2-м такте устанавливает делитель 85 в нулевое состояние, а триггер 84 в единичное состояние, который открывает элемент И 83. На (n2+1)-м такте через элемент И 83 тактовый импульс подается на синхровходы регистров 78, в которые осуществляется запись собственных чисел. Триггер 84 устанавливается в нулевое состояние. На ((i-1)n+i+mn2-1)-м такте (i 1) на выходе делителя 85 формируется единичный сигнал, который на ((i-n)n+i+mn2)-м такте (i 1) открывает элемент И 83 и разрешает запись в регистры 78j. На (n2(m+1)-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на (n2(m+1))-м такте устанавливает триггер 84 в единичное состояние и разрешается запись в регистры 78j. На (n2(m+1))-м такте выполняется проверка точности вычислений - . Если данное соотношение выполняется, то на выходе 89 признака окончания вычислений формируется единичный сигнал = 1. При этом с выходом 88i(i= ) снимаются значения i. Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений i продолжается. Проверка соотношения - выполняется вычитателями 79i, схемами 80i сравнения (i= ) и элементом И 81. Рассмотрим работу устройства (фиг. 1). На выходы 1i и 4i (i= ) подаются элементы входной матрицы { dij} = { aij, } в моменты времени
tdij= i+(j-1)n+p+mn2, i= , j= , p= , m= 0, 1, 2, . . . На вход 2 подаются элементы c(o)qj, 1 j< q в момент времени
tcqj(o)= (q-1) n+j-1. На выходы 5 и 6 подаются соответственно управляющие сигналы и матриц { ij} и { ijI} в моменты времени
t= (i-1)n+j-1, i, j = ;
t= (i-1)n+j-1+mn2, i, j = , m = 1,2,3, . . . Собственные значения i(m) формируются на выходах 11 (i= ), при значении = 1 на выходе 12 в моменты времени
t= n2(m+1). Элементы матрицы { n(m)ij} формируются на выходе 33 вычислительного модуля 8 в моменты времени
t= (i-1)n+j+mn2, i, j = , m = 1,2,3, . . . На фиг. 2 показана организация входного и выходного потоков данных для n= 3. В табл. 2-7 приведены состояния триггеров, регистров и значения на выходах вычислительных модулей 8 и 9. На десятом такте в блоке 10 анализа (табл. 1) формируется значение 1(1), на четырнадцатом такте - 2(1), на восемнадцатом такте - 1(1), на девятнадцатом такте - 1(2), на двадцать третьем такте - 2(2), на двадцать седьмом такте - 3(2) . На двадцать седьмом такте выполняется проверка соотношения - . Если на выходе 12 формируется признак = 1, то значения i снимаются с выходов 11. Если признак = 0, то итерационный процесс вычисления i продолжается.
Формула изобретения
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5