Содержание к диссертации
Введение
1 Итерационные методы решения СЛАУ: обзор литературы 14
2 Формулировка задачи и алгоритм неявного итерационного полинейного рекуррентного метода 23
2.1 Получение системы разностных эллиптических уравнений с матрицей положительного типа 23
2.2 Алгоритм неявного итерационного полинейного рекуррентного метода с линейной экстраполяцией приращения решения 27
2.2.1 Общая идея метода 27
2.2.2 Методика преобразований разностных уравнений в локальном направлении 30
2.2.3 Алгоритм преобразований исходной СЛАУ 36
2.3 Алгоритм неявного итерационного полинейного рекуррентного метода с квадратичной экстраполяцией приращения решения 48
2.4 Обоснование корректности неявного итерационного полинейного рекуррентного метода 51
3 Тестирование эффективности неявного итерационного полинейного рекуррентного метода решения СЛАУ 71
3.1 Предварительная оценка эффективности неявного итерационного полинейного рекуррентного метода 71
3.1.1 Первая тестовая задача 74
3.1.2 Вторая тестовая задача 81
3.2 Полуэмпирическая оценка оптимального итерационного параметра компенсации... 88
3.2.1 Линейная экстраполяция приращения решения 89
3.2.2 Квадратичная экстраполяция приращения решения 92
3.3 Анализ эффективности неявного итерационного полинейного рекуррентного метода в широком диапазоне требований по точности 93
4 Развитие неявного итерационного полинейного рекуррентного метода решения СЛАУ 116
4.1 Применение технологии автоматической адаптации итерационного параметра компенсации 116
4.2 Алгоритм неявного итерационного по линейного рекуррентного метода с экстраполяцией приращения решения вдоль глобального координатного направления 124
4.2.1 Идея алгоритма на примере выбора глобального направления вдоль координаты 124
4.2.2 Модификация расчетных формул в случае автоматического определения параметра компенсации 131
4.2.3 Анализ результатов решения тестовых задач 132
4.3 Алгоритм неявного итерационного полинейного рекуррентного метода с экстраполяцией приращения решения по технологии модифицированного полинейного метода 148
4.3.1 Вывод расчетных формул 149
4.3.2 Модификация расчетных формул в случае автоматического определения параметра компенсации 150
4.3.3 Анализ результатов решения тестовых задач 151
4.4 Сравнительный анализ эффективности итерационных методов на примере решения модельных задач 163
4.4.1 Тестирование алгоритма метода Bi-CGStab 164
4.4.2 Вторая модельная задача 166
4.4.3 Третья модельная задача 169
4.4.4 Четвертая модельная задача 171
Заключение 177
Список используемой литературы 179
- Получение системы разностных эллиптических уравнений с матрицей положительного типа
- Алгоритм неявного итерационного полинейного рекуррентного метода с квадратичной экстраполяцией приращения решения
- Анализ эффективности неявного итерационного полинейного рекуррентного метода в широком диапазоне требований по точности
- Идея алгоритма на примере выбора глобального направления вдоль координаты
Введение к работе
Актуальность проблемы. Появление в начале второй половины XX столетия электронной вычислительной техники и ее интенсивное проникновение, в первую очередь, в научно-практическую деятельность человека привело к резкому ускорению разработок разнообразных вычислительных методов. В частности, их применение оказалось особенно эффективным для решения задач теплообмена, динамики жидкостей, электрофизики и так далее. Связано это с тем, что численный эксперимент по своей сути является относительно недорогим, оперативным и достаточно информативным методом исследования сложных нелинейных природных процессов.
Современные методы решения задач математической физики зачастую сводятся к разностной аппроксимации многомерных дифференциальных уравнений, что, в свою очередь, приводит к построению системы линейных алгебраических уравнений (СЛАУ), матрица которой имеет большую размерность и разреженно-упорядоченную структуру. Для одномерных по пространству задач матрица СЛАУ имеет трехдиагональную структуру. Такая система легко решается прямым экономичным методом скалярной прогонки, который, по сути, представляет собой специальный вид метода исключения Гаусса решения систем линейных уравнений. Для двух- и трехмерных задач количество диагоналей возрастает, как правило, до пяти и семи соответственно. Это, казалось бы, небольшое изменение структуры матрицы сильно усложняет процедуру нахождения решения системы. До сих пор не удалось разработать прямой, экономичный, устойчивый к ошибкам округления метод, способный решать СЛАУ для многомерных по пространству задач с линейной трудоемкостью относительно числа неизвестных, наподобие того, как это было сделано для одномерного случая.
С другой стороны, исходные уравнения задач математической физики, как правило, нелинейные по сути, что совместно с вышеуказанной проблемой пространственной многомерности предопределяет использование итерационных подходов при разработке методов решения подобных СЛАУ. Итерационным методам решения систем линейных уравнений посвящено огромное число исследований, нашедших свое отражение и обобщение в монографиях Д.К. и В.Н. Фаддеевых, А.А. Самарского и Е.С. Николаева, А.А. Самарского и П.Н. Вабищевича, Г.И. Марчука, Н.С. Бахвалова, В. Вазова и Дж. Форсайта, В.П. Ильина, Д. Янга, Ю.А. Кузнецова, Е. Вашпресса, Ю. Саада, Дж. Ортега и многих других. На смену широко распространенным в 50-70-е годы прошлого столетия методам Якоби, Га-усса-Зейделя, различным вариантам метода последовательной верхней релаксации и их блочным модификациям, а также методам переменных направлений и дробных шагов (Д. Писмэн и X. Рэчфорд, Н.Н. Яненко, М. Лиз, Г.И. Марчук, Дж. Дуглас) пришли итерационные градиентные методы (О. Аксельссон, Г. Голуб, Х.А. ван дер Ворст, В.П. Ильин, Ю. Саад, Р. Вайс, Ю.Н. Захаров, Р. Фройнд), восходящие к пионерским работам
Л.В. Канторовича, М.А. Красносельского, В.М. Фридмана, Г. Темпле, М. Хестенса и Е. Штифеля, В. Арнольди, К. Ланцоша.
Особое место занимают методы неполной факторизации, впервые предложенные Н.И. Булеевым, а также его принцип компенсации в силу их относительной простоты реализации и высокой эффективности решения СЛАУ. Систематическому изложению и развитию этого вопроса посвящены работы В.П. Ильина и В.П. Гинкина.
Несмотря на достигнутые успехи, исследования по совершенствованию итерационных методов решения СЛАУ далеки до завершения. В частности, это касается решения разностных эллиптических СЛАУ для многомерных задач. Очевидно, что, пока для таких задач не будет (если будет) создан прямой метод с линейной трудоемкостью относительно числа неизвестных, проблема повышения производительности итерационных методов будет оставаться актуальной.
В настоящее время наиболее перспективными можно считать те направления разработки новых методов решения СЛАУ, в которых на уровне алгоритма учитывается фундаментальное свойство краевых эллиптических задач обязательной чувствительности решения в каждой точке области определения задачи возмущения в любой иной, включая граничную, точке. Такая чувствительность обеспечивается современными градиентными методами, но не напрямую от точки к точке, а опосредованно, через коэффициенты, полученные при минимизации норм соответствующих функционалов. С другой стороны, прямой неявный метод исключения Гаусса полностью соответствует этому фундаментальному свойству, однако его применение затруднено большим числом операций, необходимых для его реализации. Следовательно, для разработки нового эффективного метода решения разностных эллиптических СЛАУ необходимо сочетать итерационный подход с максимально высокой степенью его неявности.
Целью диссертационной работы является построение итерационного максимально неявного метода решения больших систем линейных алгебраических уравнений с разреженными матрицами, возникающими при сеточных аппроксимациях двумерных эллиптических задач математической физики на регулярных сетках.
Основные задачи исследования состоят в следующем:
Разработка, обоснование и исследование эффективности неявного итерационного полинейного рекуррентного метода решения СЛАУ с пяти-диагональной матрицей положительного типа с применением ЭВМ.
Сравнительный анализ неявного итерационного полинейного рекуррентного и некоторых других известных методов на примерах решения СЛАУ с пятидиагональной матрицей положительного типа.
Научная новизна работы определяется следующими положениями: 1. Предложен неявный итерационный полинейный рекуррентный метод решения СЛАУ с пятидиагональной матрицей положительного типа, отличающийся от других подобных методов оригинальной неполной факторизацией матрицы исходной системы, позволяющей при построении
решения на текущем итерационном слое сводить к минимуму влияние приближения решения с предыдущего итерационного слоя.
На основе неявного итерационного полинейного рекуррентного метода разработано четыре алгоритма (LR1, LR2, LRs, LRz), позволяющих более эффективно строить решение разностных эллиптических СЛАУ с пя-тидиагональными матрицами положительного типа по сравнению с лучшими представителями современных методов решения подобных СЛАУ. Для каждого из алгоритмов получена простая полуэмпирическая оценка постоянного оптимального параметра компенсации. Теоретически показана корректность алгоритмов LR1 и LR2 в случае сходимости решения.
Исследована применимость в алгоритмах LR1, LR2, LRs и LRz технологии автоматизации определения переменного оптимального параметра компенсации В.Г. Зверева.
По результатам решения типичных тестовых и модельных задач проанализированы основные характеристики алгоритмов LR1, LR2, LRs и LRz: времени исполнения, средней скорости сходимости, вычислительной устойчивости - в зависимости от сеточного разбиения области (размерности матрицы), вида решаемого уравнения и типа граничных условий задачи, а также величины итерационного параметра компенсации.
Основные положения, выносимые на защиту:
Неявный итерационный полинейный рекуррентный метод решения СЛАУ с пятидиагональной матрицей положительного типа.
Четыре алгоритма (LR1, LR2, LRs, LRz), разработанные на основе неявного итерационного полинейного рекуррентного метода, для решения разностных эллиптических СЛАУ с пятидиагональными матрицами положительного типа и полученные для каждого из них простые полуэмпирические оценки постоянного оптимального параметра компенсации, а также теоретическое обоснование корректности алгоритмов LR1 и LR2 в случае сходимости решения.
Результаты применимости в алгоритмах LR1, LR2, LRs и LRz технологии автоматизации определения переменного оптимального параметра компенсации В.Г. Зверева.
Анализ основных характеристик алгоритмов LR1, LR2, LRs и LRz: времени исполнения, средней скорости сходимости, вычислительной устойчивости - в зависимости от сеточного разбиения области (размерности матрицы), вида решаемого уравнения и типа граничных условий задачи, а также величины итерационного параметра компенсации.
Достоверность полученных результатов следует:
из корректной математической постановки задач как дифференциальной, так и разностной;
из сравнения с аналитическими решениями при тестовых расчетах;
из постоянного контроля параметров сходимости в процессе построения итерационного решения предложенными алгоритмами: нормы невязки, нормы погрешности, средней скорости сходимости.
Теоретическая значимость. Разработан принципиально новый итерационный метод, позволяющий строить серию эффективных алгоритмов решения СЛАУ с пятидиагональной матрицей положительного типа, которые возникают в случае разностной дискретизации двумерных краевых эллиптических задач на регулярных сетках. Задачи обобщения данного метода на случай трех независимых переменных, а также построения на его основе эффективных предобуславливателей представляются вполне разрешимыми.
Практическая значимость. Неявный итерационный полинейный рекуррентный метод может быть использован для эффективного решения СЛАУ, получаемых при разностной аппроксимации краевых эллиптических задач математической физики в регулярных областях. Все алгоритмы метода характеризуются высокой скоростью сходимости, которая слабо зависит от размерности системы. Метод также может быть успешно использован для решения «жестких» систем с плохо обусловленными матрицами.
Личный вклад автора состоит в разработке алгоритмов неявного итерационного полинейного рекуррентного метода, проведении теоретического доказательства корректности алгоритмов LR1 и LR2, получении полуэмпирической оценки оптимального параметра компенсации, в исследовании основных характеристик алгоритмов метода и проведении сравнительного анализа с другими итерационными методами.
Апробирование. Основные результаты диссертации доложены на 7 конференциях и опубликованы в 9 работах, в том числе две работы - в журналах из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Объем диссертации составляет 187 страниц, работа содержит 22 таблицы и 92 рисунка. Список цитируемой литературы включает 108 наименований.
Получение системы разностных эллиптических уравнений с матрицей положительного типа
В [92] рассмотрены итерационные процессы, основанные на блочных //-расщеплениях квадратных матриц, причем показывается, что таким типом расщепления обладают только блочные //-матрицы. Исследована сходимость итерационных процессов, основанных на подобных расщеплениями блочных //-матриц (в общем случае комплекснозначных). Доказывается, что итерационные процессы, соответствующие этим расщеплениям, являются сходящимися. Показано, что норма итерационной матрицы, связанной со строго блочно-диагональным доминантным расщеплением, не превосходит единицы. Приводится верхняя оценка спектрального радиуса, зависящая от величины диагонального преобладания. Выводятся достаточные условия сходимости и даются некоторые оценки асимптотической скорости сходимости, результаты которых могут быть использованы при конструировании сходящихся блочных итерационных методов решения больших блочных систем линейных уравнений.
Исследованию краевых задач на основе решения уравнения Пуассона, посвящено большое количество как теоретических, так и численных работ. Многие из методов решения краевых задач опираются на использование расчетной сетки как регулярной, так и не регулярной, тогда как другие основываются на бессеточном подходе. В [93] при решении уравнения Пуассона с краевыми условиями Дирихле и Неймана представлены два альтернативных бессеточных метода - безэлементный метод Галеркина и модификация метода FP. Основой метода FP является метод наименьших квадратов. А по сути FP-мстод состоит в аппроксимации функции в произвольной точке области значениями функции в точках так называемой области поддержки или опорных точках. Основой данного метода служит разложение функции в ряд Тейлора с использованием опорных точек и последующим составлением систем линейных алгебраических уравнений с учетом удовлетворения уравнению Пуассона и граничным условиям. Расположение точек в области исследования не обязательно должно быть регулярным, что делает метод гибким при сложной геометрии рассматриваемой задачи.
При исследовании итерационных методов порядок сходимости является одним из важных показателей эффективности итерационного процесса. В работе [94] рассматривается итерационный метод второго порядка сходимости для решения СЛАУ, идея которого состоит в преобразовании на каждой итерации не только вектора решения, но и самой матрицы перехода. Подобный приём требует необходимости хранения большого объёма данных. На основе предложенного метода представлен алгоритм уже первого порядка сходимости с регулируемой нормой матрицы перехода, что позволяет эффективно распараллеливать процесс нахождения решения.
Предлагаемый в работе [95] метод является альтернативой разностным и вариационно-разностным алгоритмам решения краевой задачи с эллиптическим оператором второго порядка в двумерной области, когда двумерная область решения представляется в виде объединения прямоугольников, причем коэффициенты дифференциального оператора предполагаются в них кусочно-постоянными. Метод основан на расщеплении дифференциального оператора по координатам, с ориентацией на использование специфической системы базисных функций, обладающими высоким аппроксимирующим качеством, то есть на приближении решения малым числом базисных функций. Поиск решения двумерной задачи сводится к решению только одномерных с ориентацией алгоритма на достаточно малую размерность алгебраических систем уравнений и, соответственно, на быструю сходимость итерационного процесса и существенную экономию памяти ЭВМ.
При построении эффективных параллельных методов решения СЛАУ [96-105] на современных кластерных суперкомпьютерах используются многие из перечисленных методов: метод последовательной верхней релаксации, попеременно-треугольный метод А.А. Самарского, метод Зейделя с использованием различного рода предобуславливания, что, соответственно, повышает скорость сходимости методов. В настоящее время распараллеливание вычислительных процессов стало де-факто стандартом при решении сложных трехмерных задач динамики жидкости и теплообмена.
На основании проведенного обзора можно сделать вывод о том, что наиболее перспективным направлением развития вычислительных методов в области решения разностных эллиптических уравнений является направление максимального увеличения степени неявности метода, причем эта неявность в алгоритмическом плане должна выражаться рекуррентными соотношениями от узла к узлу разностной сетки разбиения области исследования. Иными словами на уровне вычислительных формул метода должен в некотором смысле моделироваться механизм «мгновенной» - за одну итерацию - передачи информации из любого узла сетки в любой другой узел. Нечто подобное происходит и в современных высокоэффективных градиентных методах, однако здесь имеет место не «поточечный» (детализированный) механизм передачи информации, а осредненный, поскольку в этом участвуют вспомогательные коэффициенты, полученные из условия глобальной по всей расчетной области минимизации соответствующих функционалов. С другой стороны рекуррентный механизм пересчета числовых полей плохо совместим с принципом распараллеливания вычислительного алгоритма, поскольку процесс вычислений в каком-либо узле должен «ждать», когда пройдут вычисления во всех предшествующих ему узлах. Выход из данной ситуации видится в сочетании сильно неявных «поточечных» методов с градиентными методами, ускоряющими сходимость метода в подпространствах Крылова. Такое сочетание, как известно, производится с помощью методов неполной факторизации Н.И. Булеева, когда на базе «хорошего» релаксационного метода создается качественный предобуславливатель, встраиваемый далее в алгоритм градиентного метода.
В заключении необходимо отметить, что по настоящее время одной из актуальных проблем вычислительной алгебры, как с теоретической, так и практической точки зрения, остаётся выбор оптимальных алгоритмов. Этот вопрос достаточно содержателен при решении разностных уравнений в силу большого объёма требуемых вычислений и наличия разнообразных итерационных алгоритмов, имеющих, в свою очередь, свободу в подборе счетных параметров.
Сравнение эффективности итерационных методов можно достаточно успешно проводить с помощью теоретических оценок скорости сходимости итераций. При этом надо иметь в виду, что подобные оценки не могут быть всеобъемлющими, поскольку они проводятся, как правило, для упрощенных постановок задач математической физики, и нередко имеют асимптотический характер, то есть, справедливы при И, є —» 0. К тому же не для каждого метода удается получить такие оценки.
Другой путь заключается в проведении численных экспериментов. Здесь требуется подбор характерных методических задач и чистота эксперимента, то есть аккуратность в соблюдении равных условий при сравнении различных итерационных методов. При этом понятие оптимального алгоритма имеет смысл в применении к решению определенного класса задач на конкретной вычислительной системе.
Алгоритм неявного итерационного полинейного рекуррентного метода с квадратичной экстраполяцией приращения решения
Подстановка (3.8) и (3.10) в (3.9) позволяет получить аналитическое выражение для источника S. Исходя из выбора рода граничного условия на какой-либо границе Q и (3.10) получаются значения (выражения) для коэффициентов av, Ьг, сг на этой границе. Например, если на границе {х=0, 0 у 1} используются условия первого рода, то аг = 0, Ьг = 1, с, = 0; если второго рода то а, = 1, Ьг = 0, сг = 2у2(\-у)2 и так далее. Выбор рода граничного условия является варьируемым параметром тестовой задачи. Описание типов граничных условий приведены в таблице 3.2.
При использовании четвертого типа граничных условий (задача Неймана) в целях стабилизации и, соответственно, сходимости решения использована методика осредненной коррекции источникового члена в каждом узле расчетной сетки таким образом, чтобы интегрально по всей области на разностном уровне точно выполнилась теорема Грина [107,108].
Разностная аппроксимация задачи проведена методом контрольного объема [2] на равномерной разностной сетке ік=1(х,,у : x,=(i-l)hx, } j-{j-\)hy\ l i n, \ j m\; hx=\l(n—l); A =l/(m —l)}. Начальное приближение решения выбрано постоянным по области Ф,у=1. Константа С\ выбиралось из соображения max(w(xj/))=l, следовательно Сі = 256. Пробные расчеты показали, что для всех рассматриваемых методов скорость сходимости слабо реагирует на изменение константы Сг. При варьировании ее значения от 2 до 2000, что соответствует 10 3 (vj/v ) 103, количество итераций, необходимых для сходимости решения, изменялось, в лучшем случае, не более чем в два раза. Поэтому этот параметр был принят равным Сг — 2 и в дальнейшем не менялся. В таблице 3.3 приведены результаты решения задачи Дирихле в виде количества итераций, необходимых для достижения заданной точности для различных сеточных разбиений области. В числителе приведено собственное количество итераций метода, а в знаменателе -условное. Все расчеты проведены при оптимальном — для каждого метода и каждой сетки -значении итерационного параметра компенсации (число в скобках), которое каждый раз определялось экспериментально путем серии пробных расчетов. Следует заметить, что под оптимальным итерационным параметром компенсации понимается такое его значение, которое позволяет достигать заданной точности за минимальное количество итераций. Число значащих цифр в значении итерационного параметра компенсации определялось из соображения дальнейшего неуменьшения количества необходимых итераций. Видно, что результаты в трех правых колонках (mLL, LR1, LR2) практически совпадают между собой. Любопытно, что при уменьшении сеточного шага LR2 дает понижение количества итераций с 2 до 1, то есть становится фактически прямым. Объясняется это, видимо, тем, что на мелких шагах формула квадратичной экстраполяции практически точно (до ошибок машинного округления) предсказывает значение приращения решения во «внешаблонном» сеточном узле. В таблице 3.4 приведены данные по количеству итераций, которые потребовались для решения задачи на сетке 101x101 при є =10 4. В качестве варьируемого параметра выступали разные типы граничных условий согласно таблице 3.2. Видно, что опять выделяется группа результатов в трех правых колонках. Методы mLL и LR1 дают практически идентичные результаты, а алгоритм LR2 демонстрирует несколько более высокую скорость сходимости. Здесь же следует отметить, что результаты решения задачи Неймана представляют собой самостоятельный весьма важный интерес. Дело в том, что в практических исследованиях наибольшую трудность представляет собой построение поля давления (точнее приращения давления) при моделировании несжимаемых течений [2]. Можно строго показать, что в этом случае решается задача Неймана. И от того, насколько точно и эффективно будет решаться эта задача, зависит успех всего процесса численного моделирования течения. Следует обратить внимание на то, что у всех рассматриваемых методов при решении задачи Неймана хоть и не намного, но все же понизилось оптимальное значение итерационного параметра компенсации. Уменьшение этого параметра приводит к повышению «инертности» при построении очередного итерационного приближения решения. В ситуации, когда не существует ни одного узла, в котором решение могло бы быть привязано по своему абсолютному значению, как при граничных условиях первого рода, такое увеличение «инертности» представляется естественным. Для иллюстрации временных затрат компьютера на построение решения тем или иным методом можно привести данные по времени решения задачи Дирихле на сетке 401x401 (последняя строка таблицы 3.3). Метод SOR - 374,0 сек, LL - 22,9 сек, mLL - 1,4 сек, LR1 -1,0 сек, LR2 - 0,5 сек. Расчеты проводились на PC AMD 1,66 Ггц, RAM 1 Гб, Compaq Visual Fortran На рисунке 3.2 приведены графики поведения отношения норм невязок висимости от условного номера итерации к . Решалась задача Дирихле на сетке 101x101 при оптимальных значениях итерационных параметров компенсации для каждого метода (таблица 3.3 — четвертая строка или таблица 3.4 — первая строка). Общее собственное количество итераций ограничивалось величиной 2500. Видно, что отношения норм невязок, достигнув величин 10" -е-10-7, далее перестают изменяться. Это связано с тем, что расчеты проводились с одинарной точностью, при котором длина мантиссы не превышает семи знаков.
На рисунках 3.3 и 3.4 представлены отношения норм погрешности и средней скорости сходимости методов также в зависимости от к . Нетрудно заметить, что на всех рисунках демонстрируется очевидное преимущество методов mLL, LR1 и LR2 перед классическими LL и SOR За один собственный итерационный шаг эти методы уменьшают нормы невязки и погрешности на 1 + 4 порядка.
Анализ эффективности неявного итерационного полинейного рекуррентного метода в широком диапазоне требований по точности
Объяснение столь необычного поведения кривых в области I связанно, видимо, с тем, что эффективность алгоритма LR2 (как, впрочем, и алгоритма LR1) напрямую зависит от точности предсказания поведения решения во «внешаблонном» узле. Тогда понятно, что чем мельче шаг разбиения и выше порядок экстраполяционной формулы, тем точнее предсказывается значение искомой функции в этом узле. При повышении требований по точности решения увеличивается количество итераций, сопровождаемое накоплением ошибок округления, которые тем значительнее, чем больше узлов разбиения (а следовательно, и уравнений) приходится обрабатывать в процессе построения решения. Именно поэтому в области III кривые сходимости ведут себя привычным образом: чем больше уравнений - тем медленнее сходится решение.
Результаты, представленные на рисунке 3.21, по смыслу те же самые, что и на рисунке 3.20, но полученные алгоритмом LR1. Они еще раз подтверждают правоту объяснения необычного поведения кривых в области I. Поскольку точность предсказания поведения решения во «внешаблонном» узле алгоритма LR1 ниже, чем у LR2, то переходное поведение кривых должно проявля гься раньше (при больших значениях точности расчетов) и выражаться менее наглядно. Действительно, на рисунке 3.21 слабое пересечение кривых имеет место в области I (а не II, как на рисунке 3.20) и не для всех сеточных разбиений.
В целях полноты исследования характеристик алгоритмов LR1 и LR2, в условиях предельно высоких требований по точности решения, было интересно систематизировано рассмотреть результаты расчетов этими методами первой и второй тестовых задач. Частично эти результаты по первой тестовой задаче представлены в таблице 3.9 (две крайние правые колонки) и на рисунках 3.20, 3.21; а по второй тестовой задаче - в таблице 3.10 (две крайние правые колонки). Также были проведены расчеты первой и второй тестовых задач с различными типами граничных условий (см. таблицу 3.2). Некоторые результаты проведенных расчетов представлены в таблице 3.11 (первая тестовая задача) и в таблице 3.12 (вторая тестовая задача) при следующих фиксированных параметрах: сеточное разбиение единичной области 101x101, критерий сходимости є = 5x10-14, итерационный параметр компенсации 9 подби рался исходя из требования минимизации количества итераций. Как обычно в числителе представлены собственные количества итераций, в знаменателе — условные, в скобках - 8ор(. По результатам таблиц видно, что усложнение постановки задачи, связанное с уменьшением числа граничных условий первого рода, приводит к замедлению сходимости. С другой стороны самосопряженность матрицы А системы влияния на темпы сходимости не оказывает. Также для обеих задач имеет место слабо выраженная тенденция увеличения значения Qopt по мере уменьшения числа граничных условий первого рода. Особо следует отметить крайнюю правую колонку таблиц (тип граничных условий 4, задача Неймана). Для данной задачи устойчивая сходимость наблюдается при є 10 12 при условии применения специального корректирующего процесс сходимости алгоритма, упомянутого в параграфе 3.1.1. И даже в этом случае, как будет показано далее, не всегда численное решение системы стремится к изначальному аналитическому тестовой задачи. В общем случае они могут отличаться на константу, что, впрочем, корректно в рамках задачи Неймана. Поэтому здесь и далее для данной задачи выбирается пониженное требование по точности є = 5х Ю-12. Примечание — Результаты расчета первой тестовой задачи алгоритмом LR1. Сетка 101x101. s = 5xl0- . Номера кривых соответствуют номеру граничного условия: 1 — тип г.у. 0; 2 - тип г.у. 1; 3 - тип г.у. 2; 4 - тип г.у. 3; 5 — тип г.у. 4.
На рисунках 3.22 и 3.23 представлены графики изменения отношения норм невязки при решении первой тестовой задачи в зависимости от номера итерации для разных типов граничных условий алгоритмов LR1 и LR2 соответственно. Видно, что для обоих алгоритмов характерно первоначальное уменьшение нормы невязки приблизительно на три порядка, исключение составляет задача Неймана (кривая 5), решение которой сходится медленнее всего (по крайней мере на начальном этапе итераций). Более плотное расположение кривых на рисунке 3.23 говорит о том, что алгоритм LR2 менее чувствителен к типу граничных условий, чем алгоритм LR1.
Важнейшей характеристикой процесса сходимости решения является её средняя скорость г (см. формулу (3.6)) и те асимптотические значения (f, к которым она стремится при k — оо. На рисунке 3.24 приведены зависимости средней скорости сходимости от номера итерации при решении первой тестовой задачи для различных сеточных разбиений области решения Q. Хорошо видно, что практически для всех расчетов средняя скорость сходимости в процессе итераций меняется слабо, достаточно быстро достигая своего предельного асимптотического значения. Обращает на себя внимание, что хотя на начальном этапе итераций значение (У для алгоритма LR2 как правило выше, чем для алгоритма LR1, но в итоге, при выходе величин скорости сходимости на свои асимптотические значения, они оказываются выше для LR1, чем для LR2. Достаточно большие величины Cf — в диапазоне от 0,7 до 2,5 говорят о том, что за одну итерацию погрешность в среднем уменьшается в 2 -г 10 раз.
Взаимное расположение кривых на рисунке 3.24 также позволяет оценить зависимость средней скорости сходимости СТ от величины сеточного шага h. В частности, хорошо видно, что при уменьшении h на порядок (увеличение числа уравнений в сто раз) величина СТ уменьшается приблизительно в три раза. В более общем виде эту зависимость можно оценить формулой О Constyjh , где под Q понимается предельное (асимптотическое) значение Cf при к -» оо.
На рисунке 3.25 представлены графики зависимостей СТ от к при решении первой тестовой задачи для различных типов граничных условий. Здесь, как и на рисунке 3.24, следует отметить как собственно высокие значения СТ, так и достаточно быстрый выход величин СТ на свои асимптоты. Более плотное расположение кривых на рисунке 3.25 б) (алгоритм LR2) естественным образом согласуется с результатами рисунка 3.23, иллюстрируя более слабую зависимость алгоритма LR2 от типа граничных условий.
Идея алгоритма на примере выбора глобального направления вдоль координаты
Видно, что максимальные отклонения имеют место для второй тестовой задачи, но так же как и в параграфе 3.3, в целом процент отклонения не выходит за рамки одного процента и, тем самым, обеспечивает достаточно точную первоначальную оценку значения итерационного параметра компенсации.
И, в заключение, следует обсудить результаты использования технологии адаптации итерационного параметра, которые представлены в таблице 4.5. Решалась, как и в параграфе 4.1, первая задача при следующих параметрах: расчетная область — единичный квадрат, граничные условия первого рода по всем границам; С\ = 256, Сг - 2, Ф = 1, є = 5х10 14. В отличие от аналогичных данных таблицы 4.1 здесь отсутствуют результаты для случая не оптимизированного 6 = 1, (90=1) поскольку, как уже отмечалось ранее, при 9. 9 1 построение решения алгоритмом LRs приводит к его расходимости. Аналогичная ситуация наблюдается и при расчетах алгоритмом LRsa. В целях сохранения структуры представления результатов аналогичной параграфу 4.1 для неоптимизированных 8(90)были выбраны значения: 0,900; 0,990; 0,998, - при которых заведомо имела место сходимость решения. Это позволило оценить эффективность не только технологии адаптации, но и степени приближенности в и opt. Хорошо видно, что отличие в от Вор1 на 1% увеличивает количество необходимых для сходимости решения итераций в несколько раз, а отличие 0 от Qopt на 10% - на порядок и более. Еще одна любопытная деталь: применение адаптивного 9 не только уменьшает количество итераций (6 = 90 = 0,990), как это было в параграфе 4.1, но и увеличивает их (8 = 90 = 0,998). Причем чем ближе 9 к впр, (на мелких сетках), тем заметнее это увеличение (правая часть таблицы 4.5). В то время как для в удаленных от Qopl использование переменного 9 никак не влияет на эффективность метода: количество итераций, необходимых для сходимости решения, практически совпадают. Правда имеет место одно исключение - расчет на сетке 401x401 при 0 = 00= 0,9. Здесь использование технологии адаптации привело к 25-30% увеличению числа итераций. И все-таки, это не идет ни в какое сравнение со случаями оптимизированного 9, когда на той же самой сетке 401x401 использование переменного итерационного параметра компенсации привело к трехкратному увеличению числа итераций. В итоге по результатам данного параграфа можно сделать следующие выводы: 1. Разработан третий алгоритм неявного итерационного полинейного рекуррентного метода (LRs) с экстраполяцией приращения решения первого порядка вдоль глобального направления. 2. Эффективность и качественное поведение процесса сходимости решения алгоритмом LRs являются практически такими же, как и LR1 и LR2. При этом возросшее количество операций на одну итерацию соответствующим образом компенсируется уменьшением числа итераций, необходимых для сходимости решения. 3. Средняя скорость сходимости Ок слабо меняется в процессе итераций и имеет место оценка Qa х 25y[h для задачи Дирихле, где Qa = lim Qk. 4. Полуэмпирические оценки оптимального значения итерационного параметра компенсации, выполненные для алгоритма LR1, также хорошо выполняются и для алгоритма LRs. 5. При оптимизации сходимости по параметру 9 для алгоритма LRs имеет место существенная неустойчивость тем большая, чем ближе 9 к Qopt, что сильно затрудняет сам процесс оптимизации. 6. Использование технологии адаптации итерационного параметра компенсации для алгоритма LRs в общем случае замедляет процесс сходимости решения. Алгоритм неявного итерационного полинейного рекуррентного метода с экстраполяцией приращения решения по технологии модифицированного полинейного метода Как уже отмечалось в параграфе 2.2, отсутствие точного соотношения, связывающего значение компоненты вектора решения Ф в так называемом «внешаблонном» узле с остальными компонентами Ф рассматриваемого разностного шаблона, приводит к необходимости использования приближенных формул, откуда, в свою очередь, вытекает итерационный характер метода. Понятно, что в общем случае качество используемых приближений должно отражаться на эффективности получаемых алгоритмах метода. Именно в этом направлении могут открывается перспективы по улучшению его вычислительных характеристик. Общую стратегию построения замыкающих «внешаблонный» узел алгоритмов можно сформулировать следующим образом: чем точнее (в идеале точно) выражается компонента вектора решения во «внешаблонном» узле через компоненты в остальных узлах шаблона, тем эффективнее алгоритм полинейного рекуррентного метода (в идеале он должен стать прямым). Идея рассматриваемого в данном разделе алгоритма метода (в дальнейшем LRz) состоит в том, чтобы для исключения компоненты Ф во «внешаблонном» узле воспользоваться способом определения двухточечных связей поперек глобального направления (вдоль направления локальных прогонок) из модифицированного полинейного метода (mLL) [24]. То есть для глобального направления вдоль координаты л: использовать соотношения типа в случае локального прохода по направлению возрастания индекса/ и соотношение типа в случае прохода при уменьшении/ Расчетные формулы для коэффициентов , ,г\ и Ну таковы, что значения % и вычисляются один раз, а величины ц и ц подправляются на каждой итерации, так как зависят от искомого решения. Причем, что важно, эти формулы строятся на базе самих разностных уравнений и, следовательно, по мере сходимости решения становятся всё более точными. Иными словами выражения (4.42) и (4.43) для сошедшегося решения представляют собой точные (вернее практически точные) двухточечные связи компонентов вектора решения.
