Талтыкина (1235576), страница 2
Текст из файла (страница 2)
Называя метод быстрым,обычно имеют в виду, что его сложность составляет ( 2 ), при → ∞.В последнее время этот термин используют по отношению к алгоритмам почти линейной по сложности, то есть сложности ( log ), с некоторым > 0. Для приближённых методов чаще всего отдельно выделяют зависимость сложности от требуемой точности , обычно также логарифмическую,указывая ( log log −1 ), > 0.Среди наиболее известных быстрых методов можно отметить мультипольные разложения [11], метод кластеризации граничных элементов [12], методлокальных волн [13], метод интерполяции на регулярную сетку [14] и другие.
Данные методы являются безматричными или операторными (матрица в явном виде не участвует в операции умножения). Они, как правило,9формулируются в аналитической форме для конкретного ядра интегрального оператора (см. обзор в [16]). Для их применения в ранее созданном программном обеспечении решения исходных задач требуется переработка всехэтапов алгоритма дискретизации интегрального оператора и решения СЛАУ,что является весьма трудоёмкой процедурой.
Поэтому с целью ускоренияработы уже созданных алгоритмов и отлаженных программ для численного решения задач Дирихле для уравнения Гельмгольца и задач дифракциибыл использован мозаично-скелетонный метод [15, 17, 18]. При его реализации основная матрица СЛАУ полностью не вычисляется и не сохраняется,а в процедуре матрично-векторного умножения используется некоторое еёприближение. При определённых предположениях относительно свойств ядра интегрального оператора для построения такого приближения достаточновычислить относительно небольшое число элементов исходной матрицы. Поэтому при использовании мозаично-скелетонного метода в имеющуюся программу вычислений необходимо добавить только процедуры построения ихранения приближённой матрицы и изменить модуль матрично-векторногоумножения, а метод дискретизации и процедура вычисления элементов исходной матрицы остаются прежними.Первая работа по мозаично-скелетонному методу появилась в 1993 году [17].
В работах [19, 20] заложена теоретическая основа для поиска надёжных аппроксимаций блоков плотных матриц по малому количеству элементов. Работа [21] посвящена доказательству существования малоранговыхаппроксимаций матриц, порождаемых асимптотически гладкими и осцилляционными ядрами интегральных операторов (в частности, фундаментальнымрешением уравнения Гельмгольца, которое используется в настоящей работе).Метод развивался в работах [15, 18, 22], где помимо теоретических аспектов,приведены численные эксперименты, демонстрирующие его эффективность.Применение мозаично-скелетонного метода при численном решении двумерных и трёхмерных задач описано в [18], [23] и [24] – [29] соответственно.Целью данной работы является адаптация и реализация мозаичноскелетонного метода для численного решения трёхмерных задач Дирихледля уравнения Гельмгольца и трёхмерных скалярных стационарных задачдифракции акустических волн.
В рамках реализации этой цели необходимо10решить следующие задачи:1. Адаптировать мозаично-скелетонный метод для решения СЛАУ с комплексными коэффициентами;2. Реализовать быстрый метод в уже готовых программах решения краевых задач и задач дифракции;3. Создать параллельную версию данного метода и приближенногоматрично-векторного умножения;4.
Провести численные эксперименты.Научная новизна работы состоит в следующем:1. Мозаично-скелетонный метод впервые применён к решению трёхмерных задач Дирихле для уравнения Гельмгольца;2. Мозаично-скелетонный метод впервые применён к решению трёхмерных скалярных стационарных задач дифракции;3. Впервые создана параллельная версия метода для систем с общей памятью.Теоретическая и практическая ценность. В данной работе исследовано применение мозаично-скелетонного метода к решению СЛАУ, аппроксимирующих интегральные уравнения Фредгольма I рода. Мозаичный методразработан и реализован в виде дополнительных модулей к программам решения краевых задач для уравнения Гельмгольца и задач дифракции.
Проведены численные эксперименты, по результатам которых сделан вывод обэффективности использования быстрого метода для данного класса задач.Мозаично-скелетонный метод может быть использован для решения другихзадач математической физики, которые формулируются в виде граничныхинтегральных уравнений.Публикации. Основные результаты диссертации опубликованы в работах [28]– [37]. Для программ численного решения рассматриваемых задачполучены два свидетельства о регистрации программного продукта [38, 39].11Cтруктура работы. Работа состоит из введения, трёх глав и заключения. Работа написана на 72 страницах и содержит 10 таблиц, 25 рисунков исписок использованных источников из 43 наименований.Глава 1 состоит из двух параграфов, в которых приведены обобщённыепостановки задач Дирихле для уравнения Гельмгольца и задачи дифракции.Также эта глава содержит теоремы единственности решений исходных задач.В первом параграфе рассмотрены интегральные постановки задач Дирихледля уравнения Гельмгольца.
Во втором параграфе представлены интегральные уравнения, эквивалентные задачам дифракции. Для рассматриваемыхинтегральных уравнений приведены теоремы эквивалентности исходным задачам. Данная глава использует материалы работ [4]– [9].Глава 2 состоит из двух параграфов, первый из которых содержит описание численного метода решения исходных задач. Данный параграф также содержит дискретные аналоги соответствующих интегральных уравненийи метод их аппроксимации системами линейных алгебраических уравнений.Параграф использует результаты работ [4]– [9].
Второй параграф содержитописание мозаично-скелетонного метода, в частности, подробно рассмотренывсе этапы метода. Кроме того приведен алгоритм построения неполной крестовой аппроксимации, который является заключительным шагом мозаичноскелетонного метода. Также приведены оценки погрешности такой аппроксимации. Рассматриваемый параграф основан на результатах работ [15]– [22].В главе 3 представлено описание работы программ и их параллельныхверсий, а также результаты численных экспериментов решения задач Дирихле для уравнения Гельмгольца и задач дифракции акустических волн.Глава содержит 4 параграфа, первые три относятся к программной реализации решения исходных задач.
В них подробно описана структура программи технология сборки, а также реализации параллельной версии мозаичноскелетонного метода и матрично-векторного умножения.Последний параграф содержит примеры решения задач. Примеры различаются формой включения, параметрами сред и типом источника. В рамках численных экспериментов проведено сравнение времени решения СЛАУс использованием мозаично-скелетонного метода и без него, сделан выводоб эффективности использования мозаично-скелетонного метода.
Приведе12ны погрешности решения исходных задач и эквивалентных им граничныхинтегральных уравнений. Приведены результаты тестирования параллельной версии мозаичного метода и матрично-векторного умножения в GMRES.Данная глава использует работы [5, 9, 41].Апробация работы. Основные результаты работы докладывались наДальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток 2013, 2014), Всероссийской научно-практической конференции «Информационные технологии и высокопроизводительные вычисления» (Хабаровск, 2013), Первой международной конференции молодых ученых и специалистов (Баку, 2014), Третьей международной научной конференции «Информационные технологии и системы» (Челябинск, 2014), Конференции «Научно-техническое и экономическое сотрудничество стран АТРв XXI веке» (Хабаровск, 2013, 2015).В заключение автор выражает искреннюю благодарность своему научному руководителю Смагину Сергею Ивановичу, а также Каширину АлексеюАлексеевичу за помощь в работе.131Интегральные уравнения задач Дирихле для уравнения Гельмгольцаи задач дифракции акустическихволн1.1Обобщённые постановки задач ДирихлеРассмотрим трёхмерное евклидово пространство R3 с ортогональной системой координат 1 2 3 .
Пусть в этом пространстве имеется произвольнаязамкнутая липшицева поверхность Γ, разделяющая его на внутреннюю область Ω и внешнюю область Ω = R3 ∖Ω .Сформулируем исходные задачи [40].Задача 1 (внутренняя задача Дирихле). Найти функцию () ∈ 1 (Ω ),удовлетворяющую уравнению Гельмгольца∆ + 2 = 0, ∈ Ω ,(1.1)и граничному условию ∈ Γ. = ,(1.2)Задача 2 (внешняя задача Дирихле). Найти функцию () ∈ 1 (Ω ), удовлетворяющую уравнению Гельмгольца∆ + 2 = 0, ∈ Ω ,(1.3)граничному условию ∈ Γ, = ,(1.4)и условию излучения на бесконечности(︁−1 / || − = ||)︁,|| → ∞.(1.5)Здесь ∆ = ∇2 – оператор Лапласа, ∇ = (/1 , /2 , /3 ), – волновое число, Im() ≥ 0, () – след на Γ функции () , ∈ 1/2 (Γ) –14известная функция.
Определения используемых здесь и далее функциональных пространств имеются в работе [40].1Замечание 1. Если Im() = 0, то ∈ loc(Ω ).Справедливы следующие теоремы [40].Теорема 1. Пусть Im() > 0 или 2 не является собственным значениемзадачи∆ + 2 = 0, ∈ Ω , = 0, ∈ Γ.(1.6)Тогда для любой функции ∈ 1/2 (Γ) существует единственное решениезадачи 1 из пространства 1 (Ω ).Если же 2 – собственное значение задачи (1.6), то задача 1 разрешиматогда и только тогда, когда⟨, ⟩Γ = 0для всех собственных функций () задачи (1.6). В этом случае задача 1имеет бесконечное множество решений.Теорема 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
