Sequence(Under Construction!)
Sequence
Continuouity: Generating Function / Series Infinity: Convergence / Boundary Operation: Calculus / Product / Recurrence (Iteration) / Continuous Fraction
Continuouity
離散數列與連續函數彼此轉換。結果稱之為「生成函數」。
(2 -5 1 0 4) ←→ 2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴ a(x) p(x)
得以援引函數運算:加減乘除、微分、積分。
得以援引分析方法:求值、求解、求根、求極值、內插、迴歸。
數論與分析兩大領域打通了!
Infinity
設計奇葩的多項式,製造奇葩的數列。
分數多項式、長除法,可以製造無限長數列。
1/(1-x) = x⁰ + x¹ + x² + x³ + ... ←→ (1 1 1 1 ...)
https://en.wikipedia.org/wiki/Formal_power_series
連乘化倒數 P = (1+x)(1+x^2)(1+x^3)... Q = (1-x)(1-x^2)(1-x^3)... PQ = (1-x^2)(1-x^4)(1-x^6)... 只有偶數 1/Q = P/PQ = (1-x)(1-x^3)(1-x^5).... 只有奇數 Q = 1/(1-x)(1-x^3)(1-x^5)...
Convergence
the radius of convergence https://en.wikipedia.org/wiki/Cauchy–Hadamard_theorem
https://en.wikipedia.org/wiki/Arithmetic_progression https://en.wikipedia.org/wiki/Geometric_series https://en.wikipedia.org/wiki/Cauchy_sequence
1/e^(x^2) sqrt(π) 1/x ln(x) 發散 1/(x^2) pi^2 / 6 (離散版本) 1/x! e (離散版本)
Operation
微積分,可以製造什麼東西呢?
1/(1-x)² = 0x⁰ + 1x¹ + 2x² + 3x³ + ... ←→ (0 1 2 3 ...)
數列前綴和、差分。函數微分、積分。
https://en.wikipedia.org/wiki/Euler–Maclaurin_formula
https://en.wikipedia.org/wiki/Lagrange's_identity https://en.wikipedia.org/wiki/Cauchy_product https://en.wikipedia.org/wiki/Euler_product
Recurrence
https://en.wikipedia.org/wiki/Fibonacci_number https://en.wikipedia.org/wiki/Recamán's_sequence https://en.wikipedia.org/wiki/Holonomic_function
Taylor Series(Under Construction!)
Power Series(aₙ ⟷ aₙxⁿ)
(2 -5 1 0 4) ⟷ 2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴ (a₀ a₁ a₂ a₃ a₄) ⟷ a₀x⁰ + a₁x¹ + a₂x² + a₃x³ + a₄x⁴
Power Series正向延伸。Laurent Series雙向延伸。Christol's Theorem推廣成有限體。
演算法是數論轉換、傅立葉轉換。
p-Adic Number
https://books.google.com.tw/books?id=ZOfUsvemJDMC&pg=PA241
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.2931&rep=rep1&type=pdf
多項式:以(x-a)當作底數,快速得知f(a)的數值。泰勒展開式。
多項式分式:同上,為了避免除以零,所以移項,(x-a)f(a)。
整數:以任意整數當作底數,可以知道整除效果。
分數:同上,分子與分母互質,分子減去多少可以整除。
https://en.wikipedia.org/wiki/Arithmetic_dynamics
Taylor Series
這是一道數學公式。將平滑函數變成多項式函數。
換句話說,以無限項的多項式函數,趨近平滑函數。
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
Taylor Series
一個多項式函數表示成(x-a)的Power Series。
以傅立葉轉換來做比喻,xⁿ有如波,係數有如頻譜。
公式源自泰勒展開式。當取樣間距Δx小於1、接近0,後續項次迅速縮小,微不足道,無關緊要,於是捨去後續項次。
Taylor expansion f(x+Δx) = f(x) / 0! + f′(x) Δx / 1! + f″(x) Δx² / 2! + ... f(x-Δx) = f(x) / 0! - f′(x) Δx / 1! + f″(x) Δx² / 2! - ... 1st-order central derivative f(x+Δx) - f(x-Δx) = 2 f′(x) Δx + ... ≈ 2 f′(x) Δx f′(x) ≈ [f(x+Δx) - f(x-Δx)] / 2Δx 2nd-order central derivative f(x+Δx) + f(x-Δx) = 2 f(x) + f″(x) Δx² + ... ≈ 2 f(x) + f″(x) Δx² f″(x) ≈ [f(x+Δx) + f(x-Δx) - 2 f(x)] / Δx² 1st-order central integral f′(x) ≈ [f(x+Δx) - f(x-Δx)] / 2Δx f(x) ≈ [∫f(x+Δx) - ∫f(x-Δx)] / 2Δx f(x-Δx) ≈ [∫f(x) - ∫f(x-2Δx)] / 2Δx ∫f(x) ≈ ∫f(x-2Δx) + f(x-Δx) ⋅ 2Δx ∫f(x) ≈ [... + f(x-3Δx) + f(x-Δx)] ⋅ 2Δx
1 1 2 f(x + Δx) = f(x) + ―― f'(x) Δx + —— f"(x) Δx + ... 1! 2! 1 1 f(x + Δx) = f(x) + —— F'(x)ᵀ Δx + —— Δxᵀ F"(x)ᵀ Δx + ... 1! 2! F'(x)ᵀ = J(x), F"(x)ᵀ = F"(x) = H(x) Δxⁿ projects onto basis, which is function gradient.
1. newton optimization: order-1 2. euler method: order-1
Condition number https://en.wikipedia.org/wiki/Condition_number
binomial coefficient / cauchy integral formula https://riteme.site/blog/2018-3-2/cut-the-stick.html
differential operator -> polynomial
https://w3.math.sinica.edu.tw/mathmedia/HTMLarticle18.jsp?mID=43208
Approximation
pade approximation https://math.stackexchange.com/questions/860293/ Parker–Sochacki method tylor solve ODE https://en.wikipedia.org/wiki/Parker%E2%80%93Sochacki_method
延伸閱讀:Linear Approximation(Linearizarion)
泰勒展開式可以詮釋牛頓法求極值。
二階泰勒展開,令前後兩步高低差距盡量大(盡量走往高處)。對步伐方向Δx微分,得到最佳移動方向。
2nd order Taylor expansion 1 F(x + Δx) - F(x) = Δxᵀ F'(x) + — Δxᵀ F"(x) Δx 2 d ——— [ F(x + Δx) - F(x) ] = F'(x) + F"(x) Δx = 0 dΔx -F"(x) Δx = F'(x) Δx = -F"(x)⁻¹ F'(x)
延伸閱讀:Quadratic Function特殊用途
二階泰勒展開式是二次函數,矩陣是Hessian Matrix。根據Hessian Matrix是否正定,可以初步推測該處是極小值、鞍點。
syms x y f = y*exp(x - 1) - x*log(y); taylor(f, [x, y], [1, 1], 'Order', 3)
g1 = Plot3D[y*Exp[x-1] - x*Log[y], {x, -3, 3}, {y, -3, 3}, PlotRange -> {-3, 3}, BoxRatios->{1,1,1}, ClippingStyle -> None, Mesh-> None, Axes->None, Boxed -> False, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-2, 2}]] &)]; g2 = Plot3D[x + ((x-1)^2)/2 + ((y-1)^2)/2, {x, -3, 3}, {y, -3, 3}, PlotRange -> {-3, 3}, BoxRatios->{1,1,1}, ClippingStyle -> None, Mesh-> None, Axes->None, Boxed -> False, ColorFunction -> "SolarColors"];
延伸閱讀:Quadratic Form特殊用途
二次型除以x長度平方,換句話說,向量經過線性變換再投影回去,即是「虛擬特徵值Rayleigh Quotient」。
二次型開根號(必須是半正定矩陣),換句話說,向量經過線性變換的長度,形成「歐氏長度函數Euclidean Length Function」。
延伸閱讀:約束最佳化
constraint http://www.gotoandplay.it/_articles/2005/08/advCharPhysics.php http://www.gotoandplay.it/_articles/2005/08/advCharPhysics_p02.php constraint, move toward dx, taylor expansion c(x) >= 0 c(x + dx) ~= c(x) + c'(x) dot dx >= 0
Fourier Series(Under Construction!)
Fourier Series
泰勒級數:多個螺旋線疊加。 傅立葉級數:多個圓形疊加。 不動函數:形狀不變。 特徵函數:簡諧運動?特徵值:圓形膨脹收縮。
Weierstrass function。處處連續處處不可微分。 Fabius function。處處平滑處處不可解析。 橫批:無窮遞迴。
Arithmetic Cosine Transform Arithmetic Fourier Transform
首項不除以 sqrt(2) idct(dct([0,1,2,3,4])) = [2,3,4,5,6] idct(dct([1,2,3,4,5])) = [4,5,6,7,8] idct(dct([2,3,4,5,6])) = [6,7,8,9,10]
fixed point of fourier transform: gauss, sqrt(1/|x|) sqrt(1/|x|) + sqrt(1/|x+5|) ---> flat at [0,5]
http://fourierart.com/ http://mathworld.wolfram.com/Epicycloid.html http://mathworld.wolfram.com/WattsCurve.html
波粒二象性是脈衝函數做Laplace Transform?
Fourier Transform
e的純虛數次方會不斷繞圈。採用單位根的次方e𝑖⋅2π/N。
複數 垂直座標 轉換機制 頻率座標 轉換名稱 時間複雜度 一一 一一一一一 一一一一一 一一一一一 一一一一一 一一一一一 數字 實部、虛部 長度、角度 幅長、幅角 極轉換 O(1) 函數 實部、虛部 複數波 強度、相位 傅立葉轉換 O(NlogN)
一個數值,得到極座標表示法 一個數列,得到傅立葉轉換 一個矩陣,得到特徵分解
e^x 輸入相加=輸出相乘 fourier transform 輸入點積=輸出卷積
傅立葉轉換也許可以視作座標系轉換。有些問題在垂直座標很難算,在頻率座標卻很好算。複數乘法變長度相乘、角度相加。數列卷積變數列乘法。
傅立葉轉換是積分變換,可以視作向量空間的座標系。
Eigenvalue與Fourier Transform
循環矩陣,特徵向量是傅立葉矩陣,特徵值是第一個橫條的傅立葉轉換。
http://math.stackexchange.com/questions/25126/
1. 兩個循環矩陣相乘 = 總是可以用fourier matrix作對角化 = 對角線矩陣相乘 (還是循環矩陣) (C = F D F⁻¹) (F⁻¹ = Fᵀ) (對應的eigenvalue相乘) 2. 兩串數列的循環卷積 = fft = 對應項相乘 3. 兩個多項式的循環乘法 = 多項式求值,以e^-itn取樣 = 對應的點座標相乘 4. 兩串函數值的循環乘法 = 這是甚麼東西? 5. 兩串分解式的循環乘法 = 這是甚麼東西? (2n個根融合成n個根)
tridiagonal and Toeplitz matrix's eigenvalues: a + 2 sqrt(bc) cos(k pi / (n+1)) for k = 1~n
eigenvectors of fourier matrix is gaussian function eigenvalues of fourier matrix is +1 -1 +i -i F^4 = I
傅立葉矩陣的特徵向量是高斯,特徵值是 {-1, +1, -i, +i} https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Eigenvalues_and_eigenvectors 循環矩陣的特徵向量是傅立葉,特徵值是傅立葉轉換結果 https://en.wikipedia.org/wiki/Circulant_matrix#Properties 共伴矩陣的特徵向量是 [1 x^1 x^2 ...] ,特徵值是遞迴方程式的根x。 det = 0 是原本的遞迴方程式。 https://en.wikipedia.org/wiki/Companion_matrix
Chirp Z-transform
fast inverse CZT algorithm Generalizing the inverse FFT off the unit circle https://www.news.iastate.edu/news/2019/10/10/signalprocessing
https://en.wikipedia.org/wiki/Rader's_FFT_algorithm
Harmonic Series(Under Construction!)
Dirichlet Series(aₙ ⟷ aₙnˣ)
(2 -5 1 0 4) ⟷ 2⋅0ˣ - 5⋅1ˣ + 1⋅2ˣ + 0⋅3ˣ + 4⋅4ˣ (a₀ a₁ a₂ a₃ a₄) ⟷ a₀0ˣ + a₁1ˣ + a₂2ˣ + a₃3ˣ + a₄4ˣ
狄利克雷級數與狄利克雷卷積(乘性卷積)仍有許多謎團,例如千禧年大獎難題的黎曼猜想,就是狄利克雷級數求根。
Lambert Series
原數列每一項除以(1+xⁱ)後z轉換,等於積分後z轉換。左式叫做Lambert series。
Lamber W Function
無限次方變成轉圈。
Harmonic Series
Riemann ζ Function
原數列ζ轉換、再乘上一個倍率ζ(s),等於積分後ζ轉換。
反元素:
ζ(s) = sum 1/(nˢ) 1/ζ(s) = sum u(n)/(nˢ)
Gamma Function
階乘推廣到複數。
https://en.wikipedia.org/wiki/Gamma_function
Grandi's Series(Under Construction!)
Grandi's Series
解析延拓Analytic Continuation
Cesàro summation assigns Grandi's divergent series
http://mathworld.wolfram.com/Zeta-RegularizedProduct.html https://www.quora.com/Why-is-the-regularized-product-of-all-prime-numbers-equal-to-4-pi-2