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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к цифровой вычислительной технике и может быть использовано для быстрого решения систем линейных алгебраических уравнений . Цель изобретения - повьшение производительности устройства. Устройство содержит матрицу пхп умножителей , п регистров, п сумматоров, п блоков приоритетного формирования нулей и элементов задержки, п элементов сравнения, элемент И, элемент ИЛИ, элемент НЕ, два одновибратора. Увеличение производительности устройства обеспечивается в результате уменьшения интервала времени между двумя последовательными записями приближений в регистр за счет определения моментов окончания формирова- 1НИЯ результатов. 2 ил. i (Л tc СП 4 сл

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

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

РЕСПУБЛИК (51) 4 G 06 F 15/324

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К д ВТОРСНОМУ СВИДЕТЕЛЬСТВУ 1 С!

: 2

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3830248/24-24 (22) 25.12.84 (46) 30.08.86. Бюл. У 32 (71) Институт проблем моделирования в энергетике АН УССР (72) В.Н. Белецкий, М.Н. Кулик, А.А. Чемерис, Г.П. Карась, A.Ï. Павлусенко и С.Ф. Семенов (53) 681.32(088.8) (56) Пухов Г.Е. Структурно-аналоговые цифровые вычислительные системы.

Электроника и моделирование. Киев:

Наукова думка, 1975, вып.7, с.50.

Алексеенко А.Г., Шагурин И.И. Микросхемотехника. М.: Радио и связь, 1982, с.416.

Карцев M.À, Брик В.А. Вычислительные системы и синхронная арифметика, М.: Радио и связь, 1981, с.316.

„„SU» 1254504 А1 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

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

ИЛИ, элемент НЕ, два одновибратора.

Увеличение производительности устройства обеспечивается в:результате уменьшения интервала времени между двумя последовательными записями приближений в регистр за счет определения моментов окончания формирования результатов. 2 ил.

1254504

inax (! b„ l)

<Х хоx; 1= 1 гх

t1 т {à,;", L i х, i} х1 J i имеем

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

Цель изобретения — повышение производительности устройства., На фиг.1 представлена блок-схема устройства для решения СЛАУ порядка два; на фиг." — схема одного разряда блока приоритетного формирования нулеи.

Устройство содержит первый и второй регистры 1.1 и 1.2, умножители

2.1.1, 2.1.2, 2.2. I 2.2.2 матрицы умножителей, первый и второй сумматоры 3.1 и 3.2, первый и второй блоки 4.1 и 4.2 приоритетного формирования нулей, первый и второй элементы 5.1 и 5.2 задержки, первый и Второй элементы 6.1 и 6.2 сравнения, элемент ИЛИ 7 первый и второй одноВибратор 8, элемент HE 9„ элемент

И 10. одно?1ибратор 1 1, входы 12-15 задания коэффициентсв уравнений, Входы 16 и 17 задания Величин пра.зых частей уравнений, вход 18 зат1уска устройства, Выходы 19 и 20 результата устройства, Выход 21 сигнала окончания решения. Блок приоритетного формирования нулей содержит m идентичных схем, где Ql = разрядность устройства каждая из которых содержит одковибратор 22, элемент 23 заэлемент И 24, вход 25, ход 26.

Устройство работает образом. !

В блоке приоритетного формирования нулей в стационарном режиме "О" или "1" на входе 25 повторяется на его выходе 26. При перек1почении "1" в "0" на входе ?5 одновибратора 22 последний запускавтсн и на его Выходе имеет место "1", на выходе 26 формируется. 0". При переключе?п1и

"О" в "1" на Входе 25 одновибратор

22 запускается. На его выходе формируется отрицательный импульс длительностью, после Окончания которого на Выходе 26 формируется значение " 1". Таким обоазом значение " 1" ня Выходе устрОйcvB=; формируется с задержкой на регулируемое время 7 в то время, хак значение "О" сразу же поступает на Выход.

Перед началом решения в исходной

СЛАУ Ах=Ь осуществляется замена переменной

x = Z — х гпа х

5 где х — вектор компоненты которо àõ

Э го положительные и не меньше максимального по модулю решения х. СЛАУ

12

Ах = Ь, такой, что выполняются неравенства

1О ОЫ =Ах +ЫЕ =А й, ?па х

В результате приходим к СЛАУ.вида

AZ= f решение которой неотрицательное, так как

Z = х +х >О

4? àÕ

Указанное преобразование осуществляется, если компоненты матрицы А удовлетворяют условиям

О а„; 1, а, (О, à,. >+}а;„l

9 ei

В этом случае значение х . долж од но удовлетворять неравенству где тах11Ь1 - наибольшая по модулю компонента вектора Ь.

Из перавенств х1

0

i,j

Поскольку О а.. <1, a,. .О, то

13. (А-.E) Z О и, следовательно (А — Е)? =(А-Е) (х +х ) =Ах +Ь вЂ” (х +

+ Îx " о х åõ

+.х ), откуда

f = Ax +Ьсх +х = А (Ах +Ъ)

=Af = Z", Далее СЛАУ преобразуется к виду

50 Z = Z I(AZ f) p=2" целое число, так, чтобы при Z< > Z

2 выполнялось Z — 1" (AZ — f ) > Z

"1

-ti(A? — f) . На входы 12-17 задаются соответственно значения компонент

55 (1-Ра„„), Ра,, Чр, (1-Р,), РЯх, )if .На вход 18 поступает сигнал пуска устройства, по которому запускается одновибратор 11, на выходе кото>04 4

Таким образом, в устройстве имеет место вычислительный процесс, обеспечивающий монотонную сходимость т последовательности Z у к решению

Z СЛАУ вида А f = Z.

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

8, импульс на выходе которого длится до тех пор, пока в регистрах не устанавливается решение (повторные запуски прекращаются и на выходе

21 формируется единичный сигнал, указывающий на то, что решение найдено) . Элемент НЕ 9 необходим для того, чтобы блокировать сигнал готовности на время запуска одновибратора. После формирования сигнала готовности определяется решение х системы Ах = Ь по формуле х

= Z+ — х

1 аX

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

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

Устройство для решения систем линейных алгебраических уравнений, содержащее и регистров, матрицу и х и умножителей, п сумматоров, выход i-ro регистра (i=1„...,п) подключен к входу первого сомножителя умножителей i-ro столбца матрицы, входы второго сомножителя умножителей матрицы подключены к входам задания коэффициентов уравнений устройства, выходы ;х ()=1,..., n) умножителей i-й строки матрицы умножителей подключены к j-м информационным входам i-го сумматора, (n+1)-е информационные входы сумматоров подключены к входам задания величин правых частей уравнений устройства, о т л и ч а ю щ е е с я тем, что, с целью увеличения произвоZ Н- = 1 (AZ (11 -f ) т 1 т

-1 откуда Z = А f. Запись значения

Z (" 1 > Z невозможна, так как

Z ("1=Z — p (AZ -f) = 2

3 1 3., рого формируется короткий отрицатель ный импульс, поступающий на R-входы регистров 1. В результате значения на выходах регистров обнуляются, на выходах сумматоров 3 формируются значения (111, и (llf, которые .через

1 1 2 устройства приоритетного формирования нулей и элементы задержки поступают на D-входы регистров 1 и по сигналу от элемента сравнения записываются в регистры. Таким образом устанавливаются значения компонент вектора начального приближения Z

=yf, В дальнейшем на выходе сумматора

3.1 будет формироваться значение

Z = Z -p(a Z +а Z -f ), 1 1 1 12 2 1 а на выходе сумматора второй строки — значение

20 а1

Время задержки включения 1 в

i-м (i=1,2) устройстве приоритетного формирования нулей не меньше значения

О шах (10)11 (о )1 (10) 2 (01)12 25 где („).,1, — наибольшее и наимень(О1)1,( шее время переключения значения разрядов из

11 1 11 llpll ltplt

1 на ход умножите 30 ля i é строки j-ro столбца.

Это обеспечивает формирование на выходе i ãî устройства приоритетного формирования нулей значения у, 1 35 удовлетворяющего неравенству у, а Е. — р (а Z +а Z — f ), 1 11 1 И 2 1

i = 1,2.

Поступление информации с выхода устройств приоритетного формирования

40 нулей на D-входы регистров через линии задержки исключает возможность записи значений, которые меньше значений, хранимых регистрами, во время отключения сигналов записи в регистр, 45 формируемых элементами сравнения.

В последующие моменты времени T„, Т,..., Tä в силу изотонности отоб-.

2У э ражения Z — - p (AZ-f) в регистры будут записываться значения последовательных приближений

50 т т т

Z = Z < Z o — t" (AZ o-f ), Z«Z2 Z, — Р(АК -й) т т т т

254504

Щг.2

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

Техред И.Попович

Редактор И. Касарда

Корректор Е. Сирохман

Заказ 4723/54 . Тираж 671

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

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

Подписное

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

3 1 дительности устройства, оно содержит и блоков приоритетного формирования нулей, и элементов задержки, и элементов сравнения, элемент ИЛИ, элемент И, элемент НЕ, первый и второй одновибраторы, выход i-го сумматора подключен к информационному вхоgy i-ro блока приоритетного формирования нулей, выход которого подключен к первому входу i-го элемента сравнения и входу i-ro элемента задержки, второй вход i-го элемента сравнения подключен к выходу i-ro регистра, выход i-ro элемента сравнения подключен к входу считывания

i-ro регистра и к i-му входу элемента ИЛИ, выход i- ro элемента задержки подключен к информационному входу

i-ro регистра, выход элемента ИЛИ подключен к входу первого одновибратора и входу элемента НЕ, выходы первого одновибратора и элемента НЕ подключены соответственно к первому

Ь и второму входам элемента И, выход которого подключен к выходу сигнала окончания решения уравнения устройства, вход запуска устройства подключен к входу второго одновибратора, выход которого подключен к входам установки в "0" и регистров, выходы которых подключены к выходам результата устройства, при этом блок npu1ð оритетного формирования нулей содержит m одновибраторов (m — оазрядность устройства), m элементов И,, m элементов задержки, вход k-го (k=1,...,m) разряда блока приори1 тетного формирования нулей подключен к информационному входу k-го одновибратора и входу k — ro элемента задержки, выходы К-х одновибратора и элемента задержки подключены соот2б ветственно к первому и второму входам k-ro элемента И, выход которого подключен к выходу k-ro разряда блока приоритетного формирования нулей.