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

Крукиер, Борис Львович

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

Крукиер, Борис Львович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Двухпараметрические попеременно-треугольные и двуциклические методы решения сильно несимметричных систем линейных алгебраических уравнений»

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

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

КРУКИЕР Борис Львович

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

01.01.07 - Вычислительная математика

АВТОРЕФЕРАТ

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

Москва - 2005

Работа выполнена в Ростовском Государственном Университете

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

Л.Г. Чикина

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

профессор Карамзин Ю.Н.

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

Ведущая организация: Казанский Государственный Университет

Защита состоится «_»_2005 года в_часов на заседании

диссертационного совета К002.058.01 по защите диссертации на соискание ученной степени кандидата физико-математических наук при Институте математического моделирования РАН по адресу 125047, г.Москва, Миусская пл., д. 4-А.

С диссертацией можно ознакомиться в научной библиотеке ИММ РАН.

Автореферат разослан «30» ОЪ 2005 г.

Ученый секретарь диссертационного Совета, кандидат физико-математических наук

В.И. Похилко

ХАРАКТЕРИСТИКА РАБОТЫ

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

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

РОС. И ¡'М5 МАЯ Ы-; ".¿. Гг ЬЛ 3

С.ПстерС>5>г

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

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

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

В соответствии с этими целями решен ряд задач:

• разработаны, теоретически обоснованы и численно проверены двухпараметрические попеременно-треугольный (ПТКМ) и двуциклический (ДТКМ) итерационные методы решения СЛАУ с сильно несимметричной матрицей;

• рассмотрены Вопросы ускорения двухпараметрических ПТКМ и ДТКМ;

• предложено использование параметрических и безпараметрических ПТКМ и ДТКМ в качестве переобуславливателей для методов вариационного типа.

Научная новизна работы определяется полученными теоретическими результатами исследования:

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

• определением (в частных случаях) оптимальных параметров двухпараметрических ПТКМ и ДТКМ;

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

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

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

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

1. предложены двухпараметрические итерационные методы решения сильно несимметричных систем: попеременно-треугольный (ПТКМ) и дву-циклический (ДТКМ) кососимметричные методы;

2. получены достаточные условия сходимости двухпараметрических ПТКМ и ДТКМ;

3. для частных случаев проведены исследования по нахождению оптимального итерационного параметра для двухпараметрических ДТКМ и ПТКМ;

4. предложен метод ускорения сходимости двухпараметрических ДТКМ и ПТКМ за счет специального выбора компонент обращаемого оператора;

5. показана эффективность использования этих методов в качестве переобуславливателя для методов вариационного типа.

Апробация работы. Основные результаты диссертации докладывались на IX и X Всероссийских школах-семинарах молодых ученых «Современные проблемы математического моделирования» (п. Абрау-Дюрсо. 2001г., 2003г.); на международной конференции «Математическое моделирование и вычислительный эксперимент в механике и физике» (i. Ростов-на-Дону, 2001г.); на международной конференции IMMC-2002 «Итерационные методы и матричные вычисления» (г. Ростов-на-Дону, 2002г.); Conference «Computa-

tional linear algebra with applications», MILOV1, 2002; International Conference on Computational Mathematics, Novosibirsk, 2002; Annual Scientific Congerence GAMM 2003; Session 22, 2003, Abano Terme - Padua; IX и X Всероссийские Совещания по проблемам построения сеток для решения задач математической физики (п. Абрау-Дюрсо, 2002г., 2004г.), Всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики» (Ростов-на-Дону, 2004); на 5-ой Всероссийской конференции «Сеточные методы для краевых задач и приложения» (г. Казань, 2004г.);

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

Структура и объем диссертации. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Библиография включает 133 наименований. Общий объем диссертации составляет 163 страницы, включая 14 таблиц и 12 рисунков.

Автор глубоко признателен своему научному руководителю к.ф.-м.н., с.н.с Чикиной Л.Г. и благодарит коллектив ЛВЭ ЮГИНФО РГУ за внимание к работе, оказанную помощь и полезные советы.

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

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

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

Ay = f О)

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

V-1 - у"

- + Ау -f > (2)

^п

где 5„ - операторы метода, А - исходная матрица системы, г„ > 0 - последовательность итерационных параметров; у0 - начальное приближение, / -правая часть (1), f,y° е //, Я-конечномерное гильбертово пространство,у" -решение на и-ой итерации, п - номер итерации.

Итерационный метод (2) можно записать в эквивалентном виде z"*' = г" - г ,s;V", где г" = Ау" -f - вектор невязки на п-ой итерации, a z" = / -у - вектор погрешности (ошибки) этого метода, у — точное решение системы (1).

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

В разделе 1.2. рассматриваются классические итерационные методы: Яко-би и Чебышева, Гаусса-Зейделя, последовательной верхней релаксации (SOR) и его модификации, симметричной и несимметричной последовательной верхней релаксации (SSOR, USSOR), треугольные, попеременно-треугольные и методы LU - разложения.

Определение 1. Итерационный метод (2) называется ^-циклическим, если

для любого п > 0 и фиксированного ,s > 1.

Определение 2. Итерационный метод (2) называется стационарным, если матрица S, и параметр т„ не зависит от номера итерации (оператор метода В = В„ является постоянной матрицей).

Определение 3. Итерационный метод (2) называется треугольным ТМ (попеременно-треугольным ГТТМ), если оператор метода имеет вид

В = ВС+ г/?! или В = В( +тЯ2 (В = (В, + £УД,)В(~'(ВГ + ®/?2)), где Л/ и - некоторые нижняя и верхняя треугольные части исходной матрицы А системы (1), В( - самосопряженная матрица.

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

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

А=А0+А/, А0= (А + А1)/2=Ао, А,= (А-А7)/2=-А,7. Причем для кососимметричной составляющей справедливо следующее разложение

А^Кц+Ки

где К; и Кц строго нижняя и верхняя треугольные части матрицы Л/, причем

Ки~ .

Определение 4. Оператор А называется диссипативным, если для любого вектора х * о его симметричная часть положительно определена (Ах,Х) = (А1ГХ,Х)>0.

Определение 5. Оператор .4 называется сильно несимметричным, если в какой либо норме ||л , ||»||.

Для исследования итерационного метода (2) рассмотрим однородное уравнение для векторов погрешностей

В*к*,~2к+Лгк= О, *= 0,1,2,...; 20=у0-у т

или в разрешенной относительно гы форме гш = йгк, где

в = В-\В-тА) называется оператором перехода итерационного метода (2).

Если оператор перехода С = С(г) зависит от итерационного параметра г, то метод (2) будем считать однопараметрическим итерационным методом, если же С = зависит не только от г, но и от некоторого второго параметра «, то - двухпараметрическим.

Для получения условий сходимости итерационного метода (2) надо исследовать его оператор перехода и оценить его спектр р{в) = шах

или его норму ЦбЦ < 1.

Класс кососимметричных методов был предложен в 1979 году Л.А. Кру-киером и основан на идеи включения в оператор В итерационного метода (2) треугольных частей К, или Ки только кососимметрической составляющей Ах .

Теоретическое и численное исследование этого класса методов, выполненное за последние годы, позволило построить сходящиеся методы для СЛАУ с диссипативными сильно несимметричными матрицами. Были получены однопараметрические треугольные (ТКМ), попеременно треугольные (ПТКМ) и двуциклические (ДТКМ) кососимметрические итерационные методы решения для сильно несимметричных диссипативных матриц.

Отметим, что основное свойство этого класса методов состоит в том, что кососимметричная составляющая оператора метода пропорциональна косо-симметричной составляющей оператора системы, т.е

В^тАг

Исследования были проведены в энергетической норме В0 + /?')> 0. Оператор перехода ТКМ в этой норме имеет вид

С{т) = (Е + тГУ(Е + тР0),

где

исследование оператора Е 4 тР0 дало достаточное условие сходимости ТКМ (ПТКМ, ДТКМ) в виде В„ > 0,5тЛ0.

Во второй главе представлены основные теоретические и численные результаты.

Исследовано обобщение однопараметрических ПТКМ и ДТКМ, введением в оператор метода В параметра со, отличного, в общем случае, от параметра метода т. Исследования таких двухпараметрических ПТКМ(т, со) и ДТКМ(т, со) проводилось по методике, отличной от разработанной ранее для однопараметрических методов.

Использованный при доказательствах энергетический подход позволил доказать достаточные условия сходимости в норме = б0-0,5<Мо

^^(т,®)]^ Сначала достаточные условия сходимости методов даны

без каких либо ограничений на свойства невырожденного оператора системы А, а затем, в следствиях, они приведены для случая диссипативного оператора системы (1).

В разделе 11.1. и его подразделах рассмотрен энергетический подход исследования ДТКМ (т, со), доказана теорема сходимости и следствие к ней. В частных случаях доказаны теоремы о нахождении оптимального параметра и проверена чувствительность метода к его изменениям.

Двухпараметрический ДТКМ имеет вид

где В1 =(Diag(Bl) + c)KlУ оператор первого цикла, Ви = (Diag(Bu) + соК,,}-оператор второго цикла. Оператор перехода метода (3) имеет следующий вид

) 4соК, )У ^ 4 Ау= /,

(3)

С = В?{ВЬ - ГЛ)В$ {ви - тА) = Проделывая простые преобразования с оператором Сь, приводим его к виду

Требование положительной определенности оператора >0, позволяет получить оператор перехода в виде

а = Л/"» С ЛГ* /.о "/.о >

где

0,=\Е + -Р,

Е- г-

т.е. исследование сходимости метода проводится в энергетической норме Аналогичные преобразования производятся и для оператора О, . Тогда для сходимости метода достаточно, чтобы

¡С|| = Це^Ц^ С, 4 Л^Ц < 1.

А это в свою очередь означает, что достаточно потребовать

'1,0 = Г

Ои <1.

Теорема 1. (Достаточное условие сходимости двухпараметрических ДТКМ). Пусть

= вы = Ко > о,Л',,, = = Ко > 0. (4)

Тогда для сходимости метода (3) достаточно выполнения следующих условий

ЧЪу.У)

0<т<а+

{р,уЛуУ 2 (Риу,у) (ЪуЛУ)'

где Р[ = = лфл$0.

Следствие 1. Если оператор А исходной системы (1) диссипативен и выполнены условия (4), то для сходимости метода (3) достаточно выполнения условия

0<г <со.

Доказано, что достаточно простыми преобразованиями операторные неравенства (4) можно свести к легко проверяемому неравенству

а,<2АМ

ikiMwr

где Bt =Diag(B„o) = Diag(Bl0).

Для нахождения оптимального параметра, при условии, что оператор метода не зависит от параметра релаксации, т.е. m=const>0 и оператор метода содержит параметр, пропорциональный параметру релаксации, т.е. а=кт доказаны следующие теоремы:

Теорема 2. Пусть оператор А системы (1) диссипативен, со = const > О и для двухпараметрического ДТКМ выполнены достаточные условия сходимости N0 > 0, где N0 удовлетворяет условиям

\N,a, если ^m„(NL0)>

R„. если Ama(Nua)>Amn(Nl0),

0<Г <0.

Пусть также

О < т,а,, (у,у)< т1(Р1у,у) <(Р,у,Р,у)< М, (Р,у,у) < М,а,2(у,у).

О < т„а,, (у,у) < ти(Р„у,у) <(Р„у, Р„у) < Ми(Риу,у) < М(,ат(у,у)

О < та, (у,у) < т(Р,у,у) < (/> у, Р,у) < М(Р,у,у) < Ма2 (у,у), (5)

где Т = L,U,

т = гсш.{т,,ти), а, = шах (а,л,аш), М =шю (М,,М(/), а2-тт{ре1г,а1П).

Тогда при

2 т'

двухпараметрический ДТКМ сходится и для погрешности справедлива оценка

где

у"-у! . к = 0,1,-,

_ + <*\ м1™2 Л

* / . _ . ч

А =

т(4 + Мтгах)

1+-

4 + Могау

и т,М, а/ определены из соотношения (5).

Число итераций, достаточных для достижения заданной точности е, оценивается числом

п(е)

= ню

"Ц/л)'

Теорема 3. Пусть оператор А системы (1) диссипативен, а> = кти для двухпараметрического ДТКМ выполнены достаточные условия сходимости Л',, > 0, где /V,, удовлетворяет условиям

Ко, ее™ ^(Нм^^Л^'о)'

Н«- еслмЛтш(Лг(;п)>Ятш(УУло),

0<г <<в.

Тогда при

двухпараметрический ДТКМ сходится в энергетической норме //^ и для погрешности справедлива оценка

где

Рг='

и М, а1 определены из соотношения (5).

Чиспо итераций, достаточных для достижения заданной точности е, оценивается числом

И(£) =-¡¿—¿г.

В разделе 11.2. и его подразделах рассмотрен энергетический подход исследования ПТКМ (г,со), доказана теорема сходимости и следствие к ней. И также, как для ДТКМ (т,со), в частных случаях доказаны теоремы о нахождении оптимального параметра метода.

Двухпараметрический ПТКМ имеет вид

V"*' — Vй

(В< + юК, )В? (Вс + а>К, К-- Ау" = / . (6)

Оператор перехода метода (6) имеет следующий вид

С^В'(В-Ы), (7)

где

В = (Вс + соК, )В-' (в, + аК, ). Сделав достаточно простые преобразования в (7), получаем

О = + со А)~' (А',, - (г -а)А),#0 = В,,- (оА0 = ЛГ0'. Требование положительной определенности оператора N0>0, позволяет получить оператор перехода в виде С = /V"- в Л^, где

G = (E + aP) '(£-(r-a)p),p = N'^AN"2. Т.к. оператор Gподобен оператору G, то исследование сходимости метода будем проводить в энергетической норме Nu, т.е. для сходимости метода достаточно потребовать |6l| v = ||с?|| < 1.

Теорема 4. (Достаточное условие сходимости двухпараметрических ПТКМ). Пусть

^о - Д) ~ 0JА)= >0. (8)

Тогда для сходимости метода (6) достаточно выполнения следующего условия

о <Т<2й}+рЩ, (Ру,Ру)

где Р = N^AN0'!.

Следствие 2. Если оператор А исходной системы (1) диссипативен и выполнено условие (8), то для сходимости метода (6) достаточно выполнения следующего условия

0 < г < 2о>.

Отметим, что достаточно простыми преобразованиями операторное неравенство (8) можно свести к легко проверяемому неравенству

0<„<д IB WMMMKIHIM

••<с) ¡ой

Также, как и для ДТМК, для метода ПТКМ в частных случаях co=const>0 и со = кт можно найти оптимальный параметр.

Теорема 5. Пусть оператор А системы (1) диссипативен, а = const > 0 и для двухпараметрического ПТКМ (б) выполнены достаточные условия сходимости

В0 -юАа >0 и 0<т<2а> Тогда, оптимальный параметр метода находится по формуле

г =(й л--,

опт '

двухпараметрический ПТКМ сходится и для погрешности справедлива оценка

где

^ а, +а^согтг

т(\+Мт2аА

Р\ =-*-~

1 + Меогах

и т, М, ОС] определены из соотношения

О < таг, {у,у) < т(Ру,у) < (Ру,Ру) £М(Ру,у) < Ма2(у,у), (9)

^е а, = Ятп (/>) > О, ог2 = Л^ (Рв).

Число итераций, достаточных для достижения заданной точности е, оценивается числом

п{£)-ЖУ

Теорема 6. Пусть оператор А системы (1) диссипативен, со-кт и для двухпараметрического ПТКМ (6) выполнены достаточные условия сходимости

В0-^Аа>0 и 0<г<2ю.

Тогда, оптимальный параметр метода находится по формуле

г = . = (о

опт I ГТ опт'

двухпараметрический ПТКМ сходится и для погрешности справедлива оценка

где

л ЦТ

* (К

5\М

1 + -

где М. а, из (9).

Число итераций, достаточных для достижения заданной точности е, оценивается числом

В разделе 11.3. рассмотрены возможности ускорения сходимости предложенных методов, на примере двухпараметрического ДТКМ.

Ускорение предложенных методов может быть достигнуто не только за счет наличия параметров и их оптимального выбора, но и за счет специального построения операторов Вс, В\, Ви, входящих в структуру обращаемых операторов методов ГТГКМ и ДТКМ, которые обеспечивают положительную определенность операторам, задающим норму в методах, и тем самым, снимающим операторные ограничения в достаточных условиях сходимости.

Теорема 7.

Пусть оператор А системы (1) диссипативен и 0 < г < а. Для сходимости двухпараметрического ДТКМ достаточно, чтобы диагонали в операторах метода первого и второго циклов вычислялись по формуле

где Т=Ь, и, числовой параметр 5 > О.

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

4%)

В разделе 11.4. приведены численные результаты тестирования рассмотренных методов и их сравнения с классическими методами. Модельная задача, описана в разделе 1.3.4.

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

--Ду + - и—+ 4 ' +у—+ 4 >

Ре 2 ' ' '

= /(х,У)

¿к (к ду ду (х,у)е П = [0,1]х[0,1],

Правая часть / и краевые условия выбирались таким образом, чтобы аналитическим решением задачи была гладкая функция 5(ху)=е*>,5т(жф1'п(яу).

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

Поле скоростей заданно в таблице 1 и подобранно таким образом, чтобы удовлетворить условие несжимаемости среды, т.е. 0^(У)-0, У={и,у}

Таблица 1.

Задача и V

1 1 -1

2 1-2х 2у-1

3 х+у х-у

4 зт2лх -27гусоз2тсх

Итерационный процесс останавливался при выполнении следующего ус ловия

г«>

Численное исследование на модельной задачи проводилось для кососим-метрических методов, разработанных ранее, их модификаций, 850Я и двух-параметрических ПТКМ и ДТКМ. Все эти методы имеют похожую структуру и имеют один порядок арифметических операций на каждой итерации. Таким образом, для оценки эффективности методов достаточно сравнивать лишь число итераций. Все расчеты выполнялись на одной и той же ПЭВМ, на модельных задачах 1-4, с числом Ре = 103, 104, 105.

На рисунках по шкале вверх указано количество итераций сделанных каждым методом, для расчетов на модельных задачах 1-4, с числом Ре = 105.

На рисунке 1 показано численное сравнение различных вариантов метода ПТКМ. Для методов ПТКМ брали следующие диагонали в операторе метода:

ПТКМ-1 : Вс = Е, для параметров (2т,т),

ПТКМ-2 : Вс = Е, для параметров (т,т),

ПТКМД :ВС = Б, 0 = 1(01 + £>2) = 1 ^{КыКт1Л + КГЫКЫ) +1, для параметров (2т,т),

ДПТКМ: Diag(вc) = bcn + для параметров (2, т)

1 ! I

■ ПТКМ-1 ■ ПТКМ-2 □ ПТКМД ■ ДПТКМ ИЗБСЖ

Рисунок 1. 19

На рисунке 2 показано численное сравнение методов ДТКМ. Для методов ДТКМ брали следующие операторы метода: ДТКМ: 5, = Е + 2т К, ,Ви = Е + 2тКи, для параметров (2т,т), ДТКМО: В, =E-(oD0 + 2тК,,Bu=E-a>D0 + 2тКи, D„ = 0,5Diag(Kr Ки + К, Ки), для параметров (2т,т), ДДТКМ: В, = Diag(B,) + 2Kl,Ви = Diag(B,) + 2K,.,w* параметров(2,т)

Diag{B,) = Diag{Bu) = Ъш = Ъш = £|<ц| + ЦЦ+ТЫ

ill

14000 ---"

12000 10000 8000 6000 4000 2000 0

1 задача 2 задача 3 задача 4 задача

а дткм ■ дткмо ■ ддткм bssor

Рисунок 2

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

В главе III рассмотрены вариационные методы BiCG и GMRES(m), которые использовались для решения модельной задачи как самостоятельно, так и с переобуславпиванием, где в качестве переобуславливателей использовались двухпараметрические ПТКМ и ДТКМ. Для оценки эффективности такого подхода, полученные численные результаты сравнивались с аналогичными результатами для «классического» переобуславливателя, которым являет-

ся ЗЯСЖ. Для улучшения сходимости вариационных методов предлагалась технология левого переобусдавливания.

На рисунке 3 показано численное сравнение метода ОМЯЕБСЮ) с 4 пере-обуславливателями: ПТКМ-1, ДПТКМ, ДПТКМ1, где

На рисунке 4 показано численное сравнение метода ЕЛСО с 4 переобу-славливателями: ПТКМ-1, ДПТКМ, ДПТКМ 1, где

Ь<., + + и ЗБСЖ.

ШвМЯЕ8(10) ■ вМ1ЧЕ5(10)+ПТКМ-1 □ СМКЕ5(10)+ДПТКМ

■ СМРЕЗ(10)+ДПТКМ1 О С1ИРЕЗ(10)+8ЭОК

Рисунок 3.

1 задача 2 задача 3 задача 4 задача

■ ВЮв ИВЮС+ПТКМИ □ вгсс+дпткм

■ вюс+дпткм1 авюс+ввоя

Рисунок 4 21

На рисунке 5 показано численное сравнение метода СМ11Е8(10) с 3 переобу-славливателями: ДТКМ, ДДТКМ, 55(Ж. На рисунке 6 показано численное сравнение метода ЕНСв с 3 переобуславливателями: ДТКМ, ДДТКМ, ЗБСЖ.

2500 2000

1 задача 2 задача 3 задача 4 задача

■ вМЯЕ^Ю) ■ СМЯЕв(10)+ДТКМ

■ СМРЕ8(10)+ДПТКМ ВСМ(*Е8(Ю)+580Н

Рисунок 5. 3000^--------

2500 2000 1500 1000 500 0

1 задача 2 задача 3 задача 4 задача а виге ■ В)СС+ДТКМ ивюо+дпткм ввюо+ззоя

Рисунок 6.

По результатам данных тестов можно заметить, что все рассматриваемые операторы являться хорошими переобуславливателями для метода СМКЕЗ(Ю), но достаточно слабыми переобуславливателями для метода

вюа

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

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Т.В. Белоконь, Б.Л. Крукиер Эффективные методы решения уравнения конвекции-диффузии с сильно меняющимся полем скоростей. Сборник трудов IX Всероссийская школа семинар «Современные проблемы математического моделирования», Изд. РГУ, Ростов-на-Дону, 2001, стр. 48-53.

2. Субботина Т.Н., Крукиер Б.Л. Решение нестационарного уравнения конвекции-диффузии треугольными кососимметричными схемами V Сборник трудов IX Всероссийской школы-семинара "Современные проблемы математического моделирования" Ростов-на-Дону, 2001, стр. 324334.

3. L.A. Krukier, T.V.Belokon, B.L.Krukier Iterative methods for linear equation systems with dominant skew-symmetric part, Proceedings of International Conference on Computational Mathematics, IMC&MG publisher, Novosibirsk, v.l, 2002,107 - 112.

4. Б.Л. Крукиер Двухпараметрический попеременно-треугольный итерационный метод решения сильно несимметричных систем линейных алгебраических уравнений. Тезисы докладов IX Всероссийского совещания по проблемам построения сеток для решения задач математической физики. Изд. ИПМ РАН, ИПМ УрО РАН, 2002, с 35.

5 Krukier L А , Belokon Т V , Krukier В L Special preconditioned for solution of transport-dominated convection-diffusion problems. MILOVI, 2002, pp.43, Book of abstracts of conference computational linear algebra with applications.

6. L.G. Chikina, B.L. Krukier Solution of linear equation systems with a dominant skew-symmetric part using the product triangular iterative method. Сотр. Methods in Appl. Math, V. 3, №4, 2003, pp.647-650.

7. L.A. Krukier, O.Lapshina, B.L.Krukier Special preconditioners for solution of transport-dominated convection-diffusion problem, PAMM, Proceedings Appl. Math.&Mech., Wiley InterScience publisher, 2003, v.3, №1, 549 -550.

8. L.A. Krukier, O.Lapshina, B.L.Krukier Special preconditioners for solution of transport-dominated convection-diffusion problems Annual Scientific Con-gerence GAMM 2003; Session 22, 2003, pp.234, Book of Abstracts. Abano Terme - Padua.

9. Л.Г. Чикина, Б.Л. Крукиер Двухлараметрический двуциклический итерационный метод решения сильно несимметричных систем линейных алгебраических уравнений. Вычислительные технологии, Новосибирск, Том 9, № 5,2004, стр. 102-113.

10. Б. Л. Крукиер. Оптимизация двухпараметрического двуциклического треугольного итерационного метода с постоянным итерационным параметром в операторах метода. «Сеточные методы для краевых задач и приложения» Материалы 5-го Всероссийского семинара, посвященного 200-летию Казанского ун-та. - Казань: Казанский гос. ун-т. - 2004. стр. 118-121.

11. Б.Л. Крукиер Ускорение метода ДДТКМ и его численное исследование, Сборник трудов X Всероссийской школы-семинара «Современные проблемы математического моделирования», Изд. РГУ, Ростов-на-Дону, 2004, стр. 127-133.

12. Чикина Л.Г., Пичугина О.А., Крукиер Б.Л. Решение сильно несимметричных систем линейных алгебраических уравнений вариационными методами с переобуславливателями специального вида. Сборник трудов Всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики». - Ростов-на-Дону: Издательство РГУ. - 2004. стр. 159-170.

Издательство ООО «ЦВВР» Лицензия ЛР № 65-36 от 05 08 99 г Сдано в набор 23 03 05 г Подписано в печать 23 03 05 г Формат 60*84 1/ 16 Заказ № 584 Бумага офсетная Гарнитура «Тайме» Оперативная печать Тираж 100 экз Печ Лист 1,0. Уел печ л 1,0 Типография- Иугательско-полиграфический комплекс « Биос» РГУ 344091, г Ростов-на-Дону, ул Зорге, 28/2, корп 5 «В», тел (863) 247-80-51 Лицензия на полиграфическую деятельность № 65-125 от 09.02 98 г

РНБ Русский фонд

2005-4 41995

í Ifí

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

введение. i. итерационные методы решения слау.

1.1. НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ МАТРИЦ И ТЕОРИИ ИТЕРАЦИОННЫХ МЕТОДОВ.

1.1.1. Типы матриц и их основные свойства.

1.1.2. Сведения из теории матриц. 1.3. Локализация спектра матриц.

1.1.4. Лемма Келлога.

1.1.5. Основные сведения из теории итерационных методов.

1.1.6. Методы ускорения сходимости.

1.2. КЛАССИЧЕСКИЕ ИТЕРАЦИОННЫЕ МЕТОДЫ (ОБЗОР).

1.2.1. Метод Якоби.

1.2.2. Метод Гаусса-Зейделя.

1.2.3. SOR (метод последовательной верхней релаксации).

1.2.3.1. Модифицированный SOR (modified successive overrelaxation) MSOR.

1.2.3.2. Метод релаксации с ускорением (accelerated overrelaxation) - AOR.

1.2.4. SSOR (симметричныйметод SOR) и USSOR (Несимметричный SOR).

1.2.5. Треугольные методы.

1.2.6. Попеременно-треугольные методы.

1.2.7. LU—разложение.

1.3. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СИЛЬНО НЕСИММЕТРИЧНЫХ СЛАУ.

1.3.1. Вариационные методы.

1.3.2. Кососимметричные итерационные методы (КМ).

1.3.2.1. Треугольные КМ (ТКМ).

1.3.2.2. Попеременно-треугольные КМ (ПТКМ).

1.3.2.3. Двуциклические треугольные КМ (ДТКМ).

1.3.2.4. Численное исследование на модельной задаче.

1.3.3. Методы эрмитова и косоэрмитоваразложения. ii. двухпараметрические кососимметрические треугольные итерационные методы.

II. 1. ДВУХПАРАМЕТРИЧЕСКИЙ ДТКМ.

II. 1.1. Условия сходимости метода.:.

II. 1.2. Нахождение оптимального параметра метода.

11.2. ДВУХПАРАМЕТРИЧЕСКИЙ ПТКМ.

II.2.1. Условия сходимости метода.

И. 2.2. Нахождение оптимального параметра метода.

11.3. УСКОРЕНИЕ ТРЕУГОЛЬНЫХ КОСОСИММЕТРИЧНЫХ МЕТОДОВ.

11.4. ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ НА МОДЕЛЬНОЙ ЗАДАЧЕ. iii. использование кососимметрических итерационных методов для переобуславливания вариационных методов.

III. 1. МЕТОДЫ ПОДПРОСТРАНСТВА КРЫЛОВА.

111.2. ПЕРЕОБУСЛАВЛИВАНИЕ.

111.3. GMRES И ЕГО МОДИФИКАЦИИ.

111.4. BlCG И ЕГО МОДИФИКАЦИИ.

111.5. ПЕРЕОБУСЛАВЛИВАНИЕ GMRES И BlCG.

111.6. ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ НА МОДЕЛЬНОЙ ЗАДАЧЕ. литература.

Введение диссертация по математике, на тему "Двухпараметрические попеременно-треугольные и двуциклические методы решения сильно несимметричных систем линейных алгебраических уравнений"

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

Для решения задач математической физики широко используются методы дискретизации исходных дифференциальных или интегральных уравнений, краевых и начальных условий, которые позволяют преобразовать исходную непрерывную задачу в дискретную, т.е. перейти из бесконечномерного в конечномерное пространство, как правило, достаточно большой размерности. Далее, в этом конечномерном пространстве задачу преобразуют в систему линейных алгебраических уравнений, которую затем надо решить на ЭВМ. Такая технология решения сложных научно-технических задач, описываемых системами интегро-дифференциальных уравнений, краевых и начальных условий была разработана в начале 60-тых годов А.А.Самарским и была названа им вычислительным экспериментом. В данной работе особое внимание уделяется предпоследнему этапу технологии вычислительного эксперимента — решению системы линейных алгебраических уравнений. В соответствии с мировой статистикой 80% задач, решаемых на ЭВМ - это задачи нахождения решения системы линейных алгебраических уравнений (СЛАУ). В работе рассматриваются итерационные методы решения этой задачи, т.к. речь идет о СЛАУ содержащих сотни тысяч неизвестных и уравнений, а прямые методы их решений при таком размере СЛАУ не эффективны. Несмотря на то, что теория итерационных методов в достаточной степени разработана для достаточно большого класса матриц, остаются проблемы по созданию новых эффективных итерационных методов решения СЛАУ для матриц, обладающих достаточно специфическими свойствами. Одним из таких классов матриц являются сильно несимметричные матрицы, которые получаются, например, при центрально-разностной аппроксимации уравнения конвекции-диффузии с малым параметром при старшей производной.

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

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

В соответствии с этими целями решен ряд задач:

• рассмотрены вопросы ускорения двухпараметрических ПТКМ и ДТКМ;

Научная новизна работы определяется полученными теоретическими результатами исследования:

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

• определением (в частных случаях) оптимальных параметров двухпараметрических ПТКМ и ДТКМ;

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

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

1. предложены двухпараметрические итерационные методы решения сильно несимметричных систем: попеременно-треугольный (ПТКМ) и двуцик-лический (ДТКМ) кососимметричные методы;

2. получены достаточные условия сходимости двухпараметрических ПТКМ и ДТКМ;

5. показана эффективность использования этих методов в качестве пере-обуславливателя для методов вариационного типа.

Основные результаты диссертации докладывались на IX и X Всероссийских школах-семинарах молодых ученых «Современные проблемы математического моделирования» (п. Абрау-Дюрсо, 2001г., 2003г.); на 5-ой Всероссийской конференции «Сеточные методы для краевых задач и приложения» (г. Казань, 2004г.); на международной конференции «Математическое моделирование и вычислительный эксперимент в механике и физике» (г. Ростов-на-Дону, 2001г.); на международной конференции IMMC-2002 «Итерационные методы и матричные вычисления» (г. Ростов-на-Дону, 2002г.); IX и X Всероссийские Совещания по проблемам построения сеток для решения задач математической физики (п. Абрау-Дюрсо, 2002г., 2004г.), Всероссийской научно-технической конференции «Параллельные вычисления в задачах математической физики» (Ростов-на-Дону, 2004). Annual Scientific Congerence GAMM 2003; Session 22, 2003, Abano Terme -Padua; Conference computational linear algebra with applications, MILOVI, 2002; International Conference on Computational Mathematics, Novosibirsk, 2002.

По теме диссертации опубликовано 12 печатных работ, из них 4 статьи в российских и зарубежных реферируемых журналах, 6 статей в сборниках трудов и 2 в тезисах докладов российских и международных конференций. В совместных работах автор принимал участие на всех этапах исследования.

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

Ay = f. (1)

Большинство итерационных методов, которые применяются для решения СЛАУ, могут быть объединены общей канонической формулой v"+1 - у"

В/-+ (2) где Вп - операторы метода, А - исходная матрица системы, тп> 0 - последовательность итерационных параметров; у0 - начальное приближение, / - правая часть (1), f, у0 е Н, Н - конечномерное гильбертово пространство, у11 — решение на «-ой итерации, п - номер итерации.

Итерационный метод (2) можно записать в эквивалентном виде z"+I =z"-rn5;1r", где г" = Ау" - f - вектор невязки на п-ой итерации, a z" =у"-у -вектор погрешности (ошибки) этого метода, у — точное решение системы (1).

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

В разделе 1.2. рассматриваются классические итерационные методы: Якоби, Гаусса-Зейделя, последовательной верхней релаксации (SOR), симметричной и несимметричной последовательной верхней релаксации (SSOR и USSOR), треугольные, попеременно-треугольные и методы неполного разложения.

Там же даны определения ^-циклического, стационарного и треугольного (ТМ) (попеременно-треугольным (ПТМ)) итерационных методов.

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

А^Ао+А], А0= (А + АТ)/2=А0Т, А1=(А-Ат)/2 = -А]т Причем для кососимметричной составляющей справедливо следующее разложение

А^Кц+Кь где К1 и Ку строго нижняя и верхняя треугольные части матрицы А], причем

Ки= -К.1 .

Для исследования итерационного метода (2) рассмотрим однородное уравнение для векторов погрешностей

В2м~*к+А2к= 0, ¿ = 0,1,2,.; г0=у0-у, т или в разрешенной относительно форме гк+х = , где в = В~\В-тА) (3) называется оператором перехода итерационного метода (2).

Если оператор перехода С = зависит от итерационного параметра г, то метод (2) будем считать однопараметрическим итерационным методом, если же <7 = О(г,со) зависит не только от г, но и от некоторого второго параметра со, то - двухпараметрическгш. Оператор А называется сильно несимметричным, если в какой либо норме

Л, Л

Для получения условий сходимости итерационного метода (2) надо исследовать его оператор перехода (3) и оценить его спектр р{р) = тах^ (С)| < 1 или его норму ¡|Ст| < 1.

Класс кососимметричных методов был предложен в 1979 году Л.А. Крукие-ром и основан на идеи включения в оператор В итерационного метода (2) треугольных частей Кь или Ки только кососимметрической составляющей А, , т.е.

В = (Вс+2тКь) или В = (Вс+2тКи),где ВС=ВТС.

Теоретическое и численное исследование этого класса методов, выполненное за последние годы, позволило построить сходящиеся методы для СЛАУ с диссипативными сильно несимметричными матрицами. Были получены однопа-раметрические треугольные (ТКМ), попеременно треугольные (ПТКМ) и дву-циклические (ДТКМ) кососимметрические итерационные методы решения для сильно несимметричных диссипативных2 матриц.

Отметим, что основное свойство этого класса методов состоит в том, что ко-сосимметричная составляющая оператора метода пропорциональна кососиммет-ричной составляющей оператора системы, причем:

Вх = тАх.

Исследования были проведены в энергетической норме + В*^> 0.

Оператор перехода ТКМ в этой норме имеет вид

0(т) = {Е + тРх)~\Е + тР,;), где р0=в-^в-^2=р; > о, рх=в-х'2 ах12 = -р; • 2

Оператор А называется диссипативиым, если для любого вектора X Ф 0 его симметричная часть положительно определена ( Ах,х) = > 0.

Т.к. норма оператора (Е + тРх) <1, а оператор Е + тР0 симметричен, то исследование оператора Е + тР0 дало достаточное условие сходимости ТКМ (ПТКМ, ДТКМ) в виде В0 > 0,5 тА0.

Во второй главе представлены основные теоретические и численные результаты.

Энергетический подход позволил доказать достаточные условия сходимости в норме = В0- 0,5а>А0 ^(г,^)^ <1|, отличной от рассмотренной ранее. Вначале достаточные условия сходимости методов даны, без каких либо ограничений на свойства невырожденного оператора системы А, а затем в следствиях они приведены для случая диссипативного оператора системы (1).

В разделе 11.1. и 11.2 и их подразделах рассмотрен энергетический подход исследования ДТКМ (т,со) и ПТКМ (т,со), доказаны теоремы сходимости и следствия к ним. В частных случаях доказаны теоремы о нахождении оптимального параметра методов.

Двухпараметрический ДТКМ имеет вид уИ+1 - V"*1'2

Diag[BL ) + соКь ) —-£-+Ауп*т =/,

Т (4) л+1/2 п V >

Diag [Ви) + соКи^——-——+Ау" = / где В, =(Diag(BL) + й)KL)- оператор первого цикла, Ви = (Diag(Ви) + соКи)~ оператор второго цикла. Оператор перехода метода (4) имеет следующий вид

С = в;1 (Вь -тА)В~; (Ви -тА) = ед,

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

GL = z J \

Nlo Vlrr^ = Blo ~тл =

Требование положительной определенности оператора N^>0, позволяет получить оператор перехода в виде

Gl = Nil Gl Nil, где

4-1

E+-PL

X-2 h

-i p AN'1 rL LO LO т.е. исследование сходимости метода проводится в энергетической норме Аналогичные преобразования производятся и для оператора Си. Тогда для сходимости метода достаточно, чтобы fJ'iQ ДГ2 IyL0 "L -iViO

N~* G N* lyU0 и lyU0

А это в свою очередь означает, что достаточно потребовать Двухпараметрический ПТКМ имеет вид

Л)П+1 п

Вс+аК^Вс+аК,,)*--^-Ау" = / .

Оператор перехода метода (5) имеет следующий вид в = В~х(В-гА), (6) где

В = {ВС+ аКь )В~1 (Вс +(оКи). Сделав достаточно простые преобразования в (6), получаем

Далее потребовав положительную определенность оператора N¿>0, получаем оператор перехода в виде 0 = где д = (Е + соР)~,(Е-(т-(о)Р),Р = ^*А^11.

Т.к. оператор С подобен оператору С, то исследование сходимости метода будем проводить в энергетической норме , т.е. для сходимости метода достаточно потребовать ЦбЦ =

Доказаны достаточное условие сходимости двухпараметрических ДТКМ и ПТКМ. В приведенных следствиях из этих теорем эти достаточные условия упрощены для класса диссипативных матриц

Для нахождении оптимального параметра, при условиях, что операторы методов не зависят от параметра релаксации, т.е.со=сот^0 или операторы методов содержит параметр, пропорциональный параметру релаксации, т.е. со = кт доказаны теоремы, дающие значения этих оптимальных параметров.

В разделе И.З. рассмотрены возможности ускорения сходимости предложенных методов, на примере двухпараметрического ДТКМ.

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

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

Хо = Diag(Вь) + 0,5со(К1+К1)-0,5соА^ > О = (Ви)-0,5а>[К1+ К{ )-0,5й)Ло>0

Так как матрицы Ы10 и Ыио симметричны, их собственные числа действительны, то по теореме Гершгорина, для положительной определенности операторов и Ыио достаточно выполнения следующих условий:

Ко1>0,

М/о}й>0, причем хотя бы для одной строки в каждой системе неравенство должно быть строгим.

Тогда, очевидно, что если в качестве диагоналей операторов метода взять следующие выражения: где Д, ={4,1 = К10 + Ки0, то они обеспечат выполнения условий положительной определенности операторов Ы10 и Ыио, тем самым дадут сходимость двухпараметрического ДТКМ с диссипативным исходным оператором, сохраняя при этом в операторах Вь и Ви информацию об изменениях в строках и столбцах исходной матрицы. Кроме того, построение диагоналей матриц Вь и Ви не требует существенных вычислительных затрат, что не снижает эффективность метода.

В разделе 11.4. приведены численные результаты тестирования рассмотренных методов и их сравнения с классическими методами.

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

Правая часть f и краевые условия выбирались таким образом, чтобы аналитическим решением задачи была гладкая функция и{х,у)=ехувт{71х)ът{71у).

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

ДС/ + -Ре /(х,у), и \дП~ Олась центральными разностями, получается система линейных алгебраических уравнений с диссипативной пятидиагональной матрицей А.

Поле скоростей подобранно таким образом, чтобы удовлетворить условие несжимаемости среды, т.е. Div(V)=0, V=fv/,v2}

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

В главе III рассмотрены вариационные методы BiCG и GMRES(m), которые использовались для решения модельной задачи как самостоятельно, так и с пере-обуславливанием, где в качестве переобуславливателей использовались двухпа-раметрические ПТКМ и ДТКМ. Для оценки эффективности такого подхода, полученные численные результаты сравнивались с аналогичными результатами для «классического» переобуславливателя, которым является SSOR. Для улучшения сходимости вариационных методов предлагалась технология левого переобу-славливания.

По результатам данных тестов можно заметить, что все рассматриваемые операторы являться хорошими переобуславливателями для метода GMRES(IO), но достаточно слабыми переобуславливателями для метода BiCG.

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

I. ИТЕРАЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Крукиер, Борис Львович, Москва

1. Андерсон Д., Таннехил Дж., Плетчер Р. Вычислительная гидромеханика и теплообмен: В 2-х т. М: Мир, 1990

2. Булеев Н.И. Пространственная модель турбулентного обмена. М.: Наука, 1989.

3. Вабищевич П.Н. Итерационные методы решения задач конвекции-диффузии.// Труды Международной летней школы молодых ученых "Итерационные методы и матричные вычисления". Ростов-на-Дону: Изд-во РГУ, 2002, стр. 328-367.

4. Воеводин В.В. Линейная алгебра. М: Наука, 1980

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

6. Г.И. Шишкин Г.И. Сеточная аппроксимация сингулярно возмущенных уравнений с конвективными членами в случае смешанных краевых условий.// Дифференциальные уравнения, 1996, 32 (5), 689-701.

7. Гантмахер Ф.Р. Теория матриц, М: Наука, 1966

8. Голуб Дж., Ван Лоун Ч. Матричные вычисления, Москва: Мир, 1999

9. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения, М: Мир, 2001

10. Еремин А.Ю., Капорин И.Е. Реализация явных чебышевских методов при решении задач большой размерности. в кн. Многопроцессорные вычислительные структуры, Таганрог, ТРТИ, 1985, вып.7, стр. 43-46

11. Капорин И.Е. О предобуславливании и распараллеливании метода сопряженных градиентов. в кн. Ортега Дж. "Введение в параллельные и векторные методы решения линейных систем". Москва: Мир, 1991, стр. 180-190

12. Крукиер Л.А, Чикина Л.Г. Кососимметрические итерационные методы решения стационарных задач конвекции-диффузии.// Изв. ВУЗов, Матем., 2000. №11.- с.62-76.

13. Крукиер Л.А. Достаточное условие сходимости треугольного итерационного метода с несамосопряженным исходным оператором.// Изв. СКНЦ ВИТ. Ест. Науки, 1989, №4, стр. 52-54

14. Крукиер Л.А. Кососимметричные итерационные методы решения стационарной задачи конвекции-диффузии с малым параметром при старшей производной.//Изв. ВУЗов. Математика, 1997, №4, стр.77-85.

15. Крукиер Л.А. Мартынова Т.С. О влиянии формы записи уравнения конвек-ции-дифузии на сходимость метода верхней релаксации.// ЖВМиМФ, т. 39, №11, 1999, стр. 1821-1827

16. Крукиер Л.А. Неявные разностные схемы и итерационный метод их решения для одного класс систем квазилинейных уравнений.// Изв. Вузов. Математика, 1979, №7, стр. 41-52

17. Крукиер Л.А. Математическое моделирование гидродинамики Азовского моря при реализации проектов реконструкции его экосистемы// Матем. мо-дел. 1991. - Т.З. -№9. - С.3-20.

18. Крукиер Л.А. Решение сильно несимметричных систем линейных алгебраических уравнений итерационным методом, основанным на кососимметрич-ной части исходной положительной матрицы.// Математическое моделирование, том13, №3, 2001, стр. 49-56

19. Крукиер Л.А., Бочев М.А. Об итерационном решении сильно несимметричных систем линейных алгебраических уравнений.// ЖВМ и МФ, т. 37, №11, 1997, стр. 1283-1293

20. Крукиер Л.А., Чикина Л.Г. Двуциклический треугольный кососимметриче-ский итерационный метод решения сильно несимметричных систем.// Известия высших учебных заведений. Математика, №5, 2001, стр. 36-42

21. Крукиер Б. Л. Ускорение метода ДДТКМ и его численное исследование, Сборник трудов X Всероссийской школы-семинара «Современные проблемы математического моделирования», Изд. РГУ, Ростов-на-Дону, 2004, стр. 127-133

22. Лебедев В.И. Финогенов С.А. О порядке выбора итерационных параметров в чебышевском циклическом итерационном методе.// ЖВМ и МФ, 1971, т. 11, №2

23. Лойцянский Л.Г. Механика жидкости и газа. М: Наука, 1970.

24. Маркус М., Минк X. Обзор по теории матриц и матричным неравенствам. М.: Наука, 1972.

25. Марчук Г.И. Методы вычислительной математики. Новосибирск: Наука, 1973

26. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. Москва: Мир, 1991

27. Роуч П. Вычислительная гидродинамика. М.: Мир, 1980

28. Самарский A.A. О регуляризации разностных схем //ЖВМ и МФ, -1967. -Т.7. -№1. С.62-93.

29. Самарский A.A. Введение в теорию разностных схем, М: Наука, 1971

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

31. Самарский A.A. Николаев Е.С. Методы решения сеточных уравнений М: Наука, 1978

32. Самарский A.A. Теория разностных схем М: Наука, 1977

33. Самарский A.A., Вабищевич П.Н. Численные методы решения задач конвекции-диффузии. Изд. УРСС, Москва, 1998

34. Самарский A.A., Вабищевич П.Н., Матус П.П. Разностные схемы с операторными множителями, Минск, 1998

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

36. Тартышников Е.Е. Краткий курс численного анализа, Москва: ВИНИТИ, 1994

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

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

39. Хорн Р. Джонсон Ч. Матричный анализ. Москва: Мир, 1989

40. Чикина Л.Г. Об одном методе решения уравнения конвекции-диффузии с преобладающей конвекцией.// Математическое моделирование, 1997, т. 9, № 2, стр. 20-25.

41. Чикина Л.Г., Крукиер Б.Л. Двухпараметрический двуциклический итерационный метод решения сильно несимметричных систем линейных алгебраических уравнений. Вычислительные технологии, Новосибирск, Том 9, № 5, 2004, стр. 102-113

42. Arnoldi W.E. The principle of minimized iteration in the solution of the matrix eigenproblem.// Quart. Appl. Math., 1951, №9, p. 17-29

43. Axelsson O. A generalized SSOR method.// BIT, 1972, 12, p. 443-467

44. Axelsson O. Iterative solution Methods. Cambridge University Press, Cambridge, 1994

45. Axelsson O., Vasilevski P.S. A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning.// SIAM J. Matrix Analysis and Applications, 1991, №12, p.625-644

46. Bai Z.Z., Golub G., Ng M. Hermitian and Skew-Hermitian splitting methods for non-Hermitian positive definite systems, SIAM J.Matrix Anal.Appl., 24, 2003, pp.603-626

47. Barrett R., Berry M., Chan T.F., Demmel J., Donato J., Dongarra J., Eijkhout V., Pozo R., Romine C., and Van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, PA, 1994

48. Buleev N.I. A numerical method for solution of two-dimensional and three -dimensional equations of diffusion.// Math. Sb., 1960, №51, p. 227-238

49. Chan T.F., Galloloulos E., Simoncini V., Szeto Т., Tong C.H. A quasi-minimal residual variant of the BiCGSTAB algorithm for nonsymmetric systems.// SIAM J. Sci. Statist. Comput., 1994, №15, p. 338-347

50. Chikina L.G., Krukier B.L. Solution of linear equation systems with a dominant skew-symmetric part using the product triangular iterative method. Сотр. Methods in Appl. Math, V. 3, №4, 2003, pp.647-650

51. D'Sylva E., Miles G.A. The SSOR iteration scheme for equations with cf- order-ings.// Computer J., 1963, №6, p.271-273

52. DeLong M. SOR as preconditioner, Doctor of Philosophy (Computer Science) Dissertation, University of Virginia, 1997

53. Dongarra Jack., J. Duff Iain., S. Sorensen Danny C., Van der Vorst H. Numerical Linear Algebra for high-performance computers. SIAM, Philadelphia, 1998

54. Elman H.C. Relaxed and stabilized incomplete factorizations for nonselfadjoint linear systems, BIT, 29(4), 1989, p.890-915

55. Elman H.C. A stability analysis of incomplete LU factorization.// Math. Comp., 1986, №47, p. 191-217

56. Fisher B., Ramage A., Silvester D.J., Wathen A.J. Towards parameter-free streamline upwinding for advection-diffusion problems, Strathclyde Mathematics Research Report, №37 (1996)

57. Fletcher R. Conjugate gradient methods for indefinite systems.// G.A. Watson (Ed.), Proceedings of the Dundee Biennal Conference on Numerical analysis, Springer, New York, 1975,p.73-89

58. Frankel S.P. Convergence Rates of Iterative Treatment of Partial Differential equation, //Math. Tables Aids Comp., 1950, v.4, p.66-75

59. Freund R.W., Nachtigal N.M. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices.// Technical Report 90.46, Part2, RIACS, NASA Ames Center, 1990

60. Golub G.H., Van der Vorst H. A. Closer to the solution: Iterative linear solvers.// in I.S. Duff and G.A.Watson (eds), The State of the Art in Numerical Analysis, Clarendon Press, Oxford, 1997, p. 63-92

61. Golub G.H., Varga R.S. Chebychev semi-iterative methods, successive overrelaxation iterative methods and second order Richardson iterative methods.// Part I, Numer. Math., 1961, V.3, p. 147-156

62. Golub G.H., Varga R.S. Chebychev semi-iterative methods, successive overrelaxation iterative methods and second order Richardson iterative methods.// Part II, Numer. Math, 1961, V.3, p. 157-166

63. Golub Gene, Van Loan Ch. Matrix Computations, Oxford, North Oxford Academic Publishing, 1983

64. Golub G, Vanderstraeten D. On the preconditioning of matrices with a dominant skew-symmetric component, Numer. Algorithms, 25, 2000, pp223-239

65. Greenbaum A. Iterative methods for solving Linear Systems. SIAM, Philadelphia, PA, 1997

66. Grote M, Huckle T. Parallel preconditioning with sparse approximate inverses.// SIAM J. Sci. Comput., 1997, №18, p. 838-853

67. Hadjidimos A. A survey of the iterative methods for the solution of linear systems by extrapolation, relaxation and other techniques.// J. Comput. Appl. Maths, 1987, №20, p. 37-51

68. Hadjidimos A. Accelerated Overrelaxation method.// Math. Comp, 1978, №32, p. 149-157

69. Hadjidimos A, Psirmani A, Yeyios A.K. On the convergence of the modified accelerated overrelaxation method (MAOR).// Applied Numerical Math, 1992, №10, p. 115-127

70. Hadjidimos A, Yeyios A.K. Symmetric accelerated overrelaxation method (SAOR).// Math. Comput. Simulation, 1982, №24, p. 72-76

71. Kaporin. I.E. Explicitly preconditioned conjugate gradient method for the solution of unsymmetric linear systems, Int.J.Comp. Math., 40, 1992, p. 169-187

72. Kaporin. I.E. High quality preconditioning of a general symmetric positive matrix based on its UTU + UTR + RTU-decomposition.- Numer. Linear Algebra Appls., N 1, 1999.

73. Kaporin I.E., A practical algorithm for faster matrix multiplication, Numerical Linear Algebra Appl., 1999, v.6, 687-700.

74. Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method, Numer. Linear Algebra with Appls., v.l, N 2, 1994, pp. 179-210.

75. Karamzin Yu. N. Zakharova I.G. On new additive difference method for parabolic equations, Math. Mod. Meth. Appl. Science., 6 (1996), pp. 353-363.

76. Kototilina L. Yu., Yeremin A. Yu. Block SSOR preconditionings for high order 3D FE systems.// BIT., 1989, v. 29, №4, p. 805-823

77. Kototilina L. Yu., Yeremin A. Yu. Factorized sparse approximate inverse preconditionings.// SIAM J. Matrix Analysis and Applications, 1993, №14, p. 45-58

78. Krukier L.A., Chikina L.G., Belokon T.V. Triangular skew-symmetric iterative solvers for strongly nonsymmetric positive real linear system of equations.// Applied Numerical Mathematics, 2002, №41, p. 89-105

79. Krukier L.A., Convergence acceleration of triangular iterative methods based on the skew-symmetric part of the matrix.// Applied Numer. Math., 1999, v.30, N3-4, p.281-290

80. Krukier L.A., Lapshina O., Krukier B.L. Special preconditioners for solution of transport-dominated convection-diffusion problem, PAMM, Proceedings Appl. Math.&Mech., Wiley InterScience publisher, 2003, v.3, №1, 549 550.

81. Krukier L.A., Lapshina O., Krukier B.L. Special preconditioners for solution of transport-dominated convection-diffusion problems Annual Scientific Conger-ence GAMM 2003; Session 22, 2003, pp.234, Book of Abstracts. Abano Terme -Padua

82. Kuznetsov Y.A. Matrix Iterative Methods in subspace.// Proceedings of the International Congress of Mathematicians, Warszawa, August 16-24, 1983, North Holland, Amsterdam

83. Lanczos C. Chebyshev polynomials in the solution of large-scale linear systems.// Toronto Symposium on Computing Techniques, 1952, p. 124-133

84. Lynn M.S. On the equivalence of SOR, SSOR and USOR as applied to a- ordered systems of linear equations.// Computer J., 1964, №7, p.72-75

85. Manteuffel T.A. Adaptive procedure for estimating parameters for the nonsym-metric Tchebychev iteration.//Numerical Math., 1978, v. 31, p 183-208

86. Manteuffel T.A. An incomplete factorization technique for positive definite linear systems.// Math Comp., 1980, V. 34, p. 473-497

87. Manteuffel T.A. The Tchebychev iteration for nonsymmetric linear systems.// Numerical Math., 1977, v. 28, p. 307-327

88. McDowell Variable Successive Overrelaxation.// Report №244, Dept. Computer Sciences, University of Illinois, Utbana.

89. Meijerink J.A., Van Der Vorst H.A. An iterative solution method for linear systems of which the coefficient matrix is symmetric M-matrix.// Math. Comp., 1977, №31(137), p. 148-162

90. Meurant G. Computer solution for large linear systems. Elsevier Science B.V., 1999

91. Morton K.W. Numerical solution of convection-diffusion problems. Chap-man&Hall, 1996

92. Nachtigal N. A look-ahead variant of the Lanczos algorithm and its application in quasi-minimal residual method for non-Hermitian linear systems, Ph. D. Dissertation, Massachusetts Institute of Technology, Cambridge MA, 1991

93. Paige C.C., Saunders M.A. Solution of sparse indefinite systems of linear equations.// SIAM J. Numerical Anal., 1975, №12, p. 617-629

94. Parlett B.N., Taylor D.R., Lin Z.A. A look-ahead Lanczos algorithm for unsym-metric matrices.// Math. Comp., 1985, №44, p. 105-124

95. Raithby G.L., Skew upstream differencing schemes for problems involving fluid flow // Comput neths. Appl. Mech. Engrg., 1976. V.9. - P. 153-164

96. Russell D.B. On obtaining Solutions to Navier-Stokes equations with automatic digital computers.// Aeronautical research council report R&M 3331 Engineering Laboratory, Oxford, 1963

97. Saad Y. A flexible inner-outer preconditioned GMRES algorithm.// SIAM J. Scientific Computing., 1993, №14, p. 461-469

98. Saad Y. Iterative methods for Sparse Linear Systems. PWS Publishing Company, 1995

99. Saad Y., Schultz M.H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems.// SIAM J. Scientific and Statistical Computing., 1986, p. 856-869

100. Saad Y., Van der Vorst H. A. Iterative solution of linear systems in the 20th century.// J. of Computanional and Applied Mathemetics , Elsevier Science, 2000, №123, p. 1-33

101. Sonnoveld P. CGS: a fast Lanzos-type solver for nonsymmetric linear systems.// SIAM J. Sci. Statist. Comput., 1989, №10, p. 36-52

102. Sturler E. De Truncation strategies for optimal Krylov subspace methods.// SIAM J. Numerical Anal., 1999, v. 36, №3. p. 864-889

103. Taussky O. Positive-definite matrices and their role in the study of the characteristic roots of general matrices.//Adv. Math., 1968, v.2, p. 175-186

104. Taylor P.J. A generalization of Systematic Relaxation methods for consistently ordered matrices.// Num. Math., 1969, №13, p. 377-395

105. Van der Vorst H.A. Bi-CGSTAB: a fast and smoothly converging variant if Bi-CG for the solution of non-symmetric linear systems.// SIAM J. Sei. Statist. Comput., 1992, №3, p. 631-644

106. Van der Vorst H.A. Krylov Subspace Iteration.// Computing in Science and Engineering, Vol. 2(1) January/February 2000, p. 32-37

107. Van Der Vorst H.A. Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE problems.// J. Comput. Phys., 1981, №44, p. 1-19

108. Van der Vorst, H.A. Vuik C. GMRESR: a family of nested GMRES methods.// Numerical linear Algebra with Applications, 1994, №1, p. 369-386

109. Varga R.S. Factorization and normalized iterative methods.// R.E. Langer (Ed), Boundary Problems in Differential equation, University of Wisconsin Press, Madison, 1960, p.121-142

110. Varga R.S. Matrix iterative analysis, Aprentice-Hall, Englewood Cliffs, NJ, 1962

111. Varga R.S., Eiermann M., Niethammer W. Acceleration of Relaxation Methods for Non-Hermitian linear systems.// SIAM J. Matrix Anal. Appl., 1991, №13, p. 979-991

112. Wang C-L, Bai Z-Z. Sufficient conditions for the convergent splittings of non-Hermitian positive definite matrices, Linear Alg. Appl. 330, 2001, 215-218

113. Wang C-L, Bai Z-Z Skew-Hermitian triangular splitting iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, BIT Numerical Mathematics, 44, 2004, pp.363-386

114. Weiss R. Parameter-Free linear solvers, Berlin: Akademie Verlag, 1996

115. Woznicki Z.I. Matrix splitting principles.// International Journal of mathematics and mathematical sciences, № 28(5), 2001, p.251-284

116. Woznicki Z.I. Nonnegative splitting theory.// Japan Journal of industrial and applied mathematics, 1994, V. 11, №2, p. 289-342

117. Woznicki Z.I. The sigma-SOR algorithm and the optimal strategy for the illustration of the SOR iterative method.// Math. Comp., 62, 1994, p. 619-644

118. Young D.M. Iterative methods for solving partial differential equations of elliptic type, Doctoral Thesis, Harvard University, Cambridge, MA, 1950

119. Young D.M. Iterative solution of large linear iterative systems.// Academic Press, New York, 1971

120. Young D.M. On accelerated SSOR method for solving large linear systems.// Advances in Mathematic, V.23, 1977, p.215-271

121. Zhang J. Preconditioned iterative methods and finite difference schemes for con-vection-diffiision.// Applied mathematics and computation, 109(2000) p. 11-30