Содержание к диссертации
Введение
1 Рандомизированные алгоритмы для решения больших систем линейных алгебраических уравнений . 9
1.1 Рандомизация с помощью случайных разреженных матриц. 10
1.2 Итерационные методы решения систем линейных алгебраических уравнений 15
1.2.1 Метод, основанный на преобразовании спектра
1.2.2 Нестационарный итерационный процесс со случайными параметрами 17
1.2.3 Рандомизация метода Гаусса-Зейделя 20
1.3 Дискретные варианты алгоритма блуждания по границе. 21
1.3.1 Алгоритм изотропного случайного блуждания по границе 22
1.3.2 Дискретная версия метода случайного блуждания по границе 22
1.4 Численные результаты 24
2 Рандомизированный алгоритм для сингулярного разложения матриц и его применения к моделированию случайных полей и реше нию систем линейных алгебраических уравнений . 32
2.1 Сингулярное разложение матриц 33
2.2 Варианты рандомизации сингулярного разложения матриц 34
2.2.1 Метод разреженного сингулярного разложения матриц . 34
2.2.2 Рандомизированный метод главных компонент 36
2.3 Моделирование случайных полей 38
2.3.1 Разложение Кархунена-Лоева 38
2.3.2 Дискретизация разложения Кархунена-Лоева 39
2.3.3 Численные эксперименты по моделированию неоднородных случайных полей 41
2.3.4 Численные результаты сравнения методов рандомизированного сингулярного разложения. 48
2.4 Алгоритмы блуждания по границе 50
3 Стохастические граничные методы фундаментальных решений и их приложения . 57
3.1 Формулировка метода фундаментальных решений 58
3.2 Уравнение Лапласа 60
3.3 Уравнения Ламе 61
3.4 Аппроксимация функции Грина 62
3.5 Дискретизация интеграла Пуассона 64
3.6 Метод, основанный на обращении интегральной формулы Пуассона 65
3.6.1 Система уравнений Ламе. 68
3.7 Сравнительные эксперименты 71
3.8 Задача о нахождении электроемкости для цепочки сфер. 81
Заключение 91
Список литературы
- Метод, основанный на преобразовании спектра
- Алгоритм изотропного случайного блуждания по границе
- Численные эксперименты по моделированию неоднородных случайных полей
- Метод, основанный на обращении интегральной формулы Пуассона
Введение к работе
Актуальность темы. С увеличением мощности вычислительной техники размерность задач и требуемый объем вычислений постоянно увеличиваются. Рандомизированные методы все чаще появляются в задачах, где требуется работать с данными большой размерности, например, при решении многомерных задач для уравнений в частных производных, трехмерных интегральных уравнений теории потенциала, при моделировании случайных полей, решении обратных задач томографии или кристаллографии, при решении уравнения Шрединге-ра, при моделировании турбулентных потоков и т.д. Область применения методов статистического моделирования для решения задач большой размерности ограничена следующими условиями: (1) дисперсия оценки мала, (2) не требуется большой точности, (3) вычислительная сложность случайной оценки растет медленно с возрастанием размерности т. Условие (3) достаточно часто выполнено, а вот условия (1) и (2) являются основной проблемой, так как скорость сходимости методов Монте-Карло мала, примерно как а/л/N, где а - среднеквадрати-ческое отклонение и N - размер выборки. Поэтому точность методов Монте-Карло на практике обычно не превосходит 1 — 2%. Уменьшение дисперсии часто достигается с помощью некоторого преобразования, результатом применения которого является случайная оценка с меньшей дисперсией. Уменьшение размерности задачи является одним из возможных приемов для уменьшения дисперсии. Например, дисперсия будет уменьшена, если при вычислении многократного интеграла возможно интегрирование только по части переменных.
За последние пару десятков лет, рандомизированные методы, основанные на явлении концентрации меры, интенсивно развивались. Первые результаты для концентрации были получены П. Леви в его книге по функциональному анализу. Явление концентрации мер приобрело большую популярность в математическом сообществе и нашло многочисленные приложения в функциональном анализе, геометрии, теории вероятности, комбинаторике и технических науках. Разработано много статистических методов для работы с большими матрицами, которые основаны именно на этой концепции. В линейной алгебре особенно стоит отметить следующие методы: рандомизированный проекционный метод, который был признан мощным инструментом для
уменьшения размерности. Также следует отметить фундаментальный результат Джонсона и Линденштрауса: для любого 0 < є < 1, множества X, состоящего из т точек в пространстве R , и для любого целого числа к > О(-^^), существует отображение /: Rw —* Rfc, такое что V-u, v Є X выполнено
(1 - е)\\и - v\\2 < \\f(u) - f(v)\\2 < (1 + е)\\и - v\\2.
В последнее время появилось множество работ по рандомизации различных матричных операций: произведение матриц, сингулярное разложение и др. В данной работе для нахождения решения применялись несколько рандомизированных алгоритмов для работы с матрицами большой размерности: метод разрежения, рандомизированный метод сингулярного разложения и рандомизированный метод главных компонент.
В последние десятилетия значительные усилия исследователей были направлены на развитие так называемых бессеточных численных методов. Среди этих методов большую популярность завоевал метод фундаментальных решений - граничный бессеточный метод аппроксимации решений однородных эллиптических уравнений. Для аппроксимации решения однородного эллиптического уравнения L[u] = О метод фундаментальных решений использует линейную комбинацию сингулярных решений (х, у) этого же уравнения с координатами син-гулярностей у (координатами источников) за пределами области решения. Таким образом, применение метода фундаментальных решений предполагает, что фундаментальные решения рассматриваемого уравнения известны в явном аналитическом виде. Хотя это обстоятельство сужает сферу применения, тем не менее, в последние десятилетия этот метод нашел обширные приложения в инженерных расчетах. При использовании даного метода исследователи столкнулись со следующими особенностями: (1) полученные системы уравнений являются плохо обусловленными, (2) в случае сложных невыпуклых областей его применение приводит к решению прямоугольных систем большой размерности. Метод фундаментальных решений был впервые предложен В. Д. Купрадзе и М. А. Алексидзе как метод обобщенных рядов Фурье. Более общий подход, основанный на аппроксимации граничного условия линейной комбинацией полного набора функций, использовался в методе Треффца.
Цель работы. Основные цели работы можно сформулировать следующим образом:
Построение и численное исследование нового алгоритма рандомизации итерационных методов решения линейных алгебраических уравнений на основе случайных разреженных матриц.
Построение дискретного варианта метода блуждания по границе, позоляющий эффективно решать многомерные задачи теории потенциала для невыпуклых областей.
Построение эффективных методов моделирования однородных и неоднородных гауссовских случайных полей с заданным корреляционным тензором.
Построение стохастического граничного алгоритма решения многомерных краевых задач на основе рандомизированных вариантов метода фундаментальных решений.
Научная новизна.
Построены новые рандомизированные итерационные методы для решения больших систем линейных алгебраических уравнений. В частности, построен рандомизированный метод Гаусса-Зейделя, позволяющий расширить область применимости стандартного метода Монте-Карло для решения краевых задач.
Предложен новый дискретный вариант алгоритма блуждания по границе для решения задачи Дирихле для уравнения Лапласа на основе низкорангового приближения ядра интегрального уравнения с помощью вырожденных ядер.
Разработана новая дискретная рандомизированная модель для однородных и неоднородных случайных полей с заданным корреляционным тензором, в основе которой лежит рандомизация низкорангового приближения для разложения Кархунена-Лоэва.
Построен и исследован граничный стохастический метод решения многомерных краевых задач на основе рандомизации интегральных операторов простого и двойного слоя. При этом решение строится в виде суперпозиции фундаментальных решений со случайным распределением точек коллокации и источников. Для решения полученной системы линейных алгебраических уравнений использовался метод рандомизированного сингулярного разложения, что является существенным, так как использование метода фундаментальных решений часто приводит к решению плохообусловленных систем.
Теоретическая и практическая ценность. Результаты данной работы представляет интерес для теории и практики методов Монте-Карло, в частности, позволяет существенно расширить область применимости к решению таких традиционных задач статистического моделирования как решение больших систем линейных алгебраических уравнений и моделирование неоднородных случайных полей.
Рандомизированный метод фундаментальных решений доведен до решения практических интересных задач о вычислении емкости систем пересекающихся шаров, а также расчета диффузионной активности фрактальных частиц такой формы.
Личный вклад. Автор диссертации принимала активное участие в подготовке всех совместных статей, в особенности на стадиях разработки алгоритмов моделирования и комплекса вычислительных программ, а также при проведении численных экспериментов и анализе результатов. Вклад Моцартовой Н.С. в совместные статьи можно оценить в 50%.
Аппробация работы. Результаты, изложенные в диссертации, были доложены и обсуждались на учебно-научном семинаре «Методы Монте-Карло в вычислительной математике и математической физике», на XLVI Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2008), на седьмом семинаре IMACS методы Монте-Карло (Брюссель, 2009), на международной конференции по Вычислительной математике (Новосибирск, 2009 и 2011), на седьмой международной конференции NM&A (Болгария, 2010).
Публикации. Основные результаты диссертации опубликованы
в работах [1-5]. Из них 3 работы - в журналах из списка ВАК.
Объём и структура диссертации. Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы. Объем диссертационной работы 99 страниц. Список литературы состоит из 106 наименований.
Метод, основанный на преобразовании спектра
Пусть дана тхп матрица А достаточно большой размерности и требуется построить аппроксимацию для первых к С max(m, п) сингулярных значений и соответствующих правых сингулярных векторов. Основная идея большинства рандмизированных методов сингулярного разложения заключается в построении некоторой аппроксимации В исходной матрицы меньшего размера и в нахождении сингулярных чисел и векторов уже у новой матрицы В. Далее применяя к полученным сингулярным векторам и значениям обратное преобразование, строится аппроксимация сингулярного разложения исходной матрицы А.
В данной главе мы рассмотрим два алгоритма рандомизированного сингулярного разложения [50,76]. Метод разреженного сингулярного разложения матриц.
Данный подход состоит в следующем: случайно выбрать s строк в матрице А, сформировать s х s матрицу В и вычислить её сингулярное разложение. Подробный анализ данного алгоритма приведен в работе [50]. Рандомизированный алгоритм разреженного сингулярного разложения матриц Выбираем некоторое вероятностное распределение
Найденные Лі,... Ад, и Нк являются аппроксимацией первых к сингулярных значения и правых сингулярных векторов матрицы А соответственно.
В работе [32] были получены оценки погрешности и трудоемкости для метода разреженного сингулярного разложения матриц. Обозначим Ак наилучшую аппроксимацию ранга к матрицы А и Р = АНкНк оценку, полученную с использованием алгоритма разреженного сингулярного разложения. Предположим, что вероятностное распределение столбцов матрицы А удовлетворяет pi /3A(j)2/A, для некоторого положительного /3 1. Выберем некоторое є 0. Для s 4:к//3є2 верна следующая оценка:
Вычислительные затраты для аппроксимации сингулярных чисел и соответствующих правых сингулярных векторов для т х п матрицы А составляют Т = Тsampung + Tmuu + TSVD + Tinvop = О (Тsampling + S П + S + Usk) , где TsampUng - вычислительные затраты на выбор s строк матрицы А в соответствии с вероятностным распределением, Ттиц - на произведение S ST, T$VD - трудоемкость сингулярного разложения матрицы s х s, Tinvop - затраты на применение к полученным сингулярным векторам обратного преобразования.
Следует отметить, что выбор вероятностного распределения строк влияет на полученную аппроксимацию сингулярных чисел и векторов. Численные результаты по сравнению погрешности в зависимости от распределения приведены в работе [50]. Оптимальным является следующее дискретное распределение
В работе [50] предлагается использовать алгоритм моделирования дискретного распределения, для которого Т"sampling — slogm операций. Метод Уолкера [89] позволяет уменьшить вычислительные затраты Тзатрцпд до О (га). Следует заметить, что О (га) - это трудоемкость подготовительного этапа метода Уолкера. Реализации выборочного значения будет заключаться только в одном обращении к генератору случайных чисел.
Для того чтобы построить оценку левых сингулярных векторов матрицы А надо в приведенном алгоритме вместо строк выбирать столбцы и в оценках трудоемкости сделать замену размерности п на га.
Рандомизированный метод главных компонент Метод главных компонент - один из методов, позволяющих уменьшить размерность данных, потеряв наименьшее количество нужной информации. Данный метод начался с задачи аппроксимации данных линейными многообразиями меньшей размерности (работа К. Пирса в 1901 году [77]). Вычисление главных компонент сводится к вычислению собственных векторов и собственных значений корреляционной матрицы исходных данных. Метод применяется во многих областях, таких как распознавание образов, сжатие данных, биоинформатике и т. п. Алгоритм, приведенный ниже, представлен в работе [76].
Алгоритм рандомизированного метода главных компонент Предположим, что г, к, т и п положительные целые числа, такие что 2к т п, и А вещественная матрица размера га х гг.
Следует отметить, что применение данного алгоритма эффективно только при достаточно быстроспадающем спектре исходной матрицы. 2.3 Моделирование случайных полей
Случайные поля являются мощным математическим инструментом при моделировании стохастических неоднородных сред и явлений. Например, в метеорологии, гидрологии, во множестве разделов физики, экономике, биологии и т.д., - везде, где приходится иметь дело с последовательностями наблюдений, флуктуирующими около своего среднего уровня.
Рассмотрим случайное поле {u(t),t Є Т}, определенное на некотором множестве Т Є R , и введем обозначения m{t) = Eu{t) для функции математического ожидания и B(t, s) = E{u{t) — m(t))(u(s) — m(s)) для корреляционной функции. Поле u{t) называется однородным, если m(t) = const и B(t, s) зависит только от {t — s). Функции m{t) и B(t, s) полностью определяют u(t) в случае гауссовского случайного поля.
Наиболее часто используемый подход для моделирования однородных случайных полей заключается в построении рандомизированной спектральной модели. Спектральные представления случайного поля и его корреляционной функции имеют вид вещественные ортогональные гауссовские стохастические меры на полупространстве P, fi(dX)- спектральная мера случайного поля u(t), ( , ) обозначает скалярное произведение [78,80,90].
Основная идея, лежащая в основе методов построения спектральных моделей, состоит в том, чтобы в качестве численной модели случайного поля u{t) взять некоторую аппроксимацию стохастического интеграла (2.6).
В данном разделе будет рассмотрен рандомизированный алгоритм для моделирования случайных гауссовских полей, основанный на разложении корреляционного оператора. Основное преимущество данного подхода состоит в том, что он позволяет моделировать также неоднородные поля.
Разложение Кархунена-Лоева Рассмотрим вещественное неоднородное случайное поле и(х), х Є G определенное на вероятностном пространстве (П, А, Р). Область G в наших численных экспериментах считается ограниченной, но случай неограниченной области также может быть рассмотрен, этот результат был получен в работах [83].
Предположим, что случайное поле и(х) имеет среднее, равное нулю и дисперсию Е и2(х), ограниченную для всех х Є G. Разложение Кархунена-Лоева для случайного поля и(х) представимо в следующем виде
Алгоритм изотропного случайного блуждания по границе
Сравним методы рандомизированного сингулярного разложения из главы 2.2 : алгоритм разреженного сингулярного разложения и алгоритм рандомизированного метода главных компонент. Рассмотрим матрицу, построенную для поля Лоренца по формуле (2.18), размерности 1500 и сравним времена расчетов и погрешность для Таблица 2.2: Первые 10 собственных значения для фрактального Винеровского процесса для различных значений параметра H для корреляционной матрицы размера 960 960. Последняя строка подтаблицы показывает значение p - количество собственных значений больше 0.01.
Графики зависимости погрешности (левый график) и времени расчетов (правый график) от ранга аппроксимации k для метода главных компонент и метод разреженного сингулярного разложения. различных значений s = k (Рис.2.9).
Из правого графика Рис.2.9 видно, что рандомизированный метод главных компонент является более трудоемким, и с увеличением количества выбираемых строк время почти не меняется. При сравнении погрешностей двух методов, мы можем сделать вывод, что для k 15, т.е. если нас интересует первых несколько сингулярных вектора и числа, следует использовать рандомизированный метод главных компонент. А вот для k 16 метод разреженного сингулярного разложения быстрее и обеспечивает меньшую погрешность. На левом графике Рис.2.10 приведено сравнение сингулярных чисел с точными значениями, полученными при полном разложении матрицы. Как видно из данного графика, аппроксимация малых собственных значений - достаточно сложная проблема для рандомизированных методов. Метод разреженного сингулярного разложения хорошо аппроксимирует сингулярные числа до порядка 1.0e-4. Для рандомизированного метода главных компонент отклонение от точных значений происходит раньше, где-то около 1.0e-3, но в среднем и после него сохраняется скорость убывания и примерный порядок сингулярных чисел. На правом графике Рис.2.10 показано поведение аппроксимаций первой строчки корреляционной матрицы для s = k = 5 обоих методов.
Результаты сравнения сингулярных чисел, упорядоченных по убыванию, (левый график) и покомпонентное сравнение аппроксимации первой строчки корреляционной матрицы при s = k = 5(правый график) для метода главных компонент и метод разреженного сингулярного разложения.
Алгоритмы блуждания по границе В данной главе приведен смешанный метод, который использует рандомизированный метод сингулярного разложения и метод спарсификации, представленный в разделе 1.1.
Аппроксимация с использованием вырожденных ядер. В работе [17] представлен алгоритм, который преобразует исходное уравнение с расходящимся рядом Неймана в уравнение, матрица перехода которого имеет норму меньше единицы. Это достигается с помощью комбинации исходной матрицы и некоторых вырожденных ядер. Основная проблема в использовании данного алгоритма была в нахождении таких вырожденных ядер, с использованием которых сходимость преобразованной системы будет лучше. В данной главе предложено в качестве таких ядер рассматривать низкоранговые аппроксимации ранга к.
Рассмотрим данный метод на примере решения системы линейных алгебраических уравнений достаточно большого размера х = Ах. + b с п х п матрицей А и правой частью b = (b\,... ,bn)T. Предположим, что \\А\\ 1, таким образом ряд Неймана будет расходится.
В получена с помощью вычитания из матрицы А суммы матриц ранга 1, записанных в виде fjgf. Предположим, что такие матрицы найдены, и мы интересуемся соотношением между решением исходной системы х и решения уравнения с матрицей В.
Этот метод следует использовать, если преобразованная система с матрицей B обладает лучшими свойствами по сравнению с исходной системой с матрицей A, и значение r небольшое. Таким образом, в стандартных методах Монте-Карло, основанных на рандомизации ряда Неймана, данный метод может быть применен, если мы сможем найти разложение (2.19) с qB = B 1 для небольшого значения r. Рандомизированный метод сингулярного разложения является одним из возможных подходов для получения требуемого разложения в (2.19) и построения вспомогательной системы с матрицей перехода B. Используя это разложение, мы можем увеличивать количество используемых сингулярных чисел и соответствующих сингулярных векторов пока условие qB = B 1 не будет выполнено. Например, при решении задачи Дирихле для уравнения Лапласа в случае выпуклой области достаточно взять г = 1 [82], что полностью соответствует результатам численных экспериментов. Для невыпуклой области значение г может быть выбрано достаточно небольшим.Сделанные выводы верны также и для более общих сингулярных ядер теории потенциала, встречающихся в граничных интегральных уравнениях [53,81].
Метод блуждания по границе с использованием рандомизированного сингулярного разложения Известно, что граничные интегральные уравнения теории потенциала приводят после дискретизации к линейным системам с матрицами, которые допускают хорошую низкоранговую аппроксимацию [81].
В качестве тестовой задачи рассмотрим задачу Дирихле для уравнения Лапласа для выпуклой и невыпуклой области Au(z) = О, z Є D, и(у) = д(у), у Є Г где D Є Ш2 - односвязная ограниченная область, Г - граница области D гладкая по Ляпунову. Выражения для решения и неизвестной плотности, а также дискретизация этих уравнений приведена выше в разделе 1.3. Мы воспользуемся полученными формулами. Аппроксимация решения в точке z Є D запишется
Рассмотрим применение данного алгоритма при решении задачи Дирихле для уравнения Лапласа в случае выпуклой и невыпуклой области D. В качестве выпуклой области D был выбран эллипс с полуосями а=1.0иЬ=3.0, в качестве невыпуклой области эллипс с вырезом (1.6) с полуосями а = 1.0,6 = 3.0 и глубиной выреза равной q = 0.5. Количество выбранных узлов на границе равнялось те = 960. В таблицах 2.4 и 2.5 представлены первых t сингулярных значений {\І,І = 1,...,} для задачи с выпуклой и невыпуклой областью D соответственно. В последнем столбце таблицы (те = 960) представлены точные значения сингулярных чисел матрицы, полученных с помощью полного сингулярного разложения. В первых четырех столбцах приведены результаты аппроксимации Хі, полученные с помощью рандомизированного метода разреженного сингулярного разложения из раздела 2.2.1сs = 72,s = 96 s = 192 и s = 240.
Из результатов, приведенных в таблице 2.4, можно сделать вывод, что первые сингулярные числа разложения достаточно точно аппроксимируются уже для s = 192, а время расчетов значительно меньше времени затраченного на полное сингулярное разложение.
Для случая невыпуклой области результаты приведены в таблице 2.5. Из приведенной таблицы при сравнении сингулярных чисел для различных значений s видно, что при увеличении s аппроксимация улучшается, но погрешность аппроксимации сингулярных чисел при s = 192 больше для невыпуклого случая.
Для решения полученных к + 1 системы уравнений использовался нестационарный итерационный процесс со случайными параметрами рандомизированный с помощью случайным разреженных матриц из главы 1.1, раздел 1.2.2. При решении системы для метода спарсификации выбиралось / столбцов исходной 960 х 960 матрицы системы, для применения рандомизированного метода сингулярного разложения и получения аппроксимации ранга к выбиралось s строк исходной матрицы.
Численные эксперименты по моделированию неоднородных случайных полей
В этой главе представлены методы, применимые для решения краевых задач с эллиптическими операторами. Метод фундаментальных решений применим для решения задач, для которых фундаментальные решения известны в аналитическом виде. Дискретизация интеграла Пуассона и метод, основанный на обращении интегральной формулы Пуассона являются методами решения краевых задач, для которых выписан в явном виде интеграл Пуассона.
Представим общую схему применения этих методов:
1. Выберем вспомогательную область Da С D для внешней задачи и Da D D для внутренней задачи, где D - область определения задачи. Для метода фундаментальных решений нет жестких требований к выбору области Da, для двух других методов это должен быть круг или шар.
2. Выберем и зафиксируем тип.
Для метода фундаментальных решений и дискретизации интеграла Пуассона т - точки на границе области задачи Dиn- точки на границе вспомогательной области Da. Трудоемкость этого этапа существенно возрастает в случае сложных многосвязных областей. Для метода, основанного на обращении интегральной формулы Пуассона т = п и равно количеству членов ряда при аппроксимации интеграла Пуассона.
3. Перейдем от непрерывной к дискретной постановке задачи.
Для метода фундаментальных решений и дискретизации интеграла Пуассона этот пункт связан с выбором численного метода и построением матрицы и вектора правых частей системы. Для метода, основанного на обращении интегральной формулы Пуассона появляется необходимость численного интегрирования для каждого элемента матрицы системы и вектора правых частей. При увеличении размерности матрицы трудоемкость этого процесса быстро возрастает. Однако в связи с быстрой сходимостью итоговая трудоемкость остается вполне приемлемой, а метод обеспечивает высокую точность.
4. Построим решение системы линейных алгебраических уравнений.
Для решения полученных систем линейных алгебраических уравнений применялся метод рандомизированного сингулярного разложения. Выбор данного метода основан на необходимости решения систем с плохой обусловленностью.
Для численных экспериментов была выбрана задача Дирихле для уравнения Лапласа есть эллипс с разным значением v = f и к Є N. В качестве точного решения рассматривалась функция f(x,y) = ехр(кх)соз(ку) для различных к. Функция g(z) - след функции f(x,y) на границе области D. Вспомогательная область Da - круг радиуса R = 2max(fca, kb) + 1.
Для оценки поведения спектра матриц рассматриваемых методов была рассмотрена серия задач с увеличением диаметра области D для к = 1, 2,... , 10 и v = 3. В методах 1) и 2) количество точек коллокации с увеличением диаметра линейно возрастало( примерно как 100 к). Это было сделано, чтобы сохранить длину дуги между двумя соседними точками.
Спектр: первые 20 сингулярных значений для метода фундаментальных реше-ний(левый график) и метода дискретизации интеграла Пуассона(правый график), размерность матриц от n = 100 до n = 900. Рис. 3.2: Спектр: первые 20 сингулярных значений для метода, основанного на обращении интегральной формулы Пуассона(левый график), размерность матриц от n = 200 до n = 1000, и сравнение спектров всех трех методов для матрицы размера n = 500(правый график).
Поведение спектра при увеличении размерности матрицы показано на Рис.3.1 и на левом графике Рис.3.2. Следует отметить из этих графиков следующие особенности: а) сингулярные числа всех трех методов при увеличении размерности практически не меняются, б) сингулярных числа быстро убывают, примерно от 1 до І.Ое-4. На правом графике Рис.3.2 приведено сравнение спектров методов для п = 500. Ско-рость убывания спектра метода, основанного на обращении интегральной формулы Пуассона, наименьшая из рассматриваемых методов.
Для решения систем линейных алгебраических уравнений использовался метод рандомизированного сингулярного разложения. Данный метод обладает рядом преимуществ: он позволяет находить обобщенные решения прямоугольных систем и систем с быстроспадающим спектром, и также строить оценки для первых нескольких сингулярных чисел, правых и левых сингулярных векторов.
Рассмотрим метод фундаментальных решений более подробно и зададимся вопросом: как влияет распределение -источников на сходимость метода. Мы сравнили две возможные схемы распределения
Рассмотрим случай (a) подробнее. На графике Рис.3.4 отображено поведения ап проксимации решения при увеличении радиуса окружности с -источниками для точек на прямых \(левый график) и 2(правый график). Для R 7.05 полученное решение достаточно хорошо аппроксимирует точное решение и эти графики не приведены. При R 7.05 мы видим резкий всплеск погрешности. Из графика Рис.3.4 видно, что при увеличении радиуса погрешность аппроксимации увеличивается и оптимальным радиусом является R = 3.05.
В случае (6) мы рассмотрели два различных распределения точек в кольце. Распределение точек по углу в обоих случаях было изотропно.
1. Радиальная координата в первом случае имела нормальное распределение с математическим ожиданием, равным R\ + 0.5(i?2 — R\) и дисперсией а = 2 г. На графике Рис.3.5 отображено поведения аппроксимации решения при увеличении радиуса i?2, R\ фиксирован и равен 3.05. Из графика видно более плавное возрастание погрешности и гладкости аппроксимации по сравнению со случаем концентрических окружностей.
Решение задачи Дирихле с помощью метода фундаментальных решений с 5-источниками, имеющими нормальное распределение радиальной координаты в кольце. Решения вдоль прямых \(левый график) и 2(правый график).
Метод, основанный на обращении интегральной формулы Пуассона
Мы рассмотрели две характеристики системы: поведение сингулярных чисел и поведение L-кривой. На левом графике Рис.3.14 показано поведение сингулярных чисел для разных значений радиуса г. Можно заметить, что для малых значений г сингулярные числа спадают намного быстрее чем для значений г близких к R. Отсюда следует, что для малых значений г для аппроксимации решения понадобится меньшее количество членов сингулярного разложения.
Для решения системы линейных алгебраических уравнений Ад = Ь, где А — матрица размера (га, х п) использовался рандомизированный метод сингулярного разложения. Также предпо-лагалось, что матрица системы допускает аппроксимацию ранга а и решение представляется в виде правые и левые сингулярные вектора и { 7j, г = I,... ,а} - сингулярные значения матрицы системы А. Рассматривая только а первых членов сингулярного разложения, производилась регуляризация решения системы. Определить оптимальное значение параметра регуляризации а можно с помощью максимума кривизны L-кривой. Подробная информация о методе L-кривой и её связи с сингулярным разложением представлена в работе [105]. L-кривая - это параметрическая зависимость логарифма нормы регуляризован-ного решения lg \\да\\ от логарифма нормы невязки полученного решения и экспериментальных данных lg \\Ада — Ь\\, что можно записать
Суть данного метода состоит в вычислении для набора значений параметра регуляризации а кривизны L-кривой и поиске точки с максимальной кривизной. Значение параметра а, отвечающее оптимальному параметру регуляризации, лежит в области перегиба L-кривой.
На правом графике Рис.3.14 приведены L-кривые для разных значений г. При больших значения радиуса г график L-кривой ведет себя достаточно гладко, откуда можно сделать вывод, что фиксированное в наших экспериментах ограничение а = 750 меньше оптимального значения. При малых значения г можно легко заметить появление требуемых перегибов.
Далее рассмотрим, что будет происходить при увеличении количества шариков, образующих область D. Зафиксируем радиусы Л = 8.0 и г = 2.0 и рассмотрим поведение емкости в зависимости от расстояния между центрами 0 2 R. Из Рис.3.15 видно при "усилении невыпуклости"( при 2R) емкость возрастает, причем емкость ведет себя линейно от . При 0 значение емкости близко к 1, т.е. емкости шара.
Отношение электроемкости к радиусу при увеличении количества шаров в цепочке и варьировании расстояния I между центрами сфер.
Также был реализован следующий эксперимент: были рассмотрены цепочки из N = 5, N = 10 и N = 15 шариков, радиусы шариков были фиксированы R = 8.0, г = 2.0, а расстояние между центрами \І = f3,i = 1,..., N — 1}, где /3 - случайная равномерно распределенная величина на отрезке (0, 2R). Для каждого N наигрывалась выборка из 250, потом производилось усреднение.
Значение отношения C/R при случайном распределении центров шариков и при фиксированном расстоянии {U = R, г = 1,..., N} для N = 5,10,15.
Из результатов приведенных в Таблице 3.1 видно, что для любого числа шариков значение C/R при случайном распределении центров примерно близко к значению C/Д, полученного при фиксированном расстоянии между центрами для = R.
Рассмотрим цепочку сфер из N = 3 шариков с радиусом R = 8.0. Вспомогательные сферы имеют радиус г = 2.0. Центр первого шарика находится в начале координат. Расстояние между центрами фиксировано. Разобьем интервал [-R, (N— l)-\-R] определения задачи по оси x на подинтервалы {7» = [ХІ-\,ХІ],І = 1,...,е} для е = 500. Через каждую точку ХІ проведем плоскость перпендикулярную оси х. Дан е приведены графики Cj как функции от х для = 3.5 и = 15.5. Количество точек п = 20000 на границе области Дина границе вспомогательной области т = 2000. Из приведенных результатов можно заметить, что электроемкость при увеличении "невыпуклости"области возрастает, что полностью соответствует физическим данным.
Задача о нахождении электроемкости была решена также в случае, когда цепочка сфер расположена не на прямой, а на спирали. Области D - цепочка из N пересекающихся шаров с центрами, расположенными на спирали радиусом Rc с шагом hc. Область D и её граница Г определяются также как и в случае цепочки сфер на прямой. Данные цепочки будут характеризоваться радиусами шаров {Ri, і = 1,... , N}, расстояниями {І, І = 1,... , N — 1} между их центрами, а также радиусом спирали Rc и шагом спирали hc. Рис. 3.16: Емкость как функция от x для цепочки сфер, расположенных на прямой. Количество сфер N = 3, радиус шариков R = 8.0, радиус вспомогательных шариков г = 2.0. На графиках приведен результаты для разных значений расстояния между центрами шариков: = 3.5 на левом графике и = 15.5 на правом графике. Рис. 3.17: Область D, состоящая из 12 шариков с центрами, расположенными на спирали.
Посмотрим как размеры спирали влияют на поведение электроемкости. Рассмотрим цепочку из А = 50 шариков с Ri = R = 8.0, расстояние между центрами фиксировано і = 14.0, радиусы вспомогательных сфер г І = г = 2.0. Количество точек на границе области D равно п = 50000, количество точек на вспомогательных сферах равно т = 1750. В эксперименте менялись значения радиуса спирали Rc и шага спирали hc в интервале [16.1,49.1] с шагом 3.0.
Рис. 3.18: Слева график зависимости электроемкости от радиуса Rc и шага hc спирали. Справа график площади поверхности цилиндра, описанного около спирали с шариками при различных значения Rc,hc.
Расположение шариков менялось от самого плотного Rc = hc = 16.1 до Rc = hc = 49.1. На Рис.3.18 приведены слева график сравнения емкости и справа график площади поверхности цилиндра, содержащего спираль с цепочкой шариков, для различных значений Rc и hc.
