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

 

Изобретение относится к аналого-цифровой вычислительной технике и предназначено для решения систем линейных алгебраических уравнений. Целью изобретения TV мл мл мс является повышение быстродействия устройства . Поставленная цель достигается тем, что устройство содержит блок 1 вычисления невязок, группу из N квадраторов 2, где N - порядок системы алгебраических уравнений , блок 3 формирования производной штрафной функции, аналоговый блок 4 вычисления минимума штрафной функции, аналого-цифровой преобразователь 5 и цифровой вычислительной блок 6. Повышение быстродействия обеспечивается возможностью распараллелить вычислительный процесс , применить абсолютно сходящийся метод решения - метод минимизации суммы квадратов невязок, использовать для поиска минимума штрафной функции градиентный метод. 15 ИЛ: TV 00 СП 4:: сг 4

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

ÄÄSUÄÄ1325464 (50 4 G 06 F 7/34, G 06 J 1 02

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Ip.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ .." „ /

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ,1-„-,.„

Фиг,1 (21) 3975659/24-24 (22) 10.11.85 (46) 23.07.87. Бюл. № 27 (71) Казахский государственный университет и Алма-Атинский завод тяжелого машиностроения им. 60-летия СССР (72) А. А. Кучма, М. Г. Литвиненко, А. Т. Лукьянов, А. Т. Любушкин и В. П. Соломин (53) 681.32 (088.8) (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к аналого-цифровой вычислительной технике и предназначено для решения систем линейных алгебраических уравнений. Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит блок 1 вычисления невязок, группу из N квадраторов 2, где

N — порядок системы алгебраических уравнений, блок 3 формирования производной штрафной функции, аналоговый блок 4 вычисления минимума штрафной функции, аналого-цифровой преобразователь 5 и цифровой вычислительной блок 6. Повышение быстродействия обеспечивается возможностью распараллелить вычислительный процесс, применить абсолютно сходящийся метод решения — метод минимизации суммы квадратов невязок, использовать для поиска минимума штрафной функции градиентный метод. 15 ил:

1325464

1

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

Цель изобретения — увеличение быстродействия устройства.

На фиг. 1 представлена функциональная схема устройства; на фиг. 2 — схема блока вычисления невязок; на фиг. 3 и 4 —— схема цифрового вычислительного блока; на фиг. 5 — алгоритм работы устройства; на фиг. 6 — 15 — алгоритм работы цифрового вычислительного блока.

Устройство содержит блок 1 вычисления невязок, группу из квадраторов 2, блок 3 формирования производной штрафной функции, аналоговый блок 4 вычисления минимума штрафной функции, аналого-цифровой преобразователь 5 и цифровой вычислительный блок 6.

Блок 1 вычисления невязок содержит

N кодоуправляемых узлов 8 и N управляемых узлов 9 первой и второй групп, где N— порядок системы алгебраических уравнений, N сумматоров 10, N дешифраторов 11 и N дешифраторов 12 первой и второй групп, N элементов И 13 и N элементов И 14 первой и второй групп.

В качестве цифрового вычислительного блока используется контроллер «Электроника К1 — 20». Цифровой вычислительный блок 6 состоит из центрального процессора 15, тактового генератора 16, системного контроллера 17, буфера 18 данных, буфера

19 адреса, селектора 20 адреса, узла 21 оперативной памяти, узла 22 постоянной памяти, пульта 23 управления с индикацией, узла 24 ввода-,вывода (УВВ), шины 25 управления, шины 26 пульта управления, узлов

27 и 28 ввода-вывода и шин данных и адреса DO — D7 и АΠ— А15 соответственно.

УВВ 27 и 28 являются соответственно входным и выходным адаптерами цифрового вычислительного блока 6, с помощью которых производится обмен данными между блоком 1 и аналого-цифровым преобразователем 5. Микросхема, применяемая в качестве узла ввода-вывода в контроллере, содержит три восьмиразрядных порта (многофункциональных программируемых буферных регистра) А, В и С. Все порты А, В и С УВВ

27 настроены на вывод данных, причем выходы портов А и В образуют 1нестнадцатиразрядную магистраль данных, шесть разрядов порта С (СО--С5) объединены в магистраль адреса, а Остальные разряды порта С (С6 и С7! являются магистралью упри«пения. ! !Орты А и В УВВ 28 «астро III>l и;i прием да и иы.((норт С ие исиюльз ется1 и:)х выводы иодклк>ч "Hhl к «ь)ходам Bligh, I(>I()-цифро«ОГО lip(Образо«11 1 е. )я О.

Б I(>I. 3 формиро(шиия производной штрафной фуiii.ции устройства рсализо«ан в «иде

М «ходОВОГО сУм)>1атОР)1, выход I((> (>P()I О

2 соединен с входом схемы вычислений производной. Выход схемы вычисления является выходом блока формирования штраф ной функции и ее производной, а его входами являются соответственно входы N-входового сумматора. Схема вычисления производной может бьггь выполнена по известной, схеме дифференциатора на ОУ.

Аналоговый блок 4 вычисления минимума штрафной функции может быть реализован р в виде следящего нуль-органа, т.е. дифференциального усилителя (нуль-органа) и схемы запоминания (схемы выборки-хранения), подключенной к выходу дифференциального усилителя, Схема запоминания может быть выполнена в виде интегратора, который при нулевом входном сигнале сохраняет на своем выходе значение напряжения, запомненного на емкости. Выход схемы запоминания является выходом аналогового блока вычисления минимума штрафной функции, а его

2ц входом служит инвертирующий вход дифференциального усилителя, неинвертирующий вход дифференциального усилителя подключен к шине нулевого потенциала.

Каждый из N квадраторов группы выполнен на микросхеме аналогового перемножителя.

В качестве аналого-цифрового преобразователя обоих устройств используется модуль

Ф 7077 или микросхема К 572ПВ1 с интегрирующей схемой выборки-хранения на входе.

Управляемый узел состоит из кодоуправляемого резистора с буферным регистром, подключенного в обратную связь инвертирующего усилителя, включенного последовательно с усилителем сдвига уровня. В качестве цифрового вычислительного блока используется программируемый контроллер «Электроника К! — 20».

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

45 ей= — — В;--A,;x> где !).; — сумма квадратов невязок; х," †- к-е значение j-й переменной; е;; †- невязка иа к-й итерации;

В;Л;; — свободные члены и коэффициенты ири неизвестных;

1 — номер строки матрицы А; — номер столбца и а три ш>1 А; к — номер итера(и(и.

Q.1ÿ нахождения минимума !(, в устройст«е изменение перемеllii(>Й ill() кот»рой ироИЗ«О IHTCH П()ИСК МИИИ 1> 3 . , ill(c I II:1>I(ÒÑß

1325464

3 с учетом знака и величины производной штрафной функции.

В соответствии с приведенным методом решения и его алгоритмом, рассмотрим пошаговую работу устройства (фиг. 5 — 15) .

1-й шаг. В узел 21 памяти блока 6 с пульта 23 управления через УВВ 24 вводятся необходимые для решения данные:

N — количество уравнений в системе;

E — точность вычислений вектора неизвестных;

А;; — матрица коэффициентов;

В; — столбец свободных членов; х,4 — начальное приближение вектора неизвестных.

Каждое из этих значений (число) обрабатывается стандартной подпрограммой 1 (фиг. 15), которая позволяет осуществлять ввод чисел в десятичной системе счисления. После ввода каждого числа осуществляется его перевод в число с плавающей точкой. Основной программой число записывается в узел 21 памяти. Последовательность ввода чисел определена алгоритмом, так как в дальнейшем ключом для каждого числа является его адрес. Так, например, коэффициенты А;; при неизвестных находятся в следующих адресах узла 21: (А;;) = А((i — 1) N+ j — 11Z, где А — выбранный начальный адрес узла

21 памяти;

i — номер строки;

j — номер столбца;

Z — количество байт, необходимых для записи числа с плавающей точкой.

После массива А;; располагается массив

В;, начальный адрес В которого равен:

В= А+ ((N — 1) N+ N — 11 Z +1.

Аналогично вводится массив чисел х

Таким образом, для проведения вычислений с данными, находящимися в узле 21 памяти, процессор 15 по заданным i u j вычисляет адрес, где находится необходимое число, и производит его считывание. Аналогично после проведения арифметических действий над данными вычисляются адреса, по которым производится их запись в узел 21.

2-й шаг (фиг. 7). Производится вычисление значения моделирующего коэффициента

С; для отыскания первого приближения по первому неизвестному Xi.

С;= В; — Z, А;;х, Массив коэффициента C ; записывается после массива х ;.

3-й шаг (фиг. 8). Производится определение нормировочного коэффициента, необходимого для масштабирования матриц А и

С при проведении поиска минимума суммы квадратов невязок по i-му неизвестному. Проведение нормировки (масштабирования) вызвано ограниченной разрядностью кодоуправляемых узлов 8 и 9. Наибольшее число, которое может быть воспроизведено управляемым узлом, равно 2", где сс — его разрядность (знаковый разряд не учитывается).

Этому числу ставится в соответствие мак55 где p, — напряжение, соответствукпцсе сумме квадратов невязок с„;

1„; — машинное время (время, моделирующее переменную), >pj= кх,;

4 симальный из коэффициентов Aij и С; для данного j и определяется коэффициент К:

К=2 /М, где М вЂ” максимальный из коэффициентов

А;;и С;.

5 4-й шаг (фиг. 9). Вывод данных в блок 1 производится следующим образом. Каждый из коэффициентов А;;, С; домножается на коэффициент К, переводится в число с фиксированной точкой и побайтно выдается в

УВВ 27 в порт А и В, а в порт С этого устройства (разряды СΠ— С5) выводится адрес управпяемого элемента, который формируется в виде D= i — 1 для первых кодоуправляемых узлов 8 и в виде Р= N+ i — 1. для вторых кодоуправляемых узлов 9. Содержи15 мое портов А, В и С УВВ 27 выдается на магистрали адреса, данных и управления. 3атем программно изменяется содержимое седьмого разряда (С5) порта С УВВ 27 (формируется тактовый импульс по магистрали управления). Тактовый импульс поступает на один вход элементов И 13 и 14, а на другой вход этих элементов поступает разрешение с дешифраторов адреса. Таким образом, тактовый импульс поступает на тактовый вход того кодоуправляемого узла, адрес ко25 торого поступает по магистрали адреса и производит запись информации, поступающей по магистрали данных в буферный регистр требуемого кодоуправляемого узла.

Таким образом, значения всех моделирующих коэффициентов поочередно задаЗО ются в кодоуправляемые узлы блока 1, причем величины А;; задаются на все N первых кодоуправляемых узлов 8, а величины С задаются на все Х вторых кодоуllðàBëÿåìûх узлов 9.

5-й шаг (фиг. 10). Производится поиск

35 минимума штрафной функции по j-переменной. Напряжения, моделирующие невязки е;;, из блока 1 поступают на входы блока 3 через квадратор 2, т.е. напряжения, соответствующие невязкам е;;, возводятся в квадрат, 4О суммируются и дифференцируются. Напряжение, соответствующее производной суммы квадратов невязок (производная штрафной функции), поступает в аналоговый блок

4 вычисления минимума штрафной функции.

Выходное напряжение блока 4 поступает на

45 аналоговый вход блока 1 и на вход аналогоцифрового преобразователя 5. Блок 4 находит значение напряжения (которое соответствует величине искомой переменной), при котором штрафная функция минимальна.

С выхода блока 3 на вход аналогового

5р блока 4 вычисления минимума штрафной функции поступает величина

11 д1„

13254б4

К вЂ” масштабный коэффициент.

Блок 4 состоит из дифференциального усилителя и интегратора. На выходе дифференциального усилителя этого блока получается

11вых= ку (О— где к„— коэффициент усиления дифференциального усилителя.

Интегратор преобразует сигнал с выхода дифференциального усил ителя в соответствии с уравнением (при др,/д1„,- О): хвы

Usex.блока 4 — — — (U> ! о где А= ф — = — выбранные парамет- 15

КС dt К ры схемы.

Таким образом, на выходе блока 4 вычисления минимума штрафной функции имеем напряжение, равное величине искомой неизвестной: хло

U.оодока4 = Аьа ) = = х1 и

Во время нахождения минимума штрафной функции по j-му неизвестному аналоговыми блоками предлагаемого устройства Ilpoцессор находится в режиме ожидания.

6-й шаг (фиг. 11) . Производится считывание полученного в аналоговых блоках первого приближения j-го неизвестного xj. Цетральный процессор 15 в соответствии с алгоритмом формирует тактовый импульс запуска аналого-цифрового преобразователя 5.

Для этого программно изменяется содержимое восьмого разряда (С7) порта С УВВ 27.

По окончании преобразования аналогового сигнала в аналого-цифровом преобразователе 5 производится считывание информации через порты А и В УВВ 28. Для исключения случайных помех данный цикл можно производить несколько раз, а затем усреднять полученные значения, причем максимальное и минимальное значения при усреднении не 4О учитываются.

7.-й шаг (фиг. 12). Центральный процессор 15 в соответствии с программой производит сравнение номера переменной с числом уравнений. Если j(N, вычисляются ко- 45 эфф ициенты

C;= С+ А;;х; — А;;х ь

Таким образом, при вычислении минимума штрафной функции для j-го неизвестного используется новое приближение всех j — 1 неизвестных и старое приближение осталь- 5О ных j+ 1 неизвестных, т.е. С; равно

3=3M, и

S;= В; — Х A;jx,— Х Аух, .

Фв! .11+!

Вычисленные коэффициенты С, записываются в те же ячейки памяти, где находились С; для нахождения предыдущего пере- 55 менного. Затем осуществляется процесс нахождения минимума штрафной функции (поиск минимального коэффициента, нормирование и вывод значений коэффициентов и т.д.) для следующего неизвестного, т.е. опять выполняется вычислительный процесс, начиная с третьего шага.

Если j= N, то выполняется следующий шаг.

8-й шаг (фиг. 13) . Производится сравнение нового приближения для всех неизвестных со старым приближением, т.е. проверяется выполнение условия х ; — х ) (Е

Если данное неравенство не выполняется хотя бы для одного неизвестного, то значениям xj присваиваются значения х; с

j = 1 до j =N, т.е. вычислительный процесс выполняется с третьего шага (при этом, на

8-м шаге также вычисляются новые значе. ния коэффициентов C;) .

Если неравенство ) х, — х; (Е выполняется для всех неизвестных, то производится вывод полученного решения, т.е. выполняется 9-й шаг.

9-й шаг (фиг. 14). Производится вывод полученного решения из массива х;. Для этого данные считываются из узла 21 памяти, переводятся в десятичную систему счисления и выводятся на пульт 23 управления (индикатор). На этом процесс нахождения искомых неизвестных заканчивается.

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

Устройство для решения систем линейных алгебраических уравнений, содержащее блок вычисления невязок, блок формирования производной штрафной функции, аналогоцифровой преобразователь, цифровой вычислительный блок, группа выходов аналогоцифрового преобразователя подключена к группе информационных входов цифрового вычислительного блока. первый и второй выходы цифрового вычислительного блока подключены соответственно к первому и второму цифровому информационным входам блока вычисления невязки, третий выход цифрового вычислительного блока подключен к цифровому управляющему входу блока вычисления невязок и к управляющему входу аналого-цифрового преобразователя отличаюи4ееся тем, что, с целью повышения быстродействия устройства, в него введены аналоговый блок вычисления минимума штрафной функции и группа из N квадраторов, где — N порядок системы линейных алгебраических уравнений, -й выход (1= 1,...

%) блока вычисления невязок подключен к информационному входу i-ro квадратора группы, выход которого подключен к 1-му информационному входу блока формирования производной штрафной функции, выход которого подключен к входу аналогового блока вычисления минимума штрафной функции, выход которого подключен к аналоговому входу блока вычисления невязок и к информационному входу аналого-цифрового преобразователя, при этом блок вычисле1325464

7 ния невязок содержит источник опорного напряжения, первую группу из N дешифраторов, вторую группу из N дешифраторов, первую группу из N элементов И, вторую группу из N элементов И, первую группу из

N кодоуправляемых узлов, вторую группу из N кодоуправляемых узлов, сумматоров, выход источника опорного напряжения блока вычисления невязок подклюен к аналоговым входам N кодоуправляемых узлов первой группы блока. вычисления невязок, аналоговые входы N кодоуправляемых узлов второй группы блока вычисления невязок подключены к аналоговому входу блока вычисления невязок, первый информационный цифровой вход блока вычисления невязок подключен к цифровым входам Л кодоуправляемых узлов первой группы блока вычисления невязок и к цифровым входам

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

8 невязок подключен к первым входам N элементов и первой группы блока вычисления невязок и к первым входам N элементов И второй группы блока вычисления невязок, выход i-го дешифратора первой группы (i= 1,...,N) блока вычисления невязок подключен к второму входу i-го элемента

И первой группы блока вычисления невязок, выход i-го дешифратора второй группы блока вычисления невязок подключен к вто10 рому входу i-го элемента И второй группы блока вычисления невязок, выход -го элемента И первой группы блока вычисления невязок подключен к тактовому входу -го кодоуправляемого узла первой группы блока вычисления невязок, выход -го элемента И второй группы блока вычисления невязок подключен к тактовому входу i-го кодоуправляемого узла второй группы блока вычисления невязок, выходы N кодоуправляемых узлов первой и второй групп блока

20 вычисления невязок подключены соответственно к первому и второму аналоговым входам -го сумматора блока вычисления невязок, выход -ro сумматора блока вычисления невязок подключен к i-му выходу блока вычисления невязок.

1325464 ф.з

1 шаг

2 шаг

5 шаг

5 шаг

7 исаг

В исаг

9 исаг

Фссг 5

1325464

Фиг. б

1325464

Фиг. 10

Фиг.77

Фиг.72

Фиг, Р г. 75

1325464

Составитель В. Смирнов

Редактор В. Петраш Текрсд И. Верес Корректор И. Муска

Заказ 3110/44 Тираж 672 Подписное

ВНИИГ1И Государственно о комитета СССР по делам и обретений и открытий

1 l 3035, Москва. Ж вЂ” -35, Раугиская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4