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

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

       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變成一半。

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

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

UVa 1356 1280 12528 ICPC 3001

Polynomial Function

Polynomial

由未知數(變數)與已知數(常數)的加法、減法、乘法所組成的式子,就叫做「多項式」。以變數次方為主角,多項式可以拆成許多「項」。

多項式的資料結構,要嘛開個array,每一格存一種次方的係數;要嘛開個list,把係數為零的項統統去掉然後串成一串。

多項式的運算,主要有加、減、乘、除、模、微、積、分解、代入。中學到大學接觸了六年,應當難不倒各位讀者,就不贅述了。

UVa 392 126 10719 10586 10951 463 930 10428 498 10268 10105

Polynomial Function

「多項式函數」。離散與連續的橋樑。離散的係數值,變成連續的函數值。數學家正在探索其奧秘。

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

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

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

Horner's Rule

f(x) = 3x³ + 2x + 1 = ((((3 ⋅ x) + 0) ⋅ x) + 2) ⋅ x) + 1
f(5) = 3x³ + 2x + 1 = ((((3 ⋅ 5) + 0) ⋅ 5) + 2) ⋅ 5) + 1

這是一個演算法。一元多項式函數,代入數值。一乘一加,不斷更迭,求得函數值。完全不需要次方運算。

Taylor Series

              f'(a)          f"(a)             
f(x) = f(a) + ――――― (x-a)¹ + ――――― (x-a)² + ...
                1!             2!              

這是一道數學公式。將平滑函數變成多項式函數。

換句話說,以無限項的多項式函數,趨近平滑函數。

y  = f(x)
                                     h¹         h²      
y₊ = f(x₊) = f(x + h) = f(x) + f'(x) ―― + f"(x) ―― + ...
                                     1!         2!      

這是另一種形式。當x略微增減,得知y如何增減。

當h介於±1之間,則次方越大、數值越小。後面的項,數值越來越小,越來越細膩,越來越不重要。只取前幾項,即是取近似值!多取幾項,即是逼近真實值!數值精確度,以項數多寡來決定。

UVa 12413

e

「歐拉數Euler Number」。實際數值差不多是2.72。

計算eˣ的演算法:Taylor Series與Horner's Rule。

π

「圓周率」。圓周長除以直徑,實際數值差不多是3.14。

http://en.wikipedia.org/wiki/Category:Pi_algorithms

延伸閱讀:π is wrong!

http://www.math.utah.edu/~palais/pi.html

有兩派人馬,一派支持角度,一派支持面積。

角度派認為π是180°,是圓周角360°的一半,要乘以二才能補成360°,極不方便。這派人馬認為應該替360°特別訂立一個代號。

面積派認為π剛好就是單位圓面積,明明很方便,不需要改。

延伸閱讀:math.h

https://zhuanlan.zhihu.com/p/20085048

Contour

Contour(Level Set)

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

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