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

• Автор: Крукиер, Борис Львович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 156 с. : 11 ил.

ВВЕДЕНИЕ

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

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

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

1.1.2. Сведения из теории матриц

1.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)
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. Методы эрмитова и косоэрмитова разложения
И. ДВУХПАРАМЕТРИЧЕСКИЕ КОСОСИММЕТРИЧЕСКИЕ ТРЕУГОЛЬНЫЕ ИТЕРАЦИОННЫЕ МЕТОДЫ
11.1. Двухпараметрический ПТКМ
11.1.1. Условия сходимости ПТКМ (Энергетический подход)
П. 1.2. Нахождение оптимального параметра метода (Энергетический подход)
11.1.3. Условия сходимости метода (Спектральный подход)
11.1.4. Нахождение оптимального параметра метода (Спектральный подход)
11.2. ДВУХПАРЛМЕТРИЧЕСКИЙ ДТКМ
11.2.1. Условия сходимости метода
11.3. УСКОРЕНИЕ ТРЕУГОЛЬНЫХ КОСОСИММЕТРИЧНЫХ МЕТОДОВ
11.4. ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ НА МОДЕЛЬНОЙ ЗАДАЧЕ
III. ИСПОЛЬЗОВАНИЕ КОСОСИММЕТРИЧЕСКИХ ИТЕРАЦИОННЫХ МЕТОДОВ ДЛЯ ПЕРЕОБУСЛАВЛИВАНИЯ ВАРИАЦИОННЫХ МЕТОДОВ
111.1. Методы подпространства Крылова
111.2. Переобуславливание
111.3. GMRES И ЕГО МОДИФИКАЦИИ
111.4. BlCG И ЕГО МОДИФИКАЦИИ
111.5. Переобуславливание GMRES и BiCG
IH.6. Численное исследование на модельной задаче
ЛИТЕРАТУРА

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

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

сцЛ = {D~ °hL)1 dias{Eni,0J2Eni )/;
E ,E - единичные матрицы порядка Dx, D, соответственно.
В этом случае основное соотношение для собственных чисел /л и Я спектров операторов c(j2) и ) соответственно имеют вид:
(Я + а>1-1 )(Я + а>2 -1) = соха>г(лгЛ, и при этом уменьшается классическая оценка Янга, данная для случая <ц - со2
Для некоторых случаев были получены оптимальные параметры. Было показано, что метод MSOR при оптимальных параметрах сходится намного быстрее, чем SOR при оптимальном параметре, причем сходимость имеет место даже для задач, при которых метод SOR расходится [121].
1.2.3.2. Метод релаксации с ускорением (accelerated overrelaxation)
Рассматривается итерационный процесс следующего вида:
Хт+1 = ТсоХт + Сс» ГДе Тсо = (1 ~ = 0Х »
что приводит к появлению экстраполяционного варианта метода. С использованием такого подхода был предложен двухпараметрический экстраполяционный вариант метода SOR [75]:
Xm+1 — г,соХт гСг,т ’ ГДС
={D-rL)~ 1 -co)D + (со r)L + coU], дгсо = co(D-rLjX f.
Данный метод можно рассматривать как более общий случай экстраполяционного метода Якоби (г -0) с экстраполяционным параметром со, или как экстраполяционный метод SOR (г Ф 0) с экстраполяционным параметром со/г и релаксационным параметром г
Позднее были предложены другие варианты ускорения метода SOR, сочетающие в себе одновременно несколько подходов к ускорению метода [74,76,77].
Другой подход к ускорению стационарных итерационных методов состоит в выборе нестационарных итерационных параметров.