Skip to content

奇点分析

Singularity analysis · Singularity analysis of generating functions

在带缺口的复邻域内把主导奇点的局部幂对数展开逐项转移为生成函数系数渐近。

条目类型
方法

形式陈述

ρ>0主导奇点。一个以 ρ 为尖点的 Δ-域可写为

Δ(ρ,η,θ)={z:|z|<ρ+η, zρ, |arg(zρ)|>θ},

其中 η>00<θ<π/2。它在 ρ 向外的射线附近挖去一个楔形,使围道能够从收敛圆外侧逼近奇点而不穿过支割。若 A 能解析延拓到这样的区域,并在其中具有局部展开

A(z)=j=0mcj(1zρ)αj+Rm(z),

则奇点分析用Cauchy 系数积分把每个标准项转成系数项。对

α{0,1,2,},

基本尺度为

[zn](1zρ)αρnnα1Γ(α).

余项也必须满足相应的 Δ-域界,才能把误差传递到系数;只有沿实轴的局部等价通常不够。

直觉

方法的核心是把 Cauchy 圆变形成围住主导奇点的钥匙孔轮廓。远离奇点的轮廓段因模更大而指数较小,主要积分集中在离 ρ1/n 的邻域。缩放 z=ρ(1+t/n) 后,局部幂变成 Hankel 积分,而 1/Γ(α) 正是那条积分的常数。

Δ-域不是技术装饰。它提供从奇点两侧绕行的空间,并排除函数在紧贴主导点外侧藏有额外奇点。若只知道 zρ 时的实数渐近,复平面其他方向的剧烈行为仍可能改变系数。

例子与边界

Catalan 生成函数

C(z)=114z2z

ρ=1/4 附近令 X=14z,有

C(z)=21+X=22X1/2+2X+O(X3/2).

奇异项是 2(14z)1/2。由于

Γ(12)=2π,

转移得到

[zn]C(z)24nn3/2Γ(1/2)=4nπn3/2,

与 Catalan 数的 Stirling 渐近一致。常数、指数尺度和 n3/2 都从局部展开逐项得到。

展开中的 22X 都是 z 的一次多项式,对 n>1 不再贡献系数;真正控制尾部的是首个非整数幂 X1/2。若所谓“正则项”只在局部解析、却不能继续越过其他主导点,则仍须保留它的全局影响,不能仅凭外观看起来光滑就删去。

α 是非正整数,Γ(α) 有极点,而 (1z)α 是多项式并最终没有系数;不能把 1/Γ(α)=0 当成普遍主项而忽略可能存在的对数因子。形如 (1z)mlog(1/(1z)) 的项需要专门的对数转移公式。

若圆周上有多个主导奇点,应分别建立局部展开并把贡献相加;周期性会产生根单位振荡。若函数具有本性奇点、自然边界,或主要贡献来自随 n 移动的点,则应改用鞍点法、圆法或其他工具。

推论与应用

解析组合的转移定理把标准幂—对数尺度及其误差界整理成可重复使用的规则。结合符号方法,代数型树规格常产生平方根奇点和通用的 ρnn3/2 行为;对数奇点常对应循环,极点则常对应有限状态或有理结构。

完整工作流是:先定位全部主导点,再证明 Δ-解析延拓,求局部展开,最后逐项转移并控制余项。任一步缺失都可能得到正确外形却错误常数,或在周期剩余类上给出根本不成立的统一渐近。

参考资料
  • Philippe Flajolet and Andrew Odlyzko, “Singularity analysis of generating functions,” SIAM Journal on Discrete Mathematics 3(2), 1990, pp. 216–240。
  • Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapter VI。
  • Peter Henrici, Applied and Computational Complex Analysis, Vol. 2, Wiley, 1977, Chapter 11, coefficient asymptotics。
关系图谱7 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系