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

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

Иллюстрации

Показать все

Реферат

 

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

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

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (633024 (б1) До полн н тельное к авт, санд- ву— (22) Заявлено 25.12.75 (21) 2302808/18-24 с присоединением заявки №вЂ” (23) Приоритет— (43) Опубликовано 15.11.7R.Бюллетень ¹ 42

О

4 канав . д ™ (5l) М. Кл.

G 06 F 15/36

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

Совета Министров СССР оо делам изооретений и открытий (53) УД.К 681.325 (088.8) (45) Дата опубликования вписания 20.11.78 1

В, В, Яковлев и Г. В. Йобрис (72) Авторы изобретения

Ленинградский ордена Ленина институт инженеров железнодорожного транспорта им. академика

В. Н. Образцова (71) Заявитель (54) ВЕРОЯТНОСТНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ .

CHCTFM ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ

УРАВНЕН ИЙ

1

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

Известно вероятностное устройство 5 для решения систем линейных алгебраических уравнений, содержащее преобразователи число-вероятность, блоки умножения и сложения, генератор случайных чисел, интеграторы корней. Недостатком тц этого устройства является низкое быстродействие, связанное с медленной сходимостью процесса итераций, и большая аппаратная сложность (11.

Наиболее близким техническим реше» 15 кием к данному изобретению является вероятностное устройство для решения систем линейных алгебраических уравнений, содержашее последовательно соединенные первый блок ключей, блок преобразовате- 20 лей число-вероятность, блок умножения, блок сложения, блок интегрирования, вто рой блок ключей, управпяюший вход которого соединен с управпякнцим входом пер2 вого блока ключей и с. выходом блока управления, вход которого соединен с выходом генератора тактовых импульсов и со входом генератора случайных чисел, выход которого подключен к управляюшему входу блока преобразователей число-вероятность и.

Недостатком этого устройства также является низкое быстродействие.

Пель изобретения заключается в повышении быстродействия вероятностного устройства для решения систем линейных алгебраических уравнений. Qns достижв ния постановленной задачи оно содержит блок задержки, входы которого соединены с выходами блока сложения, а выходиI со входами блока умножения соответственно.

Блок-схема устройства приведена на фиг. 1. На фиг. 2 приведен пример соединения блоков применительно к решению систем линейных алгебраических уравнений третьего порядка.

Устройство содержит первый блок калошей 1, блок преобразователей число-веF>

1акнм образом, дпя получения нового и точного значения корня (т.е. результата каждой поспедуюшей итерации) требуется только один Mашинный такт.

У Технико-экономический эффект заявляемого устройства закпючается в резком (10-50 раз) сокрашении времени дпя решения СЛАУ по методу итераций.

63302 4

/ ких уравнений Т получим, воспользовавшись соотношением (3) (1р) где щ -количество тактов, необходимое дпя получения результата с точность С

$p — параметр нормального распределения.

T=tmf (4)

Так как обычно m >Ъ, то уравнение

lO (4) дает время решения большее в раз, чем уравнение (3), справедливое для предлагаемого устройства. Обычно итерационный процесс завершается через несколько десятков итераций, т.е. Р = 10- -50.

fS

Это число и определяет выигрыш в быстродействии заявляемого устройства.

Физически этот эффект можно объяснить тем, что если в схеме прототипа (кн) каждое новое приближение Х должно быть выражено в форме многоразрядного кода (на что требуется 7п машинных тактов), то в предлагаемом устройстве каж(к+а дое новое приближение Х образуется в форме вероятности появления бинарного символа и, следовательно, занимает лишь

1 такт машинного времени.

Соединения выходов блока задержки

10 с выходами блока умножения 3 уста- з© навпиваются в соответствии с уравнением (2). На фиг. 2 показан пример расположения таких соединений применительно к решению систем пинейных алгебраических уравнений третьего порядка.

33

Анализ этой схемы показывает, что выражения дпя поспедоватепьных приближений значенид корней Х, Õ . Х в точности совпадают с видом уравнения (2) .

Например, для выхода Х< схемы получаем (к+g) (x) (K) г г (ъХ з

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

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

Источники информации, принятые во внимание прн экспертизе:

1. Яковлев В. В., Федоров P. Ф. Стохастические вычислительные машины, Л., Машиностроение, 1974, с. 322-329.

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

N 481042, . G O6 Р 15/36, 1974, 633024

Юг. /

Составитель A. Карасов

Редактор El. Зубов Техред A. Àëàòûðåâ. Корректор Во Сердюк

Заказ 6555/39 Тираж 784 Подписное

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

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

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