close

Вход

Забыли?

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

?

презентацию

код для вставкиСкачать
В.Ю.Протасов (МГУ)
Совместный спектральный радиус матриц:
приложения и методы вычисления.
, A m -- л и н ей н ы е оп ераторы в R
A1 ,
ˆ ( A 1 ,
, Am )
lim
k
m ax
d 1 ,..., d k {1,..., m }
d
Ad 1
1/ k
Ad k
Геометрический смысл:
ˆ 1 сущ ествует норм а
д ля которой
Ai
A2M
M
A1 M
1 при всех
в R
dg f
i 1 , ... , m
Возьмём единичный шар в этой норме:
ˆ 1 сущ ествует центрально-сим м етричное вы пуклое тело M R ,
d g f
для которого
ˆ
Ai M int M ,
inf { 0 |
i 1 , ... , m
1
A1 ,
, 1
Am
сж ати я в н екоторой н орм е}
Геометрический смысл JSR
x
П усть m 2. П ред п ол ож и м , что сем ей ство
xR
dd
произвольная точка ,
O k ( x ) { Ad 1
Ad k x ,
m ax
d j 1, 2,
A1 ,
A 2 н еп ри вод и м о.
A1 x
x 0,
j 1,
A2 x
, k } - орб ита точки x .
O1 ( x ) , O 2 ( x ) , O 3 ( x ) , ...
|u |
|
u Ok
ˆ
k
Приложения:
1960
1988-90
1991
1989-92
Rota, Strang (теория нормированных алгебр)
Барабанов, Козякин (динамическе системы с переключениями)
Daubechies, Lagarias, Cohen, Heil, …. (теория всплесков)
Micchelli, Prautzsch, Dyn, Dahmen, … (уточняющие схемы – теория приближений и
дизайн кривых и поверхностей)
Распределение случайных рядов (теория вероятностей),
Асимптотика бинарной функции разбиения Эйлера (комбинаторика, теория чисел),
Емкость кодов, оценка числа неперекрывающихся слов, теория графов, ....
Основные свойства
m 1.
Д ля одного оператора ˆ (A) = (A) = lim
k
A
k
1/ k
m ax | j |
j 1,..., d
Если операторы A1 , ... , A m ком м утирую т, либо их м атрицы сим м етричны ,
либо их м атрицы -- верхне (ниж не) треуго льны е, то
ˆ ( A 1 , ..., A m )
В общ ем случае, однако
m ax
( A ) , ..., ( A ) ˆ ( A 1 , ..., A m )
1
m
m ax
( A ) , ..., ( A ) 1
m
Всплески с компактным носителем
{
j ,k
} j , k Z
полная ортонорм ированная систем а (П О Н С ) в L 2 ( R ),
j ,k
( x ) 2 j / 2 (2 j x k )
П рим ер 1. С истем а Х аара (H aar, 1909), ( x ) [ 0 , 1 / 2 ] [1 / 2 , 1]
1,0
1, 1
А.Хаар (1909), В.А. Котельников (1933), К.Э.Шеннон (1949),.
1, 1
1980-90: С.Малла, И.Мейер, И.Добеши, Ч.Чуи, А.Коэн, В.Дамен, и др.
I.Daubechies (1988) – всплески с компактным носителем.
Преимущества всплесков:
Локализация (компактные носители),
Быстрые алгоритмы вычисления коэффициентов,
Характеризация функциональных пространств
..
.
Обработка сигналов
Теория функций, теория приближений
f (x)
c
j,k
j,k
(x) ,
k, jZ
c
j,k
Диф. Уравнения (Вейвлет-Галёркин метод, и др.)
( f ,
j,k
) f ( x) j,k
( x) d x
Построение всплесков. Масштабирующие уравнения.
Для построения системы всплесков с компактным носителем нужно решить
масштабирующие уравнение (refinement equation)
– разностное функциональное уравнение со сжатием аргумента.
N
( x) c k (2 x k ) ,
k 0
c0 ,
, cN
- последовательность комплексных коэффициентов.
c N (2 x N )
( x)
c 0 (2 x )
c1 (2 x 1)
.......
Это – обычное разностное уравнение, но с двоичным сжатием аргумента.
К огд а м астаб и рую щ ая ф ун кц и я н ай д ен а, всп л еск-ф ун кц и я явн о вы п и сы вается:
N
(x) ( 1) c k 1 (2 x k ),
k
k 0
гд е c 0 , .. . , c N - коф ф и ц и ен ты м асш таб и рую щ его ура вн ен и я .
Примеры систем всплесков
1. Всплески Хаара (1909)
( x ) (2 x ) (2 x 1)
Масштабирующее уравнение:
1
1
1
0
0
1
1
2. Всплески Шеннона-Котельникова
( x) 1
sin x
( x) x
(1933, 1949)
sin 2 x sin x
Носитель некомпактен!
x
3. Всплески Мейера (1986), Всплески Баттла-Лемарье (1987) Носитель некомпактен!
4. Всплески Добеши (1988)
( x) 1
3
(2 x ) 4
2
Второй всплеск Добеши. Масштабирующее уравнение:
3
3
(2 x 1) 4
3
3
(2 x 2) 4
0
3
2
1
3
4
3
0
(2 x 3)
Что известно о масштабирующих уравнениях ?
N
( x) c k (2 x k ) ,
k 0
N
( x) d x
Если есть решение с компактным носителем, и
0
c
то
k
2
k 0
N
Обратно, если
c
k
2
,
то есть решение с компактным носителем. Оно единственно
k 0
с точностью о домножения на константу и сосредоточено на отрезке [0, N].
( x)
Но только в обобщённых функциях из
S '( R )
0
ˆ ( )
m ( / 2) ˆ ( / 2) ,
m ( )
N
1
N
c
2
k
e
2 i k
k 0
ˆ ( )
m (2
j
)
j 1
Масштабирующая функция не бывает бесконечно-гладкой
C
N
(R )
Примеры масштабирующих уравнений
Примеры 1. c 0 c1 1
Тривиально: ( x ) (2 x ) (2 x 1)
Пример 2.
Пример 3.
c0 c0 1
c1 1 ,
,
2
1
0
c1 ,
4
3
4
c2 ,
1
2
c2 3
c3 ,
4
0
1
2
1
4
0
3
Решение неустойчиво !
Малые изменения коэффициентов могут приводить к резким изменениям решения:
Пример 4.
c0 Tо же с примером c 0 1
2
1
4
c1 1 c1 3
4
c2 1
c2 3
чисто сингулярно.
2
4
c3 1
4
чисто сингулярно.
Cavaretta, Dahmen and Micchelli (1991)
Описание всех масштабирующих сплайнов с целыми узлами.
Lawton, Lee and Sсhen (1995)
Описание всех масштабирующих сплайнов.
Для любого N существует конечное число масштабирующих сплайнов порядка N
Berg and Plonka (2000), Hirn (2008)
Cклассификация всех кусочно-гладких масштабирующих функций.
Т еорем а ( П . 2005).
Е сли сущ ествует 0 для которого гладко сть
м асш табирую щ ей ф ункции на интервале (0, ) превосходит ее
гладкость на R , то -- м асш табирую щ и й сплайн с целы м и узлам и.
Все кусочно-гладкие масштабирующие функции -- сплайны.
Все они – линейные комбинации целых сдвигов B-сплайна.
“ Типичная ” масштабирующая функция и всплеск-функция
Пример 5
( x)
1
(2 x ) 3
2
1
(2 x 1) 3
(2 x 2) 3
2
(2 x 3)
3
( x)
log 2 3
1.58...
(максимальная гладкость)
( x)
( x)
log 2 1.5
0.58...
(минимальная гладкость)
0
sup 0
|
| ( x h) ( x) | C h
(изломы во всех двоичнорациональных точках)
3
log 2 1.5
for all x , h
0.58...
показатель гладкости (показатель Гельдера)
Непрерывна, но не дифференцируема
Тем не менее, она дифференцируема почти всюду
( x)
sup 0
|
| ( x h) ( x) | C h
П очти во всех точках
( x)
log 2 2.25
Локальная гладкость в точке x
1.17...
С ледовательно, '( x ) 0 п. в .
Фрактальная природа всплесков. Переменная локальная гладкость.
Как определить, будет ли масштабирующая функция непрерывной ?
I.Daubechies, D.Lagarias, 1991
C (R )
A.Cavaretta, W.Dahmen, C.Micchelli, 1991
Б олее того,
ˆ (T 0 , T1 ) 1
log 2 ˆ ( T 0 , T1 )
C.Heil, D.Strang, 1994
ˆ ( A 0 , A 1 ) lim
k
T0 , T1 -
1/ k
m ax
d1 ,
,d k
Ad 1
Ad k
Пример. N 4,
N N м атрицы (2-б лочны е тёплицевы м атриц ы ),
(Ti ) j k c 2 j k 1 i
c 0 , c1 , c 2 , c 3 , c 4
c0
c2
T0 c4
0
c1
c3
T1 0
0
0
0
c1
c0
c3
c2
0
c4
c0
0
c2
c1
c4
c3
0
0
0
0
c1 c3 0 c0
c2 c4 Е сли только м асш таб ирцую щ ая ф ункция ( x ) -- не сплайн,
она им еет перем енную локальную глад кость .
0
Гладкость почти всюду
m in log 2 ˆ
0 log 2 0
m ax Минимальная
локальная гладкость
log 2 Максимальная
локальная гладкость
1/ k
С овм естны й спектральны й рад иус
ˆ ( A 0 , A 1 )
lim
Н иж ний спектральны й рад иус
( A 0 , A1 )
lim
П оказатель Л япунова
( x)
0 ( A 0 , A1 )
lim
k
k
m ax
Ad 1
Ad k
m in
Ad 1
Ad k
d 1 ,..., d k { 0 ,1}
1/ k
k
d 1 ,..., d k { 0 ,1}
Ad 1
d1 ,..., d k { 0 ,1}
Ad k
1/ k
1/ 2
k
Т еорем а. Д ля лю бого x [0,1] им еем ( x ) [ m in , m ax ] .
Д ля каж дого [ m in , m ax ] локальная гладкость = ( x ) достигается
на всю ду плотном м нож естве точек x [0,1] .
Д ля почти всех
x [0,1] им еем
( x ) 0 lo g 2 0 .
N
Как вычислить или оценить JSR ?
П ереб ором
( по опред елению ) D aubechies, Lagarias, H eil, S trang,
Э споненциальная слож ность. H eil, S trang (1994) д ля вы числения JS R специальны х 2 2-м атриц
с относит е ль ной погреш нос тью
= 0.05 переб рали все произвед ения д о д лины k 19.
G .G ripenberg (1996) - ``branch and bound '' алгоритм .
Р азум ны й переб ор. Ч асто очень эф ективен. Н о теоретически плох.
Сходимость к величине JSR при растущем к чрезвычайно медленная.
П р и ч и н а м ед л ен н о й сх о д и м о сти :
1/ k
m ax
d 1 ,..., d k {1, ..., m }
Ad 1
Ad k
В ы б р ан н ая н о р м а в R
dd
ˆ ,
k м о ж ет б ы ть сл и ш к о м д ал ек а
о т то й , в к о то р о й все о п ер ато р ы - сж и м аю щ и е.
С к о р о сть сх о д и м о сти
C
,
гд е к о н с тан та C - о тн о ш ен и е д вух н о р м .
k
О н а м о ж ет б ы ть о ч ен ь вел и к а.
Отрицательные результаты о сложности задачи вычисления JSR:
Blondel, Tsitsiclis (1997-2000).
Задача приближённого вычисления JSR для рациональных матриц NP-сложна.
Задача определения: верно ли, что JSR строго меньше 1
(для рациональных неотрицательных матриц) алгоритмически неразрешима,
начиная с размерноти d = 47.
1
Не существует алгоритма, полиномиального по размерности d и по точности
для приближения JSR с относительной погрешностью Т ем н е м ен ее, сущ ествую т ал гори тм ы , п ол и н ом и ал ьн ы е
(п о отд ел ьн ости ) п о d и п о
1
(уви д и м ) .
Инвариантные нормы
Теорема 1 (Н. Барабанов, 1988)
a) Д ля непривод им ого сем ейства операторо в A 1 , ..., A m сущ ествует 0
и норм а
m ax
, д ля которой пр и лю б ом x R
A 1 x , ... , A m x
=
d
x
b) Д ля лю б ой такой норм ы им еем ˆ ( A1 , ..., Am ).
Независимо был установлен ‘’двойственный’’ факт:
A 2M
Теорема 2 (A.Дранишников, С.Конягин, В.Протасов, 1996)
M
a) Д ля неприводим ого сем ейства операторо в A 1 , ..., A m сущ ествует 0
A1 M
и сим м етричное вы пуклое тело M ( инвариант ное т ел о ) такое, что
def
AM
C onv ( A 1 M , ..., A m M ) M
b) Д ля лю бо го такого тела ˆ ( A 1 , ..., A m ).
d ef
AM
*
C o n v ( A 1 M , ... , A m M )
Д войственность: M = B (поляра к B ), где B - единичн ы й ш ар в Б арабановской норм е
*
для сопряж енны х операторов A 1 , .. ., A m
*
(F.W irth, E .P lishk e, 2005 )
П рим ер 1. М атрицы д е Р ам а.
1 2
A1 0
П ри 0.25
П ри 0.25
;
A2 ,
1 2 0
(0 , 0.5)
им еем ˆ = ( A1 ) m ax{ 1 2 , }.
им еем ˆ =
( A1 A2 ) 1
2
4 7
2
.
П ри всех им еем инвариантны й ш естиугольник М ( ) .
Y
M ()
X
П рим ер 2. 2 n 2 n м атрицы A1 , A 2 ф ункции разбиения Э йлера (т еория чисел).
О ни состоят из 0 и 1.
Д л я них ˆ ( A0 A 1 ) при нечетны х n , и ˆ
( A1 ) при четны х n.
И нвариантная норм а строится для всех n 13 .
П рим ер 3. П роб лем а ём кости д воины х код ов, изб егаю щ их д анны х запрещ енны х разностей.
Д ля лю б ого наб ора запрещ ённы х разностей ём кость равна JS R д вух 0-1 м атриц разм ер ности d 2
П ри м алы х m инвариан тн ая норм а явно строится и наход ится знач ение ём кости.
m 1
.
Алгоритм приближения инвариантной нормы многогранниками
Q k A Pk
Б ерем произвольны й начальны й м ногогранни к P0 R
d
(1 ) Q k
центрально-сим м етричны й относительно нул я,
Pk
послед овательность { Pk } опред еляется инд ук тивно:
и сод ерж ит не б олее N C d (1 d ) / 2
(1 ) Q k 1 Pk 1 Q k 1
верш ин.
Pk 2
Е сли полож ить Pk 1 A Pk , то м ногогранник Pm м ож ет им еть д о 2
m
верш ин,
и слож ность б уд ет экспоненциальной.
Н е нуж но хранить все верш ины Pm , м ож но пр иб лиж ать, Pm Q m .
После С 0 1
итераций получим нужное приближение
Общее число операций
C ( d , A0 , A1 ) ( diam Pm )
1/ m
ˆ
( d 1) / 2
Для d=2 число операций: C 3 / 2
При
A m Pk
Pk 1
Q k 1 A Pk C onv ( A1 , A 2 ). М ногогранник Pk 1 приб лиж ает Q k 1
с о тносительной погреш ностью :
A 1 Pk
0 .0 0 0 1 требуется 10 6
операций.
Для d =2 алгоритм был запрограммирован И.Шейпаком в 1998.
При d > 2 непонятно как практически реализовывать
Оценка JSR с помощью тензорных произведений матриц
Протасов (1997),
Zhow (1998),
Blondel, Nesterov (2005)
А л го р и тм - п о л и н о м и ал ьн ы й п о р азм ер н о сти d . Д аёт гр уб ы е о ц ен ки н а ˆ .
L p - спектраьны й радиус ( p -радиус),
p ( A 1 , ..., A m ) lim
k
p [1 , ]
k
m
Ad1
d1 , , d k
Определен в 1995 независимо: Y.Wang (p = 1),
Д л я л ю б о г о p и м еем :
Д ля целы х четны х
м атрицы
A =
1
m
p
p 2 r значение p
m
Ak
2r
ˆ
p
A dm
1 / pm
ˆ ,
R.Q.Jia (для всех p)
m
1/ p
p
вы чи сляется как об ы чное соб ственное значени е
2 r ( A 1 , ... , A m )
( A)
1/ 2r
.
k 1
Ч ерез A B об означено тензорное (кронек ер овское) пр - е м атриц A , B - м атрица разм ера d
2
Д л я л ю б о го r и м еем :
М атрица A k
2r
В еличина 1/ 2 r
им еет разм ерность d
2r
( A)
ˆ
m
1/ 2 r
1
m
м атрица A =
A
m
1/ 2 r
1/ 2 r
( A)
2r
им еет разм ерность d
k
2r
.
k 1
m
( A ) даёт приближ ени JS R с погреш но сть ю
1/ 2 r
1 ln m
2r
(A ) , гд е A =
П ри м ер 1. Д л я д вух d d м атри ц вел и чи н а
1
m
Р азм ерн ость м атри ц ы A равн а d
2
(м ож н о п он и зи ть д о
П р и м ер 2. Д л я д вух d d м атри ц вел и чи н а
4
4
Ak
2
п ри б л и ж ает ˆ с
=
2 1 41%
k 1
2
(A ) , гд е A =
(м ож н о п он и зи ть д о
d /2 )
1
m
Р азм ерн ость м атри ц ы A равн а d
m
4
m
Ak
k 1
d / 24)
4
п ри б л и ж ает ˆ с
=
4
2 1 19 %
Идея доказательства. p-инвариантные нормы.
N N ( R ) м нож ество всех норм в R .
d
d
N вы пуклы й невы р ож д енны й точечны й конус.
Д ля епривод им ого сем ейства м атриц A 1 , ... , A m и д ля p [1, + ] рассм отрим оператор
F : N N,
1
m
F ( | . | )[ u ] Д ля лю б ой норм ы | . | N
m
j 1
| Am u | 1/ p
p
ф ункционал
,
F ( |.| )
u R
d
F(N)
такж е норм а.
f
f
П ри м еры . p = 1.
F ( | . | )[ u ] 1
m
p = .
F ( | . | ) [ u ] m ax
| A u |,
1
| A u | ...
1
... , | A m u |
| A mu |
П ри p = 2 оп ератор F сохран яет евкли д овы н орм ы
N
(ед и н и чн ы й ш ар - элли п сои д ).
Т еорем а . Д ля неприводим ого сем ейства { A 1 , ... , Am } и лю бого p [1, ] оператор F
им еет ''собственны й вектор'': сущ еств ует норм а | . | N и > 0 , для которы х
F ( | . | )[ u ] | u | ,
u R .
d
Д ля лю бой такой норм ы ''собственное знач ение '' рав но p ( A 1 , ... , Am ).
F(N2r)
f
f
С лед ст вие. П ри p 2 r (r - целое)
N 2r
x
2r
(a j , x) j
1/ 2 r
F им еет инвари антны й конус
сущ ествует инвариантная норм а f N 2 r ,
соответствую щ ая вектору П еррона-Ф роб ениуса опера тора F .
Н а конусе N 2 r оператор F зад аётся м атрицей
2 r ( A 1 , ..., A m )
( A)
1/ 2 r
.
A =
1
m
m
k 1
Ak
2r
N2r
Алгоритм вычисления JSR поиском лучшей нормы
в определенном семействе норм.
Идея: мы не можем найти инвариантную норму. Тогда приблизим её с помощью
норм из определеннго конечномерного класса.
(стандартный трюк в теории приближений)
(V.Blondel, Yu.Nesterov, J.Theys, 2005)
(V.Protasov, R.Jungers, and V.Blondel, 2010)
Рассмотрим сначала случай неотрицательных матриц
В озьм ём класс ``прям оугольны х'' норм
rk
u
x
m ax
i 1 ,..., d
ui
,
u
> 0 .
xi
d
x
m in
Ax
k
x
x 0
rk x 0
d
м ногогранник с m граням и
subject to:
R
,
A Ad 1
Т еорем а. Д ля лю бого k им еем
Ad k
d
1/ k
rk
1/ k
ˆ
rk
1/ k
Случай произвольных матриц
Берём все ``эллипсоидные'' нормы
u
X
( Xu , u ) , где X - положительно-определённая матрица.
Реш аем следую щ ую задачу полуопределённог о програм м ирования
k
с одним (м атричны м ) неизвестны м X
и m ограничениям и.
X
rk
m in
subject to:
X
T
A X A
0
rk X
0
,
A Ad 1
Ad k
X
О бщ ая задача полуопределённого програм м и рования:
l 0 ( X 1 , ..., X q ) m in
X 1 , ..., X q
0
l s ( X 1 , ..., X q ) 0 ,
s 1, ..., N
Эффективно решается методом внутренней точки. ЛП-задачи – частный случай.
Т еорем а. Д ля лю бого k им еем
d
1 /( 2 k )
rk
1 /( 2 k )
ˆ
rk
1 /( 2 k )
Доказать больше иногда легче.
Джордж Пойа «Математика и правдоподобные рассуждения» (1954)
Если не получается что-то доказать, можно попробовать доказать больше.
Если не получается хорошо приблизить JSR, можно попробовать …
вычислить его точно.
Понятие экстремальной нормы
О пр еделение. Н орм а
.
является экстрем альной, если
Aj
ˆ , j 1, ... , m .
Д ля экстрем альной норм ы сходим ость осущ е ствляется в один ш аг:
1/ k
m ax
d 1 ,..., d k {1,..., m }
Ad 1
Ad k
ˆ ,
k Е сли M - единичны й ш ар экстрем альной но рм ы , то A j M ˆ M ,
A2M
A1 M
M
j 1, ..., m .
Как построить экстремальную норму ?
П усть m =2. Н орм ируем м атрицы так, что бы ˆ ( A 1 , A 2 ) 1
v
xR
dd
произвольная точка ,
O k ( x ) { Ad1
(x) Ad k x ,
{ y R dd ,
d j 1, 2,
{ k j } j N ,
(x)
x 0,
j 1,
,k }
x
xk j O m j ( x ) ,
lim x k j x}
j A1 x
- м нож ество частичны х пред елов (точек на копления) орб иты.
П усть
M ( x ) C onv ( ( x ), ( x ));
dim M ( x ) d
тогд а
( x ) непусто,
O1 ( x ) , O 2 ( x ) , O 3 ( x ) ,
и
A1 ( x )
A2 ( x)
(свой ство сам оп од об и я
A1 K
( x)
A2 K
K)
A2 x
, O ( x)
Будем строить единичный шар экстремальной нормы в качестве многогранника M .
Оказывается, что такая норма существует для большинства семейств матриц.
Наблюдение 1. Для приводимого семейства задача вычисления JSR сводится к
Нескольким аналогичным задачам в меньших размерностях. Таким образом,
предполагаем, что семейство неприводимо.
Наблюдение 2. Если произведение П максимальное, то его максимальный
собственный вектор v должен быть крайней точкой множества M.
Если M – многогранник, то v -- его вершина.
Итак, максимальные собственные векторы произведения П и всех его циклических
перестановок -- вершины M.
Qv
Наблюдение 3. Критерий остановки:
Л ем м а. П усть ( ) = 1 и
*
произведение Q , для которого (v*, Q v ) > (v*, v),
то -
v
v* - м аксим альны й
собственны й вектор . Е сли сущ ествует другое
не м аксим альное .
v
Qv
Алгоритм точного вычисления JSR (Н.Гуглиелми, В.Протасов, 2011)
Б ерем м акси м альн ы й соб ствен н ы й вектор v1 of
П олагаем v j Ad k j 2
j 2,
Ad k v1 ,
vk
Ad k 2
Ad1
v1
Ad k .
, k.
…..
Ad 2
Ad 1
v3
Ad k 1
Ad k
v2
vs A j v 1
v p Aiv q
‘’Мертвые’’ ветви
Каждый раз проверяем, будет ли новая точка принадлежать выпуклой оболочке
предыдущих точек (ЛП задача).
Алгоритм завершается, когда не появилось ни одной новой вершины.
Инвариантный многогранник M – выпуклая оболочка всех точек, построенных алгоритмом
Для каждой очередной вершины применяем критерий остановки:
П усть v j -- м аксим альны й соб ственны й век тор циклической перестановки *
такой, что
*
( v j , v j ) = 1,
j 1, . .., k .
не являет ся м ак сим аль ны м
Т о гд а:
Д ля некоторого j {1, .. . , m } и некоторой верш ины v s им еем
v
*
vk
*
j
…..
vk
*
v1
v1
*
2
*
|( v j , v s ) |
*
3
v3
v
v2
vs A j v r
v p Aiv q
Д ля каж д ой новой верш ины v s все произвед ен ия | ( v j , v s ) | , j 1, ... , k ,
*
не д олж ны превосход ить 1. И наче, -- н е м аксим альн ы й
1.
Пример 1. Задача о плотности единиц в ромбе Паскаля:
(S.Finch, P.Sebah, and Z.-Q.Bai, 2008)
Плотность единиц в ромбе Паскаля порядка n
-- между C n
log 2 ( A1 , A2 )
и
И звестно, что ˆ ( A1 , A2 ) = 2.
О тносительно ( A1 , A2 ), вы двинута гипотеза, ч то он равен
1+ 5
На самом деле,
( A1 , A2 ) A1 A2
3
(алгоритм работает несколько секунд)
3
1/ 6
1.6376...
2
= 1.6180...
C n
log 2 ˆ ( A1 , A2 )
, где
В ы б и р аем
A1 A 2
3
3
Инвариантный многогранник M 1 имеет 8 верш ин.
П рим ер 2. Асим птотика бинарной ф ункции разбиени я Э йл ера.
Бинарна я фу нкция разбиения Эй лер а
k d 0 2 d1 2 d 2 1
2
2
m 1
bd ( k ) -- это количество разложен и й
d m 1 ,
гд е d j {0,1,
, d 1}
Как мы знаем, b2 ( k ) 1. Д ля d 3 нужно оценить рост bd ( k ) при k .
b2 ( k )
1
b3 ( k )
s ( k 1)
b4 ( k )
k / 2 1
( L. E u l er , 1 7 2 8)
(S te rn, 1858 )
( K losinsky, A lexanderson, H ill m an , 1984 )
К акова асимптотика величины bd ( k )
при k ?
L.Euler (1728), A.Tanturri (1918), K.Mahler (1940), N.de Bruijn (1948)
L.Carlitz (1965), D.Knuth (1966), R.Churchhouse (1969), B.Reznick (1990)
О твет:
b2 r ( k )
C k
1
C k
,
b2 r 1 ( k )
1 log 2 ( A1 , A2 ),
A 1 , A2
гд е log 2 r
C k
2
,
(B .R eznick, 1990)
гд е
2 lo g 2 ˆ ( A1 , A2 )
(V . P rotas ov, 2000 )
Пример. При d = 5 :
это ( d 1) ( d 1) м атри ц ы и з н ул ей и ед и н и ц :
есл и 2 2 k j i d 1
1,
( Ai ) j k 0 , и н аче.
А лгори тм вы чи сляет точн ы е зн ачен и я д ля d
1
0
A1 0
0
1
1
1
1
1
1
0
1
0
0
1
1
1
1
A2 0
0
100.
О казы вается, что д ля всех d и м еем
ли б о ˆ ( A 1 A2 ) , ( A 1 ) , ли б о: ( A 1 A 2 ) , ˆ
Для размерности 50 программа работает 5 минут,
для размерности 100 -- около 20 минут
( A1 )
1
0
1
1
1
1
1
1
0
0
0
1
Функция разбиения Эйлера для троичного разложения:
В ы бираем
A1 A 3
Экстремальный многогранник M 3 имеет 16 верш ин.
Пример 3. Асимптотика числа слов двоичного алфавита без перекрытий.
Задача сводится к вычислению JSR и LSR двух 20x20-матриц.
2
(B lerk, 1988 ) ,
ˆ 2.584
2. 226
(K oba ya shi, 1988)
Э тот результат последовательн о улучш ался:
2 .2 2 6
ˆ 2 .5 8 4
K for u (1988), K obayashi (1988), C assaigne (19 93), Lepisto (1995)
10
( A1 A2 ) 1 /11
2.41756...
;
ˆ ( A1 A2 ) Программа работает 8 минут
1/ 2
2.51793...
Вычисление JSR для случайных пар матриц
Вычисление JSR и LSR для случайных пар булевских матриц размерности d = 100.
Условия конечной сходимости алгоритма
О п ред елен и е. П рои звед ен и е Ad k
Ad 1 н азы вается д ом и н и рую щ и м , если ( )= 1,
и сущ ествует q 1 такое, что ( ) < q д ля всех остальн ы х п рои звед ен и й
Ad n
н е являю щ и хся степ ен ям и , и ли степ ен ям и е го ц и кли чески х п ерестан овок.
доминирующее
максимальное
Т еоре м а 1. А лгоритм сходится за конечное врем я тогд а и только тогда
когда произведение дом и нирую щ е е.
Ad1 ,
Спасибо!
Документ
Категория
Презентации
Просмотров
6
Размер файла
1 983 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа