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

• Абдель Малик Джихан
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Абдель Малик Джихан

Введение.

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

Список литературы диссертационного исследования кандидат технических наук Абдель Малик Джихан, 2008 год

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.