Сложность приближения иррациональных чисел рациональными тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ИОСКОВСЖЖ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСШОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени И.В.ЛОМОНОСОВА

Г.

) Г

' 0 ОД Ка правах рукописи

УДК 511, 519.7

>

Марзух эль Овейхан 14

Сложность приближения иррациональных чисел рациональными

Специальность 01.01.09. - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА - 1994

Работа выполнена на кафедре дискретной математики механико-штематического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

доцент С.Б.Гашков. Официальные оппоненты: доктор физико-математических наук, профессор Н.М. Тимофеев; кандидат физико-математических наук А. В. Макаров.

Ведущая организация - Московский энергетический институт,

Защита диссертации состоится 3 июня 1994 года в 16 час. 05 мин. на заседании Специализированного

совета ..........(Д. 053.05) при ЖТ по адресу: 119899,

ГСП, Москва, Воробьевы Горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 1994 года.

- Ученый секретарь Специализированного , совета (Д. 053.05) при МГУ

д.ф.-м.н., профессор В. Н. Чубариков

ОЩЯ ХАРАКТЕРИСТИКА РАБОЙ

Актуальность теми. ,. Задачи о сложности вычисления или построения в тон юи ином смысле разных объектов в последнее время часто рассматрваотся во мнош разделах математики: в анализе ( в теории прйипенвй ), вотслотельной математике, алгебре ( в так называемой алгебраической теории сложности ), теории чисел, геометрш (в та называемой вычислительной геометрии ), логике и теорни алгоривк® и более всего - в теории сложности булевых фушщй. В чаяаэсти, вопросы о сложности приближенного вычисления'действителша чисел, рассматривались, например в работах ВотоШ ,1.,Вогге1п Е.1' и ^гшвеа V.2'

В работе изучаются задачи о сложности реализации рациональных чисел формулами в некоторых базисах, состоящих из арк^йшескн операций, и о сложности приближения иррациональных чисел рациональными. В качестве базисов будем рассматривать следунге множества операций В = { &у,х-у,ху,х/у,х~'1},В0= < х+у.гм/.гуд"1,! }, В1 = {х+у,ху,х'\ц, Вг = В3 = {^.(^'«ГУИ}-

Понятие форедш над базисом В и реализуемой ев функции свределяет-ся индуктивно стадзртннм образом, подобно тещу как определяются формулы в алгебре логике и теории сложности булевых функций Под сложностью формулы понимается число символов переняли и констант (в рассматриваемом случае - единиц) в форму®. Слонсстью рационального числа г назнвазтся_ минимальная сложность резлизущей

1' Borseln J.H,Borgeln R,P. On the ccmplexlty ol iamlllar iunc- . ■ tlons and mrnbers.- SIAM Review, 1938, v. 30, № 4, p.589-601.

2) Strassen1?. Berechnungen In partiellen Algebren endlichen lyps.-Compnttog, 11 -{1973).- s.181 - 196.

31 Яблонский C.B. Введение в дискретйув математику.- И.: Наука, 1986.

1) Лупанов O.E. Асшпотические оценки сложности управляли сис-

тем. - М.: изд. МГУ, 1984.

его формула к обозначается она Меру сложности Ц (г) =

= (г) , ш. будет сказано далее, нош интерпретировать как

наименьшее шшчество еяшчшх сопротивлений, из которых в построить тсзедовательаншраллельнув схему (Д-схему) с сопротивлением г и ей наимегодуд сушу элементов в ветвящихся цепных дробях, предагакляаш г.(.о ветвящихся дробях са.5)).чВозноаш и другие содецтвлкяне интерпретации.

• Формулы образует пропой и важный подкласс схем .причем любую схему мошо.не изкеняя глубины, преобразоЕть в формулу. Глубина является ватй мерой сжтаости, так как она оцешвает вреш вычисления ®нкцаи с учетом возможности параллельного использовэ-ния многих 1?вдессоров. Изучение формул оправдывается также тем, что некотсрка виде вычислительных устройств моделируются именно формулами.

Цель работы - получение точных оценок сложности реализация рядкшшш чисел формулами в некоторых базисах, состоящих из ^яфетических операций, и нахождение условий их обращения в равенство; - получение асимптотически точных оценок сложности щиДтоешой реализации иррациональных чисел формулаш; - исследован® асимптотического поведения наименьоего знаменателя рациональной лроби, с-щиблихащей данное иррациокгльное число.

Ц е т о я я к а исследований. В работе используются методы дасиетаой катеиатикЕ и математической кибернетики, теории чисел и ¡ЕтряческоЗ теории даофантовьк приблшшй.

Научная новизна. Все основные результаты работы ноше. Некоюше результат являются уточнениями ранее известных. В работе получены во многах ватах случаях точные значения слог-гости реализаш рациональных чисел формулами в непрерывных бази-

51 Скоробоггша В.Я. 1еория ветвящихся цепных дробей и ее применен® в вычислительной математике. - II.: Наука, 1983. - 2 -

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

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

Апробация. Результаты работы докладавались на семинаре Б.Н.Чубарикева и Г.И.Архзтова и на семинаре А.И.Аптекарега, В.В.Вашовз, Е.А.Рахманова в МГУ.

П у б л и к а ц и а. По теме диссертации автором представлены к опубликованию 2 работы,'названия которых приведены в кощв автореферата .

Структура диссертации. Диссертация состоит из введения и двух глав, состоящих каддая из трех параграфов, и. списка.литературы. Полный обьем - 94 стр.текста.

СОДЕРШШ РАБОТЫ

В первой главе работ рассматриваются, главша образом, вопросы о сущности реализации рациональных чисел фо{нулами.

Во второй главе рассматриваются следушие мера слошиж приб- . лиаения действительных чисел рациональными :

К«,с) = ш1п { Х(г) : |в - г| < с}, где Х(г) - знаменатель несократимой дроби, представляпаей число г, Lg («,С) = nln { Lg (г) : - г| < с}, i = 0,1,2.

' Результаты о первой из них, видимо, мозяо рассматривать их отно-• сящиеся к теории даофантовнх приближений. В §§ I и 2 первой глава излагаются основные понятия и результаты, используемые в дальнейшем.

В § 3 доказывается несколько утверждений о слсаиости реализации рациональных чисел формулами.

Ншшя оценка сжиности реализации ращонвльш чисел формулами дается в теореме 3, доказательство которой существенно опирается • на один результат О.И.Касим-заде. Через Р^- обозначается .п-тый член последовательности йбоначчи, а через И - делая часть числа х. Т е. о р е м а 3. Для любой несократимой дроби р/д, р, q <= к, Ьд (р/д) > Ьд (р/д) » % (р/д) » L%(^^(ш(g.p)-1/2))J

Ьв (Р/д) г Ьд (р/д) > ь^р/д) > 1Ыфт^-иг))\-1.

В случае тах(д,р) = ?п первое неравенство достигается только на дробях

№ - ш ?ЛРп-к' где »'п> < 2-

В случае щ = ? первое неравенство достигается только на дроби

р/1 - МУп-зР "1 ™ УпЛА1^ № <2В качестве следствия получаются некоторые экстремальнее свойства

цепных а ветввдюя дробей и описание мшшкша формул для некоторых чисел. -'

Следствие! Среда всех несокрагиш дробей со знаменателем Рп наименьшую сувд элементов в представлявдих и обыкновенных цепных дробях имею дроби и Р^/Р • Минимальные формулы в базисах В, В0, В,, В2 для этих чисел соотвествувт цепным дробям

[0;11ИДЛ,] и ГО; ,1...,1,21, где 2 = Ы, и цепным дробям

п-1 раз п-л раз [0;2|1...,1|] и Г0;2,1...,1,21, где 2 = 1+1 ш 1+ Г1. Слошость

п-л раз п-4 раз

каждой из них равна п-1. Среди всех несократимых дробей со

знаьргателем Рп нэныгньшуг сумму элементов в представляют их ветвядихся цепных дробях имеют дроби Р^.^ . где (к,п) « 2. Минимальные формулы в упомянутых базисах для этих чисел соответствуй ветвшися цешва дробям вида |—. где Д. - формула,

. соответивугаая целим дробям [0;,1...,!,] или Г0;11...Л|21, а % ■

^ГРгт т Т^® - формула, соответствующая цепным дробям [I; ,1... ,1,1 или

б-) раз

ГI;|1..■ Л|21, где = {к,п-К[ (формулы, записи которых в а-л раз

приведенной формулировке не имеют смысла из-за отрицательности чисел а-З, р-3, п-3, п-4, естественно,следует исключить из этой, формулировке). Сложность казяой из них равна п-2.

Иногестзо всех дробей, да которых достигаются неравенства теоремы 3, устроено довольно слошо. Представление об этом дает следующий частичный результат, справедливый в полном объеме да базисов Б и В0, и частично - для базисов В1( 1 = 1,2,3. 1 е о р е м а 4... . , . .

Первое неравенство теоремы з достигается при п,ю 2 ди дробей

УвД^в+Л+Р' У ^P^ * 2> i1"1'11' * 2' Я066® ?п-1?пД?п+1Рп»Р* у которых (п-1 ,пнТ) $ 2, (п+1,ш) < 2, и дробей ^-^п-^п+Ли)' У которых (П-1.Ш+1) í 2,(п+1,и-1) < 2 (это утверэдение теорема верно и для базиса В,), а такге для хробей .

?п-Л+ггА+,- У ког°- '

рнх (п+1 ,и+1) í 2, пд > 2, а символ • означает + или - (если символ • есть +, то утверждение теоремы верно и для базисов Вг и

В3). Вторе неравенство теоремы 3 достигается для дробей __J_

у которых' = 0,1 и (fc+í.l+f) í 2, (М,т1) í 2,íl+í.ш+í) í 2, S,i?¡,I » 2, причем для этих дробей первое неравенство не достигается (это утверждение теоремы верно и для базисов В2 и В3). Минимальные формулы из теоремы 4 не -являются цепшми дробями. В следущей теореме указывается серия цепных дробей, для которых достигаются неравенства теоремы 3. Г в о р е м а 5.

Если Lg (р/ф = X, 1 = 0,1,2,3, и при некотором Ьн FfeP + ?í:+!9>fI>JJ'?S-íP + ¥> Wí •

то при любом n « n Lg (f0;il...l,p/ql) = X -f п. . '

в

для следущих дробей г выполняется равенство

Lg (г) = Кг) = tlog^(I(rH/2))J + с ,с = 0 юш 1, :

Г = (0;1...П, [0;1...121...1],ГО;1...1221...1},(0;1...12221...1J, Г0;1...122221...II, [0;1...1222221...11, [0;2222221...1), [0;1...131...1], 10,М...1231...11, [0;1...12231...13, [0;1...122231...1], Ю;1... 12321. ..1], [0;1...1321...11,

СО;1___13221...13, I0;31...1], 10;331...П, (0;41...13,ГО;421...1].

Далее суша элементов цепной дроби, представляющей число г,

-5- .

обозначает через 1(г), а знаменатель обычной несократимой дроби, равной г - через ,Ь(г).

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

Т е о'р е в а 6. Для любых г « справедливы соотношения Кг) » Ь^г) = * ? Ьз (г) = ^{г) £

Llo^(^^(I(гH/2)}JH%(v^(г(r)-1/г))JHlo^(/5(IBг(rИ/г))J.

Для г = (дШ/д, д/(д±1), где д = уп+| или ? г , и » 4,

\(Г) = Ч(Г) = Ч(Г)^Ч(Г) = 1в(г1 =

= [1оё^(НгН/2))] = [Ю^(^(1{Г)-)/2))]. а да г = зЛ/д при те1 же д

^(Г) =%(г) = ао^(1(г)-1/2))1 = [1о^(/5(1Вг(|г|)-1/2))].

Во второй глазе рассматриваются задача о сложности приближения иррационаднвх чисел рациональными. С помощьи теоремы 3 дается уточнение в одам чайном случае теоремы I работы6' .

следствие 3. Для почти всех чисел а е к при любом « > О

» | - (1+5)% £ - Ов(1).

для всех идвциональных алгебраических чисел <г

> |(1-о(1))1о^

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

^(«.с) * {к^ | - 0(1).

61 Гашков йБ. О сложности приближенного вычисления действительных часы схемами ж формулами в некоторых рациональных Оазисах.-Дискретшз математика - 1990 - т.2 Н°4 с.26-46 - 6 -

В следупцей теореме указываются точные выражения для различил мер сложности е-приблшвния числа Ф - золотого сечения.

Теорема 7. Для любого! = 0,1,2,3

= шх{-2КlQS^i/5/е - 1))/4 + I/2J-I, -2Ц1о3ф(^/с + 1))/4J-2} <

В теореме 8 даются асимтотически точные неравенства для меры сложности 1(о,е) произвольного иррационального числа а и тем сашм обосновывается еще одно экстремальное свойство золотого сечения. Теорема 8. Для всех иррациональных чисел а

причем все неравенства обращаются в равенства лишь при а, эквивалентных Ф.

В теореме 9 устанавливаются асимтотически точные неравенства для меры сложности Ь(а,е) в терминах скорости роста элементов цепной дроби для а. С ее помощью строятся примеры чисел, у которых функция 1(а,с) для некоторой последовательности растет очень медленно, а для некотрой последовательности еп почти максимально быстро, Теорема 9. Пусть Лх) - функция, равная в нуле нулю и монотонно стремящаяся к 4« при х -» -к», и голошельвзе число а разлагается в цепную дробь с элементами аа * и, которые бесконечно часто удовлетворяют асимптотическому неравенству ant) > где руа^ - n-ая подходящая дробь. Обозначим g(x) обратную функцию к

Их)!2. Тогда для некоторых последовательностей с и 5 .стремяиих-

+ 1) - 2 « Lg (Ф,с) =

ся к нули, справедлив асимптотические неравенства

ICa.g >1/(2^1/^), C&1/SJ.

Если se всегда amJ « , то

I(a,c) i I/^I/c)), К«,с) i g(I/e). . .

Из теорема 9 и теорем йнчина71 выводится следущее утверкдение. Следствие 4. Для почти всех а е r и любого 8 > 0 при некоторых, пологителша с и С

c//clog^ïoglos±)HS ' < 1(<х,с) < С /(Iogi(loglo4)"V , a для некоторых последовательностей еп к гд -> О С//yogi (logîogi} ' > 1С«.в_),

и п_

> с /(log! (logicgi))/cn'.

n n

Теорема 9 применяется к доказательству следующего утверащения о слозеости приближения непрерывных функций формулами. Следствие 6. Для любой непрерывной фунши h е Cla.bJ, принимающей иррациональные значения в некоторых рациональных точках,

Ш sup bg(h,e)/2og 1/с > о с -> о

и для любой монотонной функции 1(c), найдется такая аналитическая $гшсция*Ь « Cla,W, что

Пи in/ Lr (Ь,е)Д(е) <1. с -» о . „ ■

Существует такая аналитическая функция h е Cla.bJ, что для некотрг

рых констант с и С, 0 < с < С,

с ïog 1 /с < ig№,c) < с log 1 /с Для формулирования теорем 10 и И понадобятся следующие обозначения, Пусть о = [a0;ar..,an,... ] - бесконечная цепная дробь, Pi/'n " шследовательшсть подходящих дробей, = а <*п

= [a ;a .... 1 - последовательность остатков. Если a ,„ нечетно,

1 и ml * nid

7)Хинчин А.Я. Цепные дроби.- М.: Наука, 1978.

то положим г = (а „ + 1)/2. Если а .четно, то пологам г =

п * п+2 ' п+2 а

ат2/2 в случае 0nt)«m3 > I и гп = (ап+г + 2)/2 в противном случае, Изложим

■ Т ta « ni - (r+H0)2f (g-r)iri-l) r (á . . (Г+0)га 7(a) = Um sup У (а), ГД9

а —» m u

TnW = шах <Gr (^,,V,/nt2),Fr (^Г^З'^Ь

n n

Обозначим Kjj множество всех чисел o e r+, y которых разложения ç цепннз дроби не содержат элементов, превосходязщ а, а > I.

В теореме 10 содержится признак "плохой приближаемости" действительного числа. ... .. .....

Теорема 10. Справедливо равенство lim sup

еЬ2 (а,с) = 7(a).

с —» О

Число а - плохо приближаемое тогда и только тогда, когда г (а) < ». В теореме II указываются экстремальные свойства некоторых цепных дробей в классах Кц.

Теорема И.При любом четном а и нечетном а > 7 для всех о«^ 1(a) < <[1;alai...]),

причем равенство возможно шь для чисел, в разложениях которых в цепную дробь содержатся сколь угодно длинные последовательности следущих друг за другом элементов, совпадайте с последовательностями alai... .При a = 5 среди чисел а « Kj наибольшую величину г(а) имеют числа вида о =

= [...,I5I5...51,4,1515...1511...,1515...151,4,1515...151,...],

H ■ h . Ä2n-1 я2п

где mln{-b-2n_,,è2J имеет вершим пределом бесконечность ( в промежутках между соседними блоками ,I5I5...151,4II5I5...15<,

могут стоять любые элементы) и только такие числа . При a = 3 среди чисел а е Kj наибольшую величину т(а) имеют подобным же образом определяемые числа

[..■,1313...31,2,1313...131,...,1313...131,2,1313...131,...],

Щ Ä2n-1 Ä2n

и только ohé. Во множестве ^т(а) : а 6 KJ максимальное число

является предельной точкой этого множества.

- 9 -

Работа автора со теме диссертации Шарзук эль ОЕейш. Сложность реализации рациональных чисел формулам, последовательность Фибоначчи и приближение иррациональных чисел. - сдано в печать в журнал "Дискретная математика" 2 Гашков С.Б, Марзук эль Овейхан. Сложность приближения кррацио- • нальных чисел рациональными и одно свойство, золотого сечения.-сдано в печать в журнал "Дискретная математика"

Подписано к печати <0Ч 1994 г.

Отпечатано на ротапринте в Формат бумаги 30x42/4

Производственном комбинате Объем & п. л.

Литературного фонда России Заку^Тир. 100