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

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

Фомина Любовь Николаевна

004697746

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

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

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

-2 СЕН 2010

Томск-2010

004607746

Работа выполнена на кафедре вычислительной математики ГОУ ВПО «Кемеровский государственный университет»

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

Фомин Александр Аркадьевич

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

профессор

Старченко Александр Васильевич

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

профессор

Бубенчиков Алексей Михайлович

кандидат физико-математических наук, научный сотрудник Балаганский Максим Юрьевич

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН, г. Новосибирск

Защита диссертации состоится 23 сентября 2010 г. в 10:30 на заседании диссертационного совета Д 212.267.08 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 36, 2-й учебный корпус, ауд. 102.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 2 августа 2010 г.

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

А.В. Скворцов

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

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

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

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

A.A. Самарского и П.Н. Вабшцевича, Г.И. Марчука, Н.С. Бахвалова,

B. Вазова и Дж. Форсайта, В.П. Ильина, Д. Янга, Ю.А. Кузнецова, Е. Вашпресса, Ю. Саада, Дж. Ортега и многих других. На смену широко распространенным в 50-70-е годы прошлого столетия методам Якоби, Га-усса-Зейделя, различным вариантам метода последовательной верхней релаксации и их блочным модификациям, а также методам переменных направлений и дробных шагов (Д. Писмэн и X. Рэчфорд, H.H. Яненко, М. Лиз, Г.И. Марчук, Дж. Дуглас) пришли итерационные градиентные методы (О. Аксельссон, Г. Голуб, Х.А. ван дер Ворст, В.П. Ильин, Ю. Саад, Р. Вайс, Ю.Н. Захаров, Р. Фройнд), восходящие к пионерским работам

Л.В. Канторовича, М.А. Красносельского, В.М. Фридмана, Г. Темпле, М. Хестенса и Е. Штифеля, В. Арнольда, К. Ланцоша.

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

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

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

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

Основные задачи исследования состоят в следующем:

1. Разработка, обоснование и исследование эффективности неявного итерационного полинейного рекуррентного метода решения СЛАУ с пяти-диагональной матрицей положительного типа с применением ЭВМ.

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

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

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

решения на текущем итерационном слое сводить к минимуму влияние приближения решения с предыдущего итерационного слоя.

2. На основе неявного итерационного полинейного рекуррентного метода разработано четыре алгоритма (ЬЮ, Ы12, ЬКэ, ЬКг), позволяющих более эффективно строить решение разностных эллиптических СЛАУ с пя-тидиагональными матрицами положительного типа по сравнению с лучшими представителями современных методов решения подобных СЛАУ. Для каждого из алгоритмов получена простая полуэмпирическая оценка постоянного оптимального параметра компенсации. Теоретически показана корректность алгоритмов 1Л11 и Ы12 в случае сходимости решения.

3. Исследована применимость в алгоритмах ЬШ, 1Л12, ЬЛб и ЬЯг технологии автоматизации определения переменного оптимального параметра компенсации В.Г. Зверева.

4. По результатам решения типичных тестовых и модельных задач проанализированы основные характеристики алгоритмов ЬЮ, ЬК2, ЬКб и

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

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

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

2. Четыре алгоритма (ЬЮ, ЬЫ2, ЬЯб, ЬЯг), разработанные на основе неявного итерационного полинейного рекуррентного метода, для решения разностных эллиптических СЛАУ с пятидиагональными матрицами положительного типа и полученные для каждого из них простые полуэмпирические оценки постоянного оптимального параметра компенсации, а также теоретическое обоснование корректности алгоритмов 1Л11 и Ы12 в случае сходимости решения.

3. Результаты применимости в алгоритмах 1Л1, Ы12, ЬЯб и ЬЯг технологии автоматизации определения переменного оптимального параметра компенсации В.Г. Зверева.

4. Анализ основных характеристик алгоритмов 11111, 1Л12, ЬЯб и ЬЯз: времени исполнения, средней скорости сходимости, вычислительной устойчивости - в зависимости от сеточного разбиения области (размерности матрицы), вида решаемого уравнения и типа граничных условий задачи, а также величины итерационного параметра компенсации.

Достоверность полученных результатов следует:

• из корректной математической постановки задач как дифференциальной, так и разностной;

• из сравнения с аналитическими решениями при тестовых расчетах;

• из постоянного контроля параметров сходимости в процессе построения итерационного решения предложенными алгоритмами: нормы невязки, нормы погрешности, средней скорости сходимости.

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

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

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

Апробирование. Основные результаты диссертации доложены на 7 конференциях и опубликованы в 9 работах, в том числе две работы - в журналах из списка ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Объем диссертации составляет 187 страниц, работа содержит 22 таблицы и 92 рисунка. Список цитируемой литературы включает 108 наименований.

Краткое содержание работы

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

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

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

приводятся вычислительные формулы и теоретически обосновывается корректность первых двух алгоритмов 1Л11 и ЬЙ2.

Пусть определена некоторая краевая задача тепло- или массопереноса в двумерной прямоугольной области С1={(х,у)\ 0< х <1^, 0< у 1у). Внутри области О поведение искомой функции Ф(х,у) описывается обобщенным дифференциальньш уравнением

где Vх, V1' - коэффициенты при старших производных, 5 - источник. А на границе области Г имеют место граничные условия третьего рода

атФ'п+ЬгФ = сг, (2)

где аг, 6Г, сг - известные величины, а п - нормаль к границе.

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

Рисунок 1 - Структуры исходной и полностью преобразованной матриц

СЛАУ

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

В общем виде неявный итерационный полинейный рекуррентный метод может быть представлен следующими шагами:

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

преобразования матрицы и фрагмент соответствующей структуры матрицы

2. Нетрудно видеть, что подсистема уравнений на шаблонах

2 < / < п, 1 á j < т по причине наличия уравнений, соответствующих шаблонам «граничного» типа на линии i = 2, и уравнений, соответствующих действительно граничным шаблонам на линиях i = п (при 1 < j < т) и j=\,j = m (при 2 < ; < я), замкнута и, следовательно, может быть решена.

3. Последовательное применение вдоль оси х п.1 излагаемого алгоритма (п- 2) раза (увеличением индекса г, прямой ход) позволяет получать преобразованные СЛАУ с последовательно выделяемой замкнутой подсистемой все меньшей размерности (подсистема 2, подсистема 3, ...). Необходимо заметить, что рекуррентная воспроизводимость уравнений, соответствующих «граничным» четырех- и трехточечным шаблонам вдоль линий i = const, послужила основой названию рассматриваемого метода.

4. Последнее применение предлагаемой процедуры линейных преобразований к уравнениям на сеточных линиях п - 1 и п (рисунок 3) позволяет получить замкнутую подсистему трехточечных по j уравнений вдоль сеточной линии i = п. Трехточечная структура этой подсистемы обусловлена естественным усечением исходных разностных уравнений на границе области x-Lx. Решается эта подсистема методом трехточечной скалярной прогонки, и тем самым определяются компоненты подвектора решения Ф„j, j = \,т на правой границе области.

5. Подстановка подвектора = в предпоследнюю подсистему (рисунок 3, подсистема п - 1) позволяет получить замкнутую, в общем случае, трехточечную систему уравнений на массиве индексов (; = и-1, 1 < } < т), которая снова решается методом скалярной прогонки и так далее (уменьшение индекса обратный ход). Процедура обратного хода вдоль оси х повторяется (п - 1) раз, что позволяет найти оставшиеся компоненты искомого вектора решения.

Рисунок 3 - Замыкание полинейного рекуррентного преобразования разностных шаблонов на правой границе расчетной области

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

Предполагаемая в п.1 процедура линейных преобразований представляет собой поэтапную последовательность линейных комбинаций исходных уравнений, в которой только один этап является приближенным, а все остальные этапы - эквивалентными преобразованиями. Благодаря этому приближенному этапу метод представляет собой итерационный процесс. При этом в качестве одной итерации считается сумма поочередных проходов вдоль глобального направления х, а затем вдоль глобального направления у. Следует заметить, что алгоритмы ЬЮ, 1Л12, ГЛя и ЬКг неявного итерационного полинейного рекуррентного метода различаются между собой содержанием этапа приближенных преобразований. Все остальные преобразования всех алгоритмов неявного итерационного полинейного рекуррентного метода совпадают между собой.

Суть этапа приближенных преобразований состоит в том, чтобы выразить компонент искомого вектора решения в так называемом «внешаблон-ном» узле через компоненты вектора решения в соседних узлах разностной сетки. Делается это с помощью экстраполяционной формулы, записанной относительно приращения решения ДФ*+1 = Ф*+1 -Ф,у, здесь к- номер итерации. Например, в случае линейной экстраполяции формула имеет вид

у- .1 : '...4. .

\

подсистема п

ф^1 = ф' +е[2 (ф$ -ф'+1)-(ф$ - ф*+3)], (3)

где 6 - итерационный параметр компенсации, причем 0 < 0 < 1, поскольку нетрудно показать, что использование (3) в конечном счете приводит к результату, математически идентичному использованию принципа обобщенной компенсации Булеева-Ильина на классе линейных пробных векторов. Алгоритм неявного итерационного полинейного рекуррентного метода с экстраполяционной формулой (3) назван 1Л11.

Второй алгоритм (Ы12) получается, если вместо формулы линейной экстраполяции (3) использовать формулу квадратичной экстраполяции

ф<+1=Ф< +е ¡з[(Ф*;1 ■-Ф*+1)-(Ф$ ■-Ф*+2)]+(Ф$ -ф,у+з)|, (4)

действие которой математически идентично применению принципа обо-щенной компенсации Булеева-Ильина на классе квадратичных пробных векторов. Тогда понятно, что для задач с линейным по координатам решением алгоритм ЬЮ является прямым (не итерационным), аналогично для задач с квадратичным по координатам решением прямым является ЬЯ2.

Здесь следует обратить внимание на то, что в отличие от условия применимости принципа компенсации Н.И. Булеева, предполагающего гладкость поведения искомой функции, формулам (3) и (4) этого не требуется, поскольку для их применимости достаточна гладкость поведения приращения решения, что практически никак не ограничивает характер искомой функции.

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

д Ф +9® (Ф -Ф ) + £ Ф =М /, (5)

^ (я) Л (п) ПА (П)

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

В третьей главе излагаются результаты исследования характеристик алгоритмов 1Л11 и путем вычислительного эксперимента. При этом сходимость решения контролируется по значению отношения норм векторов невязок

МИКИ

и средней скорости сходимости (2 (используется сферическая нормировка). Решение найдено, если выполнено условие ||л* | / < е, где 6 - заданная точность решения.

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

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

Характеристики алгоритма исследуются с помощью решения двух тестовых задач. Формулировка первой задачи включает в себя уравнение (1) без конвективных членов (11= У= 0) в единичном квадрате с краевыми условиями (2). Коэффициенты при старших, производных и точное решение задачи заданы соотношениями: Vх = 1 + 2

= 1 + 2 [о, 5 - (х - 0,5)2 - (у - 0,5)2], и(х,у) = 25б[лу(1 - *)(1 -Формулировка второй задачи отличается от первой не нулевыми полями и я V, которые определяются следующим образом: У(х,у) = у3 / (1. + х2); на левой границе 11(0,у) = 0, а внутри области решения и на оставшихся границах II рассчитывается из соотношения 1/'х + У'у - 0. Коэффициенты при старших производных вычисляются по формуле Vх = уу = ехр(5 /2), где /2 = у2 + х2. Аналитическое решение имеет вид и(х,у) = ехр(~ 10 /2)со5(8л/2).

Тип г. у. Описание

0 Первый род на всех границах

1 На границе {у=1;0<х<1} - второй род; на остальных - первый

2 На границе {у= 1; 0^х<1} и {х= 1; 0<>><1} -второй род; на остальных - первый

3 На границе {х = 0;0^_)>£1} - первый род; на остальных - второй

4 Второй род на всех границах

Для обеих тестовых задач коэффициенты краевых условий определяются из аналитического решения, при этом сочетание различных условий на разных граничных отрезках образуют тип граничных условий, описание которых представлено в таблице. Начальное приближение решения берется постоянным Ф°у = 1.

В первом параграфе третьей главы обсуждаются результаты сравнительного анализа решения первой и второй тестовых задач как классическими методами (SOR - метод последовательной верхней релаксации; LL - полинейный метод), так и современньми методами (mLL - модифицированный полинейный метод [Зверев В.Г. Модифицированный полинейный метод решения разностных эллиптических уравнений//ЖВМ и МФ. -1998. - Т. 38. - № 9. - С. 1553-1562], а также LR1 и LR2). Для корректного сравнения результатов введено понятие условного номера итерации k~nÁk, где коэффициент пА показывает, во сколько раз одна итерация

метода «А» решается медленнее одной итерации метода SOR. Здесь {А} = {SORLL,mLL,LRl,LR2}.

На рисунке 4 представлены результаты решения первой тестовой задачи с граничными условиями первого рода; сеточное разбиение 101x101. Видно, что за одну итерацию LR1 и LR2 понижают невязку на 3 -i- 4 порядка. При этом средняя скорость сходимости б* для алгоритмов mLL, LR1 и LR2

Рисунок 4 - Кривые сходимости первой тестовой задачи

изменяется в пределах 1,0 + 6,0, в то время как для методов LL и SOR ■

0,02 -s- 0,40.

Во второй тестовой задаче оператор СЛАУ не самосопряжен, однако это практически никак не сказалось на результатах решения алгоритмами mLL, LR1 и LR2. Чего нельзя сказать про методы SOR и LL, которые на мелких сетках и смешанных граничных условиях не всегда способны достичь требуемой точности (рисунок 5).

Расчеты также показали, что величина $ сильно зависит от значения итерационного параметра компенсации G: его отклонение от своего оптимального значения на 2,5 % приводит к уменьшению средней скорости сходимости вплоть до порядка. Дальнейшее, еще большее отклонение величины 0 от оптимального значения Вор1 вплоть до нуля приводит к уменьшению еще где-то на порядок. Поэтому оценка оптимального значения 8 является важной задачей.

lg;

Рисунок 5 - Кривые сходимости решения второй тестовой задачи

Для этого во втором параграфе третьей главы методом разложения в ряд Тейлора формул (3) и (4) получены полуэмпирические оценки оптимального значения итерационного параметра компенсации.

Для алгоритма Ц11 она выражается в виде 0 = 1 -а,/г2 + 0{кг), в то время как для алгоритма 1Л12 - в виде 0 = 1 - о2/г3 + 0(/г4). Путем статистического анализа результатов проведенных расчетов получены оценки константы а. Для 1Л1 ст,-10, а для 1Л2 ст2~100. При этом показано, что для удержания оцениваемого значения 0 в районе ~1% от 0ор, достаточно ст определить с относительной погрешностью в 100%..

В третьем параграфе третьей главы приводятся результаты более детального исследования характеристик алгоритмов Ц11 и ЬИ2. Программа исследований включает в себя решение первой и второй тестовых задач: 1)на четырех равномерных сетках: 41x41, 101x101, 201x201, 401x401 - задача Дирихле; 2) для пяти типов граничных условий (см. таблицу) на сетке 101x101; 3) при четырех значениях итерационного параметра компен-

20 30 £

0

41x41

401x401

сации: вор1, 0,990вор1, 0,9759^, 0, -задача Дирихле, сетка 101x101. Расчеты проводились с двойной точностью представления чисел с предельно высоким требованием к точности решения е = 5* 10"и.

На рисунке 6 представлены результаты применения алгоритма 1Л2 для решения первой тестовой задачи. Номера кривых на среднем фрагменте соответствуют типам граничных условий (см. таблицу). На первом шаге

10 20 30 к

Рисунок б - Кривые сходимости решения первой тестовой задачи алгоритмом ЬИ2

норма невязки уменьшается на 2-4 порядка, а заданная точность решения достигается за 20-30 итераций, то есть в среднем за одну итерацию норма невязки уменьшается от половины до целого порядка. При этом скорость сходимости слабо зависит от числа уравнений и от типа используемых граничных условий. Видно, что увеличение числа уравнений на два порядка приводит к понижению средней скорости сходимости приблизительно в три раза. При этом сами кривые быстро выходят на свои асимптотические значения Q" - lim Qk. Их взаиморасположение хорошо укладывается в оценку £7° а 13 -Jh . Аналогичная оценка для LR1 составляет ß" «18 4h .

Как и ранее, имеет место зависимость Q от номера итерации для различных значений итерационного параметра компенсации: отклонение 0 от bopt на 2,5 % понижает ß4 вплоть до порядка. Дальнейшее уменьшение 0 до нуля приводит к уменьшению ß* еще на порядок.

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

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

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

В первом параграфе четвертой главы рассматривается технология автоматизации определения значения итерационного параметра компенсации индивидуально для каждого расчетного узла на каждом итерационном шаге [ZverevV.G. About the iteration method for solving difference equations // Lecture notes in Computer science. — Berlin Heidelberg: Springer-Verlag. - 2005. - Vol. 3401. - pp. 621-628]. Суть идеи заключается в минимизации влияния очередного приближения решения с предыдущего итерационного шага, для чего в правой части каждого уравнения выделяется сумма слагаемых, отражающая итерационный характер записи уравнения. Эта сумма приравнивается к нулю, а из полученного уравнения вычисляется значение 6. Тогда для алгоритма LR1 формула расчета переменного значения итерационного параметра компенсации при проходе вдоль х координаты имеет вид

0„ = Э0 ■ mirt{l,тах{0,Ф*+1 у_2 /(2-ФkMj)}}. (6)

В (6) использовано естественное ограничение 0,; е [0,1], а 0О = const - корректирующий множитель, «ручной» подбор которого усиливает результат оптимизации итерационного параметра компенсации. Аналогичная формула используется и вдоль координаты .у. Для алгоритма LR2 имеет место подобное соотношение

в„ - 60 ■тт{\,тах{^ФкМ}_г /(3(Ф*+1;_, -Ф?+1у) + Ф?+1;+,)}}. (7)

Рисунок 7 иллюстрирует результаты применения технологии автоматизации определения б на примере решения первой тестовой задачи с граничным условием первого рода на сетке 401x401. Поскольку в данном случае для 1.112 0ор, = 1,0, на правом фрагменте рисунка два графика, а не четыре.

Рисунок 7 - Кривая: 1 - без автоматизации, 6 = во = 1,0; 2 - с автоматизацией, 0О = 1,0; 3 - без автоматизации, 6 = 0О = 0,9970; 4 - с автоматизацией,

60 = 0,9980.

Расчеты показали, что технология автоматизации не исчерпывает всего потенциала оптимизации. Не для каждого алгоритма она эффективна: алгоритм LR2 практически не чувствителен к ее использованию. А «ручная» оптимизация итерационного параметра компенсации как постоянного, так и переменного (с помощью 60) дает практически одинаковые результаты.

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

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

Расчеты показали, что средняя скорость сходимости $ слабо меняется в процессе итераций в случае симметричной матрицы системы, для несимметричных матриц такое изменение заметнее. При этом и в том и другом случае для задачи Дирихле имеет место оценка Q" = lim Qk » 25~Jh. Для LRs

ек—wo

opt, полученная для алгоритма LR1. Что касается влияния точности предсказания величины параметра 8 на процесс сходимости, то в качественном отношении оно имеет такой же характер, как и для алгоритмов LR1 и LR2.

Идея рассматриваемого в третьем параграфе четвертой главы алгоритма LRz состоит в том, чтобы для исключения компоненты вектора Ф во «внешаблонном» узле воспользоваться способом определения двухточечных связей поперек глобального направления из модифицированного полинейного метода (mLL). То есть для локального направления вдоль координаты у использовать соотношения типа

Причем, что важно, коэффициенты и т^ строятся на базе самих разностных уравнений и, следовательно, первоначально являются приближенными, но по мере сходимости решения становятся всё более точными. Иными словами, выражения (8) для сошедшегося решения представляют собой практически точные двухточечные связи компонентов вектора найденного решения. В этом принципиальное отличие данного алгоритма от предыдущих LR1, LR2 и LRs, в которых экстраполяционные соотношения с фиксированными коэффициентами на всем протяжении сходимости решения остаются приближенными, а сама сходимость обеспечивается за счет уменьшения величины приращения решения ДФ^ = Ф*,+1 - Фу. Данная особенность алгоритма LRz повышает его «разрешающие» возможности по отношению к предыдущим алгоритмам при решении задач повышенной сложности.

На рисунке 8 представлены результаты решения второй тестовой задачи. Нумерация кривых совпадает с нумерацией кривых рисунка 6. Удвоенное по отношению к LR1 время выполнения одной итерации так же, как и для LRs, компенсируется приблизительно двойным сокращением количества итераций для достижения требуемой точности решения. Поэтому в целом можно утверждать, что алгоритм LRz является равноэффективным по скорости сходимости с алгоритмами LR1, LR2 и LRs. При этом средняя скорость сходимости g* слабо меняется в процессе итераций и также имеет место оценка Q" = lim Qk » 25-Jh для задачи Дирихле. А оценка оптимального значения итерационного параметра компенсации, выполненная для алгоритма LR1, так же хорошо выполняется и для LRz. Использование технологии автоматизации определения параметра компенсации ускоряет счет LRz по отношению к использованию постоянного, не оптимизированного параметра. Дальнейшая «ручная» оптимизация автоматически определенного параметра компенсации практически не приводит к ускорению вычислений.

В четвертом параграфе четвертой главы анализируются численные решения нескольких модельных задач работы [Van der Vorst H.A. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linerar systems // SIAM J. Sei. Stat. Comput. - 1992. - Vol. 13. -№ 2. - pp. 631-644] бисопряженным методом со стабилизацией и неявным итерационным полинейным рекуррентным методом. Эти задачи (в исходной работе - вторая, третья и четвертая) представляют собой интерес по двум причинам: во-первых, несмотря на явно условную формулировку, они

V,,L

201x201

обладают характерными особенностями реальных физических задач; во-вторых, их разностная аппроксимация приводит к СЛАУ с плохо обусловленными матрицами. Расчеты данных задач с точностью s = Ю~10 проводились тремя вариантами бисопряженного метода: без преаобуславливанш (Bi-CGSiab), с предобуславливателем, построенным на базе неполной LU факторизации матрицы СЛАУ (Bi-CGStab Р LU) и с предобуславливателем, выполненным на базе явного метода Н.И. Булеева (Bi-CGStab Р В), а также всеми алгоритмами неявного итерационного полинейного рекуррентного метода.

На рисунке 9 представлены результаты решения второй и третьей модельных задач. Видно, что во второй задаче за разумное количество итераций (161) сходимость решения с заданной точностью удалось достичь только алгоритмом LR1. Алгоритм LRz также позволил решить задачу, но для этого потребовалось около двух тысяч итераций. В то же время все три реализации метода бисопряженных градиентов не позволили получить решение даже за 5 ООО итераций.

На правом фрагменте рисунка 9 приведены результаты решения

третьей задачи, при этом дня схо- - ---- —2Q ,,

димости Bi-CGStab потребовалось

более 500 итераций (около 2 500). Рисунок 8 - Кривые сходимости

Графики отношений норм невя- Решения пеРв°й тестовой задачи г алгоритмом LRz

зок решения четвертой модельной

задачи приведены на рисунке 10. Видно, что отсутствие предобуславливателя резко снижает скорость сходимости метода бисопряженных градиентов и не позволяет понизить отношение норм невязок ниже величины порядка е*«5,0х10~3.

Рисунок 9 - Кривые сходимости для второй (слева) и третьей (справа) модельных задач

С другой стороны, алгоритмы ЬШ, Ы12 и ЬЛб стабилизировались в районе величины е* и 2,0x10"5 за первые 10 + 100 итераций, и только четвертый алгоритм ЬЯг, что является принципиально важным, достиг требуемого уровня по точности £=Ю"10, хотя для этого потребовалось провести около 2000 итераций. Иными словами, на данной задаче подтвердились предполагаемые повышенные «разрешающие» возможности алгоритма 1Л1г по отношению к алгоритмам ЬШ, 1Л2 и

Рисунок 10 - Кривые сходимости для четвертой модельной задачи

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

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

2. Разработано четыре алгоритма полинейного рекуррентного метода: LR1, LR2, LRs и LRz. При этом три из них: LR1, LRs и LRz - являются прямыми методами в случае линейного решения исходной дифференциальной задачи, а алгоритм LR2 - прямым методом в случае квадратичного решения.

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

4. Проведено теоретическое обоснование корректности алгоритмов LR1 и LR2 в случае сходимости решения.

5. Предложена простая полуэмпирическая методика оценки оптимального значения постоянного параметра компенсации: для алгоритмов с линейной экстраполяцией приращения решения (LR1, LRs, LRz) &ор, «1 - <5\h (<т, ~ 10), для алгоритма с квадратичной экстраполяцией (LR2) -Qop, ~ 1 - <т2/г3 (с2 ~ 100), где h - шаг сеточного разбиения.

6. По результатам решения типичных тестовых и модельных задач выявлена высокая эффективность метода: средняя скорость сходимости, как правило, варьируется в пределах от « 0,5 до » 3,0 в зависимости от сеточного шага и типа граничных условий. Также показано, что средняя скорость сходимости слабо зависит от числа решаемых уравнений и ее асимптотическое значение для задачи Дирихле имеет порядок 0[4h\. При этом для алгоритма LR1: Q"»18 -Jh ; для LR2: Q" «13 yfh ; для LRs и LRz: Qa«25y[h.

7. Исследована применимость в алгоритмах LR1, LR2, LRs и LRz технологии автоматизации определения переменного оптимального параметра компенсации В.Г.Зверева. Показано, что эта технология не исчерпывает всего потенциала оптимизации и может считаться эффективной, если не используются иные способы оптимизации параметра компенсации.

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

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

1. Фомина Л.Н. Использование полинейного рекуррентного метода с переменным параметром компенсации для решения разностных эллиптических уравнений / Л.Н. Фомина // Вычислительные технологии. -ИВТ СО РАН. - 2009. - Т. 14. - № 4. - С. 108-120.

2. Фомин A.A. Об одном варианте полинейного рекуррентного метода решения разностных эллиптических уравнений / A.A. Фомин,

\

JI.H. Фомина // Вестник Томского государственного университета. Математика и межаника. - 2010. - № 2. - С. 20-27.

3. Фомин A.A. Сравнение эффективности высокоскоростных методов решения разностных эллиптических СЛАУ / A.A. Фомин, Л.Н. Фомина // Вестник Томского государственного университета. Математика и механика. -2009.- №2. -С. 71-77.

4. Фомин A.A. Полинейный рекуррентный метод решения разностных эллиптических уравнений / A.A. Фомин, Л.Н. Фомина // Кемерово: КемГУ. -2007. - 78с. - Деп. в ВИНИТИ 06.04.2007, № 385-В2007.

5. Фомин А. А. Полинейный рекуррентный метод решения СЛАУ с пя-тидиатональной матрицей / A.A. Фомин, Л.Н. Фомина // Четвертая Сибирская школа-семинар по параллельным и высокопроизводительным вычислениям (Томск, 9-11 октября 2007 г.). - Томск: Дельтаплан. - 2008,- С. 192-201.

6. Фомин A.A. Обоснование корректности полинейного рекуррентного метода решения разностных эллиптических уравнений / A.A. Фомин, Л.Н. Фомина // Пятая Сибирская конференция по параллельным и высокопроизводительным вычислениям (Томск, 1-3 декабря 2009 года). - Томск: Изд-во ТГУ. - 2009. - С. 133-137.

7. Фомина Л. Н. Неявный полинейно-рекуррентный метод решения разностных эллиптических уравнений / Л.Н. Фомина // Математические методы в технике и технологиях - ММТТ-20. Т. 1. - Ярославль: Изд-во ЯГТУ. - 2007. - С. 167-171.

8. Фомина Л.Н. Полинейный рекуррентный метод решения разностных эллиптических уравнений / Л.Н. Фомина // Математическое образование в регионах России: труды международной научно-практической конференции 26 окт. 2007 г. - Барнаул: Изд-во АлтГТУ. - 2007. - С. 15-21.

9. Фомина Л.Н. Сравнение высокоскоростных методов решения эллиптических СЛАУ / Л.Н. Фомина // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всероссийской научно-практической конф. с международным участием (14-15 ноября 2008 г.). -Томск: Изд-во ТГУ. - 2008. - С. 212-214.

Тираж 120 экз. Отпечатано в ОАО «ИПП «Кузбасс» 650066, г. Кемерово, пр-т Октябрьский, 28

Перечень условных обозначений, сокращений.

Введение.

1 Итерационные методы решения СЛАУ: обзор литературы.

2 Формулировка задачи и алгоритм неявного итерационного полинейного рекуррентного метода.

2.1 Получение системы разностных эллиптических уравнений с матрицей положительного типа.

2.2 Алгоритм неявного итерационного полинейного рекуррентного метода с линейной экстраполяцией приращения решения.

2.2.1 Общая идея метода.

2.2.2 Методика преобразований разностных уравнений в локальном направлении.

2.2.3 Алгоритм преобразований исходной СЛАУ.

2.3 Алгоритм неявного итерационного полинейного рекуррентного метода с квадратичной экстраполяцией приращения решения.

2.4 Обоснование корректности неявного итерационного полинейного рекуррентного метода.

3 Тестирование эффективности неявного итерационного полинейного рекуррентного метода решения СЛАУ.

3.1 Предварительная оценка эффективности неявного итерационного полинейного рекуррентного метода.

3.1.1 Первая тестовая задача.

3.1.2 Вторая тестовая задача.

3.2 Полуэмпирическая оценка оптимального итерационного параметра компенсации.

3.2.1 Линейная экстраполяция приращения решения.

3.2.2 Квадратичная экстраполяция приращения решения.

3.3 Анализ эффективности неявного итерационного полинейного рекуррентного метода в широком диапазоне требований по точности.

4 Развитие неявного итерационного полинейного рекуррентного метода решения СЛАУ.

4.1 Применение технологии автоматической адаптации итерационного параметра компенсации.

4.2 Алгоритм неявного итерационного по линейного рекуррентного метода с экстраполяцией приращения решения вдоль глобального координатного направления.

4.2.1 Идея алгоритма на примере выбора глобального направления вдоль координаты х.

4.2.2 Модификация расчетных формул в случае автоматического определения параметра компенсации.

4.2.3 Анализ результатов решения тестовых задач.

4.3 Алгоритм неявного итерационного полинейного рекуррентного метода с экстраполяцией приращения решения по технологии модифицированного полинейного метода.

4.3.1 Вывод расчетных формул.

4.3.2 Модификация расчетных формул в случае автоматического определения параметра компенсации.

4.3.3 Анализ результатов решения тестовых задач.

4.4 Сравнительный анализ эффективности итерационных методов на примере решения модельных задач.

4.4.1 Тестирование алгоритма метода Bi-CGStab.

4.4.2 Вторая модельная задача.

4.4.3 Третья модельная задача.

4.4.4 Четвертая модельная задача.

Первые итерационные методы решения систем линейных алгебраических уравнений (СЛАУ) были разработаны еще в XIX веке. Это широко известные методы простой итерации (метод Якоби), Гаусса-Зейделя, последовательной верхней релаксации. В начале XX века Ричардсон разработал свою схему численного решения уравнения Пуассона. Однако только с появлением в начале второй половины XX столетия электронной вычислительной техники и её интенсивного проникновения, в первую очередь, в научно-практическую деятельность человека привело к резкому ускорению разработок и модификаций разнообразных вычислительных методов решения систем линейных уравнений. В частности, применение вычислительных методов оказалось особенно эффективным для решения задач теплообмена, динамики жидкостей, магнитной гидродинамики, переноса зарядов и многих других. Связано это с чем, что численный эксперимент по своей сути является относительно не дорогим, достаточно оперативным и информативным методом исследования сложных нелинейных процессов указанных задач.

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

С другой стороны, как указывает С. Патанкар, исходные уравнения гидродинамики и те-пломассопереноса нелинейные по сути, что совместно с вышеуказанной проблемой пространственной многомерности предопределяет использование итерационных подходов при разработке методов решения подобных СЛАУ. Итерационным методам решения систем линейных уравнений посвящено огромное число исследований, нашедших свое отражение и обобщение в монографиях Д.К. и В.Н. Фаддеевых, А.А. Самарского и Е.С. Николаева, А.А. Самарского и П.Н. Вабищевича, Г.И. Марчука, Н.С. Бахвалова, В. Вазова и Дж. Форсайта, В.П. Ильина, Д. Янга, Ю.А. Кузнецова, Е. Вашпресса, Ю. Саада, Дж. Ортега и многих других. На смену широко распространенным в 50 - 70-е годы прошлого столетия методам Якоби, Гаусса-Зейделя, различным вариантам метода последовательной верхней релаксации и их блочным модификациям, а также методам переменных направлений и дробных шагов (Д. Писмэн и X. Рэчфорд, Н.Н. Яненко, М. Лиз, Г.И. Марчук, Дж. Дуглас) пришли итерационные градиентные методы (О. Аксельссон, Г. Голуб, Х.А. ван дер Ворст, В.П. Ильин, Ю. Саад, Р. Вайс, Ю.Н. Захаров, Р. Фройнд), восходящие к пионерским работам JI.B. Канторовича, М.А. Красносельского, В.М. Фридмана, Г. Темпле, М. Хестенса и Е. Штифеля, В. Арнольди, К. Ланцоша.

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

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

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

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

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

Основные задачи исследования состоят в следующем:

1. Разработать, обосновать и исследовать эффективность неявного итерационного поли-нейного рекуррентного метода решения СЛАУ с пятидиагональной матрицей положительного типа с применением ЭВМ.

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

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

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

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

3. Исследована применимость в алгоритмах LR1, LR2, LRs и LRz технологии В.Г. Зверева автоматизации определения переменного оптимального параметра компенсации.

4. По результатам решения типичных тестовых и модельных задач проанализированы основные характеристики алгоритмов LR1, LR2, LRs и LRz: времени исполнения, средней скорости сходимости, вычислительной устойчивости, - в зависимости от сеточного разбиения области (размерности матрицы), вида решаемого уравнения и типа граничных условий задачи, а также величины итерационного параметра компенсации.

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

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

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

3. Результаты применимости в алгоритмах LR1, LR2, LRs и LRz технологии В.Г. Зверева автоматизации определения переменного оптимального параметра компенсации.

4. Анализ основных характеристик алгоритмов LR1, LR2, LRs и LRz: времени исполнения, средней скорости сходимости, вычислительной устойчивости, — в зависимости от сеточного разбиения области (размерности матрицы), вида решаемого уравнения и тина граничных условий задачи, а также величины итерационного параметра компенсации.

Достоверность полученных результатов следует:

• из корректной математической постановки задач как дифференциальной, так и разностной;

• из сравнения с известными аналитическими решениями при тестовых расчетах;

• из постоянного контроля параметров сходимости решения: нормы невязки, нормы погрешности, средней скорости сходимости.

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

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

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

Основные выводы параграфа 4.4 можно сформулировать следующим образом.

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

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

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

4. Алгоритм LRz обладает более высокими «разрешающими» возможностями по отношению к алгоритмам LR1, LR2 и LRs безотносительно к его скорости сходимости и количества необходимых для сходимости итераций.

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

Заключение

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

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

2. Разработано четыре алгоритма полинейного рекуррентного метода: LR1, LR2, LRs и LRz. При этом три из них: LR1, LRs и LRz, - являются прямыми методами в случае линейного решения исходной дифференциальной задачи, а алгоритм LR2 — прямым методом в случае квадратичного решения.

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

4. Проведено теоретическое обоснование корректности алгоритмов LR1 и LR2 в случае сходимости решения.

5. Предложена простая полу эмпирическая методика оценки оптимального значения постоянного параметра компенсации: для алгоритмов с линейной экстраполяцией приращения решения (LR1, LRs, LRz) Qop,» 1 - а,/Г (cr,~10), для алгоритма с квадратичной экстраполяцией приращения решения (LR2) Qopt ~ 1 - a2h3 (ст2~100), где h - шаг сеточного разбиения.

6. По результатам решения типичных тестовых и модельных задач выявлена высокая эффективность метода: средняя скорость сходимости, как правило, варьируется в пределах от ~ 0,5 до ~ 3,0 в зависимости от сеточного шага и типа граничных условий. Также показано, что средняя скорость сходимости слабо зависит от числа решаемых уравнений и её асимптотическое значение для задачи Дирихле имеет порядок При этом для алгоритма LR1: Qа »18 y[h ; для LR2: Qa «13 Jh ; для LRs и LRz: Qa -25 yfh .

7. Исследована применимость в алгоритмах LR1, LR2, LRs и LRz технологии автоматизации определения переменного оптимального параметра компенсации В.Г. Зверева. Показано, что эта технология не исчерпывает всего потенциала оптимизации и может считаться эффективной, если не используются иные способы оптимизации параметра компенсации.

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

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

2. Патанкар С. Численные методы решения задач теплообмена и динамики жидкости / С. Патанкар. М.: Энергоатомиздат. - 1984. - 152 с.

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

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

5. Фаддеев Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фаддеева.- М.: Физматгиз. 1963. - 656 с.

6. Марчук Г.И. Методы вычислительной математики / Г.И. Марчук. Новосибирск. Наука.- 1973.-351 с.

7. Самарский А.А. Численные методы / А.А. Самарский, А.В. Гулин. М.: Наука. -1989.

8. Yousef Saad. Iterative Methods for Sparse Linear Systems / Y. Saad. N.Y.: PWS Publ. -1996.-460 p.

9. Самарский А.А. Введение в численные методы / А.А. Самарский. М.: Наука. - 1987. -270 с.

10. Бахвалов Н.С. Численные методы / Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. -М.: Наука.-1987.-636 с.

11. Крылов В.И. Вычислительные методы / В.И. Крылов, В.В. Бобков, П.И. Монастырский. -М.: Наука. 1976. - Т. 1. - 304 с.

12. Крылов В.И. Вычислительные методы / В.И. Крылов,В.В. Бобков, П.И. Монастырский. -М.: Наука. 1977. - Т. 2. - 400 с.

13. Молер К. Численное решение системы линейных алгебраических уравнений / Дж. Форсайт, К. Молер; под ред. Г.И. Марчука. М.: Мир. - 1969. - 167 с.

14. Вабищевич П.Н. Вычислительная теплопередача / П.Н. Вабищевич, А.А. Самарский. -М.: Едиториал УРСС. 2003. - 785 с.

15. Рихтмайер Р. Разностные методы решения краевых задач/ Р. Рихтмайер, К. Мортон; под ред. Б.М. Будака и А.Д. Горбунова. М.: Мир. - 1972. - 421 с.

16. Ильин В.П. Методы неполной факторизации для решения алгебраических систем / В.П. Ильин. М.: Физматлит. - 1995. - 288 с.

17. ОртегаДж. Введение в численые методы решения дифференциальных уравнений / Дж. Ортега, У. Пул; под ред. А.А. Абрамова. — М.: Наука. Гл. ред. физ.-мат. лит. 1986. -288 с.

18. Самарский А.А. Численные методы решения задач конвекции-диффузии / А.А. Самарский, П.Н. Вабищевич. М.: Эдиториал УРСС. - 1999. - 248 с.

19. Ильин В.П. Методы конечных разностей и конечных объемов для эллиптических уравнений / В.П. Ильин. Новосибирск: Изд-во Ин-та математики. - 2000. - 345 с.

20. Ильин В.П. Методы и технологии конечных элементов / В.П. Ильин. — Новосибирск: Изд-во ИВМ и МГ СО РАН. 2007.

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

22. Кузнецов Ю.А. Итерационные методы в подпространствах / Ю.А. Кузнецов. Москва. -1984.- 134 с.

23. Кузнецов Ю.А. Блочно-релаксационные методы в подпространствах, их оптимизация и применение / Ю.А. Кузнецов // В сб: Вычислительные методы в прикладной математике. Новосибирск: Наука. Сибирское отделение. - 1982. - С. 119-143.

24. Зверев В.Г. Модифицированный полинейный метод решения разностных эллиптических уравнений / В.Г. Зверев // ЖВМ и МФ. 1998. - Т. 38. - № 9. - С. 1553-1562.

25. Зверев В.Г. Неявный блочный итерационный метод для решения двумерных эллиптических уравнений / В.Г. Зверев // ЖВМ и МФ. 2000. - Т. 40. - № 4. -С. 590-597.

26. Zverev V.G. About the iteration method for solving difference equations / V.G. Zverev // Lecture notes in computer science. Berlin Heidelberg: Springer-Verlag. - 2005. - vol. 3401. -pp. 621-628.

27. Ильин В.П. Численные методы решения задач электрооптики / В.П. Ильин. — Новосибирск: Наука, Сибирское отделение. 1974. - 203 с.

28. Ильин В.П. Численные методы решения задач электрофизики / В.П. Ильин. М.: Наука, Главная редакция физ-мат. литературы. - 1985. - 335 с.

29. Джордж А. Численные решения больших разреженных систем уравнений / А. Джордж, Дж. Лю. М.: Мир. - 1984. - 334 с.

30. Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров будующего / В.П. Ильин // Математика. Информатика. Природа. — 1999. - № 6. - С. 11-18.

31. Лаевский Ю.М. О некоторых итогах развития современной вычислительной математики / Ю.М. Лаевский // Вычислительные технологии. ИВТ СО РАН. - 2002. - т. 7. - № 2. -С. 74-83.

32. Фадцеева В.Н. Вычислительные методы линейной алгебры. Библиографический указатель 1828-1974гг. / В.Н. Фадцеева, Ю.А. Кузнецов, Г.Н. Грекова, Т.А. Долженкова. -Новосибирск. — 1976. 418 с.

33. Богачев К.Ю. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений / К.Ю. Богачев. Препринт . - Москва. — 1998. — 137 с.

34. Слепцов А.Г. Об ускорении сходимости линейных итераций // Моделирование в механике / А.Г. Слепцов. Новосибирск: ВЦ СО АН СССР. - 1989. - Т. 3. - № 5. -С. 118-125.

35. Маслянкин В.И. К решению систем линейных уравнений с разреженной матрицей итерационными методами / В.И. Маслянкин, М.И. Мухина, А.А. Резник // Математическое моделирование. 1992. - Т. 4. -№ 5. - С. 100-108.

36. Захаров Ю.Н. Градиентные итерационные методы решения задач гидродинамики / Ю.Н. Захаров. — Новосибирск: Наука. 2004. - 239 с.

37. Захаров Ю.Н. Об одном методе ускорения сходимости итерационных схем / Ю.Н. Захаров, Ю.И. Шокин, Н.Н. Яненко // Численные методы механики сплошных сред.- 1974.-Т. 5. —№5.-С. 57-62.

38. Вайс Р. Итерационные методы решения систем линейных уравнений, от прошлого к будущему / Р. Вайс, И. Подгаецкая, X. Хсфнер, В. Шонауер // Математическое моделирование. -2001. Т. 13. -№ 2. - С. 39-50.

39. Гасеми Камалванд М. Об одном методе конгруэнтного типа для линейных систем с сопряженно-нормальными матрицами коэффициентов / М. Гасеми Камалванд, Х.Д. Икрамов // ЖВМ и МФ. 2009. - Т. 49. - № 2. - С. 211-224.

40. Дана М. Численное сравнение двух методов минимальных невязок для линейных многочленов от унитарных матриц / М. Дана, Х.Д. Икрамов // ЖВМ и МФ. 2006. -Т. 46.-№ 12.-С. 2138-2148.

41. ЮхноЛ.Ф. Модификация некоторых методов типа сопряженных направлений для решения систем линейных алгебраических уравнений / Л.Ф. Юхно // ЖВМ и МФ. 2007. -Т. 47. - № 11. — С. 1811-1818.

42. Юхно Л.Ф. О некоторых методах типа сопряженных направлений для решения прямоугольных систем линейных алгебраических уравнений / Л.Ф. Юхно // ЖВМ и МФ.- 2007. Т. 47. - № 12. - С. 1979-1987.

43. Алыпина Е.А. Градиентные методы с ускоренной сходимостью / Е.А. Алыпина, А.А. Болтаев, О.А. Качер // ЖВМ и МФ. 2005. - Т. 45. - № 3. - С. 374-382.

44. Бобышев В.Н. О сходимости метода сопряженных пар / В.Н. Бобышев, С.Г. Довман // Разностные методы математической физики / Под ред. Е.С. Николаева. М.: Изд-во Моск. ун-та. - 1984. - С. 3-9.

45. Капорин И.Е. К развитию метода минимальных итераций / И.Е. Капорин // Разностные методы математической физики / Под ред. Е.С. Николаева. — М.: Изд-во Моск. ун-та. -1984.-С. 18-26.

46. Кучеров А.Б. Метод приближенной факторизации для решения разностных смешанных эллиптических краевых задач / А.Б. Кучеров, М.М. Макаров // Разностные методы математической физики / Под ред. Е.С. Николаева. М.: Изд-во Моск. ун-та. - 1984. -С. 54-65.

47. Келер У. К оценкам энергетической эквивалентности разностных эллиптических операторов с переменными и постоянными коэффициентами / У. Келер // Разностные методы математической физики / Под ред. Е.С. Николаева. М.: Изд-во Моск. ун-та. — 1984.-С. 27-34.

48. Булгаков А.Я. Учет вычислительных погрешностей в одном варианте метода сопряженных градиентов / А.Я. Булгаков, С.К. Годунов // В сб: Вычислительные методы линейной алгебры. Новосибирск: Наука. Сибирское отделение. — 1985. - С. 38-55.

49. Гинкин В.П. Новый метод расчета трехмерной конвекции на сетках большой размерности / В.П. Гинкин, С.М. Ганина // Математическое моделирование. 2003. - Т. 15. - № 6. -С. 55-58.

50. Не J. Н. Approximate analytical solution for certain strongly nonlinear oscillations by the variational iteration method / J.H. He // Сибирский журнал вычислительной математики / Новосибирск: СО РАН. 2002. - Т. 5. - № 1. - С. 57-69.

51. Малеев А.А. О методе SOR с пересекающимися подсистемами / А.А. Малеев // ЖВМ и МФ. 2006. - Т. 46. - № 6. - С. 963-974.

52. Johnsson Lennart Highly Concurrent Algorithms for Solving Linear systems of Equations / Lennart Johnsson. Препринт. — Computer Science California Institute of Technology Pasadena, CA 91125. - 1983. - 20 p.

53. Thomas C. Oppe A Package for Solving Large Sparse Linear Systems by Various Iterative Methods / Thomas C. Oppe, Wayne D. Joubert, David R. Kincaid. NSPCG User's Guide. V 1.0.- 1988. -84 p

54. Shapira Y. Towards automatic multigrid algorithms for SPD. Nonsymmetric and indefinite problems / Y. Shapira Y., M. Israeli and A. Sidi. Препринт. - Computer Science Department. Technion. Haifa 32000, Israel. - 16 c.

55. Бураго Н.Г. Вычислительная механика / Н.Г. Бураго. Препринт. - Москва. - 2005. -247 с.

56. Яненко Н.Н. Метод дробных шагов решения многомерных задач математической физики / Н.Н. Яненко. Новосибирск: Наука. Сибирское отделение. - 1967. - 196 с.

57. Годунов С.К. Разностные схемы (введение в теорию) / С.К. Годунов, B.C. Рябенький. -М.: Наука. 1973.-400 с.

58. Белоцерковский О.М. Метод расщепления в применении к решению задач динамики вязкой несжимаемой жидкости / О.М. Белоцерковский, В.А. Гущин, В.В. Щенников // ЖВМ и МФ. 1975. — Т. 15.-№ 1.-С. 197-207.

59. Ковеня В.М. Метод расщепления в задачах газовой динамики / В.М. Ковеня, Н.Н. Яненко. Новосибирск: Наука. Сибирское отделение. - 1981. - 304 с.

60. Ладыженская О.А. Линейные и квазилинейные уравнения эллиптического типа / О.А. Ладыженская, Н.Н. Уральцева. М.: Наука. Главная редакция физ.-мат. литературы. - 1973.-578 с.

61. Четверушкин Б.Н. Об одном итерационном алгоритме решения разностных уравнений / Б.Н. Четверушкин //ЖВМ и МФ. 1976. - Т. 16. -№ 2. - С. 519-524.

62. Четверушкин Б.Н. "а-(3"- итерационный метод // Вычислительные методы линейной алгебры. Труды Всесоюзной конференции (Москва, август 1982 г.) / Б.Н. Четверушкин. -М.: АН СССР. Ощел вычислительной математики. 1983. - С. 233-237.

63. Андриенко Д.А. Решение двумерного уравнения Пуассона нелинейным итерационным методом / Д.А. Андриенко, С.Т. Суржиков // Школа-семинар "Аэрофизика и физическая механика классических и квантовых систем". ИПМех РАН, 3-4 декабря. — 2007. -С.227-230.

64. Гинкин В.П. Оптимальный предобуславливатель в методе сопряженных градиентов для трехмерной HEX-Z геометрии / В.П. Гинкин, А.В. Кулик. Препринт . - Обнинск. - 1999. -20 с.

65. Губайдулин Д.А. Алгоритм решения трехмерных задач напорно-безнапорной стационарной фильтрации жидкости со сгущающимися участками сетки / Д.А. Губайдулин, П.А. Мазуров, А.В. Цепаев // Вычислительные методы и программирование. 2005. - Т. 6. - С. 217-225.

66. Альчиков В.В. Использование метода неполной факторизации Холесского сопряженных градиентов для решение трехмерных уравнений Лапласа / В.В. Альчиков, В.И. Быков // Вычислительные технологии. - 2000. - Т. 5. - № 6. - С. 15-19.

67. Гинкин В.П. Метод параболических прогонок для решения двумерных уравнений эллиптического типа / В.Г1. Гинкин. Обнинск. - 1981. - Препринт ФЭИ-1153.

68. Гинкин В.П. Новый вариант метода неполной факторизации для решения двумерных уравнений эллиптического типа с несимметричными матрицами / В.П. Гинкин, Н.М. Троянова, П.В. Новиков И Математическое моделирование. 2004. - Т. 16. - № 7. -С. 101-116.

69. Богачев К.Ю. Блочные предобусловливатели класса ILLJ для задач фильтрации многокомпонентной смеси в пористой среде / К.Ю. Богачев, Я.В. Жабицкий // Вестник МГУ. Серия 1: Математика. Механика. Изд-во МГУ. -2009. - № 5. - С. 19-24.

70. Максимов М.М. Один из методов неполного блочного разложения при численном моделировании задач фильтрации / М.М. Максимов, Л.П. Рыбицкая, М.Е. Травкина // Математическое моделирование. 1990. - Т. 2. - № 2. - С. 99-107.

71. Ильин В.П. Методы бисопряженных направлений в подпространствах Крылова /

72. B.П. Ильин // Сибирский журнал индустриальной математики. — 2008. — Т. 11. — № 4.1. C.47-60.

73. Бубякин А.А. Об одном подходе к построению схем повышенного порядка точности в методе конечных элементов / А.А. Бубякин, Ю. М. Лаевский // Сибирский журнал вычислительной математики / Новосибирск: СО РАН. 2004. - Т. 7. - № 4. -С. 287-300.

74. Zhang Y. Gauss type preconditioning techniques for linear system / Y. Zhang, T.Z. Huang, X.P. Liu // Appl. Mathem. Сотр. 2007. - № 188. - pp. 612-633.

75. Бубякин А. А. Компактная проекционно-сеточная схема для одного класса двумерных уравнений диффузии / А. А. Бубякин, Ю. М. Лаевский // Сибирский журнал вычислительной математики / Новосибирск: СО РАН. 2003. - Т. 6. - №2. -С.125-138.

76. Huang T.Z. Modified Incomplete Cholesky Factorization for Solving Electromagnetic Scattering Problems / T.Z. Huang, Y. Zhang, and L. Li // Progress In Electromagnetics Research B. 2009. - 'Г. 13. - C. 41-58.

77. Giraud L. Convergence in Backward Error of Relaxed GMRES / L. Giraud, S. Gratton, J. Langou // SIAM J. Sci. Comput. 2007. - vol. 29. - № 2. - pp. 710-728.

78. Эйрих С.Н. Подход к модернизации генетического алгоритма для решения систем линейных алгебраических уравнений / С.Н. Эйрих // Вектор науки ТГУ. Изд-во Тольяттинский гос. ун-т. -2009. - № 4(7). - С. 5-7.

79. Быченков Ю.В. О предобусловливании седловых задач методами переменных симметричных и кососимметричных итераций / Ю.В. Быченков // ЖВМ и МФ. 2009. -Т. 49.-№3,-С. 411-421.

80. Макеев А.Г. Продолжение по параметру решения в виде уединенного бегущего импульса в системе типа реакция-диффузия / А.Г. Макеев, H.JI. Семендяева // ЖВМ и МФ. 2009. - Т. 49. - № 4. - С. 646-661.

81. Ильин В.П. О методах сопряженных и полусопряженных направлений с предобусловливающими проекторами / В.П. Ильин // Докл. РАН. 2008. — Т. 419. - № 3.- С. 303-306.

82. Ильин В.П. О методах полу сопряженных направлений с динамическим предобусловливанием / В.П. Ильин, Е.А. Ицкович // Сибирский журнал индустриальной математики. 2007. - Т. 10. - № 4. - С. 41-54.

83. Ильин В.П. О сеточных технологиях для двумерных краевых задач / В.П. Ильин,

84. B.М. Свешников, B.C. Сынах // Сибирский журнал индустриальной математики. 2000. -Т. 3.-№ 1.-С. 124-136.

85. Гинкин В.П. Эффективный метод решения плохо обусловленных трехмерных уравнений эллиптического типа на примере решения задачи Стефана для моделирования кристаллизации расплавов / В.П. Гинкин, О.М. Гинкина, С.М. Ганина, К.Г. Чернов,

86. C.В. Пупко, А.Б. Кагаленко. Препринт. ГНЦ РФ-ФЭИ, г. Обнинск.

87. Чадов С.Н. Реализация алгоритма решения несимметричных систем линейных уравнений на графических процессорах / С.Н. Чадов // Вычислительные методы и програмирование.- 2009. Т. 10. - С. 321-326.

88. Гаврилов А.В. Моделирование полей в аксиально симметричной среде / А.В. Гаврилов, Я.Л. Гурьева, В.П. Ильин, Е.А. Ицкович // Сибирский журнал индустриальной математики. 2001. - Т. 4. - № 1. - С. 38-51.

89. Van der Vorst Н.А. BI-CGSTAB: a fast and smoothly converging variant of BI-CG for the solution of nonsymmetric linerar systems / H.A. van der Vorst // SIAM J. Sci. Stat. Comput. -1992.-vol. 13,-№2.-pp. 631-644.

90. Павлов А.С. О решении обусловленных линейных систем итерационными методами / А.С. Павлов, Л.Ф. Юхно // Математическое моделирование. 2004. - Т. 16. - № 7. -С. 13-20.

91. Graves-Morris P.R. The breakdowns of BiCGStab / P.R. Graves-Morris // Numer. Algorithms. 2002. - vol. 29. - pp. 97-105.

92. Гурьева Я.Л. О численном решении трехмерных диффузионно-конвективных краевых задач / Я.Л. Гурьева, В.П. Ильин // Сибирский журнал индустриальной математики. -2003. Т. 6. -№ 1. - С. 27-34.

93. Малеев А.А. Итерационные процессы, основанные на блочных //-расщеплениях / А.А. Малеев // ЖВМ и МФ. 2008. - Т. 48. - № 4. - С. 539-561.

94. Шевченко И.В. Численное моделирование движения воздушных масс бессеточными методами / И.В. Шевченко // Математическое моделирование. 2008. - Т. 20. — № 10. -С. 75-85.

95. Вшивков В.А. Итерационный метод решения СЛАУ первого порядка сходимости с регулируемой матрицей перехода / В.А. Вшивков, О.А. Засыпкина // Сибирский журнал индустриальной математики. 2008. - Т. 11. - № 2. - С. 40-49.

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

97. Вшивков В.А. Построение эффективного параллельного метода решения уравнения Пуассона для моделирования эволюции протопланетного диска / В.А. Вшивков,

98. A.В. Снытников // Вычислительные методы и програмирование. — 2009. — Т. 10. — С. 116-122.

99. Витковский В.Э. Вычислительная производительность параллельного алгоритма прогонки на кластерных суперкомпьютерах с распределенной памятью /

100. B.Э. Витковский, М.П. Федорук // Вычислительные методы и програмирование. 2008. -Т. 9.-С. 305-310.

101. Богачев К.Ю. Применение параллельного предобусловливателя CPR к задаче фильтрации вязкой сжимаемой жидкости в пористой среде / К.Ю. Богачев, И.Г. Горелов // Вычислительные методы и програмирование. 2008. - Т. 9. - С. 184-190.

102. Shapira Y. Parallelizable Incomplete Ш-typc Precondition for the Solution of Sparse Linear Systems / Y. Shapira, A. Sidi and M.A. Israeli. Препринт. - Technion-Computer Science Department - Technical Report CS0799-1993. - 30 p.

103. Теренков В.И. О реализации прямых методов решения сеточных уравнений на многопроцессорных вычислительных системах / В.И. Теренков // Разностные методы математической физики / Под ред. Е.С. Николаева. М.: Изд-во Моск. ун-та. - 1984. — С. 97-105.

104. Головашкин Д.Л. Параллельное решение СЛАУ методом Зейделя / Д.Л. Головашкин, О.Е. Горбунов // Вестник Самарского гос. тех. ун-та. Серия физико-математические науки.-2004.-№27.-С. 10-13.

105. Милюкова О.Ю. Новые паралельные итерационные методы с факторизованными матрицами предобуславливания для решения эллиптических уравнений на треугольных сетках / О.Ю. Милюкова // Математическое моделирование. 2007. — Т. 19. — №9. — С. 27—48.

106. Кучеров А.Б. Паралельные и конвективные алгоритмы попеременно-треугольного итерационного метода / А.Б. Кучеров, Е.С. Николаев // Разностные методы математической физики / Под ред. Е.С. Николаева. М.: Изд-во Моск. ун-та. - 1984. -С. 66-83.

107. Ильин В.П. О методах неполной факторизации с обобщенной компенсацией /

108. B.П. Ильин, К.Ю. Лаевский // Сибирский журнал вычислительной математики. 1998. -Т. 1. - № 4. - С. 321-336.

109. Фомин А.А. Численное исследование влияния граничных условий на решение задач термогравитационной конвекции в открытых областях / А.А. Фомин. Томск: Томский университет. - 1985. - 51с. - Деп. в ВИНИТИ 22.11.85 № 8069-В.

110. Кузнецов А.Е. Численное моделирование существенно дозвуковых стационарных неизотермических течений однородного вязкого газа в каналах / А.Е. Кузнецов, М.Х. Стрелец // Численные методы механики сплошной среды. 1983. - Т. 14. - № 6.1. C. 97-114.