Быстрая полилинейная аппроксимация матриц и интегральные уравнения

• Автор: Савостьянов, Дмитрий Валериевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 143 с. : ил.

11 Быстрые методы решения интегральных уравнений
1.2 Историческая справка
1.3 Основной результат данной работы
1.4 Содержание работы по главам
Глава 1. Мозаично-скелетонный метод
1.1 Описание и развитие мозаично-скелетонного метода
1.1.1 Описание метода
1.1.2 Методы дожимания (переаппроксимации)
1.1.3 Численные эксперименты
1.2 Параллельная версия метода
1.2.1 Особенности кластерных станций
1.2.2 Модель параллелизации и распределение нагрузки
1.3 Выводы
Глава 2. Метод трехмерной крестовой аппроксимации
2.1 Введение
2.2 Теорема существования
2.3 Трехмерный крестовый метод
2.3.1 Как нельзя построить этот алгоритм
2.3.2 Как можно построить этот алгоритм
2.3.3 Как добиться почти линейной сложности
2.3.4 Как сделать алгоритм эффективным
2.3.5 Сложность полученного метода
2.4 Важные детали
2.4.1 Как найти подматрицу максимального объема
2.4.2 Как найти наибольший элемент в срезке
2.4.3 Как добавить векторы в ортогональный набор
2.4.4 Как проверять точность аппроксимации
2.4.5 Какова точность «нулевого приближения»
2.5 Модельные численные эксперименты
2.6 Асимптотика предложенного метода
2.6.1 Теоретические оценки
2.6.2 Практические значения ранга
2.6.3 Время работы алгоритма
2.7 Выводы

Глава 3. Приложения к численному решению уравнений
3.1 Применение мозаично-скелетонного метода к задаче Дирихле для уравнения Гельмгольца
3.1.1 Некоторые факты из теории потенциала
3.1.2 Интегральное уравнение и дискретизация
3.1.3 Численные эксперименты
3.2 Применение мозаично-скелетонного метода к задаче гидроакустики
3.2.1 Постановка задачи
3.2.2 Метод замкнутых дискретных вихревых рамок
3.2.3 Вычисление элементов матриц
3.2.4 Численные эксперименты
3.3 Применение тензорных аппроксимаций к решению простейшего интегрального уравнения
3.3.1 Постановка задачи
3.3.2 Дискретизация задачи
3.3.3 Сжатие матрицы
3.3.4 Структурированные векторы
3.3.5 Предобусловливание тензорных матриц
3.3.6 Численные результаты
3.4 Выводы
Глава 4. Специфика матриц в одной задаче электродинамики
4.1 Постановка задачи
4.1.1 Физическая постановка
4.1.2 Интегральное уравнение
4.2 Метод дискретизации
4.3 Специфика полученной матрицы
4.4 Параллельный алгоритм
4.5 Численные эксперименты
4.6 Пример решения обратной задачи
4.6.1 Приближение Борна
4.6.2 Горизонтальное зондирование
4.6.3 Двумерное зондирование
4.7 Применение трилинейной крестовой аппроксимации для
сжатия данных
4.8 Выводы
Заключение
Литература

К1. Быстрые методы решения интегральных уравнений
В последние годы при решении сложных инженерных задач (геологоразведки, акустики моря, ЯМР в квантовой химии) все чаще используются интегральные уравнения. Интерес к ним обусловлен несколькими причинами.
• Интегральные уравнения позволяют понизить размерность задачи, сводя, например, трехмерную задачу к интегральным уравнениям записанным на границе области — двумерном многообразии.
• Интегральные уравнения позволяют сводить краевые задачи в бесконечных областях к задачам на ограниченном носителе, как например метод объемного интегрального уравнения для задачи рассеяния.
Серьезным фактором, затрудняющим применение интегральных уравнений в практических расчетах, являются затраты на вычисление, хранение и умножение на матрицу возникающей линейной системы. В подавляющем большинстве случаев она плотная, а значит при числе неизвестных п в общем случае на ее хранение требуется п2 ячеек памяти. Долгое время именно за счет этого интегральные уравнения проигрывали в глазах инженеров-вычислителей подходам, основанным на дифференциальных уравнениях. Последние при дискретизации приводят к разреженным матрицам, на хранение которых требуется лишь 0[п) элементов памяти. Однако возникают другие сложности: например, прямое решение такой системы приводит к заполнению, а итерационное требует построения предобусловливателя, так как возникающая матрица обычно очень плохо обусловлена.
Если мы хотим использовать методы интегральных уравнений так же эффективно, как и дифференциальные постановки, требуется предложить быстрые алгоритмы решения возникающих линейных систем. Называя метод «быстрым», обычно имеют в виду, что его сложность составляет о(п2), где п — размерность линейной системы; в последнее время этот термин все чаще относят к алгоритмам почти линейной по п сложности, то есть сложности O[nogan), с некоторым а > 0. Для приближенных методов чаще всего отдельно выделяют зависимость сложности от параметра точности £, обычно тоже логарифмическую, указывая 0(пк^апк^ь е-1). При этом для

Положим также В(, = Вр.
1.4 В матрицах II' и V' уточняется расположение подматрицы максимального объема (см. пункт 2.4.3).
1.5 В полученной срезке отыскивается максимальный (или близкий к нему) элемент (см. пункт 2.4.2). Пусть он стоит на позиции
(1р) 1р) •
2.1 Вычисляется распорка гур, отвечающая мультииндексу (1Р,}Р), из нее вычитаются значения Ар-.
2.2 Вектор р ортогонализуется к уже имеющемуся набору векторов У = [-п>1 >ур_1]
Он совпадает с точными значениями массива А на позициях р вычисленных срезок и р вычисленных векторов-распорок. Размеры матриц 11; и V' равны пх (г + гр), размер ядер В" равен (г+тр)х(г+тр). Чтобы вернуться к прежнему размеру опорных матриц и ядер, применим метод редукции Таккера.
3.1 Составляется трехмерный массив В" — [В"... В"] размера (г + гр) х (г + гр) х Р и Мя него строится разложение Таккера (2.4) с помощью БУБ-алгоритма, описанного на с. 34 формулами (2.5),
3 Аппроксимант Лр представлен в виде

(2.18)