跳转到内容

分形/复平面迭代/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
华夏公益教科书