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

О

£

«•о

о, /

«.азиизичл* "шзачаъ ¿игзагач-мачаъ <,ииш_иирсгь

И^Ьш^щш!! Цр^ЬЬ ОДпрд}!

чьгзачог гиыьръьрг» изг*шгаъ ъьэ>ьрьъзми.-»ьз1-0Р9аъ шпы.ъьрь исачпьис ьч чьраоичаъ приору Фи&ьш-

оБьюпьис

0.13.02 «СЩттГштшд^шЬ Ьщ1Гщ1)шр<}Ьрэ [ГшпЬш^тшртииГр тЬЩЪр^ш^шЬ ч^инир^шМЬрр )»Ы]1ппдш|1 Ч[1шш1)ши штп^йшТф Ьш]д11ш11 шшЫпи|ипашр1ш11

оьао'ач.ьг

ьръчиъ - 97

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

Аветисян Армине Геворковна

РАЗРАБОТКА ДИФФЕРЕНЦИАЛЬНО-ТЕШЮРОВСКИХ МОДЕЛЕЙ РЕШЕНИЯ КОНЕЧНЫХ ЗАДАЧ И СОЗДАНИЕ ПАКЕТА ПРИКЛАДНЫХ

ПРОГРАММ

АВТОРЕФЕРАТ диссертации, на соискание унеиоя степени кандидата технических наук по специальности Ел з.02-"Системы автоматизации"

ЕРЕВАН - 97

Ü2Íuminml^[i ^шишрЦЦ t StffiramnmUfi '11Ьшш1)ш11 ^шртшрпцршшЦши <,ш1Гш[[1шрш1т111:

R^itnmljmli цЫ^шфпр" <,<, ДО piu»mliJig-mln)aiií.

шцц., ajpn$>. OS. DJiiínlijrali

^ш2шп1пп1)ш1| QtayiJitímfunulitp' áU mljmijtiiriilpn,

ш/jjj., щраф. US. ПпшрЬиш!!

jyigblnn 4.D. ünJitnqTnpjnjli

Опш^агашр t¡an{tfaititípcjDif»pi\r <.m2tlmimljmli inbfubjilitnjji li Jib^piImmJitpiijli

hmjljnlicaU qjunm-hbmtntpuicatunb JitanaJiwEitn

"la^inqmtaipptlii] 1}шр]1лп[ш t is>s>7p. rfmifQ

<.'4ii'<i-¡i оз2 СГша1пп(}11шш1{шЬ hmphpipiif S'QáS-Ji qJimailjrnlj lijimnbpji ijmh[]iíniií (hmngMi4 SbpjmliJi ф., ios>

amhlnn|untmipf[nlr[! ^шрЬф t йшйпршйиц A^áS-li qpmijaipralmiií: DbJiUmqJipp шошр1|шй t; _ _:

cx32 CTtnnümqliwailjmti hmphpqfi л л . . j q

ршриишцпр, uuq.j»., щцЫпл ^ aátilpali

Работа выполнена в Государственном Инженерном Университете Армении.

Научны* руководитель: член-корр. КА РА,

д.т.н., проф. С.О. Симонян

Официальные оппоненты: акад. ИА РА,

д.т.н., проф. А.А. Аракалян.

к.ф-к.к., доцент B.C. Егиазаряк

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

Защита диссертации состоится ¿¿¿¿>J/JJ? 97г. / на засе-

дании специализированного совета 032 в ГКУА (адрес: ул. Теряна, юб)

С диссертацией можно ознакомиться в библиотеке ГХУА. Автореферат разослан___1997г.. .

Учения секретарь специализированного совета 032 V "-lli3-*- Адиюмян

к.т.н., доцент ' i

- 3 -

ОБЩЕЕ СОДЕРЖА!ЖЕ РАБОТУ

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

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

2. Разработка параллельных методов математического моделирования, направленных на их эффективнее использование в высокопроизводительных средствах вычислительной техники и автоматизированных системах различного назначения.

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

Актуальность темы. При применении д1!№зрет^альио_тея-лоРоп_ ских (ДТ-) преобразований, предложенных акад. Г.Е. Пуховым, в результате специфической алгебраизации рассматриваемых задач получаются простейшие вычислительные процедуры, обладающие максимальной степень» расцепления, распараллеливания и агрегации переменных этих задач. В связи с этим становится настоятельной необходимостью проведение широкомасштабных научных исследований гто выявлению как принципиальных, так и практических возможностей использования этих преобразований в рассматриваемой мало изучениея_ области, полученные на основе которых новые научные результаты могут быть использованы как в традиционных,так и в параллельных

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

Цели диссертации

1. Разработка новых математических моделей для эффективного решения конечных задач на современных компьютерах с применением ДГ-преобразованиа, в частности:

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

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

- ДТ-локальных и ДГ-квазилинейных моделей решения целочис-лэнных, булевых и псевдобулэвых задач математического программирования.

2. Создание пакета прикладных программ открытого типа с широкими вычислительными возможностями при использовании алгебры ДГ-преобразований, разработанных ДТ-моделей и ряда известных методов решения отмеченных классов задач.

3. Проведение сравнительного анализа ряда известных методов и разработанных Д1-моделей с целью определения вычислительных характеристик последних.

Научная новизна работы заключается в следующем:

- разработаны новые эффективные модели решения конечных задач рассмотренных классов, основанные на ДТ-преобразованиях;

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

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

- выявлены сравнительные вычислительные характеристики разработанных ДТ-моделей и ряда известных методов.

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

Результата работы использованы:

- в рамках госбюджетной темы 94-166 ГИУА <1995-97гг.>, финансируемой на конкурсной основе Министерством экономики Республики Армения;

- в работах ООО ФВ а Г (акт о внедрении от 28 октября 1996г);

- в процессе обучения студентов, магистрантов и аспирантов ГИУА по специальностям "Автоматизированные системы научных исследований" и "Системы управления".

Теоретические и практические результаты работы были доложены и обсуждены:

- на мевдународной конференции "Application от Critical Technologies for* the Needs of Society" (ЕрвВЭН, 1995г.);

- на научно-технической конференции профессорско-преподавательского состава ГИУА (Ереван, 1996г.);

- на научных семинарах кафедры "Информатика и управление", а также сектора "Измерительная техника и информационные системы" ГИУА (1992-96ГГ.);

- на научных семинарах магистрантов и аспирантов по специальности "Системы управления" Аспирантской школы ГИУА (1992-96ГГ.).

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

Состав и обьем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего ns> наименований, а также из трех приложений, представленных на 30 страницах (приложение 1- параллельная модель одновременного определения корней алгебраических многочленов; приложение 2- распечатки машинных программ основных модулей пакета; приложение 3-пример выполнения одного из меню). Основной текст диссертации изложен на 148 страницах, содержит 23 рисунка и 19 таблиц.

Диссертация написана на армянском языке.

- б -

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, приведены основные научные результаты и краткое содержание работы.

В первой главе представлены основные понятия ДТ-преобразований :

- прямое преобразование:

н* г дКХ<Р

хсю -

К! I э«.к

К- 0,00, <1.1 >

xct) -I £ -- I -ХОО. <1-2>

где ХОО - тейлоровское изображение (дискрета) оригинала х<о с центром разложения t^ (функция цэлочисленного аргумента к), а н -масштабная постоянная, обеспечивающая приравнивание размерностей оригиналов и их изображений;

- обратное преобразование:

00 rt-t

" z — •

K-o[ Н J

Для назначения связи между оригиналами и их изображениями пользуются знаками Z3Z или , т.е. обозначениями:

X<fc> Г-Г ХСЮ ИЛИ xct> 2» ХСЮ. <1-3?

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

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

Для решения систем нелинейных уравнений предложены:

I. ДТ-гомотопические модели

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

Г<Х> - О <2.1 >

(где г - <r1,~.,rn>T - вектор нелинейных алгебраических и/или трансцэндентных функций г^-ЧдГ, зависящих от постоянного вектора неизвестных переменных х « <х1,._,хп>т) предполагается, что их решения существуют, параметрически зависят от независимой переменной t, т.е. х « х<о, а также, что в качестве функций х<о выступают соответствующие тейлоровские разложения.

Расширенный прямореализуемый эквивалент <р<z<t:»-o системы

уравнений с2.о в области ДТ-преобразованна имеет вид:

¿<Z<K» - О, К-ОТ^" , <2.2)

где * = " 1 • • • • »^în^21 • • • • ^ктор изображений,

соответствующий расширенному вектору <р, причем вектора изображения 4>i тлФ2 соответствуют векторам и f2, a ZO(3-<xT<IO!YTciC»T= -cx^lO.....^«!«^^^....^^*»7 - расширенный вектор дискрет, соответствующий расширенному вектору z<t>-ocT<o,YT<t>:>T. Функция гомотоши образуется так:

p(Z(t),fc) - <p(Z(t)) -I- R(t)4p(Z(0))-0, (2.3)

где R(t) - функция, удовлетворяющая условиям

1(0) - -1,

(2.4)

Î

R(tt) - О.

В этом случае, очевидно, величины t4 обеспечивают получение решений системы (2.1).

В ДТ-гомотопических моделях предложен и/или используется ряд производящих функция Ret), удовлетворяющих условиям <2.4): тригонометрические функции, нормированные функции стирлингового типа, многочлены Чэбышева i рода, многочлены Лагерра, модифицированные многочлены Эрмита, Лежащцза х рода, модифицированная функция Еес-селя, зависящая от квадрата полу аргумента. Ддя каждой из этих функций получены общие формулы для расчета соответствующих ДТ-изображений.

ДТ-изображение системы <2.3) имеет следующий ввд:

ФШЮ.Ю = ¿(ZOO) + R(K)-¿(Z(0)) - О, (2.5)

или в явном виде:

D(Z(0)bH-K:-Z(X) + Q(К) - О, VX-TT^", (2.6)

где D (Z (О)) - якобиан расширенной прямореализуемой системы z(t))-o при zco)=zC0), причем

Q(1) = R(1W(Z<0>>, (2.7а)

Q(K) - R(K)-¿(Z(0))+H~*d(Z(1),.. • ,Z(K-1)),VK-ST® , (2.76) где d<o - векторы свободных членов, порожденные переходом из области оригиналов в область ДТ-изображений. При этом:

»»"О.

С2.8)

|Z(K) =-D_1(Z(0))-Q(K)-HK , *К=1,°°,если det(D(Z(0)))*o,

(ZOO =-D+(Z(0))-Q(K)-HK , УК--).» .если det(D(Z(0)))-o,

где D+ (Z (О ) ) - матрица, псевдообратная к D (Z (О ) ), а решения-приЗ-лижения расширенной системы задаются соотношениями: ' г(^)-г(0)-0_1(г(0))- Е Q2p(K)-t.^.

К-1 <2.9 )

+ 00 к 2(t )-z(0)-D (Z(O))- EQ7p(K)-C.

1 K=1 ZF 1

Показано, что необходимые условия сходимости решений задачи совпадают с необходимыми условиями сходимости метода Ньютона, а в изолированных точках ^ для сходимости приближений 2 (ъ) к решениям задачи достаточно выполнение условий и» - о, что

__К—ко *

эквивалентно условиям

11-P<zoc»lp2te

к—>ео *

li» P(û®))i 2,о - °

К—► CD

на октаэдрическую, евклидову

(здесь 1,2,оо - индексы, указывающие и кубическую нормы соответственно).

Получена также оценка скорости сходимости

î r i^-zj2,

Kfix f t к

где p,Y > о - некоторые постоянные, а а = ^ RP(K)* [-^J .

п. ДТ-матрично-векгорные (ДТ-МВ) модели . Система неавтономных линейных уравнений

А(Ь)-Х(*) - a(t) (2.10)

сгде A(t) - (aiJ(t)), l.J-TTK" Я a (t ) - (a1(t),...,ari(t))T COOT-

ветственно матрица и вектор правых частей системы, обладающие

элементами, представимыми рядами Тейлора, a x(t.) - (x1<t).....

xn(t))T - вектор искомых переменных? в области- ДТ-изображений представляется следующей гишрсистемой, обладающей составным вектором дискрет х(-)-(х<о>т;x(i)r|х(2)т =;••• ¡х(к)т)т с размерностью n(K+i)xi и блочно-нижнетреутолъноа гиперматрицзй порядка п(к+1):

А (0) 0 о 0

А(1) А(О) О ... 0

' : : : :

А(К) А(К-1) А0С-2) ... А(О)

Х(0)

Х(1)

Х(К)

.(К)

(2.11)

где А(К)П1А(Ь), Х(К)_^Х(1), а(К)_1_а(Ь).

В компактной записи последняя имеет вид

А(" ) "X (" ) " »(• ) , (2-12)

где А(•)- квадратная матрица порядка п-(к+1), а »(• )-(»(о)т |а(1)т [••• |а(к)т )т - составной вектор дискрет правых частей системы (2.Ю) с размерностью п-(к+1)х1.

Таким образом, решение задачи (2.10) свожгся к поиску вектора х(-) и определению функционального вектора х(ъ) в соответствии с преобразованием , при котором рассматриваются два следующих случая:

1. Матрица а (о) невырождена, при котором, очевидно, невырож-

дена также гшзрматрица а (•). Для этого случая имеем:

х(о) х(1 )

Ло 1 0 0 1 ... | 0

Л1 0 • • • i 0

i :

jv-i Va 1 0 .

х(к)

где

йо " а_1(°) - а_1(0)-е -

- -а_1(0)-[ а(1).а-1 (о)] - а_1(0)-л-,

а(о) а(К)

(2.13)

(2.14)

- -А"1(0)-^А(Р)-/^._1> - А_1(0)-/^ , V К > 2.

В компактной записи составное вектор дискрет ХСО представляется в виде:

Х(*) - А"1(-)-а(.) - Д(.)-^(.), (2.15)

где А~1 (•) - д(-) - обратная матрица гиперматрицы д(-) порядка п-(к+1). а преобразование (1-2) приобретает вид:

х(ъ) = 'а'^соз* £»<ю- ^а<р>-х<к:-р^. (2.16)

2. Матрица а (о) вырождена, при котором вырождена также гиперматрица А(-). В этом случае составной вектор дискрет ХСО определяется в соответствии с выражением

х(-) - *(.)+••{•) ♦ (2.17)

где +л(-) и л(«)> - гиперматрицы порядка г>-(к+1) со структуроа гиперматриш .), компоненты-блоки которой вычисляются слэдующим образом:

(2.18)

í»o+- А-(О) - А+(0)-Е - А+ <о)-лв4

-А+(0)-[А(1)-А'1'(0)] - А+(0).

V* -А+(0)-\ А(Р)-/Ь =» P¿1 К Р> + А+(0)." v К > 2

Е .

и,- -А+(0)-[ А(1)] - А+(0) Л '

(2.19)

+ ак" -а+<°)-1 a(p)- + vp - а+(0)- + ^ , v к > 2.

Р= 1

В соотношении (2.17) матрица +w - di=«g(+w.... ,+v), причем +w -

к+i шт.

- E-a (О) • A (O), Y(«)»(V(0) !Y(1) ¡ * • • | Y (К) ) -n-(K+l) - МврНЫЯ

составной вектор корректирующих дискрет с компонентами y(p)

- ÍO -

- (у, (p), • ■. .уп(р> )т • р=°.к. который определяется из системы

- = (2.20)

где w+ - «"as (v+,...,w+), причем v+» e-a(o)-a+(o). Матрицы .«(■>)

_ k+1 ШТ. _ _

и /)(•)+ - шперматривд порядка п-(к>1) с компонентами +a{j),j*ojc и j«o,x, также обладающими вышеуказанной структурой. В

этом случае решение задачи в соответствии с преобразованием (1.2) имеет вид:

Х(0 - Ц-±-} • |а+СО>« £аСЮ- 2A<p5*XfK_p5j++>'-Y(K)J. (2.21)

т. Матрично-векторная параллельная модель Гипврматрицу c2.1i) представим в виде

A<0¿0-XC.) - аСО^О, <2.22)

где acojo - квадратная матрица порядка п-<к+1>, х<оЗо»<х<о)т \ !x<i)Ti•••;хск>т)т - п-ск+1) - мерный составной вектор неизвестных дискрет, а а<оЗо=<аСО)Т |аС1)Т | • • • |аСК»Т - СОСТЭВНОЙ ВвКТОр дискрет правых частей той же размерности. Для решения этой системы имеем выражения:

-i

Х<-> » А <0,К)-а<0,К), если rangACO) = п, С2.23Э>

Х<-> = А СО,К >-a<0,)0+W<0,JO-Y<0,K), вСЛИ ran6AÍOXn, <2,23б>

т

где у<о^о-сусоэ [усо {•••|уск> > - п-<к+1> - мерный произвольный вектор дискрет, у<о5о - е - а+<о^о• аТо^о - матрица рассогласований порядка п-<к+1>, а+<оЗо - е-обратная матрица матрицы асоЗо порядка п-ск+1>.

IV. ДТ-ньютоновская и ДТ-жордановая модели Неавтономные системы нелинейных уравнений вида

ГСх<0,0 = О <2.24 >

<ЗДЗСЬ Г<х<Ь),0 - СГ1<хС0>0,-.Д' <х<Ь>,Ь»Т и ХСО = <*1<Ъ>,

п - мерные векторы, соответственно, нелинейных и/ или трансцендентных функций с переменными коэффициентами и искомых переменных) обладают некоторыми конечными или бесконечными множествами решений при совместности этих систем и не обладают ни одним решением, в противном случае.

При применении метода Ньютона для решения ДТ-эквивалента

РСХСО,.) » о <2.25)

системы <2,24) (где ГСХ<К),К) ПГ 1Чх<1-),Ъ), Р<Х<.),.>-<ГТ<Х<0),0): гт<х<1),1); •• • !Гтсхск),к))т - ш=г>-<к+1> - мерный составной вектор с п - мерными векторами автономных операторов, а х(-) = (х(о)т; ;х(1)т] - - •; х(к )т )г - ш - мерный составной вектор неизвестных п-мерных векторов дискрет искомых зависимостей х<*.)) получена еле-

дующая модель:

Х<.)_^., =» ХС.) -D-1CO-FC.> , р+1 р р'

Х<-> - lim ХС.) ,

оо р

(2.26)

где якобиан о<.э - лзгко обратимая блочно-нижнетреугольная гипер-иатрица со слэдуюцэй структурой:

dc.) -

D< 0) О 0 ... 0

Dil) D<0) 0 ... 0

: • :

DOO 0CK-13 DCK-25 ... D<0)

причем в<о> _ п - мерный якобиан системы сг^гч), с<1> - ей гессиан. ос2) _ матрица ей частных производных 3-е го порядка и т.д. Посла нахождения составного вектора дискрет хс.> зависимости х<о легко определяются в соответствии с <1-2).

Системы вида <2.24), в общем случае, допускают следующее эквивалентное (неоднозначное) формальное представление:

А.(х<ЬУ,Ь)'Х(Ь) - Ь(хСО,Ь), С2^27)

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

A(X<0),0) 0 ... О

A(X<1),1 ) А (XC0),0)) ... 0

• ;

А (X<JO,K) A(XCK-l).K-l) ... А(X<0),0)

Х<0)

Х(1)

Х(К)

Ь(Х<0>,0)

Ь(Х<1),1)

Ь(Х<Ю,Х)

<2^8)

системы <2^7) при применении схемы жордановой диагонализации и метода последовательной верхней релаксации получена модель:

|х<->

, - <l-w)-XC.) +t«jCd~ic.)^.,d~ 1СО)Т, tu е <0,2),

р+1 р 11 ЛИЯ

Х<->

Ilm X<«)

Р-

<229)

где

причем

dii<">

Ii

... 1, ч i?l m- i, . .-1, . b, <• > - ¿.„a, <»).d <•)

m-1.

, 1 - l^n ,

p-1 ip

"U

U

<•) -

1,пт-р + 1

m-p-M ,j

PP

»P'1

m-p+1 ,m- p+1

i,J - l^n-p ,

Ь?СО = Ь?_1СО -1 1

«Г1 ^о-ь*-1 со

1 р-+1 т-р+1

т- р+1, т- р +1

1,т-р

Затем, в соответствии с преобразованием <1.2> определяется решения СИСТеМЫ С2.25).

На основе жордановоа модели предложена также параллельная глобально-сходящаяся модель одновременного определения всех корней алгебраических многочленов (приложение 1).

Для решения задач математического программирования вида

|х(х) —» п»1п

1 Х (x; с(х) < о

(2.30)

(здесь ь(х) - скалярный критерий качества, х-(х1.....хп)т~ вектор

искомых переменных, с(х) - (с1(х).....ст(х))т- ш - мерный о™£г»>

вектор ограничивающих условий, причем ь(х) и с(х) имеют частные производные первого порядка по всем компонентам вектора х) предложены ДГ-локальные и ДТ-квазилинейные модели, в которых все ограничения типа односторонних слабых неравенств приведены к эквивалентному редуцированному вектору ограничений типа равенств:

э(с(х)) - 1е+51<жс (х)].с(х) = о. (2.31)

При этом:

ДТ-локальная модель имеет следующий вид:

Х^СК+15 - - ^<^<K:>:>+2k1.ЭQT<Xv,<)O>^■

*SGQCXl/K:»»Q0<v<^O:>J , х/о>-хо, ,

(2.32 )

где

БОО <Х „<К>)=с11ае

0, если <> сх^«»»«»!

1, если <?

4, если О^Х^СОЭХО

, если к=о

о, если к>ю

- перестраиваемая индикаторная матрица ограничивающих условий, а ДТ-квазилинейная модель такова:

ДХк<Р+1Э =

н

V

к+1 ЬСХ

X, + ДХ, <ъ> к к

к. • дОТ<Хк5-рСХк>] • ЪСР>, > = ДХ =? ,

о

г Г Ь -|р

-к2'^ЬСХк> + "1 - -Тс' —'к

ХСОЗ=Х »?; Дх, <0)=ДХ о к

(2.33

Р»0

к + 1

Ь<Х, Э + ?ЬСХ, >• ДХ, <о . к к к

В этих моделях к1 и к2 - выбираемые коэффициенты с довольно большими величинами, эр (х) - обобщенный якобиан составного вектора ограничений осхэ-о, компоненты которого определяются в соответствии с множествами

д<}. в . 1 , VI—1 ,п.

а) Для задач целочисленного программирования

Р(Х) = (51(Х)^..^М(Х)|Я(Х)) - О,

где чсх> - один из следующих ограничений св зависимости от требований целочисленности переменных задач):

К2Р(Х)=Я (Х)-л£(Х)=£ ^(2Р^п)-Х2г-0, если х1бО,±1,._Д(р1-1);У1-Х^,

Г«1

р _

Ир(Х) » Е О, г б N. если хк е 0,-1,_,-^-1); У1-1,п ,

_ (2.34)

Кр<Х) » Е О, г е N. еСЛИ х1 е 0,1_,,

г«1

в которых <>(•) и 5(•)— числа Стерлинга 1-ого рода.

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

0<хз-(5 (х)^..^: (Х)|К (х (х ))т - о,

где __

(х1-1)-0, 1-1 ^г , (2.35)

а при агрегированной модели:

О(Х) - (51(Х)^..^т(Х)! Ь1(Х)|Ь2(Х))Г = О,

где

(Ь. (X) = (С052ЛХ)Т-е - п » О,

1 _ (2.36)

Ь2(Х) = X • <Х-е) - О,

причем С052ТТХ = )Т - п - МврНЫЙ ВвКТОр, 3

в = - и мерный единичный вектор.

в) В неагрегированной модели псевдобулзвых задач

<?(х,х) - (бт (х,х) I в * (хД) |в!(хД) )т = о,

гДе _ _ _ т

Гв (Х,Х) = (ь (х,х)_д> (х,х))т - о.

|в2(х,х) - (ь21(х^с),„4>2л(х^с))т - о.

В агрегированной модели:

О(ХД) = (3Т(Х,Х)!Ь (ХД)!Ь (ХД)!Ь (ХД))Т - О,

где 12 3

(2.37 )

Ь1(Х^С) = (С03ЯХ)Т-С05ПХ + п =■ О,

Ь2(ХРС) = ХТ-Х + ХТ-Х - п = О, (2.38)

Ь (Х.Х) = (ХТ+ ХТ)-е - п = О,

причем cos2ttx» (cos27txl^.,cos27an)t и cos2tix - (cos2ji<ir_, со^ггоГ^)T - n - мерные функциональные векторы, а в - (i_,i)T n - мерный единичный вектор.

Третья глава диссертации посвящена разработке пакета прикладных программ собьем - з5о,л Кбайт) с машинной реализацией ДГ-преобразований, а тага® предложенных ДТ-модзлэя и ряда известных методов. Структура пакета представлена на рис. i. Пакет рассчитан для персональных вычислительных машин, универсален, язык реализации - pascal. Пакет работает в пакетном, графическом, диалоговом и диагностическом режимах, ввод-вывод и численные расчеты - типа pascal. Основные математигическиэ объекты пакета - произвольные выражения, функции, матрицы, векторы, раду, коэффициенты целого или вещественного типа, что позволяет эксплуатировать пакет без каких-лиЗо предварительных знаний. Исходные данные всех типов вводятся без каких-либо первоначальных изменений.

Рис. 1

Модульная структура пакета (созданы 9 модулей со своими процедурами) дает возможность расширить его новыми программами и

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

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

Четвертая глава работы посвящена решению ряда задач различных классов (задач ошталального управления кораблем, торпедой, самолетом, модельных примеров) всеми вышеуказанными моделями, а также получению следующих сравнительных характеристик:

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

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

2. в ДГ-МВ моделях:

а) При фиксированном значении параметра к, т.е. степени многочленов Тейлора, аппроксимирующих компоненты xi<t), i-i,n , вектора искомых переменных x(t) гиперсистема (2.11) определенна-, ибо количество содержащихся в ней уравнений (м) равно количеству искомых дискрет (и), т.е. м = n =<к+1)-п, из-за чего найденное при этом решение x(t) является явным "точным" решением. Однако, при применении известного метода приравнивания коэффициентов (МПК) порожденная для определения коэффициентов искомых многочленов-компонентов вектора x(t) система характеризуется следующими свойствами:

- обычно переопределенна и в, частности, если степень многочленов Гейлора, аппроксимирующих элементы а^(t), i.j=i,n матрицы a(t.), .также равна к, то имеем оценку м < 2-(x+i)-n > n ■» (k+i)-n;

- обычно несовместна, и, как следствие, обладает некоторым "неточным" псевдорешением или нормальным решением (при совместности порожденной системы, что на практике встречается редко, эти решения совпадают с точным решением исходной задачи).

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

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

Преимущества ДТ-МВ моделей неоспоримы и в свете того, что они обычно требуют п4-к2к-зэг»3+<2к2+4к+з)г»2-2га операций умножения и п4+<к-з>п3+<4к2+лк+11>п2-2с2к+з>п операций суммирования, значительно меньших аналогичных оценок МШ - <к-и>4п4-к5к3+ик2+вк+

+25п3+С4К2+7К+3>п2+20С+1Эг1 ОШраВДЙ УМНОЖвНИЯ И <К+1>4п4+2СЗК3+

+5к2+2юп3+к<к+1>п2-зооиэп операций суммирования.

п. Оценка степени распараллеливания и эффективности

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

Для разработанных ДТ-моделей получены оценки показателей распараллеливания и определено оптимальное число необходимых процессоров (р).

1. В ДТ-гомотопических моделях оценки распараллеливания и эффективности в основном, совпадают с соответствующими оценками метода Ньютона и квазиньютоновских методов, которые представлены в табл.1 <а, р. - соответственно времена выполнения операций суммирования и умножения). В этом случае целесообразно организовать* вычисления в асинхронном режиме.

2. Для ДТ-МВ моделей обоснована организация вычислений блочным, прямым и диагональным способами, при которых полученные оценки показателей распараллеливания также представлены в таб. 1, соответственно в строках а), б) и в).

3. При использовании ДТ-локальных и Д1-квазилинейных моделей целесообразно выбрать векторную систему из г» процессоров, полученные при которой оценки распараллеливания представлены в последних двух стррках табл. 1.

Таким образом, из предложенных ДТ-моделей для распараллеливания алгоритмов широкие возможности предоставляют ДТ-МВ модели, причем при отмеченных 3-х алгоритмах количество используемых процессоров несравненно меньше количества необходимых процессоров при использовании МПК (п2-(к+1)2). ДТ-гомотопические, Д1-локальные и Д1-квазилинейные модели, в основном, повторяют возможности распараллеливания соответственно квазиньютоновских, субградиент-

ных непрерывных и квазилинейных известных моделей.

Таблица 1

Модель р 3 Р Е Р

ДТ-гомотоп. п (2пф- (п-И )У ) (2п&+(г>гИ)ц)Уп(й+}1)

ДТ-МВ а) К+1 п(<*+Д) п(сгц)

((Ио^п+р) (оИое2п*ц)' <к+1>

б) 2 п <К+1 > • т?У (<*+}!) <к+1>-п

в) г>- (К+2)-1 0. 3 Д1 о ^п ( 3-Мо^п ) о. з^1ое2п (з+1ое2п) п-(К+2)-1

ДГ-локальная 11 (2псЦ- (п+1 )Ц )/ (**/! ) (2псе-(п+1)ц)/п(сН71)

ДТ-квазили-нейная п (2г»с**4(п+1 )рУ(<*+11) (21(т*+1 )Ц )Угх (а+Д )

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

На основе использования предложенных дг-гомотэгсгсоских мотелей стало возможным получение намного более рас::::л, частности, в задаче оптимального управления торпеде2, а такта р: -шений неавтономных задач в результате заат,ггзлы:о малого сбю^л вычислений на основе использования Д1-МВ моделей. При зтем г.:з вычислительные операции для решения рассматриваемых задач с начала до конца реализуются машинными способами. Выявлено также следующее важное свойство ДТ-МВ моделей: при увеличении значений па-•раметра к соответствующие гиперматрицу просто расширяются, а составные векторы дискрет вычисляются аналогично, без каких либо дополнительных затруднений.

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

ЗАКЛЮЧЕНИЕ

Научные результаты диссертации::

I. В области специального математического обеспечения автоматизированных систем:

- разработаны ДТ-модели решения конечных задач.

1. Для решения автономных систем конечных уравнений предложены ДГ-гомотопические модели с применением различных производя-' щих функций:

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

б) в которых для использования предложенных, модифицированных и известных специальных производящих функций получены общие формулы расчета' их ДТ-изображений;

в) для которых получены условия сходимости вычислительных процэссов и оценки скорости сходимости.

2. Для решения неавтономных систем линейных уравнений:

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

б) разработана ДТ-ЫВ параллельная модель с большой степенью распаралеливания, обладающая высокой машинной производительностью.

3. Для решения неавтономных нелинейных систем разработаны ДГ-ньютоновские и ДТ-жордановые модели, обладающие основными преимуществами вышеназванных ДГ-МВ моделей.

4. Для решения различных классов задач (целочисленных, булевых и псевдобулевых) математического программирования разработаны ДГ-локальные и ДГ-квазилинейные модели, эффективность' которых повышается по мере увеличения размерности задач с применением специальных дополнительных "ограничивающих условий.

и. в области программного обеспечения автоматизированных систем

- создан пакет прикладных программ, основанный на ДТ-пре- . образованиях:

1. Который предназначен для персональных вычислительных машин, универсален, язык реализации - pascal, работает в пакетном.

графическом, диагностическом и диалоговом режимах. Основные математические объекты пакета - это любые выражения, функции, матрицы, вектора и ряда, коэффициенты целого или вещественного типа.

2. Модульное построение которого (созданы 9 модулей со своими процедурами) дает возможность дополнить его новыми программами и процедурами. Работа пакета управляется в диалоговом режиме посредством меню, т.е. дает возможность эксплуатировать его любому пользователю. Работа пакета в графическом режиме значительно упрощает анализ полученных результатов.

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

т. Выявление качественных и количественных характеристик предложенных моделей.

1. Получены зависимости между количеством вычислительных операций и средним числом итераций, с учетом порядка систем и количества используемых дискрет.

2. Оценены степени распараллеливания вычислительных процедур и эффективность моделей.•

Основные результаты диссертации опубликованы в следующих работах:

1. имгаъзиъ ил., аааазаъ ч-.ч., ачьэьизаъ ад., аоьадозаъ'

"1.1:. СТшп1гад{1шшд11ш& йрш<ц1Ьр]1 фшрЬр}] ^ш^пиТд4 ЭДйЦшй ц}1фЬрЫ1д[1Ш[-р1щпр]ш11 ¿ишфп(ишр)шТ1ЬЬр11 (1рш <1[Ьр2шЦпр {ийц^рЬЬрЭ. 94-166 1п1пп. дшр1. рМшф чриншлЦиЬ. ЬшгЦ. 1996 • 33 ф

г. АВЕТИСЯН А.Г. О некоторых характеристиках ДТ-гомотопических моделей. Вопросы повышения эффективности систем управления технологическими процессами /сб. статей.- Ереван, ПСУА, САУРА, Ч. 1, 1996, С.53-58.

3. АВЕТИСЯН А.Г., ОВАКШЯН В.О. Параллельная модель определения комплексных корней алгебраических многочленов. // Вопросы повышения эффективности систем управления технологическими процессами /сб. статей.- Ереван, ГИУА, САУРА, 1994., С.30-35.

4. АВЕТИСЯН А.Г., СИМОНЯН С.О. Пакет прикладных программ для решения конечных задач на основе использования дифференциально-тейлоровских преобразований. /у Вопросы повышения эффективности систем управления технологическими процессами /сб. статей.-Ереван, ГИУА САУРА, 1996., Ч. 1, С.65-6?.

5. СИМОНЯН С.О., АВЕТИСЯН А.Г. Дифференциально-тейлоровская гомотопическая модель систем конечных уравнения //Электрон, моделирование, 1997. N 1, Том 19, С. 19-25.

6. СИМОНЯН С.О., АВЕТИСЯН А.Г. Конструктивный способ решения линейных неавтономных систем конечных уравнений на основе ДГ-пре-образований // Электрон, моделирование, 1997, n 4.

7. СИМОНЯН С.О., АВЕТИСЯН А.Г..ОВАКИМШ B.O. Дифференциальные спектры специальных производящих функций. //Вопросы повышения^ эффективности систем управления технологическими цроцэссами. /сб. статей.- Ереван, ГИУА, САУРА, 1994, С.25-29.

е. СИМОНЯН С.О., АВЕТИСЯН А.Г. Процедуры решения нелинейных неавтономных систем уравнений, основанные на ДТ-преобразованиях. /Материалы научно-технической конференции ГИУА. Ереван, ГИУА, 1996.

9. AVETISSYAN A.G., SIMONYAN S. An Application Program Package for Solving Finite Problems Based on Differential-Taylor transformation //International Conference on "Application of Critical Technologies for the Need's of Society". Yerevan, 1995.

10. SIMONYAN S.H., AVETISSYAN A.G. Effectiv Aggregation and "Fast" Models for Solving Psewdoboolean Problems of -Mathematical Programming //The Problems-of the Efficiency Improvement of the Control Systems of Technological Processes. ANCAC. VoL 3, Yerevan, 1992.- pp.33—42.

11. SIMONYAN S.H., AVETISSYAN A.G. Jordanian reduction of finite systems and the effective method of their* solution // The problems of the efficiency improvement of the control systems of technological processes.- Yerevan, 1992.- P.14-24.

12. SIMONYAN S.H., AVETISSYAN A.G. The Parallel Globally Convergent Method of Defining Real Roots of Algebraic Polynomial. //The Problems of the Efficiency Improvement of the Control Systems of. Technological Processes; ANCAC. Vol. 3, Yerevan, 1992. pp. 25-32.

13. SIMONYAN S.H., AVETISSYAN A.G. The Procedures for the Solution of Finite Systems of Nonlinear Equations based on Computational Schemes of Linear Algebra // International Conference on "Application of Critical Technologies for the Need's of Society". Yerevan, 1995.

[ШФОФОКГ'

UmblmiJunimtpjuili qjimraljrali mpijjnilipbhpü ЫГ

i. Qilmmfoimmgiímli htniíujlpnpqbpli hmuinilj itiupt¡iíinwfil]caljaili uiqnihni|iJuiti plnnquiiltnnniif

- ilhn?mUnn hilnxhnTibnh tmWmli T-g-JimbiIibnh Jymliniifp:

1. ЧЬргпЩпр hratlramDpmiíIihpJi nii[mnlmií bmiímljrapqbpji [mínínib huiiímp' шшп^шрОДшй bb ipalrtnqnili шршшцрпц фшЫде^шЬЬр!! yipinniitniTp 10-hmínmnqJili ifmjhilibp4

ш) npnlip одщфп& hli ilmb¡in¡m[jtaglimjli ptapàp ramnjiáinlmil Ii harçtln- ' Umkrall iftö rapijjmlmiTlbmnipjmifp4 ji 2bnph{iij p, K.t^ quipmtlbwpbpli QlqqQp-Ijnq n+3 ¿шфш]йшррт1р тшрш&шрриЬшГ qmpqmqmjli qmqmhbD pilmjjili pliptn-gmlpnpqbpli tpnqtfinljhpiqtiaili hlnnprai{npmpjrali;

p) npnligntil oquitnqnpín{nji рпрр ШЕш^шрВДшй ü hnranili tnptnmqpnrç ^nililjglimlibpti bmiftnp шпшд![шй bli 1Ä-njniuil)bplibpli hnrçililinli plrqhnilmip pnilrai-âlibpp;

q) npntig hraiírap пишдфий bli ЬшгЦпцш^шй qflpirpliptngbbpli qniquiiljiui-lítnli рш1{шршр qrajiínitihbpto ш qmqraiTJimilmti tnpnjqnipjuiü qlraihtnmtnl¡aili[i:

2. tnilmnlmtí q&mjlih hratjmmiipminihpji hnultnlpiipqhpji imínlmli hrailtup*

ra) ^шВДшй t 1S-U4 qmqtnbbn-burçnpjiniljnili ilm^in» npti шщшЬЦпи! t

harçilnrçmtitnli jilipnigniljnipqhpji pcapip tnpqjmlraitlbmmppuli ti qtnpq ilbphlmijinlunli Jipraljralraigmir (i ЬшгИ ЬпиГшщштшфшй h[iqbptfimnp|iglibp|i limlmlnnilnpilmö pinljm-libppJiti-bDmlilipulraiâlj Ijcnnrngilmöpli ni rçpintig hmljmqmp¿iímli haiiíinp тпшдфнй mlimiJiinlilj tnpmiiihuijuinipjmlilihpli ;

p) ¡ГгшЩшй t qmqnihtmailiuilmigiiiiili mntmlbiniqnijl] niuinjiiiaitotl, muinji li ptnpâp Ьшгфщш^шЬ tnpiijmlmnlbmnipjniifp oduujmö qniqmhtm ilnqfciQ:

3. D^ rai{mnlmif q&mjjili htnilniiraipminibpji braiimlimpqhpji шрцрзЛСЩЬш imínímü hmiírap ^щЩшй'tili ЦЬрр ЗДшй (ГпцЬ^Ьрр bJnHimlimli шпш-'ilhimpjniMihpml odimjiníi T-B-lijmmnbpiili 11 IJè-dnpqmlijml] йгщЬ^ЪЬрд:

4. Umpbiimm[iliralirali öpuiqpaiijnpilnili шшррЬр inuuhpji {miTpnrugrapJiit. ршцшЬ, Ijbqä—ртцшТх ) ¡ulqliplibp¡i [niôifuili banlaip шпшгшрЭДшй щшдшдр^ шпь11ш11шфш11ш11ььр|1 libpifnidiTtoli ¿ímlitnqraphni{ йгшЭДшй kli 1-Í3-—inbr\mjfili Ii Ift-pilraqliqímijtili ilm}b[lil;pn:

и. Oilmnilmmmgilinli hmilüiliuipqhpti ôpmqprajtiti niquihm{iíuili plraiqini(mDmir

- T-a-abmthnhmpimlibbnli ilnni htuniijiiiü lifrnmnmliuili &1шдрЬр|) фшрЬрЬ umbnümifp*

i. Qpo lraifuujuibm{tn& t nibhtnuinitjuilj huijilnqnilpiiti libphliajlibpti haiiíuip, htnlipuilrçuilmil] t, Jipuitiuiliaigifuili [hqnili4 pascal -Ii t b ai2fuuimmil t фшрЬрш-jfili » qpin5>lil¡mlimb, qliinqlmuw¡il|uil}!nli b hpl|[unuuijlili nbdtiinibpniil: ФшрЬр[1 hjiiiliinliinli iíuiphilnjm|il)uitiuili op]bt¡iníibpQ 1]ш11ш]ш1[ш11 mpmmhuijinmpjmlilibp,

3>mliligtiuilibp, ilmmpjiglibp. ЦЫ^шпрЪЬр Ii 2ШР1?ЬР bli, qnpömlijiglihpli Jipmljaili ni unípnqj mjiajli Uli:

2. Dp¡i tímpuaijlili Ipjmnigtlaiöpi! (пшЬдйЦшй Uli » tlnipulibp' JipMig щрпдЬцтршЬЬрпЦ) hlnnpaitjnpnip/nili t тшфа phi¡[m¡bb[ tnjli Imp &ptnqpbpnt| U qpngtqmpralibpnil: (Draphpji шг1ишшш11рц timipíinljbpnjilniil t ilblijmlibpti lili^n-gntf hplj[untnnj[iü Dbijulmil. aijntilipli hlnnpuiilnpmpjmli t mmiJiti mjTi 2ш11ш-qnpôfc[ gmbljragraö oqimnmjipng linniTJig: Ompbpji nrçlutnmralipn qpmifrlilpiilpiili nb-dtiifntil МцптЬфпрЬй hb2mmgliimí t mnaigtiraù tnprjjmlif¡libp¡i iibl[lirapmlirailQ:

3. ûpn. pragji IBHmiUpuihnrçillig Ii 10^tínj]bilibpli JipmljmlnngmilJig, ßlujqpljratf t lirali iltpjrailnp tutajjiplibpji [niiriltnli tf)i 2ШРВ hrajuiliji hiiraliui!|Iib-p}i líbpblnnjmlirali Jipratjmlnngtrrali tqpngbiptpmlibpQ, ¡i1i¿li t¡ hlrapniilnpnipjmli t pliábnmit Inujli lil^nulmjpiuil Ii Ьш^шишршцпр quijilailihbpniil 1рптшрЬ[ iljmljiluiö Ii htnpnliji tlni)bilihp]i hmübilniinmljrali xlbpimtmipjnilqi:

ni. ОпшутрМшй Jnnhilihpti pmtolimlimli m npmlimlimU plmipaiqpbnti ршдшЬш[Ц1пи(р:

í. Umaigilmö bli Ьшг^гщш^шЬ ppímqnipjnililibpli praüuiliJi Ii Jimbpuigliui-Iibpji lililí P"ll> 1Ф2*1 liuituilraúmpjmüübpii4 b[l]bintl hratímlimpqbpli l{nipq{ig m oqmmqnpôtjn^ rjjialmbmtibpji puilrailjjig:

2. <Шп1шит1ш0 bli línijbilibpji qniqmhtïDuiljniIraigiluili mninJidmlilibpQ Ii шр-q jiuüra t{bin ni р]ш bu :