Нелинейные аппроксимации матриц

• Автор: Оселедец, Иван Валерьевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

1.1 Нелинейные аппроксимации матриц: зачем и как

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

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

Глава 1. Метод чёрных точек и наилучшие циркулянтные предобуслав-ливатели

1.1 Введение

1.2 Задачи С+Я и Б+Я аппроксимации

1.3 Чёрные точки, малые ранги и скелетоны

1.4 Адаптивная версия метода чёрных точек

1.5 Тёплицев случай

1.5.1 Быстрое вычисление образа Фурье для тёплицевой матрицы

1.6 Существование С+Я аппроксимации для некоторых классов тёплицевых матриц

1.7 Численные эксперименты
1.8 Метод чёрных точек для произвольного шаблона
1.9 Неизвестный шаблон
1.10 Выводы
Глава 2. Нестандартные вейвлет-преобразования
2.1 Введение
2.2 Основные понятия и определения
2.3 Вейвлет-пространство. Масштабирующие и лифтинговые коэффициенты
2.4 Основная система
2.5 Решение основной системы
2.6 Нахождение масштабирующих коэффициентов
2.7 Алгоритм вычисления вейвлет-преобразования
2.8 Численные эксперименты
2.8.1 Пример
2.8.2 Пример
2.9 Выводы
Глава 3. Тензорные аппроксимации матриц со структурированными факторами
3.1 Введение

3.2 Масштабированные циркулянтные предобуславливатели
3.3 Приближённое обращение структурированных матриц
3.4 Методы построения приближённой обратной
матрицы
3.4.1 Метод Ньютона с аппроксимациями
3.4.2 Модифицированный метод Ньютона
3.5 Численные результаты
3.5.1 Масштабированный циркулянтный преобуслав-ливатель
3.5.2 Предобуславливатели на основе метода Ньютона
3.6 Выводы
Глава 4. Супер-быстрое обращение двухуровневым тёплицевых матриц
4.1 Введение
4.2 TDS формат
4.3 Арифметика TDS формата
4.3.1 Основные арифметические операции
4.4 Основные арифметические операции в тензорном формате
4.4.1 TDS-рекомпрессия
4.4.2 Оператор обрезания
4.5 Метод Ньютона и выбор начального приближения
4.6 Численные результаты
4.7 Структура обратных к двухуровневым матрицам специального вида
4.7.1 Так почему же 5?
4.7.2 Обобщение на случай большего числа слагаемых
4.8 Выводы
Заключение
Литература

ВВБДЕНИЕ
М. Нелинейные аппроксимации матриц: зачем и как
К решению линейных систем уравнений — основной задаче линейной алгебры и матричного анализа — сводится подавляющее большинство практических вычислительных задач. Однако, несмотря на наличие универсальных методов, многие приложения приводят к «большим» системам, которые не могу быть решены даже на современных суперкомпьютерах.
В данной диссертации развиваются эффективные методы вычислений с плотными матрицами, в которых сами матрицы и результаты матричных операций аппроксимируются матрицами специальной структуры, определённой относительно малым числом параметров. Зависимость от параметров носит нелинейный характер, поэтому речь идёт о методах нелинейной матричной аппроксимации.
Плотные матрицы описываются 1Ч2 параметрами. Если мы хотим ускорить работу с ними, то необходимо построить «сжатое» представление матрицы с помощью меньшего числа параметров. Матрицы, описываемые малым числом параметров, будем называть структурированными.
Часто структура матрицы видна сразу или следует из физических свойств задачи. Например, в задачах с оператором, инвариантным относительно сдвига, получающиеся матрицы имеют тёплицеву (или блочно-тёплицеву в многомерных задачах) структуру, т.е. элемент матрицы зависит лишь от разности индексов: сщ = . Для
тёплицевых матриц существуют быстрые алгоритмы, основанные на БПФ. Тёплицевы матрицы — классический пример матриц с линейной структурой. Можно привести другие примеры: ганкелевы матрицы (сщ = Ь^), ленточные матрицы, разреженные матрицы.
Ещё один важнейший класс матриц — матрицы малого ранга, т.е. матрицы вида
А = иУт,
И е 1ИХТ,У е 1тхт, где ранг г < т.,п. Это — пример матрицы с нелинейной структурой: её элементы зависят от параметров (элементов матриц И и V) нелинейно.
Таким образом, эффективные алгоритмы могут быть основаны на нелинейных малопараметрических аппроксимациях матриц. Однако далеко не всегда очевидно, как получить эффективное малопараметрическое представление матрицы. Более того, чтобы быстро работать с такими структурами, мы должны уметь выполнять матричные

2.5. Решение основной системы
Займёмся теперь решением системы (2.8). Так как (2.8) должно выполняться при О Д р Д т, то оно равносильно тому, что
разность (к +1) -го порядка, взятая от многочлена степени не выше к равна 0, то основная система эквивалентна уравнению(2.9). При этом Р(х) - Уже произвольный многочлен степени (ти + к + 1).
Найдём теперь такие многочлены Р5(х), ітіп < ] ^ ]тах, что
Для решения системы (2.8) достаточно указать какие-нибудь многочлены Р,(х). Пусть сначала все ДД = ]тщ, ...Дтах + к + 1 различны. Тогда многочлен Pj однозначно определяется своими значениями в этих точках. Докажем следующую теорему.
Теорема 4 1. Многочлен Р,(х) такой, что
ДР(х) = ^ач[х1;х0+1);...;х(Нк+1)]Р(х) (2.9)
для любого многочлена Р(х) — азХ5+к+1 • Но так как разделённая
[хг;х(г+1);...;Х(г+к+1)]Р;М
(2.10)
Ітіп Д ^ )тахТогда, подставляя эти многочлены в (2.9), получим, что
од = ЦР) (х)
(2.11)
удовлетворяет (2.10) при к = 0.
2. Многочлен Р, (х) такой, что
(2.12)
)+к
ч(х) = (х}-х(н.к+1)) П(х-х0, Н+1
удовлетворяет (2.10) при к Д