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

На иравахрукоинеп

Ц)

БАСКАКОВ АНДРЕЙ ЕВГЕНЬЕВИЧ

РАЗРАБОТКА МЕТОДОВ МАКРОМОДЕЛИРОВАНИЯ ЛИНЕЙНЫХ ЭКВИВАЛЕНТНЫХ ЭЛЕКТРИЧЕСКИХ СХЕМ С ИСПОЛЬЗОВАНИЕМ РАЗРЕЖЕННОСТИ МАТРИЦ

МОДЕЛЕЙ

Специальность 05.13.12 - Системы автоматизации проектировании (микроэлектроника)(технические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

9 «ЮН 2011

Москиа - 2011

4849022

Работа выполнена в Московском государственном институте электроники и

математики.

доктор технических паук, профессор Борисов Николай Иванович доктор технических наук, доцент Никольский Сергей Николаевич; доктор технических паук Сарафанов Альберт Викторович Федеральное Государственное Унитарное Предприятие Московский научно-исследовательский радиотехнический институт (г. Москва).

Защита диссертации состоится «28» июня 2011 г. в 16 часов на заседании диссертационного совета Д 212.133.03, в Московском государственном институте электроники и математики «МИЭМ» по адресу: г. Москва, Б. Трехсвя-тптсльскпй пер., д. 3.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики «МИЭМ». Автореферат размещён на сайте учёного совета «МИЭМ» http://sovet.niitme.ru

Автореферат разослан « » ^_2011 г.

Ученый секретарь диссертационного совета, доктор технических паук, профессор

Научный руководитель -

Официальные оппоненты:

Ведущая организация -

Лсохин 10.Л

Общая характеристика работы

Актуальность работы

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

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

ли с точки зрения заданного критерия.

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

Одним из эффективных подходов к снижению трудоёмкости процесса анализа линейных эквивалентных электрических схем является макромоде-лпровашю. суть которого состоит в переходе от модели к макромоделн, содержащей значительно меньшее количество уравнений и отражающей только соотношение "вход-выход". При получении различных характеристик модели по макромоделн точность вычислений не теряется, а время анализа сокращается на 1-3 порядка. Резкое сокращение времени анализа модели обеспечивает высокую практическую значимость макромоделпрования. Важно так же отмстить следующие возможности данного подхода:

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

2. Построение эффективной и экономичной конструктивной базы проектирования за счёт преобразования стандартных моделей большой размерности в макромодели.

Несмотря на огромный эффект, который даст применение макромоделпрования, в рамках данного подхода имеется ряд вопросов, требующих до-

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

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

Цель и задачи работы

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

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

высокой трудоёмкостью возникающих задач.

2. Проведён обзор методов и подходов к снижению трудоёмкости процессов анализа, и оптимизации линейных эквивалентных электрических схем.

3. Разработан метод построения макромоделп, использующий разреженность матриц модели.

4. Проведено исследование разработанного метода, в рамках которого получены оценки его трудоёмкости.

Методы исследования

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

На защиту выносятся:

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

и отличающийся от существующих методов наличием оптимальной промежуточной макромоделп.

2. Алгоритм приведения полиномиальной матрицы к треугольной форме с минимальным окаймлением и не дефектной треугольной подматрицей за счёт перестановки её строк и столбцов.

Практическая значимость

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

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

Реализация и внедрение результатов исследований

Полученные в данной работе результаты были использованы в рамках НИР «Исследование проблемы стойкости бортовой радиоэлектронной аппаратуры космического аппарата к воздействию электростатических разрядов» проводимой в Московском государственном институте электроники и математики (технический универси тет) с 01.01.2010 но 31.12.2010 г., а так же используются в учебном процессе МГИЭМ.

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на отчётных конференциях МГИЭМ (2007, 2008, 2009 г.), иаучно-прак-тнческом семинаре «Новые информационные технологии в автоматизированных системах» (2008, 2010 г.).

Публикации

Результаты диссертационной работы отражены в восьми опубликованных печатных работах. В том числе опубликована одна статья в журнале, включённом в перечень ВАК.

Структура диссертации

Диссертация состоит из введения, пяти глав, заключения и списка литературы.

Краткое содержание работы

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

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

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

кость метода, что не позволяет применять его к моделям большой размерности.

Использование любых свойств моделей является ключом к построению эффективных и экономичных методов их анализа. В полной мере это относится и к макромоделпровашпо. Исходя из тот, что матрицы моделей линейных эквивалентных электрических схем п других моделей, возникающих н САПР, зачастую являются разреженными, делается вывод о необходимости разработки методов, учитывающих это свойство при построении макромоделп, что в конечном счёте должно привести к сокращению вычислительных затрат п затрат памяти ЭВМ.

Во второй главе решаются следующие задачи:

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

2. Разработка метода построении макромоделп с использованием разреженности матриц модели.

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

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

Л(р)х(р) = у(р), (1)

где

Л(Р) = + А(1_1Р" ' + ... + А0, Лг е К"х'\г = 1.../(.

9

Вектор у (р) - вектор входных величин, х (р) может быть представлен как совокупность векторов :Г1 и х2, трактуемых как внутренние и выходные переменные соответственно. Обозначив размер вектора как т < п, представим (1) в блочной форме

Ли (Р) >1« СР) •Т! т

¿21 (?>) -422 (7') Г-2 У2

где А\ \ (р) имеет порядок т. Запишем (2) в виде системы двух уравнений относительно .Т[ и хо

Аи (р) XI + .4,2 (р) х2 = У1 М\ (р) XI + Л'2'2 (р) Х2 = у2.

Выразив XI из первого уравнения (3), и, подставив его во второе уравнение, получим

(-Аи (р) Лп (/') ^12 (р) + Л22(р)) х2 = у2 - А2, (р) /\п' (р) У\■ (4)

Уравнение (4) представляет собой макромодель, так как содержит только входные и выходные переменные. Введём следующие обозначения:

А(р) = (~А21 (р)Ап1(р) А12 (р) + А22(р)),

X — Хо 1

у = у2~ А21(р)у\й1 (р)у1.

Тогда (4) можно записать в виде

А (р) х = у. (5)

Построение макромодели (5) по модели (1) предсталяст собой шаг редукции. Матрица макромодели А (р) является рациональной матрицей, что отражено в диссертации.

Ключевой задачей шага редукции является обращение полиномиальной матрицы Ац (р) с сохранением аналитической зависимости от параметра р. Вид Лц1 (р) выбирается таким образом, чтобы снизить затраты на вычисления Л(р) при заданном р. Если матрица модели Лц (р) является регулярной полиномиальной матрицей первой степени, то Лп' (р) представляется и следующем виде.

А^(р) = В(Юр + ЕГ^т, (С)

где В, Б £ С"""" - матрицы, содержащие левые и правые собственные векторы матрицы Лп (р) соответственно; Б - диагональная матрица, для формирования которой требуется вычислить собственные значения матрицы А(р)]Е - едшшчпня матрица порядка пг. Вычисление Л^1 (р) в виде (0) возможно только в случае, если Ли (р) не является дефектной. В главе отмечается, что дефектность матрицы, т. е. ситуация, при которой алгебраическая кратность хотя бы одного ее собственного значения превышает геометрическую, является чрезвычайно редкой.

В случае если Лц (р) является нерегулярной или имеет степень /( > 1 для Лц1 (р) существуют аналогичные (6) выражения, приведённые в диссертации.

Таким образом, для построения макромоделн (4) требуется решить полную проблему собственных значений матрицы Лц (р), что является трудоёмкой задачей. Применяемый для её решения метод, основанный на преобразованиях подобия, имеет трудоёмкость, пропорциональную гп4 мультипликативных операций, а объём требуемой памяти ЭВМ ~ 2т2. Если порядок матрицы модели А (р) и соответственно количество исключаемых внутренних переменных т велики, то такие трудоёмкость и затраты памяти могут сделать невозможным построение макромоделн за разумное время.

Далее рассматриваются различные методы снижения трудоёмкости процесса построения макромодели за счёт использования разреженности матриц

И

модели, среди которых основными являются следующие.

1. Применение интерполяционного метода, для решения полной проблемы собственных значений матрицы Ли (р). Суть метода состоит в поиске методом Мюллера корней функции / (р) = (М(Лц(р)), которые являются собственными значениями Ац (р). Вычисление значения / при заданном р является наиболее трудоёмкой операцией в данном методе и производится посредством нормализованного ¿(^-разложения матрицы Ац (р), учитывающем её разреженность. Собственные векторы Ац(р) вычисляются в процессе такого разложения.

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

Ключевой недостаток первого метода состоит в том, что если Ац (р) является несимметричной н пе положительно определённой, то в процессе нормализованного ¿(^-разложения возникает проблема выбора, ведущих строк, обеспечивающих сохранение разреженности и точности разложении. Одновременное достижение указанных свойств в общем случае невозможно, что вынуждает использовать эвристические правила. Получение точных оценок трудоёмкости разреженного ¿(^-разложение, как и любых других алгоритмов разложения несимметричных разреженных матриц, чрезвычайно затруднительно, поскольку все они базируются на эвристических правилах. По этой причине такой подход не является предпочтительным.

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

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

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

Предлагается новый метод построения макромоделп, использующий разреженность матриц модели. Метод нацелен на снижение трудоёмкости основной задачи построения макромоделп, а именно, решении полной проблемы собственных значений полиномиальной матрицы Ли (р), которая предполагается разреженной. Суть метода состоит в сведении указанной проблемы к обобщённой проблеме собственных значений небольшого размера с последующим применением интерполяционного метода для её решения. Рассмотрим общую схему метода.

Пусть требуется вычислить все собственные значения п векторы разреженной полиномиальной матрицы А (р) порядка п:

А(р)х = 0. (7)

Введём матрицы Р и (} являющиеся матрицами перестановок строк и столбцов соответственно. Умножив (7) слева на Р, и, обозначив х = (]тх, получим

РА (р) (Зтх = 0. (8)

Далее предположим, что найдены такие Р и С}, которые приводят А (р) к треугольной форме е окаймлением, то есть уравнение (8) может быть представлено в виде

ЛУ2 (Р)

¿21 (Р) Ли (р)

13

г(2)

= о,

(9)

где Ь (]>) является не дефектной ппжпе-треуголыюй полиномиальной матрицей порядка к с тождественно не равными пулю диагональными элементами. Запишем (9) в виде системы уравнении относительно и :г'2'

Ь(р) х^+Л1о (рЫ2> = 0

(10)

А21(р)хМ + А22(р)хМ = 0.

Выразив .г'1' из первого уравнения (10) и, подставив его во второе уравнение, получим обобщённую проблему собственных значений

(Л22 (р) - Л2] (р) Ь-1 (я) Л12 (р)) х® =0. (11)

Можно показать, что собственные значения, вычисленные но проблемам (11) п (7) совпадают. Пусть - собственный вектор проблемы (11), отвечающий собственному значению р,, тогда легко убедиться, что вектор

X =

х-(2)

является собственным вектором (7). Таким образом, исходная проблема собственных значений (7) была сведена к обобщённой проблеме (11), матрица которой, как показывает практика, будет плотпой.

Матрица (р) в (11) при поиске собственных значений и векторов может быть представлена в виде, удобном для вычислений (6). Это в свою очередь требует решения полной проблемы собственных значений матрицы Ь(р), которая выполняется сравнительно быстро, так как с.з.-ня треугольной матрицы вычисляются тривиально и, что немаловажно, - практически без погрешности, а для поиска собственных векторов требуется многократное решение СЛАУ с треугольной матрицей.

Итак, в рассмотренном подходе можно выделить 3 основных шага:

1. Вычисление матриц перестановок Р и таких, что РА(р)С}т имеет

14

треугольную форму с окаймлением. При этом Ь (р) должна быть не дефектна.

2. Решение полной обобщённой проблемы собственных значений матрицы

Цр).

3. Решение полной обобщённой проблемы собственных значений (11).

На шаге 2 возникает задача многократного решения СЛАУ с разреженной трапециевидной матрицей. Метод решения данной задачи строится на основании точного метода решения СЛАУ с разреженной треугольной матрицей, что является хорошо изученной задачей.

Основной объё'м вычислений ложится на шаг 3. Его трудоёмкость определяется в первую очередь размером возникающей проблемы собственных значений (11). В связи с этим желательно, чтобы порядок к матрицы Ь(р) в (9) был максимальным. В идеальном случае к = п, что вообще исключает шагЗ. Таким образом, для получения матриц перестановок на таге 1 требуется решить дискретную оптимизационную задачу с ограничениями, в которой варьируемыми параметрами являются матрицы перестановок, целевой функцией - порядок к матрицы Ь (р) в (9). Ограничением является требование того, чтобы Ь (р) не была дефектна. Разработке метода решения указанной задачи посвящена глава 3. Анализ п метод решения обобщённой проблемы собственных значений (11) рассматриваются в главе 4.

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

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

главе метода построения макромодели. Рассмотрим постановку данной задачи.

Пусть дана полиномиальная матрица А(р) степени а, порядка п:

1=0

где Л, б С"*", г = 1,2,. Необходимо найти такие Р и (}, что Л (А) = РТ (А) С}т имеет треугольную форму с: окаймлением, то есть

Матрицы Л-21 (р), Л22 (р), А[2 (р) условно называются окаймлением, размер которого определяется порядком матрицы Л2-¿{р)- При поиске матриц Р п (Ц необходимо учесть следующие требования:

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

2. Необходимо минимизировать размер окаймления.

Первое требование продиктовано тем, что в дальнейшем будет проводиться вычисление Ь 1 (р) согласно (6). Минимизация размера окаймления необходима для снижения трудоёмкости решения обобщённой проблемы собственных значений (11).

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

(12)

Л(А) =

Ир) аи(р)

(р) л22 (р)

где к \ - размер окаймления матрицы Т, имеющей треугольную форму с окаймлением. Это означает, что в ра.мках данной задачи числовые значения исходной матрицы роли не играют, важно лишь расположение её ненулевых элементов. При решении подобных задач распространённой практикой является их формулировка в терминах теории графов. Именно таким путём задача (13) была исследована и решена в 1970-х годах известным учёным в области автоматизации проектирования СБИС Альберто Санджованни-Впн-чептелли и Теодором Бпкартом. В главе даётся необходимая теоретическая база, а так же приводятся алгоритмы решения данной задачи. Такие а;тго-рнтмы производят последовательное расширение набора строк и столбцов исходной матрицы, которые войдут в Ь.

При выборе метода решения Г1, отмечается, что данная задач является ^Р-нолной. то есть не найден алгоритм её решения, трудоёмкость которого зависела бы от размера задачи (в данном случае это порядок матрицы А (р)) полиномиально. Сложность таких задач состоит в невозможности оценить время их решения.

Принимая во внимание сказанное выше, а так же результаты исследований. проведённых А. Санджованин-Впнчентеллп, задача Р1 заменяется задачей Р2. суть которой состоит в поиске таких матриц перестановок, при которых полученная треугольная подматрица уже не может быть расширена за счёт оставшихся строк и столбцов.

Задача Р'2 не является ЛГР-подной. Ключевым вопросом в алгоритме её решения является последовательный выбор элементов, попадающих на диагональ треугольной подматрицы. Априори сделать выбор, приводящий к минимальному окаймлению невозможно, поэтому для этого применяют эвристические правила.

Используя метод решения задачи Р2, а так же критерии дефектности

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

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

В четвёртой главе проводится анализ существующих методов решения полной обобщённой проблемы собственных значений (ОПСЗ), возникающей и рамках предложенного во второй главе метода построения макроыоделп. Эта задача состоит в следующем.

Пусть дана квадратная матрица Т (р), элементы которой являются функциями параметра р, тогда ОПСЗ состоит в поиске таких скаляров р, и векторов что выполняется

В главе рассматриваются задачи моделирования, в которых возникают различного вида обобщённые проблемы собственных значений. На практике встречаются полиномиальные н рациональные Т(р). Однако возможны случаи более общей зависимости Т от р.

Несмотря на значительный объём работ по методам решения ОПСЗ, существует большое количество прикладных задач, для решения которых возможностей существующих методов недостаточно. Применяемые методы зачастую не соответствуют уровню сложности современных задач. Поэтому, как отмечается авторитетными в этой области авторами, требуется глубокое исследование рассматриваемой задачи.

Для решения обыкновенной проблемы собственных значений Ах — \х или ОПСЗ вида Ах = АЕх доступны многие, хорошо зарекомендовавшие себя

(14)

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

В главе проводится обзор методов решения (1-1), в котором отмечаются различные аспекты теоретического и практического характера. Такие методы можно разделить на 3 группы:

1. Методы линеаризации для ОПСЗ с полиномиальной или рациональной матрицей. В результате линеаризации получают ОПСЗ с пучком матриц большого порядка. Такие методы нацелены на поиск небольшого количества интересующих собственных значений и собственных векторов.

2. Уточняющие методы. В данный класс попадает большинство существующий методов решения ОПСЗ (метод Кублановскон, метод обратной итерации и его разновидности и др.). Суть методов состоит в итерационном приближении к собственному значению. Методы данного класса применяются для уточнения найденных собственных значений и векторов.

3. Интерполяционные методы. Сюда входят методы, основанные па поиске корней детермпнантного уравнения матрицы проблемы. Наиболее известным и эффективным методом данной группы является метод Мюллера (метод последовательной квадратично]"! интерполяции).

На основании проведённого обзора делается выбор метода Мюллера для

решения детермипаптпого уравнения рацнопалыюй матрицы проблемы. Формула, определяющая процесс поиска корней имеет вид

(р ~ Р1)''' (Р ~ Рч)'

где {)[,... рч - ранее найденные интерполяционным методом собственные значения, / (р) = с1е1 (Г (р)), (1 (р) = (//! - р) ■ ■ ■ (рк - р). Здесь //ь... рк - собственные значения Ь (р) (11). Использование функционального нормирующего множителя (1(р) обусловлено тем, что / (р) является дробпорационалыюй функцией от р. Если вычислят!, /5 (р) без (1{р), то степень многочлена знаменателя но мере нахождения корней в определенный момент превысит степень многочлена числителя, что приведёт к срыву вычислительного процесса вследствие того, что интерполяционный метод начнёт сходиться к оо. Метод Мюллера вычисляет очередное приближение к корню (р) по трём предыдущим приближениям рь^-ь^-г как корень полинома второй степени, проходящего через точки /Др,:)), (/>¿-1, /Др,-1)), (/'¿-2, /Дл^))- И;! корней такого полинома выбирается тот, который расположен ближе всего к VI-

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

1. Среднее количество шагов необходимых для поиска корпя интерполяционным методом.

2. Соотношение ф порядков матрицы обобщён пса! проблемы собственных значении (11) н матрицы Л (;;).

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

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

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

В пятой главе проводится краткий обзор средств построения программного обеспечения для решения вычислительных задач. Среди таких средств выделяются языки программирования, среды разработки, библиотеки решения различных задач, включая вычислительные задачи линейной алгебры и задачи на графах. В главе обосновывается выбор пакета MATLAB в качестве основной среды разработки, коллекции пакетов SuitcSparsc для решения различных задач с. разреженными матрицами, библиотеки Boost Graph Library для решения задач па графах. Так же приводится описание написанных программ.

Основные результаты работы

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

2. Проведено исследование, в результате которого были получены оценки трудоёмкости п затрат памяти ЭВМ разработанного метода, показывающие целесообразность его применения в случае разреженности матриц модели.

3. Разработанный метод и содержащиеся в нём алгоритмы реализованы в виде коллекции МАТЬАВ-программ.

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

Публикации

Научные и практические результаты диссертационной работы отражены в следующих публикациях.

1. Баскаков Л.Е. Разработка методов редукции динамических моделей с разреженными матрицами для повышения качества проектируемых объектов. /,' Качество. Инновации. Образование. 2009. №9. С.58-64.

2. Баскаков Л.Е. Подход к увеличению быстродействия макромодели линейной системы за счёт снижения ее точности. / / Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. -М. МИЭМ, 2000. С. 91.

3. Баскаков Л.Е. Использование разреженности матриц в макромодели-ровашш. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. -М. МИЭМ, 2007. С. 99-100.

4. Баскаков Л.Е. Обзор методов редукции линейных динамических моделей, основанных ва идее аппроксимации. / . Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладе!!. -М. МИЭМ. 2008. С. 119-121.

5. Баскаков Л.Е. Задача приведения матрицы к треугольной форме с окаймлением в рамках редукции динамических моделей высокой размерности. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. -М. МИЭМ, 2008. О. 121-122.

6. Баскаков Л.Е., Борисов Н.П. Алгоритм построения макромоделн. основанный на идее метода определяющих величин. // Новые информационные технологии в автоматизированных системах: материалы одиннадцатого научно-практического семинара. - Моск. гос. пн-т электроники п математики. М., 2008, 134 с. С. 93-98.

7. Баскаков А.Е. Решение задачи обращения треугольной полшюмшш.-пой матрицы в рамках макромоделпровапня. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МПЭМ. Тезисы докладов. -М. МПЭМ, 2009. С. 59-00.

8. Баскаков А.Е. Обзор методов решения обобщённой проблемы собственных значений плотной матрицы, элементы которой нелинейно зависят от параметра. // Новые информационные технологии в автоматизированных системах: материалы тринадцатого научно-практического семинара. - Моск. гос. ин-т электроники и математики. М., 2010, 309 с. С. 223-231.

Подписано в печать 25.05.2011 г. Тираж 150 экз. Заказ № 1396 Отпечатано в типографии «АллА Принт» Тел. (495) 621-86-07, факс (495) 621-70-09 wwvv.allaprmt.ru