函數的次可加性 (subadditivity)是函數的一個性質,它粗略的聲稱計算函數對定義域 中兩個元素的和總是返回小於等於這個函數對每個元素的值的和的某個值。在數學的各個領域中有很多次可加函數的例子,特別是範數 和平方根 。加性函數 是次可加函數的特殊情況。
一個函數 f:A→B,其定義域A和陪域B上分別定義了某種加法
+
A
{\displaystyle +_{A}}
和
+
B
{\displaystyle +_{B}}
,且陪域B上定義了偏序關係 「
≤
{\displaystyle \leq }
」。若該函數滿足:∀x,y∈A,有
f
(
x
+
A
y
)
≤
f
(
x
)
+
B
f
(
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滿足:∀有限集
{
x
i
|
x
i
∈
A
,
i
=
1
⋯
n
}
{\displaystyle \{x_{i}|x_{i}\in A,i=1\cdots n\}}
,有
f
(
∑
k
=
1
n
x
i
)
≤
∑
k
=
1
n
f
(
x
i
)
{\displaystyle f\left(\sum _{k=1}^{n}x_{i}\right)\leq \sum _{k=1}^{n}f(x_{i})}
,則稱f滿足有限次可加性 。
若上述函數f滿足:∀可列集
{
x
i
|
x
i
∈
A
,
i
=
1
⋯
∞
}
{\displaystyle \{x_{i}|x_{i}\in A,i=1\cdots \infty \}}
,有
f
(
∑
k
=
1
∞
x
i
)
≤
∑
k
=
1
∞
f
(
x
i
)
{\displaystyle f\left(\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,B\in S}
,有
f
(
A
∪
B
)
≤
f
(
A
)
+
f
(
B
)
{\displaystyle f(A\cup B)\leq f(A)+f(B)}
,則稱f為次可加的。
∀
A
i
∈
S
,
i
=
1
⋯
n
{\displaystyle \forall {A_{i}}\in S,i=1\cdots n}
,有
f
(
⋃
i
=
1
n
A
i
)
≤
∑
i
=
1
n
f
(
A
i
)
{\displaystyle f\left(\bigcup _{i=1}^{n}A_{i}\right)\leq \sum _{i=1}^{n}f(A_{i})}
,則稱f為有限次可加的。
∀
A
i
∈
S
,
i
=
1
⋯
∞
{\displaystyle \forall {A_{i}}\in S,i=1\cdots \infty }
,有
f
(
⋃
i
=
1
∞
A
i
)
≤
∑
i
=
1
∞
f
(
A
i
)
{\displaystyle f\left(\bigcup _{i=1}^{\infty }A_{i}\right)\leq \sum _{i=1}^{\infty }f(A_{i})}
,則稱f為可列次可加的。
平方根 函數,它有非負 實數 定義域和陪域,因為
∀
x
,
y
≥
0
{\displaystyle \forall x,y\geq 0}
我們有:
x
+
y
≤
x
+
y
.
{\displaystyle {\sqrt {x+y}}\leq {\sqrt {x}}+{\sqrt {y}}.}
若序列
{
a
n
}
,
n
≥
1
{\displaystyle \left\{a_{n}\right\},n\geq 1}
滿足:
∀
i
,
j
≥
1
{\displaystyle \forall i,j\geq 1}
,有
a
i
+
j
≤
a
i
+
a
j
{\displaystyle a_{i+j}\leq a_{i}+a_{j}}
。
則稱該序列為次可加的 ,或稱該序列滿足次可加性 ,或稱該序列是次可加序列 。
對於次可加序列,有Michael Fekete 的重要引理。[ 1]
引理 (Michael Fekete):對任一次可加序列
{
a
n
}
n
=
1
∞
{\displaystyle {\left\{a_{n}\right\}}_{n=1}^{\infty }}
,有
lim
n
→
∞
a
n
n
=
inf
a
n
n
{\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=\inf {\frac {a_{n}}{n}}}
。(注意該極限可能是-∞。)
Fekete 引理的對應者對於次可加函數也成立:
a
n
+
m
≥
a
n
+
a
m
.
{\displaystyle a_{n+m}\geq a_{n}+a_{m}.}
(極限可以是正無窮: 考慮序列
a
n
=
log
n
!
{\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 .
本條目含有來自PlanetMath 《Subadditivity 》的內容,版權遵守知識共享協議:署名-相同方式共享 協議 。