Введение к работе
Актуальность темы.
Актуальность темы диссертационной работы обусловлена необходимостью эффективного (в реальном времени и с высокой точностью) численного решения систем линейных алгебраических уравнений (СЛАУ) большой размерности Численное решение СЛАУ - одна из наиболее часто встречающихся задач в научно-технических исследованиях Такая задача возникает в математической физике (численное решение дифференциальных и интегральных уравнений), экономике, статистике При этом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000 К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру Существующие библиотеки программ на языках высокого уровня (Фортран и др.), разработаны на основе, так называемых, прямых методов решения СЛАУ, типа метода Гаусса и его модификаций Число арифметических операций умножения для численного решения СЛАУ размерностью N с помощью прямого метода ~ N* Кубическая зависимость числа арифметичеких операций от размера матрицы СЛАУ приводит при N > 1000 к нереально большому времени решения даже на самых современных ПЭВМ Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае N > 1000 по причине недостаточности объема оперативной памяти для хранения данных задачи
Итерационные методы решения СЛАУ намного экономнее, как по машинному времени решения, так и по использованию оперативной памяти Так, если итерационный метод является быстро сходящимся с числом итераций m«N, то время решения, пропорциональное уже квадрату размера матрицы ~ т N2, оказывается существенно меньше, примерно в N 1т раз для вещественной и IN 1т раз для комплексной СЛАУ Кроме того, требуется хранить в оперативной памяти, как правило, только одну матрицу, например, матрицу перехода явного итерационного метода При использовании быстро сходящихся итерационных методов вполне решаемыми в реальном времени на современных ПЭВМ оказываются СЛАУ с комплексной матрицей размерностью N»1000
В настоящее время отсутствуют библиотеки подпрограмм широкого назначения для численного решения больших и сверхбольших СЛАУ Таким образом, разработка эффективных итерационных алгоритмов для широкого класса матриц СЛАУ большой размерности и библиотек подпрограмм на их основе является актуальной задачей
Наиболее алгоритмически простыми среди итерационных методов являются стационарные итерационные методы, такие как оптимальный метод простой итерации и метод релаксации В то же время показано, что можно добиться их эффективной сходимости для достаточно широкого класса вещественных и комплексных матриц СЛАУ Для нестационарных итерационных мегодов, таких как метод с чебышевским набором параметров, минимальных невязок, сопряженных градиентов, сходимость доказана в узком классе матриц, например, таких как вещественные симметричные положительно определенные матрицы И в этом узком классе матриц сходимость опгимальных стационарных методов, опирающихся на известные спектральные матричные свойства, оказывается в некоторых случаях даже лучшей При этом число арифметических операций стационарного алгоритма минимально Еще одним преимуществом оптимального метода простой итерации является возможность естественного распараллеливания алгоритма при постановке его на современные параллельные ЭВМ, так как алгоритм по существу сводится к одному умножению матрицы на вектор Все эти аргументы указывают на выбор стационарных итерационных методов в качестве алгоритмической основы для библиотеки подпрограмм по решению СЛАУ с большими матрицами
Цель работы.
Целью работы является разработка эффективных стационарных итерационных алгоритмов для некоторых широких классов матриц СЛАУ и библиотеки подпрограмм на языке Visual Fortran на их основе, решающих задачу эффективного численного решения СЛАУ большой размерности, а также численные исследования на основе разработанной библиотеки конкретных 2D и 3D задач электродинамики и электростатики В соответствии с целью работы поставлены следующие научные задачи
Разработка алгоритмов определения оптимального параметра модифицированного метода простой итерации в случаях достаточно произвольной конфигурации комплексного спектра матрицы перехода, таких как комплексный отрезок, круг, треугольник, многоугольник
Разработка эффективных явных стационарных алгоритмов и подпрограмм, основанных на методе оптимальной простой итерации для таких типов матриц, как матрицы (вещественные и комплексные эрмитовые) с вещественным положительным спектром, а также комплексные симметричные неэрмитовые матрицы с комплексным спектром, возникающие в результате дискретизации интегральных операторов в задачах рассеяния электромагнитных волн на локально неоднородных прозрачных телах
Разработка эффективных неявных стационарных алгоритмов и подпрограмм, основанных на методе релаксации с параметром и методе оптимальной релаксации для таких типов матриц, как трехдиагональные несиммет-
ричные теплицевы матрицы, симметричные положительно определенные матрицы, а также блочно трехдиагональные, возникающие при дискретизации краевых задач для дифференциальных уравнений в частных производных с помощью разностных схем
Разработка структуры и программных модулей библиотеки подпрограмм на языке Visual Fortran на основе стационарных итерационных методов для решения СЛАУ большой размерности с широкими классами матриц
Демонстрация возможностей библиотеки и определение границ ее применимости Численные решения с помощью разработанной библиотеки СЛАУ большой размерности, возникающей в 2D и 3D задачах рассеяния электромагнитных волн на локальных прозрачных неоднородностях и в двумерных краевых задачах для уравнения Пуассона с источниками
Научная новизна.
Все поставленные и перечисленные научные задачи решены и облада
ют научной новизной
Основные положения и результаты, выносимые на защиту.
Библиотека программ на языке Visual Fortran на основе стационарных итерационных методов для решения СЛАУ большой размерности для некоторых широких классов матриц
Алгоритмы и подпрограммы определения оптимального параметра модифицированного метода простой итерации в случаях достаточно произвольной конфигурации комплексного спектра матрицы перехода, таких как комплексный отрезок, круг, треугольник и многоугольник
Алгоритмы и программы быстро сходящихся стационарных итерационных процессов, использующие априорную информацию о спектральных свойствах матрицы СЛАУ, в том числе
Эффективные явные стационарные алгоритмы и подпрограммы, основанные на методе оптимальной простой итерации для решения СЛАУ с такими типами матриц, как матрицы с положительным спектром, а также комплексные симметричные неэрмитовые матрицы с комплексным спектром, возникающие в результате дискретизации интегральных операторов в задачах рассеяния электромагнитных волн на локально неоднородных прозрачных телах
Эффективные неявные стационарные алгоритмы и подпрограммы, основанные на методе релаксации с параметром и методе оптимальной релаксации для решения СЛАУ с такими типами матриц, как трехдиагональные несимметричные теплицевы матрицы, симметричные положительно определенные матрицы и блочные трехдиагональные, возникающие при дискретизации краевых задач для дифференциальных уравнений в частных производных с помощью разностных схем
Численные результаты, полученные с помощью разработанной библиотеки по решению больших СЛАУ в 2D и 3D задачах рассеяния электромагнитных волн, а также в 2D краевой задаче для уравнения Пуассона
Теоретическая значимость работы.
Теоретическая значимость диссертационного исследования состоит в том, что
Определены классы матриц, объединенные общностью их спектральных свойств, для которых воможно построение быстро сходящихся стационарных итерационных алгоритмов
Созданы алгоритмы метода оптимальной простой итерации в следующих случаях конфигурации комплексного спектра матрицы перехода - отрезок, круг, треугольник, многоугольник
Созданы алгоритмы метода оптимальной релаксации для решения СЛАУ с следующими типами матриц трехдиагональная, в общем случае несимметричная теплицева матрица, а также положительно определенная симметричная блочная трехдиагональная матрица
Разработана функциональная блок-схема библиотеки подпрограмм для решения некоторых классов СЛАУ большой размерности стационарными итерационными методами
Методы исследования.
Исследования работы базируются на использовании аппарата численных методов, линейной алгебры, математической физики, а также методов модульного и объектно-ориентированного программирования
Практическая ценность работы.
Разработанная библиотека подпрограмм может быть использована для решения больших СЛАУ с размерностью матрицы больше и много больше 1000, возникающих в задачах математической физики, экономики, статистики Так, с помощью библиотеки моделировались двумерные и трехмерные задачи рассеяния электромагнитных волн на биологических органах и тканях Результаты исследований вошли в 2005г в работы по проекту «Разработка пакета прикладных программ и исследование задач взаимодействия электромагнитного излучения с трехмерными диэлектриками и биологическими объектами на основе объемных интегральных уравнений электродинамики» ведомственной научной программы «Развитие научного потенциала высшей школы» Степень обоснованности научных положений, рекомендаций и выводов.
Достоверность и обоснованность полученных результатов базируется на корректной постановке задачи по решению СЛАУ с помощью быстро сходящихся итерационных методов, использованием различных тестовых задач для верификации полученных численных результатов, сравнением их с известными решениями, полученными другими методами, а также сравнением
с решениями СЛАУ, полученными с помощью стандартных библиотек подпрограмм
Апробация работы.
Основные положения и результаты работы докладывались и обсуждались на
. Международной конференции «Информационно-вычислительные технологии в науке» (Москва 2007 г ),
. Научно-технических конференциях МИРЭА (Москва 2005 г, 2007 г), . Научном семинаре МИРЭА «Математические методы в прикладных исследованиях» (Москва, 2007 г)
Публикации.
По материалам диссертации опубликовано 15 работ, из них 2 публикации в ведущих рецензируемых научных изданиях, рекомендованных ВАК, 4 свидетельства об отраслевой регистрации разработки в Отраслевом фонде алгоритмов и программ, 4 публикации в Телеграфе отраслевого фонда, 3 статьи в научных вестниках ВУЗов и Межвузовском сборнике трудов, 2 статьи в сборниках трудов конференции
Личный вклад соискателя.
В работах соискателя в качестве соавтора выступает научный консультант Куликов С П , в одной работе - научный руководитель Самохин А Б , которым принадлежит постановка задач, разработка совместно с соискателем направлений и математических методов исследований, а также формулирование полученных результатов Соискателем создана структура библиотеки подпрограмм, разработаны итерационные алгоритмы и компьютерные программы, получены основные результаты, подготовлены тексты статей, сформулированы выводы Также автором получены численные результаты для СЛАУ с матрицами большой размерности, исследованы границы применения библиотеки подпрограмм Соискателем единолично подготовлена диссертация, сформулированы положения, выносимые на защиту и выводы Таким образом, личный вклад соискателя в диссертационную работу и получение научных результатов, которые выносятся на защиту, является определяющим
Объём работы.
Диссертация состоит из введения, четырех глав, выводов Содержание диссертации изложено на 140 страницах, включая 30 рисунков, 3 таблицы и списка цитируемой литературы из 46 наименований
