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

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

003166013

АБДЕЛЬ МАЛИК Джихан

РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ БИБЛИОТЕКИ ПРОГРАММ ДЛЯ РЕШЕНИЯ ИТЕРАЦИОННЫМИ МЕТОДАМИ НЕКОТОРЫХ КЛАССОВ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ БОЛЬШОЙ РАЗМЕРНОСТИ

Специальность 05 13.18 - Математическое моделирование, численные методы и комплексы программ

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

2 7 2008

Москва 2008

003166013

Работа выполнена на кафедре «Прикладная математика» Московского государственного института радиотехники, электроники и автоматики (Технического Университета)

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

Научный консультант

Официальные оппоненты

Ведущая организация

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

заслуженный деятель науки Самохин Александр Борисович кандидат физико-математических наук, доцент

Куликов Сергей Павлович доктор технических наук, профессор Ткаченко Владимир Максимович, кандидат физико-математических наук, доцент

Растягаев Дмитрий Владимирович

Институт электронных управляющих машин (ИНЭУМ)

сио

Защита состоится й^иш^/ 2008 года в /3 на заседании диссертационного совета Д212 131 03 Московского государственного института радиотехники, электроники и автоматики (Технического Университета) по адресу 119454, г Москва, пр-т Вернадского д 78

С диссертацией можно ознакомиться в библиотеке Московского государственного института радиотехники, электроники и автоматики (Технического Университета)

Автореферат разослан Р£ 2008г

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

Диссертационного совета Д 212 131 03 к т н , доцент

Т:

ягунов О А.

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

Актуальность темы.

Актуальность темы диссертационной работы обусловлена необходимостью эффективного (в реальном времени и с высокой точностью) численного решения систем линейных алгебраических уравнений (СЛАУ) большой размерности Численное решение СЛАУ - одна из наиболее часто встречающихся задач в научно-технических исследованиях Такая задача возникает в математической физике (численное решение дифференциальных и интегральных уравнений), экономике, статистике При этом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000 К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру Существующие библиотеки программ на языках высокого уровня (Фортран и др.), разработаны на основе, так называемых, прямых методов решения СЛАУ, типа метода Гаусса и его модификаций Число арифметических операций умножения для численного решения СЛАУ размерностью N с помощью прямого метода ~ ,V' Кубическая зависимость числа арифметичеких операций от размера матрицы СЛАУ приводит при N >1000 к нереально большому времени решения даже на самых современных ПЭВМ Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае N > 1000 по причине недостаточности объема оперативной памяти для хранения данных задачи

Итерационные методы решения СЛАУ намного экономнее, как по машинному времени решения, так и по использованию оперативной памяти Так, если итерационный метод является быстро сходящимся с числом итераций m« N, то время решения, пропорциональное уже квадрату размера матрицы ~ т N2, оказывается существенно меньше, примерно в Nim раз для вещественной и 2Nim раз для комплексной СЛАУ Кроме того, требуется хранить в оперативной памяти, как правило, только одну матрицу, например, матрицу перехода явного итерационного метода При использовании быстро сходящихся итерационных методов вполне решаемыми в реальном времени на современных ПЭВМ оказываются СЛАУ с комплексной матрицей размерностью N»1000

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

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

Цель работы.

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

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

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

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

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

• Разработка структуры и программных модулей библиотеки подпрограмм на языке Visual Fortran на основе стационарных итерационных методов для решения СЛАУ большой размерности с широкими классами матриц

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

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

• Все поставленные и перечисленные научные задачи решены и обладают научной новизной

Основные положения и результаты, выносимые на защиту.

• Библиотека программ на языке Visual Fortran на основе стационарных итерационных методов для решения СЛАУ большой размерности для некоторых широких классов матриц

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

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

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

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

• Численные результаты, полученные с помощью разработанной библиотеки по решению больших СЛАУ в 20 и ЗБ задачах рассеяния электромагнитных волн, а также в 20 краевой задаче для уравнения Пуассона

Теоретическая значимость работы.

Теоретическая значимость диссертационного исследования состоит в том, что

• Определены классы матриц, объединенные общностью их спектральных свойств, для которых воможно построение быстро сходящихся стационарных итерационных алгоритмов

• Созданы алгоритмы метода оптимальной простой итерации в следующих случаях конфигурации комплексного спектра матрицы перехода - отрезок, круг, треугольник, многоугольник

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

• Разработана функциональная блок-схема библиотеки подпрограмм для решения некоторых классов СЛАУ большой размерности стационарными итерационными методами

Методы исследования.

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

Практическая ценность работы.

Разработанная библиотека подпрограмм может быть использована для решения больших СЛАУ с размерностью матрицы больше и много больше 1000, возникающих в задачах математической физики, экономики, статистики Так, с помощью библиотеки моделировались двумерные и трехмерные задачи рассеяния электромагнитных волн на биологических органах и тканях Результаты исследований вошли в 2005г в работы по проекту «Разработка пакета прикладных программ и исследование задач взаимодействия электромагнитного излучения с трехмерными диэлектриками и биологическими объектами на основе объемных интегральных уравнений электродинамики» ведомственной научной программы «Развитие научного потенциала высшей школы»

Степень обоснованности научных положений, рекомендаций и выводов.

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

с решениями СЛАУ, полученными с помощью стандартных библиотек подпрограмм

Апробация работы.

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

на

. Международной конференции «Информационно-вычислительные технологии в науке» (Москва 2007 г ),

. Научно-технических конференциях МИРЭА (Москва 2005 г, 2007 г), . Научном семинаре МИРЭА «Математические методы в прикладных исследованиях» (Москва, 2007 г)

Публикации.

По материалам диссертации опубликовано 15 работ, из них 2 публикации в ведущих рецензируемых научных изданиях, рекомендованных ВАК, 4 свидетельства об отраслевой регистрации разработки в Отраслевом фонде алгоритмов и программ, 4 публикации в Телеграфе отраслевого фонда, 3 статьи в научных вестниках ВУЗов и Межвузовском сборнике трудов, 2 статьи в сборниках трудов конференции

Личный вклад соискателя.

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

Объём работы.

Диссертация состоит из введения, четырех глав, выводов Содержание диссертации изложено на 140 страницах, включая 30 рисунков, 3 таблицы и списка цитируемой литературы из 46 наименований

СОДЕРЖАНИЕ РАБОТЫ.

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

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

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

Пусть исходная СЛАУ имеет вид

Ах = ! (1)

где А - заданная квадратная невырожденная, в общем случае комплексная матрица коэффициентов СЛАУ размером N N, х - искомый вектор из N элементов, Г - заданный, в общем случае комплексный вектор правой части из N элементов Тем или иным способом приведем (1) к виду удобному для проведения простых итераций

х = Тх + 0 (2)

Здесь Т- явная, получаемая не более, чем за ¿V2 операций умножения, матрица перехода, с помощью которой итерации, начиная с начального приближения х^ строятся следующим образом

,(* + !к - 0,1,2, (3)

Так, если Т = Е-А, то будем называть (3) методом простой итерации, если же Т = -£>"' (/. + £/), то (3) - метод Якоби, где А = Ь + п + и - разложение на нижнюю треугольную, диагональную и верхнюю треугольную матрицы

Метод простой итерации (3) сходится, если радиус сходимости матрицы перехода

Р = Р(Т) < 1 (4)

Условие (4), как правило, является большим ограничением применимости (3) Значительно расширить область сходимости (3) можно модифицировав метод и введя в матрицу перехода комплексный параметр к

Т = Т(к) = 7^-, £ = (5)

1 -к 1-к W

Для многих практически важных случаев конфигурации спектральной области матрицы перехода Т возможно построение алгоритма поиска оптимального параметра к0 в (5), минимизирующего радиус сходимости модифицированной матрицы перехода Т

МП* )) = ттр(Г(к))<1 (6)

к

Путь поиска оптимального параметра в (6) известен Если точка 1 на комплексной плоскости не принадлежит выпуклой оболочке <ЛТ комплексного спектра матрицы перехода Г, то возможно построение сходящегося ряда (3) с матрицей перехода (5) Для оптимальной сходимости необходимо найти круг соа, содержащий <ЛГ и «видимый» из точки 1 под минимальным углом 2 а Его центр является оптимальным параметром к„, а скорость сходимости определяется при этом, как р = %т(а)

Для некоторых типов конфигураций спектральной области матрицы перехода возможно построение алгоритма поиска к0 Это такие спектральные области, как круг, комплексный отрезок, треугольник, многоугольник, не содержащие точку 1 Соответственно для классов матриц перехода с такими спектральными областями возможно построение сходящегося ряда оптимальной простой итерации

В частности, для матрицы Л с положительным спектром (вещественной или комплексной эрмитовой), оптимальный параметр известен

где 0тт=1 -атач>^т.>, =1_атт~ минимальное и максимальное вещественные собственные числа матрицы перехода соответственно макси-

мальное и минимальное собственное число матрицы А Радиус сходимости при этом р = (I - /(1 + £), где = /атш Аналогичный радиус сходимости в случае вещественных положительно определенных матриц имеет нестационарный метод минимальных невязок

Таким образом, оптимальный параметр в рассматриваемом случае может быть найден алгоритмически с помощью степенного метода, не более, чем за т /V2 арифметических операций умножения, где т - число итераций степенного метода при нахождении максимального и минимального собственного числа Число итераций степенного метода т « N, так как оптимальный параметр определяется с точностью в 2-3 значащие цифры, и на общих затратах метода оптимальной простой итерации затраты этой части алгоритма почти не сказываются

Аналогично, с помощью (7), вычисляется оптимальный параметр в случаях, когда область расположения спектра матрицы Т - окружность, а также окружность и любые включения в ее внутреннюю часть, не содержащая точку 1, а также область спектра - комплексный отрезок, расположенный на луче, исходящем из точки 1 Если область расположения спектра близка к перечисленным выше, то формула (7) может служить для приближенного определения оптимального параметра

Если спектр матрицы Т лежит на произвольном комплексном отрезке, то оптимальный параметр для сходимости модифицированного метода простой итерации есть точка к„ пересечения окружности, проходящей через точку 1 и концы отрезка, с серединным перпендикуляром к отрезку Таким образом, алгоритм поиска оптимального параметра к0 в этом случае также определен Назовем окружность с центром в точке к0 и проходящую через точки конца отрезка «оптимальной» для спектра-отрезка, так как ее центр - это значение оптимального параметра

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

В случае, если спектр матрицы перехода лежит на ломаной, состоящей из нескольких отрезков, или на многоугольнике, быть может включая его внутреннюю часть, причем выпуклая оболочка спектра не содержит точку 1, алгоритм поиска оптимального параметра следующий Находится некоторый характерный треугольник из состава многоугольника, «оптимальная» окружность для которого содержит всю область расположения спектра Значение ее центра принимается за оптимальный параметр сходимости

Практически важен случай, когда точка 0 является точкой накопления спектрального множества матрицы перехода, полученной в результате дискретизации вполне непрерывного интегрального оператора В этом случае одной из вершин характерного треугольника является точка 0, одна из близких к точке 1 вершин многоугольника и вершина многоугольника, наиболее удаленная от точки 0 Если же вся спектральная область сосредоточена вблизи точки 0, то расчет оптимального параметра проводится с помощью формулы (7), где втт = 0 Конкретные примеры расчетов оптимального параметра в этом случае представлены в главе 4

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

Метод релаксации проводится по итерационной схеме с неявной матрицей перехода (I + (1 + к)0)х{к + = (*£>- + / (8)

Здесь А = ь + О + и - описанное выше в методе Якоби разложение исходной матрицы, параметр метода релаксации Эквивалентная явная матрица перехода предполагает трудоемкое обращение матрицы, стоящей в левой части (8), и в итерационном процессе не участвует При лг = 0- это метод Зейделя Для метода релаксации оптимальный параметр для сходимости в аналитическом виде удается найти для следующих типов матрицы СЛАУ 1) трехдиагональная теплицева, вообще говоря, несимметричная матрица, 2) симметричная положительно определенная согласованно упорядоченная (блочная трехдиагональная) матрица

В случае трехдиагональной теплицевой матрицы СЛАУ произвольного размера исследован спектр эквивалентной матрицы перехода процесса релаксации Собственные числа этой матрицы определяются через корни многочленов Чебышева 2 рода на отрезке (0,4), найден минимум по параметру к максимального по модулю собственного числа В этом случае оптимальный параметр сходимости

I а_1а1 -1+ ¡1-// -

тах ^ 2 "0~ """ 1

а* -1+ 1-А/

к -.----=-(9)

Здесь ¡л =4сс« (я-/(М + 1))- максимальный корень многочленов Чебыше-шах

ва второго рода на интервале (0 4), - коэффициенты трехдиагональ-

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

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

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

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

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

Рассмотрена стационарная задача рассеяния электромагнитных волн на прозрачном неоднородном теле, которая описывается в общем случае сингулярным интегральным уравнением для комплексной амплитуды полного электрического поля Е = Е° + Ер"с, состоящего из суммы падающего и рассеянного в присутствии диэлектрика полей Е(р) = (р) + v(e(p) - 1)Ё(р) +

+ vp \{E{q)-№q)klG(r)dQ+ \((s(q)- 1)ËW),grad)gradG(r)dQ (10)

e a

Здесь s(q) -относительная диэлектрическая проницаемость в области неоднородности Q, комплекснозначная функция координат q, ¿„-волновое число свободного пространства, v р - сингулярный интеграл в смысле главного значения, коэффициент v во внеинтегральном члене имеет значение к = 1/3 в трехмерном векторном случае и и = 1/2 в двумерном векторном

случае, функция Грина в трехмерном случае есть G(r) = ex^Jk_'}rl ; в двумерном содержит функцию Ханкеля второго рода нулевого порядка

GO") = --H0<2)(r), где г = \p-q\-расстояние между точкой истока q = (У,У) и 4

точкой наблюдения р = (х,у), х,у- система координат, связанная с областью Q занятой диэлектриком

Уравнение (10) уже представлено в виде, удобном для применения метода простой итерации Е = Е° + 7Е В скалярном двумерном случае Е-поляризации это интегральное уравнение Фредгольма второго рода Спектр такого вполне непрерывного интегрального оператора перехода Т дискретный с точкой накопления собственных чисел в т 0

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

Установлены закономерности спектральных картин оператора Т (и возникающей при его дискретизации матрицы перехода Т) и алгоритмы определения оптимального параметра сходимости итераций в различных типах задач рассеяния

13

Рассмотрим случай, когда функция диэлектрической проницаемости имеет в области (5 набор кусочно-постоянных значений г,,/ = 1 ..и, например, одно значение г,, отличное от значения в свободном пространстве г, * 1. Непрерывный спектр оператора перехода состоит при этом из отрезков [о,1-г,],( = 1..77, в частности из одного отрезка [од-г,], независимо от конфигурации и размеров области. Дискретный же спектр имеет те же закономерности, что и в скалярном двумерном случае.

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

-0.1 О 0 1 0 2 -0.1 Яе([д), 11е(к), I 03

а) б)

Рис. 1 Спектральные картины в рэлеевской области.

На рис. 1 а) изображен спектр в задаче рассеяния на малом в сечении круглом цилиндре диаметром й = 0.Ы, где Я - длина волны в свободном пространстве, и с постоянной относительной диэлектрической проницаемостью г. = 4. На рис. 1 б) - представлен спектр оператора перехода в двумерном векторном рэлеевском случае. Размер диэлектрического квадрата в сечении цилиндра с/ = 0.075/1, где Л - длина волны, значение проницаемости е = 2.

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

В векторных рэлеевских случаях, когда дискретный спектр несущественно сосредоточен возле т. 0, в случае вещественных £, >1,1 = 1..и, оптимальный параметр для сходимости есть где ^ = тах£(,/ = 1..и. Так, на рис. 1-6 к = -0.5 - значение оптимального параметра сходимости.

Таким образом, в рэлеевской (быть может только по одной координате) области оптимальный параметр задается простой формулой

к = Мх' 2 (П)

а радиус сходимости оптимального ряда простой итерации р = \к!(\ -к)| < 1

В блияшей резонансной области, когда й < Л, оптимальный параметр может иметь близкое к (11) значение В скалярном случае ввиду обособленности этого собственного числа, эффективно находится степенным методом, а в векторных случаях оно известно

Наиболее трудоемок для расчетов случай резонансного рассеяния, когда длина волны в среде соизмерима или меньше области неоднородности Характерная спектральная картина дискретного спектра в этой области представлена на рис 2 Линейные размеры спектральной области намного больше 1, а спектральные точки дискретного спектра на комплексной плоскости почти вплотную подходят к г 1 Это ухудшает сходимость процесса итераций Тем не менее, из-за большого числа неизвестных, необходимых для хорошей аппроксимации задачи в этой области, имеет место выигрыш как во временных затратах, так и в ресурсах памяти при использовании метода оптимальной простой итерации

Конечно, определение спектральной картины также требует машинных затрат » п Однако, оказалось, что область локализации дискретного спектра вместе с оптимальным параметром («• на рисунках) устанавливаются с достаточной для дальнейших расчетов точностью при совсем слабой точности аппроксимации задачи в 2-3 сеточных узла на длину волны в среде и далее при улучшении точности аппроксимации до требуемых 8-10 узлов на длину волны в среде практически не изменяются Практически не изменяется при этом и количество итераций необходимое для достижения заданной точности Размерность же СЛАУ п увеличивается при этом в 10-16 раз для двумерных задач и в 30-64 раз для трехмерных при отсутствии временных затрат на определение оптимального параметра Все спектральные картины и значения оптимальных параметров на представленных в работе примерах были определены для небольших значений п < 100 200 и при расчетах с большими значениями " уже практически не изменялись

На рис 2 представлена спектральная картина задачи рассеяния и поглощения плоской электромагнитной волны частоты 0 9 Ггц на мышечном цилиндре диаметра 0 25м с несимметричным костным включением Комплексная диэлектрическая проницаемость тканей в этом диапазоне составляет соответственно е = 58-62г и £ = 14-3; Число точек спектра на рис 2 и = 192, что соответствует 2 5 узлам сетки на длину волны в мышечной среде Оптимальный параметр найден как центр описанной окружности вокруг ближайшего к т 0 треугольника, образованного точкой накопления собственных

чисел - т.О, собственным числом на вещественной оси слева от т.О и одним из собственных чисел справа от т. 1.

Расчет задачи поглощения проведен с этим оптимальным параметром при достаточной аппроксимации в 7.5 узлов сетки на длину волны в мышечной среде. При этом общее число комплексных неизвестных составило 1728, что уже недоступно для расчетов на ПЭВМ с помощью прямых методов. Решение с точностью = 10~5 по электрическому полю получено за т = 950 итераций и заняло несколько минут машинного времени.

-30 о

-90 ВДц)Де(к),1 20

Рис.2. Спектральная картина, геометрия 20 области и диаграмма поглощения резонансного рассеяния на неоднородном цилиндре

Здесь же приведена картина сеточных узлов двумерной несимметричной области рассеяния и поверхностная диаграмма сечения поглощения электромагнитной волны при ее распространении со стороны неоднородного включения. Моделирование таких задач необходимо при разработке устройств СВЧ-гипертермии и СВЧ-диагностики биологических тканей.

На рис.3 представлено решение трехмерной векторной задачи рассеяния на кубе со стороной к0с! = 0.75Л, где Л- длина волны в свободном пространстве, и проницаемостью е = 4. Расчет спектра и значения оптимального параметра /с = -1.5-2.4; на рис.З.а проведен при слабой аппроксимации задачи в 3 узла расчетной сетки на длину волны в среде при общем количестве узлов сетки N = 6-6-6 = 216. При этом вещественная часть оптимального параметра получена из непрерывного спектра к = (\-е)/2 = -\.5 .

Диаграмма направленности (рис 3,6), которая уже не изменяется при дальнейшем улучшении аппроксимации, получена при этом же оптимальном параметре и общем числе узлов сетки N = 9-9-9 = 729. Размер комплексной матрицы перехода при этом 3 ■ Л? = 2187 Решение задачи такого размера недоступно существующими библиотеками программ.

-4 Re(ß),Red).Re(K) 2

а) б)

Рис.3. Численное решение трехмерной векторной задачи рассеяния

Численно решается также задача распределения электростатического потенциала по двумерной области, сводящаяся к краевой задаче для уравнения Пуассона. Показаны возможности разработанной библиотеки в части неявных стационарных алгоритмов, а именно алгоритма оптимального метода релаксации. Пятидиагональная матрица А имеет здесь блочную трехдиаго-нальную структуру и является отрицательно определенной и согласованно упорядоченной матрицей. Методом оптимальной релаксации получены численное решения при порядках СЛАУ N > 1000. Оптимальный параметр найден с помощью второй части формулы (11), а максимальное по модулю собственное число матрицы Якоби определено степенным методом. Сравнения с другими итерационными методами показывают лучшую сходимость здесь метода оптимальной релаксации.

В заключении сформулированы основные выводы и результаты.

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

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

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

3. Разработаны алгоритмы метода релаксации и программные модули библиотеки подпрограмм для решения СЛАУ с матрицами таких типов, как

Т

вещественная трехдиагональная теплицева, в общем случае несимметричная матрица, вещественная симметричная положительно определенная, вещественная симметричная положительно определенная и согласованно упорядоченная (блочно трехдиагональная)

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

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

Основное содержание диссертации опубликовано в работах

1 Куликов С П , Абдель Малик Дж Численное решение системы линейных алгебраических уравнений итерационным методом оптимальной релаксации при согласованно упорядоченной матрице перехода// Сб трудов 54-й Научно-технической конференции МИРЭА, Ч 2 Физико-математические науки, М МИРЭА, 2005, с 19-22

2 Куликов С П, Абдель Малик Дж Комплекс программ для численного решения СЛАУ методами оптимальной простой итерации// Межвуз Сб науч Трудов «Теоретические вопросы вычислительной техники и программного обеспечения», М МИРЭА, 2006, с 182-184

3 Куликов С П , Абдель Малик Дж Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 7071, ОФАП, № Гос Регистрации 50200601839 от 23 10 2006

4 Куликов С П, Абдель Малик Дж Решение системы линейных алгебраических уравнений с положительно определенной матрицей с помощью метода оптимальной простой итерации// Инновации в науке и образовании, Телеграф отраслевого фонда алгоритмов и программ, 2006, №10 (21), с 16

5 Абдель Малик Дж Библиотека подпрограмм для решения некоторых типов СЛАУ большой размерности стационарными итерационными методами Сб трудов 56-й Научно-технической конференции МИРЭА, 4 2 Физико-математические науки М , 2007, с 44-51

6 Куликов С П , Самохин А Б , Абдель Малик Дж Математические обоснования библиотеки программ для решения СЛАУ методом оптимальной

простой итерации Научный вестник МИРЭА М .МИРЭА, 2007, №1(2), с 71-80

7 Куликов С П , Абдель Малик Дж Метод оптимальной простой итерации для решения комплексной СЛАУ большой размерности и численное решение 20 и ЗБ задач электромагнитного рассеяния Научный вестник МГТУ ГА Серия «Прикладная математика и информатика», М МГТУ ГА, 2007, № 120, с 100-110

8. Куликов С П , Абдель Малик Дж Оптимальный параметр сходимости метода релаксации на примере решения СЛАУ с трехдиагональной несимметричной теплицевой матрицей Нелинейный мир М Радиотехника, №10-11,2007, т 5, с 680-684

9 Куликов С П , Абдель Малик Дж Математические обоснования и библиотека подпрограмм для решения некоторых типов СЛАУ большой размерности стационарными итерационными методами Нелинейный мир М Радиотехника, 2007, №12, т 5, с 765-768

10 Куликов СП , Абдель Малик Дж Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8189, ОФАП, № Гос Регистрации 50200700873 от 26 04 2007.

11 Куликов С П , Абдель Малик Дж Численное решение СЛАУ итерационным методом оптимальной релаксации при согласованно - упорядоченной матрице перехода Телеграф отраслевого фонда алгоритмов и программ Инновации в науке и образовании 2007, №4(27), с 37

12 Куликов СП , Абдель Малик Дж Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8190, ОФАП, № Гос Регистрации 50200700874 от 26 04 2007

13 Куликов С П , Абдель Малик Дж Решение СЛАУ с положительно определенной матрицей итерационным методом Зейделя Телеграф отраслевого фонда алгоритмов и программ Инновации в науке и образовании 2007, №4(27), с 37

14 Куликов С П , Абдель Малик Дж Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8367, ОФАП, № Гос Регистрации 50200701094 от 28 05 2007

15 Куликов С П , Абдель Малик Дж Метод оптимальной простой итерации для решения СЛАУ большой размерности с комплексной неэрмитовой матрицей Телеграф отраслевого фонда алгоритмов и программ Инновации в науке и образовании 2007, №5(28), с 29

Подписано в печать 20 02 2008 Формат 60x84 1/16

Бумага офсетная Печать офсетная Усл. печ л. 0,93. Уел кр -отт 3,72 Уч-изд л 1,0 Тираж 100 экз Заказ 94

Государственное образовательное учреждение высшего профессионального образования "Московский государственный институт радиотехники, электроники и автоматики (технический университет)" 119454, Москва, пр. Вернадского, 78

Введение.

1. Математические обоснования применимости явных стационарных итерационных методов для решения некоторых классов СЛАУ большой размерности.

1.1. Постановка задачи и методы решения.

1.2. Прямые методы решения СЛАУ.

1.3. Стационарные одношаговые'итерационные методы.

1.3.1. Явные'методы простой итерации.

1.3:2. Условие выхода из вычислительного процесса по заданной точности в методах простой итерации ■

1.3.3. Метод явной оптимальной простой итерации

1.3.3.1 Случай комплексной неэрмитовой матрицы СЛАУ

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

2.1. Неявные методы простой итерации

2.2 Модификация и оптимизация,сходимости методов простой итерации

2.3. Спектр матрицы перехода и сходимость метода Ричардсона в случае трехдиагональной теплицевой матрицы СЛАУ

2.4. Спектр операторов перехода и сходимость методов Якоби, Зейделя и релаксации в случае трехдиагональной теплицевой матрицы СЛАУ

2.5. Метод оптимальной релаксации для согласованно упорядоченной положительно определенной матрицы СЛАУ

2.6. Случай вещественной симметричной положительно определенной матрицы СЛАУ. Метод Зейделя и метод релаксации с формальным параметром

3. Описание структуры и подпрограмм библиотеки.

4. Численные исследования.

4.1. Численные исследования скалярных двумерных задач рассеяния электромагнитных волн.64 4.2 Численные исследования задач поглощения электромагнитных волн в биологических структурах и тканях.

4.3. Численные исследования векторных двумерных и трехмерных задач рассеяния электромагнитных волн:.

4.4. Численные исследования1 двумерных краевых задач электростатики (уравнения Пуассона с источниками).

Численное решение системы линейных алгебраических уравнений (СЛАУ) - одна из наиболее часто встречающихся задач линейной алгебры и численных методов в научных и технических исследованиях. Такая задача возникает во многих прикладных дисциплинах, таких как математическая физика (численное решение дифференциальных и интегральных уравнений), экономика, статистика. При этом прикладные задачи часто требуют решения больших и сверхбольших СЛАУ с числом неизвестных более 1000. К таким СЛАУ, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов по линейному размеру. Так задачи электродинамики и акустики в неоднородной среде требуют, как минимум 8-10 узлов расчетной сетки на длину волны в среде [1]. В наиболее интересной резонансной области, когда длина волны соизмерима с размерами области неоднородности, это приводит, например, для задачи рассеяния на прозрачном неоднородном теле линейного размера в длину волны к комплексной СЛАУ с числом комплексных неизвестных N=10*10*10=1000. Удвоение числа узлов сетки по линейному размеру с целью, например, тестирования достигнутой точности аппроксимации задачи потребует уже решения комплексной СЛАУ с N=8000, что равносильно по машинным затратам решению вещественной СЛАУ с N=16000.

Существующие библиотеки программ на языках высокого уровня (Фортран, СИ и их современные модификации, а также программы, входящие в пакеты Mathcad и Mathlab), разработаны на основе, так называемых, прямых методов решения СЛАУ, типа метода Гаусса-Жордана и его модификаций. Число арифметических операций умножения для численного решения СЛАУ размерностью N с помощью прямого метода ~ N3 [2]. Кубическая* зависимость числа арифметических операций от размера матрицы СЛАУ приводит при N>1000 к нереально большому времени решения даже на самых современных ПЭВМ. Для ориентира укажем, что решение вещественной СЛАУ с N=1000 вещественных неизвестных на ПЭВМ Pentium-4, 3.2 Ггц, 512 Mb занимает 2-3 мин машинного времени. Кроме того, время решения несоразмерно возрастает при использовании прямых методов в случае N>1000 по причине недостаточности объема оперативной памяти для хранения данных задачи. В прямых методах требуется, как правило, хранить 1-2 служебных матрицы того же размера, что и исходная матрица. При недостатке оперативной памяти данные задачи располагаются частично на твердом диске и обменное время между процессором и памятью существенно возрастает. Задача может быть не решена ввиду недостатка виртуальной памяти, либо займет нереально большое машинное время.

Итерационные методы решения СЛАУ намного экономнее, как по машинному времени решения, так и по использованию оперативной памяти. Так, если итерационный метод, является быстро сходящимся с числом итераций m«N, то время решения, пропорциональное уже квадрату размера матрицы ~ m*N , оказывается- существенно меньше, примерно в N/m раз для вещественной и 2N/m раз для комплексной СЛАУ. Кроме того, требуется хранить в оперативной памяти, как правило, только одну матрицу - матрицу перехода итерационного метода. При использовании быстро сходящихся итерационных методов вполне решаемыми в реальном времени на современных ПЭВМ оказываются комплексные СЛАУ с N >1000 и N » 1000.

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

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

Основная сложность при построении такой библиотеки- вытекает из главного недостатком итерационных методов численного решения СЛАУ, а именно, из их неуниверсальности и;требований выбора методов и их подстройки для различных типов матрицы СЛАУ. Так, для явного метода оптимальной простой итерации в общем случае комплексной матрицы известен лишь путь определения оптимального параметра, который минимизирует радиус сходимости модифицированной матрицы перехода [1]. Этот путь основан на знании комплексного спектра матрицы, однако его реализация в алгоритм далеко неоднозначна и для разного типа матриц (и, соответственно, разных типов спектров матрицы перехода) проводится различными способами. Так, требуется найти выпуклую оболочку комплексного спектра матрицы перехода, «видимую» под наименьшим углом из т.1 на комплексной плоскости. При этом выпуклая оболочка спектра не должна содержать т.1, иначе задача таким итерационным методом (с такой матрицей перехода) не решается.

Следует сказать, что исходная- матрица СЛАУ , матрица А , трансформируется в матрицу перехода Т множеством способов, соответствующих различным итерационным методам. Выбор итерационного метода должен базироваться на.априорном знании пользователем свойств исходной матрицы, точнее свойств ее спектра. В этом состоит основное ограничение применения библиотеки итерационных методов. Однако, матрицы СЛАУ, возникающие в определенных прикладных областях, как правило, имеют определенные известные свойства. Так, матрицы, возникающие при решении краевых задач для обыкновенных дифференциальных уравнений, методом сеток, являются, как правило, вещественными, симметричными, положительно определенными трехдиагональными или ленточными матрицами, а при решении краевых задач для- дифференциальных уравнений в частных производных еще и дополнительно согласованно упорядоченными (блочными трехдиагональными) матрицами. Для решения СЛАУ с такой матрицей наиболее эффективным по скорости сходимости (в том числе и среди неявных методов, как показано в п. 2.5) является метод оптимальной релаксации, для которого оптимальный параметр представлен простой аналитической формулой [3, 42]. В случае трехдиагональ-ной теплицевой, не обязательно симметричной, (т.е. не обязательно положительно определенной), матрицы СЛАУ, показана наибольшая эффективность оптимального метода релаксации среди стационарных итерационных методов [15].

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

Если же дополнительно матрица перехода является согласованно упорядоченной (блочно трехдиагональной), то для нее наилучшие результаты показывает метод оптимальной релаксации, с оптимальным параметром, представленным простой аналитической формулой [3, 42]. В формулу для оптимального параметра метода релаксации входит значение максимального по модулю собственного числа матрицы перехода Якоби, которое определяется специальной подпрограммой с помощью степенного метода [35]. Аналогичное значение для оптимального параметра справедливо и для некоторых неположительно определенных (и даже с комплексным спектром), но согласованно упорядоченных матриц, таких как трехдиагональная несимметричная теплицевая матрица [15].

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

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

Использование степенного метода в случаях автоматического вычисления оптимального параметра по наибольшему и наименьшему по модулю собственному числу ненамного увеличивает машинные затраты, так как степенной метод также итерационный и определение оптимального параметра не требует высокой точности (достаточно двух-трех значащих цифр). Соответственно, число итераций степенного метода небольшое - mi =10-30.

В случаях векторного рэлеевского рассеяния, когда интегральный оператор задачи сингулярен, оператор перехода имеет непрерывный спектр в виде отрезка от т.О до т. 1-е, где е- значение относительной диэлектрической проницаемости среды рассеивателя [1]. Дискретный спектр в релеевском случае незначителен. Таким образом, оптималь

1 -б ныи параметр сходимости здесь строго определен к = —-.

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

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

В соответствии с целью работы поставлены следующие научные задачи:

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

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

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

• Разработка структуры и программных модулей библиотеки подпрограмм на языке Visual Fortran на основе стационарных итерационных методов для решения СЛАУ большой размерности с широкими классами матриц

• Демонстрация возможностей библиотеки и определение границ её применимости. Численные решения с помощью разработанной библиотеки СЛАУ большой размерности, возникающей в 2D и 3D задачах рассеяния электромагнитных волн на локальных прозрачных неоднородно-стях и в двумерных краевых задачах для уравнения Пуассона с источниками.

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

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

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

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

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

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

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

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

1. Самохин А.Б. —М: Радио и связь, 1998. —160 с.

2. Численные методы. Куликов С.П., Самохин А.Б., Чердынцев В.В. Учебное пособие —М.: МИРЭА, 2003 —80 с. Электронная версия:

3. Численные методы. 4.1. Куликов С.П., Самохин А.Б., Чердынцев В.В.—М.: МИРЭА, 2006 —80 е., http://www.pm.fcvb.mirea.ru

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

5. Фортран и вычислительные методы. Самохин А.Б. и др. — М.:Русина, 1994. —120 с.

6. Численные методы и программирование на Фортране для персонального компьютера. Самохин А.Б. и др. —М.:Радио и связь, 1996.—224 с.

7. Численные методы. Самарский А.А., Гулин А.В. Учебное пособие для вузов. -М: Наука, 1989. -432 с.

8. Введение в численные методы. Самарский А. А. Учебное пособие для вузов. 3-е изд., стер. СПб: Издательство «Лань», 2005. -288с.

9. Численные методы. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. —М.:Бином. Лаборатория знаний, 2006. —636 с.

10. Основы численных методов. Вержбицкий В.М. —М.:Высшая школа, 2002. —840 с.

11. Численные методы. Использование MATLAB,— М.:Изд.»Вильямс», 2001.-720 с.

12. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.- 124 p.- http://www. Net-lib.org/templates/ Templates.html

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

14. Матрицы и вычисления. Воеводин В.В., Кузнецов Ю.А. — М.:Наука. —320 с.

15. Трехдиагональные матрицы и их приложения. Ильин В.П., Кузнецов Ю.И. —М.:Наука, 1985. —208 с.

16. Метод последовательных приближений для задач рассеяния волн на диэлектриках. Куликов С.П., Самохин А.Б. —Изв. Вузов— Радиофизика, 1986, 29, №1, с.99-105.

17. Численное решение интегрального уравнения рассеяния итерационными методами. Куликов С.П. Сб. трудов 54 научно-технической конференции МИРЭА. 4.2.—М.: МИРЭА, 2005. —с. 9-15.

18. Метод сингулярных объемных интегральных уравнений для задач электромагнитного рассеяния на сложных трехмерных диэлектрических структурах. Самохин А.Б. —Электромагнитные волны и электронные системы, 2007, 12, №8, с.7-14.

19. Dielectric Properties of Tissues and Biological Materials. A critical review. Crit.Rev.Biomed. Eng., Vol.17, pp. 25-104,1989.

20. M. Okoniewski, M.A.Stuchly. A Study of the Handset Antenna and Human Body Interaction. IEEE Trans. On Microwave Theory and Techniques, Vol. 44, No. 10, 1996.

21. American National Standart safety levels with respect to human exposure to radio frequency electromagnetic fields, 300 kHz to 100 GHz, NY:IEEE, 1991.

22. Сборник научных программ на Фортране. Руководство программиста. Вып. 2. Матричная алгебра и линейная алгебра. Пер. с англ. С .Я. Виленкина. -М.: Статистика, 1974.

23. Современный Фортран. Бартеньев О. В.- 4-е изд., доп. И перераб. М.: ДИАЛОГ -МИФИ, 2005. - 560с.

24. Фортран для профессионалов. Математическая! библиотека IMSL: Ч. 1. Бартеньев О. В. М.: ДИАЛОГ-МИФИ, 2000. - 448с.

25. Фортран для профессионалов. Математическая библиотека IMSL:

26. Бартеньев О. В. М.: ДИАЛОГ-МИФИ, 2001. - 320с.

27. Фортран для профессионалов. Математическая библиотека IMSL:

28. Бартеньев О. В. М.: ДИАЛОГ-МИФИ, 2001. - 368с.

29. Графика OpenGL: Программирование на Фортране. Бартеньев О. В. М.: ДИАЛОГ-МИФИ, 1999. - 368с.

30. Fortran: основы программирования. Артёмов/И. Л М.: ДИАЛОГ-МИФИ, 2007.- 304с.

31. Библиотека алгоритмов 516-1006. (Справочное пособие.) Вып. 2 М.,Агеев М. И., Алик В'. П., Марков Ю. И. «Сов. Радио», 1976, 136с.

32. Библиотека алгоритмов 1016-1506. (Справочное пособие.) Вып. 3 М. Агеев М. И., Алик В. П., Марков Ю. И. «Сов. Радио», 1976, 128с. (Библиотека технической кибернетики).

33. Современный Фортран. Самоучитель. Немнюгин М. А., Стесик О. Л. СПб: БХВ-Петербург, 2004. - 496с.

34. Fortran & Win32 API: Создание программного интерфейса для Windows современного Фортрана. Штыков В .В., М.: ДИАЛОГ-МИФИ, 2001. -304с.

35. Параллельные вычисления. Воеводин В.В., Воеводин Вл.В. СПб: БХВ-Петербург, 2004. - 608с.

36. Программирование Windows-приложений на языке Fortran. Элементы управления и графика Windows. Васильченко В. В. М.: ДИАЛОГ-МИФИ, 2006. - 400с.

37. Куликов С.П., Абдель Малик Дж. Комплекс программ для численного решения СЛАУ методами оптимальной простой итерации// Межвуз. Сб. науч. Трудов «Теоретические вопросы вычислительной техники и программного обеспечения», М., МИРЭА, 2006, с. 182-184.

38. Куликов С.П., Абдель Малик Дж. Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 7071, ОФАП, № Гос. Регистрации 50200601839 от 23.10.2006.

39. Абдель Малик Дж. Библиотека подпрограмм для решения некоторых типов СЛАУ большой размерности стационарными итерационными методами. Сб. трудов 56-й Научно-технической конференции МИРЭА, 4.2. Физико-математические науки. М., 2007, с.44-51.

40. Куликов С.П., Самохин А.Б., Абдель Малик Дж. Математические обоснования библиотеки программ для решения СЛАУ методом оптимальной простой итерации. Научный вестник МИРЭА. №1(2), 2007, с.71-80.

41. Куликов С.П., Абдель Малик Дж. Оптимальный параметр сходимости метода релаксации на примере решения СЛАУ с трехдиагональной несимметричной теплицевой матрицей. Нелинейный мир. №10-11, т.5, 2007, с.680-684.

42. Куликов С.П., Абдель Малик Дж. Математические обоснования и библиотека подпрограмм для решения некоторых типов СЛАУ большой размерности стационарными итерационными методами. Нелинейный мир. №12, т.5, 2007, с.765-768.

43. Куликов С.П., Абдель Малик Дж. Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8189, ОФАП, № Гос. Регистрации 50200700873 от 26.04.2007.

44. Куликов С.П., Абдель Малик Дж. Численное решение СЛАУ итерационным методом оптимальной релаксации при согласованно-упорядоченной матрице перехода. Телеграф отраслевого фонда алгоритмов и программ. Инновации в науке и образовании. №4(27), 2007, с.37.

45. Куликов С.П., Абдель Малик Дж. Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8190, ОФАП, № Гос. Регистрации 50200700874 от 26.04.2007.

46. Куликов С.П., Абдель Малик Дж. Решение СЛАУ с положительно определенной матрицей итерационным методом Зейделя. Телеграф отраслевого фонда алгоритмов и программ. Инновации в науке и образовании. №4(27), 2007, с.37.

47. Куликов С.П., Абдель Малик Дж. Свидетельство об отраслевой регистрации разработки в фонде алгоритмов и программ № 8367, ОФАП, № Гос. Регистрации 50200701094 от 28.05.2007.

48. Куликов С.П., Абдель Малик Дж. Метод оптимальной простой итерации для решения СЛАУ большой размерности с комплексной неэрмитовой матрицей. Телеграф отраслевого фонда алгоритмов и программ. Инновации в науке и образовании. №5(28), 2007, с.29.