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

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

Содержание
Используемые обозначения
Введение
Глава 1. Мозаично-скелетонный метод
1.1 Аппроксимация для асиптотически гладких ядер
1.2 Оценки асимптотической гладкости
1.3 Аппроксимация для гармонических ядер
1.4 Аппроксимация для осцилляционных ядер
Глава 2. Алгоритмы аппроксимации сложности О(п2)
2.1 Аппроксимация блока по методу Ландоша
2.2 Описание алгоритма
2.3 Численные эксперименты
2.3.1 Уравнение электрического поля
2.3.2 Задача обтекания
Глава 3. Псевдоскелетные аппроксимации
3.1 Возможность псевдоскелетной аппроксимации
3.1.1 Экстремальные подматрицы
3.1.2 Оценки псевдоскелетной аппроксимации
3.2 Аппроксимации при помощи подматрицы максимального объема
3.3 Принцип выбора псевдоскелетной компоненты
3.4 Численные эксперименты
Литература

Используемые обозначения
9tz — вещественная часть числа z;
3z — мнимая часть числа z;
N = ІІХІІ2 — евклидова норма вектора х;
основание логарифма там, где это важно, считается равным двум: log х = log2 х;
[xj — наибольшее п є % такое, что п. ^ х;
|"х] — наименьшее п Є Ъ такое, что п ^ х;
z- = z (z — 1) ■ ■ • (z — 1с + 1); z* = z(z + 1) • • ■ (z + k — 1) — символ Похгаммера;
(У = z-/kl — биномиальный коэффициент;
'(*) = z)./y — „мультиномиальный“ коэффициент, соответствующий мультииндексу "v;
Г (z) = J" e_t tz~’ dt, 9tz > 0 — гамма-функция Эйлера;
В(>c,y) = jJtx~’ (1 — t)v_I dt, 9tx>0, lHt|>0 — бета-функция Эйлера; Уф — градиент скалярной функции (р;
V • А — дивергенция векторной функции А;
const. — положительная константа, не зависящая от изменяемых параметров;
ЦАЦг ■— спектральная норма матрицы А;
IJА)) f — фробениусова норма матрицы А;
IIА||с = maXij |оу| — максимум модуля элементов матрицы А; ranktA — е-ранг матрицы А, то есть mint rank (А + Е), где минимум берется по всем матрицам Е таким, что ||Е|| ^ е.

Введение
Настоящая работа посвящена изучению одного из подходов для быстрого приближенного умножения на плотные неструктурированные матрицы. Такая задача возникает, например, при построении численного метода решения уравнения
которое каким-то образом дискретизируется (скажем, коллокацией или по методу Галеркина), и возникает линейная система А^Хп = Ьп, размерность п которой растет при увеличении точности дискретизации. Ключевой вопрос — как быстро растет объем памяти, необходимый для хранения дискретизированного оператора, и число арифметических действий, необходимое для решения задачи с заданной точностью, в зависимости от п. Предполагается, что задача поставлена корректно и ядро К(х,у) сингулярно.
Предположим, что для решения линейной системы используется какой-либо итерационный метод (возможно, с предобусловлива-нием). Тогда основные вычислительные затраты связаны с операцией матрично-векторного умножения на Ап, что приводит к следующей задаче матричной аппроксимации, составляющей содежание проблемы: найти „близкую“ к Ап матрицу Ап, такую, что
• матрично-векторное умножение у — Апх выполняется быстро;
• объем памяти, необходимый для хранения А^, мал;
• погрешность в решении, допускаемая при замене Ап на Ап, сравнима с погрешностью дискретизации.
Говоря „быстро“ и „мал“ мы имеем в виду о(п2) арифметических операций и о (п2) ячеек памяти. Сложнее указать строгий критерий близости Аи и А*., обеспечивающий допустимую погрешность в решении. В дальнейшем мы будем понимать под этим условие ||АП—Ап|]р ^ еЦАцЦр, где £ не зависит от п, потому что для тех конкрет-

Далее,
та та та ^
ц ю *т~к=т_ (?) ^-к ^ < л © ^Ь- Л
к=0 к=0 к=
Теперь мы готовы К доказательству второй из формул (1.18). Объединяя (1.19) и (1.23), получаем

К1Х’У) = —п=т Х'Рк*С0Е!'у^кк(х’£') ЛсГ£.>
т Р-Л
откуда
|Rp(x,-y)| ^ ]Г tk|pk(cosy)| max|К(х,£,)]. (1.27)

Начнем с последнего члена. Наименьший радиус шара, содержащего узлы {у (j)}, р = a^/in/2. Далее, узлы (х(г)} содержатся в области (<т + })а ^ ЦхЩ ^ {2сг+|)а, поэтому при t = |
(сг+ — /ттг)а ^ |х — £,| ^ (2оЧ-| + л/т)а,
так что |К(х, £,) | ^ const. т.9/1а?.
Наконец, в силу лемм 1.7 и 1.
~ 2+1_т ~
Y_ tk |Pk(cosy)| ^ —-- Y_ tk+m~’ (k + m - 1 )ffl=i
k=p k=p
1 1 V1 — t m—

^ const.2 p ( 2+ ^

Теорема 1.4. Пусть матрица порождается гармоническим по у ядром К(х,у) на сетках {хД)}р=1, {у(Ш£=1> заданных на ограниченном множестве Б с Кт и подчиненных условию (1.3). Тогда Vе, 0<£<е0, и УпеМ, п > По, существуют мозаично-скелетонные аппроксимации