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

СООЗ СОНЕТСНИХСОЛЮЛ РИРЕСПУБЛИН ЯО И 6 й 7 Ы 244а ВЕННОЙ НОМИТЕТ СССРИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ГОСУДПО ДЕЛ ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СвилТЕЛЬСТВУ Ъ 4 ъФ" 6 . йюжАйжа(71) Киевский ордена Трудового Красного Знамени институт инженеров граж данской авиации(56) Авторское свидетельство СССР Р 805336, кл. С 06 Р 15/324, 1978.Авторское свидетельство СССР В 836396, кл. С 06 Р 15/324, 1979.Пухов Г.Е. и др. Разрядно-аналоговые вычислительные систевщ. М.: Советское радио, 1978, с. 254. (54) УСТРОЙСТВО ДЛЯ РВПЕНИЯ СИСТЕИ ЛИНЕЙНЫХ АЛГЕВРАИЧВСКИХ УРАВНЕНИЙ (57) Изобретение относится к области вычислительной техники и может быть применено автономно илн в качествеспецпроцессора в мультипроцессорныхвычислительных системах для оперативного решения систем линейных алгебраических уравнений. Цель изобретения - повышение быстродействия.Устройство содержит и блоков вычисления разрядов, и (ш) вычислительных блоков. Блок вычисления разрядасодержит два сумматора-вычитателя,сумматор, два элемента НЕ, элемент Иэлемент сложения по модулю два игруппу ключей. Вычислительный блоксодержит блок вычисления разряда иблок восстановления остатка, содержащий (и) сумматоров-вычитателейи группу ключей. За счет совмещенияво времени вычислительных операцийс временем переходного процесса достигается цель изобретения. 4 ил.(2 а основ сист уравнений может быть записан ных ве оровбинар1(хя кот как екторы н2 Х.ебраических уравернутой форме назапишем следунщим х -2 тему2 АХЭ Изобретение относится к вычислительной технике и может быть применено автономно или в качестве спецпроцессора в мультипроцессорных вычислительных системах для оперативного решения систем алгебраическогоуправления динамическими объектами.Целью изобретения является увеличение быстродействия,На фиг. 1 представлена схема уст- Оройства для решения систем линейныхалгебраических уравнений для случая,когда и3 и ш = 4; на фиг. 2схема блока вычисления разряда; нафиг. 3 - схема вычислительного блока; 5на фиг. 4 - схема блока восстановления остатка,Устройство для решения систем линейных алгебраических уравнений(. " 1, и, 1 = 1,т), (,и+1)-е входные шины 41, выходные шины результата 1-го (1 = 1,М) разряда -го неизвестного 5;, 6 7; . Блок вычисления разряда 1 (фиг. 2) содержит два, оо,11, хоо,11, - разрядность представл формации, а 1 == 1,2,и компонентов разрядсФормируем следующие ых элементов93 2 сумматора-вычитателя 8, сумматор 9, два элемента НЕ 10, элемент И 11, элемент сложения по модулю два 12 и группу ключей 13,Вычислительный блок 2 (фиг. 3). содержит блок 1 вычисления разряда, блок 14 восстановления остатка и 1 с-управляющих шин 15 1 б , 17; (1 с=1и). Блок 14 восстановления остатка (фиг. 4) содержит (и -1) сумматоров-вычитателей 18 и (и) группу ключей 19,Работу матричной вычислительной структуры для решения систем линейных алгебраических уравнений АХ=Г порядка и для случая, когда норма матрицы А удовлетворяет условиюР А 3 2 й - поясним на конкретном примере (где А - матрица коэффициентов; Х векторы неизвестных и правых частей; 0 - диагональная матрица, элементами которой являются диагональные эле" менты матрицы А). Запишем значения коэффициентов аматрицы А и компонент х и Е; векторов Х и Г в разрядной форме 31,ч формируем следуннцие матрицы б2 бэ 79 где 3;, - разрядная матрица З 1, составленная иэ разрядных век(5) а11 пишем первую строажении (4) при я иллюстрации уравнений в Зип=2. с1сходнойоряет у к матрица а ис а мц уравнений1 А Здет не болчески для влет овию к е "2" т1можно х, бу (факти компоненФ пре ос овании вторых ра в(к кхх,,каждый скх) вычи Анало тор Х ск ет)( Э я каждого к ния (9) т.е авнений вид 1 с 2 (а 1имеют разныать Алгоритм вкнента х ищения разр-2 а =Г:1 к.образом. 3если йки, и отри мпоисле знак з выр ядных(к Таким образом, в соответствии с (6)каждая строка выражения (4) можетбыть представлена в виде и разрядных уравнений, по которым организуем вычисление компонентов х, следуюк щим образом.Из первых разрядных уравнений выражения (4), записанных в виде-ф с (1Е -2 а х =Еи,е эЕ - 2 а; х = Г, ) = ),п, (7) определим х,. При этом считается, что остаток Г, в выражении (4) можетпринимать значения соответственно(д (- к2 АХ-й =Е Е -2 а)хф Определим значения вторых разрядова к 1х , т.е. вектор Х = (хх , хк(к-) (к 1)1Х - Х ЕЭ ствляется следующим будет положителен, еют одинаковые знаи, когда значения 3 лторов а,;, которая,5664062 ,6914062 етственн Определим системы е й нй 1 (9 Зна нйЗна,0 0 Знх 3 н 0).аким образом, значение х"; может врыть вычислено в результате реаличации одной иэ строк таблицы, а вкличинахпредставляется в видеК 1 К Кг суммы двух значенийх)1 = х + х) ) Ф благодаря чему при реал эации первКстроки х = 2, Векторпри этомС 1 может быть записан как Х = (х, +Сг к кг ф х, +хг+хг++х+х).= 04 х 1 = 0 + 0 = 0г01 хг = О+ 0= О,а (О. Модуль х"; определяется в соответствии с таблицей. Рассмотрим изложенноеном примере,0,625 Х 1 + 0,3125 Х 2 = 00,375 Х 1 + 0,8125 Х 2 0Решение х,х 2 равно соотвХ 1 = 0,625, Х 2 = 0,5625,удовлетворяет ли матрицауравнений условиюй А = 1,4615384.(11Р, (О, - х, =О, - х, =О;Р = 0 - х = 1 = - х = Оу = 0,0195313- О+ 0 = О1+0=1. 4 4Знх, =1, х,РешениеХ, = (1010) -0625Х = (1001)-0,5625.Работа устройства происходит следующим образом. ЗОНа входные шины 4 4 п подаются соответственно значения компонентов Е, Г вектора правых частей Р решаемой сйстемы уравнений АХ = Р, На входные шины 3(д = 1,2п) 35 подаются значения диагональных элементов а матрицы А и на входные шины 3, (дг 1) подаются значения побочных элементов а матрицы А. Пбсле этого в схеме протекает переходной про цесс, по окончанию которого в каждом (д; 1)-м блоке вычисления разряда 1 моделируется соответственно д-я строка выражения 7, благодаря чему на выходе элемента сложения по модулю два 4512 и элементов НЕ 10(д,1)-го блока вычисления разряда 1 и соответственно на входной шине первого разряда неизвестного по 5;, 6 7; таблице образуются соответственно значениягЗнх х х первого разряда д-го неизвестного х;. На выходе сумматора 9(д 1) блока вычисления .разряда 1 образуется в соответствии с (7) значе(Чние Е, , поступающее на второй,ин)рор мационный вход сумматора-вычитателя 8 блока восстановления остатка 14(д,2)-го вычислительного блока 2в котором моделируется д-я строка выражения (8). При этом в блоке восстановления остатка 14 вычисляется энао) -) н)чение й; = 2 А Х - Е , а в блоке вычисления разряда 1 - соответственноор -г г (г)Е; - 2 а(х; = Г;, Благодаря этому на выходе элемента сложения по модулю два 12 и элементов (д,2) блока вычисления разряда 1 и на вьмодных шинахгвторого разряда 5 6), 7; образуются соответственно знак Знх.( и х х()гг) аг второго разряда д-го неизвестного Х. А на выходе сумматора 9 на блоке вы"(фг числения разряда 1 образуется К , поступающее на второй ннформационйьй вход сумматор а-вычитат еля ( д , 3 ) -го блока восстановления остатка 1 4 , Аналогичным образом в каждом д1 -м блохе восстановления остатка 1 4 моделирчет.(к-г)-) (х.) ся выражение (9), т.е. 2 А Г -й-х (1- 2 а,;-Г, сумматора 9 дЗ-го блока вычисления разряда 1. Образуется(х 1значение Е а на выходных шинахЮк к к1-го разряда 5., 6 7, д,1-го блока вычисления разряда 1 в соответстрнн стаблицей образуются соответст" венно эначейия Знх , х;, х; 1-го,к х кг разряда. д-го неизвестного Х.Таким образом, за время переходного пррцесса в,схеме на выходных шинах 5 6;, ; д 1 блоков вычис 1265793леиия разряда 1 образуются 1-е компоненты Х вектора АХ = Г неизвестных Х системы уравнений АХ = Ет кото рые можно записать какХ = т 2 (х + х,)5Кл 1Формула изобретенияУстройство для решения систем линейных алгебраических уравнений, содержащее п (и- порядок системы) блоков вычисления разряда, причем каждый блок вычисления разряда содержит сумматор, о т л и ч а ю щ е е с я15 тем, что, с целью увеличения быстродействия, в неговведено и (щ) блоков вычисления разряда и и .(щ -1) блоков восстановления остатка (щ - разрядность представления информации) причем блок вычисления разряда дополнительно содержит два сумматора-вычитателя, элемент И, группу ключей, два элемента НЕ и элемент сложения по модулю два, причем в каждом 1 р-м (х= 1,п; 1 = 1,щ) блоке вычисления разряда информационные выходы первого сумматора-вычитателя 1,-го блока вычисления разряда соединены с первой группой информационных входов второго30 сумматора-вычитателя 1 р-го блока вычисления разряда, информационные выходы которого соединены с входами первого слагаемого сумматора ,-го блока вычисления разряда, входы второго слагаемого которого соединены с выхо-З 5 дами ключей группы ,-го блока вычисления разряда, управляющие входы которых подключены к выходу элемента И 1,1-го блока вычисления разряда, выходы знака первого и второго сумматоров-вычитателей д,-го блока вычисления разряда соединены соответственно через первый и второй элементы НЕ 1,-го блока вычисления разряда соответственно к первому и второ 45 му входам элемента И 1,1-го блока вычисления разряда, 1,1-й блок восстановления остатка (1 = 1 п;= 2,щ) содержит (и) сумматор-вычитатель и (и) группу ключей, причем в каждом у 1-м (1 = 1,п, 1 = 2,щ) блокевосстановления остатка выходы ключей1 с-й (1 с =1, и) группы 1,1-го блокавосстановления остатка соединены спервой группой входов 1-го сумматора вычитателя 1,1-го блока восстановления остатка, информационные выходыкоторого соединены с второй группой ходов (Е +1)-го сумматора-вычитатепя 1.,-го бпока восстановления остатка, входы 1-х (1 = 1,п) диагональныхкоэффициентов уравнений устройствасоединены с первыми группами входовпервого и второго сумматора-вычитателя и информационными входами ключей группы 1,1-х (1 = 1,щ) блоков вычисления разряда, 1-я (1 = 1,п) группа входов коэффициентов правых частейуравнений устройства соединена с второй группой входов первого сумматоравычитателя (1,1)-го блока вычисленияразряда, первый и второй входы элемента сложения по модулю два (дт)-гоблока вычисления разряда подключенык входам знака соответственно 1-йгруппы входов коэффициентов правыхчастей уравнений устройства и входам1-х диагональных элементов уравненийустройства тт 1,п выходы сумматорат,1 -го (т " 1,и, 1= 1, м) блока вычисления разряда соединены с второй группой входов первого сумматора-вычитателя И,+1)-го блока восстановления остатка, выходы (и)-го сумматоРа-вычитателЯ 1 р 1-го (1 = 1,п;= 2,щ) блока восстановления остатка соединены с второй группой входов пеРвого сУмматоРа-вычитателЯ 1 р 1-го блока вычисления разряда, выход знакового разряда (и) -го сумматоравычитателя 1,1-го блока восстановления остатка подключен к первому входу элемента сложения по модулю два 1 р 1-го блока вычислениЯ РазРЯда,второй вход которого подключен к входу знака х-го диагонального элемента устройства, входы 1 1 (1 = 1,п, 11,п;1) элементов устройства соединены с информационными входами ключей 1-й группы 1,1-го (1 = 2 щ) блока восстановления остатка, выходы элемента сложения по модулю два, первого и второго элементов НЕ 1,1-го (1= 1,п; 1 = 1,щ) блока вычисления РазРЯда соединены с 1.р 1-ми выходами соответственно знака и первой и второй компонентами вектора неизвестных системы уравнений устройства, первый и второй управляющие входы ключей1 с-й группы (1 с = 1,и) (х,1)-го (з. 1,пр= 2,щ) блока восстановления остатка соединены с выходами соответственно первого и второго элементов НЕ12 жения но модуле два 1, ) - 1)-го (М 1) блока вычисления разряда. 11 12657932,щ) блока восстановления остатка соединен с выходом элемента сло 2г1265793 Составитель А. ЧекановА. Ворович Техред А,Кравчук Коррект имокосов Ре 67/48 Тираж 671 ВНИИПИ Государственно по делам изобретений 113035, Москва, Ж, Рауказ писноеСССР комите и открытийкая наб., д, 4(5 изводственнополиг акое предприятие, г. Ужгород, ул. Проектн