автореферат диссертации по электротехнике, 05.09.05, диссертация на тему:Полиномиальные методы символьного анализа электрических цепей

ол

' ‘ ‘ На правах рукопису

ДМИТРИШИН

Роман Васильович

ПОЛІНОМНІ МЕТОДИ СИМВОЛЬНОГО АНАЛІЗУ ЕЛЕКТРИЧНИХ КІЛ

Спеціальність 05.09.05 — Теоретична електротехніка

Автореферат дисертації на здобуття наукового ступеня доктора технічних наук

Лі.пів — 1996

Головну частку роботи виконано в Державному Університеті «Львівська політехніка».

Офіційні опоненти: ■— доктор технічних наук, професор ІВАНИЦЬ-

• КИЙ Анатолій Мечиславович;

— доктор . фізико-математичних . наук, професор ПОПОВ Богдан Олександрович;

— доктор технічних наук, професор ТРОХИМЕН-КО Ярослав Карпович.

Провідна організація: — Інститут проблем моделювання НАН України,

м. Кнїн.

2>

Захист відбудеться «_________[ »________________1996 р. о_________год. на за-

сіданні спеціалізованої вченої ради Д04.06.19 у Державному університеті «Львівська політехніка», 290646, Львів, вул. С. Бандери, 12.

З дисертацією можна ознайомитись у науково-технічній бібліотеці ДУ «Львівська політехніка».

'І о 4

Автореферат розіслано «___________» ______________ 1996 р.

Учений секретар спеціалізованої вченої ради, к. т. н., доцент

ШЕГЕДИИ О. /.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Дисертаційна робота присвячена розробленню та дослідженню поліномних методів визначення символьних схемних функцій (ССФ) інваріантних у часі лінійних кіл, у яких деякі або всі елементи позначено символами.

Приймаємо, що поліномні методи об'єднують топологічні та нетопологічні методи визначення ССФ, де ділення поліномів або відсутнє, або є без остачі. В роботі досліджено поліноми від багатьох символьних змінних (провідносгей та/або незалежних джерел струму) з дійсними, комплексними або поліном-ними коефіцієнтами (підполіномами). Підполіном -це степеневий поліном відносно комплексної частоти (б). Аналогове коло означає лінійне або лінеаризоване нелінійне електричне коло. Поліномні методи є підмножиною символьних методів. Підвалини символьно-топологічних методів (СГМ) закладено в роботах Кірхгофа, Максвела та Фойснера. Широкі розроблення та дослідження символьного напрямку в теорії кіл виконано вченими США, Канади, Англії, Польщі, України та Росії.

Дисертаційна робота розширює та поглиблює досягнення Львівської електротехнічної школи методів аналізу лінійних кіл, започаткованої професором СФризе.

АКТУАЛЬНІСТЬ ТЕМИ. ССФ відіграють важливу роль у теорії кіл і на практиці - в розробленні аналізних модулів для автоматизованих систем проектування (АСП) аналогових кіл. Аналогові модулі поряд із цифровими поширені в багатьох пристроях, особливо, в апаратурі вимірювання та зв'язку (операційні підсилювачі, фільтри, коректори, фазообертачі, лінії затримки, перетворювачі тощо).

Застосуванню чисельних методів для моделювання аналогових кіл надавалась та надається велика увага, тоді як засво-

єння складніших СГМ відкладалось на пізніше. Проте, не дивлячись на значні успіхи, чимало проблем застосування чисельних методів залишаються нерозв’язаними. Зокрема, повільно та не-досить точно моделюються задачі багатоваріантного аналізу (оптимізація, статистичні та граничні випробовування тощо), обмежуються можливості аналітичних досліджень схемних функцій, їх точних обчислень тощо. Подальше розширення сфери використання чисельних методів вимагає зусиль, сумірних із затратами на дослідження та застосування СТМ. Тому з появою потужних обчислювальних засобів для теорії кіл актуально поновлення пошукових робіт у напрямку розроблення та засвоєння складніших символьно-топологічних і аналітичних методів, які краще надаються для моделювання згаданих задач. Додатковий аргумент актуальності проблеми - зростання кількості-доповідей з теми символьного аналізу на провідних західних симпозіумах.

СТУПІНЬ ДОСЛІДЖЕНОСТІ ТЕМАТИКИ символьно-топологічного аналізу визначається такими обмеженнями: відсутні дослідження можливостей застосування схемних функцій у частотній (по точках), часовій і комплексній площинах із врахуванням особливостей дискретних моделей і ненульових початкових умов; методи декомпозиції на підставі нарощування підсхем не забезпечують моделювання відносно великих і насичених кіл; не розв'язана задача застосування еквівалентного перетворення "зірка-багатокугник" для отримання коефіцієнтів ССФ; не розроблена ефективна методика порівняння та оцінення можливостей алгоритмів обчислення коефіцієнтів ССФ; в пакетах прикладних програм символьного моделювання переважають однометодні аналізні модулі; багатоваріантний частотний аналіз виконується дуже повільно тощо.

МЕТА РОБОТИ. Розвиток теорії лінійних електричних кіл шляхом розроблення методологічних засад та дослідження обчислювальних властивостей нових, об'єднаних у групу ПОЛІНОМНИХ, методів Д-ДЕРЕВ та ПОЛІНОМНОЇ РЕДУКЦІЇ, що розширює функ-ційні можливості аналізних модулів АСП аналогових кіл для їх багатоваріантного моделювання, аналітичних досліджень схемних функцій, точних обчислень тощо.

ОСНОВНІ ЗАВДАННЯ НАУКОВИХ ДОСЛІДЖЕНЬ. Для досягнення поставленої мети необхідно дослідити та розв'язати проблеми, перелічені вище при визначенні ступеня дослідженості тематики : застосування ССФ у частотній і часовій областях із урахуванням символьних незалежних джерел струму; порівняння методів аналізу лінійних кіл для їх класифікації та використання в АСП аналогових схем; збільшення складності модельованих схем за рахунок ієрархічної декомпозиції на підставі топологічних та матрицевих моделей підсхем тощо. ОБГРУНТУВАННЯ ТЕОРЕТИЧНОЇ ТА ПРАКТИЧНОЇ ВАРТОСТІ РОБОТИ. Запропонований підхід до визначення коефіцієнтів ССФ на підставі поліномних методів має певну теоретичну вартість для теорії лінійних електричних кіл: еквівалентне перетворення "зірка-багатокутник" для поліномних провідностей і незалежних джерел струму, теорія ієрархічної декомпозиції кіл тощо. В плані навчально-методичної роботи поліномні методи можуть послужити підставою для оновлення деяких розділів навчальних програм із курсів ТОЕ, ОЕ, ТОР, а також обчислювальної та прикладної математики в напрямку застосування елементів комп'ютерної алгебри. "Швидкі* ССФ дозволять емулювати процеси частотного та часового аналізу лінійних кіл у реальному часі. Це уможливить заміну невкладистих лабораторних макетів на мобільні програмні імітатори.

Поліномні методи мають практичне застосування в розробленні анапізних модулів АСП аналогових схем, які орієнтовані на моделювання багатоваріантних задач, аналітичні дослідження схемних функцій чи їх точне обчислення тощо.

НАУКОВА НОВИЗНА РОБОТИ полягає в розробленні нового науково-практичного напрямку символьного аналізу в теорії лінійних електричних кіл на засадах підходу, який об'єднує позитивні обчислювальні властивості матрицевих і топологічних методів аналізу, а також комп'ютерної алгебри. На захист виносяться такі нові методи та основні результати:

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

2 метод поліномної редукції, який ефективний для символьного аналізу аналогових кіл підвищеної складності (десятки та сотні вузлів);

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

4 засади теорії ієрархічної декомпозиції для аналізу великих схем, яка розроблена для методу д-дерев й адаптована для методу поліномної редукції;

5 символьні схемні функції, які, на відміну від подібних класичних схемних функцій, дозволяють моделювати лінійні або лінеаризовані (через застосування дискретних моделей) кола з символьними елементами в частотній (по точках), комплексній і часовій областях через урахування символьних джерел і нєнульових початкових умов;

6 об'єднання в рамках єдиного обчислювального процесу алгоритмів д-дерев, поліномної та неполіномної редукції, що дозволило підвищити точність та зменшити час частотного багатоваріантного аналізу кіл;

7 "обчислювальний" підхід до порівняння методів аналізу лінійних кіл згідно з якісною та кількісною оцінкою відгенерова-них кожним методом послідовностей арифметичних операцій для виконання заданих розрахунків;

8 адаптивна (гібридна, альтернативна) методика розв'язування систем лінійних алгебричних рівнянь (СПАР) за редукцією Гауса, яка підвищує точність обчислень за рахунок використання властивостей особливої матриці коефіцієнтів.

ІНФОРМАЦІЯ ПРО АПРОБАЦІЮ ТА ПУБЛІКАЦІЇ РЕЗУЛЬТАТІВ НАУКОВИХ ДОСЛІДЖЕНЬ. Основні результати наукових досліджень доповідались та обговорювались на конференціях і семінарах: т-ва ім. О.СПопова з радіоелектроніки (Київ, Львів, 1967-1978 pp.), автоматизації проектування й адаптації СЯСїСГ* ронних систем (Київ, 1969-1992), теоретичної електротехніки (Львів, Шацьк, 1976-1994), застосування системи "АНАЛІТИК" (Київ, 1988-1991), фізичної та біомедичної електроніки (Київ,

1993-1995), а також виступів на семінарах у Львові, Черкасах, Москві, Санкт-Петербурзі, Воронежі, Таганрозі, Ризі, Вільнюсі, Таллінні, Новосибірську та інших містах. Автор брав участь (заочно) у міжнародних симпозіумах і конференціях: Чехія (1971, 1974), США(1993,1994), виступав у Львові на конференції "Applied Modelling & Simulation" у 1993 р. Опубліковано 48 наукових праць автора, з них 5 авторських свідоцтв. ДЕКЛАРАЦІЯ ОСОБИСТОГО ВНЕСКУ АВТОРА. Основні дослідження були виконані в організованій автором групі машинного проектування СПКБ радіотехнічного факультету Державного

університету "Львівська політехніка" в період із 1971-го до 1982-го року. За цей час за символьно-топологічною тематикою було захищено низку дисертацій на здобуття вченого ступеня кандидата технічних наук, у підготовленні яких безпосередню участь брав автор. Навчальні варіанти програм моделювання, які виконувались на замовлення промисловості, використовувались у навчальному процесі на РТФ Львівської політехніки. В спільних роботах авторові належать: ідея, алгоритми та загальні методи розв'язку, аналіз результатів.

З 1983-го року робота виконується в плані популяризації поліномних методів аналізу електронних схем як в Україні, так і за кордоном у вільний від основної роботи час у НДІ телевізійної техніки АТ “Електрон" (мЛьвів).

МЕТОДИЧНЕ ЗАБЕЗПЕЧЕННЯ. У розробленні теоретичних положень дисертації використано методи теорії електричних кіл. Математичну основу досліджень складають теорія та методи матрицевої та комп'ютерної алгебри, чисельні методи й обчислювальна математика. Вживаються елементи теорії множин, теорії графів і топології.

ВПРОВАДЖЕННЯ НАУКОВИХ РОЗРОБОК. Інформацію у вигляді короткого змісту 16-ти актів, постанов, відгуків тощо про участь у конкурсі та використання наукових розробок у промисловості для моделювання електронних схем наведено в додатку до дисертації.

СТРУКТУРА ТА ОГЛЯД РОБОТИ Дисертаційна робота складається зі вступу, чотирьох розділів, додатку та літератури, викладених на 284-х сторінках. З них 248 сторінок -основний текст включно з 58-ма сторінками рисунків. 23 сторінки займає додаток. В переліку літератури наведено 224 джерела.

У ВСТУПІ визначено об'єкт, предмет, актуальність теми та проблематику дисертаційно? роботи. Обгрунтовано структуру роботи тощо.

У ПЕРШОМУ розділі на підставі аналізу обчислювальних особливостей та історії розвитку СГМ обгрунтувано актуальність і ділянку ефективного застосування поліномних методів у теорії кіл і проектуванні аналізних модулів АСП. Відзначено, що перші методи аналізу електричних кіл базувались на застосуванні аналітичних (символьних) дій із формулами, які пізніше використовувались для відповідних чисельних розрахунків.

Перші пропозиції використання топології кола для обчислення струмів і напруг у колі належать Юрхгофу, Максвелу та Фойснеру. Наведено приклад класичного мостового кола, для якого вираз для визначника матриці провідносгей у символьному вигляді після розкриття дужок містить 28 членів, з яких після скорочення подібних залишається лише аісілл членів (23-20=8). Привабливість топологічних методів полягає в можливості для нескладних кіл безпосередньо з рисунка (топології) схеми записати формулу схемної функції з мінімальною кількістю одночленів.

Перша хвиля зацікавлення СТМ розпочалась приблизно через 100 років після появи праці Кірхгофа. З тематики СТМ відомі праці Персіваля, Натана, Мезона, Майєда, Робішо, Буавера, Коутса, Ченя, Возняцького та Белерта, Ліна, Влаха й Сінгхала тощо. Доведено, що цікава для теорії кіл у історичному плані алгебра Ванга, яка являє собою підгрунтя популярного в свій час методу структурних чисел Возняцького-Белерта та джерелом широкомасштабних досліджень Ченя,

випливає з означення розробленого автором методу розширених структурних чисел.

Проте з часом вияснилось, що очікуваного істотного прогресу в розв'язанні задач аналізу лінійних кіл (поєднання високої точності та прискорення обчислень) не було досягнуто. Незважаючи на значні обсяги науково-дослідних робіт, СТМ не витримали змагань із простішими та добре формалізованими чисельними методами та реалізованими на їх підставі програмами моделювання навіть у частотному аналізі лінійних кіл. Разом з тим для наукових досліджень та виробництва актуальні задачі та кола, які або неможливо, або задорого моделювати чисельними методами, до яких, наприклад, належать задачі: багатоваріантне моделювання (оптимізація, статистичні та граничні випробовування), аналітичні дослідження (задача чутливості), точні обчислення схемних функцій тощо.

З цих причин за останні роки з'явилась нова хвиля зацікавлення символьними методами. Розроблені на Заході пакети символьних програм (ISAAC, SYNAP, SAPEC, ASAP, SSPICE, EASY, PCSNAP, SAUCES тощо) змагаються між собою та поширеними пакетами чисельного аналізу в сфері навчальних, наукових і професійних програм моделювання відносно простих аналогових схем. Прогрес у використанні символьних методів значною мірою спричинено застосуванням сучасних персональних комп'ютерів із відносно великою пам'яттю та швидкодією. Певні надії на підвищення ефективності символьних методів фахівці покладають на використання алгоритмів ієрархічної декомпозиції, які раніше (біля 20-ти років тому) вперше були розроблені та апробовані автором.

У першому розділі проаналізовано обчислювальні проблеми СТМ: складність комбінаторних символьно-топологічних алго-

ритмів для формалізації та програмування, експоненційний ріст процесорного часу (наприклад, пошуку дерев, шляхів чи контурів графа) від кількості вузлів схеми. Виявлено чутливість частотного аналізу до точності поліномних коефіцієнтів схемних функцій. Погана точність обчислення полягає в необхідності віднімання двох кривих, які подібні до ланцюжка, тісно туляться одна до одної та ординати яких різко змінюються з частотою. Наведено аналогію між обчисленням різниці ординат та вимірюванням різниці двох відрізків довжиною десятки кілометрів, які відрізняються між собою міліметрами. • •

Труднощі, які постали перед сучасними символьними програмами можуть спричинити повторну негативну оцінку можливостей символьно-топологічних методів. Тому метою дисертаційної роботи є доведення переваг СТМ, які забезпечать останнім належне місце в теорії кіл.

Розвиткові СТМ у Росії та Україні сприяли семінари на базі Львівського університету, організовані Г.Пуховим і М.Мак-симовичем. У дисертаційній роботі використано висліди наукових досліджень із матрицево-топологічної тематики, виконані в наукових школах Росії (В.Анісімов, П.Іонкін, М.Шакіров) і України (Б.Блажкевич, Ю.Величко, А.1ваницький, Ю.Калнібо-лотський, М.Максимович, Л.Нагорний, В.Сігорський, Я.Трохи-менко). -

В плані повторного зацікавлення СТМ відзначено роботи В.Філаретова (Росія) зі синтезу формул схемних функцій електричних кіл, а також зростання кількості доповідей із СТМ на престижних міжнародних симпозіумах з кіл і систем. Проаналізовано проблематику форуму "Насолоди, небезпеки та пастки символьного аналізу", який відбувся в Лондоні в травні

1994-го року в рамках міжнародного симпозіуму з кіл і систем

ІБСА5'94. На підставі ретроспективного аналізу історії розвитку символьних методів і дослідження ділянки їх ефективного використання реально сподіватися розширення сфери застосування поліномних методів у АСП і навчальному процесі.

Матеріал ДРУГОГО розділу покликаний обгрунтувати й пояснити моделі та методичні приклади для наступного порівняльного аналізу обчислювальних особливостей головних у дисертації методів д-дерев та поліномної редукції. На початку розділу подано головні означення, терміни та позначення. Зазначено, що методи аналізу кіл як складова частина теоретичної електротехніки розвивались не лише під впливом застосувань теорії електричних і електронних пристроїв, де основними розрахунковими величинами є струми та напруги, а також інших фізичних систем (механічних, теплотехнічних, гідравлічних тощо), де розраховують тиск, температуру, швидкість та інші електроаналогії. Прийнято, що додатні напрямки струму та напруги на двополюснику з додатньою провідністю взаємно протилежні, дуга-провідність у;] напрямлена від вершини у до вершини і, дерева "ростуть" з кореня тощо. Досліджувані в роботі поліноми залежать від багатьох символьних елементів уі,У2»»—.Уш. із двома показниками степеня: 0 або 1 (скорочено-біліноми). Тобто степінь біліному дорівнює т . Бтіном означено формулою:

' 2т-1 т

Р(у)=£ X; П уЬ|. ьі=0 або 1 , (1)

і=0 і=і ‘

де Хі-коефіцієнт одночлену, який може існувати в трьох видах: дійсне число, комплексне число та степеневий поліном (підполіном) від однієї змінної - р (комплексна частота); Ь| дорівнює ОДИНИЦІ, ЯКЩО елемент У] присутній в і-му одночлені, та ну-

лю - у протилежному випадку, і -індексний номер одночлену

(або номер комбінації символьних провідностей), який визна-

чається за правилом т-розрядного лічильника з двійковими розрядами Ь}. Головною задачею символьного аналізу є знаходження коефіцієнтів Хі, які залежать від величин числових елементів та вузлів під'єднаний символьних елементів.

У загальному випадку біліноми можуть містити символьні змінні у вигляді незалежних джерел струму , ТОДІ

г г 2т-1 т _

Р(Угі)= 2 .Ік РК(у)= 2 ^ Е Хкі П уЬІ, (2)

к=і к=1 і=0 і=1

Прийнято, що кожна провідність має знаменник. Так, провідність паралельно з'єднаних елементів має знаменник, що дорівнює одиниці, а послідовно - знаменник У(р_1Г+рС)+СГ, де У=1/І?, Г=1Д. Визначено ієрархічні моделі підсхем, ордерево, топологічні методи, які вживаються в теорії кіл, певні види деформацій графа, абревіатури тощо.

Вказано, що недоцільно окремо розглядати теорію генерації й обчислення класичних шести схемних функцій (СФ) та окремо -важливих для практики інших функцій і поліномів: вузлових потенціалів і їх різниць, часових характеристик за ненульових початкових умов, характеристичного поліному та поліномів, які застосовуються в методах д-дерев і поліномної редукції. Розширену СФ позначено терміном "символьна схемна функція-(ССФ). За структурою побудови поліномів класичні СФ -це степеневі поліноми з підполіномами у вигляді біліномів, а ССФ -навпаки, біліноми зі степеневими підполіномами від р.

ССФ вживаються для трьох видів аналізу електричних кіл: частотний аналіз на фіксованих частотах, обчислення поліномів від комплексної частоти та часовий аналіз , який викорис-

товується для моделювання нелінійних аналогових кіл. У дисертації переважають дослідження ССФ на фіксованих частотах та використання провідностей у канонічному базисі методу вузлових потенціалів. ■

ССФ надаються для аналізу кіл з операторними та дискретними моделями, які можуть містити некеровані поліномні джерела струму. Останні "вписуються" в формулу ССФ на підставі правила Крамера. Досліджено два способи обчислення коефіцієнтів ССФ: послідовний і паралельний. Показано, що паралельне обчислення коефіцієнтів на підставі поліномних методів містить для загального випадку меншу кількість арифметичних операцій. Серед послідовних способів вказано на алгоритмічну простоту та ефективність правила Фойснера розкладання за вітками.

Досліджено сферу ефективного застосування ССФ. З'ясовано, що методи, які використовують ССФ у поширених на практиці випадках мають перевагу перед традиційними чисельними методами в частотному багатоваріантному аналізі кіл. Показано, що для випадку обмеженої кількості символьних провідностей (до 10-ти) має місце прискорення розрахунків частотних точок, яке для 1-го символьного елемента досягає наближено 6-ти разів (скорочено: 1 с-бр), 2с-13р, Зс-17р, 4с-17р, 5с-15р, 6с-13р, 7с-10р, 8с-7р, 9с-5р, ІОс-Зр, 12-1р. При порівнянні враховано особливості розташування символьних елементів (найбільше прискорення є у випадку, коли вони не мають спільних вузлів), дії з комплексними числами та можливість найсучасніших, орієнтованих на багатоваріантний аналіз, процедур Ґауса виконувати попередню локалізацію символьних елементів у правому нижньому куті матриці коефіцієнтів. Чим більша кількість варіантів частотних характе-

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

Показано, що часто для моделювання кіл із нерегулярними для методу вузлових напруг джерелами простішими з погляду програмування на комп'ютерах і придатними для використання в поліномних методах є способи прямого формування матриці провідностей активних кіл у порівнянні з поширеними методами, які використовують додаткові рівняння, матриці інциденції або паря графів. Важливо відзначити, що описана методика моделювання нерегулярних джерел дозволяє враховувати нескінченні провідності при викресленні певних рядків матриці

ч провідностей.

Досліджено обчислювальні властивості різних алгоритмів отримання коефіцієнтів ССФ через аналітичні обчислення важливих для аналізу несиметричних алгебричних доповнень. Встановлено, що ефективним алгоритмом пошуку цих доповнень є один із алгоритмів Б.Блажкевича, побудований на перенесенні кореневої вершини графа кола. Доведено поширення алгоритму Мезона розкладання неорієнтованого графа за вузлом на розкладання за вершиною для орграфа, що дозволило застосувати вказане розкладання в поліномних методах. Дос-

ліджено обчислювальні властивості алгоритмів розкладання графа за ребром (Фойснер) та за дугою (А.Воробкевич}.

Запропоновано "обчислювальну" методику порівняння алгоритмів і методів обчислення ССФ на підставі якісного та кількісного аналізу кінцевого продукту: відгенерованої певним алгоритмом або методом формули обчислення аналізованої функції. На прикладі класичного мостового кола отримано та порівняно сім різних алгоритмів обчислення характеристичного поліному. Підкреслено важливість застосування критерію віднімання для оцінення обчислювальних властивостей методів. Згідно даного критерію перевагу в обчисленні коефіцієнтів ССФ має алгоритм, який не вживає операції віднімання, або вибирає з двох варіантів віднімання той, що має меншу втрату значущих розрядів після нормалізації. "Обчислювальний" підхід, досліджений на прикладі генерації коефіцієнтів ССФ, дозволяє впорядкувати алгоритми теорії кіл з погляду їх застосування в аналізних модулях АСП аналогових схем.

У ТРЕТЬОМУ розділі досліджено поліномний топологічний декомпозиційний метод д-дерев. Уведено поняття д-дерева орграфа, як такого к-дерева (к=д>0), в якого дуги, що входять до некореневих вершин, виходять лише з кореневих. На відміну від к-дерев для д-дерева поняття ваги як добутку ваг його ребер (дуг) не має змісту. Д-дерево як граф відображає визначену Персівалем суму певних к-дерев. У загальному випадку кількість к-дерев графа більша від кількості його д-дерев, тому додавання поліномів к-дерев у одному поліномі д-дерева є джерелом економії арифметичних операцій під час деком-позиції кола. В рамках даної роботи використано виключно орієнтовані к- та д- дерева, тому термін "к-(д-)дерево" означає к-(д-) ордерево. Доцільність уведення образа д-дерева пояс-

нено істотним спрощенням алгоритмів декомпозиції кіл, що дозволило вперше топологічним методом отримати коефіцієнти ССФ для схем із десятками вузлами.

Розроблено алгоритм перелічення д-дерев шляхом побудови трьох циклів у циклах. Наведено таблицю залежності кількості д-дерев від кількості полюсів плавучої та укоріненої лідсхем. З таблиці видко, що кількість д-дерев збільшується в 3-8 разів на кожний.полюс і для укоріненого семиполюсника складає 3100 д-дерев. Відносно велика кількість д-дерев підсхеми є платою за точність обчислення коефіцієнтів ССФ, яка полягає у відсутності ділення та віднімання поліномів (віднімання чисел можливе для від'ємних провідностей).

За аналогією з к-деревом, д-дерево позначено згідно з дефініцією Персіваля. Запропоновано для спрощення кодування д-дерева не позначати групи з однієї вершини. Наприклад, деяке Зд-дерево £іі;23;4 можна позначити простіше:СІ23. Кожне д-

дерево позначається трьома записами: структура у вигляді символу сі із вищевказаним кодом Персіваля (наприклад,сІ2з),

машинний код топологічного образа д-дерева (наприклад, запис ±±2± означає вище на ведене Зд-дерево, у якого 1-й, 2-й і 4-й полюси укорінені, а до 3-го полюса дуга входить із 2-го) та адреса поліному даного д-дерева або його порядковий номер (наприклад, а23 означає 23-й поліном або 23-тє д-дерево підсхеми А). На рис.1 для підсхеми А в лівому стовпчику наведено машинні коди д-дерев та їх порядкові номери (після літери а). Розроблено методику переходу від коду д-дерева до його порядкового номера. Дана процедура застосовується під час злучення підсхем і складається з двох кроків: готування базових констант й обчислення зміщення. Кожна під-схема в пам'яті комп'ютера відображається у вигляді впоряд-

104 поліноми <2> після

підсхемаі

д-дерева: *

444і- = аі

33^3 зк а 2

33-^ аЗ

34±і. а4

43^ - а5

44-Ьі. г аб

2±22 а а7

2Х2А = а8

2<МА з а9

5 аЮ

4і4Х = аіі

2-и*2 = а!2

2*^3 = аІЗ

г а14

£ аі5

2і-и. г аіб

3^ = а17

4-Ш. = а18

■чи = а19

-чи = а20

*14± = а21

*Ц Iі- а а22

= а23

■ч-ч = а24

■4*3 в а25

■*•>4 = а26

*3±3 = а27

і*и. = а28

±3±± с а29

= аЗО

^41 аЗІ

АЧ2 = а32

г аЗЗ

■^22 £ а34

хх\х г а35

Х±2± с а36

ліфі. а а37

ххі.! = а38

= а39

хіі.3 ~ а40

їм» -лрог-рамния г/гіп а41 да- мер

злученая

&

:іЦ АВв' Н:

23 поліноми <2>

номери поліномів д-дерєв підсхеми В

іі*іііііі ни.

типи ті

* м„и ніш

ii.ii.li

и.л іти

м.м , ІММІ

.іііііші іш ті...,.,. і

II.. II пиши... НІНІ ІІІІ.

М.І.І ІММІ И..И.. шиті... імі.н т.. НІНІ ті.

М.І.І ...НІМІ Л..ІІ... ....шини.... ІММІ N1.. нин ІІІІ

.М.І.І .11.11.11 II. .11 ІШИМІ ІММІ НІ ІІІІІІ ті

.М.І.І II.II.II | ІНШІЇ ІММІ III .,, , НІІІІІ ІІІІІІІІІ

І ІІІІІІІІ НІІІН ІІІІІІІІІ

ІНШІ . . . . ІІІІІІІІІ

ІІІІ 1

ІІІІІІІІІ.... ІІІІ.

ІММІ III..

МІ.ІМ.... їм.

І..І..І II...

ІІІІІІІІІ ІІІІ

ІММІ.. III

МММ ....їм

І..І..І II

ІІІІІІІІ ІІІІІІІІІ

II. II НІШ

М.І.І „ІММІ

ІІІІІІІІІ ІІІІ ІІІІ 1

ІММІ ІІІІ МММ ІІІІ III 1

11.1 1

II 1

ІІІІІІІІ ІІІІІІІІІ.... ініііін ..ті.

II.II ІІІІІІІІІ..., ніш ті.

М.І.І ІММІ .ІІІІІІІІ... ІІІІІІІІІ іммі т.. инти ті

,11. .11 ІІІІІІІІІ .......іній..-. ті

.М.І.І ІММІ і ; итііі ІММІ III ІНШІ ІІІІІіиі

йод

поліному

■ означає добуток двох поліномів. Загальне кількість добутків =670,

Номер агдерева після злуки І 2 3 * 5 і 1 1 9 10 И п ІЗ Н 1$ и І? 1) 19 20 21 22 23

Кількість множень д~дерев 78 ІЗ (і и Іі <9 11 10 3$ И 10 35 31 25 15 39 26 10 36 3? 35 35 3$

Приклад множень: А =А1=а1(Ь44+Ь45+...+Ь52)+а2(Ь35+Ь36+...+Ь43)+ +<«Э+а5)(Ь27+Ь28+Ь31+ЬЭ2)+(а4+а6НЬ27+Ь29+Ь31+ЬЗЗ)+а7(Ы8+М9+. ..+Ь26)+

+ (&8+а10ИЬ1О+М1+Ь14+Ь15)+(а9+а11)(М0+Ь12+М4+Ь16)+(а12+а14)(Ь2+ЬЗ+Ьб+Ь7)+ + (аїЗ+а15НЬ2+Ь4+Ь6+Ь8)+М(а16+а17+а18). (10 множень замість 78) !

Рис-І ГтіуціЕТуда мятпиці-м.ип-»р.иі> пгтіипиіи п-ррцра двох підсхеи з кодом з луки 4 ,+4,3.3

кованих адрес поліномів д-дерев. Повний набір д-дерев підсхеми утворює її Д-модель. Пояснено формули, які визначають кількість д-дерев Д-моделей плавучих та укорінених підсхем.

У роботі досліджено взаємно-однозначну відповідність між мінорами матриці провідностей та д-деревами. Відзначено, що спосіб обчислення д-дерев типу сі;])* без віднімання мінорів на сьогодні не розроблено. Показано можливість через д-дерева визначати деякі детермінанти та алгебричні доповнення не-особливої матриці провідностей кола, що необхідно для проведення прецизійних обчислень.

Пояснено вживання терміну "декомпозиція", який у межах дисертації означає не'лише розбиття копа на підсхеми (або графа на підграфи), але й їх злучення, чому в роботі приділено головну увагу. Розроблено підстави теорії ієрархічної декомпо-зиції кіл. Встановлено, що для декомпозиції кіл достатньо розробити наступні моделі та методики: Д-модель підсхеми як множину д-дерев; методика перелічення д-дерев підсхеми; методика виявлення дозволеного добутку поліномів д-дерев підсхем; методика ідентифікації д-дерев для групування поліномів підсхем; методика злучення д-дерев та підсхем; методика генерації оптимізованих формул множення поліномів підсхем; методика вибору підсхем для оптимізації процесу декомпозиції.

Розроблено алгебру злуки вершин д-дерев двох підсхем, у якій використано чотири типи полюсів графа підсхеми: неко-реневі, локальні кореневі, глобальні кореневі та порожні (заборонені). Введено поняття сумісності злучуваних полюсів. Застосування вказаної алгебри дозволяє прискорити процесорний час злучення д-дерев за рахунок застосування спрощеного попереднього перевіряння злучених д-дерев на відповідність к-дереву. Більш трудомістка процедура ідєнтифі-

кації к-дерева та утворення з нього д-дерева виконується тільки після позитивного наслідку попереднього перевіряння. Для перевіряння злученої пари д-дерев на відповідність к-дереву використовуються алгоритми методу розширених структурних чисел.

Запропоновано спосіб кодування злуки двох підсхем А та В на підставі чотирьох чисел: загальна кількість полюсів підсхеми А; загальна кількість полюсів підсхеми В; кількість зовнішніх полюсів, до яких під'єднані підсхеми А та В; кількість спільних полюсів А та В (зовнішніх та/або внутрішніх). На підставі вказаного кодування полюсів перелічено коди усіх варіантів злуки двох підсхем, що мають від одного до шести полюсів (крім кореневого). Обчислено, що кількість варіантів злуки для таких підсхем складає 138.

Виявлено, що пари перемножуваних поліномів двох підсхем при їх відображенні на площині порядкових номерів (адрес) усіх поліномів першої та другої підсхем під час їх злучення утворюють специфічні блочні структури (рис.1). Цю властивість використано для оптимізації кількості множень поліномів д-дерев. Застосування готових формул множення для всіх варіантів злучення підсхем складає підставу методики обчислення коефіцієнтів ССФ, яка не використовує алгоритми пошуку дерев, к-дерев та д-дерев. Вказана ідея дозволила спростити програму декомпозиції, а також зменшити час генерації формули обчислення коефіцієнтів ССФ у 2-5 разів. Показано можливість об'єднання в одному обчислювальному процесі чисельного (метод Гауса) та символьного (метод д-дерев) методів для аналізу схем у частотній області, що дозволяє підвищити ефективність відгенерованих формул.

На рис.1 пояснено деякі особливості злучення д-дерев на прикладі 4-полюсноТ плавучої (А) та п'ятиполюсної укоріненої (В) підсхем. Об'єднана підсхема -укорінений триполюсник. Даний варіант злуки однозначно визначається кодом злуки

4,+4,3,3, де + означає наявність у підсхемі В глобального кореня. Цифри всередині пісдхем означають номери полюсів підсхем, адаптованих до даного коду злуки. Програмні коди д-дерев упорядковані в порядку їх зростання при умові, що код локального полюса' (і) має домінуючу вагу, тобто 444±<33±3 <іііі Прямокугнички (і) вказують на пари д-дерев підсхем А та В, які є сумісними, тобто поліноми цих д-дерев підлягають перемноженню. На рис.1 наведено приклад формули для вис-лідного А1 з кодом 000, тобто формули визначника. Внаслідок застосування описаного в дисертації алгоритму замість 78 множень поліномів достатньо виконати лише 10. Корисно звернути увагу, що внаслідок злуки двох даних підсхем кількість поліномів зменшилась майже в шість разів: (41+104}/23/ хоча середня довжина поліномів у загальному випадку дещо збільшується.

Програмування та дослідження обчислювальних властивостей методу д-дерев виконали Ю.Шаповалов, М.Ястребов та Л.Березко. Наведені дані про тестування методу д-дерев, які підтверджують відносну точність обчислення коефіцієнтів ССФ великих розріджених схем. Наведено приклад схеми на 76 вузлів, для якої обчислено поліномні коефіцієнти біліномів, що заперечує висновки (Лін,Гассон) ніби коефіцієнти ССФ практично можна обчислити для схем до 50-ти вузлів. Методика ієрархічної декомпозиції на підставі топологічного методу д-дерев [8] на 12 років випередила публікацію аналогічного

топологічного методу Старжика (США) та Сліви (Польща) в престижному часописі ІЕЕЕ.

ЧЕТВЕРТИЙ розділ презентує новий підхід до символьного аналізу електричних кіл на підставі нетопологічного методу поліномної редукції (МПР). МПР базується на розв'язаній автором задачі еквівалентного перетворення 'зірка-багатокутник” для поліномних прозідносгей та незалежних джерел струму. Структурно розділ побудований на переході від формул простішого прототипу -методу класичної чисельної редукції вузлів до складніших поліномних формул. Показано, що класичні формули виключення Гауса можна отримати з фізичних міркувань, використовуючи закон Ома та принцип суперпозиції. Переваги чисельної версії методу редукції вузлів досліджували Розен, Вінгхем, Мезон, Капахан, В.Говорков, В.Скугарев, М.Подольський, Ю.Саноцький, ЕЛаксберг та інші. Полїномні формули редукції дозволили розширити сферу дії методу редукції на комплексну та часову область з можливістю виділення символьних елементів.

На підставі аналізу обчислювальних схем методу редукції та прямого ходу Ґауса для розв'язування СПАР створено адаптивний (або альтернативний, гібридний) спосіб реалізації прямого ходу Ґауса. Суть нового підходу полягає у використанні надлишкової інформації, яку містить додатковий (контрольний) стовпець особливої матриці провідностей кола. Завдяки цьому діагональний або один із недіагональних елементів матриці можна обчислювати двома способами: через формулу Ґауса або через суму решти провідностей рядка. Вибір формули можна здійснювати на підставі критерію віднімання. Якщо операції віднімання неможливо уникнути- перевагу віддаємо відніманню чисел із більшим розкидом порядків.

Альтернативний підхід дозволяє підвищити точність аналізу пасивних і активних схем.

Наведено методичний приклад формул визначення передатної функції транзисторного підсилювача, матриця провідностей якого містить від'ємну провідність. Порівнюються три алгоритми обчислень: класичним виключенням Ґауса, чисельною редукцією та запропонованим адаптивним методом. Порівняння показали, що перші два алгоритми застосовують у різних місцях операцію віднімання, тоді як на підставі адаптивного підходу вперше такого типу завдання розв'язано без використання операції віднімання чисел. Показано, що платою за підвищення точності обчислень є ускладнення програми та використання додаткової пам'яті для контрольного стовпця матриці провідностей (у матрицевих процедурах) або додаткове обчислення власних провідностей редукованого вузла (в графному підході). Наведено формули визначення кількості достовірних розрядів мантиси в результаті виконання арифметичних дій за формулою Ґауса. Описана адаптивна методика може бути застосспана е обчислювальній математиці для підвищення точності розв'язку СЛАР.

На підставі чисельної вузлової редукції, визначення провідностей у вигляді відношення двох поліномів і аналогії з д-деревами наведено спрощений спосіб доведення умов ділення поліномів без остачі. Робочі формули поліномної редукції (рис.2) подібні до цілочисельних формул Беррейса точного виключення Ґауса, які застосовуються в комп'ютерній алгебрі. Досліджено особливість обчислення нових елементів розрідженої поліномної матриці в процесі редукції та встановлено, що можна заздалегідь визначити поліноми, які пізніше взаємно скорочуються, що дозволяє підвищити якість поліномних обчис-

У<і>= ^

Jr.UA,

ч

(і) ,(к) у'Л> = 1ІІ. ; /.*» = -і- ; 1^ у<к> 1 у<к>

ФОРМУЛІИГ ПрЯМОГ'О ходу

п-кількість вузлів кола

і=1,п; п+1«0;

Уя*і=0

V - ^ ' Е *5,і‘'п -д ) /у<і> %«І4 1

Уі • А Д

Рис.2 Формули поліаомної редукції та схема їх використання

лень. Задачу виключення непродуктивних множень та ділень розв’язано шляхом перечисления та дослідження всіх п'яти ситуацій, які можуть виникати в процесі редукції вузлів. На підставі аналізу цих ситуацій складено чотири правила утворення оптимізованих за кількістю множень та ділень поліномів формул для редукції розріджених схем. Вказані формули виконуються після нескладного визначення коду ситуації. Наслідком ' досліджень є можливість підвищення точності обчислень і зменшення процесорного часу поліномної редукції.

На рис.2 наведено формули та методичний приклад схеми обчислень за методом поліномної редукції. Знаменники усіх провідностей на к-му кроці редукції визначаються додаванням чисельників провідностей, утворених на к-1-му кроці. Головну частку процесу поліномної редукції займає обчислення чисельників провідностей. Корисно звернути увагу на властивість ділення цілих чисел без остачі (ділення на 10 під час редукції вузла 2), а також на абсолютну точність обчислення чисельників провідностей, струмів і вузлових потенціалів. Дана властивість для прикладів із цілочисельними операндами є важливим аргументом на користь застосування МПР у навчальному процесі під час виконання розрахункових робіт із самоконтролем для курсів ОЕ, ТОЕ, ТОР.

Уведена автором поліномна модель (П-модель) підсхеми відрізняється від відомої У-моделі підсхеми, яка вживається в методі неполіномної редукції вузлів наявністю знаменника, спільного для всіх провідностей. Знаменник обчислюється або як визначник матриці провідностей даної підсхеми, в якій викреслено рядки та стовпчики, що відповідають полюсам підсхеми, або як сума дерев графа підсхеми, в якого полюсні вершини злучені між собою та коренем. Зазначено, що алгоритми ієрархічної

декомпозиції на підставі Д-моделі підсхеми, досліджені в третьому розділі, можна використати для побудови алгоритмів ■ієрархічної декомпозиції на базі П-моделі підсхеми. Порівнюються обчислювальні особливості ієрархічної декомпозиції на підставі У-, Д- та П-моделей і можливості їх альтернативного використання в процесі обчислення коефіцієнтів ССФ, що поєднує позитивні властивості різних методів за точностю та часом обчислень.

Проаналізовано тестові приклади з погляду точності обчислення коефіцієнтів ССФ та довжини відгенерованих кодів формули даного обчислення. Для тестування вибрано схему кварцового фільтра та популярну на Заході схему активного фільтра на 11-ти операційних підсилювачах. Обчислювальні експерименти зі схемою кварцового фільтра показали наявність проблеми зростання кількості шумових розрядів у процесі ділення поліномів, що може викликати появу відомих у полі-номній арифметиці "зайвих" поліномних коефіцієнтів. Для зменшення похибки від ділення запропоновано використати над-лишковість особливої матриці провідностей, а також алгоритм ділення поліномів без остачі послідовно зліва та справа.

Обчислювальні експерименти показали, що для отримання прецизійних коефіцієнтів ССФ перевагу мають "дорожчі" з погляду програмування та витрат процесорного часу методи д-дерев і розширених структурних чисел, якщо вони не обмежені складністю схеми. Дослідження формули передатної функції активного фільтра показує, що “поліномну" формулу доцільно застосовувати при багатоваріантному аналізі, якщо є необхідність завдання довільних символьних елементів. Порівняння цієї формули з "чисельною", отриманою Ліном та Гассоном, показує, що МПР має перевагу при моделюванні активних

фільтрів із неідеальними операційними підсилювачами. Для визначення довжини обчислювальної формули відгенеровано послідовність операцій (формула) для визначення коефіцієнтів ССФ вищезгаданого активного фільтра. Даний приклад показує, що алгоритми МПР простіші від алгоритмів МДД, а сама формула може служити тестом для відпагодження процедур генерації формул ССФ. Вказано на методику обертання поліномної матриці на підставі використання символьних джерел струму.

На закінчення розділу виконано ескізний опис методики вибору (адаптації) алгоритмів і моделей у процесі аналізу, що є базою для реалізації концепції багатометодної програмної системи моделювання аналогових електричних кіл. Описані функції Супервізора Методів. Вхідні дані для активізації методу -це: кількість вузлів та насиченість схеми, вид аналізу (наприклад, обчислення усталеного режиму або частотної характеристики тощо), кількість символьних елементів, вимоги до точності аналізу (у т.ч. на підставі аналізу зумовленості матриці провідносгей) тощо. Наведено оцінний графік залежності споживання головних ресурсів комп'ютера (процесорний час і пам'ять) на генерацію й обчислення біліномів ССФ у залежності від кількості вузлів схеми при середній насиченості структури кола (відсутні вузли, до яких під'єднано більше шести елементів). До 10-ти вузлів найкращі "комп'ютерні" показники має метод розширених структурних чисел, від 10-ти до 100 вузлів перевагу має метод д-дерев, від 100 до 200 вузлів -метод поліномної редукції, а для більших схем - класичний метод Ґауса, орієнтований на багатоваріантний аналіз. При цьому МПР повністю перекриває можливості методу д-дерев щодо складності кола, але програє у випадку аналізу високодобротних схем, для яких вимагається підвищена точність

розрахунків (наприклад, коефіцієнтів схемних функцій у комплексній площині). Зауважено, що в процесі редукції кількість вузлів схеми зменшується, що уможливлює перехід на економніші заздалегідь запрограмовані формули (В.Філаретов) для обчислення визначників. Таким чином реалізується ідея адаптації методів у процесі генерації формупи ССФ. У загальному випадку доцільність застосування поліномів від комплексної частоти визначається кількістю частотних точок: чим більша кількість точок, тим доцільніше застосовувати поліноми за умови, що їх обчислення не вимагає істотного збільшення точності розрахунку.

В ДОДАТОК винесено матеріал, який доповнює основний, зміст дисертації. Поміщено короткі витяги з довідок: про третю премію у Всесоюзному конкурсі програм машинного проектування за 1970-й рік, про впровадження наукових розробок автора у НД! та КБ, починаючи з 1969-го і закінчуючи 1995-м роком у містах: Коврово, Львів, Нижній Новгород, Москва, Київ) у вигляді програм АСП лінійних електроних схем. Наведено копію першої сторінки форуму про символьний аналіз, про який мова ведеться у першому розділі тощо. Доведено теорему про коефіцієнти біліномів, наведено трасу обчислень при обертанні поліномної матриці п'ятого порядку, приклади та пояснення ділення поліномів без остачі тощо.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ Розроблено методологічні підстави та досліджено новий науково-практичний напрямок у теорії кіл -поліномні методи символьного аналізу аналогових електричних кіл, які поєднують корисні обчислювальні властивості матрицевих, топологічних та аналітичних алгоритмів, сумарна ефективність яких вища в порівнянні з' поширеними чисельними методами для випадку

моделювання багатоваріантних задач (оптимізація, граничні випробовування, імітація поведінки кіл у реальному часі тощо), виконання аналітичних досліджень схемних функцій (задачі чутливості, апроксимації схемних формул, точних обчислень тощо). При цьому отримано такі головні висліди:

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

2. Розроблено та досліджено новий метод поліномної редукції для аналізу лінійних електричних кіл, який на підставі розв'язаної автором задачі еквівалентного перетворення зірка-багатокутник для поліномних провідностей та джерел струму, уведення ієрархічної П-моделі підсхеми дозволяє швидше та достатньо точно за рахунок властивості ділення поліномів без остачі обчислювати коефіцієнти біліномів ССФ кіл на сотні елементів (у випадку моделювання в комплексній області) та сотні вузлів (у випадку моделювання в частотній і часовій області ).

3. Розроблено та досліджено новий метод д-дерев для аналізу лінійних кїл, який на підставі уведення образу д-дерева та ієрархічної д-моделі підсхеми дозволяє розв'язати проблему топологічного аналізу великих (до сотні вузлів) кіл, а також підвищити точність обчислення біліномів ССФ за рахунок властивості невикористання процедур віднімання та ділення поліномів.

4. Розроблено засади теорії ієрархічної декомпозиції кіл на прикладі методики злучення д-дерев та П-моделей підсхем.

Викорисгання бібліотеки завчасно підготовлених оптимізованих багатодужкових формул злучення підсхем дозволило в декілька разів прискорити обчислення коефіцієнтів біліномів ССФ та уникнути необхідності застосування процедур пошуку й злучення дерев у аналізних програмах .

5. З'ясовано, що коефіцієнти біліномів ССФ, які раніше являли собою виключно степеневі поліноми від комплексної частоти, доцільно представити у вигляді комплексних та дійсних чисел, що уможливлює багатоваріантний частотний аналіз лінійних кіл та часовий аналіз лінеаризованих кіл через використання дискретних моделей реактивних елементів {провідність і джерело). Урахування джерел дозволяє також моделювати лінійні кола в часі з ненульовими початковими умовами через використання операторних засгупних схем.

6. Об'єднано в рамках єдиного обчислювального процесу позитивні властивості алгоритмів д-дерев, числової та поліномної вузлових редукцій, що дозволяє за рахунок розроблення керуючої програми підвищити точність і зменшити час частотного багатоваріантного аналізу електричних кіл.

7. Запропоновано нову для теорії кіл "обчислювальну" методику порівняння та групування (класифікації) методів на підставі якісного та кількісного аналізу послідовностей арифметичних операцій із операндами (формул), які генеруються кожним методом. Вказана концепція дозволяє впорядкувати алгоритми методи теорії кіл з погляду їх застосування в аналізних модулях АСП аналогових схем і досліджена на прикладі генерації коефіцієнтів біліномів ССС.

8. Запропоновано та досліджено адаптивну методику розв'язування СЛАР за методом Ґауса, яка дозволяє підвищити точність обчислень за рахунок використання надлишковості

особливої матриці коефіцієнтів та критерію віднімання (з двох тотожніх способів обчислення елемента виключення (за формулою Гауса чи додавання елементів стрічки) вибираємо той, що забезпечує меншу похибку).

ПЕРЕЛІК ОСНОВНИХ ПРАЦЬ АВТОРА

1. Дмитришин Р. Оптимизация электронных схем на ЭВМ.-Киев: Техника, 1980.-222 с.

2. Дмитришин Р. Нахождение детерминанта матрицы с использованием графов //Радиоэлектроника.-Киев, 1968.- том XI, №11.-с.1239-1241.

3. Дмитришин Р. Расчёт линейных цепей методом расширенных структурных чисел //Радиоэлектроника.-Киев.-1969, том XII,№8.-с.806-813.

4. Дмитришин Р. Оптимальные алгоритмы аналитического решения некоторых определителей на ЭЦВМ //Труды симпозиума "Вопросы точности и эффективности вычислительных алгоритмов".- Киев, 1969.- с.39-46.

5. Дмитришин Р. Программа для анализа на ЭЦВМ линейных цепей символическим методом //Сб. "Автомат, проектир. радиоэлектроцепей”, КиТв:Техника, № 5, 1972.- с.14-19.

6. Дмитришин Р., Акулич Г. Алгоритм и программа для определения функции и её производной при оптимизации сложных линейных цепей //Сб."Автомат, проектир. в электронике", Киев: Техника,№ 12, 1975.-С.39-41. (розроблення та опис алгоритму, )

7. Дмитришин Р. Алгоритм и программа раскрытия детерминанта по определению на ЭВМ //Сб. "Автомат, проектир. в электронике”, Киев, № 13, 1977,- с.27-30.

8. Дмитришин Р., Шаповалов Ю. Об одном алгоритме определения параметров линейных радиосхем на ЭВМ /Др. симпозиума "Современные методы и аппаратура для измерения параметров радиотехнических цепей", Новосибирск, СНИИМ, 1973.- с.30-33. {опис д-дерево, ідея та технологія програмування методу д-дерев, участь у тестуванні програми, написаної співавтором)

9. Дмитришин Р. Алгоритмы символического определения схемных функций линейных цепей на ЭВМ (метод расширенных структурных чисел и его реализация на ЭВМ ):Дис....канд.техн.наук. Львов, 1972.

-32-

10. Дмитришин Р., Соноцький Ю., Подольський М- Машинная оптимизация допусков на элементы электронных схем // "Автоматизация проектирования е электрони>се".-Киев:Техника.1 978, вип. 17.-С.65-69. (ідея отимізації допусків, вибір то обговорення тестів)

11. Дмитришин Р., Шаповалов Ю- Вычисление схемных функций при многовсриантном анализе схем //Радиаэлектроника:Киев, том XXI, № 6, 1978.- сЛ 51 -153. (ідея багатоваріантного аналізу на основі ПБЧВ, вибір то обговорення тестів)

12. Дмитришин Р., Троцюк А. Алгоритм компактного обчислений детермінанта графа // Вісн. Львів, політехн. ін-ту, № 161. Теорія і проектування напівпровідникових і радіоелектронних пристроїв і систем". Львів, Вища школа, Видво при Львів, ун-ті, 1982, с.49-50. (ідея алгоритму, написання статті)

13. Дмитришин Р. Алгоритм обчислення визначника дігрофа схеми методом топологічної редукції //ВіснЛьвів.полггехн.ін-ту, № 161. "Теорія і проектування напівпровідникових і радіоелектронних пристроїв і систем". Львів, Вища школа, Вид-во при Львів, ун-ті, 1982.-С.50-53.

14. Дмитришин Р., Подольський М. Генерация частотных схемных функций на основе сворачивания смешанных мультиграфов электронных схем //Радиоэлектроника:Киев,том ХХУ, №6, 1982.-c.4-8. (подано ідею генерації кодів)

15. Дмитришин Р. Генерация формулы характеристического уравнения для многовариантного анализа схем //Родиоэлектро-ника:Киев, том ХХУ, N6, 1982. -с.89-91.

16. Дмитришин Р. Диграфная модель несиметричных алгебраических дополнений матрицы проводимостей электронных схем /Део-рет. электротехникаЛьвов, вып.36. -1984.- с.6-8.

17. Дмитришин Р. Формульный метод оценки эффективности алгоритмов и программ анализирующих модулей САПР /Друды Всесоюзного семинара "Автоматизация проектирования электротехнических устройств и систем", Москва, ВЗПІ.-С.39-42.

18. Дмитришин Р. Генерация схемных функций методом буквеннополиномиальной чредукции //Электронное моделирование, Киев, 1985, том 7, №1.-с.36-40.

19. Дмитришин Р., Дерябина А. Сравнение алгоритмов вычисления буквенно-полиномиальных схемных функций /Деорет. электротехникаЛьвов,вып.39,1985.-с.5-9. (подана ідея порівняння, викона-ний аналіз обчислень прикладу за методом поліномної редукції).

-33-

20. Дмитришин Р. Анализ точности вычислений при моделировании схем // Вопросы радиоэлектроники, Серия ОВР, Вып. 13,М., ИИИЭИ: i991.-c.3-6.

21. Дмитришин Р. Сверхбыстрый алгоритм генерации деревьев графа //Тезисы докладов межведомственной научно-произв.конф. "Развитие и совершенствование телевизионной техники", Львов, 1991.С.93-94.

22. Дмитришин Р.В. Генерація оптимізованих формул множення поліномів д-дерев, 36. доповідей Міжнародної науково-технічної конференції "Проблеми фізичної та біомедичної електроніки" 18-20 травня, Київ,КПІ, 1995 р.,с.25-28.

23. Дмитришин Р. Метод расширенных структурных чисел и ею реализация на ЭВМ, Proceedings of the Summer Schyool on Network Theory, Institute of Radio Enginering and Electronics Czechoslovak Academy of Sciences, Praha, 1971, pp.24-30.

24. Дмитришин P. Анализ и оптимизация на ЦВМ линейных цепей символическими методами. Proceed, of the Summer School on Network Theory, Institute of Radio Engineering and Electronics Czechoslovak Academy of Sciences, Praha, 1974.

25. Dmyfryshyn R., The Use of Symbolic-Numerical Methods for Electronic Circuit Analysis, Proc. of ISCAS'93, Chicago, 1993. pp. 1655-1657.

26. Dmytryshyn R. Polynomial Reduction Method - Solving the Problem of Polyvariant Simulation of Electronic Circuits, Proc.intern. AMSE Conference, Lviv, Sepf-Ocf 1993, pp.11-18.

27. Dmyfryshyn R. Polynomial Reduction Method, Proc. of 37th Midwest Symposium on Circuits and Systems, Lafayette, USA, August 1994, pp.1311-1314.

28. A.c. 255647 СССР. Устройство для перебора сомножителей

детерминанта матрицы/Дмитришин Р.В.(СССР). Заявка 6.VII.1967, Ьюл. N 33, 1969. .

29. А.с. 328466 СССР. Устройство для определения числа . и чётности инверсии/Дмитришин Р.В.(СССР). Заявка ЗО.VIII. 1967, Бюл. N 6, 1972.

30. А.с. 364939 СССР. Устройство для нахождения деревьев графа/Дмитришин Р.В.(СССР). Заявка 31X1967, Бюл. N 5, 1973.

.31. А.с. 377783 СССР. Устройство для анализа деревьев направленного графа линейной цепи / Дмитришин Р.В.(СССР). Заявка

31.Х. 1967. Бюл. N 18, 1973.

АНОТАЦ11: . .

Дмитришин Р.В. Полиномиальные методы символьного анализа электрических цепей. Диссертация на соискание учёной степени доктора технических наук по специальности

05.09.05 -теоретическая электротехника, Государственный университет "Львовская политехника”, Львов, 1995.

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

Ключевые слова: методы анализа цепей, символьные элементы, точность моделирования, иерархическая декомпозиция.

Dmytryshyn R.V. The Polynomial Methods for Symbolic Analysis of Electrical Circuits, State University "Lviv Polytechnic", Thesis for the Degree of Doctor of Technical Sciences competition. Specialty

05.09.05 -Theoretical Electrotechnic. Lviv, Ukraine, 1995.

43 scientific papers and 5 author's certificates containing new theoretical statements, which can be qualified as an achievement in circuits theory are defended. Two new methods of linear circuits analysis are presented: d-trees and polynomial reduction. It is defined that these methods improve the effectiveness of complex linear circuits multivariant simulation programs.

Key words: circuits analysis methods, symbolic elements, simulation accuracy, hierarchical decomposition.