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

(51) 4 С 06 Р 15/324 САНИК ИЗ 0 БРЕТЕН идетельство СССР Р 15/324, 1979 ельство СССР Р 15/324, 1 977.СТЕМНИЙ ычис с екМ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ ВТОРСНОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕ(57) Изобретение относится к влительной технике и может бытьпользовано автономно или в компсе с ЦВМ для решения систем лн ных алгебраических уравнений. Цельизобретения - увеличение точностирешения, Поставленная цель достигается тем, что устройство содержитвход 1 запуска устройства, блок 2формирования начальных значенийматрицы, блок 3 коммутации, блок 4формирования промежуточных результатов, регистры 5 - 7 хранения промежуточных результатов, блок 8 памяти констант, арифметический блок9, блок 10 управления, вход 11 матрицы значений коэффициентов, вход 12вектора значений правой, части систе"мы уравнений, выход 13 результатаустройства, Увеличение точности обеспечивается для случаев, когда элементы матрицы уравнения имеют величины различного порядка. 11 ил.1325507 27 2 Составитель В, СмирновРедактор Н. Бобкова Техред И.Попович Колб о Подписи Заказ еское предприятие, г. Ужгород, ул. Проектная оизводственно-полиг 112(46 Тираж 672ВНИИПИ Государственного комипо делам изобретений и13035, Москва, Ж, Раушская ета СССРкрытийнаб., д. 4/5Изобретение относится к вычислительной технике и может быть испопьэовано при решении систем линейныхалгебраических уравнений, напримерув системах автоматического управления динамическими объектами,Цель изобретения - повышение точности решения,На Фиг, 1 представлена структурная схема устройства.; на фиг, 2блок формирования начальных значений матрицы; на фиг. 3 - блок комму"тации; на Фиг, 4 - блок формированияпромежуточных результатов на Фиг. 5 - 15блок управления; на Фиг, 6 - узелФормирования уменьшаемых; на фиг, 7 "узел Формирования первых сомножителей; на Фиг, 8 " узел формированиявторых сомножителей; на Фиг. 9 -узел Формирования признака режима;на фиг. 10 - арифметический блок;на фиг. 11 - временная диаграмма работы блока управления,Устройство содержит вход 1 запуска устройства, блок 2 Формированияначальных значений матрицы, блок 3коммутации, блок 4 Формирования промежуточных результатов, с первого потретий регистры 5-7 хранения промежуточных результатов, блок 8 памяти констант, арифметический блок 9, блок10 управления, вход 11 матрицы значений коэффициентов системы линейныхалгебраических уравнений, вход 12вектора значений правой части системы линейных алгебраических уравнений,выход 13 результата устройства, внутренние информационные шины 14-27, выходы 28-31 блока управления,Бпок 2 формирования начальных значений содержит элементы 32 задержкии сумматоры 33-33 Блок 3 коммутации содержит коммутатор 34, мультиплексор 35, узел Зб Формированияуменьшаемых, узел 37 Формирования первых сомножителей, узел 38 Формирования вторых сомножителей, внутреннююинформационную шину 39, Блок 4 Формирования промежуточных результатовсодержит два сумматора 40 и 41, дваумножителя 42 и 43, делитель 44, Блок10 управления содержит генератор 45тактовых импульсов, ждущий мультивибратор 46, с первого по третий триггера 47-49, элемент И 50, элемент НЕ 51,счетчик 52, узел 53 элементов сравнения, узел 54 Формирования признакарежима, Узел 36 Формирования умень где А " матрица коэффициентов размерности пхп, состоящая из элементова; .=1, и, 1=1, и);В - вектор-столбец размерностии, составленный из элементов правыхчастей ЬХ - вектор-столбец решения размерности и, составленный иэ элементов х,Эта система при йе А0 имеетдля любых правых частей уравненийоднозначно определенное решениеХ=(хх) . Для отыскания этого .твектор-решения воспользуемся обратнойматрицей А , В этом случае векторрешение Х=А- Б вычисляется простымперемножением матриц,1 Для отыскания обратной матрицы А реализован алгоритм обращения матри" цы, согласно которому для вычисления матрицы А необходимо провести вычисления матриц: А ф 1, А, А+ а, 1 "Ф Щф где сР, = 0 . (1., 1, ш = 1,и),Г 1, т=,10, шФ,1 Устройство на примере решения системы линейных алгебраических уравнений третьего порядка работает следунэщим образом.Пусть исходная система имеет вид шаемых содержит пт мультиплексоров 55. Узел 37 формирования первых сомножителей содержит и мультиплексоров 55. Узел формирования вторых сомножителей содержит п мультиплексоров 55, Узел 54 формирования приэнакарережима содержит Р элементов НЕ 56, где Р= = 1 о 8 п 1, элемент И-НЕ 57. Арифметический блок 9 содержит умножитель 58 и сумматоры 59,Устройство предназначено для решения системы линейных алгебраических уравнений вида1325507 021203110,1 Окоторая по шине 39 поступает на входымультиплексора 35 и блоков 36 - 38.К выходу блока 35 подключена шина,номер диагонального элемента которойсовпадает с номером шага вычисленийпереданного по шине 19 управления изблока 10 управления, На первом шагена шину 22 передано число О. Последовательность чисел по шине 39 поступает на вход блока 36, на выходе которого сформирована на первом шаге последовательность чисел 1 О О 2 О 3 1 1 О. 25 Последовательность чисел с выходакоммутатора 34 поступает на вход блока 37, на выходе которого на первомшаге сформирована следующая последовательность чисел 021203110,которая по шине 18 поступает на информационные входы блока 3, в частности на входы коммутатора 34.Работа устройства синхронизиру ется блоком 10 управления и начинается подачей сигнала на вход 1 устройства. При этом устанавливается в нуль счетчик 52, устанавливаются в нулевое состояние КЯ-триггер 49, а в единичное состояние К 8-триггер 47.1Перевод КЯ-триггера 48 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора.45 тактовых 40 импульсов. В результате с выхода КЯ- ,триггера 48 единица поступает на один из входов элемента И 50, обеспечивая прохождение синхроимпульсов, поступающих на второй ее вход от ждущего 45 мультивибратора 46. С выхода элемента И 50 синхроимпульсы поступают на счетный вход счетчика 52. Период следования синхроимпульсов выбирается из условия полного завершения одного 50 шага вычислений.На первом шаге вычисления с выхода счетчика 52 поступает в двоичном коде "1" на шину 19 управления и на вход блока 54, в соответствии с законом работы которого на его выходе на первом шаге сформирован "0"На всех последующих шагах на выходе 28 присутствует . С выхода коммутатора 34 передана х+ 2 х+ х = Ь 2 х,+ х +Зх = 2 Ь х,+ х+ х= 2 Ь, т.е. АХ = В,121 где А = 2 1 3 - матрица коэффици 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, на выходе которого на первом шаге вычислений появляется последовательность чисел О 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 на регистр поступает управляющий сигнал , азрешающий чтение информации из того регистра. Период следования синхроимпульсов с выхода ждущего муль тивибратора 46 выбирается таким образом, что за время существования низкого перепада напряжения на его выходе полностью завершаются вычисления на данном шаге и запись результата в регистр 5, При появлении высокого потенциала на выходе элемента И 50 на вход регистра 5 поступает "1", а на второй - "0", т.е. происходит перезапись информации из первого регистра во второй, При появлении следующего синхроимпульса выдается разрешение на чтение результата из регистра 6 и на запись результата следующего шага вычисления в регистр 5, Количество шагов вычислений равно порядку обращаемой матрицы.Результаты вычислений на выходах отдельных блоков для каждого шага приведены в таблице. Влок 212031 21203 О 2 203 11 2"4 " 1203110 3 333 52 11 33 ЭЭ 2-1010-1 "1 002031 О 3-2"2"411-1"1 1510-11 1111 4 12 411-1-1 2-1510-111-3 Э 3 Э 3 5 О"111"Э 0- 2 - 1 0 - 4- 2 0 - г - 1,которая складывается в соответствиис номерами с последовательностью чисел, поступающей по шине 23, в сумматоре 41, на выходе которого на первом Ошаге сформирована последовательностьчисел 1-2-12-411-1" 1,Данная последовательность чисел с 5 шины 26 поступает на входы регистра 5 хранения промежуточных результатов, который служит для хранения развязки между собой шагов вычислений и устранения эффекта "гонок". Во время вы числения на каком-либо шаге на регистр 5 по выводу 29 поступает управляющий сигнал "0" с выхода элемента И 50 блока управления, разрешающий запись информации в данный регистр,02"19-4-20"2 14 8 2 3 3 Эв ви в й111На каждом шаге вычислений в узле 53 происходит сравнение номера шага вычисления, поступающего с выхода счетчика 52 и числа "4" (в общем слу 5 чае и+1, где и - порядок матрицы), поступающего по шине 20 четвертой константы иэ блока 8 памяти.В результате окончания последнего третьего шага вычисления в ре гистр 6 записана последовательность чисел- 2 - 1 5 1 0 - 1 1 1 - 31представляющая элементы обращенной матрицы А . В момент появления следующего четвертого синхроимпульса на выходе элемента И 50 на управляющий вход регистра 6 поступает сигнал чтения. Номер четвертого синхроимпуль са поступает также на вход узла 53, в результате чего на выходе сформирован управляющий импульс, который переводит триггер 49 в единичное состояние, а также переводит в нулевое 28 состояние триггеры 47 и 48, что соответствует запиранию блока 1 О управления.Сигнал "1" на разрешение чтения с выхода КЯ-триггера 49 по шине 31 30 поступает на управляющий вход регистра 7, Происходит перезапись информации с регистра 6 в регистр 7,Информация из регистра 7 поступает по шине 27 на входы умножителей 58 арифметического блока, на другие входы которых поступает с входа 12 информация о вектор-столбце правых частей уравнения с выходов перемножителей поступают на входы соответству ющих сумматоров 59, сигнал на выходе которых и представляет искомый вектор решения, который поступает на выход 13 результата устройства.45формула изо брет енияУстройство для решения систем линейных алгебраических уравнений, содержащее арифметический блок и блок управления, о т л и ч а ю щ е е с я тем, что, с целью повышения точности решения, в него введены блок формирования начальных значений матрицы, блок коммутации, блок памяти кон 55 стант, блок формирования промежуточ.ных результатов, первый, второй и третий регистры хранения промежуточных результатов, а входов, где и -порядок системы уравнений, векторазначений правой части системы уравнений устройства подключены к информационным входам первой группы арифметического блока, пГ входов матрицызначений коэффициентов системы уравнений устройства подключены к одноименным входам первой группы блока формирования начальных значений матрицы,вход запуска устройства подключен квходу запуска блока управления и квходу считывания блока памяти констант, 1-й выход (1=1 п) первойгруппы блока памяти констант подключен к 1-му входу значения режима блока управления, -й выход второй группы блока памяти констант подключен кх-му входу второй группы блока формирования начальных значений матрицы ик х-му входу первой группы блока формирования промежуточных результатов,:1-й выход третьей группы блока памяти констант подключен к 1-му информационному входу первой группы блока коммутации и к -му входу второйгруппы блока формирования промежуточных значений, 1.-й выход четвертойгруппы блока памяти констант подключен к х-му информационному входу второй группы блока коммутации, первый,второй и третий выходы блока управления подключены к входам считываниясоответственно первого, второго итретьего регистров хранения промежуточных результатов, четвертый выходблока управления подключен к управляющему входу блока коммутации, д-й выход группы блока управления подключенк -му информационному входу третьейгруппы блока коммутации, 1-й выход;где 1=1п , блока формирования .начальных значений матрицы подключенк 3-му информационному входу четвертой группы блока коммутации, 3-й вы-ход блока формирования промежуточныхрезультатов подключен к информационному входу 1-го разряда первого регистра хранения промежуточных результатов, выход З-го разряда первого регистра хранения промежуточных резуль"татов подключен к 1-му информационному входу 1-го разряда второго регистра хранения промежуточных результа"тов, выход 1-го разряда второго регистра хранения промежуточных результатов подключен к 1-му информационному входу пятой группы блока коммутации и к информационному входу 1-горазряда третьего регистра хранения промежуточных результатов, выход 1-го разряда третьего регистра хранения промежуточных результатов подключен к 1-му информационному входу второй группы арифметического блока, 1-й выход групп с первой по четвертую выходов блока коммутации подключен к 1-му входу соответственно групп с третьей по шестую входов блока Формирования промежуточных результатов, Выходы арифметического блока подключены к выходам результата устройства, при этом блок формирования начальных значений матрицы содержит п сумматоров и и "и элементов задержки, первый информационный вход 1.-го сумматора подключен к ( - 1)п+1-м входам первой группы блока формирования начальных значений матрнцы, второй информационный вход 1.-го сумматора подключен к 1-му входу второй группы блока формирования начальных значений матрицы, входы элементов с (1 п+ +1)-го по (1+1)п-й, где 1=0,1, ,п, задержки подключены соответственно к входам с (1 п2)-го по1(1+1)и+1+11-й первой группы блока формирования начальных значений матрицы, выход 1.-го сумматора подключен . к 1(-1)п+11-му выходу блока Формирования начальных значений матрицы, а выходы с (1 сп+К+2)-го по (1+1)п+ +1+ 1 -й блока формирования начальных значений матрицы подключены к выходам элементов задержки соответственно с (М+1)-го по В+1)п-й, при этом блок коммутации содержит коммутатор, мультиплексор, узел формирования уменьшаемых, узел формирования первых сомножителей, узел формирования вторых сомножителей, управляющий вход блока коммутации подключен к управляюще - му входу коммутатора, х-й информационный вход первой группы блока коммутации подключен к -му входу первой группы узла Формирования уменьшаемых и к 1-му входу первой группы узлаформирования первого сомножителя,Х-й информационный вход второй группы блока коммутации подключен к 1.-мувходу второй группы узла Формирования уменьшаемых, х-й информационныйвход третьей группы блока коммутацииподключен к х-му управляющему входумультиплексора блока коммутации, кх-му входу третьей группы узла формирования уменьшаемого, к -му входу102030 50 55 четвертой группы узла Формированияуменьшаемых подключен к второму информационному входу 1-го мультиплексора узла формирования уменьшаемых,выход 1-го мультиплексора узла формирования уменьшаемого подключен к 1-мувыходу узла формирования уменьшаемых,при этом узел формирования первых сомножителей содержит п мультиплексоров, 1.-й вход первой группы узлаформирования первых сомножителей подключен к первому информационному входу -го мультиплексора узла формирования первых сомножителей, 1-й вход второй группы узла формирования первых сомножителей и к 1.-му входу первой группы узла Формирования вторых сомножителей, 1-е информационные входы четвертой и пятой групп блока коммутации подключены к 1-м информационным входам соответственно первой и второй групп коммутатора блока коммутации, 1-й выход коммутатора блокакоммутации подключен к 1-му информационному входу мультиплексора, блока коммутации, к 1"му входу четвертой группы узла формирования уменьшаемых,к 1-му входу третьей группы узла фор-, мирования первых сомножителей, к 1-му входу второй группы узла формирования вторых сомножителей, выходы мультиплексора блока коммутации подключены к выходам первой группы блока коммутации, выходы узла формирования уменьшаемых подключены к выходам второй группы блока коммутации, выходы узла формирования первых сомножителейподключены к выходам третьей группыблока коммутации, выходы узла Формирования вторых сомножителей подклюфчены к выходам четвертой группы блока коммутации, при этом узел формирования уменьшаемых содержит и мультиплексоров, 1-и вход первой группы узла Формирования уменьшаемых подключен к первому информационному входу (х)п+1.1-го мультиплексора узла Формирования уменьшаемых, 1-й входвторой группы узла Формирования уменьшаемых подключен к первому информационному входу мультиплексоров с (1-1)п+1-го по (1.-1)п+1-11 -й и с (1-1)п+1+11 -го по 1 п-й узла формирования уменьшаемых, 1-й вход третьей группы входов узла формирования уменьшаемых подключен к управляющему входу 1-го мультиплексора узла Формирования уменьшаемых, 1-й входвторой группы узла Формирования пер" вых сомножителей подключен к управляющему входу .-го мультиплексора узла формирования первых сомножителей, 1-й5 информационный вход 1.-го мультиплексора, где 1=2п+1, узла формирования первых сомножителей подключен к (д)п+-1-му входу третьей группы узла формирования первых сомножителей, выход -го мультиплексора узла формирования первых сомножителей подключен к х-му выходу узла Формирования первых сомножителей, при этом узел формирования вторых сомножителей содержит и мультиплексоров, 1.-й вход первой группы узла формирования вторых сомножителей подключен к управляющему входу 1.-го мультиплексора узла Формирования вторых сомножителей, -й информационный вход г-го, где г=1,п, мультиплексора узла . формирования вторых сомножителей подключен к (х)п+г-му входу второй группы узла формирования вторых со множителей выход 1.-го мультиплексора узла формирования вторых сомножителей подключен к -му выходу узла формирования вторых сомножителей, при этом блок формирования промежуточных ЗО результатов содержит два сумматора, два умножителя, делитель, входь пер. вой группы, входы второй группы, входы третьей группы, входы четвертой группы, входы пятой группы и входы шестой группы блока формирования промежуточных результатов подключены к одноименным информационным входам соответственно первой группы делителя, первой группы первого сумматора, вто О рой группы первого сумматора, первой группы второго сумматора, первой группы первого умножителя и второй группы первого умножителя блока формирования промежуточных результатов, выхо ды первого сумматора подключены к одноименным информационным входам второй группы делителя, выходы которого подключены к одноименным информационным входам первой группы второго умножителя блока формирования промежуточных результатов, выходы первого умножителя блока Формирования промежуточных результатов подключены к одноименным информационным входам второйгруппы второго умножителя, выходы которого подключены к одноименным информационным входам второй группы второго сумматора блока формирования промежуточных результатов, выходы второгосумматора блока Формирования проме-.жуточных результатов подключены к одноименным выходам блока формированияпромежуточных результатов, при этомблок управления содержит генератортактовых импульсов, три триггера,ждущий мультивибратор, узел формирования признака режима, узел элементовсравнения, счетчик, элемент И, элемент НЕ, вход запуска блока управления подключен к входу установки в "1"первого триггера блока управления, квходу установки в "О" второго триггера блока управления и к входу установки в "О" счетчика блока управления,1.-й вход режима блока управления подключен к д-му входу первой группыузла элементов сравнения блока управления, о-й выход, где ц=11 оЕ и , счетчика блока управленияподключен к и-му входу второй группыузла элементов сравнения, к о-му входу узла форьярования признака режимаблока управления и к о-му выходу группы блока управления, выход первоготриггера блока управления подключен квходу установки в "1" третьего триггера блока управления, выход генератора тактовых импульсов блока управления подключен к входу ждущего мультивибратора блока управления и к счет"ному входу третьего триггера блокауправления, выход узла элементовсравнения блока управления подключенк входу установки в "О" первого триггера блока управления, к входу установки в "1" второго триггера блокауправления и к входу установки в "О"третьего триггера блока управления,выход ждущего мультивибратора блокауправления подключен к первому входуэлемента И блока управления, выходтретьего триггера блока управленияподключен к второму входу элемента Иблока управления, выход элемента Иблока управления подключен к счетному входу счетчика блока управления,к входу элемента НЕ блока управления,выход элемента НЕ блока управленияподключен к первому выходу блока управления, выход элемента И блока управления подключен к второму выходублока управления, выход второго триг"гера блока управления подключен ктретьему выходу блока управления, выход узла формирования признака режима блока управления подключен к1 Зчетвертому выходу блока управления, при этом узел формирования признака режима содержит 1 оЕ,пэлементов2НЕ, элемент И-НЕ, первый вход узла формирования признака режима подключен к первому входу элемента И-НЕ узла формирования признака режима, а-й вход, где зщ 21 о и , узла формирования признака режима подклю 32550714чен к входу (з)-го элемента НЕ узла формирования признака режима, выход (в-)-го элемента НЕ узла формирования признака режима подключен ка-му входу элемента И-НЕ узла формирования признака режима, выход элемента И-НЕ узла формирования признака режима подключен к выходу узла 1 О формирования признака режима,