Function (ℝⁿ ⇨ ℝ)

Numeric Array

陣列相信大家耳熟能詳。各個整數位置,各有一個數值。

Numeric Function

Plot3D[(x-3)*(x-3)*(x-3)*(y-1)*(y-1)*2*x*y, {x, -0.1, 4.4}, {y, -0.2, 1.5}, PlotRange -> {-3, 3}, Boxed -> False, Axes -> False, ColorFunction -> "SolarColors"]

函數的概念,請見本站文件「Function」。此處僅專注於有著數值、有得計算的函數。函數可以想成是陣列的連續版本。

Function可以畫成圖形

窮舉各種輸入,分別計算輸出,把輸入與輸出化作座標位置。

一元函數和二元函數容易作圖,三元函數就只能用空氣濃度來呈現函數值了,四元以上只能用幻想的。

Plot3D[Sin[x * y] * Cos[x + y], {x, -Pi, Pi}, {y, -Pi, Pi}, PlotRange -> {-2, 2}, Boxed -> False, Axes -> False, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &) ]

Function運算

函數就和實數、複數一樣,有著各種運算。以下將介紹函數的運算:求值、代入、加、減、乘、除、模、複合、微、積。

       operation (noun)      operation (verb)    result (noun)
-----  --------------------  ------------------  --------------
let =  evaluation      求值  evaluate      求值  value       值
let =  substitution    代入  substitute    代入  expression  式
+      addition        加法  add           加    sum         和
-      subtraction     減法  subtract      減    difference  差
       multiplication  乘法  multiply      乘    product     積
/      division        除法  divide        除    quotient    商
mod    modulo          模    ---           模    remainder   餘
∘      composition     複合  compose       複合  composite function 複合函數
d/dx   differentiation 微分  differentiate 微    derivative  導
∫ dx   integration     積分  integrate     積    integral    積分

求值

給定輸入數值,計算輸出數值。屬於數值計算。

代入

輸入變數替換為其他變數。屬於符號計算。

                          x = s + 2
          sin x   cos y   y = t / 2            sin(s + 2)   cos(t / 2)
f(x, y) = ————— + —————  ==========> f(s, t) = —————————— + ——————————
            y       x                             t / 2        s + 2  

加減乘除模

如果經常要把兩個函數的輸出加在一起,可以預先把兩個函數加在一起,得到新函數,節省計算時間!

兩個函數
f(x) = x² + x + 1
g(x) = -x + 2

輸入數值是1的時候,計算所有函數輸出數值的總和
f(1)        = 1² + 1 + 1 = 3
g(1)        = -1 + 2     = 1
f(1) + g(1) = 3 + 1      = 4

輸入數值是2的時候,計算所有函數輸出數值的總和
f(2)        = 2² + 2 + 1 = 7
g(2)        = -2 + 2     = 0
f(2) + g(2) = 7 + 0      = 7
如果預先讓函數相加的話
(f + g)(x) = f(x) + g(x)
           = (x² + x + 1) + (-x + 2)
           = x² + 3

那麼就可以節省計算時間
(f + g)(1)  = 1² + 3     = 4
(f + g)(2)  = 2² + 3     = 7

輸入越多種、函數越多個,節省越多時間!

用抽象的、簡潔的數學符號表達函數加法:

f + g

用直觀的、華麗的函數圖形表達函數加法:

加減乘除模概念相仿,其餘運算就不多提了。

複合

如果輸入經常接連地用函數變換兩次,可以預先把兩個函數複合在一起,得到新函數,節省計算時間!

兩個函數
f(x) = x² + x + 1
g(x) = -x + 2

輸入數值是1的時候,計算先通過g函數、再通過f函數的輸出數值
g(1)           = -1 + 2     = 1
f(g(1)) = f(1) = 1² + 1 + 1 = 3

輸入數值是2的時候,計算先通過g函數、再通過f函數的輸出數值
g(2)           = -2 + 2     = 0
f(g(2)) = f(0) = 0² + 0 + 1 = 1
如果預先讓函數複合的話
(f ∘ g)(x) = f(g(x))
           = (-x + 2)² + (-x + 2) + 1 
           = x² - 5x + 7

那麼就可以節省計算時間
(f ∘ g)(1)  = 1² - 5 + 7   = 3
(f ∘ g)(2)  = 2² - 10 + 7  = 1

輸入越多種、函數越多個,節省越多時間!

用抽象的、簡潔的數學符號表達函數複合:

f ∘ g

用直觀的、華麗的函數圖形表達函數複合?我不會畫。

微分

相鄰數字差,通通除以dx,得到新函數。

請讀者參考本站文件「Sequence」提及的離散版本。此處介紹的是連續版本,只多了個dx:一個無限微小、略大於零的數值。

用抽象的、簡潔的數學符號表達函數微分:

 d
—— f   輸入變數剛好一個
dx

 ∂
—— f   輸入變數大於一個
∂x

用直觀的、華麗的函數圖形表達函數微分:

當輸入變數只有一個,導數是座標(x,f(x))的「斜率slope」。當輸入變數有許多個,各個輸入變數分別求得斜率,合稱「梯度gradient」。

積分

從負無限大開始的連續數字和,通通乘以dx,得到新函數。

用抽象的、簡潔的數學符號表達函數積分:

∫ f dx

用直觀的、華麗的函數圖形表達函數積分:

當輸入變數只有一個,積分是左至-∞、右至x、下至0、上至f(x),四個邊界所包圍的「面積area」,面積可正可負。當輸入變數有許多個,各個輸入變數一齊累計,得到「容積volume」。

函數積分最簡單的演算法是Rectangle Rule:按照定義來,將面積切割成數條寬度為dx的矩形。

然而,左至負無限大,演算法永不結束,怎麼辦?解決方式是增設左邊界,想訂多少就多少。數學家把「自訂左右邊界的積分運算」的結果叫做「定積分definite integral」。

對計算學家來說,定積分就是區間和啦。前綴和改成區間和,就這樣而已。

矩形畢竟不是無限薄。當函數是斜線,仍有縫隙。只好改用Trapezoidal Rule:將面積切割成數條寬度為dx的梯形。

當函數是曲線,仍有縫隙。只好改用Parabolic Rule又稱Simpson's Rule:梯形的斜邊改成拋物線。

長方形的邊是零次、梯形的斜邊是一次、拋物線是二次。當函數是三次曲線,仍有縫隙。無論如何修正,只要函數是更高次曲線就仍有縫隙,況且運算量也更大了。只好改用Adaptive Simpson's Rule:dx最初是b-a;當縫隙太大,就讓dx變成一半。

有些區間已經幾乎沒有縫隙,大可不必再切半。

函數起起伏伏,難以估量縫隙大小。只好比較前後算得的面積,當面積差異足夠小,就推定面積已經足夠準確、足夠穩定了。

除了即時調整dx,亦得事前確立dx。Gauss Quadrature:當函數內急外緩,則讓dx內密外疏。使用特殊函數自訂dx。

最後介紹MCMC Integration:使用「Rejection Sampling」,以函數曲線下方的取樣次數比例,推定面積。取樣時,自訂x的分布,可達到自訂dx的效果。

UVa 1356 1280 12528 ICPC 3001

容易計算的函數類型

Linear Function:線性函數。變數的加法、減法、倍率所組成。特色是可以改寫成矩陣形式。請參考本站文件「Matrix」。

例如f(x) = 2x、f(x,y) = 2x + y。

又例如f(x, y) = 2(x - y) + 3(x + 2y)。

Affine Function:仿射函數。變數暨常數的加法、減法、倍率所組成。可以想成是線性函數又平移,不必穿過原點。

例如f(x) = 2x + 1、f(x,y) = 2x + y - 3。

又例如f(x, y) = 5((x - 1) - (3x + 2y) + 5⋅3) - 2。

Polynomial Function:多項式函數。變數暨常數的加法、減法、乘法所組成。請參考本站文件「Polynomial」。

例如f(x) = 3x + 2x + 1、f(x,y) = 3x² + 2y² + xy + y - 3。

又例如f(x, y) = y((x - 1) ⋅ (3x + 2y) + 5⋅3) - 2。

多項式函數的導數、積分,仍是多項式函數!dx竟然可以變不見!有興趣的讀者可以觀落陰請教牛頓或萊布尼茲。

多項式函數的導數、積分,可以預計算!數學家發明了大量的計算手法,得以在紙上推導微積分的結果,得到公式,不必使用前面章節的演算法。有興趣的讀者可以參考微積分、工程數學教科書。

多項式函數,雖然內容繁雜,但是性質優雅,所以用途廣泛。物理、化學、工程、經濟、……,各種領域都在使用多項式函數。

Contour(Under Construction!)

Contour(Level Set)

http://paulbourke.net/papers/conrec/

連續可微函數的等高線,可以是一條封閉曲線、一條開放曲線、多條上述曲線。

甚至曲線各處粗細不一。

f(x,y)是一群等高線。f(x,y) = 0是一個等高線。f(x,y) ≥ 0是一群等高線,形成區域,區分內部外部。

等高線,無限微小、無限綿密、無限多,填滿整個空間。

一、函數:等高線彼此不相交。

二、連續:等高線沒有端點。等高線升高降低,宛如膨脹消泄。

三、可微:等高線沒有尖角。等高線每一點只有唯一一條切線。

極值位於兩個等高線的交集。注意到極值可能不只一個。

一、函數:兩個等高線,若等高、又最高,則交集是極值。

二、連續:兩個等高線,只會內接或外接,不會交叉。

三、可微:兩個等高線,交會之處,每一點只有唯一一條切線。

切線的垂直方向,就是梯度方向。

Mathematical Morphology

Mathematical Morphology

Histogram3D[{{0,0},{0,0},{0,0}},{1},Boxed->False,Axes->None]

【註:我製圖技術差,只好介紹陣列版本,而非函數版本。】

調整函數形狀的學問。因為不是顯學,所以名稱矯揉造作,不像一般的數學名詞那樣地簡潔有力。關鍵字grayscale morphology。

基本操作是dilation和erosion,進階操作由基本操作組成。

            dilation:鄰近格子取最大值。功效是補厚。
             erosion:鄰近格子取最小值。功效是削薄。
             closing:先 dilation 再 erosion。
             opening:先 erosion 再 dilation。
   top-hat transform:原函數減掉 opening。
bottom-hat transform:closing 減掉原函數。

鄰近格子可以自訂樣式。另外,大樣式多半可以改為小樣式,效果相同而且時間複雜度更低。

例如5×5,改為兩波3×3,亦得取得5×5範圍內的最小值(最大值)。本來讀取X×Y×5×5格,變成只讀取X×Y×3×3×2格。

運算不可逆、不可抵銷,沒有反運算。個人推測這些運算可以減少亂度。

額外使用過濾函數

進階版本。額外設計一個過濾函數。設計不同的過濾函數,得到不同的效果。

窮舉原函數的每個位置;針對一個位置,令過濾函數的中心對準該位置,各個位置點對點相加(相減)後,才取最大值(最小值)。

邏輯運算的版本

不知道為什麼,影像處理教科書非常喜歡討論邏輯運算的版本。數值改成false和true,最大值(最小值)改成OR(AND),功效是增厚(削薄)圖形的外緣。

UVa 12702