Квазисепарабельные матрицы в линейной алгебре и ее приложениях

• Автор: Жлобич, Павел Георгиевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 135 с. : ил.

Оглавление

Введение

1.1 Квазисепарабельные матрицы

1.2 Историческая справка

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

1.4 Содержание работы по главам

Глава 1. Применение обобщенных матриц Фробениуса для вычисления корней многочленов

1.1 Введение

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

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

1.3.1 Стационарный цб-алгоритм
1.3.2 Прогрессивный цб-алгоритм
1.4 Дифференциальный qб-aлгopитм для квазисепарабельных матриц в хессенберговой форме
1.4.1 бцбэ алгоритм на языке многочленов
1.5 Обобщенный процесс Грама-Шмидта и бцбБ-алгоритм
ф для квазисепарабельных матриц
1.5.1 Включение сдвигов
1.6 бqбs-aлгopитм для обобщенной матрицы Фробениуса
1.6.1 Многочлен, заданный в базисе мономов
1.6.2 Многочлен, заданный в базисе ортогональных
многочленов
1.6.3 Многочлен, заданный в базисе многочленов Сегё
1.7 Численные эксперименты
1.8 Выводы
Глава 2. Обращение полиномиальных матриц Вандермонда
2.1 Введение
2.2 Принцип Теллегена
2.3 Минимальная реализация динамической системы через
граф потока сигнала
2.3.1 Многочлены Горнера и обращение матрицы Ван-
™ дермонда
2.3.2 Связь многочленов Горнера с собственными векторами матрицы Фробениуса
2.3.3 Одночлены и прямой (наблюдаемый) граф

2.3.4 Многочлены Горнера и дуальный (управляемый) ф граф
2.4 Неминимальная реализация динамической системы и обращение полиномиальной матрицы Вандермонда
2.5 Алгоритм обращения полиномиальной матрицы Вандермонда
2.6 Численные эксперименты
2.7 Выводы
Глава 3. Квазисепарабельные матрицы в задачах оптимального управления с уравнениями в частных производных
3.1 Введение
3.2 Пример оптимизационной задачи с ограничениями в виде УЧП
3.3 Многоуровневые квазисепарабельные матрицы
3.4 Численные эксперименты
3.5 Выводы
Глава 4. Численная устойчивость быстрых алгоритмов решения систем с квазисепарабельными матрицами
_ 4.1 Введение
4.2 Основные идеи алгоритмов решения квазисепарабель-ных систем
4.3 Алгоритм А
4.3.1 <511-разложение
4.3.2 Обратная прогонка
4.3.3 Анализ ошибок округления в алгоритме А
4.4 Алгоритм Б
4.4.1 Источники неустойчивости алгоритма Б
4.4.2 Численные эксперименты с алгоритмом Б
4.5 Выводы
Заключение
Литература
Введение
ь1. Квазисепарабельные матрицы
Данная работа посвящена развитию теории матриц с малоранговой структурой особого вида, называемых квазисепарабелъными, а также их применению для решения некоторых классических задач линейной алгебры. Прежде чем определить класс квазисепарабелъных матриц, сделаем несколько общих замечаний о матрицах с малоранговой структурой.
Матрицы с блоками малого ранга все активнее применяются в инженерной и научно-исследовательской практике. Например, при решении задач математической физики в интегральной форме, где возникают системы уравнений с плотными матрицами большого размера. Использование малоранговой структуры таких матриц позволяет не только «сэкономить» на хранении их коэффициентов, но и значительно ускорить некоторые операции линейной алгебры с ними (такие, как умножение на вектор). В качестве простейшего примера рассмотрим краевую задачу с оператором Штурма-Аиувилля:
В теории операторов Штурма-Лиувилля доказывается, что любое решение и(х) этой краевой задачи представимо в виде интеграла
где д(х, £,) — так называемая функция Грина для (1). Причем функция Грина, для одномерного оператора Штурма-Лиувилля имеет вид
где "Щ , П-2 — частные решения однородного уравнения £(гц) =0 с Вх{щ) — 0. Представление (2) означает, что функция д(х, £,) — сепарабельная в двух подобластях своей области определения. Следовательно, ее дискретный аналог — это матрица, в которой любая подматрица выше или ниже диагонали (с захватом диагонали) имеет ранг один.
£(и) := (р(х)и')' - д(х)и

и(х) = д(х, (£,)
а < х
£, < х Ь,

ЬАРАСК для вычисления собственных значений симметричных трехдиагональных матриц. В §1.5 будет показано, что дифференциальной версии цб-алгоритма не может существовать для произвольной квази-сепарабельной матрицы. Однако мы смогли построить такой алгоритм для одного важного частного случаю, а именно, для квазисепарабель-ной матрицы в хессенберговой форме. Напомним, что этот случай включает обобщенную матрицу Фробениуса для многочлена, представленного в базисе ортогональных многочленов.
Пусть дана произвольная квазисепарабельная матрица в хессенберговой форме:
бі діН2 діЬ2К3 діЬ2. Ьп_] Нп
«1 б2 д2Н3 дгЪз Ьп_1
0 52 с!з дзЬ4. Ьп—1 б-п (1.23)
0 0 5п—1 <*п
Вследствие того, что все элементы ниже первой поддиагонали равны нулю, квазисепарабельные генераторы в нижней части матрицы особенные: Як = 5]с, а.к = 0 и рк = 1 . В данном параграфе мы рассматриваем только скалярные квазисепарабельные матрицы, то есть мы предполагаем, что все генераторы, такие, как бк, — скаляры.
Далее мы выводим дифференциальную версию алгоритма 3. Наш первоначальный вывод может показаться чересчур громоздким и техническим, однако позже в §1.5 мы предложим альтернативный вывод, основанный на обобщенном процессе Грама-Шмидта, который прояснит некоторые детали алгоритма.
Сначала заметим, что из-за особых генераторов в нижней части матрицы многие формулы алгоритма 3 упрощаются. В частности, fk = Нк+1 и ?к = Як-1 дк-1 Далее, изменим способ вычисления генераторов

бк = бк + 5кдкЬ.к+1 — вк-т дк-1Нк
= бк + 5к(дк + $к—1 дк-1Ък)Нк+1 — вк-1 дк-1 Нк — с = бк + 5кдкЬ-к+1 — вк—7 дк-1 (Ь-к — 5кЬкНк+1) — а = бк 4- ЭкдкЬ-к+т — ?к—1 дк-1Нк — с.
Введем вспомогательную переменную 1к, определенную как
tk := Фс - ?к-1 дк-тНк - сг (= бк - 5кдкНк+1). (1.24)