Литература

Министерство общего и профессионального образования

Российской Федерации

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(Государственный университет)

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

На тему “ПРИМЕНЕНИЕ МНОГОСЕТОЧНОГО МЕТОДА

ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ”

Студента 6 курса ШКЛЯЕВА Андрея Александровича
Научный руководитель

к.ф.-м.н. Похилко В.И.

Москва

2008

Содержание

1. Введение 2

2. Описание многосеточного метода 3

3. Метод Ланцоша 4

4. Критерий сравнения обычного и многосеточного метода 4

5. Адаптивная сетка с локальным измельчением …………………………………5

6. Реализация многосеточного метода в программном комплексе FlowVision....6

7. Описание программного комплекса FlowVision ..................................................7

8. Результаты численных экспериментов ………………………………………….9

9. Заключение ………………………………………………………………………18

10. Литература ..…………………………………………………………………….19

1. Введение

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

(1.1)

Здесь - квадратная матрица размерности ( - количество неизвестных).

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

Одним из главных показателей сложности системы (1.1) является её “жесткость”, то есть отношение максимального собственного числа матрицы к минимальному числу. Жесткость задачи заключается в существовании нескольких компонент решения, которые имеют разный масштаб и конфликтуют друг с другом. Так гладкие компоненты можно эффективно аппроксимировать на грубых сетках, но они медленно сходятся на подробных сетках, и конфликтуют с высокочастотными компонентами, которые необходимо аппроксимировать с помощью подробных сеток.

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

Основоположником многосеточного метода считается Федоренко Р.П. [1-3]. В 1961 году он сформулировал многосеточный алгоритм для стандартной пятиточечной дискретизации уравнения Пуассона в единичном квадрате. Позднее его идеи получили развитие в работах Бахвалова Н.С. [4] и Шайдурова В. [5], а также в работах западных математиков – Бранта [6], Хакбуша, Троттенберга [7] и Йоппиха [8]. Последние внесли большой вклад в перенесении идей многосеточного алгоритма на область решения нелинейных уравнений, в разработку техники многоуровневой адаптации и метода вложенных итераций (полный многосеточный метод).

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

В настоящее время многосеточные алгоритмы эффективно применяются во многих программах (коммерческих кодах), которые позволяют решать различные задачи газо- и гидродинамики. Среди них выделим Fluent, CFX, STAR-CD, Cart3D и другие.

Данная работа посвящена реализации многосеточного метода в программном комплексе FlowVision [12], который позволяет решать широкий круг задач во всем диапазоне чисел Маха. Использование во FlowVision локально измельченных ортогональных сеток позволяет получать расчетные ячейки, размер которых может отличаться друг от друга в 100 раз. При этом количество расчетных ячеек может быть более миллиона. Это приводит к необходимости решать достаточно жесткую систему алгебраических уравнений (1.1).

2. Описание многосеточного метода

Пусть есть решение следующего линейного дифференциального уравнения

(2.1)

Обозначим через некоторое приближение к решению .

Тогда вместо уравнения (2.1) можно рассмотреть эквивалентное ему уравнение

(2.2)

где

(2.3)

(2.4)

Обозначим через разностный оператор, аппроксимирующий дифференциальный оператор L на сетке . Тогда вместо уравнений (2.1)-(2.2) будем иметь следующие системы линейных алгебраических уравнений (СЛАУ)

(2.5)

(2.6)

Изложим идею многосеточного метода на примере двух сеток – мелкой сетки и грубой сетки . При этом количество узлов грубой сетки значительно меньше количества узлов сетки .

Рассмотрим систему (2.5) на сетке , а (2.6) на сетке , то есть

(2.7)

(2.8)

Обозначим через некоторое приближение к решению .

п.1. Вычислим невязку (2.4)

(2.9)

п.2. Интерполируем невязку с сетки на сетку

(2.10)

п.3. Найдем решение системы (2.8) с помощью некоторого итерационного метода решения СЛАУ.

п.4. Интерполируем приращение с сетки на сетку

(2.11)

п.5. Найдем новое приближение

(2.12)

п.6. Если новое приближение не удовлетворяет системе (2.7), то сделаем некоторое (фиксированное) количество шагов итерационного метода решения СЛАУ. Если полученное приближение не удовлетворяет системе (2.7), то вернемся к выполнению п.1.

3. Метод Ланцоша

В данном разделе опишем метод Ланцоша [13], который применяется для решения несимметричных СЛАУ

(3.1)

Обозначим через Q некоторую матрицу

(3.2)

Здесь L – нижнетреугольная матрица, U – верхнетреугольная матрица.

Если ненулевые элементы матрицы A совпадают (или близки) к элементам матрицы Q, то матрицу Q называют предобуславливателем матрицы A.

Обозначим через

(3.3) ,

где I – единичная матрица.

Пусть дано некоторое начальное приближение . Вычислим .

Рассмотрим следующую итерационную процедуру

(3.4)

(3.5)

(3.6)

(3.7)

(3.8)

(3.9) , если ()

4. Критерий сравнения обычного и многосеточного метода

Из описания метода Ланцоша следует, что за один шаг этого метода будет произведено следующее количество операций умножения/деления

(4.1)

Здесь через обозначено количество ненулевых элементов матрицы A.

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

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

(4.2)

Отсюда получим

(4.3)

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

Таким образом, ускорение, достигаемое с помощью многосеточной процедуры, будет равно

(4.4)

  1. Литература.

    Литература
    3 Дорман, В. Н.Совершенствование управления затратами предприятия посредством углубления процессов бюджетирования Финансовый менеджмент.-2003г.-№5-стр.
  2. Литература (41)

    Литература
    Banerji A., Archeological History of Mewar-I (from 3rd Century B. C. to C. 300 A. D.), — «Journal of the Oriental Institute University of Baroda». 1963, June.
  3. Литература 1 (1)

    Литература
    11. «Под всеми всадниками были все как один бурые аргамаки. Впереди других понесся витязь всех бойчее, всех красивее». Это в повести Н. В. Гоголя «Тарас Бульба» описание
  4. Литература 1 (19)

    Литература
  5. Литература 1 (14)

    Литература
    К/ф построен в форме диалога А. П. Чехова с современниками, позволяет учащимся ощутить гуманизм и человечность великого писателя. Использованы фрагменты из художественных фильмов :
  6. Литература 

    Литература
    ЛИТЕРАТУРА В соответствии с Положением о государственной (итоговой) аттестации выпускников 9 и 11(12) классов общеобразовательных учреждений форму проведения устных экзаменов устанавливает общеобразовательное учреждение.
  7. Литература и программные продукты для подготовки к цт 

    Литература
    Централизованное тестирование. Английский язык : сборник тестов / Респ. ин-т контроля знаний М-ва образования Респ. Беларусь. — Минск : Аверсэв, 2008. — 95 c.
  8. Литература к книге «Современники о маршале Рокоссовском»

    Литература
    "Роман газета" № 5 98г. И№ 7 1998 г. Алексеев Сергей. Богатырские фамилии. Москва 1991г. Алексиевич С. У войны неженское лицо./Имя его известно.
  9. Литература. 10 класс ( 2 урока). Тема: значимость художественной детали в романе Ф. М. Достоевского «Преступление и наказание» тексте. Идейно- художественное значение эпизода «Сон Раскольникова» ( ч I гл. 5). Связь сна Раскольникова с идеей романа

    Литература
    Тема: значимость художественной детали в романе Ф.М. Достоевского «Преступление и наказание» тексте. Идейно- художественное значение эпизода «Сон Раскольникова» ( ч I гл.
  10. Литература по курсу «Введение в искусство»

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

Другие похожие документы..