Метод сингулярной функции для проблем собственных значений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

РГБ ОД

1 1 \\ОН ^^ Российская академия наук

' Институт вычислительной математики

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

НЕЧЕПУРЕНКО Юрий Михайлович

МЕТОД СИНГУЛЯРНОЙ ФУНКЦИИ ДЛЯ ПРОБЛЕМ СОБСТВЕННЫХ ЗНАЧЕНИЙ

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

АВТОРЕФЕРАТ

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

МОСКВА 1996

Работа выполнена в Институте вычислительной математики РАН

Официальные оппоненты: доктор физико-математических наук, профессор ИЛЬИН В.П., доктор физико-математических наук, профессор ЛЕБЕДЕВ В.И.,, доктор физико-математических наук, профессор ЛИФАНОВ И.К.

Ведущая организация: Институт математики СО РАН

7 7 У' ¿tS**

Защита состоится & ^¿ö^Jß ^ i QQfj года на заседании

Специализированного совета Д. 003.45.01 Института вычислительной математики РАН по адресу: Москва, Ленинский проспект 32-а.

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

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

года

Ученый секретарь -Специализированного совета кандидат физико-математических наук

(р/оМ-

С.А. ФИНОГЕНОВ

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

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

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

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

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

Таким образом, несмотря на наличие большого числа алгоритмов, разработка новых подходов к решению частичных проблем собственных зна-

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

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

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

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

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

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

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

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

сти выполнимо в рамках той же вычислительной технологии.

Аппробация работы. Результаты диссертации обсуждались на семинарах Института вычислительной математики РАН (Москва, 1985-96), Института проблем кибернетики РАН (Москва, 1986), Вычислительного центра РАН (Москва, 1986, 1993), Института математики СО РАН (Новосибирск, 1993,1996), Вычислительного Центра СО РАН (Новосибирск, 1996), Кафедре математики физического факультета МГУ (Москва, 1995), Кафедре вычислительной математики механико-математического факультета МГУ (Москва, 1995).

Результаты диссертации докладывались на Всесоюзной школе " Оценки сложности вычислений" (Кулдига, 1985), VII Всесоюзной конференции по вычислительным методам линейной алгебры (Москва, 1985), Всесоюзной школе-семпнаре " Численные методы для высокопроизводительных ЭВМ" (Фунзе, 1988), Школе-семпнаре "Теория приближения функций" (Свптязь, 1989), Всесоюзной конференции "Оптимизация вычислений" (Одесса, 1989), Советско-американском совещании по численным методам линейной алебры (Москва, 1990), Всесибпрской школе по вычислительной математике (Красноярск, 1991).

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

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка литературы (159 наименований); изложена на 201 странице и включает 6 рисунков и 8 таблиц.

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

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

Во-введении обосновывается актуальность темы и дается обзор содержания диссертации.

В первой главе, которая фактически является продолжением введения, сформулированы, используемые на протяжении всей работы без дополнительных пояснений, известные понятия и результаты спектральной теории матриц многочленов А € С [г]"*", где С [г] означает кольцо многочленов от одного переменного над полем комплексных чисел С .

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

с!е«;(А/ - А(г)) = 0.

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

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

В разделе 2.2 сформулирована теорема о приведении матрицы многочленов к блочной жордановой форме над полем рациональных функций С(г) и локальная теорема о приведении матрицы многочленов к нормальной жордановой форме над полем частных кольца аналитических функций. Эти две теоремы являются следствием более общих теорем алгебры о приведении матрицы с элементами из произвольного поля к нормальным формам. Указана связь неприводимых компонент полной собственной функции с блочной формой Жордана и отмечено, что значение матрицы многочленов во всех точках комплексной плоскости, за исключением, может быть, некоторого их конечного числа, имеют одну и ту же жорданову структуру.

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

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

А € Щхп, Ан = А,

где ГсЯ — заданный интервал, а Кг — кольцо аналитических функций Г —► С. Сформулированна известная теорема о приведении такой матрицы к диагональному виду преобразованием подобия с унитарной матрицей аналитических функций. Рассмотрена задача о вычислении первых и вторых производных собственных функций.

Обозначим через € Спхп(к = 0,1,...) коэффициенты разложения

матрицы А в степенной ряд по х — xq в окрестности точки хц £ Г:

Л(х) = £ (г- *о)Ч, At = А? = ~(хо) к>о к\ ах

и примем следующие обозначения:

т\ < ... < тд — попарно различные собственные значения матрицы Ао; mi,..., mq — их кратности (mi +.. . + mq = п); Ui — матрица размера п х mi, столбцы которой образуют ортонормированный базис в собственном подпространстве

ппЦА0 - Til) с С". т,;i<...< Tiqi — попарно различные собственные значения матрицы

Gi = UtH A iUi\

m,i,..., m,g. — их кратности (тц + . •. + m;i( = ш,); {7,;- — матрица размера ш,- х rriij, столбцы которой образуют ортонормированный базис в собственном подпространстве

null(G; - TijI) с cm'.

r.'j! < ... < Tijmij — полный набор собственных значений матрицы

Gi, = UjjU?(A2 - А\(А0 - Til)+Ai)UiUij,

где I означает единичную матрицу, а В+ — матрицу, псевдообратную матрице В.

Теорема 2.4.2. Пусть собственные функции fii,..., /i„ эрмитовой _ матрицы аналитических функций А упорядочены так, что fJ-i(x) < ... < цп{х) при всех х € [яо, 4- £] для некоторого е > 0. Тогда

Мхо) = Т{, ^Ы = rih = Tijk,

где

¡-1 j-i ¡'=1 j'=i

при всех fc = l,...,my; j = 1,... i = l,...,q.

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

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

Собственные функции матриц многочленов общего и специального вида и матриц аналитических функций изучаются во многих работах, в том числе, — в работах автора [3,6]. В одном из параграфов монографии [6] сделана попытка дать систематическое изложение основных свойств собственных функций. Вторая глава диссертации представляет собой этот параграф в несколько переработанном виде. Отметим, что теорема 2.4.3 и часть теоремы 2.4.2 о вычислении вторых производных — результаты, полученные автором.

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

Пусть А £ C[z]"x" — квадратная матрица многочленов порядка п и /ь ..., /п — функции С —» R, значения которых при каждом фиксированном 2 е С удовлетворяют неравенствам fi(z) < ... < fn(~) и образуют спектр эрмитовой матрицы

H(z)=A(z)HA{z), (1)

то есть являются алгебраически полным набором квадратов сингулярных чисел матрицы A(z).

Функцию ¡к будем называть к-й сингулярной функцией матрицы многочленов А.

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

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

Теорема 3.2.1. Пусть А 6 C[z]nxn — регулярная матрица многочленов, 2» — некоторое ее конечное собственное значение и qi > ... > qr — полный набор его -индексов. Тогда

fk(z) X \Z - (2 -Н. Zt)

при k = 1,... ,r.

Теорема 3.2.3. Пусть регулярная матрица многочленов А € С[г]"х" имеет бесконечное собственное значение геометрической кратности г

и 1\ > • • • > Яг — полный набор его индексов. Тогда

Д(г)х|2|*"2« (*-оо)

при к = 1,..., г, гс?е 7 = с^.4 — степень матрицы многочленов А.

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

Теорема 3.2.2. Пусть (в обозначениях теоремы 3.2.1) q\ — индекс кратности р. Тогда найдутся такие положительные а\,... ,ар, что

/*(■*) = а*|г - г»|2?1 + 0(|г - 2»|2?1+1) (г - г.)

при к = 1,...,р.

Теорема 3.2.4. Пусть (в обозначениях теоремы 3.2.3) q\ — индекс кратности р. Тогда найдутся такие положительные а% < ... < ар, что

Ш = а*[2|2^2" + СЧИ27-2"-1) (г - оо)

при к= 1

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

Непрерывную функцию /:£)—+ И, где И — открытое множество в С, называют К-аналитической (дифферецируемой) пли вещественно аналитической (дифферецируемой) в точке хо + ¿Уо € -О, если в точке

(го, 2/о) е п = {(*, л) е Я2 : х + гу £ Б}

аналитична (дифферецнруема) функция }<р : П—»И, где (р(х, у) = х + гу. Функцию

дг дх ду'

эквивалентную градиенту функции /V, называют градиентом функции / и обозначают V/.

Пусть Nt(z) при любом фиксированном : £ С означает кратность сингулярного числа fk{z)112 матрицы A(z) или, что то же самое, кратность собственного значения fk(z) эрмитовой матрицы (1).

Рассмотрим множество точек Dt С С, имеющих окрестности, в которых величина ATt(z) постоянна:

2о £ Dk

$ (2) Эе > 0 : Vz е Uc(z0) : Nt(z) = const.

Обозначим через G множество плоскпх действительных алгебраических кривых в С и их частей, т.е.

Г е G

$

3QeR[x,y](Q^0): x + iye Г =>Q(x,y)=0.

Теорема 3.3.1. Множество Dt открыто, всюду плотно в С, а его граница dDt £ G. Функция — R- аполитична в Dt.

Пусть г» — некоторое конечное собственное значение регулярной матрицы многочленов .4, г — его геометрическая кратность, q — максимальный индекс и р — кратность индекса q. Обозначим через fa > ... > /?„ полный набор сингулярных чисел матрицы B(z*), где

B(z) = d1(z)A(z)~1

и <¿1 — инвариантный множитель наибольшей степени матрицы многочленов А.

Теорема 3.3.2. Если сингулярное число fa матрицы B(zt) — простое, то сингулярная функция ft регулярной матрицы многочленов А И-аналитична в точке zt! где k = 1,... ,р.

При г = 1 (а значит, и р = 1) условие теоремы 3.3.2 выполнено и собственное значение z„ принадлежит множеству D\. Если г > 1 и условие теоремы 3.3.2 выполнено при некотором к, то z„ Dj (j = 1,..., г), поскольку в этом случае в точке 2, разрывна каждая из функций Nj (j = 1,..., г). Таким образом, теорема 3.3.2 дополняет теорему 3.3.1 и позволяет установить для регулярной матрицы многочленов R-аналитичность первых сингулярных функций в некоторых случаях, не охваченных этой теоремой.

Следствие 3.3.1. Если максимальный индекс собственного значения г» простой, т.е. р = 1, то сингулярная функция f\ JL-аполитична в точке 2».

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

Теорема 3.3.3. Если матрица многочленов А £ С[г]"х" регулярна и не имеет бесконечного собственного значения, либо имеет, но среди его индексов нет равных Ле^А, то каждое из множеств

£)к = {геОк: * = 1,...,п,

открыто, всюду плотно в С, а его граница принадлежит множеству

В разделе 3.4 получены асимптотические равенства для градиентов сингулярных функций регуляной матрицы многочленов в окрестности собственных значений, аналогичные асимптотическим равенствам из теорем 3.2.2 и 3.2.4.

Пусть 2* — некоторое конечное собственное значение регулярной матрицы многочленов А (Е С[2]пхп,.д — его максимальный индекс, р — кратность индекса д, — к-я сингулярная функция этой матрицы многочленов и

= {г € С : /к — К — дифференцируема в г}.

Отметим, что множество Г>£ содержит множество и, следовательно, оно всюду плотно в С, а его граница дИ\ 6 С.

Теорема 3.4.1. При любом к : 1 < к < р, справедливо асимптотическое равенство

ЧМг) = + |2') (г е = * - - 0).

Аналогичные асимптотические равенства имеют место и в окрестности бесконечного собственного значения.

Теорема 3.4.2. Пусть регулярная матрица многочленов А € С[;г]пхп имеет бесконечное собственное значение, д — его максимальный индекс и р — кратность индекса д. Тогда

= (2у - 2Ч)~!к(г) + 0(|г|2г~2?~2) (г € £>£, 2 - оо)

при всех к = 1,...,р.

Раздел 3.5 посвящен вычислению производных по направлению и градиентов. Сформулирована теорема об аналитичности по направлению.

Функцию / : И —»■ К, где О — открытое множество в С, называют аналитической в точке ¿о € П) по направлению е Е С, если функция = /(¿о + ев)($ £ Я, 2о + ее £ £>) аналптична справа в точке 5 = 0, т.е. предсгавима в некоторой неотрицательной полуокрестности нуля абсолютно сходящимся рядом по степеням

Теорема 3.5.1. При любых фиксированных 6 С функция = /¿(¿о + Е К) аналитична во всех точках множества И, кроме,

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

Приведены явные матричные формулы для вычисления первой и второй производных по направлению.

Теорема 3.5.2. Пусть /*>,...,/*<+р- 1 — полный набор сингулярных функций, принимающих в точке го £ С значение /к(~о) (к' < к < к' + р— 1). Тогда набор действительных чисел

— это спектр матрицы

У^ЫП, (3)

где Н(г) — матрица (1), а У* € С"*р — любая матрица столбцов, образующих ортонормированный базис в

пи11(Л(гоК-ЯЫ) (4)

— собственном подпространстве матрицы Н(го), отвечающем ее собственному значению /¡¡(га).

Теорема 3.5.3. Пусть /*»,...,/¡ь"+?-1 — полный набор сингулярных функций, принимающих в точке 2ц £ С значение /к(¿о) и имеющих в этой точке одинаковую с /ь производную по направлению е 6 С (к" < к < /с" + д — 1). Тогда, в обозначениях теоремы 3.5.2, набор действительных чисел

— это спектр матрицы

где V* £ С"*' — любая матрица столбцов, образующих ортонормированный базис в собственном подпространстве матрицы (3), отвечающем ее собственному значению

Получены достаточное условие, прн котором производная сингулярной функции ft(z) по направлению е 6 С и ее градиент связаны равенством

2 -^(z0) = eVfk(z0) + eVfk(z0), (5)

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

Матрицу (3) можно записать следующим образом:

= + (6)

где

Отметим, что матрица скалярная, т.е. диагональная с равными диагональными элементами, при ло 6 Дь, где £>* —■ множество (2), т.е. почти при всех г0.

Теорема 3.5.4. В обозначениях теоремы 3.5.2 скалярностъ матрицы Ль является достаточным условием существования градиента сингулярной функции Д и справедливости равенства (5) при любом е 6 С, а в случаях к = к' и к' 1 это условие является также и необходимым.

Следствие 3.5.1. Для сингулярной функции /1 равенство (5) справедливо при любом е в том и только том случае, когда для любого нормированного столбца V из подпространства (4)

Л А

У/^о^НгоМ^ЫгО. (?)

Таким образом, для вычисления градиента сингулярной функции /1 в тех точках го, в которых он существует и связан с производной по направлению равенством (5), нет необходимости определять ортонормиро-ванный базис в подпространстве (4). Достаточно найти любой ненулевой вектор пз этого подпространства, нормировать его и воспользоваться формулой (7).

Для сингулярной функции (к > 2) скалярность матрицы Як, вообще говоря, не является необходимым условием справедливости равен-

ства (5). Поэтому аналогичный способ вычисления градиента будет давать верный результат не во всех, но почти во всех точках, в которых это равенство справедливо (заведомо в точках ~о € Д-).

Далее рассмотрпвается более общий случай нормальной матрицы т.е. унитарно подобной диагональной. Если матрица И^ нормальная и г\,..., гр — ее спектр, то набор производных по направлению е 6 С всех сингулярных функций, принимающих в точке го значение Д(го), совпадает с точностью до перестановки элементов с набором

е?] + ёГ], ] = 1,..., р. (8)

Верно и обратное утверждение.

Теорема 3.5.5. Если спектр матрицы (6) при любом е £ С — это набор (8), то матрица Щ нормальная, аг\,...,гр — ее спектр.

Итак, если матрица Щ нормальная, то, в условиях теоремы 3.5.2, производная по направлению е спнгулярной функции ^ — это к — к' + 1 минимальное число из набора (8). В частности, для спнгулярной функции отсюда следует, что

^ г ^ г

-¿(2о) = тт(ег' + ёг,), пип-^о) = -2|г|,

где г означает максимальное по модулю собственное значение матрицы Е.\ (этот мгаимум достигается при е = —г/(г[). Таким образом, в данном случае вычисление производной по любом}' заданному направлению е € С, а также вычисление минимальной из этих производных при всех |е| = 1 сводится к вычислению собственных значений матрицы Д}.

Отметим, что при любом го £ С

и достигается при е = — р/\р\, где р = и'), а ад — любой нормиро-

ванный вектор максимизирующий |(Д1и>,к;)|.

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

Обозначим через д'Ик подмножество множества сШ*- С С и II2, содержащее все его вещественные аналитические подмногообразия размерности единица (т.е. аналитические кривые), постоянной кратности сингулярной функции /ь

Теорема 3.5.6. Если го £ д'Dt, то матрица Rt — нормальная.

Множество d"Dk = dD¡\d'Dk либо пусто, либо состоит из конечного числа точек. Поэтому теорема 3.5.6 показывает, что матрица R¡. нормальная во всех точках комплексной плоскости, за исключением, может быть, некоторого их конечного числа.

Заметим, что принадлежность точки zq множеству &D¡¡ не является необходимым условием нормальности, так что матрица i?¿ может быть нормальной во всех или некоторых точках множества д" Dt-

В разделе 3.6 рассматривается сингулярная поверхность — совокупность графиков сингулярных функций, как функций действительной х и мнимой у частей переменного z. Она является действительной алгебраической поверхностью в R3. Показано, что любой делитель характеристического многочлена сингулярной поверхности, неприводимый в кольце R[x,y, í], непрпводим, так же, и в кольце С [я, у, í] . На примере матричных пучков прядка 2 и 3 проиллюстрированы причины образования сложных неприводимых компонент сингулярной поверхности. Установлено, что проекция множества сингулярных точек сингулярной поверхности на плоскость t = 0 является границей множества точек постоянной кратности сингулярных функций.

Все результаты третьей главы получены автором в работах [4-6,10], за исключением теорем 3.3.1, 3.5.1 и 3.5.2. Эти теоремы в эквивалентных формулировках встречаются во многих других работах.

В четвертой главе описан и обоснован метод сингулярной функции для регулярной матрицы многочленов

A(z) = А0 + zAi +... + zU7, detA7 ф 0, (9)

где Ak € Cnxn (к = 0, ...,у). Все результаты этой главы получены в работах [5-7,10].

В разделе 4.1 сформулирована

Задача 4.1.1. Для заданного zq £ С найти какой-нибудь правый сингулярный вектор, отвечающий минимальному сингулярному числу матрицы A(z0) 6 С"".

К ней метод сингулярной функции сводит следующую задачу вычисления собственной пары матрицы многочленов.

Задача 4.1.2. Задана регулярная матрица многочленов (9) и точность 6>0. Требуется найти какую-нибудь пару z,v : z £ С, v £ С™, ||й||2 = 1, удовлетворяющую неравенству

цл(£Н|2 < г.

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

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

г := г0

while 2 £ D do . .

2 Sa(z)

end,

где a — положительный параметр,

5а(2) = 2-2а'Д2)Д7/(2)

— отображение £>—»С, / — минимальная сингулярная функция матицы многочленов (9)г а О — множество точек комплексной плоскости, в которых сингулярная функция / И-дифференцируема и имеет ненулевой градиент:

■О = {2 £ С : /—К-дифференцируема в 2 и У/(г) ф 0}.

Отмечено, что в силу теоремы 3.3.3 для матрицы многочленов (9), множество И открыто, всюду плотно в С, а его граница ¿Ш является подмножеством некоторой плоской действительной алгебраической кривой.

На основе теорем 3.2.2 и 3.4.1 установлена следующая теорема о сходимости в окрестностп собственного значения.

Теорема 4.2.1. Пусть 2, некоторое собственное значение матрицы многочленов (9) ид — его максимальный индекс. Тогда

■ЗД = 2* + - 2.) + 0(|2-2,|2) (2££>, *-«,).

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

Обозначим через множество нормированных правых сингуляр-

ных векторов матрицы А(г0), отвечающих ее минимальному сингулярному числу /(г0)1/2:

Р{г) = а^пнп ||Л(2)У(|2,

где 5 означает множество нормированных столбцов в С".

Правило 4.2.1. Найти какой-нибудь вектор V £ ^(¿о). Положить

¿А

и = и> = А(= оК /(20) = (ш,ш), = 2(и;, и).

В силу следствия 3.5.1 правило 4.2.1 позволяет находить значение градиента в любой точке множества £) и в некоторых точках границы этого множества, в то время как значение самой сингулярной функции будет вычислено правильно в любой точке комплексной плоскости.

В разделе 4.3 рассматривается задача 4.1.2. Отмечено, что процедура уточнения (10) является комбинацией метода градиентного спуска и одномерного метода Ньютона:

5а(г) = 2 + 2 аие,

где

" = е = -У/(2)/|У/(2)|.

Здесь е является направлением антпграднента в точке 2, а и — ньютоновским шагом решения уравнения = f(z + е£) = 0 из точки * = 0: V = —!1;(0)/^'(0). Следовательно, каждая итерация (10) состоит в 20-кратном ньютоновском шаге в направлении антиградиента.

Собственное значение г, индекса д является одновременно 29-кратным нулем и точкой глобального минимума сингулярной функции /. Кроме того, как видно из теоремы 3.4.1, главная часть антиградиента в окрестности собственного значения 2» направлена в сторону г,. Эти факторы обеспечивают установленную в теореме 4.2.1 сходимость процесса (10) вблизи собственного значения (квадратичную, если а = д, и линейную, если 0 < а < д или q < а < 2д).

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

Фиксируем некоторый набор допустимых значений параметра а:

<*о = 1 > а\ > с*2 >

где а; > 0 и ai —► О при I —» ос, п его начальное значение ар. Выбираем начальную точку 2° £ С. Из точки делаем шаг с а — ар:

С :=Sq,o(A

Если f(Q < f(z°), то следующий шаг делаем из точки г = ( с а — «;»_] (либо а = ао, если 1° = 0). В противном случае, возвращаемся в точку и делаем из нее шаг с а = Q;o+1 и т.д. Более формально:

г 2°; I := 1°

for j = 1, 2,..., J do

if f(z) < 62 or |У/(г)| < и; then goto 1 С := г - 2aif(z)/Vf(z) if f(0<f(z) then

2:=C (11)

else

l:=l + 1 end end 1 : г := 2,

где J — максимальное допустимое число шагоЕ, и — положительная величина порядка машинного нуля, 1° — индекс начального значения параметра а.

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

Значение сингулярной функции в точке z = zo € dD будет вычислено правильно. Пусть Vf(zо) означает результат вычисления "градиента" по правилу 4.2.1.

Теорема 4.3.1. Если V/(z0) ф 0, то

|V/(20)|,

где

ео = -V/(20)/)V/(20)|.

Итак, попав в точку г = ;0 € дБ, процедура (11), использующая правпло 4.2.1, лпбо остановится, либо сделает шаг в направлении убывания сингулярной функции /. Причем масштабирующий множитель у — /(-о)/!^7/(-о)| будет больше полного ньютоновского шага в этом направлении, который, в данном случае, равен

Отмечено, что направление наибольшего убывания сингулярной функции / в любой точке го 6 С и ее производную в этом направлении можно определить способом, описанным в разделе 3.5. Однако дополнительные затраты, связанные с вычислением на каждом шаге ортонормированного базиса в подпространстве Брап^-го) пли, даже, просто проверкой, является ли минимальное сингулярное число /(го)1^2 матрицы А(го) — кратным, представляются неоправданно высокой платой за более аккуратную реализацию итерационного процесса.

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

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

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

В пятой главе подробно рассматривается линейный случай:

А(г) = Л0 + гАи с^Д ф 0. (12)

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

Для определенности предполагается, что представляющие интерес собственные значения принадлежат некоторой заданной области С С С,

причем граница дС не содержит собственных значений и в С лежит лишь небольшая часть спектра пучка .4. Здесь и в дальнейшем спектр означает алгебраически полный (с учетом кратностей) набор собственных значений.

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

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

Задача 5.2.1. Для заданного пучка А £ С[г]"х" вида (12), точности £ > 0 и области С С С найти квадратный верхний треугольный пучок II и унитарные прямоугольные матрицы /У, V, удовлетворяющие двум следующим требованиям. Во-первых,

Во-вторых, спектр пучкаВ. содержит всю часть спектра пучка А + Е, лежащую в С.

Через ||.Ц, здесь и далее обозначена норма Фробениуса — квадратный корень из сумм квадратов модулей элементов.

Задача 5.2.2. Для заданного пучка А £ Щг]"*" вида (12), точности е > 0 и области С С С найти квадратный вещественный блочно-треугольный пучок К (с блоками размера 1x1 и 2x2 на главной блочной диагонали) и ортогональные прямоугольные матрицы II, V, удовлетворяющие двум следующим требованиям. Во-первых, для некоторой матрицы Е £ К.пхп, удовлетворяющей неравенству (14), справедливо равенство (13). Во-вторых, спектр пучка К содержит всю часть спектра А + Е, лежащую в С.

Таким образом, как в комплексном, так и в вещественном случае, требуется найти частичное разложение Шура для какого-нибудь пучка А+Е,

(А + Е)У = и Я для некоторой матрицы Е Е Спх", такой, что

(13)

Щ\р < ^

(14)

близкого к исходному в смысле (14). Причем спектр пучка Е может содержать собственные значения, не лежащие в С.

В разделе 5.3 описана неявная комплексная процедура исчерпывания. Она строит две ортонормпрованные системы векторов и\. «2,... и 1'ь г>2, • • • и три последовательности чисел: комплексных -25 - - ч вещественных неотрицательных , 62,... и положительных р\,рг,____

¿ог к = 1,2,..., п ск> Выбрать гк £ С Выбрать и* 6 <$/-5к := \\РкА(:к)гк\\2 рк :=

ик := РкАхук/рк

еп(1

Здесь означает множество нормированных столбцов в С":

= {« 6 С" : И|2 = 1},

Бь (при к > 2) — множество нормированных столбцов в подпространстве

8рап{иь.. ..иц}1, (15)

Р\ = I —■ единичную матрицу порядка п, а Рк (при к >2) — ортопроектор иа подпространство

5рап{иь.

Символом ± здесь и далее обозначено ортогональное дополнение соответствующего подпространства.

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

Задача 5.3.1. Для заданного 6 > 0 найти г* £ С, € такие, что

||АА(2*Ы|2 < 6.

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

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

На к-м шаге вещественной процедуры выбираем квадратную матрицу Zk порядка пк, равного 1 либо 2 , и ортогональнзгю прямоугольную матрицу Ук размера п х пк со столбцами, принадлежащими подпространству

range^,...,^]1. (16)

Полагаем

bk = \\Pk{AüVk + AlVkZk)\\F

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

РкАгУк = UkVk,

где Р\ = I — единичная матрица порядка п , а Рк (при к > 2) — орто-проектор на подпространство

range[L'b...

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

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

Задача 5.4.1. Для заданного т > 0 найтпи гк £ С, tu* £ Sk такие, что

||PtA(2)>fc|!2 < т,

где Sk означает множество нормированных столбцов в С" с действительными и мнимыми частями, принадлежащими подпространству (16) и, по определению, Pku> = PkRe(w) + iPklm(w), w £ С".

Отмечена разрешимость задачи 5.4.1 при всех к : п\ + ... + пк < п. Основное внимание уделено следующему существенному отличию вещественной процедуры от комплексной: решение задачи 5.4.1 нельзя использовать непосредственно.

Действительно, пусть найдено некоторое решение zk, wk задачи 5.4.1 с г = 8. Не нарушая общности, будем предполагать, что вектор wk либо веществен, либо его действительная и мнимая части линейно независимы. Если вектор wk веществен, то, полагая пк = 1, Vk = wk, имеем

6к = \\РшА0Ук\\Г < 6.

В противном случае, поскольку пара zk, wk также является решением задачи 5.4.1, линейная оболочка вещественной и мнимой частей вектора

и~к образует приближенное вещественное понижающее подпространство размерности 2. Выбрав в этом подпространстве какой-нибудь ортонор-мированный базпс {г^. г'г}- полагаем пк = 2, Vk = t^]. Однако теперь величина 6к может значительно превосходить <5. Более того, если zk является приближенным значением некоторого простого вещественного собственного значения, то величина очевидно, не может стремиться к нулю при т —+ 0. Таким образом, в случае, когда 1т(гу<.) ф 0, требуется более аккуратная реализация /г-ro шага процедуры исчерпывания. Предлагается действовать следующим образом.

а) Найти сингулярное разложение матрицы

T7=[ReK),ImK)], (17)

составленной пз действительной п мнимой частей вектора wk:

W = Vdizg(dud2)QT,

где V — ортогональная прямоугольная матрица размера п х 2, Q — ортогональная матрица порядка 2 и d\ > di > 0.

б) Найти ортогональную прямоугольную матрицу U размера п х 2 и квадратную верхнюю треугольную матрицу V порядка 2 такие, что

PtA^V = UV.

Положить

„(4 = 1, ит = щ,

„(2) = 2> 02) = Vj jy(2) = ц

где и 1 и V\ означают первые столбцы матриц U и V соответственно.

в) Вычислить

¿W = UPW^oF«^ (г = 1,2), (18)

где РМ означает ортопроектор на подпространство

range[Uu...,U^uU(i)]X.

Еслп minj^'1), б'2'} > S, то уточнить вектор wk (т.е. решить задачу 5.4.1 с меньшим т ) и вернуться к пункту (а). Иначе, положить

щ = nU), Vk = V®, Uk = UU),

где

j = arg mini'1', i = l,2.

Отмечено, что величина б1-1' будет, вообще говоря, меньше, если в пункте (б) полагать

= УЧ, и<'> = РьА^/ЩА^Х, где q Е И? — нормированный столбец, минимизирующий функционал

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

Теорема 5.4.2. Пусть гк, юк — некоторое решение задачи 5.4-1. Тогда для величин (18) справедливы следующие неравенства:

а(1)<(т + /м*2)М, <5(2) < т/д2,

где

(1=\1ш(2к)\\\РкА,\\2,

ад. 1 и е?2 означают соответственно максимальное и минимальное сингулярные числа матрицы (17).

Из теоремы 5.4.2 следует, что при г —► 0 величина ппп{<5^\й(2'} Таким образом, /с-й шаг вещественной процедуры исчерпывания можно свести к решению задачи 5.4.1.

Далее получено еще более оптимистичное следствие теоремы 5.4.2. Пусть г*, юк означают некоторое решение задачи 5.4.1 и гк —» г, при т —+ 0. Если 1т(г») ф 0 либо если 2Ф — вещественное собственное значение индекса единица, то

гшп{г(1\«$(2>} X г, (т-4 0),

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

В заключении приведена комбинация метода сингулярной функции с вещественной процедурой исчерпывания (алгоритм в целом) и продемонстрирована ее работа на примере вычисления приближенного частичного разложения Шура, отвечающего частичной проблеме собственных значений для сеточного уравнения конвекции-диффузии из раздела 4.5.

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

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

Задача 5.6.1. Для заданного 2о £ С найти какой-нибудь правый сингулярный вектор, отвечающий минимальному ненулевому сингулярному числу оператора РьА^о^ц..

Здесь Рь означает ортопроектор, определенный в разделах 5.3, 5.4 (для комплексной и вещественной процедур исчерпывания этот ортопроектор опреде.ляется по-разному), а — ортопроектор на подпространство (15) в комплексном и ортопроектор на подпространство (16) в вещественном случае.

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

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

В разделе 6.1 кратко описан графический метод исследования устойчивости собственных значений к возмущению начальных данных по линиям уровня первой сингулярной функции (спектральному портрету). Этот метод был предложен для числовых матриц в работах Годунова, Кприлюка, Костина, Трефетхена и, как это показано в работе автора [6] и данном разделе диссертации, распространяется на более общий случай матрицы многочленов. Возможность на основе той же вычислительной технологии оценивать устойчивость собственных значений методом спектрального портрета, дающего существенно более реалистичные результаты, чем мажорантные и асимптотические оценки, — одно из достоинств метода сингулярной функции. Отмечено, что спектральный портрет можно использовать для выбора начальных приближений в качестве альтернативы

способу, описанному в разделе 5.5.

В разделе 6.2 показано, что процедуры из четвертой главы можно использовать для вычисления собственных значений матрицы аналитических функции. Доказано, что локальные утверждения о сингулярных функциях матрицы многочленов, установленные в третьей главе, распространяются на матрицы аналитических функций. В основе доказательства лежит теорема о локальной форме Смита матрицы аналитических функций из [6].

Пусть U — область в С и А — квадратная матрица порядка п функций, аналитических в U, т.е. аналитическое отображение U —» Cnxn, z0 — некоторая точка области U и К означает кольцо функций, аналитических в этой точке. Будем говорить, что матрица X £ Кпхп унимодулярна, если

detX(20) ф 0.

Теорема 6.2.1. Для любой матрицы В £ Кпх" найдутся унимоду-лярные матрицы X,Y £ К"хп такие, что

В = XdiagCiV^O, di.....dn)Y,

n—m

где

dk(z) = (z - z0)n, k=l,...,m,

a <Zi > • ■ ■ > 4m — неотрицательные целые.

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

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

В данном разделе перечислены некоторые асимптотически быстрые алгоритмы умножения. Основное внимание уделено предложенному автором в работах [1,2,9] методу построения быстрых алгоритмов умножения на основе локальной интерполяции.

Любую квадратную числовую матрицу порядка т можно рассматривать как матрицу вида

9(Т) =

. 0(*11,*21) •••

(19)

где д — некоторая вещественная лпбо комплекснозначная функция двух действительных аргументов, а Т С К2 — декартова сетка:

т - {<11, . . . , ¿1га} X {#21, • • • , ¿2ш}, < (20)

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

1, <2) = ехр(г'*1*2), tlk = 2тг(к - 1 )/т, <21 = & - 1,

для которой известен быстрый алгоритм умножения (БПФ), требующий 0(т\о^2т) операций. Если ¡^ = £ — 1, а — произвольные точки отрезка [0, 27г], то соответствующая матрица является матрицей Вандемонда общего вида. Известный быстрый точный алгоритм ее умножения на вектор требует в к^2т раз больше операций, чем БПФ, значительно сложнее логически и численно неустойчив. Наконец, если Т — произвольная декартова сетка в [0,2ж] х [0, т — 1], то для соответствующей матрицы (19) быстрые точные алгоритмы умножения неизвестны.

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

||у-С:г||2<ф||2.

Рассмотрим следующую задачу. Для заданных д. Пт, ет (т = 1,2...) найти быстрый численно устойчивых! алгоритм умножения. Предположим, нам известно некоторое множество П таких декартовых сеток, что каждую матрицу д(X) (X £ П) мы умеем быстро и численно устойчиво умножать на вектор. Если

т

то возпкает следующий вопрос: нельзя ли свести умножение на вектор матриц д(Т) (Т £ Г) к умножению на вектор матриц д(Х) (X £ П)? Положительный ответ на этот вопрос во многих случаях дает интерполяционный метод, предложенный в работах [1,9]. Он позволяет найти аппроксимирующее исходную матрицу д(Т) выражение вида

Атд(Х)В + С, (21)

где X £ П, а А, В, С — разреженные матрицы.

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

В заключении сформулированы следующие

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

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

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

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

• Метод сингулярной функции распространен на случай регулярной матрицы аналитических функций.

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

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

По теме диссертации опубликовано более 20 печатных работ, в том числе одна монография [6]. Основные результаты диссертации представлены в следующих десяти работах.

1. Нечепуренко Ю.М. Быстрые устойчивые алгоритмы для класса линейных дискретных преобразований// Вычислительные процессы и системы. Вып. 5. — М.: Наука, 1987. — С. 292-301.

2. Нечепуренко Ю.М. О численной устойчивости одного класса алгоритмов// Ахитектура ЭВМ и численные методы. — М.: ОВМ АН СССР, 1987. — С.73-79.

3. Нечепуренко Ю.М. Об аналитичности собственных чисел эрмитовой А-матрпцы// Архитектура ЭВМ и численные методы. — М.: ОВМ АН СССР, 1991. — С. 42-47.

4. Нечепуренко Ю.М. О сингулярных числах почти вырожденной матрицы// Архитектура ЭВМ и численные методы. — М.: ОВМ АН СССР, 1991. — С. 48-51.

5. Нечепуренко Ю.М. Сингулярные функции матрицы многочленов. — М.: ИВМ РАН, 1992. (Препринт N 284).

6. Нечепуренко Ю.М. Метод сингулярной функции для проблем собственных значений. — М.: ИВМ РАН, 1994.

7. Нечепуренко Ю.М. Метод сингулярной функции для вычисления собственных значений матрицы многочленов// ЖВМ и МФ. 1995. Т. 35, N. 5. — С. 647-660.

8. Нечепуренко Ю.М. Неявная процедура исчерпывания для частичных обобщенных проблем собственных значений// ЖВМ и МФ. 1995. Т. 35, N. 7. — С. 1023-1033.

9. Nechepurenko Yu.M. Fast numerically stable algorithms for a wide class of linear discrete transforations// Sov. J. Numer. Anal. Math Modelling. 1987. V. 2, N. 1. — P. 57-74.

10. Nechepurenko Yu.M. Singular functions of polynomial matrices// Russ J. Numer. Anal. Math. Modelling. 1992. V. 7, N. 1. — P. 63-74.