close

Вход

Забыли?

вход по аккаунту

?

О монотонном алгоритме решения задачи аппроксимации сегментной функции алгебраическим полиномом с ограничением.

код для вставкиСкачать
И. Ю. Выгодчикова
О МОНОТОННОМ АЛГОРИТМЕ РЕШЕНИЯ ЗАДАЧИ
АППРОКСИМАЦИИ СЕГМЕНТНОЙ ФУНКЦИИ
АЛГЕБРАИЧЕСКИМ ПОЛИНОМОМ С ОГРАНИЧЕНИЕМ
Пусть T
= {t0 < t1 < ... < tN }, A = (a0 , a1 , . . . , an ) ? Rn+1 ,
pn (A, t) = a0 + a1 t + . . . + an tn , N ? n + 1, ?(·) сегментная
функция, ?(tk ) = [y1,k ; y2,k ], y2,k ? y1,k , k = 0, N , ? s ? 0, N : y2,s =
y1,s := ys . Обозначим f (A, k) :=
max {pn (A, tk ) ? y1,k , y2,k ? pn (A, tk )},
n+1
D := A ? R
: pn (A, ts ) = ys . Рассматривается задача
?(A) := max f (A, k) ?? min .
(1)
A?D
k=0,N
Базисом назовјм любое множество ? := tj0 < ...tjr < ... < tjn+1 ? T
с фиксированной точкой tjr = ts , ? - множество всех базисов. Пусть
i ? {0, 1} и ?i (?, tjk ) = y0.5(3+(?1)k+i ), jk , k = 0, n + 1.
Наряду с (1) рассмотрим вспомогательную задачу
?i (A, ?) := max |?i (?, tjk ) ? pn (A, tjk )| ?? min .
A?D
k=0,n+1
(2)
Рассуждениями, аналогичными в работе [1], нетрудно доказать существование решения задачи (1) и следующие два утверждения.
Теорема. Решение задачи (1) единственно. Вектор A ? Rn+1 является решением задачи (2) тогда и только тогда, когда для некоторого hi (?)
выполняются равенства ("прерванный альтернанс"):
?i (?, tjk ) ? pn (A, tjk ) = (?1)k+i hi (?) , k = 0, n + 1 \ {r} ,
(3)
pn (A, tjr ) = ys .
(4)
Теорема 2. Пусть решение задачи (1) единственно. Для того чтобы
вектор A ? Rn+1 был решением задачи (1), необходимо и достаточно,
чтобы нашјлся такой базис ? ? ?, чтобы для i = 0 или i = 1 выполнялись равенства (3)-(4) и ? (A) = hi (?).
Обозначим минимальные значения целевых функций задач (1) и (2)
?
? и ??i (?) соответственно. Ввиду теорем 1, 2 в случае единственности
решения задачи (1) имеем
?? =
max
i?{0,1},???
20
??i (?) .
(5)
Теорема 3. Пусть решение задачи (1) единственно, h ? 0, w > 0,
e ? D выполняются соотношения
v ? 0, n + 1\{r}. Если для некоторого A
("частичный прерванный альтернанс"):
e
?i (?, tjk ) ? pn A, tjk = (?1)k+i h, k = 0, n + 1 \ {{r} ? {v}} ,
v+i
e
e
?i (?, tjv ) ? pn A, tjv = (?1) (h + w) , pn A, tjr = ys ,
то hi (?) из (3), (4) удовлетворяет неравенству hi (?) > h.
Доказательство. Поскольку А из (3)-(4) решение задачи
(2) по теореме 1 и оно единственно, то h + w > hi (?). Если
0
e
hi (?) ? h, то для полинома с вектором
коэффициентов A = A ? A
e tj
имеем (?1)k+i pn (A, tjk ) ? pn A,
k
= h ? hi (?) ? 0, k = 0, n + 1\
v+i
e
\ {{r} ? {v}}, (?1)
pn (A, tjv ) ? pn A, tjv
= h + w ? hi (?) > 0,
e tj . То есть (?1)k+i pn A0 , tj ? 0, k = 0, n + 1 \ {r},
pn (A, tjr ) = pn A,
k
r
0
pn A , tjr = 0.
1. Если r = 0, получаем (?1)k+i pn A0 , tjk ? 0, k = 1, n + 1. По
непрерывности
существуют точки {?k }, k = 1,n, tjk ? ?k ? tjk+1 :
0
: pn A , ?k = 0, k = 1, n. Поскольку pn A0 , tjr = 0, tjr < ?k , k = 1, n,
полином степени n имеет n + 1 нулей, значит, A0 ? 0, что в действительности не так. Аналогично рассматривается случай r = n + 1.
2. Пусть 0 < r < n + 1. По непрерывности существуют точки tjk ? ?k+1 ? tjk+1 , k = 0, r ? 2, tjk+1 ? ?k+1 ? tjk+2 , k = r, n
? 1,
pn A0 , ?k = 0, k = 1, r ? 1?r + 1, n. Положим ?r = tjr , то pn A0 , ?r = 0.
Если существует
? ? (?r?1 , ?r ) ? (?r , ?r+1 ): pn A0 , ? = 0, тогда получаем,
что pn A0 , t имеет n + 1 нулей, что ведјт к противоречивому утверждению A0 ? 0. В противном случае, заметим, что на каждом интервале
0
0
(?k , ?k+1 ), k = 1, n ? 1 производная
p
A
,
t
обращается в 0,и, кроме
n
t
0
0
того, pn A , tjr?1 и pn A , tjr+1 имеют
один знак, а pn A0 , tjr = 0, то
есть в точке ?r функция pn A0 , t достигает локального экстремума,
0
поэтому полином pn A0 , t t в этой точке тоже обращается в 0, то есть
имеет n нулей, что возможно
только если он тождественно равен нулю,
0
следовательно, pn A , t =const, что очевидно не так.
Теорема доказана.
Приведјм алгоритм решения задачи (1), считая, что еј решение
единственно. Выберем произвольно ? ? ?. Положим ? = 0, если
e решение системы
h0 (?) ? h1 (?), и ? = 1, в противном случае. Пусть A
21
(3) (4) при
i =? . Несложно показать, что h? (?) ? 0, следовательно,
e ? = h? (?). Проверяем условие
??? (?) = ?? A,
e = ??? (?) .
? A
(6)
Если (6) выполнено, то алгоритм завершается и решение задачи (1) совпадает с решением задачи (2) на текущем базисе при i = ? . Если это не так, то ввиду единственности
задачи (1) найдјтся
k0 ? 0, N : tk0 ?
/
решения
e k0 = maxt ?? f A,
e k . Возможны следующие вариан?
/ ? : f A,
k
ты расположения точки tk0 относительно узлов текущего базиса.
1) tj0 < tk0 < tjn+1 . 1.1. ? v 6= r: tjv < tk0 < tjv+1 . Полагаем j l := jl ,
l = 0, n + 1, l 6= v , l 6= v + 1, ? := ? . Если для i ? {0, 1} справедливы:
e tj ) ? y1+i,j ),
h? (? ) = (?1)i (pn (A,
v
v
i
e
e
f (A, k0 ) = (?1) (pn (A, tk0 ) ? y1+i,k0 ),
(7)
то осуществляем присвоение: j v := k0 ,j v+1 := jv+1 . Если равенства (7) не
выполняются, то j v := jv , j v+1 := k0 . 1.2. v = 1, r = 0 и tj0 < tk0 < tj1 .
Полагаем j 0 := jr , j 1 := k0 . Если выполняются равенства (7) для i = 0
или i = 1,v = 1, берјм j l := jl , l = 2, n + 1, ? := ? . Если равенства (7) не
выполняются, берјм j l := jl?1 , l = 2, n + 1, ? := 1?? . 1.3. v = n, r = n+1
и tjn < tk0 < tjn+1 . Полагаем j n+1 := jr , j n := k0 . Если выполняются
равенства (7) для i = 0 или i = 1,v = n, берјм j l := jl , l = 0, n ? 1,
? := ? . Если равенства (7) не выполняются, берјм j l := jl+1 , l = 0, n ? 1,
? := 1 ? ? .
2) tk0 < tj0 . 2.1. r = 0. Полагаем j 0 := k0 , j 1 := jr . Если выполняются
равенства (7) для i = 0 или i = 1, v = 1, берјм j l := jl?1 , l = 2, n + 1 и
? := 1?? . Если равенства (7) не выполняются, берјм j l := jl , l = 2, n + 1
и ? := ? . 2.2. 0 < r ? n + 1. Если выполняются равенства (7) для
i = 0 или i = 1, v = 0, берјм j 0 := k0 , j l := jl , l = 1, n + 1 и ? := ? .
Если равенства (7) не выполняются, берјм j 0 := k0 , j l := jl?1 , l = 1, n,
? := 1 ? ? ; j n+1 := jr , если r = n + 1; j n+1 := jn , если r < n + 1.
3) tk0 > tjn+1 . 3.1. 0 ? r < n + 1. Если выполняются равенства (7) для
i = 0 или i = 1, v = n + 1, берјм j l := jl , l = 0, n, j n+1 := k0 и ? := ? .
Если равенства (7) не выполняются, берјм j 0 := jr , если r = 0; j 0 := j1 ,
если r > 0; j l := jl+1 , l = 1, n, j n+1 := k0 ; ? := 1 ? ? . 3.2. r = n + 1.
Полагаем j n := jr , j n+1 := k0 . Если выполняются равенства (7) для i = 0
или i = 1,v = n, берјм j l := jl+1 , l = 0, n ? 1 и ? := 1?? . Если равенства
(7) не выполняются, берјм j l := jl , l = 0, n ? 1 и ? := ? .
22
Условие монотонности h? (?) > h? (?), приводящее ввиду (5),(6)
к решению задачи (1), вытекает из теоремы 3 (достаточно положить
h := h? (?) и переобозначить ? := ? ). Перебор базисов заканчивается с
выполнением (6).
Обозначим M :=
k ? 0, N : y2,k ? y1,k = maxk?{0,N } (y2,k ? y1,k ) ,
|M | количество элементов во множестве M .
Замечание.
Одним из достаточных условий единственности решения задачи (1)
является |M | ? n + 1. В таком случае, в качестве начального базиса
целесообразно брать ? ? ?: jk ? M , k = 0, n + 1 \ {r}. Тогда решение
задачи (1) будет найдено уже на первой итерации алгоритма.
Работа выполнена при финансовой поддержке гранта Президента
РФ ( проект НШ грантќ 4383.2010.1).
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Выгодчикова И. Ю. Об условной задаче наилучшего приближения сегментной
функции алгебраическим полиномом // Математика. Механика : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 10. С. 1215.
УДК 514.764
С. В. Галаев, А. В. Гохман
ОБОБЩЕННЫЕ ГАМИЛЬТОНОВЫ СИСТЕМЫ
НА МНОГООБРАЗИЯХ С ПОЧТИ КОНТАКТНОЙ
МЕТРИЧЕСКОЙ СТРУКТУРОЙ
Вводятся понятия геодезической пульверизации связности над гладким распределением и обобщенной гамильтоновой системы, в терминах
которых дается инвариантное описание движения механической системы
со связями.
В работе [1] В. В. Вагнер привлекает развитые им ранее геометрические методы для изучения конкретных динамических систем со связями.
Используя специальные системы координат, Вагнер записывает уравнение движения неголономной системы при отсутствии внешних сил в следующем виде:
dxa
dxa
dxb dxc
dxn
= ??na
,
+ ?abc
= 0.
(1)
dt
dt
dt
dt dt
В настоящей статье мы показываем, что кривые, определяемые уравнениями (1), являются проекциями интегральных кривых векторного поля, называемого нами геодезической пульверизацией связности над распределением. В статье рассматривается векторное расслоение (D, ?, X),
23
1/--страниц
Пожаловаться на содержимое документа