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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 34,606,11 0 в 4 б САНИЕ ИЗОБРЕТЕНИ ЬСТВ вен ныи уни д тяжелого СССР Г. Литвине шкин РЕШЕНЛГЕБРАИ Еаналогое и пред линейных ю изобрет и ал- ния геб Фиг, 1 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ К АВТОРСКОМУ СВИ(54) УСТРОЙСТВО ДЛСИСТЕМ ЛИНЕЙНЫХСКИХ УРАВНЕНИЙ(57) Изобретение относитсяровой вычислительной технначено для решения системраических уравнений. Цел 1325464 А 1 является повышение быстродеиствия устройства. Поставленная цель достигается тем, что устройство содержит блок 1 вычисления невязок, группу из М квадраторов 2, где И - порядок системы алгебраических уравнений, блок 3 формирования производной штрафной функции, аналоговый блок 4 вычисления минимума штрафной функции, аналого-цифровой преобразователь 5 и цифровой вычислительной блок 6. Повышение быстродействия обеспечивается возможностью распараллелить вычислительный процесс, применить абсолютно сходящийся метод решения - метод минимизации суммы квадратов невязок, использовать для поиска минимума штрафной функции градиентный метод. 15 ил:5055 1Изобретение относится к аналого-цифровой технике и предназначено для решениясистем линейных и алгебраических уравне.ний с произвольными невырожденными матрицами коэффициентов.Цель изобретения - увеличение быстродействия устройства.На фиг. 1 представлена функциональная схема устройства; на фиг. 2 - схемаблока вычисления невязок; на фиг, 3 и 4 --схема цифрового вычислительного блока; нафиг. 5 - алгоритм работы устройства; нафиг, 6 - 15 - алгоритм работы цифровоговычислительного блока,Устройство содержит блок 1 вычисленияневязок, группу из квадраторов 2, блок 3формирования производной штрафной функции, аналоговый блок 4 вычисления минимума штрафной функции, аналого-цифровойпреобразователь 5 и цифровой вычислительный блок 6.Блок 1 вычисления невязок содержитМ кодоуправляемых узлов 8 и Я управляемых узлов 9 первой и второй групп, где Х -порядок системы алгебраических уравнений,М сумматоров 10, М дешифраторов 11 и М дешифраторов 12 первой и второй групп, Х элементов И 13 и Х элементов И 14 первой и второй групп.В качестве цифрового вычислительногоблока используется контроллер Электроника К 1 - 20. Цифровой вычислительныйблок 6 состоит из центрального процессора 15, тактового генератора 16, системногоконтроллера 17, буфера 18 данных, буфера19 адреса, селектора 20 адреса, узла 21 оперативной памяти, узла 22 постоянной памяти, пульта 23 управления с индикацией,узла 24 ввода-,вывода (УВВ), шины 25 управления, шины 26 пульта управления, узлов27 и 28 ввода-вывода и шин данных и адреса РО - Р 7 и АО - А 15 соответственно.УВВ 27 и 28 являются соответственновходным и выходным адаптерами цифровоговычислительного блока 6, с помощью которых производится обмен данными междублоком 1 и аналого-цифровым преобразователем 5. Микросхема, применяемая в качестве узла ввода-вывода в контроллере, содержит три восьмиразрядных порта (многофункциональных программируемых буферных регистра) А, В и С. Все порты А, В и С УВВ27 настроены на вывод данных, причем выходы портов А и В образуют шестнадцатиразрядную магистраль данных, шесть разрядов порта С (СОС 5) сбьединены в магистраль адреса, а Остальные разряды порта С (С 6 и С 7) являются магистралью управления.орты А и В УВВ 28 настроены ии приемлаипых (норт С не ис 1 Осьзуется 1 и:х выводы иолклксчены к ь 1 ходам аиа,нсго-цифроессс 11 с л сс р а 3 с 8 с с 1 с, 1 51 О,Бак 3 формирсшния производной штрафной фукции устройства реализован в виде" Ихолоесого суммат 01 са, выход к: Ор)1 О 2соединен с входом схемы вычислений производной. Выход схемы вычисления является выходом блока формирования штраф ной функции и ее производной, а его входами являются соответственно входы М-входо.вого сумматора. Схема вычисления производной может бьггь выполнена по известной, схеме дифференциатора на ОУ,Аналоговый блок 4 вычисления минимумаштрафной функции может быть реализованО в виде следящего нуль-органа, т.е. дифференциального усилителя (нуль-органа) и схемы запоминания (схемы выборки-хранения),подключенной к выходу дифференциальногоусилителя, Схема запоминания может бытьвыполнена в виде интегратора, который принулевом входном сигнале сохраняет на своемвыхоле значение напряжения, запомненногона емкости. Выход схемы запоминанияявляется выходом аналогового блока вычисления минимума штрафной функции, а его20 входом служит инвертирующий вход дифференциального усилителя, неинвертирующийвход дифференциального усилителя подключен к шине нулевого потенциала.Каждый из М квадраторов группы выполнен на микросхеме аналогового перемножителя.В качестве аналого-цифрового преобразователя обоих устройств используется модульф 7077 или микросхема К 572 ПВ 1 с интегри.рующей схемой выборки-хранения на входе.Управляемый узел состоит из кодоуправляемого резистора с буферным регистром,подключенного в обратную связь инвертируюецего усилителя, включенного последовательно с усилителем слвига уровня. Вкачестве цифрового вычислительногоблока используется программируемый контроллер Электроника К - 20.В устройстве в качестве, штрафной функции используется сумма квадратов невязоки градиентный метод минимизации штрафнойфункции, метод наискорейшего спуска, отно 40 сящийся к итерационным методам вариационного типа, Д,ля нахождения минимумаштрафной функции необходимо и достаточно найти первые производные этой функциипо каждой переменной и приравнять их кнулю:45 В; - -А х;где р; - сумма квадратов невязок;х," в - к-е значение 1-й переменной;есс в - невязка на к-й итерации;В;Л - свободные члены и коэффициентыпри неизвестных;- номер строки матрицы А;- номер столбца сЕстсие 1 А;к - номер итераИи.с 1,.я нахОждЕния минимума с, в устройстве изменение перемс 11:11 (си клсрос ИроИЗ 110,СИТСЯ П)ИС 1( МИ 1 И 1 С,111 ССС 111 С 1 ЕС;1 ЯЕТСЯ3с учетом знака и величины производнойштрафной функции.В соответствии с приведенным методомрешения и его алгоритмом, рассмотрим пошаговую работу устройства (фиг. 5 - 15).1-й шаг. В узел 21 памяти блока 6 с пульта 23 управления через УВВ 24 вводятсянеобходимые для решения данные:1 х 1 - количество уравнений в системе;Е - точность вычислений вектора неизвестных;А - матрица коэффициентов;В; - столбец свободных членов;х,4 - начальное приближение векторанеизвестных.Каждое из этих значений (число) обрабатывается стандартной подпрограммой 1(фиг. 15), которая позволяет осуществлятьввод чисел в десятичной системе счисления. После ввода каждого числа осуществляется его перевод в число с плавающейточкой. Основной программой число записывается в узел 21 памяти. Последовательность ввода чисел определена алгоритмом,так как в дальнейшем ключом для каждого числа является его адрес, Так, напри.мер, коэффициенты А при неизвестных находятся в следующих адресах узла 21:А = А(1 - 1) Х+ ) - 1 Х,где А - выбранный начальный адрес узла21 памяти;1 - номер строки;1 - номер столбца;Х - количество байт, необходимых длязаписи числа с плавающей точкой.После массива А располагается массивВ;, начальный адрес В которого равен:В=А+ (1 х 1 - 1)1 Ч+ Х - 112 +1.Аналогично вводится массив чисел х;.Таким образом, для проведения вычислений с данными, находящимися в узле 21памяти, процессор 15 по заданным 1 и 1 вычисляет адрес, где находится необходимоечисло, и производит его считывание. Аналогично после проведения арифметическихдействий над данными вычисляются адреса,по которым производится их запись в узел 21.2-й шаг (фиг. 7). Производится вычисление значения моделирующего коэффициентаС; для отыскания первого приближения попервому неизвестному Х.С;= В; - Х, Ах,Массив коэффициента С; записывается послемассива х;.3-й шаг (фиг. 8). Производится определение нормировочного коэффициента, необходимого для масштабирования матриц А иС при проведении поиска минимума суммыквадратов цевязок по 1-му неизвестному. Проведение нормировки (масштабирования)вызвано ограниченной разрядностью кодоуправляемых узлов 8 и 9. Наибольшее число, которое может быть воспроизведено управляемым узлом, равно 2", где а - его разрядность (знаковый разряд не учитывается),Этому числу ставится в соответствие мак 55 где ц; - напряжение, соответствукпцсе сумме квадратов цевязок с; 1; - машинное время (время, моделирующее переменную), 1 р= кх,; 4симальный из коэффициентов АЙ и С; дляданного ) и определяется коэффициент К:К= 2/М,где М - максимальный из коэффициентовАи С;.5 4-й шаг (фиг. 9), Вывод данных в блок 1производится следующим образом, Каждыйиз коэффициентов А, С; домножается накоэффициент К, переводится в число с фиксированной точкой и побайтно выдается вУВВ 27 в порт А и В, а в порт С этого устройства (разряды СО - С 5) выводится адресуправпяемого элемента, который формируется в виде Р= 1 - 1 для первых кодоуправляемых узлов 8 и в виде Р= 1 Х 1+ 1 - 1. длявторых кодоуправляемых узлов 9. Содержи 15 мое портов А, В и С УВВ 27 выдается на магистрали адреса, данных и управления. Затем программно изменяется содержимое седьмого разряда (С 5) порта С УВВ 27 (формируется тактовый импульс по магистралиуправления). Тактовый импульс поступаетна один вход элементов И 13 и 14, а на другой вход этих элементов поступает разрешение с дешифраторов адреса. Таким образом,тактовый импульс поступает на тактовыйвход того кодоуправляемого узла, адрес ко 25 торого поступает по магистрали адреса и производит запись информации, поступающей помагистрали данных в буферный регистр требуемого кодоуправляемого узла.Таким образом, значения всех моделирующих коэффициентов поочередно зада 30 ются в кодоуправляемые узлы блока 1, причем величины А задаются на все 1 х 1 первыхкодоуправляемых узлов 8, а величины С задаются на все Х вторых кодоуправляемыхузлов 9,5-й шаг (фиг. 10). Производится поиск35 минимума штрафной функции по )-переменной. Напряжения, моделирующие невязкие, из блока 1 поступают на входы блока 3через квадратор 2, т.е. напряжения, соответствующие невязкам е, возводятся в квадрат,40 суммируются и дифференцируются. Напряжение, соответствующее производной суммы квадратов цевязок (производная штрафной функции), поступает в аналоговый блок4 вычисления минимума штрафной функции.Выходное напряжение блока 4 поступает ца45 аналоговый вход блока 1 и на вход аналогоцифрового преобразователя 5. Блок 4 находит значение напряжения (которое соответствует величине искомой переменной), при котором штрафная функция минимальна.С выхода блока 3 на вход аналогового50 блока 4 вычисления минимума штрафнойфункции поступает величинад 15К - масштабный коэффициент.Блок 4 состоит из дифференциального усилителя и интегратора. На выходе дифференциального усилителя этого блока полу- чается 1 1 вых= ку О -коэффициен циального у тор преобра нциального уравнением диффере де усилениялителя.ет сигналсилителяри др/д 1 Интегдиффествии выхода 1 Осоответ 0) 1.3 вых.б А= ф -- "- = - выбранные парамет МС д 1 Кры схемы. Таким образом, на выходе блока 4 выисления минимума штрафной функции имем напряжение, равное величине искомой еизвестной: Ы1-1 аътА. бдоа 4 = А 81 = = х 1 . Во время нахождения минимума штрафной функции по 1-му неизвестному аналоговыми блоками предлагаемого устройства процессор находится в режиме ожидания.6-й шаг (фиг. 11) . Производится считывание полученного в аналоговых блоках первого приближения )-го неизвестного х). Цетральный процессор 15 в соответствии с алгоритмом формирует тактовый импульс запуска аналого-цифрового преобразователя 5. Для этого программно изменяется содержимое восьмого разряда (С 7) порта С УВВ 27. По окончании преобразования аналогового сигнала в аналого-цифровом преобразователе 5 производится считывание информации через порты А и В УВВ 28. Для исключения случайных помех данный цикл можно производить несколько раз, а затем усреднять полученные значения, причем максимальное и мини альное значения ри усреднении не 4 учитываются.7.-й шаг (фиг. 12). Центральный процессор 15 в соответствии с программой производит сравнение номера переменной с числом уравнений. Если 1( М, вычисляются ко эффициентыС;= С;+ Ах; - Ах ьТаким образом, при вычислении минимума штрафной функции для )-го неизвестного используется новое приближение всех ) - 1 неизвестных и старое приближение осталь 5 ных )+ 1 неизвестных, т.е. С; равно3=31, иЯ;= В; - Х А,х - Х А;,х,.е ,вФВычисленные коэффициенты С, записываются в те же ячейки памяти, где находились С; для нахождения предыдущего пере менного. Затем осуществляется процесс нахождения минимума штрафной функции (поиск минимального коэффициента, нормирование и вывод значений коэффициентов и т.д.) для следующего неизвестного, т.е. опять выполняется вычислительный процесс, начиная с третьего шага,Если 1= М, то выполняется следующий шаг.8-й шаг (фиг. 13), Производится сравнение нового приближения для всех неизвестных со старым приближением, т.е. проверя. ется выполнение условиях; - х ) (Е1" сли данное неравенство не выполняется хотя бы для одного неизвестного, то значениям х 1 присваиваются значения х; с ) =1 до 1=Я, т.е. вычислительный процесс выполняется с третьего шага (при этом, на 8-м шаге также вычисляются новые значе ния коэффициентов С;),Если неравенство ) х, - х( Е выполняется для всех неизвестных, то производится вывод полученного решения, т.е. выполняется 9-й шаг,9-й шаг (фиг. 14). Производится вывод полученного решения из массива х;. Для этого данные считываются из узла 21 памяти, переводятся в десятичную систему счисления и выводятся на пульт 23 управления (индикатор). На этом процесс нахождения искомых неизвестных заканчивается.Формула изобретекиУстройство для решения систем линейных алгебраических уравнений, содержащее блок вычисления невязок, блок формирования производной штрафной функции, аналогоцифровой преобразователь, цифровой вычислительный блок, группа выходов аналогоцифрового преобразователя подключена к группе информационных входов цифрового вычислительного блока. первый и второй выходы цифрового вычислительного блока подключены соответственно к первому и второму цифровому информационным входам блока вычисления невязки, третий выход цифрового вычислительного блока подключен к цифровому управляющему входу блока вычисления невязок и к управляющему входу аналого-цифрового преобразователя отличаюи 1 ееся тем, что, с целью повышения быстродействия устройства, в него введены аналоговый блок вычисления минимума штрафной функции и группа из М квадраторов, где - М порядок системы линейных алгебраических уравнений, -й выход (1= 1, %) блока вычисления невязок подключен к информационному входу -го квадратора группы, выход которого подключен к 1-му информационному входу блока формирования производной штрафной функции, выход которого подключен к входу аналогового блока вычисления минимума штрафной функции, выход которого подключен к аналоговому входу блока вычисления невязок и к информационному входу аналого-цифрового преобразователя, при этом блок вычисле 13254647ния невязок содержит источник опорного напряжения, первую группу из 1 М дешифраторов, вторую группу из Х дешифраторов, первую группу из Х элементов И, вторую группу из М элементов И, первую группу из М кодоуправляемых узлов, вторую группу из М кодоуправляемых узлов, сумматоров, выход источника опорного напряжения блока вычисления невязок подклюен к аналоговым входам У кодоуправляемых узлов первой группы блока, вычисления невязок, аналоговые входы Л/ кодоуправляемых узлов второй группы блока вычисления невязок подключены к аналоговому входу блока вычисления невязок, первый информационный цифровой вход блока вычисления невязок подключен к цифровым входам Л кодоуправляемых узлов первой группы блока вычисления невязок и к цифровым входам М кодоуправляемых узлов второй группы блока вычисления невязок, второй информационный цифровой вход блока вычисления невязок подключен к входам 1 Ч дешифраторов первой группы блока вычисления невязок и к входам Х дешифраторов второй группы блока вычисления невязок, управляющий цифровой вход блока вычисления 8невязок подключен к первым входам Х элементов и первой группы блока вычисления невязок и к первым входам М элементов И второй группы блока вычисления невязок, выход -го дешифратора первой группы (= 11 Ч) блока вычисления невязок подключен к второму входу -го элемента И первой группы блока вычисления невязок, выход -го дешифратора второй группы блока вычисления невязок подключен к вто рому входу -го элемента И второй группы блока вычисления невязок, выход -го элемента И первой группы блока вычисления невязок подключен к тактовому входу -го кодоуправляемого узла первой группы блока вычисления невязок, выход -го эле мента И второй группы блока вычисленияневязок подключен к тактовому входу -го кодоуправляемого узла второй группы блока вычисления невязок, выходы У кодоуправляемых узлов первой и второй групп блока 20 вычисления невязок подключены соответственно к первому и второму аналоговым входам -го сумматора блока вычисления невязок, выход -го сумматора блока вычисления невязок подключен к -му выходу блока вычисления невязок.Составитель В. СмирновРедактор В. Петраш Текред И. Верее Корректор И. МускаЗаказ 31 1044 Тираж 6 Т 2 ПодписноеВНИИГ 1 И Государственноо комитега СССР по делам изобретений и открытий113035, Москва. Ж - -35, Раугиская наб., д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4