Применение предобуславливателей для численного решения интегральных уравнений итерационными методами тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Федотов, Илья Евгеньевич

• Федотов, Илья Евгеньевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Федотов, Илья Евгеньевич

Оглавление

Введение 4 О численном решении интегральных уравнений многомерных задач математического моделирования и возникающих при этом проблемах

Краткий обзор существующих публикаций

Содержание и результаты работы

Глава 1. Обзор существующих методов и постановка задачи

Системы линейных алгебраических уравнений

Численные методы решения СЛАУ

Метод минимальных невязок

Многошаговый метод минимальных невязок

Использование предобуславливателей

Экономия вычислительных ресурсов в итерациях

Решение интегральных уравнений

Рассматриваемые интегральные уравнения

Уравнения с вырожденным ядром и резольвента

Дискретизация методом Галеркина

Метод коллокации для кусочно-постоянной аппроксимации

Постановка задачи

Глава 2. Изложение предлагаемых методов

Разреженный предобуславливатель для одномерных интегральных уравнений

Кусочно-постоянный предобуславливатель

Предобуславливатель для уравнения в пространстве непрерывных функций

Предобуславливатель в пространстве функций, непрерывных с производной

Предобуславливатель для уравнений с периодическими функциями

Обобщение разреженного предобуславливателя на многомерные задачи

Структура предобуславливателя в многомерном случае

Предобуславливатель в пространстве многомерных непрерывных функций

Многомерный предобуславливатель для периодических функций

Предобуславливатель для систем интегральных уравнений

Плотный предобуславливатель для интегральных уравнений

Предобуславливатель на основе резольвенты

Плотный предобуславливатель с непрерывной резольвентой

Плотный предобуславливатель для систем интегральных уравнений

Формирование плотного предобуславливателя с внешним параметром

Сокращение количества операций при умножении на вектор 82 Некоторые вопросы сходимости рассматриваемых итерационных методов при решении интегральных уравнений

Обоснование возможности подбора предобуславливателя

Обход отсутствия сходимости метода минимальных невязок

Глава 3. Программная реализация и численные эксперименты

Платформа для проведения экспериментов

Реализованное программное обеспечение

Примеры интегральных уравнений с плохой сходимостью

Численные эксперименты

Формирование прототипа матрицы СЛАУ

Сходимость для одномерного интегрального уравнения

Сходимость для одномерного уравнения с периодическими функциями

Сходимость для двумерного интегрального уравнения

Соответствие сходимости для сеток разных размерностей

Эффективность модификации ММН и МММН

Выводы

Глава 4. Применение к задачам математического моделирования

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

Теоретическое описание математической модели

Аналитическая подготовка к вычислениям

Численное решение и результаты

Расчет звукового излучения в пространстве

Описание задачи математического моделирования

Результаты численного решения

Введение диссертации (часть автореферата) на тему «Применение предобуславливателей для численного решения интегральных уравнений итерационными методами»

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

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

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

К примеру, в теории упругости для некоторого тела П + Г (Г -граница области £1), находящегося в состоянии равновесия, соотношение между напряжениями и перемещениями на поверхности тела, а также объемными силами, описывается граничным интегральным уравнением относительно неизвестных значений векторов перемещений и(р) и напряжений ¿(р) на границе области Г: с(рЫр) = ¡и{р,дЦд)с1Г{д)+ ¡Т{р,д)и{д)с1Г(д)+ \и{Р>д)Ь{д)с!П{д), реГ. г г п

Здесь и(р,д) и Т(р,д) - тензоры фундаментальных сингулярных решений для соответственно перемещений и напряжений в точке р, вызванных действием в точке д единичной сосредоточенной силы или единичного перемещения соответственно; с(р) зависит от гладкости Г в окрестности точки р; Ь(р) - вектор объемных сил. По заданным на части границы кинематическим условиям и(р) = и* (р), р еГ, и на другой части -силовым условиям ¿(р) = ^(р),реГ-Г15 на основании этого соотношения значения и(р) и ¿(р) могут быть определены для всей границы Г, после чего могут быть найдены значения перемещений в области .

Из других областей применения интегральных уравнений можно привести одну из основных задач математического моделирования в акустике - задача расчета звукового излучения в пространстве. Для некоторого вибрирующего гладкого тела, заданного границей Г, при зависимости от времени в виде множителя еш звуковое давление р(х), создаваемое на границе тела, удовлетворяет следующему граничному интегральному уравнению Гельмгольца [105]:

Здесь 0(х,у) - функция Грина для уравнения Гельмгольца. При заданных в результате измерений на границе тела Г значениях акустической скорости, может быть вычислено звуковое давление р(х) на Г, исходя из которого, может быть рассчитано распространение звука в пространстве.

Еще одной практически важной сегодня задачей является построение и численная реализация математических моделей рассеяния электромагнитных волн в объектах различной формы. Задача электромагнитного рассеяния имеет различные практические приложения в радиолокации, радиосвязи, радиоастрономии, технике СВЧ, физике плазмы и т.д. На основе фундаментальной математической модели электромагнитного поля Максвелла строятся интегральные уравнения электродинамики, описывающие рассеяние и поглощение электромагнитного излучения на неоднородных диэлектриках. Рассеяние волн на трехмерной неоднородной анизотропной структуре <2 в среде с всюду постоянным значением магнитной проницаемости //0 и тензор-функцией диэлектрической л проницаемости ё, отличной от постоянного тензора £а1 только в области (), описывается объемным интегральным уравнением второго рода следующего вида [72]: = Ё°+ — к\(е-£01)Ё]

Уравнение модели описывает компоненты векторного поля Е, возбуждаемого внешним полем Е° в области (). Конкретный вид Л интегрального оператора Я приводится в четвертой главе настоящей работы. Повышение эффективности решения такого рода уравнений позволит исследовать взаимодействие электромагнитного излучения мобильной и беспроводной связи с биологическими органами и тканями.

Многие задачи численного моделирования физических процессов и явлений, включая решение интегральных уравнений, могут быть решены приближенно путем сведения к системе линейных алгебраических уравнений (СЛАУ) с последующим ее численным решением. Проблема заключается в том, что для получения высокой точности описания поведения искомой функции полученным вектором, как правило, необходимо решение СЛАУ большой размерности, что требует значительных вычислительных ресурсов. Этот момент становится критическим, когда речь идет о многомерных интегральных уравнениях. Поэтому важны наличие и проработка методов, которые в частных случаях позволяют упростить решение СЛАУ большой размерности. В нашем случае имеются в виду СЛАУ, полученные в результате дискретизации многомерного интегрального уравнения с оператором, действующим в пространстве квадратично интегрируемых функций. К примеру, это может быть интегральное уравнение второго рода с гладким или с полярным ядром.

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

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

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

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

Краткий обзор существующих публикаций

На сегодняшний момент существует множество работ по созданию предобуславливателей. Многие из них описывают методы, известные очень давно, например, предобуславливатель Якоби и блочный предобуславливатель Якоби [97, 108], ориентированные на матрицы с диагональным преобладанием. Эти методы легко поддаются распараллеливанию, но не всегда являются достаточно эффективными. Также сюда можно отнести методы, основанные на последовательной релаксации - SOR (Successive Over Relaxation) и SSOR (Symmetric Successive Over Relaxation) [97, 108], которые являются развитием и усовершенствованием алгоритма решения СЛАУ методом Гаусса-Зейделя [79].

К широко используемым сегодня можно отнести также методы, ориентированные на разреженные матрицы и основанные на неполном разложении на треугольные составляющие, такие как метод неполного LU-разложения (ILU) и метод неполного разложения Холецкого (1С) [14, 42, 43]. При всей своей эффективности и популярности эти методы сегодня теряют свою перспективность из-за сложности распараллеливания вычислительного процесса, необходимость которого зачастую приобретает все большую актуальность.

Вследствие возрастающих возможностей распределенных вычислений появляются легко поддающиеся распараллеливанию универсальные методы, позволяющие строить предобуславливатели для любых СЛАУ. Одним из наиболее известных в этой области является метод SPAI (SParse Approximate Inverse) [101]. Он основан на минимизации нормы Фробениуса разницы предобусловленной матрицы и единичной при заданной маске разреженности предобуславливателя. Также к данной категории предобуславливателей, основанных на разреженной аппроксимации обратной матрицы, следует отнести метод FSAI (Factorized Sparse Approximate Inverse) [102], а также метод AISM, основанный на разложении матрицы с помощью формулы Шермана-Моррисона (Sherman-Morrison formula). Последний также имеет блочную модификацию, основанную на формуле Шермана-Моррисона-Вудбери (Sherman-Morrison-Woodbury formula) [96, 100]. Такие методы хороши в использовании при наличии широких возможностей распараллеленных вычислений, в обычных же условиях им, как правило, не хватает ресурсов для формирования качественного предобуславливателя.

Наконец, существует немало предобуславливателей, ориентированных на приближенное решение функциональных уравнений. К примеру, предобуславливатели для решения уравнений с лапласианом, т.е. дифференциальных уравнений с частными производными второго порядка [13], или предобуславливатели для решения задач с седловым оператором [30, 90]. Также есть предобуславливатели для решения интегральных уравнений заданного вида, к примеру, для решения конкретных задач математической физики. Среди них можно указать предобуславливатели для решения интегральных уравнений электрического (Electric Field Integral Equation, EFIE) и магнитного (Magnetic Field Integral Equation, MFIE) полей [94, 99, 104].

Достаточно давно существуют численные методы решения функциональных уравнений, использующих идею введения двух или более сеток дискретизации. Одним из наиболее известных и эффективных на сегодняшний день является многосеточный (Multigrid) метод решения эллиптических дифференциальных уравнений [97, 106], основой которого является известная информация о спектре и собственных функциях эллиптических операторов. Зависимость требуемых вычислительных ресурсов от размерности дискретизации практически линейная, однако сходимость метода напрямую зависит от свойств эллиптических операторов, что не дает возможности использовать его для произвольных функциональных уравнений. Идея нескольких сеток дискретизации, используемая в настоящей работе, сама по себе не нова и широко используется в разностных схемах, однако этого нельзя сказать применительно к интегральным уравнениям.

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

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

Содержание и результаты работы

В первой главе настоящей работы приводятся основные существующие подходы в обозначенной предметной области, которые используются как основа для изложения предлагаемых методов в последующих главах. Приводятся основные сведения о СЛАУ и описываются некоторые существующие методы их численного решения. Рассматриваются некоторые существующие способы сокращения затрачиваемых вычислительных ресурсов, в том числе использование предобуславливателей.

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

М' х)- у)и(у)с{у = /(.X), X 6 <2

В.1) о

Именно такие интегральные уравнения образуются при решении многих корректно поставленных задач математического моделирования и могут быть решены численно путем решения СЛАУ большой размерности. Уравнение (В.1) рассматривается в пространствах квадратично интегрируемых, непрерывных, непрерывных с производной и гладких периодических функций. Рассматриваются многомерные интегральные уравнения и системы интегральных уравнений, поскольку именно такие уравнения представляют основной интерес.

При численном решении уравнения (В.1) путем дискретизации получают СЛАУ с неизвестным вектором й:

Исходя из значений полученного при решении этой СЛАУ вектора, приблизительно могут быть вычислены значения неизвестной функции и{х) уравнения (В.1). Чтобы полученное в результате приближенное решение было в достаточной степени точным, СЛАУ (В.2), как правило, должна иметь достаточно большую размерность. Требуемое количество вычислительных ресурсов при решении такой СЛАУ итерационными методами в общем случае зависит от ее размерности квадратично. Это создает весьма ощутимые сложности, особенно при решении многомерных интегральных уравнений, поэтому при решении итерационными методами стараются использовать все доступные средства по увеличению скорости сходимости. Для этого используются различные методы предобуславливания СЛАУ, т.е. выполнения решения эквивалентной системы, к примеру, следующего вида:

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

Аи = и-Ки = /.

В.2)

РАй = Р/.

В.З)

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

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

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

Четвертая глава посвящена решению с использованием описанных методов многомерных задач математического моделирования.

Решается задача рассеяния электромагнитных волн на трехмерном теле. Производится расчет векторного электрического поля, возбуждаемого внешним полем в однородной изотропной пластине, на основе приведенной в [72] математической модели. При этом численно решается система трехмерных интегральных уравнений с сингулярным ядром.

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

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

В качестве основных результатов работы можно отметить следующее:

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

2. Обоснована возможность выбора оптимального предобуславливателя при решении рассматриваемых СЛАУ итерационными методами путем решения СЛАУ меньшей размерности.

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Федотов, Илья Евгеньевич

Заключение

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

Несмотря на наличие достаточно мощных вычислительных комплексов, вопрос повышения сходимости все еще остается актуальным, поскольку предположение о достаточности существующих средств для быстрого решения сегодняшних задач является весьма условным. Зачастую интегральные уравнения, особенно многомерные, решаются с достаточно низкой точностью аппроксимации. К тому же ограничения вычислительной техники нередко вынуждают пренебрегать многими параметрами и упрощать математическую модель. При рассмотрении обратных задач, т.е. таких, в которых необходимо определить свойства или конфигурацию объекта по известным данным о его поведении, зачастую требуется решать прямые задачи многократно, что также требует существенных временных затрат. В качестве другого примера, когда требуется решать прямые задачи многократно, можно привести рассмотренные в четвертой главе математические модели для случаев, когда зависимость от времени имеет более одной частотной составляющей. В этом случае функция временной зависимости раскладывается в ряд Фурье, после чего производится решение задачи для каждой частотной составляющей отдельно. В практических приложениях количество частотных составляющих, например, для случая звукового излучения, бывает порядка сотен и тысяч. Также стоит отметить, что при рассмотрении таких задач в случае коротких длин волн для обеспечения приемлемой точности необходимы очень высокие размерности дискретизации, что снова увеличивает время решения. Учитывая все эти обстоятельства, можно утверждать, что предлагаемые методы сокращения требуемого для решения количества итераций оказываются весьма актуальными при решении широкого круга многомерных задач.

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

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

Также экспериментально подтвердилась эффективность предложенной модификации итерационных ММН и МММН, направленной на то, чтобы избежать отсутствия сходимости. Отсутствие сходимости этих методов может наблюдаться для некоторых СЛАУ изначально, а в некоторых случаях может появиться при использовании предобуславливателей. Предложенный способ модификации устраняет такой риск при правильном выборе соответствующего параметра, который также может быть выбран экспериментально путем моделирования сходимости.

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Федотов, Илья Евгеньевич, 2006 год

1. Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Высш. шк., 1994. - 544 с.

2. Антоневич А.Б. Линейные функциональные уравнения. Операторный подход. Минск: Университетское, 1988.-232 с.

3. Антоневич А.Б., Радыно Я.В. Функциональный анализ и интегральные уравнения. Минск: Университетское, 1984. - 352 с.

4. Арсенин В.Я. Методы математической физики и специальные функции. 2-е изд. - М: Наука, 1984. - 383 с.

5. Бакушинский А.Б. Некоторые вопросы приближенного решения интегральных уравнений со "слабой" особенностью // Вычислительные методы и программирование: Сборник работ вычислительного центра Моск. ун-та. 1968. Т.10. - С. 9-15.

6. Бакушинский А.Б. Один метод численного решения интегральных уравнений // Вычислительные методы и программирование: Сборник работ вычислительного центра Моск. ун-та. 1965. Т.4. - С. 536-543.

7. Балакришнан A.B. Прикладной функциональный анализ. М.: Наука, 1980.-384 с.

8. Бахвалов Н.С. Численные методы. М.: Наука, 1973. - 632 с.

9. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.-600 с.

10. Ю.Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983.-335 с.

11. П.Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры. -М.: Наука, 1980.-336 с.

12. Белоцерковский С.М., Лифанов И.К. Численные методы в сингулярных интегральных уравнениях и их применение в аэродинамике, теории упругости, электродинамике. -М.: Наука, 1985. -256 с.

13. Блатов И.А., Китаева Е.В., Эксаревская М.Е. Об асимптотически иеулучшаемых оценках предобуславливателей дискретного лапласиана // Вестник ВГУ. 2000. № 1. - С. 81 -91.

14. Блатов И.А. Об оценках LU-разложений разреженных матриц и их приложениях к методам неполной факторизации // Журнал Выч. мат и мат. физ. 1997. Т.37, №3. - С. 259-276.

15. Боглаев Ю.П. Вычислительная математика и программирование. М.: Высш. шк., 1990.-544 с.

16. Брусин В.А. Матрицы и системы линейных уравнений // Соросовский Образовательный Журнал. 2000. Т.6, №1. - С. 108-112.

17. Брусин В.А. Матрицы как линейные операторы // Соросовский Образовательный Журнал. 2000. Т.6, №1. - С. 102-107.

18. Бугров Я.С., Никольский С.М. Элементы линейной алгебры и аналитической геометрии. М.: Наука, 1980. - 175 с.

19. Васильева А.Б., Тихонов H.A. Интегральные уравнения. М.: Физматлит, 2002. - 160 с.

20. Ватульян А.О. Измерение расстояний между функциями // Соросовский Образовательный Журнал. 2000. Т.6, №11. - С. 123-127.

21. Виленкин С.Я., Самохин А.Б. Итеративный метод повышения точности решения линейных операторных уравнений // Журнал Выч. мат и мат. физ. 1982. Т.22, №2. - С. 462-464.

22. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.-304 с.

23. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.-318 с.

24. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплицевыми матрицами. М.: Наука, 1987. - 320 с.

25. Волков Е.А. Численные методы. М.: Наука, 1987. - 248 с.

26. Воробьева Г.Н., Данилова А.Н. Практикум по численным методам. -М.: Высш. шк, 1979.- 184 с.

27. Вулих Б.З. Введение в функциональный анализ. М.: Наука, 1967. -416 с.

28. Гантмахер Ф.Р. Теория матриц. 4-е изд. - М.: Наука, 1988. - 552 с.

29. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.- 177 с.

30. Горелова М.В., Чижонков Е.В. К предобусловливанию седловых задач с помощью седловых операторов // Журнал Выч. мат и мат. физ. -2004. Т.44, №9. С. 1523-1533.

31. Данфорд Н., Шварц Дж. Линейные операторы: Спектральные операторы. М: Мир, 1974. - 664 с.

32. Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука, 1970.-664 с.

33. Демидович Б.П., Марон И.А., Шувалова Э.З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения. 3-е изд. - М.: Наука, 1967. - 368 с.

34. Джеффрис Г., Свирлс Б. Методы математической физики. Вып. 1. М.: Мир, 1969.-423 с.

35. Джеффрис Г., Свирлс Б. Методы математической физики. Вып. 2. М.: Мир, 1970.-352 с.

36. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. -М.: Мир, 1984. 334 с.

37. Дикусар В.В. Некоторые численные методы решения линейных алгебраических уравнений // Соросовский Образовательный Журнал. -1998. №9. -С. 111-120.

38. Икрамов Х.Д. Численные методы линейной алгебры. М.: Знание, 1987.-47 с.

39. Ильин В.А. Базисы в евклидовых пространствах и ряды Фурье // Соросовский Образовательный Журнал. 1998. №4. - С. 95-101.

40. Ильин В.А. Итерационные методы решения функциональных уравнений // Соросовский Образовательный Журнал. 2001. Т.7, №2. -С. 116-120.

41. Ильин В.А., Позняк Э.Г. Линейная алгебра. М.: Наука, 1984. - 294 с.

42. Ильин В.П. Методы неполной факторизации для решения алгебраических систем. -М.: Наука, 1995. 288 с.

43. Ильин В.П. О скорости сходимости неявных методов неполной факторизации // Журнал Выч. мат и мат. физ. 1993. Т.ЗЗ, №1. - С. 311.

44. Интегральные уравнения / П.П. Забрейко, А.И. Кошелев, М.А. Красносельский и др. М.: Наука, 1968. - 448 с.

45. Калиткин H.H. Численные методы. М.: Наука, 1978. - 512 с.

46. Канторович Л.В., Акилов Г.П. Функциональный анализ. 2-е изд. - М.: Наука, 1977.-744 с.

47. Коллатц Л. Функциональный анализ и вычислительная математика. -М.: Мир, 1969.-448 с.

48. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. 6-е изд. - М.: Наука, 1989. - 624 с.

49. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. М.: Наука, 1972. - 368 с.

50. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1984. - 831 с.

51. Краснов М.Л., Киселёв А.И., Макаренко Г.И. Интегральные уравнения -М.: Наука, 1968.- 192 с.

52. Красносельский М.А., Лифшиц Е.А., Соболев A.B. Позитивные линейные системы. М.: Наука, 1985. - 255 с.

53. Крылов В.И., Бобков В.В., Монастырный П.Н. Вычислительные методы. Т.1. -М.: Наука, 1976.-302 с.

54. Курант Р., Гильберт Д. Методы математической физики. Т.1. 3-е изд. - M.-JL: Гостехиздат, 1951. - 476 с.

55. Лизоркин П.И. Курс дифференциальных и интегральных уравнений с дополнительными главами анализа. М.: Наука, 1981. - 384 с.

56. Ловитт У.В. Линейные интегральные уравнения. М.: Гостехиздат, 1957.-266 с.

57. Люстерник Л.А., Соболев В.И. Краткий курс функционального анализа. М: Высш. шк., 1982. - 272 с.

58. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. -2-е изд. -М.: Наука, 1965. 520 с.

59. Максимов В.П. Арифметика рациональных чисел и компьютерное исследование интегральных уравнений // Соросовский Образовательный Журнал. 1999. №3. - С. 121-126.

60. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1989. -608 с.

61. Михлин С.Г. Лекции по линейным интегральным уравнениям. М.: Физматгиз, 1959.-232 с.

62. Мюнтц Г. Интегральные уравнения. Т.1. М.: Гостехтеориздат, 1934. -330 с.бЗ.Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М.: Наука, 1986. - 288 с.

63. Петровский И.Г. Лекции по теории интегральных уравнений. 3-е изд. -М.: Наука, 1965.- 128 с.

64. Полянин А. Д., Манжиров A.B. Справочник по интегральным уравнениям. -М.: Физматлит, 2003. 608 с.

65. Приближенное решение операторных уравнений / М.А. Красносельский, Г.М. Вайникко, П.П. Забрейко и др. М.: Наука, 1969. -456 с.

66. Рабинер JL, Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978. - 848 с.

67. Райс Дж. Матричные вычисления и математическое обеспечение. М.: Мир, 1984.-264 с.

68. Рисс Ф., Секефальви-Надь Б. Лекции по функциональному анализу. -2-е изд. М.: Мир, 1979. - 587 с.

69. Самарский A.A. Введение в численные методы. М.: Наука, 1982. -272 с.

70. Самарский A.A., Тулин A.B. Численные методы. М.: Наука, 1989. -432 с.

71. Самохин А.Б. Интегральные уравнения и итерационные методы в электромагнитном рассеянии. М.: Радио и связь, 1998. - 160 с.

72. Самохин А.Б. Метод коллокации для интегральных уравнений с диссипативным оператором // Дифференциальные уравнения. 1995. Т.31, №9. - С. 1588-1590.

73. Самохин А.Б. Метод простой итерации для решения линейных операторных уравнений // Журнал Выч. мат и мат. физ. 1988. Т.28, №10.-С. 1573-1583.

74. Самохин А.Б. Многошаговый метод минимальных невязок для решения линейных уравнений // Журнал Выч. мат и мат. физ. 1991. Т.31,№2.-С. 317-320.

75. Самохин А.Б. Модифицированный метод последовательных приближений // Журнал Выч. мат и мат. физ. 1973. Т.13, №6. - С. 1402-1408.

76. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. -М.: Наука, 1984. 190 с.

77. Тьюарсон Р. Разреженные матрицы. -М.: Мир, 1977. 189 с.

78. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. 3-е изд. - СПб.: Лань, 2002. - 736 с.

79. Федотов И.Е. О проблеме отсутствия сходимости метода минимальных невязок и вариантах ее решения //55 Научно-техническая конференция МИРЭА. Сборник трудов. 4.2. Физико-математические науки. М., 2006.-С. 87-91.

80. Федотов И.Е. Об ортогонализации составляющих матрицу векторов // Теоретические вопросы вычислительной техники, программного обеспечения и информационных технологий: межвузовский сборник научных трудов. -М.: МИРЭА, 2005. С. 91-101.

81. Федотов И.Е. Предобуславливатели для численного решения линейных интегральных уравнений // 54 Научно-техническая конференция МИРЭА. Сборник трудов. 4.2. Физико-математические науки. М., 2005.-С. 26-31.

82. Флетчер К. Численные методы на основе метода Галеркина. М.: Мир, 1988.-352 с.

83. Форсайт Дж., Мальком М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. - 279 с.

84. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969. - 168 с.

85. Хейгеман JL, Янг Д. Прикладные итерационные методы. М.: Мир, 1986.-448 с.

86. Хемминг Р.В. Численные методы для научных работников и инженеров. 2-е изд. - М.: Наука, 1972. - 400 с.

87. Чижонков Е.В. Обобщенный релаксационный метод для линейных задач с седловым оператором // Журнал Мат. Мод. 2001. Т. 13, №12. -С. 107.

88. Шуп Т. Решение инженерных задач на ЭВМ. М.: Мир, 1982. - 238 с.

89. Эдварде Р. Функциональный анализ: Теория и приложения. М.: Мир, 1969.- 1071 с.

90. Ainsworth М. A preconditioning based on Domain Decomposition for h-p Finite Element Approximation on Quasi-uniform meshes // SIAM J. Numer. Anal. 1996. Vol.33, №4. - P. 1358-1376.

91. Bartels R., Kaufman L. Cholesky factor updating techniques for rank 2 matrix modifications // SIAM J. Matrix Anal. Appl. 1989. Vol.10. - P. 557-592.

92. Baryamureeba V., Steihaug T. Computational Issues for a New Class of Preconditioners // Proceedings of the Second Workshop on "Large-Scale Scientific Computations" (Sozopol, Bulgaria, June 2-6, 1999). Sozopol: Vieweg, 1999.-P.128-135.

93. Bebendorf M. Approximation of Boundary Element Matrices // Numerische Mathematik. 2000. Vol.86, №4. - P. 565-589.

94. Demmel J.W. Applied Numerical Linear Algebra. Philadelphia: SIAM, 1997. -419 p.

95. Deng H., Ling H. An efficient wavelet preconditioner for iterative solution of three-dimensional electromagnetic integral equations // IEEE Trans. Antennas and Propagat. 2003. Vol.51, №3. - P. 654-660.

96. Golub G.H., Van Loan C.H. Matrix computations. 3-rd edn. -Baltimore: The Johns Hopkins University Press, 1996. - 664 p.

97. Grote M.J., Huckle T. Parallel Preconditioning with Sparse Approximate Inverses // SIAM J. of Scient. Comput. 1997. Vol.18, №3. -P. 838-853.

98. Kolotilina L.Yu., Yeremin A.Yu. Factorized sparse approximate inverse preconditioning I. Theory // SIAM J. Matrix Anal. Appl. 1993. Vol.14.-P. 45-58.

99. Kolotilina L.Yu., Yeremin A.Yu. On a family of two-level preconditionings of the incomplete block factorization type // Sov. J. Numer. Anal. Math. Modelling. 1986. Vol.1, №4. - P. 293-320.

100. Lee Jin-Fa, Lee R., Burkholder R.J. Loop star basis functions and a robust preconditioner for EFIE scattering problems // IEEE Trans. Antennas and Propagat. -2003. Vol.51, №8. P. 1855-1863.

101. Mechel F.P. Formulas of Acoustics. Berlin: Springer-Verlag, 2002. -1175 p.

102. Numerical recipes in C: The Art of Scientific Computing / W.H. Press, S.A. Teukolsky, W.T. Vetterling, etc. 2-nd edn. - Cambridge: Cambridge University Press, 1992. - 994 p.

103. Rjasanow S., Bebendorf M. Numerical Simulation of Exhaust Systems in Car Industry Efficient Calculation of Radiation Heat Transfer // Mathematics - Key Technology for the Future, Springer. - 2003. - P. 55-62.

104. Saad Y. Iterative Methods for Sparse Linear Systems. Boston: PWS Pub. Co., 1996.-448 p.

105. Saad Y., Schultz M.N. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM J. Sei. Stat. Comput. 1986. - Vol.7, №3. - P. 856-869.

106. Tyrtyshnikov E.E. Incomplete cross approximation in the mosaic-skeleton method // Computing. 2000. Vol.64, №4. - P. 367-380.

107. Van der Vorst H.A. High performance preconditioning // SIAM Sei. Stat. Comput. 1989. Vol.10-P. 1174-1185.

108. Zilli G. Iterative methods for solving sparse linear systems with a parallel preconditioner // Int. J. of Comput. Math. 1992. Vol.44. - P. 111119.