Устройство для решения линейных систем алгебраических уравнений Советский патент 1987 года по МПК G06F7/34 G06J1/02 

И:юбретение относится к аналого-цифровой технике и предназначено для решения систем линейных и алгебраических уравнений с нроизвольными невырожденными мат- 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 настроены на вывод данных, причем выходы портов А и В образуют шестнадцатиразрядную магистраль данных, шесть разрядов порта С (СО-С5) объединены в магистраль адреса, а остальмые разряды порта С (С6 и С7) являются магистралью уп- |)аи;1ения.

Порты А 11 F3 УВВ 28 настроеШ) ил прием данных (порт С не используется) и ;ix выво- д|)1 подк.чючены к выходам апалосо-цнфро- вого преобразовате.мя 5.

Б/10К 3 формирования производной цгграф- ной (туикции уст|)()йства реализован в виде N 1 ходового сумматора, выход ко opoi o

5

5

0

0

0

5

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

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

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

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

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

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

д ах/

0,

-У

ХЛ

к

е;/

В/.А,7

I.-,

,.ХПД .уК

t,jD, --rt,(.j

где |j,/ - сумма квадратов невязок;

к-е значение j-й переменной;

невязка на к-й итерации;

свободные )l и коэффициенты

при неизвестных;

номер строки матрицы А;

номер столбца матрицы А;

номер итерации. Для нахождения ми1гпмума ц, в устройстве изменение переменши (но ко гг)рой производится поиск мииимv i;ll ое 11ич твляется

J к

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

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

N - количество уравнений в системе; Е - точность вычислений вектора неизвестных;

А;у - матрица коэффициентов; В; - столбец свободных членов; х° - начальное приближение вектора

неизвестных. Каждое из этих значений (число) обрасимальный из коэффициентов А// -и С, для данного j и определяется коэффициент К:

К 2VM,

где М - максимальный из коэффициентов А,-,- и С,-.

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

Q УВВ 27 в порт А и В, а в порт С этого устройства (разряды СО-С5) выводится адрес управляемого элемента, который формируется в виде D i-1 для первых кодоуправ- ляемых узлов 8 и в виде D N+ i-1. для вторых кодоуправляемых узлов 9. Содержи20

батывается стандартной подпрограммой 1 15 мое портов А, В и С УВВ 27 выдается на ма- (фиг. 15), которая позволяет осушествлять гистрали адреса, данных и управления. Затем программно изменяется содержимое седьмого разряда (С5) порта С УВВ 27 (формируется тактовый импульс по магистрали управления). Тактовый импульс поступает на один вход элементов И 13 и 14, а на другой вход этих элементов поступает разрешение с дешифраторов адреса. Таким образом, тактовый импульс поступает на тактовый вход того кодоуправляемого узла, адрес ко- 25 торого поступает по магистрали адреса и производит запись информации, поступаюшей по магистрали данных в буферный регистр требуемого кодоуправляемого узла.

Таким образом, значения всех модели- руюших коэффициентов поочередно задаввод чисел в десятичной системе счисления. После ввода каждого числа осушест- вляется его перевод в число с плаваюшей точкой. Основной программой число записывается в узел 21 памяти. Последовательность ввода чисел определена алгоритмом, так как в дальнейшем ключом для каждого числа является его адрес. Так, например, коэффициенты А,-/ при неизвестных находятся в следуюших адресах узла 21:

А„ A(i-l)N+j-l Z,

выбранный начальный адрес узла

21 памяти;

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

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

где А

1 -

Z - количество байт, необходимых для 30 ются в кодоуправляемые узлы блока 1, призаписи числа с плаваюшей точкой.

После массива А,у располагается массив Bj, начальный адрес В которого равен:

(N -1)N+N- +1. Аналогично вводится массив чисел х°у.

чем величины А,, задаются на все N первых кодоуправляемых узлов 8, а величины С задаются на все N вторых кодоуправляемых узлов 9.

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

Таким образом, для проведения вычисле- 35 минимума штрафной функции по j-перемен- ний с данными, находяшимися в узле 21ной. Напряжения, моделирующие невязки

,/, из блока i поступают на входы блока 3 через квадратор 2, т.е. напряжения, соответствующие невязкам е/,, возводятся в квадрат, ,,. суммируются и дифференцируются. Напря- жение, соответствч-юшее производной CVMпамяти, процессор 15 по заданным i и j вычисляет адрес, где находится необходимое число, и производит его считывание. Аналогично после проведения арифметических действий над данными вычисляются адреса, по которым производится их запись в узел 21. 2-й шаг (фиг. 7). Производится вычисление значения моделирующего коэффициента С, для отыскания первого приближения по первому неизвестному

С/ В, - 2, А;ух;

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

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

Массив коэффициента С записывается после массива х /.

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

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

и ,

и/

где |i/ - напряжение, соответствующее сумме квадратов невязок с ,,; tu, - мапшнное время (время, моделирующее переменную) U4 симальный из коэффициентов А// -и С, для данного j и определяется коэффициент К:

К 2VM,

где М - максимальный из коэффициентов А,-,- и С,-.

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

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

20

15 25

ются в кодоуправляемые узлы блока 1, причем величины А,, задаются на все N первых кодоуправляемых узлов 8, а величины С задаются на все N вторых кодоуправляемых узлов 9.

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

,/, из блока i поступают на входы блока 3 через квадратор 2, т.е. напряжения, соответствующие невязкам е/,, возводятся в квадрат, суммируются и дифференцируются. Напря- жение, соответствч-юшее производной CVMпроизводноймы квадратов невязок (производная штрафной функции), поступает в аналоговый блок 4 вычисления минимума штрафной функции. Выходное напряжение блока 4 поступает на аналоговый вход блока 1 и на вход аналого- цифрового преобразователя 5. Блок 4 находит значение напряжения (которое соответствует величине искомой переменной), при котором штрафная функция минимальна.

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

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

и ,

и/

где |i/ - напряжение, соответствующее сумме квадратов невязок с ,,; tu, - мапшнное время (время, моделирующее переменную) U4 - масштабный коэффициент.

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

и

, 0-,

где Ку - коэффициент усиления дифференциального усилителя.

Интегратор преобразует сигнал с выхода дифференциального усилителя в соответствии с уравнением (при t jiy/dt ; ):

iMJ

ивых.блока UBwxdtny ,

где А -pW---4 -j7-выбранные параметры схемы.

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

AV

Jw k

:Xj

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

6-й шаг (фиг. 11). Производится считывание полученного в аналоговых блоках первого приближения j-ro неизвестного xj. Цет- ральный процессор 15 в соответствии с алгоритмом формирует тактовый импульс запуска аналого-цифрового преобразователя 5. Для этого программно изменяется содержимое восьмого разряда (С7) порта С УВВ 27. По окончании преобразования аналогового сигнала в аналого-цифровом преобразователе 5 производится считывание информации через порты А и В УВВ 28. Для исключения случайных помех данный цикл можно производить несколько раз, а затем усреднять полученные значения, причем максимальное и минимальное значения при усреднении не учитываются.

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

С,- С,-Ь А;;Х°- А,.

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

j }-1NJ

О/ D/ /( | Ху JLi /(fX(. , е( .

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

вание и вывод значений коэффициентов и т.д.) для следуюшего неизвестного, т.е. опять выполняется вычислительный процесс, начиная с третьего шага.

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

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

0lx/-x;| в

Если данное неравенство не выполняется хотя бы для одного неизвестного, то значениям х/ присваиваются значения х с до j N, т.е. вычислительный процесс выполняется с третьего шага (при этом, на 5 8-м ш аге также вычисляютс-я новые значения коэффициентов С/).

Если неравенство | х/- х° Е выполняется для всех неизвестных, то производится вывод полученного решения, т.е. выполняется 9-й шаг.

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

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

Устройство для решения систем линейных

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

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

5 быстродействия устройства, в него введены аналоговый блок вычисления минимума штрафной функции и группа из Л/ квадраторов, где - N порядок системы линейных алгебраических уравнений, t-й выход (г 1,... N) блока вычисления невязок подключен к

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

невязок подключен к первым входам N элементов и первой группы блока вычисления невязок и к первым входам N элементов И второй группы блока вычисления невязок, выход г -го дешифратора первой группы (г l,...,N) блока вычисления невязок подключен к второму входу г -го элемента И первой группы блока вычисления невязок, выход г-го дешифратора второй группы блока вычисления невязок подключен к втопервой группы блока, вычисления невязок, Ю рому входу /-го элемента И второй груп- аналоговые входы Л кодоуправляемых уз- пы блока вычисления невязок, выход г-го лов второй группы блока вычисления не- элемента И первой группы блока вычисле- вязок подключены к аналоговому входу бло- ния невязок подключен к тактовому вхо- ка вычисления невязок, первый информа- ду г-го кодоуправляемого узла первой груп- ционный цифровой вход блока вычисления пы блока вычисления невязок, выход /-го эле невязок подключен к цифровым входам Л 15 мента И второй группы блока вычисления кодоуправляемых узлов первой группы бло- невязок подключен к тактовому входу /-го ка вычисления невязок и к цифровым входам N кодоуправляемых узлов второй группы блока вычисления невязок, второй информационный цифровой вход блока вычисления невязок подключен к входам N дешифраторов первой группы блока вычисления невязок и к входам N дешифраторов второй группы блока вычисления невязок, управ20

ляюший цифровой вход блока вычисления

кодоуправляемого узла второй группы блока вычисления невязок, выходы Л кодоуправляемых узлов первой и второй групп блока вычисления невязок подключены соответственно к первому и второму аналоговым входам /-ГО сумматора блока вычисления невязок, выход/-ГО сумматора блока вычисления невязок подключен к /-му выходу блока вычисления невязок.

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

кодоуправляемого узла второй группы блока вычисления невязок, выходы Л кодоуправляемых узлов первой и второй групп блока вычисления невязок подключены соответственно к первому и второму аналоговым входам /-ГО сумматора блока вычисления невязок, выход/-ГО сумматора блока вычисления невязок подключен к /-му выходу блока вычисления невязок.

Bxohi данных

(Ь

МТ)

fPu.2.2

ирреса управлени. j

.2.2

126

Риг.З

Фиг.

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

J iuaz

Вдод данных.: N, Е, Ац, Bi ,Х/

2 шаг

Вычисление козфсриииента Ci

3 шаг.

Поиск максимального коэср- сриииента

Ч шаг

вывод нормирован, данных адресов управ ляемык злемен- тов тактовых ампумсоё

5 шаг,

Аналоговое бычасление min штрафной функции

6 шаг

7 шаг

8 шаг

9 шаг

Фиг

-,

BtiBod ад-1 реса в / Inopm С I I JfSS I

lf opMupoSaHue I imaKmofoto ин-1 пьса в разтакгпабога им-1 пульса в раз- I ряде С6

fui.9

J

JpnupoeaHuel ктобого UH-I tea 0 роз-1 tC7 I

.

Считать из I Inopmof A, В I ШВвг вычислен мое значение XI

Фиг.Ю

Фиг. 7J

Перевод числа, fj из числа с плавающей точкой в vuc/a аесятичной системы счисления

Вывод числа I JHa индикатоа

f пт

подпро рама да чисел

1

BBod числа с wBuami/pou 6 JO-u системе счисления

Перевод в чис- ло с плабанз- щей точкой

С Воз6ра/п

Ридлктор В. Петраш Заказ 31 1(); 44

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

1 13035, Москва. Ж--35. Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Ш

Фиг. 75

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

Техред И. ВересКорректор И. Муска

Тираж 672Подписное