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

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

РАЗРАБОТКА МЕТОДОВ МАКРОМОДЕЛИРОВАНИЯ

ЛИНЕЙНЫХ ЭКВИВАЛЕНТНЫХ ЭЛЕКТРИЧЕСКИХ СХЕМ

С ИСПОЛЬЗОВАНИЕМ РАЗРЕЖЕННОСТИ МАТРИЦ

МОДЕЛЕЙ

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

и)

АВТОРЕФЕРАТ

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

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

Научный руководитель - доктор технических наук, профессор Борисов Николай Иванович

Официальные оппоненты: доктор технических наук, доцент Никольский Сергей Николаевич;

доктор технических наук Сарафанов Альберт Викторович

Ведущая организация - Федеральное Государственное Унитарное Предприятие Московский научно-исследо­ вательский радиотехнический институт (г.

Москва).

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

С диссертацией можно ознакомиться в библиотеке Московского государ­ ственного института электроники и математики «МИЭМ».

Автореферат раз­ мещён на сайте учёного совета «МИЭМ» http://sovet.mitme.ru Автореферат разослан « » 2011 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов исследований Полученные в данной работе результаты были использованы в рамках НИР «Исследование проблемы стойкости бортовой радиоэлектронной аппа­ ратуры космического аппарата к воздействию электростатических разрядов»

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

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

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

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

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

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

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

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

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

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

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

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

Исходными данными для указанного выше процесса является модель, записанная с использованием преобразования Лапласа где Вектор () - вектор входных величин, () может быть представлен как совокупность векторов 1 и 2, трактуемых как внутренние и выходные пере­ менные соответственно. Обозначив размер вектора 1 как <, представим (1) в блочной форме где 11 () имеет порядок. Запишем (2) в виде системы двух уравнений относительно 1 и Выразив 1 из первого уравнения (3), и, подставив его во второе уравнение, получим Уравнение (4) представляет собой макромодель, так как содержит только входные и выходные переменные. Введём следующие обозначения:

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

Матрица макромодели () является рациональной матрицей, что отражено в диссертации.

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

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

где, C - матрицы, содержащие левые и правые собственные векто­ ры матрицы 11 () соответственно; - диагональная матрица, для формиро­ вания которой требуется вычислить собственные значения матрицы ();

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

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

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

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

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

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

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

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

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

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

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

Введём матрицы и являющиеся матрицами перестановок строк и столб­ цов соответственно. Умножив (7) слева на, и, обозначив =, получим Далее предположим, что найдены такие и, которые приводят () к треугольной форме с окаймлением, то есть уравнение (8) может быть пред­ где () является не дефектной нижне-треугольной полиномиальной матри­ цей порядка с тождественно не равными нулю диагональными элементами.

Запишем (9) в виде системы уравнений относительно (1) и (2) Выразив (1) из первого уравнения (10) и, подставив его во второе уравнение, получим обобщённую проблему собственных значений Можно показать, что собственные значения, вычисленные по проблемам (11) и (7) совпадают. Пусть (2) - собственный вектор проблемы (11), отвечающий собственному значению *, тогда легко убедиться, что вектор является собственным вектором (7). Таким образом, исходная проблема соб­ ственных значений (7) была сведена к обобщённой проблеме (11), матрица которой, как показывает практика, будет плотной.

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

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

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

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

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

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

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

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

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

где C, = 1, 2,...,. Необходимо найти такие и, что () = () имеет треугольную форму с окаймлением, то есть Матрицы 21 (), 22 (), 12 () условно называются окаймлением, размер которого определяется порядком матрицы 22 (). При поиске матриц и необходимо учесть следующие требования:

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

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

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

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

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

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

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

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

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

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

Эта задача состоит в следующем.

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

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

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

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

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

На основании проведённого обзора делается выбор метода Мюллера для решения детерминантного уравнения рациональной матрицы проблемы. Фор­ мула, определяющая процесс поиска корней имеет вид где 1,... - ранее найденные интерполяционным методом собственные зна­ ственные значения () (11). Использование функционального нормирующе­ го множителя () обусловлено тем, что () является дробнорациональной функцией от. Если вычислять () без (), то степень многочлена зна­ менателя по мере нахождения корней в определённый момент превысит сте­ пень многочлена числителя, что приведёт к срыву вычислительного процесса вследствие того, что интерполяционный метод начнёт сходиться к. Ме­ тод Мюллера вычисляет очередное приближение +1 к корню () по трём предыдущим приближениям, 1, 2 как корень полинома второй степе­ ни, проходящего через точки (, ( )), (1, (1 )), (2, (2 )). Из корней такого полинома выбирается тот, который расположен ближе всего к На основании проведённого обзора, а так же результатов второй и тре­ тьей главы, приводится оценки трудоёмкости и затрат памяти ЭВМ пред­ ложенного во второй главе метода построения макромодели, использующего разреженность матриц модели для случая когда эта матрица является по­ линомиальной матрицей первой степени. Предложенные оценки зависят от следующих факторов:

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

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

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

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

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

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

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

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

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

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

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

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

Тезисы докладов. –М. МИЭМ, 2006. С. 91.

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

99-100.

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

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

121-122.

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

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

Тезисы докладов. –М. МИЭМ, 2009. С. 59-60.

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

223-231.