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

 

нйтеитно-ТВх нг-," чес!

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

<г > 714409

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (51)м К 2

G 06 F 15/34 (22) Заявлено 171077 (21) 2531210/18-24 с присоединением заявки ¹(23) Приоритет—

Государственный комитет

СССР по делам изобретений и открытий (53} УДКб81.14 (088, 8) Опубликовано 0502.80. Бголлетень ¹ 5

Дата опубликоаания описания 10,02 ° 80 (72) Авторы изобретения

Л. Я. Нагорный, П. A. Лебедев и И. A. 7(ухов

Киевский ордена Трудового Красного Знамени институт инженербв- гражданской авиации

1 (71) Заявитель (54) ЦИФРОВОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМЫ

ЛИНЕЙНЫХ УРАВНЕНИЙ

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

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

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

Наиболее близким по технической сущности к предложенному является цифровое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицу решающих блоков, каждая из которых содержит n решающих блоков, арифметический блок, блок управлениями блок вывода и инди- З0

2 кации, два программных блока, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода . коэффициентов, два элемента ИЛИ, Каждый решающий блок содержит два элемента И, элемент НЕ, регистр и эле,мент ИЛЙ. Каждый программный блок содержит счетчик столбцов и счетчик строк (2j, Однако это устройство требует больших аппаратурких затрат при решении системы линейных уравнений высокого порядка.

Цель изобретения — упрощение устройства.

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

ИЛИ, причем первый выход арифметического блока соединен с первым вхо1 дом блока индикации. Первый вход блока управления соединен со вторым выходом арифметического блока, пер,714409

1 ный вход которого подключен к перному выходу блока управления, второй и третий выходы которого соединены соответственно с первыми управляющими входами каждого решающего блока первой и второй матриц. Четвертый и пятый выходы блока управления соединены соответственно со вторыми управляющими входами каждого решающего блока первой и второй матриц. Третий и четвертый выходы арифметического блока подключены соотнетстненно к первым информационным вхбдам каждого решающего блока первой и второй матриц. Второй и третий входы арифметического блока соединены соотнетственно через первый и второй элементы ИЛИ с выходами решающих блоков первой и второй матриц, шестой выход блока у..цэанлейия соединен с первым и вторым входами первого программнОго .блока, первый и второй выходы которого подключены ко второму и третьему входу блока индикацйи. Второй информационный вход, каждого решающего блока первой матрицы подключен к соответствующему выходу из первой групHH выходбв нттсрого программного блока. Третий информационный вход каждо го решающего блока первой матрицы подключен к соответствующему выходу из второй группы выходов второго программного блока, первый и нторс." выходы которого соединены соответственно с первым и вторым входами бло- ка сравнения. Выход блока сравнения подключен к третьему входу блока упранления, седьмой выход которого подключен к первому и второму входам второго програмМного блока. Четвер.тый вход арифметического блока соединен с первым выходом блока ввода коэффициентов, второй выход которого подключен к второму входу блока управления. Третий выход блока ввода коэффициентов соединен с первым входом-блока оперативной памяти. Четвертый выход подключен к третьему и четвертому входам первого програМмного блока. Пятый выход подключен к третьему и четвертому входам второго программного блока. Восьмой выход блока управления соединен со вторым входом блока оперативной памяти, выход которого подключен к пятому входу арифметического блока, шестой вход которого соединен с выходом .блока- постоянной памяти;- вход которого подключен к пятому выходу арифметического блока, В. устройство введены третья матрица решающих блоков, тре тий элемент ИЛИ причем девятый вы ход блока управл«еййя подклЮчен к пер"" ному управляющему входу каждого решающего блока третьей матрицы, первый информационный вход которого соединен с шестым выходом арифметИческого блока. Выходи всех решак,. их блоков третьей матрицы через третий

60 элемент ИЛИ подключены к седьмому входу арйфметйческого блока. Второй информационный вход каждого решающего блока третьей матрицы подключен к соответствующему выходу из первой группы выходов второго программного блока. Третий информационный вход подключен к соответствующему выходу из второй группы выходов второго программного блока. Второй управляющий вход каждого решающего блока третьей матрицы подключен к десятоМу выходу блока управления.

Блок-схема устройства представлена на чертеже.

ЦиФровое устройство дпя решения системы лин ейных уран не ний с разреженной матрицей содержит матрицу 1 решающих блоков, матрицу 2 реиающих . блоков, матрицу 3 решающих блоков, арифметический блок 4, блок 5 управления; блок 6 индикации, программные блоки 7 и 8, блок 9 постоянной памяти, блок 10 оперативной памяти, блок, 11 сравнения, блок 12 ввода коэффициентов, элементы ИЛИ 13-15, каждая матрица 1 состоит из 10 1 решающих блоков 16.

Устройство работает, следующим обра з ом.

С помощью блока 12 ввода коэффициентов набираются построчно коэффициент за коэффициентом матрицы Н„.

Набор этих коэффициентов производится, например, на цифровой клавиатуре, которая имеет клавиии строк и столбцов. По сигналам, поступающим с блока 12 программный блок 7 вырабатывает сигналы У„и 2, поступающие на входы решающего блока 16 матрицы

Н .,Таким образом, произоиел выбор ячейки С„„, куда заносится преобразованный на арифметическом блоке 4 коэффицйент h При наборе коэффициента 1 .н зайускается блок 5 управления, который работает по микропрограмме преобразования коэффициентов матрицы по методу разложенйя матрицы на треугольные множители с записью этих коэффициентов в виде таблицы множителей в матрицу 1, коэффициент

h „„поступает в арифметический блок

4, преобразуется и поступает в ячейку С+ решающего блока 16 матрицы 1.

Туда же поступает микрокоманда с блока 4. управления, При совпадении сигналов У„ 2 и микрокоманды происходит запись элемента h„< в соответствующем решающем блоке 16. Ввод последующих коэффициентов подматрицы Н„ осуществляется аналогично выше опйсанному, только программный блок 7 вырабатывает соответствующие координатные сигналы У„ и 2.1., которые выбирают соответствукиие решающие блоки 16 С„; матрицы 1, Для определения обработки коэффициентов h s строке матрицы Н служит блок 11 сравнения. Он сраннй714409 вает содержимое счетчиков строк и столбцов первого программного блока

6. Когда эти счетчики равны, идет обработка диагональных элементов матрици Н . Если счетчик строк меньще счетчика столбцов, то ведется обработка коэффициентов выше главной диагонали матрици, если счетчик стрбк больше счетчика столбцов, то ведется обработка коэффициентов, расположенных ниже главной диагонали матрицы. Результаты сравнения с блока 11 сравнения передаются в блок 5 управления, который вырабатывает определенные микрокоманди, необходим2е для арифметическоro блока 4, который ведет обработку коэффициентов. ГлоК 4 вйполняет операции сложения, вычитания, умножения, деления, накопления и алгебраического сложения, которые обеспечивают весь вичислительный процейс. Микропрограммы, выполняющие эти операции, могут быть зашиты .в матрицах мйкропрограмм и микроко манд. Эти микропрограммы служат как микроподпрбграммы для осНоВННх микропрограмм решения системы линейных уравнений. После ввода всех коэ»»2фициентов матрицы Н» на блоке 12 на жимается, например, клавиша И. По этой команде запускается блок 5 управления, который работает по микропрограмме обращения матрицы Н„ в обратную матрицу Н„, Для рбращения матрицы используется метод прямых решений с использованием разложения на треугольние множители, Этот метод быстродействующий и по аппаратурным затратам экономичный. ОбраШЕние матрицы Н» заключается в том, что из полученной матрицы коэффициентов мат 20

ЗО рицы 1 выбирается треугольная матрица, которая п0элементно переписывается в матрицу 2 решающих блоков через элемент ИЛИ 13 и арифметический блок 4. При этом блок 5 управления работает по микропрограмме перезаписи матрицы, вырабатывая определенные 45 микрокоманди для выборки коэффициентов иэ решающих блоков 16 матрицы 1 и пересылки их в решающие блоки 16 матрицы 2, устанавливая при этом счетчики строк и столбцов программных 50 блоков 7 и 8 в соответствующие состояния. Далее производится матричйая операция умножения матрицы 2 на матричные треугольные множители матри. цы 1. Результирующая матрица накап- 55 ливается в матрице 2. Умножение матриц производится традиционным способом;строка одной матрицы умножается на столбец другой матрицы. При умножении матриц коэф»»2ициенты вызываются в арифметический блок 4 через элемент ИЛИ 13 и элемент ИЛИ 14 и происходит их умножение с алгебраическим накоплением. Обратная Матри-, ца Н» накапливается в матрице 2 решающйх блоков. При обращении матри-, цы Н„ программные блоки 7 и 8 работают по программе, вырабатывая соответ-ствующие сигналы Ъ;; „ и Y. Z . Да1 1 лее на блоке 12 нажимается клавиша

Н, что означает, что в матрицу 1 решающих блоков вводятся коэффициенты верхней подматрипи Н„ . Ввоц коэф»»2ициентов осуществляется описанным выше способом, когда осуществляется ввод подматрици Н„ „ Нажимается клавиша умножить, и происходит операция матричного умножения Н » на

Н, Матричное произведение Н Н

«» -»

1 1

= A» хранится в матрице l. Нажатием клавиши 0 осуществляется ввод я

» части известного вектора, которая соответствует части матрицы Н, Ввод

»

Ц„поэлементно осуществляется в блок

10 оперативной памяти, по микрокоманде с блока 5 управления. После этого нажимается клавиша умножить и происходит матричное умножение матрицы 1 на известный вектор О». Получа-ется произведение Н» Н„ (2 в виде вектора размерностью О . Получен» ный вектор Н„Н„Q» для йакопления

» засылается в блок 9 постоянной памяти, где. накапливается вектор О . Нас жатием клавиши»»2 запускается блок 5 управления и происходит занесение коэффициентов подматрицы Ф„в матрицу

2 решающих блоков через арифметический блок 4 с блока 12. Занесение коэффициентов происходит вышеописанным способом. После этого нажимается клавиша умножить и происходит опера " ция матричного умножения матрицы 4 на матрицу 2. Полученное матричное произведение Ф». A = H . Н ф» хранит-1. а . ся в матрице 1. Подматрица .связи Nс— единичная матрица при включении устройства находится в дополнительной матрице 3 решаю(их блоков. Далее осуществляется матричная операция сложения 2» - Н Н„ф»= К „. Результат

-» операции величина К накапливается в матрице 3. Вызов коэффициентов маттрицы 3 решающих блоков на арифметический блок 4 осуществляется по микрокомандам с блока 5 управления, поступающим на управляющие входы решающих блоков 16 матрицы 3 через элемент

ИЛИ 15 при выработке соответствующих сигналов Y u Z программным блоком

1 1

8. Пересылка коэф»»2ипиентов в матрицу 3 с арифметического блока 4 осуществляется по микрокоманде, поступающей с блока 5 управления на вход соответствующего решающего блока 16 матрицы 3. Далее осуществляется ввод второй части исходной-матрицы Н, т.е. осуществляется последовательный ввод подматриц Н, Н, О„, ф и проделываются все матрйчние операции с этими подматрицами описанным выше способом. Последовательность нажатий клавиш остается без изменения. После выполнения всех рассмотренных вьл»»е операций в блоке 9 постоянной памяти на714409 ° копится выражение Н„Н,,< О„+ H H-

Qg = Qgqg а в матрице 3 накопится результат Ж - Н„Н„" @„+ Н н„ ф =

К „ . Осуществляя ввод последующих частей исходной матрицы H rio подматрйцам Н;, Н„., Q ф„ до последней части Н,„, Н,„, 0„„ ф,„ где N 12 и осуществив все матричные операции описанньпч выше спбсобом; получим окойчательные результаты Q = Н„Н,Q„+

+ H H< Q< g

Ос накапливается в блоке 9, à y "= .- Wc (Н„Н„1e„+ Н, Н,"Ф,+ ... +

+ Нн Н „ Ф„)=йс - .(Н„. Н.;" „-), накапливается .в матрице" 3.

Для нахождейия неизвестного векто ра связи Х нажимается клавйша Х,. .

По команде с блока 11 ввода запускается блок 5 управления, которйй вырабатывает микрокоманды перезаписи К г. .из матрицы 3 в матрицу 1 решающих бло-. ков, чтобы выйти на микроподпрограм- @ му обращения матрицы, т. е. К обраща ется в К-< . Для обращения использУется метод прямых решений с использованием разложения матрицы на треуголь- ные множителн. Обращение идет выше- 2$ описанным способом, когда находилась обратная матрица Н„. Далее происходит 1 матричная операция умножения К Q

-1 с

Х . Для этого поэлементно на арифмЕтйческий блок 4 вызывается Q из блока 9 постоянной памяти и К-" иэ матрицы 1 решающих блоков через элемеит

ИЛИ 13. Результат вектора х накапли, вается в блоке 9. После нахождения вектора Х неизвестнь1й вектор Х находится по частям. Нажимается, например, клавиша Ф, по которой запускается блок 5 управления и происходит занесение коэффициентов подматрицы ф„ в матрицу 2 решающих блоков через арифметический блок 4 с блока 12. За- 40 несейие коэффициентов происходит аналогично вышеопиаанному. По нажатию клавйши множить происходит матричная операция умйожения ф„Х на арифметическом блоке 4 с вызовом поэлементно Ф„ и х из матрицы 2 и блока

9. Результат йакаплнвается в блоке 9.

При нажатии клавиши О осуществляем ввод 0 — часть известного вектора в .блок 10 оперативной памяти. После 50 ввода происходит вычитание 0 — ф Х =

1 С

= Q,, Вычитание происходит в арифметическом блоке 4 с вызовом элементов вектора йз блока 10 и вектора ф„Х

:из блока 9. Результат вычитания засы- у лается в блок 9 постоянной памяти.

Далее осуществляется ввод подматрицы

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

1 на блок 9 постоянной памяти. Блок

5 уйравления работает по микропрограмме умножения. На арифметическом блоке ч- выполняется выражение Н„" Q = Х

Результат вектора х записывается в блок 9, Численное значение найденного вектора Х передается в блок б индикаций.Осуществляется ввод последующих частей матрицы Н по подматрицам ф, Я„ и Н„ до последней части ф, Qz и Н и после произведения всех матричных операций и вычислений описанным выше способом, получаются все численные значения вектора

1 В х у х2 хк х 2хз

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

Решение системы линейных уравне-, ний по частям значительно сокращает аппаратурные затраты. Предложенное устройство дает воэможность решить практически любую большую систему линейных уравнений с разряженной матрицей в малом аПпаратурном объеме. Исходную матрицу Н можно разбить на лю-. бое число подматриц Н, Н,..., Н, и порядок подматриц можно взять про- извольным. В устройстве максимальный порядок подматриц равен 10, т. е, все матрицы 1, 2 и дополнительная матрица имеют размерность 10 х 10 решающих блоков. Устройство в этом объеме обеспечивает решение любой большой системы .линейных уравнений высокого порядка с разреженной матрицей.

Суммарный аппаратурный экономичес-.. кий эффект составляет 28480 руб. Кроме того, сокращаются различные материалы, цеховые и Заводские расходы.

Значительно сокращаются монтажные работы.

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

Цифровое устройство для решения системы линейных уравнений, содержащее первую и вторую матрицы решающих блоков, арифметический блок, блок управления, блок индикации, первый и второй программные блоки, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициентов, элементы ИЛИ, причем первый выход арифметнческого блока соединен с первым входом блока индикации, первый вход блока управления соединен со вторым выходом арифметичес кого блока, первый вход которого под ключен к первому выходу блока управления, второй и третий выходы которого соединены соответственно с первыми управляющими входами каждого реша ющего блока первой и второй матриц

I четвертый и пять|й выходы блока управления соединены соответственно со вторыми управляющими входами каждого714409

10 решающего блока первой и второй матриц, третий и четвертый выходы арифметического блока подключен соотвегст- венно к первым информационннм входам каждого решающего блока первой и второй матриц, второй и третий входы 5 арифметического блока соединены соответственноно через первый и второй элементы ИЛИ с выходами решающих блоков первой и второй матриц, шестой выход блока управления соедийен с первЮ4" и 1О вторым входами первого программного блока, первый и второй выходы которого подключен ко второму и третьему входу блока индикации, второй информационный вход каждого решающего блока первой матрицы подключен к соответствукщему вйходу из первой группы выходов второго программного блока, третий информационный вход каждого решающего блока первой матрицЫ подключен к соответствующему выходу 20 из второй группы выходов второго программного блока, первый и второй выходы которого соединены соответственяо с первым и вторым входами блока сравнения, выход блока сравнения под- 25 ключен к третему входу блока упраВления, седьмой выход которого подключен к первому и второму входам вторбго программного блока, четвертый входарифметического блока соединен с пер- 3Q вым выходом блока ввода коэффициентов второй выход которого подключен к второму входу блока управления, третий выход блока ввода коэффициентов соединен с первым входом блока оперативной памяти, четвертый выход подключен к третьему и четвертому входам первогО программного блока, пятый выход подклю- чен к третьему и четвертому входам второго программного блока, восьмой выход .блока управления соединен со вторым входбм блока оперативной памяти, выход которого подключен к пятому входу арифметического блока, шестой вход которого соединен с выходом"" блока постоянной памяти, вход которого подключен к пятому выходу арифметического блока, о т л и ч а юще е с я тем, что, с целью тпрсщенйя устройства, оно содержит третью матрицу решающих блоков, третий элемент ИЛИ, причем девятый выХод блока управления подключен к первому управляющему входу каждого решающего блока третьей матрицы, первый информационный вход которого со-единен с шестым выходом арифметического блока, выходы всех решающих блоков третьей матрицы через третий элемент ИЛИ подключены к седьмоу входу арифметического блока, второй информационный вход каждого решающего блока третьей матрицы подключен к соответствующему выходу иэ первой группы выходов второго программного блока, третий информационный вход подключен к соответствующему выходу из второй группы выходов второго программного блока, второй управляющий вход каждого решающего блока третьей матрицы подключен к десятому выходу блока управления, Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 404090, М.Кл. G 06 Р 15/32, 1973.

2. Заявка Р 2337295, 1976,по которой принято решение о выдаче авторского свидетельства (прототип) . 714409

Составитель H. Палеева

Редактор A. Винограцов ТехредН.Ковалева Корректор Ю.Макаренко

Закааэ 9290/47,. Тираж.751 Подписное

ЦНИИПИ Государственного нове тета СССР по делам иэобретений н открытий

113035, Иосква, ) -35, Раушская наб., д. 4/5

Филиал ППП Патент, "., ужгород, ул . Проектна., 4