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

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

Овчинников Георгий Викторович

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

систем

Специальность 01.01.07 — Вычислительная математика

2 8 НОЯ 2013

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2013

005540092

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования "Московский физико-технический институт (государственный университет)"

Научный руководитель: доктор физико-математических наук, доцент

Нечепуренко Юрий Михайлович

Официальные оппоненты: Корнев Андрей Алексеевич

Защита состоится 18 декабря 2013 г. в 1400 часов на заседании диссертационного совета Д 002.045.01 в Федеральном государственном бюджетном учреждении науки Институте вычислительной математики Российской академии наук (ИВМ РАН), расположенном по адресу: 119333, г. Москва, ул. Губкина,

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институте вычислительной математики Российской академии наук.

доктор физико-математических наук, профессор кафедры вычислительной математики механико-математического факультета МГУ им. М. В. Ломоносова,

Замарашкин Николай Леонидович кандидат физико-математических наук, старший научный сотрудник ИВМ РАН

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт прикладной математ им. М.В. Келдыша РАН

Д. 8.

Автореферат разослан

2013 года.

Ученый секретарь

диссертационного совета Д 002.045.01 доктор физико-математических наук.

Бочаров Г.А.

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

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

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

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

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

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

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

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

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

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

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

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

4

Ближайшими аналогами предложенного алгоритма редукции являются методы, основанные на использовании многочленов Лагерра для построения Крыловского подпространства. В этих методах предполагается принадлежность передаточной функции пространству Харди И2, что эквивалентно рассмотрению пучков с невырожденными матрицами Е или, другими словами, пучков с индексом нильпотентности 0, в то время как предложенный в диссертационной работе подход позволяет работать с пучками индекса 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

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

А Е-А,

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

Вводится матрица

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

lim Е+ = Е+,

где

Е+ = (Е- аА)~1Е(Е - аА)~\

и £+ < Е+, если а > ß > 1/Ат1п(Л, Е).

Отмечены отличия псевдообратных матриц Дразина AD и Мура-Пенроуза

Ai

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

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

a)XE = V, Ь) EX = V*, с)ЕХЕ = Е, d) ХЕХ = X, (1)

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

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

Т> = — I {\Е-А)~1Е<1\

2т Jг

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

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

Во второй главе рассматривается задача Коши

х(0) = х°, Е^ = Ах + /, (2)

ал

где /(¿) - достаточно гладкая п-компонентная векторная функция, Ац Е соответственно отрицательно и неотрицательно определенные эрмитовые матрицы порядка п и пучок \Е — А регулярный. Решение рассматриваемой задачи Коши существует и единственно, в том, и только том случае, если

{I ~ 'Р*)(Ах° + /(0)) = 0. (3)

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

Теорема 2.1. Пусть х - решение задачи Коши (2), (3). Тогда при всехЬ > 0 справедливы неравенства

\\Тх{1)Ь < се~к1\\х% + й[* е-^-т>||/(т)Мт

J о

и

\\(1-г)хт2<\\А-%\\т\\2,

где

с=^\\Е\\2\\Е+\\2, <1=\\Е+\\2, к=-\тах(Л,Е)<1/(\\Е\\2\\А-%), а -^тах(А Е) означает максимальное конечное собственное значение пучка

\Е — А.

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

у{1)=х{Ь)+А-^{Ь)1 (4)

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

у(0) = 0, Е^ = Ау + ЕН, (5)

где

Л

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

Т^- = Е+Ау + Тк. М

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

М

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

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

< се

2 Ь

{||У(0)||2 + ^еИИ-7'(т)Ыт},

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

Кроме того, обсуждаются детали численной реализации этих оценок и проводится сравнение с аналогичной оценкой для систем ОДУ, основанной на уравнении Ляпунова.

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

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

В таких задачах считается известным вектор напряжений в портах ир(Ь), а вектор напряжений во внутренних узлах щ„(¿) - подлежащим определению. Пусть и,-„(0) = у.{п = 0, ыр(0) = 0 и в момент времени £ = О начинает подаваться непрерывный входной сигнал ир(£) с кусочно-непрерывной и ограниченной производной, и при некотором т > О входной сигнал устанавливается: = ир(т) при £ > т. Тогда существует конечный предел

Для заданных ир{1) и е > 0 определим Те(ир), как наименьшее Т > О, для которого справедливо неравенство

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

В данной главе получена верхняя оценка Те{ир).

Моделирование КС-схем на основе законов Ома и Киргхофа сводится к решению задач Коши для линейных систем обыкновенных дифференциальных и алгебраических уравнений следующего вида:

где ир{{) е 11Р; «,•„(£) € И" являются, соответственно, векторами напряжений в портах и напряжений во внутренних узлах; С, Ср и С?р - соответственно матрицы емкостей и величин обратных сопротивлениям. Причем, Ср и - матрицы размеров пхр, аСиб - квадратные симметричные матрицы порядка п, имеющие неотрицательные диагональные элементы и обладающие нестрогим диагональным преобладанием

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

Теорема 3.1. Если в рассматриваемой КС-схеме в каждый внутренний узел можно попасть из каждого портового узла двигаясь только по ребрам резисторам и входной сигнал обладает свойствами описанными ранее, то

щп{ оо) = 11ир(т),

Пт щп(Ь) = щп(оо).

Щп(£)-щп{ оо)||2<£, ¿>Т + Т.

С^ + Ср^ + Сщп + Орир = О,

(И

ей

а

где

К = 1/Ат.ЛСС-1),

т

,||С+||2 J eK^\\(S - R)üp(s)\\2ds,

о

Атя(.) означает максимальное собственное значение, ат - время установления входного сигнала.

Расчеты со схемами из промышленного дизайна микроэлектроники в большинстве случаев дают T*st < 2Т€(ир).

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

dx

х(0) = О, Е— = Ах + Ви, (6)

где x(t) - n-компонентная неизвестная векторная функция, u(t) - р-компонептиая заданная векторная функция (р <С п), В - прямоугольная матрица размера п х р, а А и Е квадратные отрицательно и неотрицательно определенные эрмитовы матрицы порядка п, соответственно. Такие дифференциально-алгебраические системы возникают в различных приложениях, например, при анализе влияния неидеальности соединений в интегральных схемах на прохождение сигнала.

Предполагается, что векторная функция u{t) непрерывная и кусочпо-непрерывпо дифференцируемая при £ > Ос ограниченными левыми и правыми производными, причем м(0) = 0 и существует некоторое т > О такое, что du/dt = 0, t > т.

В данной главе предлагается эффективный алгоритм вычисления приближенного решения задачи (6) на заданном временном интервале [О, Т}. Алгоритм основан на переходе с помощью следующей замены

y{t) = x{t) + A~lBu(t), от задачи Коши (6) к задаче вида (5) с

, 1 „du h = A B—, dt

Приближенное решение уа задачи Коши (5) ищется в виде конечного ряда по сверткам производной du/dt с базисными функциями

m— 1

ya(t) = ДХа(*)>

k—0

где

f du

Vk,a(t)= / ^A-,o(i-s)-J(s)ds, (7)

0 11

а > 0 - параметр алгоритма, a - некоторые прямоугольные матрицы размера пхр, зависящие только от матриц Ей Аи параметра а. Эти матрицы могут быть выражены следующим образом: R = А~гВ, Щ = M"R,

М£ = а[(Л - аЕ)~1А]к{аЕ - А)-1Е. (8)

В качестве базисных функций выбираются

LKa{t) = Lk(at), (9)

где

мо -

суть многочлены Лагерра, т.е. многочлены ортонормированные на [0, +оо) с весом ехр(—t):

оо ,

Je-%№*№={lkkt\:

о

Основным результатом данной главы является следующая теорема.

Теорема 4.1. Решение задачи Коши (5) существует, единственно и для пего справедливо представление

°° rt

y(t) = V Mfc° / LKa(t - s)h(s)ds, (10)

fc=о Jo

с любым параметром a > 0, где Mg - матрицы (8), а Ька ~ многочлены (9).

Следствие. Решение задачи Коши (6) существует, единственно и для него справедливо представление

оо

x(t) = J2R>k,a{t)~Ru{t). (И)

fc=0

Приближенное решение

т-1 çt

yQ(f) = VM£ Lk,a(t-s)h(s)ds (12)

k=о Jo

задачи Коши (5), получается из (10) отбрасыванием всех слагаемых начиная с m + 1-го. Отметим, что уа(0) = 0 и, следовательно, это приближенное решение удовлетворяет требуемому начальному условию.

Тогда, приближенное решение исходной задачи Коши (6) можно представить как

x{t) = ya(t) - Ru(t), (13)

где

771—1

ya{t) = Y, R>kAt)-k=0

Следующая теорема устанавливает оценку погрешности приближенного решения:

Теорема 4.2. Пусть у - точное решение задачи Коши (5), ауа - приближенное, даваемое (12). Тогда для погрешности 5уа = уа — у, справедлива следующая оценка:

<d í e-K{t-s)\\ga(s)\\2ds, t> О, Jo

\\0Уа\Ч\\2 ^ где

9а = Е-^- - Ауп - Е1г

является невязкой приближенного решения,

<1 = \\Е+\\2, К = —Лшах(Л, Е) < 1/(Ц£7||2ЦА-1||2),

« Е) означает максимальное конечное собственное значение пучка

\Е- А.

Следствие. Для погрешности 5х = х — х в обозначениях предыдущей теоремы справедлива следующая оценка:

||М*)1|2<<* С е-*-'Цд{8)\\г<18,г> 0.

Jo

Здесь

„с?х , „ „ „¿Уп ,, и

д = Е— - Ах-Ви = Е-р - Ауа - ЕЯ—, dt dt dt

и является невязкой приближенного решения (13).

Для ускорения вычисления векторов (7) предложен метод типа "разделяй и властвуй основанный на следующем представлении многочленов Ла-герра

к 3=0

обобщенный многочлен Лагерра.

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

В заключении приведены основные результаты работы:

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

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

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

Публикации автора по теме диссертации

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

2. 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.

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

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

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

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

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

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

Овчинников Георгий Викторович

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 14.11.2013. Формат 60x84 1/16 Усл. печ. л. 1,00. Тираж 100 экз. Заказ №365

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)"

141700, Московская область, г. Долгопрудный, Институтский переулок, 9 Отдел оперативной полиграфии «Физтех-полиграф» тел.:(495)408-84-30

Министерство образования и науки Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)" Факультет проблем физики и энергетики

042014^049

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

Овчинников Георгий Викторович

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

01.01.07 — Вычислительная математика

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук Нечепуренко Юрий Михайлович

Москва 2013

Содержание

Введение 5

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

0.2 Цель........................................................6

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

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

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

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

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

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

0.9 Публикации................................................11

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

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

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

1.1 Введение....................................................12

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

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

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

1.5 Выводы....................................................21

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

2.1 Введение.......................... 22

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

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

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

2.5 Выводы.......................... 35

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

3.1 Введение....................................................36

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

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

3.4 Реализация................................................41

3.5 Выводы....................................................45

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

4.1 Введение....................................................46

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

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

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

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

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

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

4.8 Близкие алгоритмы редукции и сравнение с ними . . 63 4.8.1 Передаточная функция и пространства Харди 66

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

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

4.9 Выводы....................................................73

Заключение 82

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

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

Литература 86

Введение

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.

�