Цифровое устройство для решения системы линейных уравнений

нйтеитно-техньчес О П И С А Я Г ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(22) Заявлено 17.10.77 (21) 2531210/18-24с присоединением заявки М(23) Приоритет -Государственный комитет СССР по делам изобретений и открытий(088, 8) Опубликовано 05,02.80. Бюллетень Мо 5 Дата опубликоаания описания 10,0280(72) Авторы изобретения Л. Я. Нагорный, П. А, Лебедев и И. А. жуков Киевский ордена Трудового Красного Знамени институт инженербв-гражданской авиации(54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 1Изобретение относится к области цифровой вычислительной техники и может быть использовано при построении специализированных и клавишных . ,вычислительных машин, предназначенных для решения задач методами матричной алгебры.Известны устройства, содержащие схемы набора элементов матриц, арифметическое устройство, гейератор импульсов, программное и коммутирующее устройство, блок управления, устройство вывода и индикации, блоки установки размерности матрицы, опре- деления знаков членов определителей, 15 равных нулю, элементы ИЛИ и И (1).Однако в этих устройствах процесс вычисления заканчивается на стадии раскрытия и вычисления определителя," их Функциональные возможности огранйчены, они имеют малое быстродействие вычисления.Наиболее близким по технической сущности к предложенному является цифровое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицу решающих бло" ков, каждая из которых содержит ирешающих блоков, арифметический блок, блок управлениями блок вывода и инди- ЗО 2кации, два программных бЛока, блокпостоянной памяти, блок оперативнойпамяти, блок сравнения, блок вводакоэффициентов, два элемента ИЛИ, Каждый решающий блок содержит два элемента И, элемент НЕ, регистр и эле,мент ИЛЙ, Каждый программный блоксодержит счетчик столбцов и счетчикстрок 2),Однако это устройство требуетбольших аппаратурких затрат при решении системы линейных уравнений высокого порядка.Цель изобретения - упрощение устройства,Это достигается введением дополнительных элементов в цифровое устройство для решения системы линейныхуравнений, содержащее первую и вторуюматрицы решающих блоков, арифметический блок, блок управления, блок инднкации, первый и второй программные,блоки, блок постоянной памяти, блокоперативной памяти, блок сравнения,блок ввода коэффициентов, элементыИЛИ, причем первый выход арифметического блока соединен с первым входом блока индикации. Первый входблока управления соединен со вторымвыходом арифметического блока, пер,714409 1- равления, седьмой выход которого поддом блока оперативной памяти. Четверный вход которого подключен к перному выходу блока управления, второйи третий выходи которого соединенысоответственно с первыми управляющими входами каждого решающего блокапервой и второй матриц. Четвертый ипятый выходы блока управления соединены соответственно со вторыми управляющими входачи каждого решающего блока первой и второй матриц, Третий и четвертый выходя арифметического блока подключенысоотнетстненнок первым информационным вхбдам каждого решающего блока первой и второйматриц. Второй и третий входы арифметического блока соединены соответственно через первый и второй элементы ИЛИ с выходами решающих блоковпервой и второй матриц, шестой выходблока упранлейия соединен с первым йвторым входами первого программнОго.блока, первый и второй выходы которого подключены ко второму и третьемувходу блока индикацйи, Второй информационный вход, каждого решающегоблока первой матрицы подключен к соответствующему выходу из первой групйй виходбв вттсрого программного блока, Третий информационный входкаждого решающего блока первой матрицы подключен к соответствующемувыходу из второй группы выходов второго программного блока, перний и нторс." выходи которого соединены соответственно с первым и вторым входами бло- ка сравнения, Выход блока сравнения подключен к третьему входу блока упключен к первому и второму входамвторого програмМного блока. Четвертый вход арифметического блока соединен с первым выходом блока вводакоэффициентов, второй выход которого подключен к второму входу блокауправления. Третий выход блока вводакоэффициентов соединен с первым вхотый выход подключен к третьему и четвертому входам первого програМмногоблока, Пятый выход подключен к третьему и четвертому входам второгопрограммного блока. Восьмой выходблока управления соединен со вторымвходом блока оперативной памяти, выход которого подключен к пятому входу арифметического блока, шестойвход которого соединен с выходом блока.постоянной памяти;-входкоторого подключен к пятому выходу арифметического блока, В устройство введены третья матрица решающих блоков, третий элемент ИЛИ причем. девятый выход блока управленя подклйчен к первбму управляющему входу каждого решающего блока третьей матрицы, первый информационний вход которого соединен с шестым выходом арифметИческого блока. Выходы всех решающих блоков третьей матрицы через третий 15 20 25 ЗО 35 40 45 50 55 60 элемент ИЛИ подключены к седьмом входу арйфметйческого блока, Второй информационный вход каждого решающего блока третьей матрицы подключен к соответствующему выходу из первой группы выходов второго программного блока. Третий информационный вход подключен к соответствующему выходу из второй группы выходов второго программного блока. Второй управляющий вход каждого решающего блока третьейматрицы подключен к десятоМу выходу блока управления.Блок-схема устройства представлена на чертеже. Цифровое устройство для решения системы линейных уравнений с разреженной матрицей содержит матрицу 1 решающих блоков, матрицу 2 решающих . блоков, матрицу 3 решающих блоков, арифметический блок 4, блок 5 управления; блок биндикации, программные блоки 7 и 8, блок 9 постоянной памяти, блок 10 оперативной памяти, блок, 11 сравнения, блок 12 ввода коэ Ффициентов, элейенти ИЛИ 13-15, каждая матрица 1 состоит из 10 1 решающих блоков 16.Устройство работает, следующим образ ом.С помощью блока 12 ввода коэффициентов набираются построчно коэффициент за коэффициентом матрицы Н. Набор этих коэффициентов производится, например, на цифровой клавиатуре, которая имеет клавиши строк и столбцов. По сигналам, поступающим с блока 12 программный блок 7 вырабатывает сигналы У и 2 поступающие на входы решающего блока 16 матрицы Н . Таким образом, произошел выбор ячейки С, куда заносится преобразованный на арифметическом блоке 4 коэффицйент Е . При наборе коэффициента 1.н зайускается блок 5 управления, который работает по микропрограмме преобразования коэффициентов матрицы по методу разложенйя матрицы на треугольные множители с записью этих коэффициентов в виде таблицы множителей в матрицу 1, коэффициент Ьпоступает в арифметический блок 4, преобразуется и поступает в ячейку С+ решающего блока 16 матрицы 1. Туда же поступает микрокбманда с блока 4. управления, При совпадении сигналов У 2 и микрокоманды происходит запись элемента Ь в соответствующем решающем блоке 16, Ввод последующих коэффициентов подматрици Н осуществляется аналогично выше опйсанному, только программный блок 7 вырабатывает соответствующие координатные сигналы У и 2 которые выбирают соответствукиие решающие блоки 16 С; матрицы 1, Для определения обработки коэффициентов Ь в строке матрииы Н 4 служит блок 11 сравнения. Он сравнй.вает содержимое счетчикон строк й столбцов первого программного блока 6. Когда эти счетчики равны, идет об" работка диагональных элементов матрици Н. Если счетчик строк меньще счетчика столбцов, то ведется обработка коэффициентов выше главной диагонали матрици, если счетчик стрбк больше счетчика столбцов, то ведется обработка коэффициентов, расположенных ниже главной диагонали матрицы. Результаты сравнения с блока 11 сравнения передаются н блок 5 управления, который вырабатывает определенные микрокоманди, необходимые для арифметического блока 4, который ведет обработку коэффициентов. Блой 4вйполняет операции сложения, вычитания, умножения, деления, накопления и алгебраического сложения, которые обеспечивают весь вичислительныйпро.цесс, Микропрограммы, выполняющие 20 эти операции, могут быть фзашиты ,в матрицах мйкропрограмм и микроко манд. Эти микропрограммы служат как микроподпрограммы для основных микропрограмм решения системы линейных 25 уравнений. После ввода всех коэАфициентов матрицы Н на блоке 12 нажимается, например, клавиша И. По этой команде запускается блок 5 управления, который работает по микро- З 0 программе обращения матрицы Н в обратную матрицу Н , Для рбращенияматрицы используется метод прямыхрешений с использованием разложенияна треугольние множители, Этот методбыстродействующий и по аппаратурным затратам экономичный. ОбращЕние матрицы Н заключается в том, что изполученной матрицы коэффициентов матрицы 1 выбирается треугольная матрица, которая пОэлементно переписыва ется в матрицу 2 решающих блоков через элемент ИЛИ 13 и арифметический блок 4. При этом блок 5 управления работает по микропрограмме перезаписи матрицы, вырабатывая определенные 45 микрокоманди для выборки коэффициентов иэ решающих блоков 16 матрицы 1 и пересылки их в решающие блоки 16 матрицы 2, устанавливая при этом счетчики строк и столбцов программных 50блоков 7 и 8 в соответствующие состояния. Далее производится матричйая операция умножения матрицы 2 на матричные треугольные множители матри. цы 1. Результирующая матрица накапливается в матрице 2. Умножение матриц производится традиционным способом;строка одной матрицы умножается на столбец другой матрицы. При умножении матриц коэффициенты вызываются в арифметический блок 4 через элемент ИЛИ 13 и элемент ИЛИ 14 и происходит их умножение с алгебраическим накоплением. Обратная Матри-, ца Н накапливается в матрице 2 решающйх блоков. При обращении матри-,цы Н программные блоки 7 и 8 работают по программе, вырабатывая соответ-. ствующие сигналы Ь;,и У". Е , Далее на блоке 12 нажимается клавиша Н , что означает, что в матрицу 1 решающих блоков вводятся коэффициенты верхней подматрипи Н . Вноц коэффициентов осуществляется описанным выше способом, когда осуществляется ввод подматрици ННажимается клавиша фумножить, и происходит операция матричного умножения Нна Н , Матричное произведение Н Н= А хранится в матрице 1. Нажатием клавиши 0 осуществляется ввод я части известного вектора, которая соответствует части матрицы Н , Ввод 0 поэлементно осуществляется в блок 10 оперативной памяти, по микрокоманде с блока 5 управления. После этого нажимается клавиша умножить 1 и происходит матричное умножение матрицы 1 на известный вектор О. Получается произведение Н 11 О в виде вектора размерностью 0 . Полученный вектор Н Н О для йакопления засылается в блок 9 постоянной памяти, где. накапливается вектор 0 . Нас жатием клавиши Ф запускается блок 5 управления и происходит занесение коэффициентов подматрицы ф в матрицу 2 решающих блоков через арифметический блок 4 с блока 12, Занесение коэффициентов происходит вышеописанным способом. После этого нажимается клавиша 1 умножить и происходит опера" ция матричного умножения матрицы 4 на матрицу 2. Полученное матричное произведение Ф А = Н Н ф хранит.ся в матрице 1. Подматрица связи Юс - единичная матрица при включении устройства находится в дополнительной матрице 3 решающих блоков. Далее осуществляется матричная операция сло" жения И - Н Н ф = К , Результат операции величина К накапливается в матрице 3. Вызов коэффициентов маттрицы 3 решающих блоков на арифметический блок 4 осуществляется по микрокомандам с блока 5 управления, поступающим на управляющие входы решающих блоков 16 матрицы 3 через элемент ИЛИ 15 при выработке соответствующих сигналов У. и Е программным блоком 8. Пересылка коэффициентов в матрицу 3 сарифметического блока 4 осуществляется по микрокоманде, поступающей с блбка 5 управления на нход соответствующего решающего блока 16 матрицы 3. Далее осуществляется ввод второй части исходной матрицы Н, т.е, осуществляется последовательный ввод подматриц Н, Н , 0, ф и проделываются все матрйчние операции с этими подматрицами описанным выше способом. Последовательность нажатий клавиш остается без изменения. После выполнения всех рассмотренных нише операций в блоке 9 постоянной памяти накопится выражение Н Н;, О , + НН " 0= 0 с а в матрице 3 накопится результат И - НН" ф+ Н Н ф =Кд. Осуществляя ввод последующих частей исходной матрицы Н по подматрйцам Н Н, 0, ф до последней части Н Н 0 ф, где И12 и осуществив все матричные операции описанньпч выше спбсобом; получим окойчательные результаты 0 с = НН,0+ + н,н 0+.+ Ннни к цц;о 110 О накапливается в блоке 9, а ",с =Ис ( ННФ+ Н Нф++ + Н 1 Н;" ф,)=Ис -,( НН-"р), накапливается .в матрице" 3.Для"нахождейия неизвестного вектора связи Х нажимается клавйша Х, По команде с блока 11 ввода запускается блок 5 управления, которйй вырабатывает микрокоманды перезаписи .Кг. .из матрицы 3 в матрицу 1 решающих бло-.ков, чтобы выйти на микроподпрограм- Ю му обращения матрицы, т. е. К обращается в К- . Для обращения используется метод прямых решений с использованием разложения матрицы на треуголь-ные множителн. Обращение .идет выше описанным способом, когда находилась обратная матрица Н. Далее происходит матричная операция умножения К 0сХДля этого поэлементно на арифметйческий блок 4 вызывается 0 с из Зо блока 9 постоянной памяти и К " иэ матрицы 1 решающих блоков через элемеит ИЛИ 13. Результат вектора х накапли,вается в блоке 9. После нахождения вектора Х неизвестнйй вектор Х находится по частям. Нажимается, например, клавиша ф , по которой запускаетсяблок 5 управления и происходитзанесение коэффициентов подматрицы ф в матрицу 2 решающих блоков черезарифметический блок 4 с блока 12. За Онесейие коэффициентов происходит аналогично вышеописанному. По нажатиюклавйши умножить происходитматричная операция умйожения ФХс на арифметическом блоке 4 с вызовом поэлементно Ф и х из матрицы 2 и блока9, Результат йакаплйвается в блоке 9,При нажатии клавиши 0 осуществляемввод 0 - часть известного вектора вблок 10 оперативной памяти, После 50ввода происходит вычитание 0 - ф Х =3= О Вычитание происходит в арифметическом блоке 4 с вызовом элементоввектора йз блока 10 и вектора ф Х:из .блока 9. Результат вычитания засй- улается в блок 9 постоянной памяти.Далее осуществляется ввод подматрицыН в матрицу 1, который рассматрива ется выше. Находится обратная матрица Н , которая записывается в матрице 1. После этого нажимается клавиша . умйожить, по которой происходитматричная операция умножения матрицы1 на блок 9 постоянной памяти. Блок5 уйравления работает по микропрограмме умножения. На арифметическом блоке ч-выполняется выражение Н" 0 = Х1Результат вектора Х записывается в блок 9, Численное значение найденного вектора Х передается в блок 6 индикаций.Осуществляется ввод последующих частей матрицы Н по подматрицам ф, Я и Н до последней части фн, 0 н и Н н и после произведения всех матричных операций и вычислений описанным выше способом, получаютсявсе численные значения вектора :Х= )Х ., Х= ХПолученные результаты решения исходной системы уравнения по частям печатаются на бумажной ленте или высвечиваются на цифровом табло.Решение системы линейных уравне-, ний по частям значительно сокращает аппаратурные затраты, Предложенное устройство дает воэможность решить практическилюбую большую систему линейных уравнений с разряженной матрицей в малом аПпаратурном объеме. Исходную матрицу Н можно разбить на лю-.бое число подматриц Н, Н,.Нм и порядокподматриц можно взять про- извольным. В устройстве максимальный порядок подматриц равен 10, т. е, все матрицы 1, 2 и дополнительная матрица имеют размерность 10 х 10 решающих блоков. Устройство в этом объеме обеспечивает решение любой большой системы, линейных уравнений высокого порядка с разреженной матрицей.Суммарный аппаратурный экономичес- кий эффект составляет 28480 руб, Кроме того, сокращаются различные матерналы, цеховые и заводские расходы. Значительно сокращаются монтажные работы.Формула изобретенияЦифровое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицы решающих блоков, арифметический блок, блок управления, блок индикации, первый и второй программные блоки, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициентов, элементы ИЛИ, причем первый выход арифметнческого блока соединен с первым входом блока индикации, первый вход блока управления соединен со вторым выходом арифметического блока, первый вход которого подключен к первому выходу блока управления, второй и третий выходы которого соединены соответственно с первыми управляющими входами каждого решающего блока первой и второй матриц четвертый и пятьй выходы блока управления соединены соответственно со вторыми управляющими входами каждого .решающего блока первой и второй матриц, третий и четвертый выходы арифметического блока подключен соответст-венно к первым информационным входамкаждого решающего блока первой и второй матриц, второй и третий входы 5арифметического блока соединены соответственно через первый и второй элементы ИЛИ с выходами решающих блоковпервой и второй матриц, шестой выходблока управления соедийен с первЮ 4"й Двторым входами первого программногоблока, первый и второй выходы которого подключен ко второму и третьемувходу блока индикации, второй информационный вход каждого решающего блока первой матрицы подключен к соответствующему вйходу из первой группы выходов второго программного блока, третий информационный вход каждого решающего блока первой матрицЫподключен к соответствующему выходу 20из второй группы выходов второго программногоблока, первый и второй выходы которого соединены соответственяо с первым и вторым входами блокасравнения, выход блока сравнения подключен к третему входу блока упраВления, седьмойвыход которого подключенк первому и второму входам вторбгопрограммного блока, четвертый входарифметического блока соединен с первым выходом блока ввода коэффициентоввторой выход которого подключен к второму входу блока управления, третий виход блока ввода коэффициентов соединенс первым входом блока оперативной памяти, четвертый выход подключен к третьему и четвертому входам первогО"программного блока, пятый выход подклю- :чен к третьему и четвертому входам второго программного блока, восьмойвыход, блока управления соединен совторым входбм блока оперативной памяти, выход которого подключен к пятому входу арифметического блока,шестой вход которого соединен с выходом блока постоянной памяти, входкоторого подключен к пятому выходуарифметического блока, о т л ич а ю щ е е с я тем, что,с цельюпрсценйя устРойства, оно содержиттретью матрицу решающих блоков, третий элемент ИЛИ, причем девятый выХод блока управления подключен к первому управляющему входу каждого решающего блока третьей матрицы, первый информационный вход которого соединен с шестым выходом арифметического блока, выходы всех решающих блоков третьей матрицы через третийэлемент ИЛИ подключены к седьмоу входу арифметического блока, второй информационный вход каждого решающегоблока третьей матрицы подключен к соответствующему выходу иэ первой группы выходов второго программного блока, третий информационный вход подключен к соответствующему выходу из второй группы выходов второго программного блока, второй управляющий входкаждого решающего блока третьей матрицы подключен к десятому выходу блока управления,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 404090, М.Кл. С 06 Р 15/32, 1973,2. Заявка Р 2337295, 1976,по которой принято решение о выдачеавторского свидетельства (прототип) .714409 дактор А. В Закаэ 9290/4 Тираж 751 Подписное ИИПИ Государствен по делам иэобрет 5, Иосква, Х, ного комитета СССРений н открытияРаушская наб., д, 4/ 3 л, Проектна Патент , г, Ужгород Филиал Составитель Н. Палеевав ТехредН.Ковалева Корректор Ю.Макаренк