分形及其計(jì)算機(jī)生成

1、分 形 及 其 計(jì) 算 機(jī) 生 成宣文霞傅德勝文亞平摘 要 本文重點(diǎn)以圖象的方式直觀地探討了分形的特征。 并用 c 語(yǔ)言編制程序模擬生成分形圖象 j u lia 集和m an2 de lb ro t 集, 通過(guò)對(duì)其圖象的邊界進(jìn)行逐級(jí)放大, 可以清楚地了 解到它們的無(wú)限嵌套的自相似性以及 j u lia 集和m ande lb ro t 集的密切關(guān)系。f 是分形, 是指它具有下面典型的性質(zhì)2 :(1) f 具有精細(xì)的結(jié)構(gòu), 也就是說(shuō)在任意小的尺度之下,它總有復(fù)雜的細(xì)節(jié);( 2) f 是不規(guī)整的, 它的整體與局部都不能用傳統(tǒng)的幾何 語(yǔ)言來(lái)描述;( 3) f 通常用自相似形式, 這種自相似可以是近似

2、的或是 統(tǒng)計(jì)意義下的;( 4) 一般地, f 的某種定義之下的分形維數(shù)大于它的拓?fù)?維數(shù);( 5) 在大多數(shù)令人感興趣的情形下, f 以非常簡(jiǎn)單的方法 確定, 可能由迭代過(guò)程產(chǎn)生。從以上的定義可以看出, 自相似性和標(biāo)度下變 ( 或無(wú)特征 長(zhǎng)度) 性是分形的兩大突出特點(diǎn)。 同時(shí)這兩個(gè)特點(diǎn)又是一致的, 即一個(gè)具有自相似特性的物體 ( 系統(tǒng)) 必定滿足標(biāo)度不變性。本文以下便主要研究了兩個(gè)典型的分形圖象 j u lia 集和 m ande lb ro t 集的計(jì)算機(jī)模擬生成及其局部放大算法, 一方面 從實(shí)驗(yàn)上驗(yàn)證了分形的以上特點(diǎn), 另一方面也可以使我們直 接觀察到分形精妙無(wú)比的無(wú)究變化和奧秘。關(guān)鍵詞

3、分形j u lia 集 m ande lb ro t 集自相似性近 20 年來(lái)。分形的研究受到非常廣泛的重視, 其原因在于分形既有深刻的理論意義, 又有巨大的實(shí)用價(jià)值。分形向人 們展示了一類具有標(biāo)度不變對(duì)稱性的新世界, 吸引著人們尋 求其中可能存在著的新規(guī)律和新特征。在分形的諸多研究課題中, 分形的計(jì)算機(jī)生成問(wèn)題具有 明顯的挑戰(zhàn)性, 借助計(jì)算機(jī)的繪圖手段以及快速的運(yùn)算速度, 能夠?qū)⒁恍┖?jiǎn)單的數(shù)學(xué)公式迭代過(guò)程展現(xiàn)在屏幕上, 產(chǎn)生一 幅幅生動(dòng)美麗的圖象。本文用 c 語(yǔ)言編制程序生成了 j u lia 集和m ande lb ro t 集 的圖象并逐級(jí)放大, 這個(gè)功能相當(dāng)于在計(jì)算機(jī)的顯微鏡下觀 察復(fù)

4、平面上某些特定的區(qū)域, 從中探索這些極為壯觀而意義 的分維數(shù)集, 得到一些極為相似而又混亂的圖形。二、jul ia 集與m an de lbro t 集一、分形 (fra c ta l)j u lia 集與m ande lb ro t 集來(lái)自非線性映射眾所周知, 自然界大部分是處于無(wú)序的、不穩(wěn)定的、非平衡的和隨機(jī)的狀態(tài)之中, 它存在著無(wú)數(shù)的非線性過(guò)程。例如我 們平常接觸到的天氣情況, 實(shí)際上, 完全相同的天氣是絕對(duì)不 會(huì)重現(xiàn)的。而利用傳統(tǒng)的線性近似方法去研究他們是無(wú)能為 力的, 因?yàn)閷?duì)于復(fù)雜一些的非線性系統(tǒng)和過(guò)程, 連其微分方程 ( 組) 都無(wú)法確定。分形理論與傳統(tǒng)線性近似處理方法本質(zhì)上 的區(qū)

5、別就在于它直接從非線性復(fù)雜系統(tǒng)的本身入手, 從未經(jīng) 簡(jiǎn)化和抽象的研究對(duì)象本身去認(rèn)識(shí)其內(nèi)在的規(guī)律性1 , 從而 揭示了非線性系統(tǒng)中有序與無(wú)序的統(tǒng)一, 確定性與隨機(jī)性的 統(tǒng)一。引導(dǎo)人們以新的觀念、新的手段來(lái)處理非線性世界中的 隨機(jī)性和復(fù)雜性, 透過(guò)樸朔迷離的無(wú)序的混亂現(xiàn)象和不規(guī)則 的形態(tài), 揭示隱藏在復(fù)雜現(xiàn)象背后的規(guī)律、局部和整體之間的 本質(zhì)聯(lián)系。一般地, 可把分形看作大小碎片聚集的狀態(tài), 是沒(méi)有特征 長(zhǎng)度的圖形和構(gòu)造以及現(xiàn)象的總稱。k. f a lco ne r 認(rèn)為: 稱集合x(chóng) x + 2現(xiàn)在考慮復(fù)數(shù)的情形, 按習(xí)慣, 復(fù)數(shù)用 表示, 迭代過(guò)程寫(xiě)成, n = 0, 1, 2,(1)z n+ 1

6、 = z n +給定復(fù)數(shù) z0 作為初始值, 從上式得 z1 , 繼而 z2 , z3 ,11jul ia 集我們來(lái)看以上迭代過(guò)程對(duì)于特例 = 0 的情形, 這時(shí)簡(jiǎn)單 的有2 4 8z 0 z 0 z 0 z 0對(duì)此可以分三種情況進(jìn)行討論:(1) 如果給定的復(fù)數(shù) z0 的模小于 1, 那么迭代序列中的數(shù)按模將越來(lái)越小, 且趨于零, 則說(shuō)零是 z0 z2 的吸引子。所以0復(fù)平面上所有與該原點(diǎn)相距小于 1 的點(diǎn), 都產(chǎn)生趨向此吸引子的序列。 宣文霞 南京氣象學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 助教 南京 210044 傅德勝 南京氣象學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 副教授 碩士生導(dǎo)師 南京 210044 文亞平 南京

7、氣象學(xué)院數(shù)學(xué)系 助教 南京 210044(2) 如果用與原點(diǎn)相距為 1 的點(diǎn)作為初值進(jìn)行迭代, 那么產(chǎn)生的序列總出現(xiàn)在復(fù)平面的單位圓周上。對(duì)這種情況, 稱單 位圓周為此迭代的吸引區(qū)域。(3) 如果給定的復(fù)數(shù) z0 的模大于 1, 則迭代序列中的數(shù)按模越來(lái)越大, 且趨于無(wú)窮, 這時(shí)說(shuō)無(wú)究也是 z0 z2 的吸引子。0所以復(fù)平面上所有與零點(diǎn)的距離超過(guò) 1 的點(diǎn)都產(chǎn)生趨向無(wú)窮的序列;當(dāng) 0 時(shí), 吸引子不再是零, 而且吸引區(qū)域不再是一個(gè) 簡(jiǎn)單的圓周或圓周的變形, 而是由無(wú)究多個(gè)變形閉曲線組成 的精美圖案。一般說(shuō), 對(duì) 的不同選擇, 可以有不同形狀的所 謂邊界, 數(shù)學(xué)上稱這類邊界為 j u lia 集

8、。對(duì) 的某些值, j u lia 集 很明顯是連通的, 也就是形成了單獨(dú)一個(gè)區(qū)域。但對(duì)另一些 值, j u lia 集卻不是聯(lián)通的。21m an de lbro t 集m ande lb ro t 集是基于這樣一種考慮而生成的: 在復(fù)平面 上, 使迭代過(guò)程 x x2 + 產(chǎn)生的序列確定為有界的, 那么復(fù) 數(shù) 又將怎樣分布在復(fù)平面上呢? 如此 的集合叫做m ande l2b ro t 集。其精確的定義如下1 :同時(shí), 在完成逐步放大的過(guò)程中, 由于后續(xù)圖象的精細(xì)結(jié)構(gòu)將非常敏感地依賴于前面的放大區(qū)域的選取。所以在設(shè)計(jì) 算法時(shí)采用了一個(gè)雙向鏈表來(lái)記錄逐步放大的過(guò)程, 這樣當(dāng) 在放大的過(guò)程中發(fā)現(xiàn)已經(jīng)沒(méi)

9、有更多的細(xì)節(jié)或所選取的區(qū)域不 滿意時(shí)可以回到上一幅圖, 重新選取放大區(qū)域, 并且隨時(shí)可以 對(duì)滿意的圖象進(jìn)行存盤(pán), 這樣通過(guò)運(yùn)行程序就能方便靈活地 觀測(cè)分形圖象的各種細(xì)節(jié), 了解它的無(wú)限嵌套的自相似性。程 序采用模塊化結(jié)構(gòu)設(shè)計(jì), 共有六大功能模塊組成, 分別用來(lái)完 成鼠標(biāo)初始化及位置捕獲; m ande lb ro t 集的生成; j u lia 集的生 成; 圖象數(shù)據(jù)存儲(chǔ)和圖象的恢復(fù); 處理過(guò)程的鏈表生成。 程序 布局較靈活, 因而很容易對(duì)模塊進(jìn)行修改、擴(kuò)充。11m an de lbro t 集生成模塊此模塊是核心部分, 用于生成 m ande lb ro t 集的基本圖 象。首先選擇復(fù)平面上

10、待檢查的正方形區(qū)域, 這里我們選擇左下角的坐標(biāo)為 (- 2125, - 115) , 邊長(zhǎng)為 3 的正方形, 與此正 方形相對(duì)應(yīng)的是計(jì)算機(jī)屏幕上的 480480 點(diǎn)陣。根據(jù)迭代公 c : f k (0) 1 有界m =(2)k= c : f k (0) (k ) (3)這是在計(jì)算機(jī)上生成圖象的基礎(chǔ)。以上定義可以看出: z 從 0 開(kāi)始, 是一個(gè)初始復(fù)數(shù), 進(jìn)行 反復(fù)迭代。迭代運(yùn)算的對(duì)象實(shí)際上就是那個(gè)初始復(fù)數(shù) , 它在 復(fù)平面上代表一個(gè)點(diǎn)。從這個(gè)初始點(diǎn)出發(fā)經(jīng)多次迭代后, 會(huì)有 兩種趨勢(shì):( 1) 迭代的總結(jié)果離開(kāi)平面的中心越來(lái)越遠(yuǎn), 趨向無(wú)究 大, 則初始點(diǎn) 不屬于m 集;(2) 迭代的總結(jié)果總

11、何持有限, 則初始點(diǎn) 在m 集中。 用不同的 值反復(fù)進(jìn)行迭代, 那些即使進(jìn)行了無(wú)數(shù)次的迭代運(yùn)算之后, x2 + 的值也是有限的復(fù)數(shù) 的集合, 就構(gòu)成了形狀極其復(fù)雜的m ande lb ro t 集。式 zn+ 1 z2 + , 設(shè) z= x + y i, = a + b i, z 的初值取 0, 然后n三、計(jì)算機(jī)生成對(duì)矩形區(qū)域內(nèi)的每個(gè)復(fù)數(shù) 進(jìn)行迭代, 其基本算法如下:1) co un t0, a= - 2. 25, b = - 1. 5, side= 3. 0從上面的分析可以看出, j u lia 集和m ande lb ro t 集都是考sideside2 ) de lta = m - 1,

12、 de ltb = n - 1 (m 和 n 分別代表屏幕顯示查復(fù)平面上的點(diǎn)按照迭代公式 zn+ 1 z2 + 進(jìn)行迭代時(shí)所表n區(qū)域象素點(diǎn)的寬度和高度值)3) x = 0, y= 0, co un t= 04) 當(dāng) co un t 100 且 x2 + y2 4, 重復(fù)做下面的操作x 1= x2 - y2 + a y= 2xy+ bx = x 1co un t= co un t+ 14) 根據(jù) co un t 的值標(biāo)示出當(dāng)前點(diǎn)的顏色5) 若檢測(cè)區(qū)域已取完, 則程序結(jié)束, 否則 a = a + de lta, b =現(xiàn)出來(lái)的性質(zhì)。因此, 運(yùn)用計(jì)算機(jī)模擬生成的基本處理過(guò)程如圖 1 所示。通常情況下

13、選取 j u lia 集和m ande lb ro t 集里有意義的局 部邊界進(jìn)行放大以觀察其局部細(xì)節(jié)是困難的, 這是因?yàn)榈?過(guò)程對(duì)初值的依賴是非常敏感的, 若想憑直覺(jué)來(lái)選取復(fù)平面 上的某一區(qū)域來(lái)進(jìn)行放大幾乎是不可能。所以本文在設(shè)計(jì)局 部放大算法時(shí)采取了較為新穎的方法, 即考慮直接在生成的 圖象上利用鼠標(biāo)拖動(dòng)矩形框來(lái)定位放大的區(qū)域, 由此來(lái)確定 新的迭代的開(kāi)始位置。24b + de ltb 轉(zhuǎn)至步驟 2)21 關(guān)鍵問(wèn)題的討論(1) 復(fù)數(shù)迭代理論的一個(gè)簡(jiǎn)單結(jié)果表明, 要使 z 在迭代過(guò) 程中趨向無(wú)窮大, 其充要條件是在迭代運(yùn)算的某一步| z| 2。 因此, 在研究m ande lb ro t

14、集和j u lia 集時(shí), 如果某次迭代值| z|2, 則以后的迭代序列中 z 將肯定會(huì)趨向無(wú)窮大, 再也不返 回。( 2) 由于在程序中不可能讓迭代無(wú)限制進(jìn)行下去, 故設(shè)置 一個(gè)迭代次數(shù)的上限 ( 如 100 或 1000) , 若迭代次數(shù)達(dá)到上限次數(shù)還未發(fā)散 (即| z| 2) , 則認(rèn)為此迭代序列必將有界。當(dāng)然 迭代上限在一定的范圍內(nèi)取值越大, 則得到的圖象將越精細(xì),但將花費(fèi)更多的運(yùn)算時(shí)間。綜合考慮兩方面的因素, 一般迭代 上限取 500 1000 之間的數(shù)較為適宜。(3) 程序中根據(jù)迭代次數(shù) co un t 的值來(lái)標(biāo)示屏幕上坐標(biāo)點(diǎn) 的顏色, 它的大小反映了一個(gè)點(diǎn)趨于無(wú)窮大的快慢。( 4

15、) 逐級(jí)放大時(shí), 移動(dòng)鼠標(biāo)在圖象邊界上選取新的區(qū)域,返回新的坐標(biāo)值 (x 1, y1) , 此時(shí)的 (x 1, y1) 指的是屏幕的橫、縱 坐標(biāo)。要實(shí)現(xiàn)放大 (這里的放大與普通圖象的放大不同, 它實(shí) 際上是在復(fù)平面上又選取一個(gè)矩形區(qū)域, 對(duì)區(qū)域內(nèi)的每個(gè)點(diǎn) 進(jìn)行迭代) , 必須將 (x 1, y1) 轉(zhuǎn)換為它所對(duì)應(yīng)的復(fù)平面上的一 個(gè)復(fù)數(shù)。具體操作如下:a + (s id em ) x 1b + (s id en ) y 1a =b =其中 side 的值為上次放大區(qū)域的邊長(zhǎng)。四、結(jié)果與討論圖 2 (a) 中展示了幾種j u lia 集的圖象。在圖 2 (b ) 中展示了m ande lb ro

16、t 集的基本圖象及對(duì)其邊緣放大的一系列圖象:圖 2 (a)一組 j u lia 集的圖象圖 2 (b ) m andb ro t 集及其局部放大的圖象(1) 雖然m ande lb ro t 集并非象經(jīng)典分形集那樣是數(shù)學(xué)上嚴(yán)格自相似的, 但是它卻具有一種相關(guān)特征: 如將m ande lb ro t 集的邊界放大, 便會(huì)顯示出該集無(wú)窮數(shù)量的微型縮影, 而這些 微型m ande lb ro t 集中沒(méi)有一個(gè)是與母集完全一樣的, 它們自 己也各不相同。(2) 從某種意義上講, m ande lb ro t 集概括了所有可能的j u lia 集, 它是無(wú)窮數(shù)量的j u lia 集的直觀的圖解目錄表。根

17、據(jù) 點(diǎn)在m ande lb ro t 集中的位置, 就能預(yù)測(cè)與之相關(guān)的 j u lia 集的 外形及大小, 如果 點(diǎn)在m ande lb ro t 集內(nèi), 相應(yīng)的 j u lia 集就 是連通的; 如果 點(diǎn)選自m ande lb ro t 集之外, 則其 j u lia 集就 是不連通的。很直觀地再現(xiàn)了分形的自相似性及其復(fù)雜精細(xì)的結(jié)構(gòu), 這只是對(duì)分形理論的一個(gè)初步研究。m ande lb ro t 集現(xiàn)在已經(jīng)是分形理論的內(nèi)容之一, 也成了 混沌的一種國(guó)際標(biāo)志, 它美麗無(wú)比、色彩斑斕的圖案給人以藝 術(shù)享受。如果能夠用于印染工藝, 那么探索m ande lb ro t 集和 j u lia 集的圖

18、象將是一項(xiàng)非常有價(jià)值的工作。參考文獻(xiàn)張濟(jì)忠編著, 分形, 清華大學(xué)出版社, 1995, 99 102齊東旭著, 分形及計(jì)算機(jī)生成, 科學(xué)出版社, 1996, 24 26,30d ew dney a k , 科學(xué) (中文版, 譚建亮譯) , 1985d ew dney a k , 科學(xué) (中文版, 朱丹譯) , 1988(收稿日期: 99 年 9 月 21 日)12五、結(jié)語(yǔ)34本文實(shí)現(xiàn)了m ande lb ro t 集和 j u lia 集圖象的生成與放大,issn 10072757xm ic ro c om p u te r a p p lic a t io nsm o n th ly(s i

19、n ce 1985)w u q id ie d ito r2in 2c h iefv o l. 16, n o. 3 (gen e ra l n o. 83) m a rch 2000spec ia l top ic: ne twork an d its a pp l ica t ionp5s c ience & t ech nology w u h an 430074) l an q u n ru i (s ch ool ofre search on ne twork storage techn o logyh an d ez h i ( i ns t itu te of c om p u

20、te r, c en t ra l2c h ina u n iv e rs ity ofa d u l t e d u ca t ion , x iny ang n orm a l c ol leg e x iny ang 464000)a bstrac t t h is p ap e r de sc r ibe s th e p re sen t sta tu s o f ne tw o rk sto rage a s w e ll a s th e d isadvan tage o f t rad it io na l sto rage dep end ingo n se rve r. t

21、 h e tech no lo gy o f ne tw o rk a t tach ed sto rage and sto rage lo ca l ne tw o rk a re p re sen ted. a com p a r iso n be tw een bo th is g iven. f ina lly, it g ive s an in t ro duc t io n to app lica t io n s o f sto rage lo ca l ne tw o rk and ne tw o rk a t tach ed sto rage.keywords ne tw o

22、 rk sto rage ne tw o rk a t tach ed sto rage sto rage lo ca l ne tw o rk f ib re ch anne lp9d e s ign an d a pp l ica t ion of a rem o te m on itor in g & d iagn o st ic sy stem ba sed on in tern e tj i l im ing w ang t a iy ong ( i ns t itu te of m ech an ica l e ng inee r ing , t ianj in u n iv e

23、rs ity t ianj in 300072)a bstrac t t h is p ap e r de sc r ibe s in te rne t2ba sed rem o te m o n ito r ing & d iagno sing m ach ine fau lt s. it a lso p re sen t s it s k ey tech2n ique s and p rac t ica l im p lem en ta t io n.keywords rem o te m o n ito r ing & d iagno sing in te rne t d iagno s

24、t ic cen te rrea l iza t ion m e thods of vo ice comm un ica t ion over a tm broadban d ne tworkl in c h u an (w enz h ou n orm a l c ol leg e) z h ang q i (x ian a ir f orce t e lecom m u n ica t ion e ng inee r ing i ns t itu te)p12a bstrac t t h is p ap e r in t ro duce s seve ra l m e tho d s fo

25、 r vo ice comm un ica t io n o ve r a tm b ro adband ne tw o rk and th a t in th e h yb r idf ib re co ax ia l (h fc ) ne tw o rk u sing cab le m o dem.keywords a tm b ro adband ne tw o rk vo ice o ve r ip h yb r id f ib re co ax ia l ne tw o rk cab le m o demp14ip techn o logy a pp l ied in comm un

26、 ica t ion a rea st u j ie m a q iany i c h en y i (s h ang h a i c om p u t ing t ech nology r esea rch i ns t itu te s h ang h a i 200040)a bstrac t w ith th e deve lopm en t o f in te rne t, ip becom e s a pop u la r te rm. t h is p ap e r d iscu sse s ip tech no lo gy and it s app lica t io nin

27、comm un ica t io n a rea s w ith em p h a sis o n th e ho t top ic o f ip te lep ho ny.keywords ip tech no lo gy ip te lep ho ny ip faxre sea rch & d e s ignp18d ig ita l m ap in the veh ic le l oca t ion an d nav iga t ion sy stemw e i x ing tao z h u c a il ian ( i ns t itu te of m easu rem en t &

28、 g eop hy s ics, a cad em ia s in ica w u h an 470077)a bstrac t t h e d ig ita l m ap is v ita l in a veh ic le lo ca t io n and nav iga t io n sy stem (v l n s). t h e succe ss o f a v l n s dep end s o n th ede sign o f th e d ig ita l m ap. t h is p ap e r f ir st de sc r ibe s th e requ irem en

29、 t ana ly sis o f th e d ig ita l m ap , th en d iscu sse s it s co n ten t and st ruc tu re, and f ina lly g ive s it s o b jec t2o r ien ted im p lem en ta t io n.keywords d ig ita l m ap v eh ic le l o ca t io n and n av iga t io n sy stem (v l n s)par t ia l im provem en t of a 3 a lgor ithm in

30、a i an d its im p lem en ta t ionm ap m a tch ing o b jec t2o r ien tedp21w u y u anx in (a u tom a t ic c on t rol d ep a r tm en t, u n iv e rs ity of d ef ense s c ience & t ech nology c h ang sh a 410073)a bstrac t a 3 a lgo r ithm is a c la ssica l o ne w ith h eu r ist ic sea rch in a r t if ic ia l in te lligence. t h is p ap e r g ive s it s p a r t