Рандомизированные методы решения краевых задач математической физики тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

На правах рукописи

Моцартова Надежда Сергеевна

РАНДОМИЗИРОВАННЫЕ МЕТОДЫ РЕШЕНИЯ КРАЕВЫХ ЗАДАЧ МАТЕМАТИЧЕСКОЙ ФИЗИКИ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

2 и НАР 2014

Новосибирск - 2014

005546210

005546210

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский национальный исследовательский государственный университет».

Научный руководитель:

доктор физико-математических наук, профессор Сабельфельд Карл Карлович. Официальные оппоненты:

Симонов Николай Александрович Д-Ф .-м.н., ведущий научный сотрудник. Baker Hughes, Новосибирский технологический центр,

Плотников Михаил Юрьевич к.ф.-м.н., старший научный сотрудник лаборатории разреженных газов, Федеральное государственное бюджетное учреждение науки Институт теплофизики им. С.С. Кутателадзе Сибирского отделения Российской академии наук. Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт нефтегазовой геологии и геофизики им. A.A. Трофимука Сибирского отделения Российской академии наук.

Защита состоится 26 марта 2014 г. в 15:00 часов на заседании диссертационного совета Д 003.061.01 на базе Федерального государственного бюджетного учреждения науки Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук (ИВМиМГ СО РАН) по адресу: 630090. Новосибирск, проспект академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения иаукн Института вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Автореферат разослан 21 февраля 2014 г.

Ученый секретарь

диссертационного совета Д 003.061.01 доктор физико-математических наук

Рогазинский Сергей Валентинович

Общая характеристика работы.

Актуальность темы. С увеличением мощности вычислительной техники размерность задач и требуемый объем вычислений постоянно увеличиваются. Рандомизированные методы все чаще появляются в задачах, где требуется работать с данными большой размерности, например, при решении многомерных задач для уравнений в частных производных, трехмерных интегральных уравнений теории потенциала, при моделировании случайных полей, решении обратных задач томографии или кристаллографии, при решении уравнения Шрединге-ра, при моделировании турбулентных потоков и т.д. Область применения методов статистического моделирования для решения задач большой размерности ограничена следующими условиями: (1) дисперсия оценки мала, (2) не требуется большой точности, (3) вычислительная сложность случайной оценки растет медленно с возрастанием размерности т. Условие (3) достаточно часто выполнено, а вот условия (1) и (2) являются основной проблемой, так как скорость сходимости методов Монте-Карло мала, примерно как <г/\/1У, где а - среднеквадрати-чсское отклонение и N - размер выборки. Поэтому точность методов Монте-Карло на практике обычно не превосходит 1 — 2%. Уменьшение дисперсии часто достигается с помощью некоторого преобразования, результатом применения которого является случайная оценка с меньшей дисперсией. Уменьшение размерности задачи является одним из возможных приемов для уменьшения дисперсии. Например, дисперсия будет уменьшена, если при вычислении многократного интеграла возможно интегрирование только по части переменных.

За последние пару десятков лет, рандомизированные методы, основанные на явлении концентрации меры, интенсивно развивались. Первые результаты для концентрации были получены П. Леви в его книге по функциональному анализу. Явление концентрации мер приобрело большую популярность в математическом сообществе и нашло многочисленные приложения в функциональном анализе, геометрии, теории вероятности, комбинаторике и технических науках. Разработано много статистических методов для работы с большими матрицами, которые основаны именно на этой концепции. В линейной алгебре особенно стоит отметить следующие методы: рандомизированный проекционный метод, который был признан мощным инструментом для

уменьшения размерности. Также следует отметить фундаментальный результат Джонсона и Линденштрауса: для любого 0 < е < 1, множества X, состоящего из т точек в пространстве К'^'. и для любого целого числа к > существует отображение /: Э.дг —Е^, такое

что \/и, 'ч 6 X выполнено

(1 - €)||и - «II2 < 11/Н - ¡(у)\\2 < (1 + 6)11« - Ч12.

В последнее время появилось множество работ но рандомизации различных матричных операций: произведение матриц, сингулярное разложение и др. В данной работе для нахождения решения применялись несколько рандомизированных алгоритмов для работы с матрицами большой размерности: метод разрежения, рандомизированный метод сингулярного разложения и рандомизированный метод главных компонент.

В последние десятилетия значительные усилия исследователей были направлены на развитие так называемых бессеточных численных методов. Среди этих методов большую популярность завоевал метод фундаментальных решений - граничный бессеточный метод аппроксимации решений однородных эллиптических уравнений. Для аппроксимации решения однородного эллиптического уравнения Ь[и] — О метод фундаментальных решений использует линейную комбинацию сингулярных решений £(х, у) этого же уравнения с координатами син-гулярностей у (координатами источников) за пределами области решения. Таким образом, применение метода фундаментальных решений предполагает, что фундаментальные решения рассматриваемого уравнения известны в явном аналитическом виде. Хотя это обстоятельство сужает сферу применения, тем не менее, в последние десятилетия этот метод нашел обширные приложения в инженерных расчетах. При использовании даного метода исследователи столкнулись со следующими особенностями: (1) полученные системы уравнений являются плохо обусловленными, (2) в случае сложных невьшуклых областей его применение приводит к решению прямоугольных систем большой размерности. Метод фундаментальных решений был впервые предложен В. Д. Купрадзе и М. А. Алексидзе как метод обобщенных рядов Фурье. Более общий подход, основанный на аппроксимации граничного условия линейной комбинацией полного набора функций, использовался в методе Треффца.

Цель работы. Основные цели работы можно сформулировать следующим образом:

• Построение и численное исследование нового алгоритма рандомизации итерационных методов решения линейных алгебраических уравнений на основе случайных разреженных матриц.

• Построение дискретного варианта метода блуждания но границе, позоляющий эффективно решать многомерные задачи теории потенциала для невыпуклых областей.

• Построение эффективных методов моделирования однородных и неоднородных гауссовских случайных полей с заданным корреляционным тензором.

• Построение стохастического граничного алгоритма решения многомерных краевых задач на основе рандомизированных вариантов метода фундаментальных решений.

Научная новизна.

• Построены новые рандомизированные итерационные методы для решения больших систем линейных алгебраических уравнений. В частности, построен рандомизированный метод Гаусса-Зейделя, позволяющий расширить область применимости стандартного метода Монте-Карло для решения краевых задач.

• Предложен новый дискретный вариант алгоритма блуждания по границе для решения задачи Дирихле для уравнения Лапласа на основе низкорангового приближения ядра интегрального уравнения с помощью вырожденных ядер.

• Разработана новая дискретная рандомизированная модель для однородных и неоднородных случайных полей с заданным корреляционным тензором, в основе которой лежит рандомизация низкорангового приближения для разложения Кархунена-Лоэва.

• Построен и исследован граничный стохастический метод решения многомерных краевых задач на основе рандомизации интегральных операторов простого и двойного слоя. При этом решение строится в виде суперпозиции фундаментальных решений со случайным распределением точек коллокации и источников. Для решения полученной системы линейных алгебраических уравнений использовался метод рандомизированного сингулярного разложения, что является существенным, так как использование метода фундаментальных решений часто приводит к решению плохообусловленных систем.

Теоретическая и практическая ценность. Результаты данной работы представляет интерес для теории и практики методов Монте-Карло, в частности, позволяет существенно расширить область применимости к решению таких традиционных задач статистического моделирования как решение больших систем линейных алгебраических уравнений и моделирование неоднородных случайных полей.

Рандомизированный метод фундаментальных решений доведен до решения практических интересных задач о вычислении емкости систем пересекающихся шаров, а также расчета диффузионной активности фрактальных частиц такой формы.

Личный вклад. Автор диссертации принимала активное участие в подготовке всех совместных статей, в особенности на стадиях разработки алгоритмов моделирования и комплекса вычислительных программ, а также при проведении численных экспериментов и анализе результатов. Вклад Моцартовой Н.С. в совместные статьи можно оценить в 50%.

Аппробация работы. Результаты, изложенные в диссертации, были доложены и обсуждались на учебно-научном семинаре «Методы Монте-Карло в вычислительной математике и математической физике», на XLVI Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2008), на седьмом семинаре IMACS методы Монте-Карло (Брюссель, 2009), на международной конференции по Вычислительной математике (Новосибирск, 2009 и 2011), на седьмой международной конференции NM&A (Болгария, 2010).

Публикации. Основные результаты диссертации опубликованы

в работах [1-5]. Из них 3 работы - в журналах из списка ВАК.

Объём и структура диссертации. Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы. Объем диссертационной работы 99 страниц. Список литературы состоит из 106 наименований.

Краткое содержание работы

Во введении дается краткий обзор литературы по изучаемым в диссертации вопросам, излагаются основные результаты и приведено краткое содержание по главам.

Первая глава диссертации посвящена применению алгоритма рандомизации с помощью случайных разреженных матриц к решению систем линейных алгебраических уравнений.

В разделе 1.1 приводится классический алгоритм рандомизации с помощью случайных разреженных матриц. Данный алгоритм применяется для решения систем со спектральным радиусом меньшим единицы. Приводится частный случай построения случайной разреженной матрицы, предложенный Ю. В. Булавским. Рассмотрен метод построения несмещенной оценки произведения матриц, который является обобщением алгоритма рандомизации с помощью случайных разреженных матриц, и приведены оценки дисперсии, математического ожидания и погрешности. Получено оптимальное вероятностное распределение, которое позволяет одновременно минимизировать дисперсию на каждом шаге итераций.

Во втором параграфе предложены новые алгоритмы рандомизации итерационных методов решения линейных алгебраических уравнений на основе случайных разреженных матриц. Были рассмотрены следующие методы: метод, основанный на преобразовании спектра, нестационарный итерационный процесс со случайными параметрами и метод Гаусса-Зейделя. Первые два метода не требуют приведения к явному виду и для их рандомизации достаточно на каждом шаге построить случайную оценку матрицы перехода.

В третьем параграфе на основе рандомизированных алгоритмов построен дискретный вариант метода блуждания по границе. Стандартный алгоритм блуждания по границе в случае выпуклых областей обладает замечательным свойством: дисперсия довольно медлен-

но возрастает с т как т2 ~ [1п(е)]2, где т - длина цепи Маркова, е - погрешность метода. В общем случае, когда область является невыпуклой, ядро граничного интегрального уравнения становится отрицательным в "невыпуклых частях"границы. Таким образом, в стандартном изотропном методе блуждания по границе необходимо ввести веса, из-за которых увеличится дисперсия. В новом варианте случайного дискретного блуждания по границе дисперсия не возрастает так быстро. Первая причина - в отличии от оценки по одному узлу, на каждом шаге используется набор из I узлов, которые могут быть выбраны как зависимыми, так и независимыми. Дисперсия быстро уменьшается с увеличением количества выбранных столбцов I. Вторая причина - тип выбранного итерационного процесса.

Раздел 1.4 содержит численные результаты применения метода аппроксимации матрицы последовательностью разреженных матриц к разным итерационным методам, поведение дискретного алгоритма случайного блуждания по границе для различных областей и влияние выбора вероятностного распределения строк на сходимость методов.

Вторая глава посвящена рандомизированному сингулярному разложению и его применению к моделированию случайных процессов и полей.

Во второй главе первые два раздела 2.1 и 2.2 являются вводными и содержат хорошо известную в литературе информацию. В разделе 2.1 дается общая теория сингулярного разложения матрицы и формулировка теоремы Экарта-Янга. В следующем разделе 2.2 приводятся два алгоритма рандомизированного сингулярного разложения: метод разреженного сингулярного разложения матриц и рандомизированный метод главных компонент, также приводятся оценки погрешности и трудоемкости обоих методов.

В разделе 2.3 па основе рандомиированиых методов сингулярного разложения матриц предложен новый рандомизированный алгоритм для построения разложения Кархунена-Лоэва. Общая теория разложение Кархунена-Лоэва, приведена в разделе 2.3.1. В разделе 2.3.2 описан дискретный аналог разложения Кархунена-Лоэва.

В разделе 2.3.3 предложен алгоритм моделирования однородных и неоднородных гауссовских случайных полей с заданной корреляционной матрицей, основанный на разложении Кархунена-Лоэва. Прн мо-

делировании использовалась следующая схема: рассматривались случайные процессы и поля на некоторой области С с заданным корреляционным оператором, выбиралась сетка в С и строилась дискретная аппроксимация корреляционного оператора - корреляционная матрица, с помощью алгоритма рандомизированного сингулярного разложения находились сингулярные числа и вектора корреляционной матрицы. Далее, используя дискретный аналог разложения Кархунена-Лоэва из раздела 2.3.2, получали аппроксимацию случайного поля. В качестве тестовых задач были рассмотрены случайное поле Лоренца и фрактальный Винеровский процесс.

В разделе 2.3.4 проведено численное сравнение методов рандомизированного сингулярного разложения из раздела 2.2.

Новый алгоритм блуждания по границе с использованием метода рандомизированного сингулярного разложения приведен в разделе 2.4. Метод аппроксимации с использованием вырожденных ядер, предложенный К. Сабельфельдом, позволяет перейти от решения системы х = Ах + Ь с матрицей системы А, для которой ||Л|| > 1, к решению г + 1 системы с матрицей

¿=1

норма которой уже меньше 1. Здесь /ъ . •., /г и 91, ■■■ ,Яг - некоторые вектора. В качестве тестовой задачи была рассмотрена задача Дирихле для уравнения Лапласа в случае выпуклой и невыпуклой области определения. Для решения использовалась следующая схема: строилась дискретная аппроксимация краевой задачи, получалась система уравнений, спектральный радиус матрицы перехода А которой равен 1, выбиралось и фиксировалось значение г. Далее вычислялись первые г сингулярных значения и низкоранговая аппроксимация Аг — игТ,гуТ с помощью рандомизированного сингулярного разложения, строилась вспомогательная матрица

г

В = А-Аг = А-^1г9Т , 1=1

где ^ = щ, (]1 = А^ и щ, у -, - 'столбцы матриц V),, V/.. соответственно,

Аг - сингулярные значения, используя метод аппроксимации с использованием вырожденных ядер получалось решение задачи.

Третья глава посвящена методам решения краевых задач с эллиптическим оператором, в особенности методу фундаментальных решений.

В разделе 3.1 описан метод фундаментальных решений, даются известные определения, свойства и оценки числа обусловленности и погрешности. В этом разделе показано как, используя метод фундаментальных решений, получить оценку значений нормальной производной от решения на границе.

В п. 3.2 и 3.3 рассмотрено применение метода фундаментальных решений для аппроксимации решений внутренней задачи Дирихле для уравнения Лапласа и системы уравнений Ламе.

В п. 3.4 уделено внимание решению неоднородных задач и аппроксимации функции Грина с использованием метода фундаментальных решений. Приведен алгоритм аппроксимации решения неоднородной задачи, использующий свойство симметрии функции Грина. Использование этого свойства позволяет значительно снизить вычислительные затраты.

В разделах 3.5 и 3.6 представлены метод дискретизации интеграла Пуассона и метод, основанный на обращении интегральной формулы Пуассона соответственно. Метод фундаментальных решений и методы из разделов 3.5 и 3.6 объединяет то, что в них строится вспомогательная область которая содержит область определения задачи .О, и продолжение решения за пределы области И вплоть до границы Ва. В методе фундаментальных решений предполагается, что фундаментальные решения рассматриваемого дифференциального оператора известны в явном аналитическом виде, в то время как методы, представленные в разделах 3.5 и 3.6, являются методами решения краевых задач, для которых выписан в явном виде интеграл Пуассона и вспомогательная область Оп - это круг или шар.

Рассмотрим применение методов из раздела 3.5 и 3.6 на примере решения внутренней задачи А'и(х) =0, х € И с заданной функцией на границе м|г = д■ Круг К{0, В) радиуса В, с центром в нуле содержит область определения задачи Д Ос Л"(0, В), ¿>(0, В) - граница круга.

Запишем интеграл Пуассона для вспомогательного круга К(О, R)

"<*> = ш / f^r'^ • (1)

S(0,R)

где функция f(y) является неизвестной величиной. Используя граничное условие м|г = 9, получаем следующее уравнение первого рода

«(*>-йй / (2)

5(0,Я)

Определив из этого уравнения значения f{y) на границе диска можно найти решение задачи во всей области D по формуле (1).

В методе раздела 3.5 решение задачи определяется следующим образом: вводится сетка на границе Г и строится дискретный аналог уравнения (2). Далее необходимо решить систему линейных алгебраических уравнений и воспользоваться уравнением (1) для аппроксимации решения.

В методе, основанном на обращении интегральной формулы Пуассона уравнение (1) записывается в полярной системе координат и ядро интеграла Пуассона представляется в виде ряда

1 R2 т^ 1 1 00

(3)

Ряд (3) заменяется частичной суммой длины m в уравнении (2). Преобразуя полученное уравнение, приходим к системе уравнений

/•27Г г2П

Ac=b, oíj= / /3i(0)aj(r,0)d0, h= / g(0)¡3i(0)d9 , (4) Jo Jo

где i = 1,..., 2m + l,j = 1,... ,2m + 1 и

/W) = = ^

для к = 1,...,тп. Зная решение с данной системы, аппроксимация и,п(г,8) решения задачи и(х) определяется

В разделе 3.6.1 метод, основанный на обращении интегральной формулы Пуассона применен для решения системы уравнения Ламе.

Раздел 3.7 содержит результаты численных экспериментов. Для решения систем линейных алгебраических уравнений использовался метод рандомизированного сингулярного разложения. Приведены сравнение спектров рассматриваемых методов решения краевых задач, анализ влияние распределения источников в методе фундаментальных решений на сходимость метода, поведение аппроксимации решения, полученного с помощью метода рандомизированного сингулярного разложения для различных рангов к.

Во многих прикладных физических задачах требуется решить внешнюю задачу Дирихле для уравнения Лапласа, например для для расчета коэффициента захвата сложными частицами аэрозолей, в задачах коагуляции, для расчета емкости и распределения заряда на поверхности и т.д. В разделе 3.8 приведено решение задачи о нахождении электроемкости для невыпуклой области с помощью метода фундаментальных решений. В качестве невыпуклой области была рассмотрена цепочка из пересекающихся шариков, центры которых располагались на прямой и на спирали. Для случая двух пересекающихся шариков приведен подробный анализ: влияние радиуса вспомогательных внутренних сфер на решение системы, сравнение полученного значения электроемкости с физическими данным. Приведены результаты при увеличении количества шариков в цепочке от 10 до 100, при этом решалась прямоугольная система размерности 1 750 х 50 000. Также приведены результаты при различных значений расстояния между центрами сфер. Рассмотрено поведение плотности заряда на границе трех пересекающихся шариков для разных расстояний между центрами. Из экспериментов для цепочки шариков на прямой и на спирали можно сделать следующие выводы, что значение электроемкости возрастает вследствие следующих причин.

2т+1

(6)

к=1

• При увеличении количества шариков с центрами расположенными на прямой, площадь границы увеличивается линейно и было получено линейное возрастание емкости.

• При увеличении расстояния между шариками, увеличивается "степень певыпуклости"границы и на невыпуклых участках значение емкости возрастает.

• При расположении цепочки шариков на спирали заметно, что при увеличении радиуса спирали значение емкости уменьшается. Причиной такого поведения является уменьшение "степень невыпуклости "всей цепочки, так как в случае спирали каждый шарик оказывает влияние не только на соседние, но и на всю систему в целом.

Также для проверки приведенного алгоритма решения внешней краевой задачи была решена задача с известным аналитическим решением: задача о нахождении электроемкости для эллипсоида вращения. Решалась система размерности 4 ООО х 96 ООО.

Заключение

Сформулируем основные результаты диссертационной работы:

1. Предложены новые алгоритмы рандомизации итерационных методов решения линейных алгебраических уравнений на основе случайных разреженных матриц и специальных преобразований спектрального параметра.

2. На основе рандомизированных алгоритмов построен дискретный вариант метода блуждания по границе, позволяющий эффективно решать многомерные задачи теории потенциала для невыпуклых областей.

3. На основе рандомизированных методов сингулярного разложения матриц предложен рандомизированный алгоритм для построения разложения Кархунена-Лоэва и моделирования на его основе однородных и неоднородных гауссовских случайных полей с заданной корреляционной матрицей.

4. Построен стохастический граничный алгоритм решения многомерных краевых задач на основе рандомизированных вариантов метода фундаментальных решений, при этом точечные источники и точки коллокации выбираются случайно распределенными, и задача сводится к решению большой прямоугольной системы с помощью рандомизированного метода сингулярного разложения.

5. С помощью разработанного рандомизированного метода фундаментальных решений решена задача о расчете электроемкости и коэффициента поверхностной активности для полимерных цепочек, состоящих из множества пересекающихся сфер.

Пользуясь случаем, автор выражает благодарность Сабельфельду Карл Карловичу за научное руководство.

Работы автора по теме диссертации

[1] К. Sabelfeld, N. Mozartova Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary Methods. // Monte Carlo Methods and Applications.-2009.-Vol. 15 №3.-P.257-284.

[2] K. Sabelfeld, N. Mozartova Sparsified Randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation. //Mathematics and Computers in Simulation, Volume 82, Issue 2, October 2011, Pages 295-317.

[3] K. Sabelfeld, N. Mozartova Stochastic boundary collocation and spectral methods for solving PDEs. // Monte Carlo Methods and Applications.-202.-Vol. 18 №3.-P.217-264.

[4] K. Sabelfeld, N. Mozartova Sparsified Randomization Algorithms for large systems of linear equations. //Thesis of Seventh IMACS Seminar on Monte Carlo Methods, MCM2009, Brussels, September 6-11, 2009.

[5] K. Sabelfeld, N. Mozartova Sparsified Randomization Algorithms for the SVD based Low Rank Approximations //Thesis of Numerical Methods and Applications, Seventh International Conference, August 20-24, 2010, Borovets, Bulgaria

Моцартова Надежда Сергеевна

Рандомизированные методы решения краевых задач математической

физики

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Подписано в печать 18.02.2014 Формат 60x84 1\1 б Усл. печ. л. 1 Объем 16 стр. Тираж 100 экз. Заказ № 55 Отпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лаврентьева,6 email: omegap@yandex.ru

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Новосибирский национальный исследовательский государственный университет»

Моцартова Надежда Сергеевна

Рандомизированные методы

решения краевых задач математической физики

Специальность 01.01.07 - вычислительная математика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.ф.-м.н., профессор Сабельфельд Карл Карлович

04201456931

На правах рукописи

в

Новосибирск - 2013

Оглавление

Введение..............................................................................4

1 Рандомизированные алгоритмы для решения больших систем линейных алгебраических уравнений. 9

1.1 Рандомизация с помощью случайных разреженных матриц................10

1.2 Итерационные методы решения систем линейных алгебраических уравнений ............................................................................15

1.2.1 Метод, основанный на преобразовании спектра....................15

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

Список литературы..................................................................92

Введение

Статистическое моделирование (или метод Монте-Карло) - это численный метод решения математических задач при помощи моделирования случайных величин [1]. Датой рождения метода Монте-Карло принято считать 1949 год, когда была опубликована статья Метрополиса и Улама [2]. Однако до появления вычислительных машин этот метод не имел широкого применения из-за трудоемкости моделирования большого числа случайных величин. Таким образом, возникновение и интенсивное развитие методов Монте-Карло стало возможным благодаря появлению вычислительной техники.

Метод Монте-Карло естественно применяется при моделировании любого процесса, на протекание которого влияют случайные факторы, например при решении задач статистической физики, теории турбулентности, теории переноса. Статистическое моделирование используется и для решения многих математических задач, не связанных с какими-либо случайностями, но для которых можно искусственно придумать вероятностную модель, таких как вычисление числа 7Г (предложенная Бюффоном в 1777 году), решение линейных интегральных и алгебраических уравнений, обращение матриц [3-5]. В первой работе на эту тему [2] была представлена схема Неймана-Улама, область применения которой ограничена условием сходимости ряда Неймана. Основная идея метода Неймана-Улама состояла в построении случайных оценок членов ряда Неймана на основе цепи Маркова в соответствии с ядром данного линейного уравнения. Применения методов Монте-Карло для решения интегральных уравнений были традиционно ограничены задачами переноса излучения и уравнениями диффузии [6,7]. Для решения применялся метод случайного блуждания по решетке (одни из первых работ по случайному блужданию для решения задач в частных производных в конечномерном пространстве [8,9]). В работе [10] представлены варианты различных модификаций первоначальной схемы Неймана-Улама, направленные на улучшение свойств дисперсии. Следует отметить большое количество других методов [11,12], представляющих собой рандомизированные оценки итераций на основе цепи Маркова. В работе [13] был разработан метод случайного блуждания по сферам, основанный на методе релаксации и методе Гаусса-Зейделя с черно-красной нумерацией.

В 1982 году К. Сабельфельд предложил в своей работе [14,19] первый метод Монте-Карло для решения интегральных уравнений с расходящимся рядом Неймана. Основная идея заключалась в перегруппировке членов ряда Неймана интегрального уравнения и подборе весов, таких, чтобы преобразованный ряд сходился и было возможным его устойчивое вычисление. Это было достигнуто с помощью конформного преобразования спектрального параметра интегрального уравнения, хорошо известного из линейной алгебры [15,16]. Фактически каждое конформное преобразование порождает соответствующий итерационный процесс [17].

Мотивацией при разработке метода, представленного в работе [14], было сконструировать метод Монте-Карло, который позволяет решать граничные интегральные уравнения, представимые в виде потенциалов простого и двойного слоя, плот-

ность которых удовлетворяет интегральным уравнениям со спектральным радиусом равным единице. Метод преобразования спектрального параметра был применен для решения таких задач. В итоге был сконструирован метод блуждания по границе, который наиболее эффективен для выпуклых областей. В случае невыпуклых областей данный метод также применим, но дисперсия существенно возрастает с увеличением "невыпуклости области". Метод блуждания по границе применим для решения всех классических внутренних и внешних граничных задач теплопроводности, упругости и электростатики [18-20]. Эргодическая версия алгоритма случайного блуждания по границе была предложена в работе [21] для решения задачи Робена. Множество других применений алгоритма блуждания по границе было разработано, например, в работе [22] рассматривались задачи теории упругости, а в [23] данный метод используется для вычисления электроемкости. Все эти алгоритмы хорошо применимы для выпуклых областей и сталкиваются с проблемой сильного увеличения дисперсии в случае невыпуклой области. Некоторые преобразования были предложены для того, чтобы как-то преодолеть быстрое увеличение дисперсии, например метод стабилизации в [19], раздел 6.2, или ветвление изотропного случайного блуждания по границе [24].

Новая дискретная версия алгоритма блуждания по границе предложена в нашей работе [25]. Применение данного алгоритма для решения граничных интегральных уравнений можно разделить на две основные части: 1) построение сетки на границе области и дискретного аналога интегрального уравнения, 2) применение метода рандомизированной оценки большой матрицы набором случайных матриц меньшей размерности. Основная особенность данного алгоритма состоит в том, что дисперсия незначительно возрастает при переходе от выпуклой области к невыпуклой. Идея рандомизации больших матриц набором случайных матриц меньшей размерности не является новой. Этот метод применяют для построения аппроксимации меньшего ранга [26-30], для рандомизации итерационного метода Ланцоша [31], при вычислении произведения матриц [32,33]. Во всех этих работах было подтверждено, что использование рандомизации является эффективным при работе с очень большими системами.

С увеличением мощности вычислительной техники размерность задач и требуемый объем вычислений постоянно увеличиваются. Рандомизированные методы все чаще появляются в задачах, где требуется работать с данными большой размерности, например, при решении многомерных задач для уравнений в частных производных, трехмерных интегральных уравнений теории потенциала, при моделировании случайных полей, решении обратных задач томографии или кристаллографии, при решении уравнения Шредингера, при моделировании турбулентных потоков и т.д. Область применения методов статистического моделирования для решения задач большой размерности ограничена следующими условиями: (1) дисперсия оценки мала, (2) не требуется большой точности, (3) вычислительная сложность случайной оценки растет медленно с возрастанием размерности т. Условие (3) достаточно часто выполнено, а вот условия (1) и (2) являются основной проблемой, так как скорость сходимости методов Монте-Карло мала, примерно как а/ у/П, где а - среднеквадра-

тическое отклонение и^- размер выборки. Поэтому точность методов Монте-Карло на практике обычно не превосходит 1—2%. Уменьшение дисперсии часто достигается с помощью некоторого преобразования, результатом применения которого является случайная оценка с меньшей дисперсией. Уменьшение размерности задачи является одним из возможных приемов для уменьшения дисперсии. Например, дисперсия будет уменьшена, если при вычислении многократного интеграла возможно интегрирование только по части переменных.

За последние пару десятков лет, рандомизированные методы, основанные на явлении концентрации меры [34], интенсивно развивались. Первые результаты для концентрации были получены П. Леви в его книге по функциональному анализу [35]. Явление концентрации мер приобрело большую популярность в математическом сообществе и нашло многочисленные приложения в функциональном анализе, геометрии, теории вероятности, комбинаторике и технических науках. Разработано много статистических методов для работы с большими матрицами, которые основаны именно на этой концепции. В линейной алгебре особенно стоит отметить следующие методы: рандомизированный проекционный метод, который был признан мощным инструментом для уменьшения размерности [36-39]. Также следует отметить фундаментальный результат Джонсона и Линденштрауса [40]: для любого 0 < е < 1, множества X, состоящего из т точек в пространстве М^, и для любого целого числа к > О(^р), существует отображение /: —» такое что Ми, V 6 X выполнено

(1 - е)||и - < ||/(и) - /(«)|| < (1 + е)||и - г>||2-

В последнее время появилось множество работ по рандомизации различных матричных операций: произведение матриц, сингулярное разложение и др., [25,26,28-32,4153]. В данной работе для нахождения решения применялись несколько рандомизированных алгоритмов для работы с матрицами большой размерности: метод разрежения, рандомизированный метод сингулярного разложения и рандомизированный метод главных компонент.

В последние десятилетия значительные усилия исследователей были направлены на развитие так называемых бессеточных численных методов. Среди этих методов большую популярность завоевал метод фундаментальных решений - граничный бессеточный метод аппроксимации решений однородных эллиптических уравнений. Для аппроксимации решения однородного эллиптического уравнения Ь[и] = 0 метод фундаментальных решений использует линейную комбинацию сингулярных решений £(х, у) этого же уравнения с координатами сингулярностей у (координатами источников) за пределами области решения. Таким образом, применение метода фундаментальных решений предполагает, что фундаментальные решения рассматриваемого уравнения известны в явном аналитическом виде. Хотя это обстоятельство сужает сферу применения, тем не менее, в последние десятилетия этот метод нашел обширные приложения в инженерных расчетах. При использовании даного метода исследователи столкнулись со следующими особенностями: (1) полученные системы уравнений являются плохо обусловленными, (2) в случае сложных невыпуклых областей его применение приводит к решению прямоугольных систем большой

размерности. Метод фундаментальных решений был впервые предложен В. Д. Купрадзе и М. А. Алексидзе в работах [54], [55] как метод обобщенных рядов Фурье. Сходимость была изучена в работе [56]. Более общий подход, основанный на аппроксимации граничного условия линейной комбинацией полного набора функций, использовался в методе Треффца [57], [58], [59]. Применение сингулярного разложения матриц в методе фундаментальных решений описано в работах [60], [61], [62]. В диссертации предложен новый стохастический граничный алгоритм решения многомерных краевых задач на основе рандомизированных вариантов метода фундаментальных решений, при этом координаты источников выбираются случайно распределенными, и задача сводится к решению большой прямоугольной системы с помощью рандомизированного сингулярного разложения матриц.

Перейдем к изложению содержания диссертации по главам.

Первая глава диссертации посвящена применению алгоритмов аппроксимации исходной матрицы последовательностью разреженных матриц к решению систем линейных алгебраических уравнений. В разделе (1.1) приводится стандартная схема рандомизации с помощью случайных разреженных матриц и оценки несмещенности. В (1.2) кратко описываются итерационные методы, к которым будет применен данный алгоритм: (1) метод, основанный на смещении спектра, (2) нестационарный итерационный процесс со случайными параметрами, (3) метод Гаусса-Зейделя. В этой главе также предложен новый алгоритм двойной рандомизации для метода Гаусса-Зейделя. В разделе (1.3) на примере решения двумерной задачи Дирихле для уравнения Лапласа сравниваются стандартный алгоритм случайного блуждания по границе и разработанная дискретная версия метода случайного блуждания по границе. Раздел (1.4) содержит численные результаты применения метода аппроксимации матрицы последовательностью разреженных матриц к разным итерационным методам, поведение дискретного алгоритма случайного блуждания по границе для различных областей и влияние выбора строк на сходимость методов. Результаты главы опубликованы в работе [25].

Вторая глава посвящена рандомизированному сингулярному разложению и его применению к моделированию случайных процессов и полей. Первые два раздела (2.1) и (2.2) являются вводными и содержат хорошо известную в литературе информацию. В разделе (2.1) дается общая теория сингулярного разложения матрицы и приводится формулировка теоремы Экарта-Янга. В следующем разделе (2.2) приводятся два алгоритма рандомизированного сингулярного разложения: метод разреженного сингулярного разложения матриц и рандомизированный метод главных компонент, также приводятся оценки погрешности и трудоемкости обоих методов. Моделирование случайных процессов и полей рассмотрено в разделе (2.3). При моделировании случайных полей использовалась следующая схема: рассматривались случайные процессы и поля с заданной корреляционной матрицей, с помощью алгоритма рандомизированного сингулярного разложения находились собственные числа и вектора корреляционного оператора. Далее, используя разложение Кархунена-Лоэва из раздела (2.3.1) (в разделе (2.3.2) приведен его дискретный аналог), полу-

чали аппроксимацию случайного поля. В качестве тестовых задач в разделе (2.3.3) были рассмотрены случайное поле Лоренца и фрактальный Винеровский процесс.

Метод рандомизированного сингулярного разложения был применен и при решении систем линейных алгебраических уравнений в разделе (2.4). Идея алгоритма, представленного в данном разделе, следующая. Решать систему линейных алгебраических уравнений с матрицей системы, которая имеет спектральный радиус больше или равный единице методом простой итерации нельзя. Но можно воспользоваться разложением матрицы по сингулярным векторам, то есть

í=l

где г-ранг системы, а, > а2 > ... > о,, сингулярные значения, и и^ е М'п, г/') £ ]1{а, г = 1 ,...,г левые и правые сингулярные вектора соответственно. Аппроксимируя первых 5, в <С г сингулярных числа и левых/правых сингулярных вектора, перейти к

новой системе с матрицей 5 = А — ^ 0{ Преобразованная система уравнений

»=1

с матрицей системы 5 уже будет пригодна для применения метода простой итерации. Результаты главы опубликованы в работе [63].

Третья глава посвящена методу фундаменталь�