次可加性
目录
1 函数的次可加性
1.1 定义
1.2 示例
2 序列的次可加性
2.1 定义
2.2 Michael Fekete引理
3 参见
4 引用
5 外部链接
函数的次可加性
函数的次可加性(subadditivity)是函数的一个性质,它粗略的声称计算函数对定义域中两个元素的和总是返回小于等于这个函数对每个元素的值的和的某个值。在数学的各个领域中有很多次可加函数的例子,特别是范数和平方根。加性函数是次可加函数的特殊情况。
定义
一个函数f:A→B,其定义域A和陪域B上分别定义了某种加法+A{displaystyle +_{A}}和+B{displaystyle +_{B}},且陪域B上定义了偏序关系“≤{displaystyle leq }”。若该函数满足:∀x,y∈A,有f(x+Ay)≤f(x)+Bf(y){displaystyle f(x+_{A}y)leq f(x)+_{B}f(y)}。则称f对于+A{displaystyle +_{A}}和+B{displaystyle +_{B}}满足次可加性。在上下文对于+A{displaystyle +_{A}}和+B{displaystyle +_{B}}都很明确的情况下,通常简称为 f 满足次可加性,亦称f为次可加函数。
若上述函数f满足:∀有限集{xi|xi∈A,i=1⋯n}{displaystyle {x_{i}|x_{i}in A,i=1cdots n}},有f(∑k=1nxi)≤∑k=1nf(xi){displaystyle fleft(sum _{k=1}^{n}x_{i}right)leq sum _{k=1}^{n}f(x_{i})},则称f满足有限次可加性。
若上述函数f满足:∀可列集{xi|xi∈A,i=1⋯∞}{displaystyle {x_{i}|x_{i}in A,i=1cdots infty }},有f(∑k=1∞xi)≤∑k=1∞f(xi){displaystyle fleft(sum _{k=1}^{infty }x_{i}right)leq sum _{k=1}^{infty }f(x_{i})},则称f满足可列次可加性。
示例
- 单位函数 f(x)=x{displaystyle f(x)=x} 显然是(全)可加的,这是一个平凡的例子。另一个平凡的例子是零函数 f(x)=0{displaystyle f(x)=0}。
- 范数
集函数的次可加性:定义域为集类S,值域为[0, ∞]上的广义实值集函数f,若:
∀A,B∈S{displaystyle forall A,Bin S},有f(A∪B)≤f(A)+f(B){displaystyle f(Acup B)leq f(A)+f(B)},则称f为次可加的。
∀Ai∈S,i=1⋯n{displaystyle forall {A_{i}}in S,i=1cdots n},有f(⋃i=1nAi)≤∑i=1nf(Ai){displaystyle fleft(bigcup _{i=1}^{n}A_{i}right)leq sum _{i=1}^{n}f(A_{i})},则称f为有限次可加的。
∀Ai∈S,i=1⋯∞{displaystyle forall {A_{i}}in S,i=1cdots infty },有f(⋃i=1∞Ai)≤∑i=1∞f(Ai){displaystyle fleft(bigcup _{i=1}^{infty }A_{i}right)leq sum _{i=1}^{infty }f(A_{i})},则称f为可列次可加的。
平方根函数,它有非负实数定义域和陪域,因为 ∀x,y≥0{displaystyle forall x,ygeq 0} 我们有:
- x+y≤x+y.{displaystyle {sqrt {x+y}}leq {sqrt {x}}+{sqrt {y}}.}
序列的次可加性
定义
若序列 {an},n≥1{displaystyle left{a_{n}right},ngeq 1} 满足:∀i,j≥1{displaystyle forall i,jgeq 1},有ai+j≤ai+aj{displaystyle a_{i+j}leq a_{i}+a_{j}}。
则称该序列为次可加的,或称该序列满足次可加性,或称该序列是次可加序列。
Michael Fekete引理
对于次可加序列,有Michael Fekete的重要引理。[1]
引理(Michael Fekete):对任一次可加序列 {an}n=1∞{displaystyle {left{a_{n}right}}_{n=1}^{infty }},有limn→∞ann=infann{displaystyle lim _{nto infty }{frac {a_{n}}{n}}=inf {frac {a_{n}}{n}}} 。(注意该极限可能是-∞。)
Fekete 引理的对应者对于次可加函数也成立:
an+m≥an+am.{displaystyle a_{n+m}geq a_{n}+a_{m}.} (极限可以是正无穷: 考虑序列 an=logn!{displaystyle a_{n}=log n!}。)
有不要求不等式 (1) 对于所有 m{displaystyle m} 和 n{displaystyle n} 成立的 Fekete 引理的扩展。还有结果允许你推导收敛到其存在性规定于 Fekete 引理中的极限的速率,如果存在着某种超加性和次可加性。[2]
参见
- 三角不等式
- 可加性
引用
^ Fekete, M. "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten." Mathematische Zeitschrift 17 (1923), pp. 228–249.
^ Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). ISBN 0-89871-380-3.
György Pólya and Gábor Szegö. "Problems and theorems in analysis, volume 1". Springer-Verlag, New York (1976). ISBN 0-387-05672-6.
外部链接
本條目含有来自PlanetMath《subadditivity》的內容,版权遵守知识共享协议:署名-相同方式共享协议。