асимптотические решения рекуррентных соотношений

асимптотические решения рекуррентных соотношений Введение 0.1 Общая характеристика работы. 0.2 Обзор содержания диссертации. 1 Асимптотика типа Планшереля—Ротаха для линейных рекуррентных соотношений с  рациональными коэффициентами 1.1 Введение. 1.2 Описание метода и результаты. 1.2.1 Постановка задачи и структура метода решения. 1.2.2 Построение решений с помощью Уп 1.2.3 Базис и общее решение 1.2.4 Нахождение Уп в областях 5. 1.2.5 Переходная зона Ес (случай р=2). 1.2.6 Примеры 1.3 Обоснование результатов. 1.3.1 Доказательство теоремы 1.2.1 и предложения 1.2. 1.3.2 Доказательство теоремы 1.2. 1.3.3 Доказательство теоремы 1.2. 1.3.4 Доказательство Теоремы 1.2. 1.4 Примеры (получение асимптотик). 1.4.1 Получение асимптотики многочленов Эрмита 1.4.2 Получение асимптотики многочленов Мейкснера. 2 Разностные уравнения с базисами степенного роста, возмущённые спектральным  параметром 2.1 Введение.2.1.1 Постановка задачи. 2.1.2 Обозначения и соглашения. 2.1.3 Рекуррентные соотношения с базисами степенного роста 2.1.4 Асимптотика спектральных возмущений 2.1.5 Примеры применения теоремы 2.1.2. 2.2 Доказательство теоремы 2.1.1. 2.3 Доказательство теоремы 2.1.2. 2.4 Локальные асимптотики ортогональных и совместно ортогональных многочленов. 2.4.1 Асимптотика ортогональных многочленов в окрестности предельной точки масс меры и осцилляций веса. 2.4.2 Совместно ортогональные многочлены Якоби. 2.4.3 Совместно ортогональные многочлены Лагерра. 3 Рекуррентные соотношения для рациональных аппроксимаций постоянной Эйлера 3.1 Введение. 3.2 Связь 7­форм с рекуррентными соотношениями для Qn{ 1) 3.2.1 Получение четырёхчленного рекуррентного соотношения для форм. 3.2.2 Доказательство теоремы 3.1.1. 3.3 О некоторой процедуре нахождения асимптотических разложений для решений  разностных уравнений. 3.3.1 Доказательство теоремы 3.3.1. 3.3.2 Доказательство лемм 3.4 Система рекуррентных соотношений для рациональных ап­проксимациий постоянной  Эйлера. 3.4.1 Системы рекурсий для многочленов, задаваемых формулой Родрига. 3.4.2 Доказательство теорем 3.4.1 и 3.4.3.5 Определитель целочисленной решётки, порождённой рациональными аппроксимациями постоянной Эйлера. 3.5.1 Минимальные векторы Ь и иррациональность 7. 3.5.2 Доказательство теоремы 3.5.1. 3.5.3 Оценки векторов решётки Ь и форм Рп. Введение диссертации (часть автореферата) На тему "Асимптотики решений  рекуррентных соотношений" 0.1. Общая характеристика работы К рекуррентным соотношениям п + «1,п/п­Н­­­­­ь ак,п/п­к = о, п = к,к + 1,. , (0.1)  связывающим между собой элементы последовательности {/п}^=о: приводят многие задачи анализа и теории чисел. В частности, индукцией по п легко проверяется, что  последовательности числителей {^п}^ и знаменателей {вп}£=1 числовой непрерывной  дроби а1 а0 + связаны между собой соотношениями Рп = КРп­1 + ЯпРп­2 , Я.П = Мп­1 + адп2 , 71=1,2,. и удовлетворяют начальным условиям  р­\ = 1, ро = ^о и <7­1 = 0, до = 1 Рекуррентные соотношения являются одним из древнейших математических объектов. С  ними связаны непрерывные дроби, алгоритм Эвклида, числа Фибоначи и другие  математические артефакты. Рекурсии, возникающие при разложении некоторых классов  аналитических функций в непрерывные дроби, впервые появились в работах Эйлера, а  Гаусс разложил в непрерывную дробь отношение гипергеометрических функций.  Исследования по теории непрерывных дробей и рекуррентных соотношений таких великих  математиков, как Риман, Стилтьес, Чебышев, Эрмит, Якоби, Марков, Рама­нуджан,  Пуанкаре, оказали далеко идущее влияние на дальнейшее развитие математики. Понятие  рекуррентных соотношений не потеряло своей актуальности и в наше время. Со второй половины 20­го века наблюдается новый рост интереса к рекуррентным  соотношениям в связи с непрерывными дробям и конструкциями рациональных  аппроксимаций аналитических функций. Эти конструкции впервые появились в конце 19­ го века в работах Эрмита, а затем Адамара и Паде, и получили общее название  аппроксимаций Паде. Аппроксимации Паде являются удобным вычислительным  инструментом процесса обработки данных, определяющих аналитическую функцию.  Другим современным приложением рекуррентных соотношений является теория  разностных уравнений, особенно в случае, когда разностное уравнение появляется какрезультат аппроксимации дифференциального уравнения при численном решении  последнего. Теория асимптотик решений рекуррентных соотношений, включающая в себя  асимптотическую теорию ортогональных многочленов и их обобщений, тесно связана с  вопросами сходимости непрерывных дробей, рациональных аппроксимаций; другая область применения — спектральные задачи разностных операторов, задача рассеяния. Среди  многочисленных работ, внесших за последнее время существенный вклад в развитие  асимптотической теории рациональнах аппроксимаций, ортогональных многочленов и  рекуррентных соотношенрШ, отметим работы А.Аптекарева, В.Буслаева, В.Буярова,  А.Гончара, В.Дзядыка, В.Калягина, Е.Никишина, В.Прохорова, Е.Рахманова, В.Сорокина,  П.Суетина, С.Суетина, И.Ша­рапудинова, Б.Беккермана, В. Ван Аше, М.Варги,  Д.Геронимо, П.Дейфта, A.Куэларса, Г.Лопеса, Д.Любинского, А.Мартинеса, Дж.Наттола,' Е.Саффа, B.Тотика, Г.Шталя. Нетрудно проверить, что всякая последовательность {/п}, удовлетворяющая  рекуррентному соотношению (0.1) с постоянными (не зависящими от п) коэффициентами а %,., а^ может быть записана в следующем явном виде т + > П> п0­к (0.2) 3=1 где Аь ., Аш ­ корни характеристического многочлена = хк + + ­ + ак кратностей Ь,. ,1т соответственно, ¿14— * 1"т — к. Из явного вида (0.2) последовательности {/п}^0 следует, что если корни  характеристического многочлена к(г) различны по модулю, то существует предел Нш^оо  /п+1//п, и этот предел равен одному из корней характеристического многочлена.  Оказывается, что это утверждение имеет место не только для рекуррентных соотношений с постоянными коэффициентами, но и для рекуррентных соотношений с предельно  постоянными коэффициентами, когда найти явный вид последовательности не  представляется возможным. Соответствующее утверждение составляет  содержание теоремы Пуанкаре одной из самых тонких в теории рекуррентных  соотношений. Теорема (Пуанкаре см. /110/). Пусть последовательность {/п}^=о удовлетворяет  рекуррентному соотношению (0.1) с предельно постоянными коэффициентами, корни  характеристического многочлена h(z) = lim (zk + а^­1 + • • • + akin) (0.3) n­>oo 4 ' которого  различны по модулю. Тогда либо fn = 0 при всех п > щ, либо существует предел limn^oo  fn+i/ fn, и этот предел равен одному из корней характеристического многочлена.Весьма важное уточнение теоремы Пуанкаре было сделано Перроном для невырожденных  рекуррентных соотношений. Напомним, что рекуррентное соотношение (0.1) называется  невырожденным, если ф 0 при всех п = k,k + 1,Невырожденность соотношений (0.1)  означает возможность однозначного определения значения /п при известных значениях /п+ъ • • • ? fn+k Теорема (Перрон см. /108/, /109/). Пусть корни характеристического многочлена  невырожденного рекуррентного соотношения (0.1) с предельно постоянными  коэффициентами различны по модулю. Тогда для всякого корня А характеристического  многочлена найдется последовательность {fn}%Lo> удовлетворяющая рекуррентным  соотношениям (0.1) такая, что lim^oo /п+i/ fn — А. Существенное продвижение в представлении решений рекуррентных соотношений было  получено в цикле работ Биркгофа­Трыжинского (см. /59/, см. /60/, /61/) , в которых для  любых полиномиальных по "п" коэффициентов разностного уравнения (0.1) доказывается  существование асимптотических по "п" рядов для формальных базисных решений. Теорема (Биркгоф, Трыжинский, 1932). Любое линейное разностное уравнение к­го  порядка к аг0)90+г) = 0; (ао ф 0, акф 0) (0.4) г=0 с полиномиальными коэффициентами  а{ имеет ровно к линейно независимых формальных решений следующего общего вида: оо  то р ^ Ь­7 г , (¿(г) = цх 1п г + ^ ; 5=0 .7=0 г=1 рбМ, т€Ш{0} Бели плоскость комплексного переменного г разбить на области кривыми = ^(фД^)), =  1, . ,п, то в каждой такой области, уходящей в бесконечность, существуют п линейно  независимых аналитических решений уравнения (0.4), имеющих найденную асимптотику. Особый интерес представляет случай, когда коэффициенты рекуррентного соотношения  зависят от параметра (обозначим его х): р­ 1 Эп+1(зр = У^аз(п,х)С}пЧ(х) , (0.5) о Именно такие рекуррентные соотношения приводят к ортогональным многочленам и их  обобщениям. Асимптотику решений С2п(х) для случаев стремления к бесконечности  аргумента соотношения (номера п) и параметра х при различных соотношениях между их  ростом называют асимптотиками типа Планшереля­Ротаха. Впервые (см. /107/), они  появились для асимптотического описания многочленов Эрмита Нп при п —> оо и a) х =  (2п+1)^т, 1 + b) х = (2п + 1)з ­ 2­5 3~з п­ъ г, г Е К <Ш С ; c) х = (2п+1)*0, ­1 + 5^0^1­е. для  фиксированных положительных е, си и комплексного I. Напомним, что многочлены Эрмита можно определить рекуррентными соотношениямиНп+1(х) = 2хНп{х) ­ 2пНп­.1(х) , Н0 = 1, Я1=0 пеМ. Асимптотики многочленов Эрмита были получены Планшерелем и Ротахом методом  перевала из интегральных представлений для Нп(х), и долгое время оставался открытым  вопрос о получении подобных асимптотик для многочленов, не обладающих  интегральными представлениями. Последние две декады (в работах Любинского, Рахманова, Тотика и Дейфта с соавторами)  было разработано несколько методик получения и доказательства асимптотических  формул типа Планшереля­Ротаха для ортогональных на действительной оси многочленов,  используя в качестве входных данных положительные веса ортогональности. В то же  время, в работах Шталя, Гончара, Рахманова, Аптекарева, С.Суетина, Наттола, а также  Дейфта с соавторами был достигнут определенный прогресс в получении асимптотик  многочленов, определяемых неэрмитовыми соотношениями ортогональности. Отметим,  что именно неэрмитовы соотношения ортогональности сохраняют наличие рекуррентных,  соотношения для ортогональных многочленов при рассмотрении комплексных весов  ортогональности, сосредоточенных в комплексной плоскости. • Однако, более или менее общие методики, позволяющие получать подобные асимптотики  исходя из рекуррентных соотношений вида (0.5), ещё не так развиты. Первые глубокие  результаты в этом направлении получены Геронимо с соавторами (м. /85/).Также отметим,  отсутствие общих методов исследования сильных асимптотик для многочленов  ортогональных относительно дискретных весов. В связи с этим актуальной задачей является построение асимптотических разложений для  базисных решений разностных уравнений (0.5) в перекрывающихся, уходящих на  бесконечность областях плоскости (п, х). Согласование ("сшивка") решений в пересечении  рассматриваемых областей позволяет получить глобальную асимптотическую картину  решений уравнений (0.5) в комплексной плоскости параметра х, при выборе  соответствующего масштаба, зависящего от п. Тем самым, искомый метод должен быть  ориентирован на получение глобальных асимптотик решений (0.5), используя в качестве  входных данных коэффициенты рекурсий, подобно тому, как метод наискорейшего спуска  для матричной задачи Римана­Гильберта (м. /74/, /75/) решает эту задачу для  ортогональных многочленов, стартуя с весов ортогональности. В некоторых ситуациях глобальное асимптотическое описание решения рекуррентных  соотношений не обеспечивает точного описания решения в областях (п, х) при маленьких х. Например, речь может идти о локальной асимптотике многочленов Лагерра в окрестности  точки х = 0. Сформулируем общую актуальную задачу о локальных асимптотиках такого  сорта. Рассматриваются разностные уравнения со спектральным параметром х кQ(n, х) = f(n)x qn+r + qn+i = 0, 0n G N, Z. (0.6) 0 Коэффициенты таковы, что при х — 0 уравнение (0.6) имеет решение степенного роста (с  некоторыми полиномами pj 0) Q(n,0) = 0 3 fy G С, nоо. (0.7) з Задача заключается в получение асимптотик решения (0.6), (0.7), равномерных в  "масштабированных" окрестностях т. х = 0 спектрального параметра Яп{х) ~ ?, х Siîft С С, поо. Мотивацию этой задачи можно пояснить следующими качественными соображениями.  Известно, что вне спектра решения разностных уравнений имеют экспоненциальный  характер роста или убывания. На спектре можно говорить об осцилляционном,  ограниченном характере решений. Степенной рост вида (0.7) характерен для решений  разностных уравнений (0.6) в концевых точек непрерывного спектра. Например,  ортогональные многочлены, удовлетворяющие трех­членному рекуррентному  соотношению, имеют такой порядок роста в конце носителя веса ортогональности. Тоже  справедливо и для совместно ортогональных многочленов, удовлетворяющих  рекуррентным соотношениям высокого порядка. Первые результаты в этом направлении  были получены Аптекаревым (м. /4/). Наконец, остановимся на приложениях асимптотической теории рекуррентных  соотношений. Диофантовы приближения математических констант ­ одно из наиболее  важных приложений теории рекуррентных соотношений, непрерывных дробей и  рациональных аппроксимаций аналитических функций. Многие из доказательств  трансцендентности (иррациональности) знаменитых констант основываются на  конструкциях аппроксимаций или интерполяций аналитических функций. Особый интерес  вызывает задача о построении и изучении асимптотических свойств последовательностей  рациональных приближений к постоянной Эйлера Постоянная Эйлера 7 наиболее известная константа, связанная с эйлеровыми суммами  (значениями дзета функции Римана в натуральных точках) Арифметическая природа постоянной 7 и значений в нечетных точках до сих пор не  поддается исследованию (значения ("(5) в четных точках были получены еще Эйлером).  Пока единственным конкретным результатом в этом направлении является доказательство  Р. Апери в 1978 году иррациональности С(3).Теорема (Апери /49/). Пусть числа ип и уп задаются следующим рекуррентным  соотношением п 4­ 1)3ип+1 = (2п + 1)(17п2 + 17п + 5)^ ­ п^и^ с начальными условиями  г>0:=0, := в, щ := 1, щ := Ъ. Тогда ип, £ Уп 6 N (здесь обозначает наименьшее общее кратное чисел {1,2, .,п}), и  справедливы асимптотические формулы ип\1'п = {^2 + 1)А + о(1), г>п­С(3)гд1/п = (^­1)4 +  о(1). Тем самым, рекуррентное соотношение теоремы Апери не только определяет  рациональные приближения £(3) ­ С(з), ип но и (в виду того, что ВпП —>• е, и е3(л/2 — I)4 « 0.591. < 1) доказывает  иррациональность С(3)­ Надо также отметить, что построение с помощью рекуррентных  соотношений рациональных приближений к математическим константам имеет  самостоятельный интерес и известно всего лишь несколько результатов(м. /33/, /112/, /40/)  в этом направлении. Целью работы является: О исследование решений рекуррентных (по п) соотношений с параметром х и  коэффициентами от (п, х) общего вида (см. (0.5)) в перекрывающихся, уходящих на  бесконечность областях пространства (п, х)\ 0 нахождение глобальных асимптотических разложений конкретных систем многочленов,  генерируемых рекуррентными соотношениями с рациональными по (п, х) коэффициентами  (включая многочлены ортогональные относительно дискретного веса); О нахождение локальных асимптотик решений степенного роста рекуррентных  соотношений со спектральным параметром; О исследование асимптотических и арифметических свойств рекуррентных соотношений,  генерирующих рациональные аппроксимации постоянной Эйлера. В основе проведенного в диссертации исследования лежат методы теории функции,  комплексного анализа, специальных функций, обыкновенных дифференциальных  уравнений и элементы теории динамических систем. Все приведенные в диссертации результаты являются новыми. Основные полученные  результаты таковы: 1) предложен и обоснован метод получения глобально согласованных разложений базисных решений рекуррентных соотношений с рациональными от номера и полиномиальными от  параметра коэффициентами;2) получены и доказаны формулы сильной асмптотики (типа Планше­реля ­ Ротаха) для  многочленов Мейкснера. 3) описан класс рекуррентных соотношений, базисные решения которых имеют степенной  рост; для решений этих рекуррентных соотношений доказаны асимптотики, равномерные  по спектральному параметру, взятому в соответствующих масштабах; 4) найдена асимптотика базиса решений рекуррентных соотношений генерирующих  рациональные аппроксимации постоянной Эйлера; доказана це­лочисленность числителей и знаменателей этих аппроксимаций. Диссертация изложена на 236 страницах и состоит из введения, трех глав, разбитых на  параграфы, приложения и списка литературы, содержащего 138 наименований. Список литературы диссертационного исследования доктор физико­математических  наук Туляков, Дмитрий Николаевич, 2011 год 1. М. Абрамович, И. Стиган, Справочник по специальным функциям, М. Наука, 1979. 2. А. И. Аптекарев, Асимптотические свойства многочленов, ортогональных на системе  контуров, и периодические движения цепочек Toda, Матем. сб. 125, (2), (1984), 231­258. 3. А. И. Аптекарев, Асимптотика полиномов совместной ортогональности в случае  Андэюелеско, Матем. сб. 136(125), 1(5), (1988), 56­84. 4. А. И. Аптекарев, Асимптотика ортогональных полиномов в окрестности концевой точки  интервала ортогональности, Матем. сб. 183,5., (1992), 42­62. 5. А. И. Аптекарев, Сильная асимптотика многочленов совместной ортогональности для  систем Никишина, Матем. сб. 190, (5), (1999), 3­44. 6. А. И. Аптекарев, Точные константы рациональных аппроксимаций аналитических  функций, Матем. сб. 193, (1), (2002), 3­72. 7. А. И. Аптекарев, Г. Лопес Лагомасино, И. А. Роча, Асимптотика отношения  многочленов Эрмита­Паде для системы Никишина, Матем. сб. 196, (8), (2005), 4­20. 8. А. И. Аптекарев и Р. Ф. Хабибулин, Асимптотические ряды для многочленов,  ортогональных относительно комплексного переменного веса, Труды ММО 68, (2006), 3­ 43. 9. А. И. Аптекарев (редактор), Рациональные аппроксимации константы Эйлера и  рекуррентные соотношения, Совр. пробл. матем., 2007:9.10. А. И. Аптекарев, В. Г. Лысов Асимптотика 7­форм, генерируемых совместно  ортогональными многочленами, Современные проблемы математики, 2007, вып. 9, ред. А.  И. Аптекарев, МИР АН, 55­62 11. Н. И. Ахиезер, Классическая проблема моментов и некоторые вопросы анализа,  связанные с нею, Физматгиз, М. 1961, 12. Н.И. Ахиезер, Лекции по теории аппроксимаций, М.­Л., ОГИЗ­ТТЛ, 1947. 13. А. И. Боголюбский, Рекуррентные соотношения с рациональными коэффициентами для некоторых совместно ортогональных многочленов, задаваемых формулой Родрига,  Современные проблемы математики, 2007, вып. 9, ред. А. И. Аптекарев, МИРАН, 27­35. 14. Ж. Бустаманте, Г. Лопес Лагомасино, НегтИе­РасЬё аппроксилшции для никишинских  систем аналитических функций, Мат. Сб., 138 (1992), № 11, 117­138. 15. Ф. Д. Гахов, Краевые задачи, М., ГИФМЛ, 1963. 16. А. О. Гельфонд, Исчисление конечных разностей,2­е изд. ГИФМЛ М. 1959, 17. A.A. Гончар, Рациональные аппроксимации аналитических функций, Труды  международного конгресса математиков. Беркли, 1986,1987, 739­748. 18. А. А. Гончар, О задачах Е. И. Золотарёва, связанных с рациональными функциями,  Матем. сб. 78 120, (4) (1969), 640­654. 19. А. А. Гончар, О скорости рациональной аппроксимации аналитических функций,  Труды МИАН. 116 (1984), 52­60. 20. A.A. Гончар, О скорости рациональной аппроксимации некоторых аналитических  функций, Матем. сб. 105(147), 2, (1978), 147­163. 21. А. А. Гончар, Скорость рациональной аппроксимации и свойство однозначности  аналитических функций в окрестности изолированной особой точки, Матем. сб. 94(136), 2,  (1974), 266­282. 22. A.A. Гончар, Г. Лопес, О теореме Маркова для многоточечных аппроксимаций Паде,  Матем. сб. 105(147), 4, (1978), 512­524. 23. А. А. Гончар, Е. А. Рахманов, Равновесная мера и распределение нулей экстремальных  многочленов, Матем. сб. 125(167), 1, (1984),117­127. 24. А. А. Гончар, Е. А. Рахманов, О сходимости совместных аппроксимаций Паде для  систем функций марковского типа, Труды МИАН, 157, 1981, 31­48.25. A.A. Гончар, E.А. Рахманов, О задаче равновесия для векторных потенциалов, УМН,  40, 4, 1985, 155­156. 26. А. А. Гончар, Е. А. Рахманов, Равновесные распределения и скорость рациональной  аппроксимации аналитических функций, Матем. сб. 134, 3, (1987),306­352. 27. A.A. Гончар, Е.А. Рахманов, В.Н. Сорокин Аппроксимации Эрмита­Паде для систем  функций марковского типа, Матем. сб. 188, 5, (1997),33­58. 28. А. Р. Итс, А. В. Китаев, А. С. Фокас, Изомонодромный подход в теории двумерной  квантовой гравитации, УМН., 1990, vol. 45, 6, 135­136. 29. В. А. Калягин, Об одном классе полиномов, определяемых двумя соотношениями  ортогональности, Матем. сб. 1979, Vol. 110(152), 4(12), 609­627. 30. В. А. Калягин, Аппроксимации Эрмита­Паде и спектральный анализ несимметричных  операторов, Матем. сб. 1994, Vol. 185, (6), 79­100. 31. H. С. Ландкоф, Основы современной теории потенциала, М., Наука, 1966. 32. В. Г. Лысов, Сильная асимптотика аппроксимаций Эрмита­Паде для  системы стильтьесовских функций с весом Лагерра, Матем. сб. 196, (12), (2005), 99­122. 33. Ю. В. Нестеренко, Некоторые замечания о С(3), Матем. заметки, 59 ­(6), (1996), 865­ 880. 34. Е. М. Никишин, Асимптотика линейных форм для совместных аппроксимаций Паде,  Изв. вузов. Сер. матем., 1986, 2, 33­41. 35. Е. М. Никишин, В.Н Сорокин. Рациональные аппроксимации и ортогональность, М.,  Наука, 1988. 36. Е. А. Рахманов, Об асимптотических свойствах многочленов, ортогональных на  вещественной оси, Матем. сб. 119(161), 2, (1982),163­203. 37. Г. Сегё, Ортогональные многочлены, М., Физматгиз, 1962. 38. В.Н. Сорокин, Обобщённые многочлены Полачека, Матем. сб. 200, (4), (2009), 113­130. 39. В. Н. Сорокин, Обобщение классических ортогональных многочленов и сходимость  совместных аппроксимаций Паде, Тр. сем. им. И. Г. Петровского, Изд­во Моск. ун­та, М.  1986, Vol. 11, 125­16540. В.Н. Сорокин, Об одном алгоритме быстрого вычисления 7г4, Препринт Ин­та  Прикладной Математики им. М. В. Келдыша РАН, №28, 2002. 41. В. П. Спиридонов, Очерки теории эллиптических гипергеометрических функций, УМН, 63:3(381) (2008), 3­72 42. С. П. Суетин, О равномерной сходимости диагональных аппроксимаций Паде  для гиперэллиптических функций, Матем. сб., 191, (9), (2000), 81­114. 43. С. П. Суетин, О сильной асимптотике многочленов, ортогональных относительно  комплексного веса, Матем. сб. 200, (1), (2009), 81­96. 44. Д. В. Христофоров, Рекуррентные соотношения для аппроксимаций Эрмита­Паде  одной системы из четырёх функций марковского и сти­лтьесовского типа, Современные  проблемы математики, 2007, вып. 9, ред. А. И. Аптекарев, МИР АН, 11­26. 45. И. И. Шарапудинов, Об асимптотике и весовых оценках полиномов Мейкснера,  ортогональных на сетке {0,5,25, :}, Матем. заметки, 62:4 (1997), 603­616. 46. А. А. Шкаликов, Диссипативные операторы в пространстве Крейна.  Инвариантные подпространства и свойства сужений, Функц. анализ и его прил, 41:2 (2007),  93­110. 47. Г. Шталь, Наилучшие равномерные рациональные аппроксимации \х\ на ­1,1., Матем. сб. 183, 8, (1993),85­118. 48. A. Angelesco, Sur deux extensions des fractions continues algébriques, C.R. Acad. Sei. Paris 168 (1919), 262­265. 49. R. Apery, Irrationalité de C(2) et C(3), Asterisque, 61, (1979), 11­13. 50. A. I. Aptekarev, Multiple orthogonal polynomials, J. Comput. Appl. Math. 99 (1998), no. 1­ 1, 423­448. 51. A. I. Aptekarev, P. M. Bleher, and A. B. J. Kuijlaars, Large n limit of Gaussian random  matrices with external source, Part II, Comm. Math. Phys. 259 (2005), 367­389. 52. A.I. Aptekarev, A. Branquinho, W. Van Assche, Multiple orthogonal polynomials for  classical weights, Trans. Amer. Math. Soc. 2003, Vol. 355, (10), 3887­3914. 53. A. I. Aptekarev and H. Stahl, Asymptotics of Hermite­Pade polynomials, in 'Progress in  Approximation Theory' ( A. Gonchar, E. B. Saff, eds.), SpringerVerlag, Berlin, 1992, pp. 127­ 167.54. A. I. Aptekarev and W. Van Assche, Scalar and matrix Riemann­Hilbert approach to the  strong asymptotics of Pade approximants and complex orthogonal polynomials with varying  weight, J. Approx. Theory 129 (2004), №. 2, 129­166. 55. A. I. Aptekarev, V. Kalyagin, G. Lopez Lagomasino and I. A. Rocha On the limit behaviour  of recurrence coefficients for multiple orthogonal polynomials, Journal Approximation Theory,  139, 2006, 346­370. 56. J. Baik, P. Deift, K. T­R. McLaughlin, P. Miller, and X. Zhou, Optimal tail estimates for  directed last passage site percolation with geometric random variables, Adv. Theor. Math. Phys.  5 (2001), no. 6, 1207­1250. 57. R. T. Baumel, J. L. Gammel, and J. Nuttall, Asymptotic form of Hermite­Pade polynomials,  IMA J. Appl. Math. 27 (1981), no. 3, 335­357. 58. S. N. Bernstein, Sur les polynomes orthogonaux relatifs a un segment fini. I, II, J. Math.  Pures Appl. (9) 9 (1930), 127­177; 10 (1931), 219­286. 59. D. G. Birkhoff, General Theory of Linear Difference Equations, Trans. Amer. Math. Soc.  1911, Vol. 12, (2), 243­284. 60. D.G. Birkhoff, W.J. Trjitzinsky, Analytic theory of singular difference equations, Acta Math. 1933, Vol. 60, (1), 1­89. 61. D.G. Birkhoff, Formal theory of irregular linear difference equations, Acta Math. 1930, Vol.  54, (1), 205­246. 62. P. Bleher and A. Its, Semiclassical asymptotics of orthogonal polynomials, Riemann­Hilbert  problem, and universality in the matrix model, Ann. Math. 150 (1999), 185­266. 63. P. Bleher and A. Its, Double scaling limit in the random, matrix model: the Riemann­Hilbert  approach, Comm. Pure Appl. Math. 56 (2003), 433­516. 64. P. M. Bleher and A. B. J. Kuijlaars, Large n limit of Gaussian random matrices with external  source, Part /, Comm. Math. Phys. 252 (2004), 4376. 65. P. M. Bleher and A. B. J. Kuijlaars, Large n limit of Gaussian random matrices with external  source, Part III. Double scaling limit, Comm. Math. Phys. 270 (2007), 481­517. 66. P. B. Borwein, Quadratic Hermite­Pade approximation to the exponential function, Constr.  Approx. 2 (1986), 291­302.67. M. de Bruin, Some aspects of simultaneous rational approximation, in "Numerical Analysis  and Mathematical Modelling", Banach Center Publications 24, PWN­Polish Scientific  Publishers, Warsaw, 1990, pp. 51­84. 68. T. Claeys and A. B. J. Kuijlaars, Universality of the double scaling limit in random matrix  models, Comm. Pure Appl. Math. 59 (2006), 1573­1603. 69. T. Claeys and A. B. J. Kuijlaars, Universality in unitary random matrix ensembles when the  soft edge meets the hard edge, preprint arXiv:math­ph/0701003. 70. T. Claeys, A. B. J. Kuijlaars and M. Vanlessen, Multi­critical unitary random matrix  ensembles and the general Painleve II equation, preprint arXiv:math­ph/0508062, Annals of  Mathematics (to appear). 71. T. Claeys and M. Vanlessen, Universality of a double scaling limit near singular edge points  in random matrix models, Comm. Math. Phys. 273 (2007), 499­532. 72. E. Daems, A. B. J. Kuijlaars, and W. Veys, Asymptotics of non­intersecting Brownian  motions and «4x4 Riemann­Hilbert problem, preprint arXiv:math/0701923. 73. P. Deift, Orthogonal Polynomials and Random Matrices: a RiemannHilbert approach,  Courant Lecture Notes in Mathematics, Vol. 3, New York; Amer. Math. Soc., Providence RI,  1999. 74. P. Deift and X. Zhou, A steepest descent method for oscillatory RiemannHilbert problems.  Asymptotics for the MKdV equation, Ann. of Math. (2) 137 (1993), №. 2, 295­368. 75. P. Deift, T. Kriecherbauer, K. T­R. McLaughlin, S. Venakides, and X. Zhou, Strong  asymptotics of orthogonal polynomials with respect to exponential weights, Comm. Pure Appl.  Math. 52 (1999), №. 12, 1491­1552. 76. P. Deift, T. Kriecherbauer, K. T­R. McLaughlin, S. Venakides, and X. Zhou, Asymptotics  for polynomials orthogonal with respect to varying exponential weights, Internat. Math. Res.  Notices 1997:16 (1997), 759­782. 77. M. Duits and A. B. J. Kuijlaars, Painlevé I asymptotics for orthogonal polynomials with  respect to a varying quartic weight, Nonlinearity 19 (2006), 2211­2245. 78. V. Kaliaguinea, A. Ronveaux, On an system of "classical" polynomials of simultaneous  orthogonality, J. Comput. Appl. Math. 1996, Vol. 67, (2), 20721779. S. Kamvissis, K. T­R. McLaughlin, and P. D. Miller, Semiclassical soliton ensembles for the  focusing nonlinear Schrödinger equation, Annals of Mathematics Studies, Vol. 154, Princeton  Univ. Press, Princeton NJ, 2003. 80. T. Kriecherbauer and K. T­R. McLaughlin, Strong asymptotics of polynomials orthogonal  with respect to Freud weights, Internat. Math. Res. Notices 1999:6 (1999), 299­333. 81. A. B. J. Kuijlaars, K. T­R. McLaughlin, W. Van Assche, and M. Vanlessen, The Riemann­ Hilbert approach to strong asymptotics for orthogonal polynomials on ­1,1., Adv. Math. 188  (2004), no. 2, 337­398. 82. A. B. J. Kuijlaars, H. Stahl, W. Van Assche, and F. Wielonsky, Asymptotique des  approximants de Hermite­Padé quadratiques de la fonction exponentielle et problèmes de  Riemann­Hilbert, C.R. Math. Acad. Sei. Paris 336 (2003), 893­896. 83. A. B. J. Kuijlaars, H. Stahl, W. Van Assche, and F. Wielonsky, Type II Hermite­Pade  approximation to the exponential function, J. Comput. Appl. Math, (to appear) 84. A. B. J. Kuijlaars, W. Van Assche, and F. Wielonsky, Quadratic Hermite­Pade  approximation to the exponential function: a Riemann­Hilbert approach, Constr. Approx. 21  (2005), 351­412. 85. A. K. Lenstra, H. W. Lenstra, and L. Lovasz, Factoring polynomials with rational  coefficients, Mathematische Annalen, 1982, 261, 515­534. 86. G. Lopez, Szego's theorem for polynomials orthogonal with respect to varying measures,  Berlin, Springer­Verlag, 1988. (Lecture Notes in Math. V. 1329.) 87. D.S. Lubinsky Strong asymptotics for extremal errors and polynomials associated with  Erdos­type weights, Longman Scientific and Technical, Harlow, UK, 1989. (Pitman Res. Notes  Math. Ser. V. 202.) 88. V. Lysov, F. Wielonsky, Strong asymptotics for multiple Laguerre polynomials, Constructive approximation 28, (2008), 61­111. 89. K. Mahler, Perfect systems, Compositio Math. 19 (1968), 95­166. 90. A. A. Markov, Deux demonstrations de la convergence de certaines fractions continues, Acta Math. 19 (1895), 93­104. 91. J. Nuttall, The convergence of Fade approximants to functions with branch points, in 'Pade  and rational Approximation' (E. B. Saff, R. S. Varga, eds.), Academic Press, New York, 1977,  pp. 101­109.92. J. Nuttall, Sets of minimum capacity, Padé approximants and the bubble problem, in  'Bifurcation Phenomena in Mathematical Physics and Related Topics' (C. Bardos, D. Bessis,  eds.), Reidel, Dordrecht, 1980, pp. 185­201. 93. J. Nuttall, Hermite­Padé approximants to functions meromorphic on a Riemann surface, J.  Approx. Theory 32 (1981), no. 3, 233­240. 94. J. Nuttall, Asymptotics of­diagonal Hermite­Padé polynomials, J. Approx. Theory 42 (1984), no. 4, 299­386. 95. J. Nuttall and S. R. Singh, Orthogonal polynomials and Padé approximants associated with a  system of arcs, J. Approx. Theory 21 (1977), no. 1, 1­42. 96. M. Plancherel, W. Rotach, Sur les valeures asymptotiques des polynomes d'Hermite,  Commentarii Math. Helvetici, 1929, Vol. 1, 227­257. 97. O. Perron, Über einen Satz des Herrn Poincaré, J. Reine Angew. Math. 1909, Vol. 136, 17­ 37. 98. O. Perron, Über die Poincarésche lineare Differenrengleichung, J. Reine Angew. Math. 1910, Vol. 137, 6­64. 99. H. Poincaré, Sur les Equations Linéaires aux Différentielles Ordinaires et aux Différences  Finies, Amer. J. Math. 1885, Vol. 7,(3), 203­258. 100. T. Rivoal, W. Zudilin, Diophantine properties of numbers related to Catalan's constant,  Math. Annalen, 326 (4), (2003), 705­721. 101. T. Rivoal, Rational approximations for values of derivatives of the gamma function,  (http://www­fourier.ujf­grenoble.fr/ rivoal/articles.html) 102. E. B. Saff and V. Totik, Logarithmic Potentials with External Fields, Springer­Verlag,  New­York, 1997. 103. C. L. Siegel, Topics in Complex Function Theory, Interscience, New York, Vol. I, 1969;  Vol. II, 1971. 104. H. Stahl, The structure of extremal domains associated with an analytic function, Complex  Variables Theory Appl. 4 (1985), no. 4, 339­354. 105. H. Stahl, Orthogonal polynomials with complex­valued weight function. I, II, Constr.  Approx. 2 (1986), no. 3, 225­240; 241­251.106. H. Stahl, Simultaneous rational approximants, in 'Computational Methods and Function  Theory 1994 (Penang)', World Scientific, Singapore, 1995, pp. 325­349. 107. H. Stahl, Asymptotics for quadratic Hermite­Pade polynomials associated with the  exponential function, Electronic Trans. Num. Anal. 14 (2002), 193220. 108. H. Stahl, Quadratic Hermite­Pade polynomials associated with the exponential function, J.  Approx. Theory 125 (2003), 238­294. 109. H. Stahl, Asymptotic distributions of zeros of quadratic Hermite­Pade polynomials  associated with the exponential function, Constr. Approx. 23, no. 2 (2006), 121­164. 110. V. Totik Weighted approximation with varying weights, Berlin, SpringerVerlag, 1994.  (Lecture Notes in Math. V. 1569.) 111. W. Van Assche, Pade and Hermite­Pade approximation and orthogonality, Surveys in  Approximation Theory 2 (2006), 61­91. 112. F. Wielonsky, Asymptotics of diagonal Hermite­Pade approximants to e~, J. Approx.  Theory 90 (1997), 283­298. 113. Д. H. Туляков, О локальной асимптотике отношения ортогональных полиномов в  окрестности крайней точки носителя меры ортогональности, Матем. сб. 2001, Vol. 192, (2), 139­160. 114. Д. Н. Туляков, Базисы степенного роста разностных уравнений со спектральным  параметром, Матем. сб. 200, (5), (2009), 129­158. 115. Д. Н. Туляков, Асимптотика типа Планшереля­Ротаха для линейных рекуррентных  соотношений с рациональными коэффициентами, Матем. сб. 201, (9), (2010), 111­158. 116. Д. Н. Туляков, Система рекуррентных соотношений для рациональных  аппроксимациий постоянной Эйлера, Матем. Заметки, 2009, 85, (5), 782­787. 117. Д. Н. Туляков, О некоторой процедуре нахождения асимптотических разложений для  решений разностных уравнений, Современные проблемы математики, 2007, вып. 9, ред. А.  И. Аптекарев, МИРАН, 45­53. 118. Д. Н. Туляков, Об одном свойстве условно сходящихся рядов , Матем. заметки, 2007,  81:2, 317­320.119. А. И. Аптекарев, Д. Н. Туляков, Четырёхчленные рекуррентные соотношения для 'у­ форм, Современные проблемы математики, 2007, вып. 9, ред. А. И. Аптекарев, МИРАН,  37­43. 120. А. И. Аптекарев, Д. Н. Туляков, Об определителе целочисленной решётки,  генерируемой рациональными аппроксимациями постоянной Эйлера, Труды ММО, 70,  2009, 329­345. 121. А. И. Аптекарев, В. Г. Лысов, Д. Н. Туляков, Глобальный режим распределения  собственных значений случайных матриц с ангармоническим потенциалом и внешним  источником, ТМФ, 2009, 159:1, 34­57. 122. A.I. Aptekarev, V.A. Kalyagin, V.G. Lysov and D.N. Tulyakov, Equilibrium of vector  potentials and uniformization of the algebraic curves of genus 0, J. Сотр. and Appl. Math., 233  (2009), 602­616. 123. A.I. Aptekarev, A. Draux, D.N. Tulyakov, Discrete spectra of certain corecursive Pollaczek  polynomials and its applications, Function Theory and Computational Methods, 2002, 2(2), 519­ 537 124. А. И. Аптекарев, В. Г. Лысов, Д. Н. Туляков, Случайные матрицы с внешним  источником и асимптотика совместно ортогональных многочленов, Матем. сб., 2011, 202:2, 3­56. Научная библиотека диссертаций и авторефератов  disserCat http://www.dissercat.com/content/asimptotiki­reshenii­rekurrentnykh­ sootnoshenii#ixzz3RL69eKip Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется  в анализе алгоритмов для получения асимптотической оценки рекурсивных  соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их  выполнения. Теорема была популяризована в книге Алгоритмы: построение и  анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в  которой она была введена и доказана.Не все рекурсивные соотношения могут быть решены с помощью основной теоремы.  Существует несколько её обобщений, в том числе Akra­Bazzi method. Функция T( n : размер задачи ) определена как:    if n < 1 then exit    Выполнить некоторое количество вычислений f(n)    T(n/b)    T(n/b)    ...повторить a раз...    T(n/b)  конец функции В приведенном примере алгоритм рекурсивно разделяет исходную задачу размера n на  несколько новых подзадач, каждая размером n/b. Такое разбиение может быть  представлено в виде дерева вызовов, в котором каждый узел соответствует рекурсивному  вызову, а ветви, исходящие из узла — последующим вызовам для подзадач. Каждый узел  будет иметь a ветвей. Также в каждом узле производится объём работы, соответствующий  размеру текущей подзадачи n (переданному в данный вызов функции) согласно  соотношению  узлах данного дерева. . Общий объём работы алгоритма определяется как сумма всех работ в  Вычислительная сложность подобных алгоритмов может быть представлена в виде  рекуррентного соотношения  . Его можно решить путем  многократных подстановок выражения  .[1] С помощью основной теоремы возможно быстрое вычисление подобных соотношений, что  позволяет получить асимптотическую оценку времени работы рекурсивных алгоритмов  в нотации ­нотации), не производя подстановок.       O(n) ( ΘОбщая форма[править | править вики­текст] Основная теорема рассматривает следующие рекуррентные соотношения: В применении к анализу алгоритмов константы и функции обозначают:  n — размер задачи.  a — количество подзадач в рекурсии.  n/b — размер каждой подзадачи. (Предполагается, что все подзадачи на каждом  этапе имеют одинаковый размер.)  f (n) — оценка сложности работы, производимой алгоритмом вне рекурсивных  вызовов. В нее также включается вычислительная стоимость деления на подзадачи и  объединения результатов решения подзадач. Основная теорема позволяет получить асимптотическую оценку для следующих трех  случаев: Вариант 1[править | править вики­текст] Общая форма[править | править вики­текст] Если  тогда: , и выполняется соотношение  Пример[править | править вики­текст] Согласно формуле, значения констант и сложности не рекурсивной части задачи: , где  Затем, проверяем, выполняется ли соотношение 1 варианта:. Следовательно, (Для данного примера точное решение рекуррентности даёт  условии  ). , при Вариант 2[править | править вики­текст] Общая форма[править | править вики­текст] Если для некоторой константы k ≥ 0 выполняется:  где  тогда: Пример[править | править вики­текст] Согласно формуле, значения констант и сложности не рекурсивной части задачи:  где  Проверяем соотношение варианта 2: , и следовательно,  В соответствии с 2 вариантом основной теоремы: Таким образом, рекуррентное соотношение T(n) равно  (Θ n log n). (Этот результат может быть проверен точным решением соотношения, в  котором  , при условии  .)Вариант 3[править | править вики­текст] Общая форма[править | править вики­текст] Если выполняется:  где  а также верно, что:  для некоторой константы   и достаточно больших   (так называемое условие regularity condition) тогда: Пример[править | править вики­текст] Значения констант и функции: , где  Проверяем, что выполняется соотношение из варианта 3: , и, следовательно,  Также выполняется соотношение regularity condition: , при выборе  Следовательно, согласно 3 варианту основной теоремы: Данное рекуррентное соотношение T(n) равно  формуле. (Θ n2), что совпадает с f (n) в изначальной(Этот результат подтверждается точным решением рекуррентности, в  котором  , при условии  .) Выражения, не решаемые основной теоремой[править | править вики­текст] Следующие соотношения не могут быть решены с применением основной теоремы:[2]  a не является константой, для основной теоремы требуется постоянное количество  подзадач  между f(n) и   существует неполиномиальная зависимость  a<1, но основная теорема требует наличия хотя одной подзадачи  f(n) является отрицательной величиной  близко к варианту 3, но не выполняется regularity condition. Во втором примере разница между   и   может быть выражена  соотношением  любой константы  теорема неприменима. . Следовательно, разница не является полиномом и основная  . Из него видно, что   для  Применение к некоторым алгоритмам[править | править вики­текст] Алгоритм Рекуррентное  соотношение Время  работы ПримечаниеДвоичный  поиск Обход  бинарного дерева Optimal  Sorted  Matrix  Search Сортиров ка  слиянием [3]   Основная теорема, 2  вариант:  ,  где  Основная теорема, 1  вариант:   гд [3] е  Теорема Akra­Bazzi для  и  получения   для  Основная теорема, 2  вариант:  ,  где