WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

НЕЯВНЫЙ ИТЕРАЦИОННЫЙ ПОЛИНЕЙНЫЙ РЕКУРРЕНТНЫЙ

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

УРАВНЕНИЙ

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

методы и комплексы программ

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

Томск – 2010

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

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

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

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

Ведущая организация: Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

Основные задачи

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

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:

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

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

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

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

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

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

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

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

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

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

Список цитируемой литературы включает 108 наименований.

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

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

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

Пусть определена некоторая краевая задача тепло- или массопереноса в двумерной прямоугольной области ={(x,y): 0 x Lx, 0 y Ly}.

Внутри области поведение искомой функции Ф(x,y) описывается обобщенным дифференциальным уравнением где x, y – коэффициенты при старших производных, S – источник. А на границе области Г имеют место граничные условия третьего рода где aГ, bГ, cГ – известные величины, а n – нормаль к границе.

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

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

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

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

Рисунок 2 – Схема первого шага предполагаемого линейного преобразования матрицы и фрагмент соответствующей структуры матрицы 2. Нетрудно видеть, что подсистема уравнений на шаблонах (i, j):

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

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

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

5. Подстановка подвектора n j, j = 1,m в предпоследнюю подсистему (рисунок 3, подсистема n – 1) позволяет получить замкнутую, в общем случае, трехточечную систему уравнений на массиве индексов (i = n – 1, 1 j m ), которая снова решается методом скалярной прогонки и так далее (уменьшение индекса i, обратный ход). Процедура обратного хода вдоль оси x повторяется (n – 1) раз, что позволяет найти оставшиеся компоненты искомого вектора решения.

Рисунок 3 – Замыкание полинейного рекуррентного преобразования разностных шаблонов на правой границе расчетной области Здесь, для определенности, проход вдоль координаты x будет называться глобальным направлением, а вдоль координаты y – локальным. Понятно, что глобальное направление может меняться с локальным.

Предполагаемая в п.1 процедура линейных преобразований представляет собой поэтапную последовательность линейных комбинаций исходных уравнений, в которой только один этап является приближенным, а все остальные этапы – эквивалентными преобразованиями. Благодаря этому приближенному этапу метод представляет собой итерационный процесс. При этом в качестве одной итерации считается сумма поочередных проходов вдоль глобального направления x, а затем вдоль глобального направления y. Следует заметить, что алгоритмы LR1, LR2, LRs и LRz неявного итерационного полинейного рекуррентного метода различаются между собой содержанием этапа приближенных преобразований. Все остальные преобразования всех алгоритмов неявного итерационного полинейного рекуррентного метода совпадают между собой.

Суть этапа приближенных преобразований состоит в том, чтобы выразить компонент искомого вектора решения в так называемом «внешаблонном» узле через компоненты вектора решения в соседних узлах разностной сетки. Делается это с помощью экстраполяционной формулы, записанной относительно приращения решения ij = ij ij, здесь k – номер итерации. Например, в случае линейной экстраполяции формула имеет вид где – итерационный параметр компенсации, причем 0 1, поскольку нетрудно показать, что использование (3) в конечном счете приводит к результату, математически идентичному использованию принципа обобщенной компенсации Булеева-Ильина на классе линейных пробных векторов. Алгоритм неявного итерационного полинейного рекуррентного метода с экстраполяционной формулой (3) назван LR1.

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

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

Если повторить рассмотренные выше преобразования в матричновекторной форме, то уравнение преобразованной СЛАУ с четырехдиагональной матрицей (рисунок 1) запишется в виде где матрицы G, L, M, – операторы эквивалентных преобразований, а порожденная формулами (3) или (4) матрица B – оператор приближенных преобразований. В случае сходимости решения имеет место вивалентные преобразования исходной системы, откуда и следует корректность метода.

В третьей главе излагаются результаты исследования характеристик алгоритмов LR1 и LR2 путем вычислительного эксперимента. При этом сходимость решения контролируется по значению отношения норм векторов невязок R k / R 0 и средней скорости сходимости Q k (используется сферическая нормировка). Решение найдено, если выполнено условие R k / R 0 <, где – заданная точность решения.

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

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

V ( x, y ) = y 3 / (1 + x 2 ) ; на левой границе U (0, y ) = 0, а внутри области решения и на оставшихся границах U рассчитывается из соотношения U x + Vy = 0. Коэффициенты при старших производных вычисляются по формуле x = y = exp (5 l2 ), где l2 = y 2 + x 2. Аналитическое решение имеет вид u ( x, y ) = exp (10 l 2 ) сos (8 l 2 ).

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

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

шения первой тестовой виями первого рода; сеточ- - ное разбиение 101101.

Видно, что за одну итерацию LR1 и LR2 понижают - При этом средняя скорость сходимости Qk для алготестовой задачи ритмов mLL, LR1 и LR изменяется в пределах 1,0 6,0, в то время как для методов LL и SOR – нако это практически никак не сказалось на результатах решения алгоритмами mLL, LR1 и LR2. Чего нельзя сказать про методы SOR и точности (рисунок 5).

Расчеты также показали, что величина Qk сильно зависит от значения итерационного параметра - 2,5 % приводит к уменьшению средней скорости сходимости вплоть до LR порядка. Дальнейшее, еще большее еще где-то на порядок. Поэтому оценка оптимального значения Рисунок 5 – Кривые сходимости графе третьей главы методом раз- ||R || оценки оптимального значения Для алгоритма LR1 она выражается в виде = 1 1h + O (h ), в то время как для алгоритма LR2 – в статистического анализа результа- - тов проведенных расчетов получеk ны оценки константы. Для LR1 lg ||R || 1 ~ 10, а для LR2 2 ~ 100. При лить с относительной погрешностью в 100 %.

главы приводятся результаты более детального исследования характеристик алгоритмов LR1 и LR2. - Программа исследований включает в себя решение первой и второй условий (см. таблицу) на сетке 101101; 3) при четырех значениях сации: opt, 0,990opt, 0,975opt, 0, – задача Дирихле, сетка 101101.

Расчеты проводились с двойной Рисунок 6 – Кривые сходимости точностью представления чисел с решения первой тестовой предельно высоким требованием к задачи алгоритмом LR точности решения = 510.

На рисунке 6 представлены результаты применения алгоритма LR для решения первой тестовой задачи. Номера кривых на среднем фрагменте соответствуют типам граничных условий (см. таблицу). На первом шаге норма невязки уменьшается на 2–4 порядка, а заданная точность решения достигается за 20–30 итераций, то есть в среднем за одну итерацию норма невязки уменьшается от половины до целого порядка. При этом скорость сходимости слабо зависит от числа уравнений и от типа используемых граничных условий. Видно, что увеличение числа уравнений на два порядка приводит к понижению средней скорости сходимости приблизительно в три раза. При этом сами кривые Qk быстро выходят на свои асимптотические значения Q a = lim Q k. Их взаиморасположение хорошо укладывается в оценку Q 13 h. Аналогичная оценка для LR1 составляет Q 18 h.

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

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

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

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

В первом параграфе четвертой главы рассматривается технология автоматизации определения значения итерационного параметра компенсации индивидуально для каждого расчетного узла на каждом итерационном шаге [Zverev V.G. About the iteration method for solving difference equations // Lecture notes in computer science. – Berlin Heidelberg: Springer-Verlag. – 2005.

– Vol. 3401. – pp. 621–628]. Суть идеи заключается в минимизации влияния очередного приближения решения с предыдущего итерационного шага, для чего в правой части каждого уравнения выделяется сумма слагаемых, отражающая итерационный характер записи уравнения. Эта сумма приравнивается к нулю, а из полученного уравнения вычисляется значение. Тогда для алгоритма LR1 формула расчета переменного значения итерационного параметра компенсации при проходе вдоль x координаты имеет вид В (6) использовано естественное ограничение ij [0,1], а 0 = const – корректирующий множитель, «ручной» подбор которого усиливает результат оптимизации итерационного параметра компенсации. Аналогичная формула используется и вдоль координаты y. Для алгоритма LR2 имеет место подобное соотношение Рисунок 7 иллюстрирует результаты применения технологии автоматизации определения на примере решения первой тестовой задачи с граничным условием первого рода на сетке 401401. Поскольку в данном случае для LR2 opt = 1,0, на правом фрагменте рисунка два графика, а не четыре.

lg ||R0|| Рисунок 7 – Кривая: 1 – без автоматизации, = 0 = 1,0; 2 – с автоматизацией, 0 = 1,0; 3 – без автоматизации, = 0 = 0,9970; 4 – с автоматизацией, Расчеты показали, что технология автоматизации не исчерпывает всего потенциала оптимизации. Не для каждого алгоритма она эффективна: алгоритм LR2 практически не чувствителен к ее использованию. А «ручная»

оптимизация итерационного параметра компенсации как постоянного, так и переменного (с помощью 0) дает практически одинаковые результаты.

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

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

Расчеты показали, что средняя скорость сходимости Qk слабо меняется в процессе итераций в случае симметричной матрицы системы, для несимметричных матриц такое изменение заметнее. При этом и в том и другом случае для задачи Дирихле имеет место оценка Q a = lim Q k 25 h. Для LRs также справедлива полуэмпирическая оценка opt, полученная для алгоритма LR1. Что касается влияния точности предсказания величины параметра на процесс сходимости, то в качественном отношении оно имеет такой же характер, как и для алгоритмов LR1 и LR2.

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

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

На рисунке 8 представлены результаты решения второй тестовой задачи. Нумерация кривых совпадает с нумерацией кривых рисунка 6. Удвоенное по отношению к LR1 время выполнения одной итерации так же, как и для LRs, компенсируется приблизительно двойным сокращением количества итераций для достижения требуемой точности решения. Поэтому в целом можно утверждать, что алгоритм LRz является равноэффективным по скорости сходимости с алгоритмами LR1, LR2 и LRs. При этом средняя скорость сходимости Qk слабо меняется в процессе итераций и также имеет место оценка Q a = lim Q k 25 h для задачи Дирихле. А оценка оптимальноk го значения итерационного параметра компенсации, выполненная для алгоритма 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. Sci. Stat. Comput. – 1992. – Vol. 13. – № 2. – pp. 631–644] бисопряженным методом со стабилизацией и неявным итерационным полинейным рекуррентным методом. Эти задачи (в исходной работе – вторая, третья и четвертая) представляют собой интерес по двум причинам: во-первых, несмотря на явно условную формулировку, они обладают характерными особенноlg ||R0|| стями реальных физических задач; ||R-1|| во-вторых, их разностная аппрок- - симация приводит к СЛАУ с плохо = 10 проводились тремя вариантами бисопряженного метода: без предобуславливания (Bi-CGStab), с предобуславливателем, построен- - (Bi-CGStab P LU) и с предобуслав- lg ливателем, выполненным на базе (Bi-CGStab P B), а также всеми алгоритмами неявного итерационного полинейного рекуррентного метода. - зультаты решения второй и третьей модельных задач. Видно, что во второй задаче за разумное количе- - ство итераций (161) сходимость - решения с заданной точностью удаQk лось достичь только алгоритмом LR1. Алгоритм LRz также позволил решить задачу, но для этого потребовалось около двух тысяч итераций. В то же время все три реализации метода бисопряженных градиентов не позволили получить решение даже за 5 000 итераций.

ка 9 приведены результаты решения третьей задачи, при этом для схоk димости Bi-CGStab потребовалось более 500 итераций (около 2 500).

Графики отношений норм невяалгоритмом LRz зок решения четвертой модельной задачи приведены на рисунке 10. Видно, что отсутствие предобуславливателя резко снижает скорость сходимости метода бисопряженных градиентов и не позволяет понизить отношение норм невязок ниже величины порядка *5,010–3.

Рисунок 9 – Кривые сходимости для второй (слева) и третьей (справа) С другой стороны, алгоритмы LR1, LR2 и LRs стабилизировались в районе величины * 2,010–5 за первые 10 100 итераций, и только четвертый алгоритм LRz, что является принципиально важным, достиг требуемого уровня по точности =10–10, хотя для этого потребовалось провести около 2 000 итераций. Иными словами, на данной задаче подтвердились предполагаемые повышенные «разрешающие» возможности алгоритма LRz по отношению к алгоритмам LR1, LR2 и LRs.

Рисунок 10 – Кривые сходимости для четвертой модельной задачи В заключение формулируются выводы по всему материалу диссертации.

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

2. Разработано четыре алгоритма полинейного рекуррентного метода:

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

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

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

5. Предложена простая полуэмпирическая методика оценки оптимального значения постоянного параметра компенсации: для алгоритмов с линейной экстраполяцией приращения решения (LR1, LRs, LRz) opt 1 1h (1 10), для алгоритма с квадратичной экстраполяцией (LR2) – opt 1 2 h3 (2 100), где h – шаг сеточного разбиения.

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

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

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

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

Математика и механика. – 2010. – № 2. – С. 20–27.

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

– 2009. – № 2. – C. 71–77.

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

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

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

Изд-во ТГУ. – 2009. – C. 133–137.

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

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

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





Похожие работы:

«КРАВЕЦ Ирина Викторовна ФОРМИРОВАНИЕ МАРКЕТИНГОВОЙ КОМПЕТЕНТНОСТИ СТУДЕНТА ВУЗА 13.00.01 — общая педагогика, история педагогики и образования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Оренбург 2009 2 Работа выполнена на кафедре общей педагогики ГОУ ВПО Оренбургский государственный педагогический университет доктор педагогических наук, доцент Научный руководитель : Ганаева Елена Аркадьевна доктор педагогических наук, профессор,...»

«КАПАЛИН Алексей Михайлович СОЦИАЛЬНЫЕ ФУНКЦИИ ИНСТИТУТА РУССКОЙ ПРАВОСЛАВНОЙ ЦЕРКВИ 22.00.04 - Социальная структура, социальные институты и процессы АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата социологических наук Тюмень - 2009 1 Работа выполнена на кафедре социологии и социального управления ГОУ ВПО Тюменский государственный университет. Научный руководитель : доктор социологических наук, профессор Акулич Мария Михайловна Официальные оппоненты : доктор...»

«РУНГ Эдуард Валерьевич ПЕРСИДСКИЙ ФАКТОР В ПОЛИТИЧЕСКОЙ ЖИЗНИ ГРЕЦИИ в VI – IV вв. до н.э. Специальность 07.00.03 – Всеобщая история (История древнего мира) Автореферат диссертации на соискание ученой степени доктора исторических наук Казань – 2008 Работа выполнена на кафедре истории древнего мира и средних веков исторического факультета ГОУ ВПО Казанский государственный университет им. В.И. Ульянова-Ленина и кафедре истории древней Греции и Рима исторического факультета ГОУ...»

«МЕДВЕДКОВ Алексей Анатольевич СРЕДНЕТАЕЖНЫЕ ГЕОСИСТЕМЫ БАССЕЙНА р. ЕНИСЕЙ В УСЛОВИЯХ МЕНЯЮЩЕГОСЯ КЛИМАТА 25.00.36 - геоэкология (Науки о Земле) Автореферат диссертации на соискание ученой степени кандидата географических наук Москва – 2013 Работа выполнена на кафедре физической географии мира и геоэкологии географического факультета Московского государственного университета имени М.В. Ломоносова Научный руководитель : доктор географических наук, профессор Горшков Сергей...»

«АЛЕХИНА НОННА ВИКТОРОВНА ИНДИВИДУАЛЬНЫЙ ОБРАЗОВАТЕЛЬНЫЙ ПРОЕКТ КАК СРЕДСТВО САМООПРЕДЕЛЕНИЯ ГИМНАЗИСТА Специальность— 13.00.01 - Общая педагогика Автореферат диссертации на соискание ученой степени кандидата педагогических наук Оренбург 2000 Работа выполнена на кафедре общей педагогики и менеджмента Оренбургского государственного педагогического университета кандидат педагогических наук, доцент Сафонова Научный Зинаида Геннадьевна Официальные доктор педагогических наук,...»

«СТРЕЛЬНИКОВА ИРИНА АЛЕКСАНДРОВНА ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКИЕ МЕХАНИЗМЫ СНИЖЕНИЯ РИСКОВОСТИ НАУКОЕМКИХ ИНВЕСТИЦИОННЫХ ПРОЕКТОВ (НА ПРИМЕРЕ РАДИОЭЛЕКТРОННОГО КОМПЛЕКСА) Специальность 08.00.05 – Экономика и управление народным хозяйством (экономика, организация и управление предприятиями, отраслями, комплексами промышленности) Автореферат диссертации на соискание ученой степени кандидата экономических наук Москва – 2011 Диссертация выполнена на кафедре экономико-математического...»

«ГАНЬШИН Игорь Николаевич ФОРМИРОВАНИЕ и РЕАЛИЗАЦИЯ ПРИОРИТЕТНЫХ МЕЖГОСУДАРСТВЕННЫХ ОТНОШЕНИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ и КИТАЙСКОЙ НАРОДНОЙ РЕСПУБЛИКИ в 1991-2005 годы: ОПЫТ и ПЕРСПЕКТИВЫ Специальность: 07.00.02 – Отечественная история, 07.00.15 – История международных отношений и внешней политики Автореферат диссертации на соискание ученой степени кандидата исторических наук Москва - 2009 3 Работа выполнена на кафедре истории России Российского университета дружбы народов Научный...»

«ЮРЧЕНКО МАРИНА МИХАЙЛОВНА ПОЛИТИКА США В ОТНОШЕНИИ РЕФОРМИРОВАНИЯ ООН (2001-2008 гг.) Специальность 07.00.03 – всеобщая история (новая и новейшая история) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата исторических наук Тюмень 2010 Работа выполнена на кафедре новой истории и международных отношений ГОУ ВПО Тюменский государственный университет Научный руководитель : доктор исторических наук, профессор Кондратьев Сергей Витальевич Официальные оппоненты : доктор...»

«Исакова Анастасия Андреевна СОСТАВ, СТРУКТУРА И ФУНКЦИИ ЛЕКСИКО-СЕМАНТИЧЕСКОЙ ГРУППЫ ДЕНДРОНИМЫ В ХУДОЖЕСТВЕННОМ ТЕКСТЕ НАЧАЛА XX ВЕКА (на материале поэзии Серебряного века) 10.02.01 – русский язык АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата филологических наук Курск 2011 1 Работа выполнена на кафедре теории и истории русского языка Государственного образовательного учреждения высшего профессионального образования Брянский государственный университет имени...»

«Моаззен задех Зейнаб КАТЕГОРИЯ РУССКОЙ ИМЕННОЙ ЛОКАТИВНОСТИ В ЗЕРКАЛЕ ПЕРСИДСКОГО ЯЗЫКА (ПРАГМАТИЧЕСКИЙ АСПЕКТ) Специальность 10.02.01 – русский язык Автореферат диссертации на соискание ученой степени кандидата филологических наук Москва 2010 Работа выполнена на кафедре русского языка филологического факультета ФГОУ ВПО Московский государственный университет имени М.В. Ломоносова Научный руководитель : доктор филологических наук профессор Кортава Татьяна Владимировна...»

«ГАМАЛЕЙ МАКСИМ СЕРГЕЕВИЧ Трансформация морально-этической самооценки самурайского сословия в период Токугава (1603-1868) Специальность 07.00.03 – всеобщая история (новая и новейшая история) Автореферат диссертации на соискание ученой степени кандидата исторических наук Москва – 2012 Работа выполнена на кафедре всеобщей истории факультета гуманитарных и социальных наук Федерального государственного бюджетного образовательного учреждения высшего профессионального образования...»

«ЛУКАШОВ Олег Юрьевич ИССЛЕДОВАНИЕ ВОЛНОВЫХ ЭФФЕКТОВ, ВОЗНИКАЮЩИХ ПРИ РАСПРОСТРАНЕНИИ УДАРНЫХ ВОЛН ПО РАЗВЕТВЛЕННОЙ СЕТИ ГОРНЫХ ВЫРАБОТОК 01.02.05 – Механика жидкости, газа и плазмы Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Томск - 2003 2 Работа выполнена в Томском государственном университете. Научный руководитель : доктор технических наук, ст. н. с. Палеев Дмитрий Юрьевич Официальные оппоненты : доктор физико-математических наук...»

«Кручко Галина Викторовна СТАНОВЛЕНИЕ И РАЗВИТИЕ СИСТЕМЫ СОЦИАЛЬНОЙ ЗАЩИТЫ НАСЕЛЕНИЯ КРАСНОЯРСКОГО КРАЯ (1988 – 2004 гг.) Специальность 07.00.02 – отечественная история Автореферат диссертации на соискание ученой степени кандидата исторических наук Улан – Удэ 2008 Работа выполнена на кафедре философии и истории Гуманитарного института Сибирского Федерального Университета Научный руководитель : Доктор исторических наук, профессор Северьянов Михаил Дмитриевич Официальные...»

«Губайдуллин Айдар Рушанович ПРЕЕМСТВЕННОСТЬ В ПРАВОРЕАЛИЗАЦИИ Специальность 12.00.01 – теория и история права и государства; история учений о праве и государстве АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата юридических наук Казань 2006 4 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Казанский государственный университет им. В.И. Ульянова-Ленина Научный руководитель : доктор юридических наук, профессор...»

«Белая Елена Александровна ВЗАИМОДЕЙСТВИЕ И ФАЗООБРАЗОВАНИЕ В СИСТЕМЕ МЕЛКОДИСПЕРСНЫХ ОКСИДОВ TiO2–Cr2O3 Специальность 02.00.21 Химия твердого тела Автореферат диссертации на соискание ученой степени кандидата химических наук Челябинск 2008 Работа выполнена в ГОУ ВПО Челябинский государственный педагогический университет Научный руководитель : доктор химических наук, профессор Викторов Валерий Викторович Официальные оппоненты : доктор химических наук, профессор, член-кор РАН...»

«УДК 538.9+539.3 Янилкин Алексей Витальевич Атомистические механизмы и кинетика пластической деформации металлов при высокоскоростной деформации Специальность 01.04.07 - Физика конденсированного состояния Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Долгопрудный 2010 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Московский физико-технический институт (национальный...»

«Павков Дмитрий Петрович Институциональные аспекты организации финансового рынка (на примере рынка Forex) Специальность 08.00.01 – экономическая теория Автореферат диссертации на соискание ученой степени кандидата экономических наук Петрозаводск 2007 1 Работа выполнена на кафедре экономической теории и финансов Петрозаводского государственного университета Научный руководитель : доктор экономических наук, профессор Акулов Владимир Борисович Официальные оппоненты : доктор...»

«МАКСИМОВА СВЕТЛАНА НИКОЛАЕВНА ТЕНДЕНЦИИ РАЗВИТИЯ ПРЕПОДАВАНИЯ ДРЕВНИХ ЯЗЫКОВ В РУССКОЙ КЛАССИЧЕСКОЙ ГИМНАЗИИ XIX - НАЧАЛА XX ВЕКА 13.00.01 - общая педагогика, история педагогики и образования АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата педагогических наук Ижевск 2002 Работа выполнена на кафедре педагогики и педагогической психологии Удмуртского государственного университета. Научный руководитель : кандидат педагогических наук, доцент Кондратьева Марина...»

«Навицкайте Эдита Антоновна ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА СОЗДАНИЯ ОБРАЗА ИСЛАМСКОЙ УГРОЗЫ В АНГЛОЯЗЫЧНОМ МЕДИАДИСКУРСЕ Специальность 10.02.04 – германские языки АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата филологических наук Иркутск 2012 2 Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Иркутский государственный лингвистический университет Научный руководитель : кандидат филологических...»

«Калмыков Валерий Николаевич МАССОВЫЙ СОСТАВ ПЕРВИЧНОГО КОСМИЧЕСКОГО ИЗЛУЧЕНИЯ В РАЙОНЕ ИЗЛОМА ПО ДАННЫМ УСТАНОВКИ ШАЛ МГУ Специальность 01.04.23 – физика высоких энергий АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва 2007 Работа выполнена в Научно-исследовательском институте ядерной физики им....»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.