Применение методов оптимизации для решения систем нелинейных уравнений гидродинамики Текст научной статьи по специальности «Математика»
Аннотация научной статьи по математике, автор научной работы — Захаров Юрий Николаевич, Крутиков Владимир Николаевич, Вершинин Ярослав Николаевич
Исследована возможность решения разностных задач, аппроксимирующих стационарную систему уравнений Навье Стокса многошаговыми итерационными методами минимизации, обладающими свойствами метода сопряженных градиентов . Использовались метод сопряженных градиентов и многошаговый релаксационный субградиентый метод.
Похожие темы научных работ по математике , автор научной работы — Захаров Юрий Николаевич, Крутиков Владимир Николаевич, Вершинин Ярослав Николаевич
Optimization methods for solving systems of hydrodynamics nonlinear equations
There are two approaches to numerical solving steady state problems for the system of Navier-Stokes equations describing the motion of a viscous homogeneous incompressible fluid. One of them, that is most commonly used, is reduced to the solution of the non-stationary problem for the Navier-Stokes equations by an approximate method and obtaining steady solutions in the limit. Another, less popular, method is to construct a system of nonlinear algebraic equations (SNAE) using any approximation of the stationary problem solved; then, the resulting system is solved by iterative methods. Each approach has its advantages and disadvantages. The main advantages of the second approach to the solution of stationary problems are: (1) in the process of convergence of the iterative process, the condition of noncompressibility is satisfied automatically; (2) one can use boundary conditions that are hard to implement in the usual way; (3) the method for solving stationary problems does not depend on the method of replacing the system of equations by a SNAE. Disadvantages of this approach are related to the fact that the iterative solutions of the SNAE for its convergence require restrictions on the nonlinear system operators and the initial approximation, which significantly limits the possibility of using this method for solving stationary problems. The partial approximation method for solving difference problems approximating various stationary problems for the Navier-Stokes equations , based on the minimization of the residual norm minimization by specialized methods, was used earlier and proved to be effective. The possibility of solving difference problems approximating the stationary Navier-Stokes equations , multi-step iterative minimization possessing the properties of the CG method is investigated in this paper using the method of conjugate gradients and multi-step relaxation subgradient method (MSRSM). The abovementioned optimization techniques have significant differences in the implementation and requirements to the accuracy of the one-dimensional descent. The conjugate gradient methods require a high precision search. The feature of relaxation subgradient methods, in particular, the MRSM, is the search of the direction of descent for the current gradient-coordinated minimum in a neighborhood the size of which is determined by the step of minimization. This last remark explains the effectiveness of methods of this class in the rough one-dimensional search. Both the methods have successfully coped with the posed tasks within a reasonable time and high accuracy, which is confirmed by comparing the obtained results with known ones. These results allow us to expand the range of difference methods for solving problems approximating the stationary Navier-Stokes equations , which is particularly important under conditions of minimization of multiextremal functions, where it is often necessary to use several optimization methods.
Текст научной работы на тему «Применение методов оптимизации для решения систем нелинейных уравнений гидродинамики»
ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2015 Математика и механика № 5(37)
УДК 519.6 DOI 10.17223/19988621/37/2
Ю.Н. Захаров, В.Н. Крутиков, Я.Н. Вершинин
ПРИМЕНЕНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ ГИДРОДИНАМИКИ1
Исследована возможность решения разностных задач, аппроксимирующих стационарную систему уравнений Навье - Стокса многошаговыми итерационными методами минимизации, обладающими свойствами метода сопряженных градиентов. Использовались метод сопряженных градиентов и многошаговый релаксационный субградиентый метод.
Ключевые слова: уравнение Навье - Стокса, метод оптимизации, многошаговый метод минимизации, субградиентный метод, метод сопряженных градиентов.
Существуют два подхода численного решения стационарных задач для системы уравнений Навье - Стокса, описывающей движение вязкой однородной несжимаемой жидкости. Один, и он наиболее часто используемый, сводится к решению каким-либо приближённым методом нестационарной задачи для системы уравнений Навье - Стокса и получение в пределе установившегося решения. Другой, менее популярный метод, заключается в построении системы нелинейных алгебраических уравнений (СНАУ) с помощью какой-либо аппроксимации решаемой стационарной задачи, а затем полученная система решается итерационными методами. Обзор обоих подходов можно найти в [1]. Каждый из подходов имеет свои преимущества и недостатки. Главными достоинствами второго подхода к решению стационарных задач являются: 1) при сходимости итерационного процесса автоматически выполняется условие несжимаемости (div и = 0), 2) можно использовать сложно реализуемые обычным способом краевые условия (см. [2-4]); 3) такой способ решения стационарных задач не зависит от способа замены стационарной системы уравнений Навье - Стокса на СНАУ. Недостатки данного подхода связаны с тем фактом, что итерационные методы решения СНАУ для своей сходимости требуют ограничений на нелинейные операторы системы и начальное приближение, что существенно ограничивает возможность применение этого метода решения стационарных задач (см. [5-7]). В работах [1, 8-12] был рассмотрен итерационный метод неполной аппроксимации решения разностных задач аппроксимирующих различные стационарные задачи для системы уравнений Навье - Стокса, основанный на минимизации нормы невязки, который оказался достаточно эффективным при их решении.
Для минимизации нормы невязки можно использовать методы оптимизации (МО), которые применяются для поиска минимумов многомерных функций. В настоящей работе рассматривается возможность решения разностных задач, аппроксимирующих стационарную систему уравнений Навье - Стокса итерационными методами минимизации [13-23], которые обладают свойствами метода сопряженных градиентов на квадратичных функциях [13].
1 Работа выполнена в рамках проектной части государственного задания № 1.630.2014/К.
Применение методов оптимизации для решения систем нелинейных уравнений
1. Постановка задачи
Рассмотрим в ограниченной области Q следующую стационарную задачу:
и ■ Vu + Vp = v-Дм ; (1)
где Г граница Q, и - двухмерный или трехмерный вектор скоростей, p - давление, v - коэффициент кинематической вязкости, l (и) - некоторые краевые условия. В дальнейшем считаем, что задача (1) - (3) поставлена корректно.
Для решения задачи (1) - (3) будем использовать метод сеток (хотя все дальнейшие выкладки и выводы справедливы и для других численных методов решения задачи (1) - (3)), который заключается в построении сетки в области Q и замене слагаемых в (1) разностными соотношениями (см. [21-23]). В итоге получаем, с учетом краевых условий (3), систему нелинейных алгебраических уравнений (СНАУ), размерность которой пропорциональна числу точек в ПиГ, в которых необходимо вычислять скорость и давление. Таким образом, не углубляясь в методы замены задачи (1) - (3) СНАУ, в итоге имеем систему вида (более подробно смотри [1])
где и е RmA(u,и) = АДи,и) + А2и, А1(и,и) - билинейное отображение, А2 - линейный оператор в векторном пространстве Em компонент вектора скоростей и давления.
Один из подходов решения систем нелинейных уравнений (4), аппроксимирующих уравнения гидродинамики (1) - (3), состоит в сведении задачи решения системы уравнений
Г (и) = (А(и,и) - f) = 0, i = 1,2. m, и е Rm , (5)
к задаче минимизации нормы невязки (см. [1])
\\r\|2 = f (и) = X Г'2 (и), и е Rm. (6)
Здесь m - размерность задачи.
Развитые в [1] итерационные методы решения системы (4) основываются на специально разработанных схемах построения сопряженных направлений для задачи минимизации (6) и дают надежду на возможность использования специализированных методов оптимизации. В работе исследуется возможность решения систем уравнений гидродинамики (1) методами минимизации, использующими значения функции f(и) и градиента Vf(и). В отличие от специализированных методов, где кроме функции и градиента используется дополнительная информация в виде матриц, при использовании МО сокращается время подготовки задачи для счета. При использовании МО несложно наложить на решение дополнительные ограничения, например в виде функционалов регуляризации, которые трансформируются в дополнительные изменения вида функции f (и) (6). Другой важный фактор актуальности использования МО состоит в том, что их применение не наталкивается на ограничения характеристик функции, накладываемые итераци-
Ю.Н. Захаров, В.Н. Крутиков, Я.Н. Вершинин
онным процессом, например, на ограничения свойств матриц линеаризации уравнений (5) или гессиана (6). С другой стороны, поскольку при нелинейности уравнений (5) для МО не существует доказательства их сходимости к требуемому решению и оценок их скорости сходимости, то эти вопросы следует изучать на основании вычислительного опыта.
С учетом эффективности существующих универсальных МО градиентного типа, ограничимся исследованием возможности использования применительно к задаче (6) релаксационных методов, которые при определенных условиях на квадратичных функциях обладают свойствами метода сопряженных градиентов (МСГ) [13, 14]. Свойства МСГ следующие: 1) на квадратичных функциях последовательные направления спуска в МСГ являются сопряженными векторами, что обеспечивает конечное окончание процесса за число итераций, не превосходящее размерность задачи m [16], при этом генерация последовательности не требует хранения всей системы сопряженных векторов; 2) на гладких функциях, в силу справедливости квадратичного представления функции в некоторой локальной окрестности точки, свойство конечной сходимости метода на квадратичных функциях существенно влияет на увеличение скорости сходимости метода минимизации.
Свойством генерации последовательности сопряженных направлений обладают следующие классы методов: 1) методы сопряженных градиентов [13, 14];
2) квазиньютоновские методы [16, 17]; 3) многошаговые релаксационные субградиентные методы [24-29]; 4) релаксационные субградиентые методы с растяжением пространства [16-20]. Методы классов 1 и 2 основаны на квадратичной модели функции [13, 14], а алгоритмы классов 3 и 4 организованы по типу е -субградиентных методов [15]. В методах классов 1 и 3 требуемая память для хранения промежуточной информации и вычислительные затраты на итерации пропорциональны размерности пространства m. В методах классов 2 и 4 аналогичные затраты пропорциональны m2, что ограничивает их применение в задачах высокой размерности.
На предварительном этапе отбора методов при малых размерностях численно исследовались алгоритмы классов 2 и 4: квазиньютоновский метод, основанный на формуле BFGS [14] и субградиентный метод с растяжением - сжатием пространства [18]. Перечисленные алгоритмы по затратам вычислений функции и градиента минимизируемой функции на порядок превосходят используемые методы классов 1 и 3. В силу их неприменимости в задачах высокой размерности для решения поставленных задач использовались только методы классов 1 и 3.
2. Используемые методы оптимизации
Для решения задачи минимизации (6) было выбрано два метода, описание которых приведено ниже.
1. Общая схема релаксационного процесса минимизации. Итерация рассматриваемых в работе релаксационных МО с точным одномерным спуском имеет вид
un+1 = un-ansn , an = argmin f (un-asn), n = 0,1. (7)
где задается начальная точка u , а s - градиентно-согласованное направление спуска, т.е.(У/"(un), sn) > 0.
Применение методов оптимизации для решения систем нелинейных уравнений
2. Метод сопряжённых градиентов. В методах сопряженных градиентов (МСГ) направление спуска вычисляется по правилу
5° = g 0, sn = gn +ensn-\ n = 1,2. (8)
где параметр Pn = 0 при n кратном m, а при n не кратном m вычисляется по одной из формул [10, 11]:
Здесь принято обозначение gn = Vf(un), yn 1 = Vf(un)-Vf(un '). Схемы МСГ в
соответствии с (9) будем обозначать МСГа, МСГб и МСГв.
3. Многошаговый релаксационный субградиентый метод [21, 22]. Как отмечено в [14], зачастую метод сопряженных градиентов является единственным универсальным средством решения большеразмерных задач. К недостаткам метода следует отнести необходимость высокой точности одномерного спуска и быстрое накопление погрешностей в вычислении сопряженных направлений даже в случае квадратичных функций (см. [13, 14]). По этой причине в работе для решения гладких задач минимизации использован релаксационный субградиентый метод [21, 22], менее требовательный к точности одномерного спуска. Направление спуска этого алгоритма формируется по схеме [22]
gn, если (gn,gnV) > 0,
gn -■(g^^gn-1, если (gn,gn-1) <0.
Здесь gn = Vf (un).
Алгоритм (7), (10), (11) [22] (назовем его МРСМ) предложен в [22] для минимизации негладких функций и является упрощением алгоритма из [21]. На квадратичных функциях он генерирует последовательность приближений минимума, идентичную последовательности, генерируемой алгоритмами МСГ. Алгоритм МРСМ хорошо зарекомендовал себя при решении негладких задач высокой размерности. В работе [20] приводятся результаты решения этим методом регуляри-зованной задачи линейного программирования высокой размерности с двухсторонними ограничениями.
Отличия использованных алгоритмов существенно. В МРСМ используется менее точный одномерный поиск, нежели в МСГ. При обмене процедурами одномерной минимизации эффективность обоих методов резко снижается. Субградиентный метод МРСМ использует технику выбора направления спуска, согласованного с направлениями субградиента некоторой окрестности, что обеспечивает выход метода из этой окрестности с одновременным уменьшением минимизируемой функции [15]. Низкая точность одномерного поиска для субградиентных методов более предпочтительна, поскольку обеспечивает охват и последующий выход из более широкой окрестности.
Ю.Н. Захаров, В.Н. Крутиков, Я.Н. Вершинин
В реализациях методов МСГа, МСГб, МСГв и МРСМ использовался одномерный поиск с кубической интерполяцией, точность поиска минимума которого настроена так, чтобы минимизировать количество вычислений функции и градиента, необходимых для реализации метода.
3. Результаты численных расчётов
Прежде чем обсуждать представляемые результаты расчетов, следует отметить, что полученные нами решения, как в двухмерном, так и в трехмерном случаях, сравнивались с решениями, полученными другими авторами (см. [1, 27 - 32] и цитируемую там литературу). Это сопоставление показало, что наши результаты качественно и количественно совпадают с известными расчетами.
Для проверки возможности численного решения стационарных задач для системы уравнений (1) - (3) методами оптимизации решались следующие типичные и хорошо известные краевые задачи (см. [1]).
В дальнейшем двумерный вектор скорости имеет вид u = (u, v), а трехмерный
Рассмотрим следующие задачи:
Задача 1. Задача Дирихле для одномерного уравнения Бюргерса:
du du ,, ч u — = v —— + 1 (x).
где ф1, ф2 - заданные постоянные, l(x) - известная функция.
Задача 2. Двумерное течение в прямоугольном канале (рис. 1).
Задача 3. Двумерное течение в канале с уступом (рис. 2).
Задача 4. Двумерное течение в квадратной каверне (рис. 6).
Задача 5. Трехмерное течение в единичной кубической каверне (рис. 10).
В области решения введём равномерную согласованную с границей сетку, на которой аппроксимируем задачи 1 - 5 со вторым порядком. Для решения полученных разностных задач, являющихся системами нелинейных уравнений (4), использовались следующие алгоритмы минимизации МСГа и МРСМ (см. п.2). Функция и градиент во всех методах вычислялись одновременно. Останов алгоритма осуществлялся при достижении требуемой точности е по правилу
При решении отмеченных стационарных задач для системы уравнений (1) - (3) оказалось, что методы сопряженных градиентов МСГа, МСГб и МСГв практически эквивалентны. Поэтому приводим результаты только для метода МСГа.
В таблицах указаны размерность m, параметры используемых сеток, точность е, число итераций (It), количество вычислений функции и градиента (Nfg), необходимые для достижения заданной точности е . Сравнение методов будем проводить на основе величины Nfg, так как одно вычисление Nfg превосходит по вычислительной ёмкости алгоритмические затраты метода на одну итерацию в итерационных методах решения СНАУ.
Далее на всех рисунках приведены полученные линии тока, а в таблицах значения количества итераций, вычислений правых частей и градиента.
Применение методов оптимизации для решения систем нелинейных уравнений
В табл. 1 приведены результаты расчетов задачи Дирихле для разностной задачи
г-1 = vUi-1 - 2Ui + U+1 + L
Здесь правая часть и постоянные A, B заданы так, чтобы решение задачи (13) имело вид sin(nx)