Спектрально псевдообратные матрицы и их приложение к численному анализу и решению эрмитовых дифференциально-алгебраических систем тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат наук Овчинников, Георгий Викторович

• Овчинников, Георгий Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Овчинников, Георгий Викторович

Содержание

Введение

0.1 Актуальность темы

0.2 Цель

0.3 Научная новизна

0.4 Основные положения, выносимые на защиту:

0.5 Научная значимость

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

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

0.8 Личный вклад

0.9 Публикации

0.10 Объем и структура работы

0.11 Благодарности

1 Спектрально-псевдообратные матрицы и их свойства

1.1 Введение

1.2 Доказательства свойств спектрально-псевдообратных матриц

1.3 Бескоординатные доказательства некоторых свойств спектрально-псевдообратных матриц

1.4 Псевдообратные матрицы Дразина и Мура-Пенроуза

1.5 Выводы

2 Верхние оценки норм решений эрмитовых систем обыкновенных дифференциальных и алгебраических уравнений

2.1 Введение

2.2 Устойчивость

2.3 Численная реализация

2.4 Сравнение с оценкой, основанной на уравнении Ляпунова

2.5 Выводы

3 Оценка времени установления напряжения в КС схемах

3.1 Введение

3.2 Математическая постановка задачи

3.3 Вывод оценки

3.4 Реализация

3.5 Выводы

4 Решение эрмитовых систем обыкновенных дифференциально-алгебраических уравнений на основе многочленов Лагерра

4.1 Введение

4.2 Постановка задачи

4.3 Разложение точного решения в ряд по сверткам с многочленами Лагерра

4.4 Оценка погрешности приближенного решения

4.5 Вычисление приближенного решения

4.6 Приложение к КС-схемам

4.7 Численные эксперименты

4.8 Близкие алгоритмы редукции и сравнение с ними

4.8.2 Метод моментов

4.8.3 Крыловская редукция на основе рядов по многочленам и функциям Лагерра

4.9 Выводы

Заключение

Список рисунков

Список таблиц

Литература

Введение диссертации (часть автореферата) на тему «Спектрально псевдообратные матрицы и их приложение к численному анализу и решению эрмитовых дифференциально-алгебраических систем»

Введение

0.1 Актуальность темы

Линейные системы обыкновенных дифференциальных и алгебраических уравнений (ОДАУ) возникают в различных областях науки и техники: механике, микроэлектронике, экономике и многих других. В некоторых задачах они выступают как самостоятельные математические модели рассматриваемых систем, в других, как части таких моделей, а в третьих получаются линеаризацией нелинейных моделей. В данной работе рассматриваются только линейные системы ОДАУ и линейные системы обыкновенных дифференциальных уравнений (ОДУ).

В случаях когда для решения больших систем ОДАУ методы непосредственного численного интегрирования [1] не позволяют получить решение за разумное время по причине своей высокой вычислительной стоимости, используют методы редукции, позволяющие заменять исходную систему системой того же вида, с меньшей размерностью вектора внутреннего состоянии и прежними размерностями векторов входов и выходов. Редуцированная система должна аппроксимировать исходную, в смысле близости выходов при одинаковых входах. Несмотря на значительное развитие алгоритмов редукции систем ОДАУ, разработка новых методов редукции продолжает оставаться актуальной из-за роста размерности и количества рассматриваемых задач.

К настоящему моменту для систем ОДУ скопился значительный багаж алгоритмов редукции, например, [2], [3], [4], [5], [6], не имеющих аналогов для ОДАУ. С помощью предложенных в диссертационной работе спектрально-псевдообратных матриц можно сводить задачи для ОДАУ к задачам для ОДУ, таким образом обобщая результаты полученные для ОДУ.

В ряде практических задач интерес представляет время входа решения в е-окрестность асимптотики, которое хотелось бы находить особенно быстро и более эффективно по сравнению с редукцией и последующим решением редуцированной системы. Для этой задачи, с помощью спектрально-псевдообратных матриц удалось обобщить полученные ранее другими авторами оценки [7], [8], [9].

0.2 Цель

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

0.3 Научная новизна

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

рой системы матричных уравнений. Спектрально-псевдообратные матрицы позволяют разрешать линейные эрмитовы системы ОДАУ относительно производной по времени. Эти результаты были в дальнейшем обобщены другими авторами на случай неэрмитовых систем ОДАУ в работе [10].

Для систем ОДУ известны достаточно точные оценки норм решений на основе уравнений Ляпунова [7], [8], [9]. Спектрально-псевдообратные матрицы позволили впервые получить аналогичные оценки для эрмитовых систем ОДАУ, а именно, оценки норм решений задач Коши и их проекций на подпространства, отвечающие конечным и бесконечным собственным значениям матричного пучка рассматриваемой системы. Заключительная часть работы посвящена созданию алгоритмов временной редукции для линейных систем ОДАУ, получающихся при моделировании емкостно-резистивных схем. Был предложен новый алгоритм редукции, основанный на спектрально-псевдообратных матрицах и аппроксимации матричной экспоненты рядом по функциям Лагерра. Предлагаемый алгоритм редукции, по сравнению с аналогами, применим к более широкому классу задач, а предлагаемый метод вычисления времени установления уникален. В отличии от других работ, например, таких как [13], [14], [15], в которых накладываются определенные, достаточно сильные требования на топологию рассматриваемых систем, предложенная оценка применима в случае любой связной ЯС-цепи.

Ближайшими аналогами предложенного алгоритма редукции являются работы [2], [3], [4], [5], [6] основанные на использовании многочленов Лагерра для построения Крыловского подпространства. В упомянутых работах предполагается принадлежность передаточной функции пространству Харди К2, что эквивалентно рассмотрению асимптотически устойчивых систем ОДАУ с невырожденными матрицами в то время как предложенный подход позволяет для эр-

митовых асимптотически устойчивых систем ОДАУ снять ограничение на невырожденность матрицы Е.

0.4 Основные положения, выносимые на защиту:

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

2. Для линейных систем обыкновенных дифференциальных и алгебраических уравнений с эрмитовыми матрицами предложены и обоснованы достижимые верхние оценки норм решений задач Коши. Предложен эффективный алгоритм временной редукции задач Коши для эрмитовых систем ОДАУ.

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

0.5 Научная значимость

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

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

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

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

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

При проектировании сверхбольших интегральных схем (СБИС) возникает необходимость анализа шумов и задержек сигналов, вызванных неидеальностью межсоединений. Это является основным фактором роста сложности моделирования СБИС при увеличении степени интеграции, особенно при переходе на техпроцессы в десятки нанометров. Этот факт отмечен во многих статьях и монографиях, например: [16], [17], [18], [19].

Техника электромагнитного анализа СБИС позволяет моделировать неидеальность межсоединений схемами, состоящими из резисторов, конденсаторов, индуктивностей и взаимных индуктивно-стей, которые приводят к линейным системам ОДАУ.

Зачастую, получающиеся при моделировании линейные системы ОДАУ слишком велики для непосредственного решения соответствующих задач Коши. Кроме того, в ряде задач микроэлектроники интерес представляют не столько решения, сколько их некоторые характеристики, которые хотелось бы находить более эффективно, минуя вычисление самих приближенных решений [20]. Значительный интерес представляют оценки задержки сигнала для ЯС-схем.

В микроэлектронике широко используют методы редукции, поскольку непосредственное решение задач большой размерности требует значительных вычислительных затрат. Несмотря на значительное развитие алгоритмов редукции систем ОДАУ, возникающих при моделировании СБИС, разработка новых методов редукции продолжает оставаться актуальной по причине роста размерности рассматриваемых задач и их количества [20].

Для оценки влияния неидеальности соединений на задержку сигнала в СБИС интерес представляют алгоритмы, позволяющих быстро находить решение, пусть и с небольшой точностью [20]. Значительный интерес представляют оценки задержки отклика сигнала для RC-схем [13], [14], [15].

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

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

Основные положения, сформулированные в диссертационной работе, обсуждались на семинарах в Институте вычислительной математики РАН, Институте проблем проектирования в микроэлектронике, Московском отделении Cadence Design Systems, Университете западной Бретани (г. Брест, Франция), инновационной ярмарке "International innovation fair"(г. Гуанчжоу, Китай, 2011 год) и следующих конференциях: международной конференции "International conference on Matrix Methods in Mathematics"(г. Москва, 2011 год), международной школе-конференции молодых ученых конференции "Математические идеи П. JI. Чебышева и их приложения к современным проблемам естествознания" (г. Обнинск, 2011 год), научных конференциях МФТИ 52-55 (г. Долгопрудный, 2009-2012 годы).

Данные исследования в 2010 году получили первое место в конкурсе Intel «Невозможное стало возможным» и финансирование по программе У.М.Н.И.К., заняли третье место в "Традиционном конкурсе научных работ ФПФЭ" в 2011 году и были отмечены почетным дипломом на научной конференций МФТИ-55 в 2012 году.

0.8 Личный вклад

Все теоремы в работах [11], [12] сформулированы и доказаны совместно Ю.М. Нечепуренко, а численные эксперименты проведены автором. Кроме того, автором предложен и обоснован метод быстрого вычисления сверток входного сигнала с функциями Лагерра.

0.9 Публикации

Основные результаты диссертации изложены в восьми печатных работах, 2 из которых опубликованы в журналах, рекомендованных ВАК [11,12], 6 - в тезисах докладов [21-26].

0.10 Объем и структура работы.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Полный объем диссертации составляет 91 страницу с 10 рисунками и двумя таблицами. Список литературы содержит 48 наименований.

0.11 Благодарности

Диссертант выражает особую благодарность своему научному руководителю Юрию Михайловичу Нечепуренко за постоянную помощь и ценные советы в работе над диссертацией, Сергею Григорьевичу Русакову за помощь и поддержу при работе над диссертацией и ныне ушедшей из жизни Алене Станиславовне Потягаловой, вместе с которой была начата работа над алгоритмом редукции.

Глава 1

Спектрально-псевдообратные

матрицы и их свойства

1.1 Введение

Рассмотрим регулярный матричный пучок

ХЕ — А

здесь А и Е соответственно отрицательно и неотрицательно определенные эрмитовые матрицы порядка п. Конечные собственные значения такого пучка, т.е. корни уравнения ¿еЬ(ХЕ — А) = 0, являются вещественными отрицательными [27].

Обозначим через V правый проектор Рисса на понижающее подпространство, отвечающее множеству конечных собственных значений пучка ХЕ — А [7]:

где Г - достаточно гладкий простой положительно ориентированный замкнутый контур, охватывающий все конечные собственные значения. Тогда, в силу эрмитовости матриц Л и Е, сопряженная матрица V* будет левым проектором Рисса на понижающее подпространство,

(1.1.1)

отвечающее конечным собственным значениям этого пучка, т.е.

V* = [ Е{ХЕ -2гтт Jг

и для этих проекторов справедливы следующие равенства:

a) V*E — Е = EV, b)V*A = AV. (1.1.2)

Введем в рассмотрение центральный объект данной работы, матрицу

Е+ = -5- [(\Е- (1.1.3)

2гтт Jг

которую мы далее будем называть спектрально-псевдообратной. Эта матрица удовлетворяет равенствам

а) Е+Е = V, b) ЕЕ+ = V\ с) ЕЕ+Е = Е, d) Е+ЕЕ+ = Е+,

(1.1.4)

первые два из которых очевидны, третье следует из первого и (1.1.2а), а четвертое будет доказано далее. Важно отметить, чтоЕ+ единственная матрица, удовлетворяющаяя (1.1.4). Другими словами, верна следующая теорема

Теорема 1.1. Матрица X, удовлетворяющая следующим равенствам

а) ХЕ = V, b) EX = V*, с) EXE = Е, d)XEX = X,

существует, единственна и совпадает со спектрально-псевдообратной матрицей.

1.2 Доказательства свойств спектрально-псевдообратных матриц

Лемма 1.1. Матрица (1.1.3) удовлетворяет равенствам (1.1.4). Никакая другая матрица одновременно всем этим равенствам удовлетворять не может.

Доказательство. Поскольку матрица А отрицательно определенная, а Е - неотрицательно определенная, найдется такая невырожденная матрица Р, что

а) Р*АР = Д Ъ) Р*ЕР =

1г о

О о

(1.2.1)

где I) - отрицательно определенная диагональная матрица, а /г -единичная матрица порядка г = гапкЕ1 [27]. Используя эти равенства, и учитывая, что первые г диагональных элементов матрицы И образуют множество конечных собственных значений пучка АЕ — А , можно показать, что для проектора (1.1.1) справедливо представление

Г 1Т О О О

V = Р

(1.2.2)

а для псевдообратной матрицы (1.1.3) - представление

Е+ = Р

/г О О О

р*

(1.2.3)

Опираясь на (1.2.1), (1.2.2) и (1.2.3), несложно непосредственно проверить справедливость равенств (1.1.4). Таким образом, мы доказали, что матрица (1.1.3) удовлетворяет (1.1.4). Осталось показать, что никакая другая матрица одновременно всем этим равенствам удовлетворять не может.

Очевидно достаточно убедиться, что система уравнений

а) {Е+ + А)Е = V, Ъ)Е(Е+ + А)=Г\ (1.2.4)

с) (Е+ + А)Е{Е+ + А) = Е+ + А

имеет только тривиальное решение А = 0. Из (1.2.4а,Ь) и (1.1.4а,Ь) следует, что АЕ = ЕА = 0. Раскрывая скобки в (1.2.4с) и используя эти равенства и равенство (1.1.4(1) получаем требуемое равенство А = 0. □

Применяя (1.2.1), (1.2.2) и (1.2.3) нетрудно проверить (1.1.2) и следующие равенства:

а) РЕ+ = Е+ = Е+Г*, Ъ) ГА'1 = А~1Т\ (1.2.5)

которые нам потребуются в дальнейшем. Отметим, что (1.2.5а) можно также вывести из (1.1.4а,Ь,с1), а (1.2.5Ь) непосредственно следует из (1.1.2Ь).

Рассмотрим матрицу

Е+ = (Е- аА)~1Е(Е - аА)~1. (1.2.6)

В силу (1.2.1),

Et = Р

а

(.Ir-aDr)~2 0 0 0

и, следовательно,

lim Е+ = Е+.

а—>0 а

Причем, как нетрудно видеть, Е+ < Eß , если а > ß > l/Amin(A, Е).

1.3 Бескоординатные доказательства некоторых свойств спектрально-псевдообратных матриц

В данном разделе предлагаются альтернативные (бескоординатные) доказательства некоторых свойств спектрально-псевдообратных матриц.

Для начала докажем следующую формулу:

Лемма 1.2.

е = Мхе - АГ^лах, (1.3.1)

где контур Г охватывает все собственные значения матричного пучка XЕ — А и не охватывает ноль.

Доказательство. Пользуясь формулой для представления функции от матрицы через контурный интеграл [7] запишем представление матрицы ЕА~1 в следующем виде:

ЕА~Х = — </ ф/ - ЕА~1)~1с1г.

/г0 ^ ;

где контур Го охватывает все собственные значения матрицы ЕА~~1. Заметим, что

-£ ф/ - ЕА~~г)~1с1г = £ А(А - г~1Е)~Чг,

Делая замену г~1 = Л получим

ЕА~1 = ¿ / Х~2Л(ХЕ ~ Л)~1(1Х-

Здесь контур Гх получается из контура Го преобразованием г~1. Таким образом внутри Гх лежат все собственные значения матричного пучка ХЕ — А. И следовательно интеграл по контуру Гх равен интегралу по контуру Го минус вычет на бесконечности, который равен

О в силу того, что в окрестности бесконечно удаленной точки

\~2А{\Е - А)'1 ~ Л-2.

□

Лемма 1.3. Верно равенство (1.1.2а).

Доказательство. Рассмотрим разность £"Р — Е, с учетом формулы (1.3.1):

= ¿(Е(ХЕ - А)~1Е - А(ХЕ - Ау1АХ~2)с1Х. (1.3.2) 27гг /Г

Умножая следующее тождество

(АЕ - А)А~~1Е = ЕА~1(ХЕ - А), слева на А(ХЕ — А)-1, а справа на (АЕ — А)-1 А придем к:

Е(ХЕ - А)'1 А = А(ХЕ - А)~1Е. (1.3.3)

Применяя (1.3.3) к (1.3.2) получим, что:

Е(ХЕ — А)~1Е — А(ХЕ — А)~1АХ~2 = (ЕА~1Е- Х~2А){ХЕ- А)'1 А. Заметим, что:

(.ЕА~1Е - X~2А) = А-2((АЕА~1)2 - 1)А = Х~2{ХЕА~1 + 1)(ХЕ - А). Теперь

ЕГ-Е = — ¿{ЕА^Е - Х~~2А)(1Х.

2ш Уг

В силу отсутствия у пучка АЕ — А нулевых собственных значений, контур Г всегда может быть выбран так, что этот интеграл будет равен нулю. □

Докажем четвертое из равенств (1.1.4).

Лемма 1.4. Верно равенство (1.1.4(1).

Доказательство. Для начала заметим, что из тождества

(ХЕ - А)(ХЕ - А)'1 = I,

следует, что

НПЕ-А)-1

(1.3.4)

Рассмотрим разность Е+ЕЕ+ — Е+ учитывая формулу (1.1.4Ь):

= -(ЛЕ - А)~1Е(ХЕ - А)'1.

аХ

Е+ЕЕ+ = ¿(ХЕ - А)-\1 - Т*)(1Х. (1.3.5)

2т 3г

Используя (1.3.4) производную от подынтегрального выражения запишем как

= {ХЕ - А)~1Е(ХЕ - А)~\1 - Р*). (1.3.6)

ал

Из (1.1.2а) и (1.1.2Ь) следует, что

(.ХЕ-А)Г = Г*(ХЕ-А),

откуда умножением на (ХЕ — А)~1 справа и слева получим:

(ХЕ - А)~1уР* = Т>(ХЕ — А)~х. (1.3.7)

Осталось отметить, что в силу свойств (1.3.7) и (1.1.4с) выражение (1.3.6) равно нулю, а следовательно и правая часть (1.3.5), как интеграл от регулярной внутри контура функции. Лемма доказана. □

1.4 Псевдообратные матрицы Дразина и Мура-Пенроуза

В этом разделе мы кратко напомним основные свойства двух других популярных вариантов псевдообращения: псевдообратных матриц Дразина А° [28] и Мура-Пенроуза А^ [29], а также отметим

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

Для псевдообратной матрицы Мура-Пенроуза, определяющая её система имеет следующий вид:

а)АА*А = Л, Ъ)А*АА+ = c){AÄ)* = АА*, d)(A^A)* = А*А.

Используя SVD разложения матрицы А:

А = UYV* = U

Ei О О О

V*,

(1.4.1)

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

1.

Ä = и eV* = и

Е^1 О О О

V*

2. (A*)t = (At)*.

3. (At)t = А.

4.

lim (A*A + aI)~lA* = lim A\AA* + al)~l.

a-Я-О q—>4-0

С псевдообратной матрицей Мура-Пенроуза связаны два ортогональных проектора на образы А я А*: Р = ААt и Q = А^А соответственно. На основе канонического разложения Вейерштрасса можно показать, что Е+ совпадает с псевдообратной матрицей Мура-

Пенроуза, если матрицы А и Е перестановочны. Отметим, что в этом случае V = V*, т.е. V - ортопроектор.

Для матрицы А € Спхп обладающей нулевым собственным значением кратности к, псевдообратная матрица Дразина А° определяется как матрица, удовлетворяющая следующим равенствам:

а

г)АвААв = А°, Ь)А°А = АА°, с)Ак+1А° = Ак. Используя форму Жордана для А:

А = ХЗХ~1 = X

Л О О

-1

(1.4.2)

где Жордановы блоки 7о и ^ отвечают нулевым и ненулевым собственным значениям соответственно, можно убедиться в том, что такая матрица существует, единственна, в случае к = 0 совпадает с обычной обратной матрицей и обладает следующими свойствами:

1.

А» = Х

7Г1 О О О

Х-1.

2. Пусть матрица X невырождена, а А представима в следующем виде: А = ХВХ'1. Тогда Ав = ХВ°Х~1.

3. [А*)° = {А°у.

4. (АЕ>)Е> = А, тогда и только тогда, когда размеры наибольшего Жорданова блока, отвечающего нулевым собственным значениям, не превосходят 1.

5. Пусть к - размер наибольшего Жорданова блока, отвечающего нулевым собственным значениями. Тогда, для вещественного а

Ап = Кт(А2к+1 + а?1)~1Ак.

а-ИГ '

Отметим, что является ортогональным проектором на образ А, а А°А ортогональный проектор на образ А*. В случае эрмитовой матрицы А, это означает, что Ап совпадает с А^ и Е+ в случае если матрицы исходного пучка перестановочны.

Следует отметить, что псевдообратные матрицы Мура-Пенроуза и Дразина развивались в контексте задачи наименьших квадратов [30], [31], [32], а алгоритмов временной редукции или оценок норм решений задач Коши для систем ОДАУ на их основе не существует.

1.5 Выводы

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

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

Глава 2

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

2.1 Введение

Рассмотрим задачу Коши

ПТ

х(0)=х°, Е— = Ах + /, (2.1.1)

где /(£) - достаточно гладкая п-компонентная векторная функция, А и Е соответственно отрицательно и неотрицательно определенные эрмитовые матрицы порядка п и пучок \Е — А регулярный. Конечные собственные значения такого пучка, т.е. корни уравнения 6.еЬ(ХЕ — А) = 0, являются вещественными отрицательными [27].

Решение рассматриваемой задачи Коши существует и единственно, в том, и только том случае, если

{1-Г*)(Ах° + Ц 0)) = 0, (2.1.2)

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

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

Теорема 2.1. Пусть х - решение задачи Коши (2.1.1), (2.1.2). Тогда при всех £ > О справедливы неравенства

||ТМ*)||2 < се-*%х% + <1 Ге-^||/(т)|Ыт (2.1.3)

Jo

и

\\(1-Г)х(т2<\\А-%\\№\\2, (2.1.4)

где

2\\Е+1|2, с1=\\Е+\\2, к=-Хшо,(А,Е) < 1/(||£||2||А-1||2)

й Атах(Л, Е) означает максимальное конечное собственное значение пучка ХЕ — А.

Наряду с этими оценками, мы выведем нижеследующую оценку нормы вектора

у(Ь)=х(г) + А~1№, (2.1.5)

полезная для анализа исходной системы. Несложно убедиться, что у(Ь) является решением задачи Коши

2/(0) = 0, Е^ = Ау + ЕИ, (2.1.6)

аъ

где

<и

Домножая (2.1.6) слева на Е+ и используя (1.1.4а), получим:

Г^т- = Е+Ау + РК. (И

Можно показать, что у(Ь) лежит в понижающем подпространстве, отвечающем конечным собственным значениям пучка ХЕ — А, а потому Ру = у и следовательно

§ = Е+Ау + РИ. аЬ

Этот подход позволяет разрешить (2.1.6) относительно производной по времени и, таким образом, свести исходную систему дифференциально-алгебраических уравнений (2.1.1) к системе обыкновенных дифференциальных уравнений.

Теорема 2.2. Пусть х - решение задачи Коши (2.1.1), (2.1.2) и у - вектор (2.1.5). Тогда при всех1 > 0 справедливо неравенство

\ть < се-* {||у(0)||2 + ^е-р^/'СОМт} , (2.1.7)

где с и к означают константы, определенные в теореме 2.1.

Доказательству теорем 2.1 и 2.2 посвящен раздел 2 данной главы. В разделе 3 обсуждается численная реализация полученных оценок, а в разделе 4 проводится их сравнение с известной оценкой нормы решения задачи Коши, основанной на уравнении Ляпунова.

Отметим, что согласно формуле Коши [33] решение задачи Коши (2.1.1) с единичной матрицей Е представимо в следующем виде:

х{г) = еых° + Г е^^Дт^т, Уо

откуда можно вывести формулу

у(*) = еыу(0) + А-1 Г(фт.

Используя эти две формулы несложно показать, что оценки (2.1.3) и (2.1.7) достижимы. Например, неравенство (2.1.7) превращается в равенство, если Е и, следовательно, Е+ - единичные матрицы, х° -собственный вектор матрицы А, отвечающий ее минимальному по модулю собственному значению, а /(¿) = х°(р^), где <р - скалярная функция, такая, что </?(£) < 0 и (¿/(¿) < 0. Оценка (2.1.4) очевидно достижима в случае нулевой матрицы Е.

Лемма 2.1. При всех t > 0 справедливы неравенства

а) \\еш+АР\\2 < се~к\ Ь) \\е*Е+АЕ+\\2 <

где к, с и с1 - константы, определенные в теореме 2.1. Доказательство. Из (1.2.1), (1.2.2) и (1.2.3) следует, что

(2.1.8)

ле+а

Г = Р

ешР 0 0 0

Р~\ еш+АЕ+ = Р

ешг 0 0 0

Р\

где 0Т означает главную подматрицу порядка г матрицы И, диагональные элементы которой образуют множество конечных собственных значений пучка АЕ — А. Поэтому неравенства (2.1.8) справедливы с константами с = ||Рг||2||(-Р_1)г||2 и д — ||-Рг||2, гДе Рг и (Р~1)г означают соответственно п х г-матрицы первых г столбцов матриц Р и Р"1, и

к = — Атах(А, Е) = Атт(А, — Е) — Атщ(/П, —ЕА х)

= 1/Атах(-ЕА-\1п) > 1/||£?||2||А-1||2. Но, в силу (1.2.1Ь), \\Е\\2 = ||(Р-1)Г||1, а в силу (1.2.3), ||Я+||2 =

IР,

Г N2-

□

Перейдем к доказательству теорем 2.1 и 2.2. Введем следующие обозначения: х\ = Рх, х2 — (I — Р)х. Умножая (2.1.1) слева на Е+ и используя равенства (1.1.4а), (1.1.2Ь) и (1.2.5а), для х\ можно

вывести следующее уравнение:

Поэтому, в соответствии с формулой Коши,

Xl(t) = etE+AVxQ + f* e(t-r)E+AE+f^dT p г g)

Jo

Неравенство (2.1.3) непосредственно следует из (2.1.9) и леммы 1.1.

Умножая теперь (2.1.1) слева на (I — V)A~l и учитывая, что, в силу (1.2.5Ь) и (1.1.2а), (/ — V)A~1E — 0, получим следующее равенство:

О = + (/ - V)A~lf. (2.1.10)

Поскольку А - эрмитовая отрицательно определенная матрица и каждая из двух матриц в правой части тождества

А"1 = VA~lV* + (/ - V)A-\I - V*)

эрмитовая неположительно определенная, справедливо неравенство

\\а-% >ш- - щь = ш - v)A-%.

Следовательно,

\\x2(t)h = \\(1 - r)A-lf(t)\\2 < \\A-%\\№h,

что доказывает неравенство (2.1.4). Теорема 2.1 доказана.

Отметим, что из равенств (2.1.9) и (2.1.10) непосредственно следует, что условие (2.1.2) является необходимым и достаточным для существования и единственности решения задачи Коши (2.1.1).

Для доказательства теоремы 2.2 перепишем (2.1.1) следующим образом:

2,(0) = + A-V(O), Е^ = Ау + EA~lf. (2.1.11)

Умножая (2.1.11) слева на (/ — 7>)А~1 можно установить, что у = Ту. Поэтому, умножая (2.1.11) слева на Е+ и используя формулу Коши, получим

у{1) = е*Е+АГу( 0) + Г е^Е+АТА-1!'{т)<1т. (2.1.12)

Jo

Неравенство (2.1.7) непосредственно следует из (2.1.12) и (2.1.8а). Теорема 2.2 доказана.

2.2 Устойчивость

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

^х

Е— = Ах, 2.2.1

си

с существованием неотрицательно определенного решения обобщенного уравнения Ляпунова

ХЕ+А + АЕ+Х =-Т*СГ, Х = Г*ХГ, (2.2.2)

при любой положительно определенной матрице С.

Устойчивость системы (2.2.1) по Ляпунову понимается в смысле устойчивости по Ляпунову нулевого решения её задачи Коши с начальным значением х0, т.е.

Уе > 035(£) > ОУяо : 1Ы1 < 6(е)Ы > 0 ||х(ж0,011 <

Теорема 2.3. Система (2.2.1) устойчива по Ляпунову тогда и только тогда, когда обобщенное уравнение Ляпунова (2.2.2) имеет единственное неотрицательно определенное решение при любом С = С* > 0.

Доказательство. Заметим, что х(£) = еш+АТ>х°) где х° некоторый п-компонентный вектор, решение системы (2.2.1). Учитывая (1.1.2(1) и тот факт, что х — Тх

-1г{Хх,х) = (ХЕ+Ах,х) + (АЕ+Хх,х) =

Сьи

= —(Сх,х) < —Хт[П(С,Х) (Хх,х).

Поэтому,

(Хх,х) < е-х^{с'х)\Хх°,х°), * > 0. Воспользуемся оценками

<11X112(0:,®),

справедливыми для всех х = Тх, где правое неравенство очевидно, а левое доказывает следующая цепочка

(х,х) = (Х+Хх,Х+Хх) = {Х+{Х+)1'2Хх,{Х+У'2Хх)

< \\Х+ШХ+)1'2Хх,{Х+)1'2Хх) = \\Х+ЫХх,Х+Хх) = \\Х+\\2(Хх

Выбирая С = —2А, X = Е мы завершаем доказательство следующего неравенства:

||^)||2<се-*||а:0||2, (2.2.3)

Список литературы диссертационного исследования кандидат наук Овчинников, Георгий Викторович, 2013 год

Литература

1. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жёсткие и дифференциально-алгебраические задачи. М. and Мир, 1999.

2. Knockaert L., Zutter D. De. Laguerre-SVD reduced-order modeling // IEEE Trans. Microwave Theory Techn. 2000. T. 48, № 9. C. 1469-1475.

3. Knockaert L., Zutter D. De. Stable Laguerre-SVD reduced-order modeling // IEEE Trans, on Circuits and systems. 2003. T. 50, № 4. c. 576-579.

4. Knockaert L., Zutter D. De. Laguerre-based bandlimited reduced-order modeling // IEEE Trans, on Microwave Theory and Techniques. 2004. T. 52, № 9. c. 2321-2329.

5. Model Reduction in the Time-Domain using Laguerre Polynomials and Krylov Methods / Y. Chen, V. Balakrishnan, C-K. Koh [и др.] // Proceedings of the 2002 Design, Automation and Test in Europe Conference and Exhibition. 2002.

6. Eid R. Time Domain Model Reduction by Moment Matching. TU Munchen, 2009.

7. Годунов С.К. Современные аспекты линейной алгебры. Научная книга, 1997.

8. Годунов С. К., Нечепуренко Ю. М. Оценки для главной и жесткой компонент на основе интегрального критерия качества ди-

хотомии // Журнал вычислительной математики и математической физики. 2000. Т. 40, № 1. С. 35-42.

9. Нечепуренко Ю. М. Оценка нормы матрицы Грина через интегральный критерий качества дихотомии и границы хаусдорфова множества // Математические заметки. 2002. Т. 71, № 2. С. 232— 238.

10. Nechepurnko Y.M., Sadkane М. A generalization of matrix inversion with application to linear differential-algebraic systems // Electronic Journal of Linear Algebra. 2012. № 23. C. 831-844.

11. Нечепуренко Ю.М., Овчинников Г.В. Верхние оценки норм решений эрмитовых систем обыкновенных дифференциальных и алгебраических уравнений // Уфимский математический журнал. 2009. Т. 1, № 4. С. 125-133.

12. Nechepurenko Y.M., Ovchinnikov G.V. An estimation of voltage settling time for RC circuits // Russian Journal of Numerical Analysis and Mathematical Modelling. 2010. T. 25, № 3. C. 253-259.

13. Mita R., Palumbo G. Propagation delay of an RC-circuit with a ramp input: An analytical very accurate and simple model // International Journal of Circuit Theory and Applications. 2009. T. 37, № 9. c. 987-994.

14. Friedman E.G., Mulligan Jr. J.H. Ramp input response of RC tree networks // Analog Integrated Circuits and Signal Processing. 1997. T. 14,№ 1/2. C. 53-58.

15. Gupta R., Tutuianu В., Pileggi L. The Elmore delay as a bound for RC trees with generalized input signals // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1997. T. 16, № 95. C. 104-114.

16. Celik M., Pileggi L., Odalasioglu A. 1С interconnect analysis. Kluver Academic Publishes, 2012.

17. Sheldon X.-D., Lei He T. Advanced Model Order Reduction Techniques in VLSI Design. Cambridge University Press, 2007.

18. Power-Estimation On-Chip VLSI Distributed RLC Global Interconnect Using Model Order Reduction Technique / K. Rajib, V. Md. Maheshwari, A. K. Maqbool [и др.] // International Journal of Computer Applications. 2010. T. 14, № 19. c. 92-97.

19. Потягалова А. С. Общие свойства и модификации алгоритмов редукции // Нано- и микросистемная техника. 2008. № 7. С. 1519.

20. Schilders W. Н. A. The Need for Novel Model Order Reduction Techniques in the Electronics Industry. Lecture Notes in Electrical Engineering, Springer, 2012.

21. Овчинников Г.В. Верхние границы норм решений эрмитовых систем обыкновенных дифференциальных и алгебраических уравнений // 52-я научная конференция МФТИ. 2009.

22. Овчинников Г.В. Численный анализ и решение эрмитовых систем обыкновенных дифференциальных и алгебраических уравнений // 53-я научная конференция МФТИ. 2010.

23. Нечепуренко Ю.М., Овчинников Г.В. Решение эрмитовых систем дифференциально-алгебраических уравнений на основе функций Лагерра // Международная конференция «Математические идеи П.Л.Чебышева и их приложение к современным проблемам естествознания». 2011.

24. Овчинников Г.В. Современные технологии редукции и их применение в разработке сверхбольших интегральных схем // 54-я научная конференция МФТИ. 2011.

25. Nechepurenko Y.M., Ovchinnikov G.V. An algorithm for solving the Hermitian ODAEs systems // International conference on Matrix Methods in Mathematics. 2011.

26. Овчинников Г.В. Применение спектрально-псевдообратных матриц к анализу и численному решению линейных эрмитовых систем обыкновенных дифференциальных и алгебраических уравнений. // 55-я научная конференция МФТИ. 2012.

27. Golub G.H., Van Loan C.F. Matrix computations. The John Hopkins University Press, 1991.

28. Drazin M. P. Pseudo-inverses in associative rings and semigroups // The American Mathematical Monthly. 1958. № 65. C. 506-514.

29. Penrose M. A generalized inverse for matrices // Proceedings of the Cambridge Philosophical Society. 1955. № 51. C. 406-313.

30. Penrose M. On best approximate solution of linear matrix equations // Proceedings of the Cambridge Philosophical Society. 1956. № 52. C. 17-19.

31. Campbell S.L, Meyer C.D. Generalized Inverses of Linear Transformations. Dover, New York, 1979.

32. Meyer C.D., Plemmons R.J. Convergent powers of a matrix with applications to iterative methods for singular linear systems // SIAM J. Numer. Anal. 1977. № 14. C. 699-705.

33. Годунов С.К. Обыкновенные дифференциальные уравнения с постоянными коэффициентами. Изд-во Новосиб. ун-та, 1994.

34. Templates for the solution of algebraic eigenvalue problems. Practical guide. / Zh. Bai, J. Demmel, J. Dongarra [и др.]. SIAM, 2009.

35. LAPACK Users Guide / под ред. E. Anderson, Z. Bai, C. at al. Bischof. SIAM, 1992.

36. Horn R.A., Johnson C.R. Matrix analysis. Cambridge Univercity Press, 1986.

37. Kerns K.J., Yang A.Т. Stable and efficient reduction of large multiport RC networks by pole analysis via congruence transforms // IEEE Trans. Computer-Aided Desing. 1997. T. 17, № 7. C. 734-744.

38. Kunkel P., Mehrmann V. Differential-Algebraic Equations. UMS Publishing House, 2006.

39. Суетин П.К. Классические ортогональные многочлены. Наука, 1979.

40. Handbook of Mathemathical Functions / под ред. М. Abramowitz, I.A. Stegun. Dover, 1964.

41. Stykel Т. Balanced truncation model reduction for semidiscretized Stokes equation // Linear Algebra Appl. 2006. № 415. C. 262-289.

42. Gallivan K., Grimme E., Van Dooren P. A rational Lanczos algorithm for model reduction // Numer. Algor. 1996. № 12. C. 3363.

43. Kerns K.J., Yang A.T. Preservation of passivity during RLC network reduction via congruence transforms // IEEE Trans. Computer-Aided Desing. 1998. T. 16, № 7. C. 582-590.

44. Benner P., Mehrmann V., Sorensen D.C. Dimension Reduction of Large-Scale Systems. Springer-Verlag, Berlin/Heidelberg, 2005.

45. Guoxiang G., Pramod P. Lee E.B. Approximation of Infinite-Dimensional Systems // IEEE Trans. Computer-Aided Desing. 1989. T. 34, № 6. C. 610-618.

46. Antoulas A. C. Approximation of Large-Scale Dynamical Systems. SIAM, 2005.

47. Grimme E.J. Krylov projection methods for model reduction. University of Illinois, 1997.

48. Szego G. Orthogonal Polynomials. American Mathematical Society, 1959.