Iterated Function System(Under Construction!)

Iterated Function System

「遞推函數系統」。

函數求值無限多回合,本回合輸出作為下回合輸入。

實務上改為N回合。

Iterated Function System可以畫成圖形

不同初始數值,不同路線,不同結果。

輸入輸出是相同集合,可以重疊。

亦得採用垂直座標系。

數學性質:Periodicity

週期性」。數值重複出現。

輸入輸出是有限集合,最終必然循環。

輸入輸出是無限集合,最終可能循環、最終可能不循環。

循環長度稱作period。當循環長度是1,循環退化成定值。

循環稱作orbitperiodic points

定值稱作steady statefixed point

不循環,最終必然抵達無限遠處。

數學性質:Continuity

連續性」。起點附近的點也會抵達終點附近的點。

多個連續函數的複合也是連續函數。起點到終點是連續函數。起點附近的點也會抵達終點附近的點。起點們形成連續區域與連續邊界。終點們亦然。

數學性質:Asymptoticity

漸近性」。逐步貼近一條線。

輸入輸出是離散集合(自然數、整數),最終可能抵達循環。

輸入輸出是連續集合(實數、複數),最終也可能漸近循環。

漸近循環,該循環稱作limit cycleasymptotic period,該性質稱作asymptotic periodicity

漸近定值,該定值稱作attractorattractive fixed point,該性質稱作convergence

不循環,最終可能漸近無限遠處、可能到處亂跑。到處亂跑,有時候是繞行。繞行的大致中心稱作strange attractor

數學性質:Stability

穩定性」。走往steady state、或者繞行steady state。

穩定性的原始定義:位於steady state附近的起點,只會途經steady state附近的點。

穩定性還隱含了另一個意義:位於steady state附近的起點,最終必然循環。【尚待確認:半徑小於ε的二維實數是有限個。】

steady state可以利用穩定性,分成兩種類型:

  stable steady state:周圍所有起點,最終都會循環。
unstable steady state:周圍某些起點,最終不會循環。

steady state還有另一套更清晰的分類方式,分成四種類型:

sink  :匯點。周圍聚合,宛如吸引。(stable)(attractor)
source:源點。周圍離開,宛如排斥。(unstable)
saddle:鞍點。兩者都有。     (unstable)
center:中心。周圍旋繞,宛如公轉。(neutral stable)(limit cycles)

明明主角應該是orbit,但是orbit目前仍然沒人分類。原因也許是orbit可以分成非常多種類型。

數學性質:Ergodicity

遍歷性」。無論怎麼走,分布皆相同。

令步數趨近無限大。無論初始數值為何,途經數值的出現次數,趨近相同分布。

如果循環,缺乏討論意義。步數趨近無限大,只需考慮循環數值,而循環數值顯然是固定數值。

如果不循環,才有討論意義。遍歷性是針對不循環的情況。

數學現象:Fractal

連續時,漸近循環的起點們,形成連續區域與連續邊界,邊界可能平滑、可能粗糙。邊界粗糙,該現象稱作「碎形」。

不連續時,可能不會形成區域與邊界,難以討論。

數學現象:Chaos

穩定時,一條路線,可能循環、可能不循環。

不穩定時,不循環可能漸近無限遠處、可能到處亂偏亂飄。亂偏亂飄,該現象稱作「混沌」。

課程、書籍、講義

專著《Chaos and Fractals: An Elementary Introduction》詳細介紹原理。

專著《Elegant Chaos: Algebraically Simple Chaotic Flow》《Elegant Fractals: Automated Generation of Computer Art》彙整大量素材。

Dynamical System(Under Construction!)

Dynamical System

「動態系統」。

Iterated Function System給定行進地點,Dynamical System給定行進方向。

數學式子習慣寫成微分方程式。

dt移項,Dynamical System簡化成Iterated Function System。

Dynamical System可以畫成圖形

自訂dt大小,以計算行進距離。dt越小越精準。

理論上dt必須無限微小,實務上dt無法低於浮點數最小精確值。

既然無法推導公式解、無法保證dt無限微小,怎麼保證產生Chaos?

數學性質:Periodicity

行進地點不變,稱作steady state或fixed point。這裡改成:行進方向是零向量,稱作equilibrium pointstationary point

延伸閱讀:Arithmetic Dynamics

https://en.wikipedia.org/wiki/Arithmetic_dynamics

Fractal

Fractal

繁中「碎形」、簡中「分形」。形狀粗糙,局部放大亦然。

碎形的面積有限、邊長無限。例如Coastline Paradox

碎形的粗糙程度稱作Fractal Dimension,定義源自拓樸學的Hausdorff Dimension。維基百科整理了一份碎形的粗糙程度列表

大家習慣討論遞迴碎形:局部放大,形狀依然相同。

範例:Fractal Curve

線狀碎形,通稱Fractal Curve。例如Koch curve

填滿平面的線狀碎形,通稱Space-filling Curve。例如Peano CurveDragon Curve

填滿或挖空平面的形狀碎形,沒有特地取名。例如Sierpiński CarpetMenger SpongeApollonian Gasket

Iterated Function System

特殊的Iterated Function System也可以製作碎形。

範例:Julia Set / Mandelbrot Set

複數系統,二次函數遞推。每種數值分別作為起點,最終可能循環或不循環。每個起點是否循環,劃分區域,形成Julia Set

複數系統,二次函數遞推。以原點作為起點,最終可能循環或不循環。每種常數項是否循環,劃分區域,形成Mandelbrot Set

範例:Newton Fractal

複數系統,多項式方程式求根,演算法是Newton's Method。每種數值分別作為起點,逐步漸近根。每個起點所對應的根,劃分區域,形成Newton Fractal

範例:Bifurcation Diagram

實數系統,二次函數遞推,函數是Logistic Map。以固定數值0.5作為起點,逐步漸近循環。每種係數的每個循環數值,描到二維座標平面,形成Bifurcation Diagram

Chaos

Chaos

「混沌」。沒有穩定路線。

維基百科整理了一份製造混沌的函數列表

範例:Cellular Automaton

Cellular Automaton又稱作Conway's Game of Life。二維方格平面,每個格子都有一個細胞,可能死、可能活。每個細胞根據鄰居細胞存活數量,決定下一刻死活。

Dynamical System

特殊的Dynamical System也可以製作混沌。

範例:Lorenz System

Lorenz System是模擬大氣對流的微分方程組。

範例:Double Pendulum

Double Pendulum是兩個單擺串在一起。

範例:Three-body Problem

Three-body Problem是三個天體相互運動。

Tetration

遞冪【目前稱作疊代冪次Tetration】

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

luogu P4139

遞對數【目前稱作疊代對數Iterated Logarithm】

https://en.wikipedia.org/wiki/Iterated_logarithm

Continued Fraction

遞加乘【尚無正式名稱】

多項式函數:加數無限制(係數),乘數皆相同(x)。

f(x) = 8x⁰ - 4x¹ + 0x² + 2x³
     = (((((2 ⋅ x) + 0) ⋅ x) - 4) ⋅ x) + 8

【尚無正式名稱】:加數皆相同(1),乘數無限制。

f(x) = a₀ + a₀a₁ + a₀a₁a₂ + a₀a₁a₂a₃
     = (((((a₃ + 1) ⋅ a₂) + 1) ⋅ a₁) + 1) ⋅ a₀

遞加除【目前稱作連分數Continued Fraction】

輾轉相除法:被加數無限制(商數),被除數皆相同(1)。

415/93 = 4 + (1 / (2 + (1 / (6 + (1 / 7)))))

【尚無正式名稱】:被加數皆相同(x),被除數無限制。

Euler's Continued Fraction Formula

https://en.wikipedia.org/wiki/Euler's_continued_fraction_formula

Periodic Continued Fraction

專著《A Friendly Introduction to Number Theory》

以下只介紹結論。詳情請見專著第47章、第48章。

一、連分數前n項化作一般分數。分子分母擁有遞迴公式。

a₀ + 1 / (a₁ + 1 / (a₂ + ... + 1 / aₙ)) = [a₀ a₁ ... aₙ] = pₙ/qₙ

{ p₀ = a₀
{ p₁ = a₁a₀ + 1
{ pₙ = aₙpₙ₋₁ + pₙ₋₂

{ q₀ = 1
{ q₁ = a₁
{ qₙ = aₙqₙ₋₁ + qₙ₋₂

二、相鄰兩項差距。

pₙ₋₁    pₙ    (-1)ⁿ
———— - ——— = ——————
qₙ₋₁    qₙ    qₙ₋₁qₙ

三、循環連分數等價於一元二次方程式的解。

四、Pell Equation的最小正整數解:√D̅的循環連分數,刪除第二節以降,然後化作分數。若循環節長度為奇數,需要平方處理。

solve x² - Dy² = 1

√D̅ = [a₀ b₁ b₂ ... bₘ]
p/q = [a₀ b₁ b₂ ... bₘ]

if m is even   if m is odd
{ x = p        { x = p² + q²D
{ y = q        { y = 2pq

五、Pell Equation的所有解:左式分解,取正號,各種次方。

(x + √D̅y)ⁿ = xₙ + √D̅yₙ

Fixed Point Iteration

連分數可以視作不動點遞推法。收斂時得到不動點。

https://www.zhihu.com/question/310221821/answer/585843958

連分數視作不動點遞推法視作梯度下降法。

http://www.ramanujanmachine.com/

UVa 834

Collatz Conjecture

Collatz Conjecture

3n+1猜想。凡是正整數,偶數除以2,奇數乘以3再加1,遞推下去,最後一定變成1?

UVa 100 371 694