Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 2 участников)
Строка 1: Строка 1:
Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t)\,</tex> связаны между собой уравнением Лагранжа <tex>\varphi(s) = s\psi(\varphi(s))</tex>. Мы хотим выяснить, как связаны между собой их радиусы сходимости.
+
Пусть две производящие функции <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t)\,</tex> связаны между собой уравнением Лагранжа <tex>\varphi(s) = s \cdot \psi \cdot (\varphi(s))</tex>. Мы хотим выяснить, как связаны между собой их радиусы сходимости.
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть две [[Производящая функция#main | производящие функции]] <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t),\, \psi(0) = 1\,</tex> с неотрицательными коэффицентами связаны между собой [[Уравнение Лагранжа и теорема Лагранжа#Уравнение Лагранжа и теорема Лагранжа | уравнением Лагранжа]] <tex>\varphi(s) = s\psi(\varphi(s))</tex>. Пусть  <tex>r > 0\,</tex> — [[Степенные ряды#Радиус сходимости | радиус сходимости ряда]]  <tex>\varphi,</tex> причем числовой ряд  <tex>\varphi(r)</tex> сходится. Тогда радиус сходимости ряда <tex>\psi</tex> не меньше <tex>\rho = \varphi(r)</tex>. Если числовой ряд <tex>\varphi '(r)</tex> также сходится, то радиус сходимости ряда <tex>\psi</tex> равен <tex>\rho = \varphi(r)</tex>.
+
Пусть две [[Производящая функция#main | производящие функции]] <tex>\varphi = \varphi(s)</tex> и <tex>\psi = \psi(t),\, \psi(0) = 1\,</tex> с неотрицательными коэффицентами связаны между собой [[Уравнение Лагранжа и теорема Лагранжа#Уравнение Лагранжа и теорема Лагранжа | уравнением Лагранжа]] <tex>\varphi(s) = s \cdot \psi \cdot (\varphi(s))</tex>. Пусть  <tex>r > 0\,</tex> — [[Степенные ряды#Радиус сходимости | радиус сходимости ряда]]  <tex>\varphi,</tex> причем числовой ряд  <tex>\varphi(r)</tex> сходится. Пусть радиус сходимости ряда <tex>\psi</tex> равен <tex>\rho</tex>. Тогда
 +
<tex>1. \ \rho \geqslant \varphi(r),</tex>
 +
 
 +
<tex>2. \ \rho = \varphi(r),</tex> если числовой ряд <tex>\varphi '(r)</tex> также сходится.
 +
 
 
'''Замечание'''
 
'''Замечание'''
 
Требование неотрицательности коэффициентов рядов естественно, если мы рассматриваем производящие функции для языков. В этом случае естественно также ожидать, что радиус сходимости производящего ряда для числа неприводимых слов больше радиуса сходимости производящего ряда для числа всех слов в языке (последняя последовательность растет быстрее последовательности чисел неприводимых слов).
 
Требование неотрицательности коэффициентов рядов естественно, если мы рассматриваем производящие функции для языков. В этом случае естественно также ожидать, что радиус сходимости производящего ряда для числа неприводимых слов больше радиуса сходимости производящего ряда для числа всех слов в языке (последняя последовательность растет быстрее последовательности чисел неприводимых слов).
  
 
|proof=
 
|proof=
Докажем, что ряд  <tex>\psi(s)</tex> сходится абсолютно в любой точке  <tex>s,\,\left\vert s \right\vert = q < \rho</tex>.
+
<tex>1. \  </tex>Докажем, что ряд  <tex>\psi(s)</tex> сходится абсолютно в любой точке  <tex>s,\,\left\vert s \right\vert = q < \rho</tex>.
Поскольку функция  <tex>\varphi</tex> монотонна и непрерывна на отрезке <tex>[0, r],\,</tex>существует точка <tex>p \in [0, r]</tex>, такая, что <tex>\varphi(p) = q</tex>. Поэтому для любой частичной суммы <tex>\psi_n(s) = psi_0 + psi_1 \cdot s + \ldots + psi_n \cdot s^n</tex> ряда <tex> \psi(s) </tex>
+
Поскольку функция  <tex>\varphi</tex> монотонна и непрерывна на отрезке <tex>[0, r],\,</tex>существует точка <tex>p \in [0, r]</tex>, такая, что <tex>\varphi(p) = q</tex>. Поэтому для любой частичной суммы <tex> \psi_n(s) = \psi_0 + \psi_1 \cdot s + \ldots + \psi_n \cdot s^n</tex> ряда <tex> \psi(s) </tex>
 +
<tex> \left\vert \psi_n(s) \right\vert \leqslant \psi_n(q) = \psi_n(\varphi(p)) \leqslant \varphi(p),</tex>
 +
где последнее неравенство следует из предыдущего замечания.
 +
Первое утверждение теоремы доказано.
 +
 
 +
 
 +
<tex>2. \ </tex>Перепишем теперь утверждение Лагранжа <tex> \varphi(s) = s \cdot \psi \cdot (\varphi(s)) </tex> в виде <tex> \psi(\lambda) = \dfrac {\lambda} {\varphi^{-1}(\lambda)}. </tex>
 +
Функции <tex>\psi(\lambda) </tex> и <tex> \varphi^{-1}(\lambda)</tex> определены и
 +
[https://ru.wikipedia.org/wiki/%D0%93%D0%BE%D0%BB%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 голоморфны]
 +
внутри круга радиуса <tex>\rho </tex>. Теорема будет доказана, если мы покажем, что функцию <tex>\varphi^{-1}(\lambda)</tex> нельзя продолжить голоморфно ни в какую окрестность точки <tex>\rho</tex>.
 +
Предположим, что такое продолжение существует. Тогда
 +
 +
<tex> ({\varphi^{-1}}')(\rho) = \lim_{n \to \rho - 0}({\varphi^{-1}} ')(\lambda) = \dfrac {1} {\lim_{t \to r - 0} {\varphi} ' (t)}. </tex>
  
 +
Последний предел существует и, по условию теоремы, положителен.
 +
Поэтому функция <tex>\varphi^{-1}</tex>обратима в окрестности точки <tex>\rho,</tex> что, в свою очередь, противоречит условиям теоремы.
 
}}
 
}}
 +
Отметим, что производящий ряд для [[Числа Каталана|чисел Каталана]] <tex>Cat(s)</tex>сходится при <tex>s = r = \dfrac{1}{4},</tex> так как числа Каталана имеют асимптотику <tex>4^n \cdot n^{-3/2},</tex> а ряд <tex>\sum_{} n^{-3/2}</tex> сходится. С другой стороны, коэффиценты производной имеют асимптотику <tex>4^n \cdot n^{-1/2},</tex> и поэтому ряд  <tex>Cat ' (\dfrac{1}{4})</tex> расходится. В результате теорема в полном объеме к функции Каталана неприменима, а второе утверждение оказывается неверным.
 +
 +
== См. также ==
 +
 +
* [[Производящая функция]]
 +
* [[Уравнение Лагранжа и теорема Лагранжа]]
 +
* [[Числа Каталана]]
 +
 +
== Источники информации ==
 +
* [https://www.mccme.ru/free-books/lando/lando-genfunc.pdf Ландо С.А., Лекции о производящих функциях, 2007 год]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящая функция]]

Текущая версия на 19:19, 4 сентября 2022

Пусть две производящие функции [math]\varphi = \varphi(s)[/math] и [math]\psi = \psi(t)\,[/math] связаны между собой уравнением Лагранжа [math]\varphi(s) = s \cdot \psi \cdot (\varphi(s))[/math]. Мы хотим выяснить, как связаны между собой их радиусы сходимости.

Теорема:
Пусть две производящие функции [math]\varphi = \varphi(s)[/math] и [math]\psi = \psi(t),\, \psi(0) = 1\,[/math] с неотрицательными коэффицентами связаны между собой уравнением Лагранжа [math]\varphi(s) = s \cdot \psi \cdot (\varphi(s))[/math]. Пусть [math]r \gt 0\,[/math] радиус сходимости ряда [math]\varphi,[/math] причем числовой ряд [math]\varphi(r)[/math] сходится. Пусть радиус сходимости ряда [math]\psi[/math] равен [math]\rho[/math]. Тогда

[math]1. \ \rho \geqslant \varphi(r),[/math]

[math]2. \ \rho = \varphi(r),[/math] если числовой ряд [math]\varphi '(r)[/math] также сходится.

Замечание

Требование неотрицательности коэффициентов рядов естественно, если мы рассматриваем производящие функции для языков. В этом случае естественно также ожидать, что радиус сходимости производящего ряда для числа неприводимых слов больше радиуса сходимости производящего ряда для числа всех слов в языке (последняя последовательность растет быстрее последовательности чисел неприводимых слов).
Доказательство:
[math]\triangleright[/math]

[math]1. \ [/math]Докажем, что ряд [math]\psi(s)[/math] сходится абсолютно в любой точке [math]s,\,\left\vert s \right\vert = q \lt \rho[/math]. Поскольку функция [math]\varphi[/math] монотонна и непрерывна на отрезке [math][0, r],\,[/math]существует точка [math]p \in [0, r][/math], такая, что [math]\varphi(p) = q[/math]. Поэтому для любой частичной суммы [math] \psi_n(s) = \psi_0 + \psi_1 \cdot s + \ldots + \psi_n \cdot s^n[/math] ряда [math] \psi(s) [/math] [math] \left\vert \psi_n(s) \right\vert \leqslant \psi_n(q) = \psi_n(\varphi(p)) \leqslant \varphi(p),[/math] где последнее неравенство следует из предыдущего замечания. Первое утверждение теоремы доказано.


[math]2. \ [/math]Перепишем теперь утверждение Лагранжа [math] \varphi(s) = s \cdot \psi \cdot (\varphi(s)) [/math] в виде [math] \psi(\lambda) = \dfrac {\lambda} {\varphi^{-1}(\lambda)}. [/math] Функции [math]\psi(\lambda) [/math] и [math] \varphi^{-1}(\lambda)[/math] определены и голоморфны внутри круга радиуса [math]\rho [/math]. Теорема будет доказана, если мы покажем, что функцию [math]\varphi^{-1}(\lambda)[/math] нельзя продолжить голоморфно ни в какую окрестность точки [math]\rho[/math]. Предположим, что такое продолжение существует. Тогда

[math] ({\varphi^{-1}}')(\rho) = \lim_{n \to \rho - 0}({\varphi^{-1}} ')(\lambda) = \dfrac {1} {\lim_{t \to r - 0} {\varphi} ' (t)}. [/math]

Последний предел существует и, по условию теоремы, положителен.

Поэтому функция [math]\varphi^{-1}[/math]обратима в окрестности точки [math]\rho,[/math] что, в свою очередь, противоречит условиям теоремы.
[math]\triangleleft[/math]

Отметим, что производящий ряд для чисел Каталана [math]Cat(s)[/math]сходится при [math]s = r = \dfrac{1}{4},[/math] так как числа Каталана имеют асимптотику [math]4^n \cdot n^{-3/2},[/math] а ряд [math]\sum_{} n^{-3/2}[/math] сходится. С другой стороны, коэффиценты производной имеют асимптотику [math]4^n \cdot n^{-1/2},[/math] и поэтому ряд [math]Cat ' (\dfrac{1}{4})[/math] расходится. В результате теорема в полном объеме к функции Каталана неприменима, а второе утверждение оказывается неверным.

См. также

Источники информации