跳轉到內容

分形/複平面迭代/q迭代

來自華夏公益教科書,開放世界開放書籍
透過臨界軌道逆迭代繪製的Julia集(在Siegel圓盤的情況下)
用向後迭代生成的動態平面的週期性外部射線

迭代在數學中指的是迭代一個函式的過程,即重複應用一個函式,使用一次迭代的輸出作為下一次迭代的輸入。[1] 即使是看似簡單的函式的迭代也會產生複雜的行為和難題。[2]

可以進行逆(向後迭代)

  • 排斥器用於繪製Julia集(IIM/J)[3]
  • Jlia集外的圓圈(半徑=ER)用於繪製逃逸時間等值線(趨向於Julia集)[4]
  • Julia集內的圓圈(半徑=AR)用於繪製吸引時間等值線(趨向於Julia集)[5]
  • 臨界軌道(在Siegel圓盤情況下)用於繪製Julia集(可能僅在黃金分割的情況下)
  • 用於繪製外部射線

向前迭代的排斥器是向後迭代的吸引器

  • 迭代始終在動態平面上。
  • 引數平面上沒有動態。
  • Mandelbrot集沒有動力學。它是一組引數值。
  • 引數平面上沒有軌道,不應該在引數平面上繪製軌道。
  • 臨界點的軌道在動態平面上

迭代理論

[編輯 | 編輯原始碼]

這是安德魯·羅賓斯2006-02-15在Tetration論壇上的文章的一部分,作者是安德魯·羅賓斯

"迭代是動力學、混沌、分析、遞迴函式和數論的基礎。在這些學科中,大多數情況下所需的迭代是整數迭代,即迭代引數為整數。然而,在動力系統研究中,連續迭代對於解決某些系統至關重要。

不同的迭代型別可以分類如下

  • 離散迭代
    • 整數迭代
    • 分數迭代或有理迭代
      • 非解析分數迭代
      • 解析分數迭代
  • 連續迭代

離散迭代

[編輯 | 編輯原始碼]

迭代函式

整數迭代

[編輯 | 編輯原始碼]

迭代的通常定義,其中函式方程

用於生成序列


稱為f(x)的自然迭代,在組合下形成一個么半群。


對於可逆函式f(x),逆函式也被認為是迭代,並形成序列

稱為f(x)的整數迭代,在組合下形成一個群。

分數迭代或有理迭代

[編輯 | 編輯原始碼]

求解函式方程:。求解完該函式方程後,就可以求出有理迭代,即的整數迭代。

非解析分數迭代

[edit | edit source]

選擇非解析分數迭代,得到的結果將不是唯一的。(Iga 的方法)

解析分數迭代

[edit | edit source]

求解解析分數迭代,將得到一個唯一的解。(Dahl 的方法)

連續迭代

[edit | edit source]

這是對通常迭代概念的推廣,其中函式方程(FE):f n(x) = f(f n-1(x)) 必須在域(實數或複數)的所有 n 中成立。如果不是這樣,那麼為了討論這些型別的“迭代”(即使它們在技術上不是“迭代”,因為它們不遵循迭代的 FE),我們將討論它們,就好像它們是 f n(x) 的表示式,其中 0 ≤ Re(n) ≤ 1,並且在其他地方由迭代的 FE 定義。因此,即使一種方法是解析的,如果它不滿足這個基本的 FE,那麼根據這個重新定義,它就是非解析的。

非解析連續迭代

[edit | edit source]

選擇非解析連續迭代,得到的結果將不是唯一的。(Galidakis 和 Woon 的方法)

解析連續迭代或解析迭代

[edit | edit source]

求解解析連續迭代,將得到一個唯一的解。

實解析迭代

[edit | edit source]

復解析迭代或全純迭代

[edit | edit source]

步長

[edit | edit source]
  • 整數
  • 分數
  • 動態對映的連續迭代。[8][9] 該連續迭代可以透過有限元方法進行離散化,然後在計算機上並行求解。


視覺化

[edit | edit source]

分解

[edit | edit source]

在復二次多項式的情況下,迭代過程中的移動是複數。它包含 2 個移動

  • 角移動 = 旋轉(參見倍增對映)
  • 徑向移動(參見外部和內部射線,不變曲線)
    • 落入目標集和吸引子(在雙曲和拋物線情況下)



角移動(旋轉)

[edit | edit source]

以轉數計算複數的幅角[14]

/*
gives argument of complex number in turns 


*/

double GiveTurn( double complex z){
double t;

  t =  carg(z);
  t /= 2*pi; // now in turns
  if (t<0.0) t += 1.0; // map from (-1/2,1/2] to [0, 1) 
  return (t);
}

方向

[edit | edit source]

正向

[edit | edit source]

反向

[edit | edit source]
多值複數平方根函式的實部和虛部之間的過渡

反向迭代或逆迭代[15]

  • Peitgen
  • W Jung
  • John Bonobo[16]

Peitgen

[edit | edit source]
 /* Zn*Zn=Z(n+1)-c */
                Zx=Zx-Cx;
                Zy=Zy-Cy;
                /* sqrt of complex number algorithm from Peitgen, Jurgens, Saupe: Fractals for the classroom */
                if (Zx>0)
                {
                 NewZx=sqrt((Zx+sqrt(Zx*Zx+Zy*Zy))/2);
                 NewZy=Zy/(2*NewZx);        
                 }
                 else /* ZX <= 0 */
                 {
                  if (Zx<0)
                     {
                      NewZy=sign(Zy)*sqrt((-Zx+sqrt(Zx*Zx+Zy*Zy))/2);
                      NewZx=Zy/(2*NewZy);        
                      }
                      else /* Zx=0 */
                      {
                       NewZx=sqrt(fabs(Zy)/2);
                       if (NewZx>0) NewZy=Zy/(2*NewZx);
                          else NewZy=0;    
                      }
                 };
              if (rand()<(RAND_MAX/2))
              {   
                  Zx=NewZx;
                  Zy=NewZy; 
                  }
              else {Zx=-NewZx;
                  Zy=-NewZy; }

Mandel

[edit | edit source]

以下是使用來自 Wolf Jung 編寫的程式 Mandel 的程式碼,進行逆迭代的 c 程式碼示例。

/*
/*

 gcc i.c -lm -Wall
 ./a.out
 
 
 
 
z = 0.000000000000000  +0.000000000000000 i
z = -0.229955135116281  -0.141357981605006 i
z = -0.378328716195789  -0.041691618297441 i
z = -0.414752103217922  +0.051390827017207 i



 


*/

#include <stdio.h>
#include <math.h> // M_PI; needs -lm also 
#include <complex.h>

/* find c in component of Mandelbrot set 
 
   uses code by Wolf Jung from program Mandel
   see function mndlbrot::bifurcate from mandelbrot.cpp
   http://www.mndynamics.com/indexp.html

*/
double complex GiveC(double InternalAngleInTurns, double InternalRadius, unsigned int Period)
{
  //0 <= InternalRay<= 1
  //0 <= InternalAngleInTurns <=1
  double t = InternalAngleInTurns *2*M_PI; // from turns to radians
  double R2 = InternalRadius * InternalRadius;
  double Cx, Cy; /* C = Cx+Cy*i */

  switch ( Period ) // of component 
    {
    case 1: // main cardioid
      Cx = (cos(t)*InternalRadius)/2-(cos(2*t)*R2)/4; 
      Cy = (sin(t)*InternalRadius)/2-(sin(2*t)*R2)/4; 
      break;
    case 2: // only one component 
      Cx = InternalRadius * 0.25*cos(t) - 1.0;
      Cy = InternalRadius * 0.25*sin(t); 
      break;
      // for each iPeriodChild  there are 2^(iPeriodChild-1) roots. 
    default: // higher periods : to do, use newton method 
      Cx = 0.0;
      Cy = 0.0; 
      break; }

  return Cx + Cy*I;
}

/* mndyncxmics::root from mndyncxmo.cpp  by Wolf Jung (C) 2007-2014. */

// input = x,y
// output = u+v*I = sqrt(x+y*i) 
complex double GiveRoot(complex double z)
{  
  double x = creal(z);
  double y = cimag(z);
  double u, v;
  
   v  = sqrt(x*x + y*y);

   if (x > 0.0)
        { u = sqrt(0.5*(v + x)); v = 0.5*y/u; return  u+v*I; }
   if (x < 0.0)
         { v = sqrt(0.5*(v - x)); if (y < 0.0) v = -v; u = 0.5*y/v; return  u+v*I; }
   if (y >= 0.0) 
       { u = sqrt(0.5*y); v = u; return  u+v*I; }

   u = sqrt(-0.5*y); 
   v = -u;
   return  u+v*I;
}

// from mndlbrot.cpp  by Wolf Jung (C) 2007-2014. part of Madel 5.12 
// input : c, z , mode
// c = cx+cy*i where cx and cy are global variables defined in mndynamo.h
// z = x+y*i
// 
// output : z = x+y*i
complex double InverseIteration(complex double z, complex double c, char key)
{
    double x = creal(z);
    double y = cimag(z);
    double cx = creal(c);
    double cy = cimag(c);
   
   // f^{-1}(z) = inverse with principal value
   if (cx*cx + cy*cy < 1e-20) 
   {  
      z = GiveRoot(x - cx + (y - cy)*I); // 2-nd inverse function = key b 
      if (key == 'B') { x = -x; y = -y; } // 1-st inverse function = key a   
      return -z;
   }
    
   //f^{-1}(z) =  inverse with argument adjusted
   double u, v;
   complex double uv ;
   double w = cx*cx + cy*cy;
    
   uv = GiveRoot(-cx/w -(cy/w)*I); 
   u = creal(uv);
   v = cimag(uv);
   //
   z =  GiveRoot(w - cx*x - cy*y + (cy*x - cx*y)*I);
   x = creal(z);
   y = cimag(z);
   //
   w = u*x - v*y; 
   y = u*y + v*x; 
   x = w;
  
   if (key =='A'){
    x = -x; 
    y = -y;  // 1-st inverse function = key a
  }
  return x+y*I; // key b =  2-nd inverse function

}


 /*f^{-1}(z) =  inverse with argument adjusted
    "When you write the real and imaginary parts in the formulas as complex numbers again,
       you see that it is sqrt( -c / |c|^2 )  *  sqrt( |c|^2 - conj(c)*z ) ,
     so this is just sqrt( z - c )  except for the overall sign:
    the standard square-root takes values in the right halfplane,  but this is rotated by the squareroot of -c .
    The new line between the two planes has half the argument of -c .
    (It is not orthogonal to c ...  )" 
    ...
    "the argument adjusting in the inverse branch has nothing to do with computing external arguments.  It is related to itineraries and kneading sequences,  ...
    Kneading sequences are explained in demo 4 or 5, in my slides on the stripping algorithm, and in several papers by Bruin and Schleicher.
 
    W Jung " */
    
    
double complex GiveInverseAdjusted (complex double z, complex double c, char key){

  
  double t = cabs(c);
  t = t*t;
  
  
  z =  csqrt(-c/t)*csqrt(t-z*conj(c)); 
  if (key =='A') z = -z; // 1-st inverse function = key a
  // else key == 'B'
  return z; 


}   








// make iMax inverse iteration with negative sign ( a in Wolf Jung notation )
complex double GivePrecriticalA(complex double z, complex double c, int iMax)
{
  complex double za = z;  
  int i; 
  
  
  for(i=0;i<iMax ;++i){
    printf("i = %d ,  z = (%f, %f) \n ", i,  creal(za), cimag(za) );
    za = InverseIteration(za,c, 'A'); 
    

   }

 printf("i = %d ,  z = (%f, %f) \n ", i,  creal(za), cimag(za) );
 return za;
}



// make iMax inverse iteration with negative sign ( a in Wolf Jung notation )
complex double GivePrecriticalA2(complex double z, complex double c, int iMax)
{
  complex double za = z;  
  int i; 
  
  
  for(i=0;i<iMax ;++i){
    printf("i = %d ,  z = (%f, %f) \n ", i,  creal(za), cimag(za) );
    za = GiveInverseAdjusted(za,c, 'A'); 
    

   }

 printf("i = %d ,  z = (%f, %f) \n ", i,  creal(za), cimag(za) );
 return za;
}





int main(){
  
 complex double c;
 complex double z;
 complex double zcr = 0.0; // critical point

 int iMax = 10;
 int iPeriodChild = 3; // period of
 int iPeriodParent = 1;

 
     c = GiveC(1.0/((double) iPeriodChild), 1.0, iPeriodParent); // root point = The unique point on the boundary of a mu-atom of period P where two external angles of denominator = (2^P-1) meet.
     z = GivePrecriticalA( zcr, c, iMax);
     printf("iAngle = %d/%d  c = (%f, %f); z = (%.16f, %.16f) \n ", iPeriodParent,  iPeriodChild, creal(c), cimag(c), creal(z), cimag(z) );

      z = GivePrecriticalA2( zcr, c, iMax);
     printf("iAngle = %d/%d  c = (%f, %f); z = (%.16f, %.16f) \n ", iPeriodParent,  iPeriodChild, creal(c), cimag(c), creal(z), cimag(z) );

return 0; 
}

測試

[edit | edit source]

可以無限次迭代。測試將告知何時可以停止。

  • 正向迭代的逃逸測試

目標集或陷阱

[編輯 | 編輯原始碼]

目標集 用於測試。當 zn 在目標集中時,就可以停止迭代。

引數平面

[編輯 | 編輯原始碼]

"曼德布羅特集沒有動力學。它是一組引數值。引數平面上沒有軌道,不應該在引數平面上繪製軌道。臨界點的軌道在動力學平面上"

動態平面

[編輯 | 編輯原始碼]
  "The polynomial Pc maps each dynamical ray to another ray doubling the angle (which we measure in full turns, i.e. 0 = 1 = 2π rad = 360◦), and the dynamical rays of any polynomial “look like straight rays” near infinity. This allows us to study the
   Mandelbrot and Julia sets combinatorially, replacing the dynamical plane by the unit circle, rays by angles, and the quadratic polynomial by the doubling modulo one map." Virpi K a u k o[17]

c=0時的動態平面 f0

[編輯 | 編輯原始碼]
具有勢函式 的徑向向量場的等勢曲線(紅色)和積分曲線(藍色)。

假設 c=0,那麼可以將動力學平面稱為 平面。

這裡,動力學平面可以被分為:

  • Julia 集 =
  • Fatou 集,它包含兩個子集:
    • Julia 集的內部 = 有限吸引子的吸引域 =
    • Julia 集的外部 = 無窮大的吸引域 =

正向迭代

[編輯 | 編輯原始碼]
單位圓內的複數的 10 次方
指數螺旋
arg 的主值分支

其中:

  • r 是複數 z = x + i 的絕對值模數幅值
  • 是複數 z 的輻角(在許多應用中稱為“相位”),是半徑與正實軸的夾角。通常使用主值。

因此

以及前向迭代:[18]

正向迭代

  • 對半徑平方並使角度翻倍(相位,幅角)[19][20]
  • 得到前向軌跡 = **點列表** {z0, z1, z2, z3... , zn},這些點位於指數螺旋線上。[21][22]

你可以互動式地檢查它

混沌與複數平方對映
[edit | edit source]

迭代呈現混沌現象的非正式原因是,角度在每次迭代中翻倍,而翻倍隨著角度變得越來越大而迅速增長,但相差 2π 弧度的倍數的角度是相同的。因此,當角度超過 2π 時,它必須透過 2π 除以餘數進行*迴圈*。因此,角度根據二元變換(也稱為 2x 模 1 對映)進行變換。由於初始值 *z*0 被選擇為其幅角不是 π 的有理倍數,因此 *z**n* 的前向軌跡不能重複自身並變得週期性。

更正式地說,迭代可以寫成

其中 是透過迭代上述步驟獲得的複數序列,而 代表初始起始數字。我們可以精確地解決此迭代

從角度 θ 開始,我們可以將初始項寫成 ,因此 。這使得角度的連續加倍變得清晰。(這等效於關係 )。

逃逸測試
[edit | edit source]

如果距離

  • 點 z 屬於 Julia 集外部
  • Julia 集


那麼點 z 逃逸(= 它的幅度大於 逃逸半徑 = ER


之後

另請參閱

反向迭代

[edit | edit source]
使用適當選擇的原像對復二次多項式進行反向迭代

每個角度(實數)α ∈ R/Z 以周為單位測量,都具有

  • 一個像 = 2α mod 1 在 倍增對映
  • "在 倍增對映 下有兩個原像:”。[24] 倍增對映的逆函式是多值函式。

注意,這兩個原像之間的差異

是半個週轉 = 180 度 = Pi 弧度。

在倍增對映 d 下的像和原像

在復動力平面使用二次多項式 進行反向迭代

給出反向軌道 = **原像的二叉樹** 

在這樣的樹中,如果沒有額外資訊,就無法選擇好的路徑。

注意,原象顯示旋轉對稱性(180 度)

有關其他函式,請參閱 Fractalforum[25]


另請參閱

fc 的動態平面

[edit | edit source]

可以使用以下方法進行檢查

逃逸時間或吸引時間的等高線

[edit | edit source]

IIM/J 繪製的朱莉婭集

[edit | edit source]

理論

  • 週期點在朱莉婭集中稠密
  • 朱莉婭集是排斥週期點的集合的閉包

因此,繪製排斥週期點及其軌道(正向和反向 = 逆向)可以直觀地很好地近似朱莉婭集 = 點集足夠稠密,這些點在朱莉婭集上的非均勻分佈並不重要。


在逃逸時間中,計算點 z 的正向迭代。

在 IIM/J 中,計算

  • 複雜二次多項式的排斥不動點[26]
  • 透過逆向迭代計算 的原象

 "We know the periodic points are dense in the Julia set, but in the case of weird ones (like the ones with Cremer points, or even some with Siegel disks where the disk itself is very 'deep' within the Julia set, as measured by the external rays), the periodic points tend to avoid certain parts of the Julia set as long as possible. This is what causes the 'inverse method' of rendering images of Julia sets to be so bad for those cases." Jacques Carette[27]

因為平方根多值函式,所以每個 都有兩個原象 。因此,逆向迭代會建立二叉樹 的原象。

由於二叉樹的擴充套件增長,原象的數量呈指數級增長:完整二叉樹中節點的數量



其中

  • 是樹的高度

如果要繪製完整二叉樹,則儲存二叉樹的方法會浪費大量記憶體,因此另一種方法是

  • 執行緒二叉樹
  • 只繪製二叉樹中的某些路徑
    • 隨機路徑:最長路徑 = 從根到葉的路徑

另請參閱

樹的根
[edit | edit source]
  • 複雜二次多項式的排斥不動點[30]
  • - beta
  • 其他排斥週期點(填充的朱利亞集的切割點)。這在拋物線朱利亞集的情況下尤其重要。

“...排斥不動點β的原像。它們形成一棵樹狀的

                                               beta
                    beta                                            -beta
   beta                         -beta                    x                     y

因此,當您從β開始構建樹時,每個點最終都會被計算兩次。如果您從-β開始,您將獲得相同數量的點,但計算次數減半。

類似的情況也適用於臨界軌道的原像。如果z在臨界軌道上,它的兩個原像中也會有一個在其中,所以您應該繪製-z及其原像的樹,以避免重複計算相同點。”(Wolf Jung

IIM 的變體
[編輯 | 編輯原始碼]
  • 隨機選擇兩個根中的一個 IIM(直到選擇的最大級別)。隨機遍歷樹。最簡單的編碼和快速,但效率低下。從它開始。
    • 兩個根以相同的機率
    • 一個根比另一個根更頻繁
  • 繪製所有根(直到選擇的最大級別)[31]
    • 使用遞迴
    • 使用堆疊(更快?)
  • 在二叉樹中繪製一些罕見路徑 = MIIM。這是繪製所有根的修改。停止使用一些罕見路徑。
    • 使用命中表(while hit(pixel(iX,iY)) < HitMax)[32]
    • 使用導數(while derivative(z) < DerivativeMax)[33][34]
      • “透過修剪樹的密集分支來加快計算速度。一種這樣的方法是在對映變得收縮(累積導數變大)時修剪分支。”Paul Nylander[35]
      • “如果導數大於極限,我們就從給定的位置切斷子樹。這消除了逆迭代中占主導地位的、高度收縮的區域,這些區域已經被記錄下來。我們可以迭代地計算後續的導數。用絕對導數的對數來著色” [36]

程式碼示例

與之比較


另請參閱

另請參閱

[編輯 | 編輯原始碼]
  • 動力系統
    • 不動點
    • 李雅普諾夫數
  • 函式方程
    • 阿貝爾函式
    • 施羅德函式
    • 博特切函式
    • 朱利亞函式
  • 特殊矩陣
    • 卡萊曼矩陣
    • 貝爾矩陣
    • 阿貝爾-羅賓斯矩陣

參考文獻

[編輯 | 編輯原始碼]
  1. 維基百科:迭代
  2. 從區域性到全域性的迭代理論 - 瓦茨拉夫·庫切拉
  3. 朱利亞集的逆迭代演算法 - 馬克·麥克盧爾
  4. 微型計算機的復迭代
  5. 關於具有兩個臨界點的有理對映 - 約翰·米爾諾,圖 5
  6. 迭代函式 - 湯姆·戴維斯
  7. 迭代函式的泰勒級數的存在性和唯一性 - 丹尼爾·蓋斯勒
  8. 動力學對映的連續迭代 - R. 阿爾德羅萬迪,L. P. 弗雷塔斯(聖保羅,IFT)
  9. 分形的連續迭代 - 格拉德·維斯特多普
  10. 如何摺疊朱利亞分形 - 史蒂文·維滕斯
  11. 將圓形摺疊成朱利亞集 - 卡爾·西姆斯
  12. 朱利亞集中複雜性的視覺解釋 - 奧克·施賴弗斯,雅克·J·範·維克(見支援資訊中的影片)
  13. 如何構建朱利亞集
  14. 轉向
  15. 理解朱利亞集和曼德布羅集 - 卡爾·西姆斯
  16. 繪製朱利亞集的快速方法:逆迭代 - 約翰·博諾博
  17. 曼德布羅集中可見分量的樹 - 維爾皮·考科,FUNDAMENTA MATHEMATICAE 164(2000)
  18. 多項式迭代的實部和虛部 - 朱莉婭·A·巴恩斯,克林頓·P·卡里和麗貝斯·E·紹布羅克。紐約數學雜誌 16(2010)749-761。
  19. mandelbrot-hue - 理查德·A·湯姆森
  20. 相位 - 利納斯·維普斯塔斯
  21. 複數 - 戴維·E·喬伊斯
  22. 複數的冪 - 夢之箱
  23. 拋物線朱利亞集是多項式時間可計算的 - 馬克·布拉弗曼
  24. 符號動力學和自相似群 - 弗拉基米爾·涅克拉舍維奇
  25. 關於一般朱利亞集 IFS 的更高次冪查詢。
  26. 維基百科:排斥不動點
  27. mathbbc/185430 mathoverflow 問題:多項式迭代的週期點聚類
  28. Wolfram Alpha
  29. 示例
  30. wikipedia : 排斥不動點
  31. Fractint 文件 - 逆 Julia 集
  32. 影像和 c 原始碼 : 使用命中限制的 IIMM
  33. 克里斯·金 - 探索混沌的黑暗之心
  34. Drakopoulos V.,比較 Julia 集的渲染方法,WSCG 雜誌 10 (2002),155-161
  35. bugman123:分形
  36. dhushara : DarkHeart
華夏公益教科書