ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.04.2021
Просмотров: 2128
Скачиваний: 4
40
В результате пришли к
слабой формулировке
задачи 1. Она заключается в нахож-
дении тройки
(
u
,
H
, p
)
∈
H
1
(Ω)
×
V
T ,N
×
L
2
0
(Ω)
из (7), (8). Отметим, что при вы-
полнении условий (i)–(iii) не удается доказать разрешимость задачи (9) без допол-
нительных условий на исходные данные. А именно, вместо (v
0
) пусть выполняется
более жесткое условие (v)
j
∈
rot
V
T ,N
. Для вектора скорости достаточно потре-
бовать (vi)
g
∈
H
1
/
2
T
(Γ) :
g
|
Γ
1
=
0
. Рассматривая сужение (7) на подпространство
V
0
T
≡
V
×
V
T,N
, заключаем, что пара
(
u
,
H
)
удовлетворяет тождеству
ν
(
∇
u
,
∇
v
) +
ν
1
(rot
H
,
rot
Ψ
) + ((
u
· ∇
)
u
,
v
) +
κ
[(rot
Ψ
×
H
,
u
)
−
(rot
H
×
H
,
v
)] =
=
h
f
,
v
i
+
ν
1
(
j
,
rot
Ψ
)
∀
(
v
,
Ψ
)
∈
V
0
T
.
(9)
Лемма 2.2.
Пусть выполняются условия (i)-(vi) и пусть
(
u
,
H
)
∈
H
1
(Ω)
×
V
T ,N
– решение задачи (8), (9). Тогда существуют такие функции
p
∈
L
2
0
(Ω)
и
E
∈
H
(rot
,
Ω)
, что
E
×
n
|
Γ
1
=
0
, тройка
(
u
,
H
, p
)
удовлетворяет тождеству (7), а
четверка
(
u
,
H
, p,
E
)
удовлетворяет уравнениям (11) почти всюду в
Ω
и уравнени-
ям (1) в следующем смысле:
−
ν
∆
u
+ (
u
· ∇
)
u
−
κ
rot
H
×
H
+
∇
p
=
f
в
(
D
0
(Ω))
3
,
div
u
= 0
в
Ω
.
(10)
Теорема 2.1.
При выполнении условий (i)–(vi) существует слабое решение зада-
чи
1
(
u
,
H
, p
)
∈
H
1
(Ω)
×
V
T ,N
×
L
2
0
(Ω)
и справедливы оценки
k
u
k
1
6
M
u
,
k
H
k
1
6
M
H
,
(11)
где
M
u
,
M
H
– положительные неубывающие функции исходных данных задачи
1
:
f
,
j
и
g
.
Работа выполнена при финансовой поддержке РФФИ (проекты 13-01-00313-а
и 12-01-31288) и грантов ДВО РАН (проекты 12-I-П17-03 и 12-III-А-03-038).
Список литературы
1.
Fernandes P., Gilardi G. Magnetostatic and electrostatic problems in inhomogeneous
anisotropic media with irregular boundary and mixed boundary conditions // Math.
Mod. Meth. Appl. Sci. 1997. V. 7. P. 957–991.
2.
Auchmuty G., Alexander J.S. Finite energy solutions of mixed 3d div-curl systems //
Quarterly of applied mathematics. 2006. V. 64, N 2. P. 335-357
3.
Auchmuty G. The main inequality of 3d vector analysis // Math Modelling & Methods
in Appl. Sciences. 2004. V. 14. P. 79–103.
4.
Girault V., Raviart P.A. Finite element methods for Navier-Stokes equations. Theory and
algorithms. Berlin: Springer-Verlag, 1986.
5.
Valli A. Orthogonal decompositions of
L
2
(Ω)
3
. Preprint UTM 493. Department of
Mathematics. University of Toronto. Galamen 1995.
6.
Алексеев Г.В. Разрешимость задач управления для стационарных уравнений магнит-
ной гидродинамики вязкой жидкости // Сиб. мат. журн. 2004. Т. 45,
N
2. С. 243–262.
7.
Алексеев Г.В. Задачи управления для стационарных уравнений магнитной гидроди-
намики // Докл. РАН. 2004. Т. 395, N 3. С. 322–325.
8.
Алексеев Г.В., Бризицкий Р.В. Разрешимость смешанной задачи для стационарных
уравнений магнитной гидродинамики вязкой жидкости // Дальневост. мат. журн.
2002. Т. 3, N 2. С. 285–301.
9.
Алексеев Г.В., Бризицкий Р.В. Разрешимость обратных экстремальных задач для
стационарных уравнений магнитной гидродинамики вязкой жидкости со смешанны-
ми граничными условиями // Дальневост. мат. ж. 2003. Т.4. N 1. С. 108 - 126.
10.
Бризицкий Р.В., Терешко Д.А. О разрешимости краевых задач для стационарных
уравнений магнитной гидродинамики с неоднородными смешанными граничными
условиями // Дифференц. уравнения. 2007. Т. 43, N 2. С. 239–250.
11.
Schotzau D. Mixed finite element methods for stationary incompressible magneto-
hydrodynamics // Numer. Math. 2004. V. 96. P. 771–800.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
УДК 519.853.6:519.642.3
ПАРАЛЛЕЛЬНЫЕ ДВОЙСТВЕННЫЕ
АЛГОРИТМЫ ДЛЯ ЗАДАЧ
РЕГУЛЯРИЗАЦИИ
С НЕДИФФЕРЕНЦИРУЕМЫМ
СТАБИЛИЗАТОРОМ
А.С. Величко
Институт автоматики и процессов управления ДВО РАН
Россия, 690041, Владивосток, Радио 5
E-mail:
vandre@dvo.ru
Ключевые слова:
регуляризация, условная оптимизация, численные ме-
тоды, параллельный алгоритм
В работе рассматриваются подходы теории и численных методов для экстре-
мальных задач, используемые для решения задач регуляризации с недиф-
ференцируемыми стабилизирующими функционалами. Для возникающих
задач квадратичной оптимизации с линейными ограничениями использо-
ваны численные методы, в том числе параллельные, основанные на двой-
ственной постановке оптимизационной задачи и нелинейном методе Якоби.
Предлагаемый подход используется для решения некорректных задач регу-
ляризации большой размерности для интегрального уравнения Фредгольма
1 рода, которая в частности возникает в задаче восстановления гравитаци-
онного поля Земли в математической геофизике.
Введение
В работах Васина В.В., Агеева А.Л. [1, 2] рассматривается метод регуляризации
для решения некорректно поставленной задачи для операторного уравнения
Au
=
f
.
Классическая тихоновская регуляризация не всегда позволяет с приемлемым каче-
ством восстановить истинное решение, поскольку функционалы, содержащие норму
пространства Соболева, могут обладают сильным регуляризующим эффектом, что
приводит к заглаживанию тонкой структуры решения. Восстановление решений с
высокой степенью точности в частности требует мелкой сетки, что вызывает необ-
ходимость решать задачи большой размерности. Небольшие значения параметра
регуляризации вызывают неустойчивость численных методов решения возникаю-
щих задач оптимизации. Использование стабилизирующих функционалов другого
типа приводит к необходимости решать оптимизационные задачи с недифференци-
руемым функционалом, особенности поиска решений которых являются предметом
данной работы.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
42
1.
Методы регуляризации и задачи
оптимизации
1.1.
Регуляризация для уравнения Фредгольма
В качестве примеров использования данного подхода в работах [3, 4] рассмат-
ривалось интегральное уравнения Фредгольма
b
Z
a
K
(
t, s
)
u
(
s
)
ds
=
y
(
t
)
, для которого
возникает задача безусловной недифференцируемой оптимизации
min
{
u
j
}
n
m
X
i
=1
h
m
h
n
X
j
=1
h
n
K
(
t
i
, s
j
)
u
j
−
y
i
+
n
X
j
=1
h
n
K
(
t
i
, s
j
)
u
j
−
y
i
2
i
+
αh
n
n
X
j
=1
u
2
j
o
.
(1)
где
h
n
, h
m
– шаги сетки,
α
– параметр регуляризации, здесь и далее для кратко-
сти обозначений
u
j
=
u
(
s
j
)
, y
i
=
y
(
t
i
)
. Классическая тихоновская регуляризация
предполагает решение квадратичной задачи безусловной оптимизации
min
{
u
j
}
n
m
X
i
=1
h
m
n
X
j
=1
h
n
K
(
t
i
, s
j
)
u
j
−
y
i
2
+
αh
n
n
X
j
=1
u
2
j
o
.
(2)
1.2.
Задача условной оптимизации
В работах Васина В.В., Еремина И.И. [5, 6] использовались субградиентные,
проксимальные методы и методы решения систем неравенств с помощью проектив-
ных методов. Данные численные методы зачастую подвержены медленной скорости
сходимости, а для задач большой размерности эта проблема усиливается. С другой
стороны, альтернативой использования специальных методов негладкой оптимиза-
ции для решения задач (1)-(2) может служить их предварительное эквивалентное
преобразование к задачам квадратичной оптимизации с линейными ограничения-
ми, для которых существуют эффективные численные методы [7]. Для задачи (1)
возможно ее представление в виде:
min
{
u
j
,w
i
}
n
h
m
m
X
i
=1
w
i
+
h
m
m
X
i
=1
w
2
i
+
αh
n
n
X
j
=1
u
2
j
o
с линейными ограничениями
w
i
>
n
X
j
=1
hK
(
t
i
, s
j
)
u
j
−
y
i
, w
i
>
−
n
X
j
=1
hK
(
t
i
, s
j
)
u
j
−
y
i
.
Данный прием не является универсальным, а обусловлен наличием задачи именно
на минимум оптимизируемого функционала.
2.
Двойственное представление задачи,
численные методы и алгоритмы
2.1.
Двойственная постановка
Следуя [8], представим последнюю задачу, для краткости записанную в виде
min
x
{
(1
/
2)
x
0
Qx
+
c
0
x, Ax
6
b
}
, в двойственной постановке
min
p
{
(1
/
2)
p
0
Dp
+
d
0
p, p
>
0
}
.
Здесь
D
=
AQ
−
1
A
0
, d
=
b
+
AQ
−
1
c
и для оптимальных решений прямой и двойствен-
ной постановки задачи выполняется соотношение
x
∗
=
−
Q
−
1
(
c
+
A
0
p
∗
)
.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
43
2.2.
Параллельный алгоритм
Идея параллельного алгоритма для решения двойственной задачи основана на
модификации нелинейного метода Якоби для задачи оптимизации, в котором на ша-
ге
(
s
+ 1)
параллельно решается
k
одномерных квадратичных подзадач. Значение
k
равно размерности двойственной переменной – вектора
p
. Подзадачи формируют-
ся, когда
i
принимает значения от
1
до
k
, и принимают вид
min
{
(1
/
2)
p
(
i
)
Dp
(
i
)
+
d
0
p
(
i
)
, p
i
>
0
}
, где
p
(
i
)
= (
p
s
1
, . . . , p
i
, . . . , p
s
k
)
. Особенностью параллельного алгоритма
является то, что на шаге
(
s
+ 1)
вектор
p
s
+1
= (
p
s
1
, . . . , p
i
∗
, . . . , p
s
k
)
определяется из
условия
i
∗
= argmin
i
{
(1
/
2)
p
(
i
)
Dp
(
i
)
+
d
0
p
(
i
)
}
.
2.3.
Вычислительные эксперименты
Параллельный алгоритм для многопроцессорной вычислительной архитектуры
с распределенной памятью реализован на языке Matlab и Octave [9] с использо-
ванием библиотеки функций интерфейса передачи сообщений MPI в реализации
‘OpenMPI’ [10] и пакета ‘OpenMPI Extension for Octave’ [11]. Расчеты проводятся
на многопроцессорном вычислительном комплексе Центра коллективного пользова-
ния Дальневосточного отделения РАН во Владивостоке «Дальневосточный вычис-
лительный ресурс» [12]. В численных расчетах ядро
K
(
t, s
)
уравнения Фредгольма
выбиралось в виде
H
(
t
−
s
)
2
+
H
2
, где
H
= 10
, что приводит к числу обусловленности для
матрицы с элементами
K
(
t
i
, s
i
)
порядка
10
16
. Модельные решения были представле-
ны функцией
u
(
s
) =
10
4
√
2
π
exp
{−
s
2
32
}
+
10
√
2
π
exp
{−
(
s
−
4)
2
2
}
на отрезке [-10,10]. Значения
правой части уравнения Фредгольма
y
(
t
)
брались не с использованием решения ин-
тегрального уравнения, а по аппроксимационной формуле для интеграла в узлах
t
i
,
когда берутся значения
u
(
s
j
)
по истинной (наперед заданной) функции
u
(
s
)
в узлах
сетки
s
j
. Параметр регуляризации
α
выбирался равным
10
−
6
. На рис. 1 показано
восстановление модельного решения с помощью решения рассматриваемой оптими-
зационной задачи, на рис. 2 – с помощью классической тихоновской регуляризации.
Величина «ускорения»
R
n
параллельного алгоритма определяется как отношение
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
-10
-5
0
5
10
u(s)
s
Рис. 1.
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
-10
-5
0
5
10
u(s)
s
Рис. 2.
времени выполнения алгоритма на одном процессоре к времени выполнения алго-
ритма на
n
параллельных процессорах. В соответствии с закона Амдала без учета
сетевых межпроцессорных обменов
R
n
=
n
(
n
−
1)
a
+1
, где
a
– доля непараллельного ко-
да алгоритма. При «идеальном» распараллелеливании процесса вычислений
a
= 0
,
и тогда
R
n
=
n
[8]. Для рассматриваемого в данной работе параллельного алгорит-
ма на рис. 3 сплошной линией показан график фактического ускорения (speedup),
пунктирной линией – аппроксимация теоретической зависимости для
R
n
с оценкой
для доли непараллельного кода алгоритма
a
= 0
,
04
.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.
44
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
speedup
processes
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
speedup
processes
Рис. 3.
Список литературы
1.
Васин В.В. Устойчивая аппроксимация негладких решений некорректно поставлен-
ных задач // ДАН. 2005. Т. 402, № 5. C. 586-589.
2.
Васин В.В., Агеев А.Л. Некорректные задачи с априорной информацией. Екатерин-
бург : Наука, 1993. 262 с.
3.
Vasin V.V., Korotkii M.A. Tikhonov regularization with nondifferentiable stabilizing
functionals // Journal of Inverse and Ill-posed Problems. 2007. Vol. 15, No 8. P. 853-
865.
4.
Васин В.В., Сережникова Т.И. Регулярный алгоритм аппроксимации негладких ре-
шений для интегральных уравнений Фредгольма первого рода // Вычислительные
технологии. 2010. Т. 15, № 2. С. 15-23.
5.
Васин В.В., Еремин И.И. Операторы и итерационные процессы фейровского типа.
Теория и приложения. Москва, Ижевск : НИЦ РХД, 2005.
6.
Васин В.В. Итерационные процессы фейеровского типа в некорректных задачах с
априорной информацией // Известия высших учебных заведений. Математика. 2009.
№2. С. 3-24.
7.
Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010. 274 с.
8.
Bertsekas D.P, Tsitsiklis J.N. Parallel and Distributed Computation: Numerical Methods.
Athena Scientific, 1997.
9.
GNU Octave.
http://www.octave.org
.
10.
OpenMPI.
http://www.open-mpi.org
.
11.
OpenMPI Extension for Octave.
http://octave.sourceforge.net/openmpi_ext/index.html
.
12.
Центр коллективного пользования ДВО РАН «Дальневосточный вычислительный
ресурс».
http://www.cc.dvo.ru
.
Сборник материалов XXXVII Дальневосточной Математической Школы-Семинара
имени академика Е.В. Золотова, Владивосток, 8 – 14 сентября 2013 г.