次可加性

维基百科,自由的百科全书
跳转至: 导航搜索

函数的次可加性[编辑]

函数的次可加性(subadditivity)是函数的一个性质,它粗略的声称计算函数对定义域中两个元素的和总是返回小于等于这个函数对每个元素的值的和的某个值。在数学的各个领域中有很多次可加函数的例子,特别是范数平方根加性函数是次可加函数的特殊情况。

定义[编辑]

一个函数f:A→B,其定义域A和陪域B上分别定义了某种加法+_A+_B,且陪域B上定义了偏序关系\leq”。若该函数满足:∀x,y∈A,有f(x+_Ay)\leq f(x)+_Bf(y)。则称f对于+_A+_B满足次可加性。在上下文对于+_A+_B都很明确的情况下,通常简称为 f 满足次可加性,亦称f为次可加函数

若上述函数f满足:∀有限集\{x_i|x_i \in A,i=1\cdots n\},有f \left( \sum_{k=1}^n x_i \right) \leq \sum_{k=1}^n f(x_i),则称f满足有限次可加性

若上述函数f满足:∀可列集\{x_i|x_i \in A,i=1\cdots \infty\},有f \left( \sum_{k=1}^\infty x_i \right) \leq \sum_{k=1}^\infty f(x_i),则称f满足可列次可加性

示例[编辑]

  • 范数
  • 集函数的次可加性:定义域为集类S,值域为[0, ∞]上的广义实值集函数f,若:
    • \forall A, B \in S,有f(A \cup B) \leq f(A) + f(B),则称f为次可加的。
    • \forall {A_i} \in S, i=1\cdots n,有f\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^{n} f(A_i),则称f为有限次可加的。
    • \forall {A_i} \in S, i=1\cdots \infty,有f\left(\bigcup_{i=1}^\infty A_i\right) \leq \sum_{i=1}^{\infty} f(A_i),则称f为可列次可加的。
  • 平方根函数,它有非负实数定义域和陪域,因为 \forall x, y \geq 0 我们有:
\sqrt{x+y}\leq \sqrt{x}+\sqrt{y}.

序列的次可加性[编辑]

定义[编辑]

序列 \left \{ a_n \right \}, n \geq 1 满足:\forall i,j \geq 1,有a_{i+j}\leq a_i+a_j。 则称该序列为次可加的,或称该序列满足次可加性,或称该序列是次可加序列

Michael Fekete引理[编辑]

对于次可加序列,有Michael Fekete的重要引理。[1]

引理(Michael Fekete):对任一次可加序列 {\left \{ a_n \right \}}_{n=1}^\infty,有\lim_{n \to \infty} \frac{a_n}{n} = \inf \frac{a_n}{n} 。(注意该极限可能是-∞。)

Fekete 引理的对应者对于次可加函数也成立: a_{n+m}\geq a_n + a_m. (极限可以是正无穷: 考虑序列 a_n = \log n!。)

有不要求不等式 (1) 对于所有 mn 成立的 Fekete 引理的扩展。还有结果允许你推导收敛到其存在性规定于 Fekete 引理中的极限的速率,如果存在着某种超加性和次可加性。[2]

参见[编辑]

引用[编辑]

  1. ^ Fekete, M. "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten." Mathematische Zeitschrift 17 (1923), pp. 228–249.
  2. ^ Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). ISBN 0-89871-380-3.

外部链接[编辑]

本條目含有来自PlanetMathsubadditivity》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议