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

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

На правах рукописи УДК 511, 519.7

Марзук эль Овейхан Слокяость приблиаения иррациональных чисел рациональными

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

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

МОСКВА - 1994

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

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

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

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

Защита диссертации состоится 3 июня 1994 года в 16 час. 05 шн. на заседании Специализированного • V совета ... СД.053.05) при ИГУ по адресу: 119899,

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

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

Автореферат разослан "1в" О-У-^Шс! 1994 года. Ученый секретарь Специализированного совета СД.053.05) при МГУ /

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

ОБЩ ХАРШШСТт РАБОЫ

Актуальность темы.

Задай о слошости вычисления или построения в тон ии ином смысле разни оОьектов в последнее время часто рассматривался во многих разделах математики: в анализе ( в теории приввиензй ), шчнслиешаой математике, алгебре ( з так называемой алгебраической теории слошости ), теории чисел, геометрии (в та называемой вычислительной геометрии ), логике и теории алгорпяЕ и более всего - в теории слогасти булевых функций. В частаэсти, вопросы о слогаосш яриблшгенного вычисления кйстзительса чисел, рассматривались, например в работах.Вогне1п Л. ,Вопге1л С.1' и Зягшеп Т.г)

В работе изучавтся задачи о сложности реализации рациональных чисел формулами в некоторш базисах, состояли из арк^гтичесша операций, и о сложности приблихенпя иррациональных чисел рациональными. В качестве базисов будем рассматривать следуете многества слеращй В = { &у,х-у,щ,х/ц,х~\\ },Б0= { г^.г-у.гуд-1,1 }, В, = {пу,1у,х~',\}, Вг = {г+у,х"1,1>, ;В3 = {г+2/,(аГ1С1)"1.1}-Понятие форядулы над базисом В и реализуемой ез функции определяется индуктивно стандгртшм образом, подобно тему как определяются формулы в алгебре логике и теории сложности булзнз £уякщй 3),4) Под слоггостьп формулы понимается число симвмоз иерегепюс и констант (в рассматриваемом случае - единиц) в формуле. Сложностью рационального числа г назывался минимальная сяхшоиь реализущзй

1' Borweln J.M.BonelD R.r. Oil the coaplexlty of laalllar Tunc- . tlons and nrabers.- SliM Review, 1938, v. 30, fl° 4, p.589-60i.

21 Strassen V. Berechnungen In partiellen Algebren endlichen lyps.-Compütüg, 11 -(1973).- 3.161 - 196.

3) Яблонский C.B. Введение в дискретную матаяшку,- Ii.: Наука, 1936.

41 Лупанов О.Б. Асштотические оценки слошосзд управлять систем. - 14.: изд. Ш. IS34.

его формуй к обозначается она Lg(r). Иеру слотш Lg (г) =

= Lg (г) , еж Судет оказало далее, мошо интерпретировать как

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

■ Формулы образуй: простой и важный подкласс схем,прячем любую схему юезо.е изиеняя глубины, преобразоБть в формулу. Глубина является ваша керой сжшгаск, так как она оценивает время вычисления йнкциа с учетом возможности параллельного использования многих процессоров. Изучение формул оправдывается также тем .что некаторга ваш вычислительных устройств моделируются именно формулой.

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

Иетогжка исследований. В работе исгользуит-ся методы деяретшй математики и математической кибернетики, теории чисел и штрической теории диофантоЕЩ приближений.

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

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

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

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

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

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

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

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

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

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

L(a,c) = um { Ь(Г) : |а - Г| « е }. где Ь(г) - знаменатель несократимой дроби, представлявдей число г, Lr (о:,с) = min { Ьд (г) : |а - г| « С i = 0,1,2.

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

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

Нижняя оценка слшносга реализации рациональных шел формулами дается в теореме 3, доказательство которой существенно опирается • на один результат О.Н.Касим-заде. Через -обозначается .п-тый член последовательности йбоначчи, а через [х] - цалая часть числа х. Теорема 3. Ды любой несократимой дроби р/д, р, д е и, Ьд (р/д) ) ^ (р/д) > Ьз (р/д) ^ [1о^(/3(гаК?,рМ/2))]

Б случае пах(д,р) = ?п первое неравенство достигается только на дробях Р/д = или уРкРп_к. где (к,п) < 2.

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

М = МУа-к? " 1 ™ Г«е <П-*> < 2-

В качестве следствия получатся некоторые экстремальные свойства

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

Следствие1 Сред всех несократимых дробей со знаменателем ?п нагменыаув сушу элзментов в представляшшх их обыкновенных цепных дробях имеет дроби и ?П.2/ТП- Минимальные формулы в базисах'В, В0, В,, В2 да этих чисел соотвествуиг цепным дробям

Г0;,1...,1|1 и [О;,I."...1,21,'где 2 = Ы, и цепным дробям

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

п-и раз п-4 раз

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

знам?гатедем наиненыпув сумму элементов в представляпцих их ветвящихся цепных дробях шеют дроби Г^.^ . где (1с,п) « 2. Шшимальннз формулы в упомянутых базисах для этих чисел соответствуя! ветващинея цешнм дробям вида ф + ^ , где - формула,

. соответствущая цепнш дробям [0;,1...,1,1 или [0;^....1,21. а Ф,

р-1 раз р-^ раз

- формула, соответствущая цепным дробям [1;,1___.1,1 или

в-1 раз

Г1;,1....1,21. где {б.й = {к.п-1} (формулы, записи которых в раз

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

- 4 -

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

Первое неравенство теорема 3 достигается при и,о > 2 ш дробей У^уС?^,?^,), у которых (0+1 ,ш) ? 2, (ин1,п) < 2, дроСей

у К0Т0РИ (п-1 .пн-1> « 2, (11+1,и) « 2, и дробей ^Л,*-,). у КОТОРН (Е-1.т+1) « 2,(а+1 ,а-1) < 2 (это утвергдение теоремы верно и для базиса В1), а тают для хробей •

У^ГУ^Г УА^Лт У КИ°-

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

у которых' к.,х,ц = 0,1 и (к*1,Ы) $ 2, « 2,(1+1,п+)) « 2,

£ 2, причем для этих дробей первое нзравениво не достигается (это утверждение теореш верно и для базисов В2 и В3). Минимальные формулы из теормы 4 не -являются цепными дробями. В следущей теорме указывается серия цепных дробей, длз которых достигается неравенства теормы 3. Теорема 5.

Если 1ц СР/О = I, 1 = 0,1,2,3, и при некоторм ьи

V+ > • + ¥ > •

то при любом п е и 1», ([0; |1...1|р/д]) = 14 п.

а

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

Хз (г) = Кг) = 11оё^/5(1(г)-1/2Ш + с ,с = 0 или 1, :

г = Ю;1...1], (0;1... 121... 13.10:1...1221... 13, Ю;1... 12221...1], [0;1...122221...И, [0;1...1222221...11, [0:2222221... 11, [0;1...131...1], [0;1...1231...1), Ю;1...12231...1], [0:1...122231...11, Ю;1...12321...11, [0:1...1321...11, [0:1...13221...1], [0:31...1], £0;331...13. Ю;41...11,10:421...11. Далее суша элементов ценной дроби, представлявде! число г,

- 5 -

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

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

Тео'ренаб. Для лзбнх г « 0+ справедливы соотношения 1(г) » Ь^Сг) = Ьв^Сг) ? (г) » 1з (г) = Ьц(г) ^

/2))]Н1о^(^(Кг)-1 /2)) .1 > (г )-1 /2))].

Для г = (д±1}/д, ?/(?±1), где <з = уп+1 ши , п ? 4, Ьв (Г) = (Г) = (Г) ч Ьп (Г) = Хп(г) =

= и-0^(/5(Цг)-1/гШ = .

а для г = ±1/9 при те1 же д

^ (г) = %(г) = = ио^СУЗС^С^О^/г))].

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

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

> I ' (1+5»% 1о&г I " °а(1

для всех щвшональшх алгебраических чисел «

3^(0,е) г |(1-о(1))1о^ I; для всех чкел а с ограниченными элементами разложения в цепную дробь

^(а.с) ? | - 0(1).

6) Гашков СЛ. О сложности приближенного вычисления действитель-

ных чисел схемами и формулами в некоторых рациональных базисах.-

Даскрешн математика - 1990 - т.2 Я°4 с.25-46

- 6 -

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

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

+ 1) - 2 i Ij, №,е) =

= шах{-2К%(^/е - 1))/4 + I/2J-I. ♦ l))/4J-2} <

< 2Н(/3/С +

Ш'с) - \ <♦.»)+1 = U 1 " 1 J/^

__

1/(V5Vg 6 Ь(#,е) < +

Ilm sup = /i + Ha inf №,c)/e = l//S.

с —» 0 £ c e —♦ 0

В теореме 8 даются асимтотически точные неравенства для меры

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

Zta Inf Ь(«,с)Ус $ 1/V5, гш svp Ua,e)Vc > vA+Xv5,

Е-»0 е->0 с с

[ liffl sup L(ct,e)]/f Ш Inf Ь(а,с)1 >Ф, I е 0 J' е -* О '

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

В теореме 9 устанавливаются асимтотически точные неравенства для меры сложности Ь(а,е) в терминах скорсти роста элементов цепной дроби для а. С ее помощью строятся примеры чисел, у которых функция 1(«,с) для некоторой последовательности растет очень медленно, а для некогрой последовательности сп почта максимально быстро. Теорема 9. Пусть 1{х) - функция, равная в нуле нули и монотонно стремящаяся к -к» при х +®, и положительное число а разлагается в цепную дробь с элементами ов « н, которые бесконечно часто удовлетворяют асимптотическому неравенству ant, ä ifqj. где Pi/^n " й~ая подюдацая дробь. Обозначим g(x) обратную функцию к

Kxjx2. Тогда для некоторых последовательностей е и а .стремящих-

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

> 1Д2сЕй1/д), K«,e¿ < «i/g.

Если se всегда а и € то

1С«,«0 с Щгс&1/с)), Ц«,с) >еЦЩ. .

Кз теореш 9 и теореи йнчина7' выводится следущве утверждение. Следствие 4. Для почти всех а"е к и любого в > о при некоторых положительных с и С

cy/tio^Ciogio^7^ < l(*,c) < С /(íoglcioglog£нг)/с \ а для некоторых последовательностей сп и 5п -» О С//yogi (lOglOgi ) ' > Ца.у,

и п__

1<«.д > с /(íogi(lcgíogi})/c п п

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

Ш sup Lg(ti,c)/lcg 1 /с > О

Е -» О

.и для лгбой монотонной функции L(с), найдется такая аналитическая ФУНКЦИЯ Ь е CIC,l)J, ЧТО

Ш Inf In (Ь,е)Д(е) < 1.

С -» О 2

Существует такая аналитическая функция h е C[a,t>], что для некоторых констант с и С, 0 < с < С,

с los Vе * bgft.c) $ С log 1/с Для формулирования теорем 10 и II понадобятся следущие обозначения. Пусть a = [c0;a1...,cn>...'] - бесконечная цепная дробь, рудс - последовательность подходящих дробей, * = <Jn/?n+1, а <*п = [аю;аЕ+1... ] - последовательность остатков. Если an+2 нечетно,

7,ХинчинА.Я. Шше дроби.-М.: Наука, 1978.

- В -

то пологам rn = (ont2 + 1)/2. Если а^четно, то положим гд = атг/2 в случае ^f)ant3 > I и rn = (aat2 + 2)/2 в противном случае. Положим

■ V 1л о. л) - (г+и*)гИа-г)»+0 Г, (Û а а) -

- (ГЩЫаЩ • Gr"M,a) - т+щщ.

7(а) = Ш вир *-(«). где

п —♦ t»

7ПМ = Bai {Gr (fÎnt1.«n+3'aa+2),Fr ^п+1 'ав+3,аи+г^ ' и и

Обозначим Кц множество всех чисел а « у которых разложения ç цепные дроби не содергат злементов, превосходящих а, а > I.

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

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

Ш SVp ebZ(a,c) = r(ot). с -» О

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

Теорема П.При любом четном а и нечетном а > 7 для всех а е К^

г(«) S 7([l;alal...J), причем равенство возмоано лишь для тесел, в разложениях которых в цепную дробь содержатся сколь угодно даше последовательности медущих друг за другом элементов, совладение с последовательностями al al..-. .При а - 5 среди чисел « « Kg наибольшую величину 7(а) имеют числа вида а =

= [...,1515...51,4,1515...151,...,1515...15) ,4,1515...151,...I,

V . ^-i ^ -

где mln{ fe2El_1 имеет вершим пределом бесконечность ( в про- ■

мвяуткэх меяду соседними блоками ,1515...151,4,1515...151,

К2п-1 Ча могут стоять любые элемента) и только такие числа .

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

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

V й2п-1 йгп

и только они. Во множестве {т(°0 : a е у максимальное число

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

- Э -