Brain Storm | 
2007-07-05 9:45| 
21 Comments | 本文內(nèi)容遵從CC版權(quán)協(xié)議 轉(zhuǎn)載請注明出自matrix67.com
很多東西都是吹神了的，其中麥田圈之謎相當(dāng)引人注目。上個世紀(jì)里人們時不時能聽見某個農(nóng)民早晨醒了到麥田地一看立馬嚇得屁滾尿流的故事。上面這幅圖就是97年在英國Silbury山上發(fā)現(xiàn)的麥田圈，看上去大致上是一個雪花形狀。你或許會覺得這個圖形很好看。看了下面的文字后，你會發(fā)現(xiàn)這個圖形遠(yuǎn)遠(yuǎn)不是“好看”可以概括的，它的背后還有很多東西。
在說明什么是分形藝術(shù)前，我們先按照下面的方法構(gòu)造一個圖形?？聪聢D，首先畫一個線段，然后把它平分成三段，去掉中間那一段并用兩條等長的線段代替。這樣，原來的一條線段就變成了四條小的線段。用相同的方法把每一條小的線段的中間三分之一替換為等邊三角形的兩邊，得到了16條更小的線段。然后繼續(xù)對16條線段進(jìn)行相同的操作，并無限地迭代下去。下圖是這個圖形前五次迭代的過程，可以看到這樣的分辨率下已經(jīng)不能顯示出第五次迭代后圖形的所有細(xì)節(jié)了。這樣的圖形可以用Logo語言很輕松地畫出來。
你可能注意到一個有趣的事實：整個線條的長度每一次都變成了原來的4/3。如果最初的線段長為一個單位，那么第一次操作后總長度變成了4/3，第二次操作后總長增加到16/9，第n次操作后長度為(4/3)^n。毫無疑問，操作無限進(jìn)行下去，這條曲線將達(dá)到無限長。難以置信的是這條無限長的曲線卻“始終只有那么大”。
當(dāng)把三條這樣的曲線頭尾相接組成一個封閉圖形時，有趣的事情發(fā)生了。這個雪花一樣的圖形有著無限長的邊界，但是它的總面積卻是有限的。換句話說，無限長的曲線圍住了一塊有限的面積。有人可能會問為什么面積是有限的。雖然從上面的圖上看結(jié)論很顯然，但這里我們還是要給出一個簡單的證明。三條曲線中每一條的第n次迭代前有4^(n-1)個長為(1/3)^(n-1)的線段，迭代后多出的面積為4^(n-1)個邊長為(1/3)^n的等邊三角形。把4^(n-1)擴大到4^n，再把所有邊長為(1/3)^n的等邊三角形擴大為同樣邊長的正方形，總面積仍是有限的，因為無窮級數(shù)Σ4^n/9^n顯然收斂。這個神奇的雪花圖形叫做Koch雪花，其中那條無限長的曲線就叫做Koch曲線。他是由瑞典數(shù)學(xué)家Helge von Koch最先提出來的。本文最開頭提到的麥田圈圖形顯然是想描繪Koch雪花。
分形這一課題提出的時間比較晚。Koch曲線于1904年提出，是最早提出的分形圖形之一。我們仔細(xì)觀察一下這條特別的曲線。它有一個很強的特點：你可以把它分成若干部分，每一個部分都和原來一樣（只是大小不同）。這樣的圖形叫做“自相似”圖形(self-similar)，它是分形圖形(fractal)最主要的特征。自相似往往都和遞歸、無窮之類的東西聯(lián)系在一起。比如，自相似圖形往往是用遞歸法構(gòu)造出來的，可以無限地分解下去。一條Koch曲線中包含有無數(shù)大小不同的Koch曲線。你可以對這條曲線的尖端部分不斷放大，但你所看到的始終和最開始一樣。它的復(fù)雜性不隨尺度減小而消失。另外值得一提的是，這條曲線是一條連續(xù)的，但處處不光滑（不可微）的曲線。曲線上的任何一個點都是尖點。
分形圖形有一種特殊的計算維度的方法。我們可以看到，在有限空間內(nèi)就可以達(dá)到無限長的分形曲線似乎已經(jīng)超越了一維的境界，但說它是二維圖形又還不夠。Hausdorff維度就是專門用來對付這種分形圖形的。簡單地說，Hausdorff維度描述分形圖形中整個圖形的大小與一維大小的關(guān)系。比如，正方形是一個分形圖形，因為它可以分成四個一模一樣的小正方形，每一個小正方形的邊長都是原來的1/2。當(dāng)然，你也可以把正方形分成9個邊長為1/3的小正方形。事實上，一個正方形可以分割為a^2個邊長為1/a的小正方形。那個指數(shù)2就是正方形的維度。矩形、三角形都是一樣，給你a^2個同樣的形狀才能拼成一個邊長為a倍的相似形，因此它們都是二維的。我們把這里的“邊長”理解為一維上的長度，那個1/a則是兩個相似形的相似比。如果一個自相似形包含自身N份，每一份的一維大小都是原來的1/s，則這個相似形的Hausdorff維度為log(N)/log(s)。一個立方體可以分成8份，每一份的一維長度都是原來的一半，因此立方體的維度為log(8)/log(2)=3。同樣地，一個Koch曲線包含四個小Koch曲線，大小兩個Koch曲線的相似比為1/3，因此Koch曲線的Hausdorff維度為log(4)/log(3)。它約等于1.26，是一個介于1和2之間的實數(shù)。
我們常說分形圖形是一門藝術(shù)。把不同大小的Koch雪花拼接起來可以得到很多美麗的圖形。如果有MM看了前面的文字一句也不懂，下面這些圖片或許會讓你眼前一亮。
放圖前留下一句話：
Matrix67原創(chuàng)
轉(zhuǎn)貼請注明出處
雖然有些東西似乎是顯然的，但一個完整的定義仍然很有必要。比如，大多數(shù)人并不知道函數(shù)的連續(xù)性是怎么定義的，雖然大家一直在用。有人可能會說，函數(shù)是不是連續(xù)的一看就知道了嘛，需要定義么。事實上，如果沒有嚴(yán)格的定義，你很難把下面兩個問題說清楚。
你知道嗎，除了常函數(shù)之外還存在其它沒有最小正周期的周期函數(shù)?？紤]一個這樣的函數(shù)：它的定義域為全體實數(shù)，當(dāng)x為有理數(shù)時f(x)=1，當(dāng)x為無理數(shù)時f(x)=0。顯然，任何有理數(shù)都是這個函數(shù)的一個最小正周期，因為一個有理數(shù)加有理數(shù)還是有理數(shù)，而一個無理數(shù)加有理數(shù)仍然是無理數(shù)。因此，該函數(shù)的最小正周期可以任意小。如果非要畫出它的圖象，大致看上去就是兩根直線。請問這個函數(shù)是連續(xù)函數(shù)嗎？如果把這個函數(shù)改一下，當(dāng)x為無理數(shù)時f(x)=0，當(dāng)x為有理數(shù)時f(x)=x，那新的函數(shù)是連續(xù)函數(shù)嗎？
Cauchy定義專門用來解決這一類問題，它嚴(yán)格地定義了函數(shù)的連續(xù)性。Cauchy定義是說，函數(shù)f在x=c處連續(xù)當(dāng)且僅當(dāng)對于一個任意小的正數(shù)ε，你總能找到一個正數(shù)δ使得對于定義域上的所有滿足c-δ< x <c+δ的x都有f(c)-ε<f(x)<f(c)+ε。直觀地說，如果函數(shù)上有一點P，對于任意小的ε，P點左右一定范圍內(nèi)的點與P的縱坐標(biāo)之差均小于ε，那么函數(shù)在P點處連續(xù)。這樣就保證了P點兩旁的點與P無限接近，也就是我們常說的“連續(xù)”。這又被稱作為Epsilon-Delta定義，可以寫成“ε-δ定義”。
有了Cauchy定義，回過頭來看前面的問題，我們可以推出：第一個函數(shù)在任何一點都不連續(xù)，因為當(dāng)ε< 1時，δ范圍內(nèi)總存在至少一個點跳出了ε的范圍；第二個函數(shù)只在x=0處是連續(xù)的，因為此時不管ε是多少，只需要δ比ε小一點就可以滿足ε-δ定義了。
在拓?fù)鋵W(xué)中，也有類似于ε-δ的連續(xù)性定義。假如一個函數(shù)f(t)對應(yīng)空間中的點，對于任意小的正數(shù)ε，總能找到一個δ使得定義域(t-δ,t+δ)對應(yīng)的所有點與f(t)的距離都不超過ε，那么我們就說f(t)所對應(yīng)的曲線在點f(t)處連續(xù)。
回到我們的話題，如何構(gòu)造一條曲線使得它可以填滿整個平面。在這里我們僅僅說明存在一條填滿單位正方形的曲線就夠了，因為將此單位正方形平鋪在平面上就可以得到填滿整個平面的曲線。大多數(shù)人可能會想到下面這種構(gòu)造方法：先畫一條單位長的曲線，然后把它變成一個幾字形，接著把每一條水平的小橫線段變成一個幾字形，然后不斷迭代下去，最后得到的圖形一定可以填滿整個單位正方形。我們甚至可以遞歸地定義出一個描述此圖形的函數(shù)：將定義域平均分成五份，第二和第四份對應(yīng)兩條豎直線段上的點，并繼續(xù)對剩下的三個區(qū)間重復(fù)進(jìn)行這種操作。這個函數(shù)雖然分布得有些“不均勻”，但它確實是一個合法的函數(shù)。最后的圖形顯然可以填充一個正方形，但它是不是一條曲線我們還不知道呢。稍作分析你會發(fā)現(xiàn)這條“曲線”根本不符合前面所說的ε-δ定義，考慮任何一個可以無限細(xì)分的地方（比如x=1/2處），只要ε<1/2，δ再小其范圍內(nèi)也有一條豎線捅破ε的界線。這就好像當(dāng)n趨于無窮時sin(nx)根本不是一條確定的曲線一樣，因為某個特定的函數(shù)值根本不能匯聚到一點?？紤]到這一點，我們能想到的很多可以填滿平面的“曲線”都不是真正意義上的連續(xù)曲線。為了避免這樣的情況出現(xiàn)，這條曲線必須“先把自己周圍填滿再延伸出去”，而填滿自己周圍前又必須先填滿“更小規(guī)模的周圍”。這讓我們聯(lián)想到分形圖形。
德國數(shù)學(xué)家David Hilbert發(fā)現(xiàn)了這樣一種可以填滿整個單位正方形的分形曲線，他稱它為Hilbert曲線。我們來看一看這條曲線是怎么構(gòu)造出來的。首先，我們把一個正方形分割為4個小正方形，然后從左下角的那個小正方形開始，畫一條線經(jīng)過所有小正方形，最后到達(dá)右下角?，F(xiàn)在，我們把這個正方形分成16個小正方形，目標(biāo)同樣是從左下角出發(fā)遍歷所有的格子最后到達(dá)右下角。而在這之前我們已經(jīng)得到了一個2x2方格的遍歷方法，我們正好可以用它。把兩個2x2的格子原封不動地放在上面兩排，右旋90度放在左下，左旋90度放在右下，然后再補三條線段把它們連起來。現(xiàn)在我們得到了一種從左下到右下遍歷4x4方格的方法，而這又可以用于更大規(guī)模的圖形中。用剛才的方法把四個4x4的方格放到8x8的方格中，我們就得到了一條經(jīng)過所有64個小方格的曲線。不斷地這樣做下去，無限多次地迭代后，每個方格都變得無窮小，最后的圖形顯然經(jīng)過了方格上所有的點，它就是我們所說的Hilbert曲線。下圖是一個迭代了n多次后的圖形，大致上反映出Hilbert曲線的樣子。
根據(jù)上面這種方法，我們可以構(gòu)造出函數(shù)f(t)使它能映射到單位正方形中的所有點。Hilbert曲線首先經(jīng)過單位正方形左下1/4的所有點，然后順勢北上，東征到右上角，最后到達(dá)東南方的1/4正方形，其中的每一個階段都是一個邊長縮小了一半的“小Hilbert曲線”。函數(shù)f(t)也如此定義：[0,1/4]對應(yīng)左下角的小正方形中所有的點，[1/4,1/2]就對應(yīng)左上角，依此類推。每個區(qū)間繼續(xù)劃分為四份，依次對應(yīng)面積為1/16的正方形，并無限制地這么細(xì)分下去。注意這里的定義域劃分都是閉區(qū)間的形式，這并不會發(fā)生沖突，因為所有m/4^n處的點都是兩個小Hilbert曲線的“交接處”。比如那個f(1/4)點就是左上左下兩塊1/4正方形共有的，即單位正方形正左邊的那一點。這個函數(shù)是一條根正苗紅的連續(xù)曲線，完全符合ε-δ定義，因為f(t-δ)和f(t+δ)顯然都在f(t)的周圍。
Hilbert曲線是一條經(jīng)典的分形曲線。它違背了很多常理。比如，把Hilbert曲線平鋪在整個平面上，它就成了一條填滿整個平面的曲線。兩條Hilbert曲線對接可以形成一個封閉曲線，而這個封閉曲線竟然沒有內(nèi)部空間。回想我們上次介紹的Hausdorff維度，你會發(fā)現(xiàn)這條曲線是二維的，因為它包含自身4份，每一份的一維大小都是原來的一半，因此維度等于log(4)/log(2)。這再一次說明了它可以填滿整個平面。
Hilbert曲線的價值在于建立一維空間與二維空間一一對應(yīng)的關(guān)系。Hilbert曲線可以看作是一個一維空間到二維空間的映射，也就是說我們證明了直線上的點和平面上的點一樣多（集合的勢相同）。Hilbert曲線也是一種遍歷二維格點的方法，它同樣可以用來證明自然數(shù)和有理數(shù)一樣多。如果你已經(jīng)知道此結(jié)論的Cantor證明，你會立刻明白Hilbert遍歷法的證明，這里就不再多說了。當(dāng)然，Hilbert曲線也可以擴展到三維空間，甚至更高維的空間，從而建立一維到任意多維的映射關(guān)系。下圖就是一個三維Hilbert曲線（在迭代過程中）的樣子。
{$ASSERTIONS+}
uses graph,crt;
const
x1=320; y1=20;
x2=90; y2=420;
x3=550; y3=420;
density=2500;
timestep=10;
var
gd,gm,i,r:integer;
x,y:real;
begin
gd:=D8bit;
gm:=m640x480;
InitGraph(gd,gm,'');
Assert(graphResult=grOk);
x:=x1;
y:=y1;
for i:=1 to density do
begin
r:=random(3);
if r=0 then
begin
x:=(x+x1)/2;
y:=(y+y1)/2;
end
else if r=1 then
begin
x:=(x+x2)/2;
y:=(y+y2)/2;
end
else begin
x:=(x+x3)/2;
y:=(y+y3)/2;
end;
PutPixel(round(x),round(y),white);
Delay(timestep);
end;
CloseGraph;
end.const
n=1 shl 5-1;
var
i,j:integer;
begin
for i:=0 to n do
begin
for j:=0 to n do
if i and j = j then write('#')
else write(' ');
writeln;
end;
readln;
end.#include <stdio.h>
int main()
{
const int n=(1<<5)-1;
int i,j;
for (i=0; i<=n; i++)
{
for (j=0; j<=n; j++)
printf( (i&j)==j ? "#" : " ");
printf("\n");
}
getchar();
return 0;
}#
##
# #
####
# #
## ##
# # # #
########
# #
## ##
# # # #
#### ####
# # # #
## ## ## ##
# # # # # # # #
################
# #
## ##
# # # #
#### ####
# # # #
## ## ## ##
# # # # # # # #
######## ########
# # # #
## ## ## ##
# # # # # # # #
#### #### #### ####
# # # # # # # #
## ## ## ## ## ## ## ##
# # # # # # # # # # # # # # # #
################################ 考慮函數(shù)f(z)=z^2-0.75。固定z0的值后，我們可以通過不斷地迭代算出一系列的z值：z1=f(z0), z2=f(z1), z3=f(z2), ...。比如，當(dāng)z0 = 1時，我們可以依次迭代出：
z1 = f(1.0) = 1.0^2 - 0.75 = 0.25
z2 = f(0.25) = 0.25^2 - 0.75 = -0.6875
z3 = f(-0.6875) = (-0.6875)^2 - 0.75 = -0.2773
z4 = f(-0.2773) = (-0.2773)^2 - 0.75 = -0.6731
z5 = f(-0.6731) = (-0.6731)^2 - 0.75 = -0.2970
...
可以看出，z值始終在某一范圍內(nèi)，并將最終收斂到某一個值上。
但當(dāng)z0=2時，情況就不一樣了。幾次迭代后我們將立即發(fā)現(xiàn)z值最終會趨于無窮大：
z1 = f(2.0) = (2.0)^2 - 0.75 = 3.25
z2 = f(3.25) = (3.25)^2 - 0.75 = 9.8125
z3 = f(9.8125) = (9.8125)^2 - 0.75 = 95.535
z4 = f(95.535) = (95.535)^2 - 0.75 = 9126.2
z5 = f(9126.2) = (9126.2)^2 - 0.75 = 83287819.2
...
經(jīng)過計算，我們可以得到如下結(jié)論：當(dāng)z0屬于[-1.5, 1.5]時，z值始終不會超出某個范圍；而當(dāng)z0小于-1.5或大于1.5后，z值最終將趨于無窮。
現(xiàn)在，我們把這個函數(shù)擴展到整個復(fù)數(shù)范圍。對于復(fù)數(shù)z0=x+iy，取不同的x值和y值，函數(shù)迭代的結(jié)果不一樣：對于有些z0，函數(shù)值約束在某一范圍內(nèi)；而對于另一些z0，函數(shù)值則發(fā)散到無窮。由于復(fù)數(shù)對應(yīng)平面上的點，因此我們可以用一個平面圖形來表示，對于哪些z0函數(shù)值最終趨于無窮，對于哪些z0函數(shù)值最終不會趨于無窮。我們用深灰色表示不會使函數(shù)值趨于無窮的z0；對于其它的z0，我們用不同的顏色來區(qū)別不同的發(fā)散速度。由于當(dāng)某個時候|z|>2時，函數(shù)值一定發(fā)散，因此這里定義發(fā)散速度為：使|z|大于2的迭代次數(shù)越少，則發(fā)散速度越快。這個圖形可以編程畫出。和上次一樣，我用Pascal語言，因為我不會C的圖形操作。某個MM要過生日了，我把這個自己編程畫的圖片送給她^_^{$ASSERTIONS+}
uses graph;
type
complex=record
re:real;
im:real;
end;
operator * (a:complex; b:complex) c:complex;
begin
c.re := a.re*b.re - a.im*b.im;
c.im := a.im*b.re + a.re*b.im;
end;
operator + (a:complex; b:complex) c:complex;
begin
c.re := a.re + b.re;
c.im := a.im + b.im;
end;
var
z,c:complex;
gd,gm,i,j,k:integer;
begin
gd:=D8bit;
gm:=m640x480;
InitGraph(gd,gm,'');
Assert(graphResult=grOk);
c.re:=-0.75;
c.im:=0;
for i:=-300 to 300 do
for j:=-200 to 200 do
begin
z.re:=i/200;
z.im:=j/200;
for k:=0 to 200 do
begin
if sqrt(z.re*z.re + z.im*z.im) >2 then break
else z:=(z*z)+c;
end;
PutPixel(i+300,j+200,k)
end;
readln;
CloseGraph;
end.
代碼在Windows XP SP2，F(xiàn)PC 2.0下通過編譯，麻煩大家?guī)兔蟾嬉幌鲁绦蜻\行是否正常（上次有人告訴我說我寫的繪圖程序不能編譯）。在我這里，程序運行的結(jié)果如下：
這個美麗的分形圖形表現(xiàn)的就是f(z)=z^2-0.75時的Julia集?？紤]復(fù)數(shù)函數(shù)f(z)=z^2+c，不同的復(fù)數(shù)c對應(yīng)著不同的Julia集。也就是說，每取一個不同的c你都能得到一個不同的Julia集分形圖形，并且令人吃驚的是每一個分形圖形都是那么美麗。下面的六幅圖片是取不同的c值得到的分形圖形。你可能不相信這樣一個簡單的構(gòu)造法則可以生成這么美麗的圖形，這沒什么，你可以改變上面程序代碼中c變量的值來親自驗證。
c = 0.45, -0.1428
c = 0.285, 0.01
c = 0.285, 0
c = -0.8, 0.156
c = -0.835, -0.2321
c = -0.70176, -0.3842
類似地，我們固定z0=0，那么對于不同的復(fù)數(shù)c，函數(shù)的迭代結(jié)果也不同。由于復(fù)數(shù)c對應(yīng)平面上的點，因此我們可以用一個平面圖形來表示，對于某個復(fù)數(shù)c，函數(shù)f(z)=z^2+c從z0=0開始迭代是否會發(fā)散到無窮。我們同樣用不同顏色來表示不同的發(fā)散速度，最后得出的就是Mandelbrot集分形圖形：
前面說過，分形圖形是可以無限遞歸下去的，它的復(fù)雜度不隨尺度減小而消失。Mandelbrot集的神奇之處就在于，你可以對這個分形圖形不斷放大，不同的尺度下你所看到的景象可能完全不同。放大到一定時候，你可以看到更小規(guī)模的Mandelbrot集，這證明Mandelbrot集是自相似的。下面的15幅圖演示了Mandelbrot集的一個放大過程，你可以在這個過程中看到不同樣式的分形圖形。
