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