函數(shù)迭代是數(shù)學(xué)中一個(gè)非常重要和有趣的主題,它在不同的領(lǐng)域有著不同的應(yīng)用和著眼點(diǎn)。在動(dòng)力系統(tǒng)中,函數(shù)迭代可以揭示復(fù)雜系統(tǒng)的演化規(guī)律和混沌現(xiàn)象;在計(jì)算數(shù)學(xué)中,函數(shù)迭代可以求解各種非線性方程和優(yōu)化問(wèn)題。
1
離散動(dòng)力系統(tǒng)這門(mén)學(xué)科的主要任務(wù)就是研究“函數(shù)迭代”。自然,這里的“函數(shù)”是在最廣泛的意義上理解的,即它的定義域可以是任何“空間”——帶有某個(gè)數(shù)學(xué)結(jié)構(gòu)的一類集合。當(dāng)然,最簡(jiǎn)單的空間就是實(shí)數(shù)軸上的單位區(qū)間或坐標(biāo)平面上的單位圓周,即便對(duì)于這樣“簡(jiǎn)單”的空間所對(duì)應(yīng)的“一維離散動(dòng)力系統(tǒng)”,其主題卻可以寫(xiě)成一本有五百頁(yè)的大書(shū),需要的數(shù)學(xué)語(yǔ)言來(lái)自分析、拓?fù)洹缀?、代?shù)等幾乎所有現(xiàn)代數(shù)學(xué)的分支。
在離散動(dòng)力系統(tǒng)的范圍談?wù)摵瘮?shù)迭代,討論的重點(diǎn)是不動(dòng)點(diǎn)和周期點(diǎn)的穩(wěn)定性問(wèn)題,探索的目光聚焦在迭代點(diǎn)軌道的最終性態(tài),而混沌學(xué)家則更感興趣于最終走向不可預(yù)測(cè)的不規(guī)則行為,并由此進(jìn)一步用概率統(tǒng)計(jì)的工具研究所有這些行蹤詭異的軌道的整體性質(zhì)。這些都是我在前幾篇文章中試圖向讀者介紹的基本概念和知識(shí)。
然而,在出發(fā)點(diǎn)和目的性完全不一樣的另一個(gè)極其有用的數(shù)學(xué)領(lǐng)域——計(jì)算數(shù)學(xué)里,“函數(shù)迭代”同樣扮演著不可或缺的角色?!坝?jì)算數(shù)學(xué)”,顧名思義,就是以計(jì)算為特征的數(shù)學(xué),它設(shè)計(jì)可行、快速、有效、穩(wěn)定的算法,通過(guò)電子計(jì)算機(jī)的程序?qū)崿F(xiàn),數(shù)值求解科學(xué)技術(shù)中建立起來(lái)的各類方程:常微分方程、偏微分方程、積分方程或一般的算子方程。離散化這些“連續(xù)性方程”就得到線性或非線性的代數(shù)方程組,求解這些方程組的一個(gè)主要方法就是“迭代法”。
與離散動(dòng)力系統(tǒng)研究函數(shù)迭代的多重目的不太一樣的是,計(jì)算數(shù)學(xué)研究迭代的目標(biāo)很一致:尋求迭代軌道的收斂性及其速率。為此,計(jì)算數(shù)學(xué)領(lǐng)域里的學(xué)者談到迭代時(shí)對(duì)周期點(diǎn)幾乎是“冷若冰霜”的,因?yàn)樗鼘?dǎo)致迭代法不收斂,這不是計(jì)算數(shù)學(xué)家和工程學(xué)家所樂(lè)見(jiàn)的。所以當(dāng)我們從計(jì)算數(shù)學(xué)的觀點(diǎn)看函數(shù)迭代時(shí),我們的注意力只需放在迭代軌道收斂性這點(diǎn)上。
四十一年前,我在南京大學(xué)數(shù)學(xué)系修讀計(jì)算數(shù)學(xué)最優(yōu)化理論與方法碩士研究生的第一門(mén)專業(yè)基礎(chǔ)課是“非線性方程組的迭代解”,選用的教材是馬里蘭大學(xué)數(shù)學(xué)系James M. Ortega和Werner C. Rheinboldt 于1970年出版的Iterative Solution of Nonlinear Equations in Several Variables(多變?cè)蔷€性方程的迭代解),分兩學(xué)期學(xué)完。第一學(xué)期由老師講授課程,第二學(xué)期由學(xué)生分章報(bào)告,我們的收獲很大,我甚至做了書(shū)中全部習(xí)題。五年后,在密歇根州立大學(xué)讀博士學(xué)位的課程時(shí),由于修了李天巖教授一門(mén)“[0, 1]上的遍歷理論”學(xué)年課程,我對(duì)離散動(dòng)力系統(tǒng)中的“函數(shù)迭代”產(chǎn)生了興趣,第二年寫(xiě)的博士論文居然與計(jì)算遍歷理論掛上了鉤。可以說(shuō),在我求學(xué)成長(zhǎng)的歲月中,我先后戴著計(jì)算數(shù)學(xué)和動(dòng)力系統(tǒng)的面具,學(xué)過(guò)兩次“函數(shù)的迭代”。
學(xué)過(guò)的知識(shí)有用,就沒(méi)有白學(xué)。這兩種“函數(shù)迭代”的理論都對(duì)我的研究論文有過(guò)貢獻(xiàn),所以算是做到了“學(xué)以致用”。但是現(xiàn)在的我多了一個(gè)想法:將自己年輕時(shí)代學(xué)來(lái)的有用知識(shí)服務(wù)于公眾,傳播更多的數(shù)學(xué)真理。在這篇文章里,我將向?qū)茖W(xué)計(jì)算感興趣的人介紹迭代法背后的基本思想。與往常一樣,我們主要考慮區(qū)間函數(shù)的簡(jiǎn)單情形,方便大家理解。
2
假設(shè)G是定義在一個(gè)區(qū)間I上的連續(xù)函數(shù),并將I映到自身,這樣在I中取定一個(gè)初始點(diǎn)x0,由此出發(fā),就可以周而復(fù)始地迭代下去得到迭代點(diǎn)數(shù)列
x0, x1, x2, …, xn, …,
記為{xn},其中第n個(gè)迭代點(diǎn)xn是G在第n-1個(gè)迭代點(diǎn)xn-1的值,即
xn= G(xn-1), n = 1, 2, …; 給定x0。
如果將n個(gè)G復(fù)合起來(lái)的復(fù)合函數(shù)記為Gn,則xn= Gn(x0)。由于函數(shù)G連續(xù)并將I映入I,函數(shù)Gn也連續(xù)且將I映入I。
計(jì)算數(shù)學(xué)家對(duì)函數(shù)迭代的基本要求是:迭代點(diǎn)數(shù)列{xn}必須收斂。在討論這個(gè)數(shù)列何時(shí)收斂的問(wèn)題前,我們先問(wèn)另一個(gè)問(wèn)題:假設(shè){xn}確實(shí)收斂到I中的一點(diǎn),這個(gè)極限點(diǎn)會(huì)有什么性質(zhì)?或言之,數(shù)列{xn}的極限x*與迭代的函數(shù)G有什么關(guān)系?
注意我們已經(jīng)假設(shè)G在定義域區(qū)間I上連續(xù),這個(gè)信息加上初等微分學(xué)中的連續(xù)概念就提供了回答上述問(wèn)話的線索。連續(xù)函數(shù)有一個(gè)基于數(shù)列的等價(jià)說(shuō)法,即函數(shù)f在點(diǎn)a連續(xù)當(dāng)且僅當(dāng)任給f定義域內(nèi)的數(shù)列{xn},只要它收斂于a,則對(duì)應(yīng)的函數(shù)值數(shù)列{f(xn)}收斂到f(a)。由迭代程式xn= G(xn-1)可知,兩個(gè)數(shù)列{xn}和{G(xn-1)}是恒等的數(shù)列,既然{xn}收斂到x*,那么{G(xn-1)}也收斂到同一個(gè)極限x*。另一方面,由于數(shù)列{xn-1}和{xn}一樣收斂到x*,故G在x*的連續(xù)性就推出{G(xn-1)}收斂到G(x*)。這樣x*和G(x*)都是{xn}的極限,由收斂數(shù)列極限的唯一性,必有x* = G(x*)。這說(shuō)明,迭代點(diǎn)數(shù)列{Gn(x0)}如果收斂到連續(xù)函數(shù)G的定義域中的一點(diǎn),則它一定是G的不動(dòng)點(diǎn)。這個(gè)命題的逆否命題可以幫助我們確認(rèn)何時(shí)一個(gè)迭代點(diǎn)數(shù)列不可能收斂,那就是只要迭代函數(shù)G沒(méi)有不動(dòng)點(diǎn)。例如,如果一個(gè)人迭代自然指數(shù)函數(shù)G(x) = ex,則無(wú)論他從哪一個(gè)初始點(diǎn)出發(fā),迭代點(diǎn)數(shù)列都不會(huì)收斂,因?yàn)椴粍?dòng)點(diǎn)方程x = ex在實(shí)數(shù)集合里無(wú)解。
上述簡(jiǎn)單結(jié)論的一個(gè)邏輯后果是,計(jì)算數(shù)學(xué)中迭代法的目的是數(shù)值求解不動(dòng)點(diǎn)方程x = G(x)。如果這個(gè)方程根本無(wú)解,那就不必構(gòu)造什么迭代法求解它了,所以在研究迭代法前,要先假設(shè)G至少有一個(gè)不動(dòng)點(diǎn)。但是,如果閉著眼睛隨便選取初始點(diǎn)x0開(kāi)始迭代,能保證{Gn(x0)}收斂嗎?
3
我們先看一個(gè)簡(jiǎn)單的例子。設(shè)G(x) = -x,則G有唯一的不動(dòng)點(diǎn)0。然而如果我們?nèi)∪我环橇銛?shù)x0作為初始點(diǎn)迭代G,則得到一個(gè)周期為二的軌道:x0, -x0, x0, -x0, …,不收斂到0。對(duì)函數(shù)G求導(dǎo)數(shù),我們發(fā)現(xiàn)在不動(dòng)點(diǎn)0處,G的導(dǎo)數(shù)值的絕對(duì)值等于1。如果G(x) = 2x,則對(duì)任一初始點(diǎn)x0,易見(jiàn)Gn(x0) = 2nx0,故當(dāng)xn> 0時(shí),{Gn(x0)}發(fā)散到正無(wú)窮大,而當(dāng)xn< 0時(shí),{Gn(x0)}發(fā)散到負(fù)無(wú)窮大,都不收斂到唯一不動(dòng)點(diǎn)0。注意到對(duì)這個(gè)G,導(dǎo)數(shù)在不動(dòng)點(diǎn)0的值的絕對(duì)值大于1。
我們?cè)倏匆粋€(gè)例子:G(x) = x – x2。這時(shí)G依然只有唯一的不動(dòng)點(diǎn)0。運(yùn)用“圖像迭代法”,或通過(guò)初等微分學(xué)中的“單調(diào)收斂定理”可以嚴(yán)格證明:當(dāng)0 < x0?≤ 1時(shí),{Gn(x0)}收斂到不動(dòng)點(diǎn)0,而當(dāng)x0?< 0或x0?> 1時(shí),{Gn(x0)}發(fā)散到負(fù)無(wú)窮大。雖然G在不動(dòng)點(diǎn)0處導(dǎo)數(shù)的絕對(duì)值等于1,但對(duì)不動(dòng)點(diǎn)右側(cè)臨近的初始點(diǎn),迭代點(diǎn)數(shù)列收斂到該不動(dòng)點(diǎn)。讀者可以用幾何方法畫(huà)出一個(gè)連續(xù)函數(shù)y = G(x)的圖像曲線,它與xy-直角坐標(biāo)系的對(duì)角線y = x相切于一點(diǎn)(x*, x*),在切點(diǎn)的左側(cè),曲線位于對(duì)角線上方,向上彎曲;在切點(diǎn)的右側(cè),曲線位于對(duì)角線下方,向下彎曲。然后你就會(huì)發(fā)現(xiàn),盡管G在x*處的導(dǎo)數(shù)絕對(duì)值等于1,但從x*左右兩邊附近的任一初始點(diǎn)x0出發(fā)的迭代點(diǎn)數(shù)列{Gn(x0)}收斂到x*。
這些例子說(shuō)明,在迭代函數(shù)G可求導(dǎo)數(shù)的前提下,當(dāng)G在其不動(dòng)點(diǎn)x*的導(dǎo)數(shù)絕對(duì)值等于1時(shí),在其附近出發(fā)的迭代點(diǎn)數(shù)列可能收斂到x*,也可能不收斂到x*;而當(dāng)G在不動(dòng)點(diǎn)x*的導(dǎo)數(shù)絕對(duì)值大于1時(shí),則根本不能指望迭代點(diǎn)數(shù)列會(huì)收斂到x*。因此,要想迭代法xn= G(xn-1)生成的數(shù)列收斂到G的一個(gè)不動(dòng)點(diǎn),我們一般需要假設(shè)G在這個(gè)不動(dòng)點(diǎn)的導(dǎo)數(shù)絕對(duì)值嚴(yán)格小于1。雖然這個(gè)假設(shè)不是迭代法收斂的必要條件,但確實(shí)是保證收斂的一個(gè)充分條件。它的證明不難,也容易理解,但需要對(duì)導(dǎo)數(shù)的極限定義有透徹的理解。
許多人號(hào)稱學(xué)過(guò)微積分,但可能還需要溫故一下微積分學(xué)中最基礎(chǔ)性的概念——極限,所以我們先來(lái)回憶一下函數(shù)在一點(diǎn)的極限的精確定義:函數(shù)f當(dāng)自變量x趨向于數(shù)a時(shí)有極限L,是指對(duì)于任意給定的正數(shù)ε,存在正數(shù)δ,使得只要位于f定義域內(nèi)的x減去a的絕對(duì)值大于0但又小于δ,其對(duì)應(yīng)的函數(shù)值f(x)減去L的絕對(duì)值就會(huì)小于ε。用數(shù)學(xué)的符號(hào),就是要找到δ,使得若不等式0 < |x – a| < δ成立,則不等式|f(x) – L| < ε也成立。
由于函數(shù)的導(dǎo)數(shù)是通過(guò)函數(shù)的平均變化率的極限來(lái)定義的,函數(shù)f在其定義域內(nèi)一點(diǎn)a的導(dǎo)數(shù)f’(a) = limx → a(f(x) – f(a))/(x-a)按照上面的“ε-δ”語(yǔ)言來(lái)說(shuō)就是:任給正數(shù)ε,存在正數(shù)δ,使得對(duì)f定義域內(nèi)的所有x,不等式0 < |x – a| < δ推出不等式
|(f(x)–f(a))/(x-a) – f’(a)| < ?ε。
好了,我們用上面的導(dǎo)數(shù)定義來(lái)證明關(guān)于迭代法收斂性的一個(gè)基本定理:設(shè)想迭代函數(shù)G在其定義域區(qū)間內(nèi)部有一個(gè)不動(dòng)點(diǎn)x*并且在該點(diǎn)有導(dǎo)數(shù)。如果|G’(x*)| < 1,則存在以x*為中點(diǎn)的一個(gè)小區(qū)間(x* - δ, x* + δ),使得任取此區(qū)間中的一點(diǎn)x0作為初始點(diǎn),迭代點(diǎn)數(shù)列{Gn(x0)}中的所有點(diǎn)都在同一區(qū)間內(nèi)并且lim?n → ∞?Gn(x0) = x*。
在讀懂下面的解析證明之前,不知道這個(gè)命題的讀者可用圖像迭代法看到迭代點(diǎn)的收斂性。我們現(xiàn)在嚴(yán)格證明之。首先因?yàn)閤*位于G的定義域區(qū)間的內(nèi)部,存在一個(gè)正數(shù)δ0使得區(qū)間(x*-δ0, x*+δ0)包含在G的定義域中。由假設(shè)條件,可取ε = (1 - |G’(x*)|)/2 > 0。對(duì)于這個(gè)正數(shù),上述的導(dǎo)數(shù)定義告訴我們,存在正數(shù)δ ≤ δ0,使得滿足不等式0 < |x – x*| < δ的所有點(diǎn)x也滿足不等式
|(G(x)–G(x*))/(x-x*) – G’(x*)| < ?(1 - |G’(x*)|)/2。
由于G(x*) = x*,上式可以改寫(xiě)成
|(G(x)–x*)/(x-x*) – G’(x*)| < ?(1 - |G’(x*)|)/2。
運(yùn)用代數(shù)不等式 |a| - |b| ≤ |a – b|,就可推出 |G(x*)-x*|/|x-x*| - |G’(x*)| < (1 - |G’(x*)|)/2。故
|G(x)-x*|/|x-x*| < |G’(x*)| + (1 - |G’(x*)|)/2 = (1 + |G’(x*)|)/2。
記r = (1 + |G’(x*)|)/2,則正數(shù)r < 1。上面的不等式即為
|G(x)-x*| < r |x-x*|, 任給(x*-δ, x*+δ)中的點(diǎn)x。
因?yàn)閞小于1,此不等式說(shuō)明,當(dāng)初始點(diǎn)x0屬于(x*-δ, x*+δ)時(shí),第一個(gè)迭代點(diǎn)x1= G(x0)也在(x*-δ, x*+δ)之中,故同一不等式保證第二個(gè)迭代點(diǎn)x2= G(x1) = G2(x0)繼續(xù)落在(x*-δ, x*+δ)當(dāng)中,且有|x2– x*| < r |x1?– x*| < r2?|x0?– x*|。推而廣之,我們知道所有迭代點(diǎn)xn?都在區(qū)間(x*-δ, x*+δ)之內(nèi),并滿足不等式
|xn– x*| < rn?|x0?– x*|,n = 1, 2, 3, …。
因?yàn)閘imn → ∞r(nóng)n= 0,結(jié)論就是:迭代點(diǎn)數(shù)列{xn} 趨向于x*。
4
我們證明了G在不動(dòng)點(diǎn)x*的導(dǎo)數(shù)絕對(duì)值小于1是迭代法xn= G(xn-1), n = 1, 2, …具有“局部收斂性”的一個(gè)絕對(duì)重要的充分條件,這里的“局部”意指當(dāng)初始點(diǎn)充分靠近x*時(shí)就能獲得收斂性。更進(jìn)一步,這個(gè)收斂的快慢程度也與|G’(x*)|有關(guān):此值越接近于0,則收斂得越快。自然,最理想的值應(yīng)該就是0了,這時(shí)的收斂速度超過(guò)了像趨向于0的等比數(shù)列{rn}那樣的“線性收斂”,所以被稱為“超線性收斂”。
那么,有名聞遐邇且至少具有超線性收斂的迭代法嗎?當(dāng)然有,而且只需要初等微分學(xué)中的泰勒公式就可以構(gòu)造出許多更高收斂階的迭代法。然而一般而言,如同俗語(yǔ)所述,“一分耕耘一分收獲”,要獲得高階的迭代法,成本也是可觀的,計(jì)算數(shù)學(xué)中的“成本”是用“計(jì)算工作量”來(lái)衡量的。不過(guò),我們幾乎都聽(tīng)過(guò)一個(gè)大名鼎鼎的迭代法,甚至和它常打交道,這就是名字掛的是“牛頓”但實(shí)際上應(yīng)該是“辛普森”的“牛頓迭代法”。
牛頓迭代法用于數(shù)值求解非線性方程,它的基本思想用幾何表達(dá)最直觀易懂。解方程f(x) = 0的幾何意義就是找到函數(shù)y = f(x)的圖像與x-軸的交點(diǎn)。在函數(shù)f可求導(dǎo)且導(dǎo)數(shù)值都不為零的條件下,設(shè)x*是方程的一個(gè)解,但我們卻不知道它是幾,于是我們先取一個(gè)初始點(diǎn)x0作為x*的一個(gè)猜測(cè)。自然f(x0)一般不恰好為零。在圖像上的點(diǎn)(x0, f(x0))處作曲線的切線,根據(jù)導(dǎo)數(shù)的幾何解釋,這根切線的斜率是f’(x0)。由直線的點(diǎn)斜式方程可知,切線的方程是y – f(x0) = f’(x0)(x – x0),在此方程中令y = 0而解出未知數(shù)x的值 x1= x0- f(x0)/f’(x0),它就是切線與x-軸的交點(diǎn)的x-坐標(biāo),當(dāng)x0距離精確解x*不遠(yuǎn)時(shí)應(yīng)該比x0更靠近x*。對(duì)x1重復(fù)做上面的事,得到比x1離x*更近的點(diǎn)x2。由此類推,有了下列求解方程f(x) = 0的牛頓迭代法:
xn= xn-1– f(xn-1)/f’(xn-1),n = 1, 2, 3, …。
如果將原方程f(x) = 0改寫(xiě)成與之等價(jià)的不動(dòng)點(diǎn)方程x = x – f(x)/f’(x),那么上述的牛頓法就是用于后一個(gè)方程的直接迭代法 xn= G(xn-1), n = 1, 2, …, 其中G(x) = x – f(x)/f’(x)。為了研究牛頓法的收斂速率,我們需要假定f的二階導(dǎo)數(shù)在x*存在,這樣就保證了迭代函數(shù)G在x*處一階導(dǎo)數(shù)的存在性。求導(dǎo)數(shù)的商法則給出
G’(x*) = 1 – [f’(x*)2– f(x*)f’’(x*)]/f’(x*)2= f(x*)f’’(x*)/f’(x*)2= 0,
理由是f(x*) = 0。根據(jù)上面證明出的迭代收斂基本定理,存在以x*為中心的某個(gè)開(kāi)區(qū)間(x*-δ, x*+δ),使得只要初始點(diǎn)x0取之于它,牛頓法產(chǎn)生的迭代點(diǎn)數(shù)列{xn}不僅收斂到解x*,而且收斂速率是超線性的。事實(shí)上,在關(guān)于二階導(dǎo)數(shù)稍微更強(qiáng)一點(diǎn)的條件下,牛頓迭代是二階收斂的。
5
到目前為止講到的迭代收斂都是局部性的,那怎么擴(kuò)大保證收斂的初始點(diǎn)范圍呢?當(dāng)然,有不少途徑,其中一個(gè)十分簡(jiǎn)單,但對(duì)導(dǎo)數(shù)的要求卻頗為苛刻。既然簡(jiǎn)單,便適合在這里提及。應(yīng)用這個(gè)方法需滿足的條件是:將定義域區(qū)間[a, b]映到自身的迭代函數(shù)G有一個(gè)不動(dòng)點(diǎn)x*,且導(dǎo)數(shù)處處存在并滿足不等式|G’(x)| ≤ r,其中r為小于1的一個(gè)正數(shù)。
若條件成立,則對(duì)[a, b]中的任一初始點(diǎn)x0,由微分學(xué)里的拉格朗日中值定理,
G(x0) – x* = G(x0) – G(x*) = G’(c)(x0– x*),
其中c是位于x0和x*之間的一個(gè)數(shù)。這樣,
|G(x0) – x*| = | G’(c)(x0– x*)| = |G’(c)| |x0– x*| ≤ r |x0– x*|,
即G(x0)不僅位于[a, b],而且比x0更靠近x*。用歸納法,得到
|Gn(x0) – x*| ≤ rn|x0– x*| → 0。
因此,迭代點(diǎn)數(shù)列{Gn(x0)}收斂到x*。
如果我們?cè)倏匆淮巫C明就會(huì)發(fā)現(xiàn),施加于導(dǎo)數(shù)的要求事實(shí)上是為了實(shí)現(xiàn)不等式
|G(x) – G(x*)| ≤ r |x – x*|,任給定義域[a, b]中的點(diǎn)x。
只要這個(gè)不等式滿足,該迭代法對(duì)任意初始點(diǎn)都會(huì)收斂。然而該不等式并不要求G必須可導(dǎo),甚至也不需要G在x ≠ x*處連續(xù)。當(dāng)然,用于迭代的函數(shù)一般都是至少連續(xù)的,所以可以將上述不等式中的特殊點(diǎn)x*改為與x有同等地位的y,即
|G(x) – G(y)| ≤ r |x – y|,任給閉區(qū)間[a, b]中的點(diǎn)x和y,
其中G將[a, b]映到自身,且0 < r < 1。滿足這些條件的G稱為在區(qū)間[a, b]上是壓縮的。區(qū)間上的壓縮函數(shù)是處處連續(xù)的,但不一定處處可導(dǎo)。壓縮函數(shù)一定存在不動(dòng)點(diǎn),因?yàn)檫@是“壓縮”性質(zhì)的一個(gè)直接推論,證明的基本思想來(lái)自公比絕對(duì)值小于1的等比級(jí)數(shù)的收斂性和實(shí)數(shù)的完備性這兩個(gè)事實(shí),細(xì)說(shuō)如下:
在區(qū)間[a, b]中任取一點(diǎn)x0迭代G,得迭代點(diǎn)數(shù)列{xn},其中xn= G(xn-1) = Gn(x0)。則對(duì)任意正整數(shù)n有
|xn+1– xn| = |G(xn) – G(xn-1)| ≤ r |xn– xn-1|。
累次使用上述過(guò)程,就有 |xn+1– xn| ≤ rn|x1– x0|。從而對(duì)任意自然數(shù)p,由代數(shù)中的三角不等式及已得的不等式,
|xn+p– xn| ≤ |xn+1– xn| + |xn+2– xn+1| + … + |xn+p– xn+p-1|
≤ (1 + r + … + rp) |xn+1– xn| ≤ rn|x1– x0|/(1-r)。
既然limn → ∞r(nóng)n= 0,上式右端數(shù)列的極限為0,說(shuō)明{xn}是一個(gè)柯西數(shù)列,即雙下標(biāo)數(shù)列{|xm– xn|}當(dāng)m和n都趨于無(wú)窮大時(shí)的極限為0。因?yàn)樵趯?shí)數(shù)集內(nèi),任何柯西數(shù)列都是收斂的,故極限limn → ∞xn= x*存在。由于對(duì)所有n都有a ≤ xn≤ b,極限x*屬于[a, b];由于G處處連續(xù),x*是G的不動(dòng)點(diǎn)。如果在幾行之上的不等式中取p → ∞時(shí)的極限,我們還可以得出迭代到第n步后的“誤差估計(jì)”:
|x* – xn| ≤ rn|x1– x0|/(1-r),
這是計(jì)算數(shù)學(xué)家和工程師最愛(ài)看到的結(jié)果。
更進(jìn)一步,壓縮函數(shù)不僅有不動(dòng)點(diǎn),而且僅有一個(gè)不動(dòng)點(diǎn),因?yàn)槿绻邢喈惒粍?dòng)點(diǎn)x*和y*的話,則 |x*- y*| = |G(x*) – G(y*)| ≤ r |x* - y*|,因?yàn)閤* - y* ≠ 0及r < 1,這個(gè)不等式是不可能的。這個(gè)唯一性是許多其他著名的不動(dòng)點(diǎn)定理如“布勞威爾不動(dòng)點(diǎn)定理”所缺乏的,一維的布勞威爾不動(dòng)點(diǎn)定理本質(zhì)上就是微分學(xué)里的介值定理,它只要求函數(shù)連續(xù),所以少了一點(diǎn)限制條件,不動(dòng)點(diǎn)的個(gè)數(shù)就有可能大于一。這和家長(zhǎng)對(duì)孩子讀書(shū)的框框條條效果類似,限制越多,自由越少,子女今后的成就也就可能越少。
6
在數(shù)學(xué)上,“唯一性”是很重要的一條性質(zhì),因此壓縮函數(shù)的概念被抽象成泛函分析中所謂“距離空間”內(nèi)的“壓縮映射”。這門(mén)學(xué)科的集大成者、波蘭利沃夫數(shù)學(xué)學(xué)派的領(lǐng)袖巴拿赫 (Stefan Banach,1892-1945),在他進(jìn)入而立之年時(shí),提出了一個(gè)“壓縮映射定理”,現(xiàn)在該定理又以它的創(chuàng)立者命名為:巴拿赫不動(dòng)點(diǎn)定理。其專業(yè)性陳述是這樣的:
令(X, d)為一個(gè)完備的距離空間。若G: X → X為一壓縮映射,即存在小于1的一個(gè)數(shù)r,使得
d(G(x), G(y)) ≤ r d(x, y)
對(duì)X中所有的元素x和y都成立,則G有并只有一個(gè)不動(dòng)點(diǎn)x*,且從X中任一初始點(diǎn)x0出發(fā)的迭代點(diǎn)列{Gn(x0)}收斂到x*,其第n個(gè)迭代點(diǎn)的逼近上界為
d(x*, xn) ≤ rnd(x1, x0)/(1-r)。
這幾個(gè)抽象術(shù)語(yǔ)自然需要解釋,但只要發(fā)現(xiàn)上面定理的內(nèi)容,包括條件結(jié)論中的兩個(gè)不等式,與之前實(shí)變量的壓縮函數(shù)幾乎是一個(gè)模式,就會(huì)知道巴拿赫不動(dòng)點(diǎn)定理理解起來(lái)一點(diǎn)也不難。這也充分說(shuō)明任何抽象理論都源自簡(jiǎn)單的具體模型。
首先,什么是距離空間?“距離”是我們?nèi)粘I钪兴究找?jiàn)慣的幾何概念,這個(gè)量不能為負(fù),與度量距離的兩點(diǎn)次序無(wú)關(guān),而且兩點(diǎn)之間的距離為零當(dāng)且僅當(dāng)這兩點(diǎn)重合。距離還有一個(gè)關(guān)鍵的性質(zhì):北京和南京之間的距離肯定不大于北京和揚(yáng)州的距離加上揚(yáng)州和南京的距離。據(jù)說(shuō)這個(gè)被稱為“三角不等式”的性質(zhì)連聰明的狗都可透徹理解,否則它們一見(jiàn)主人就不會(huì)沿著人狗連線的方向直奔而來(lái)。顯而易見(jiàn),實(shí)數(shù)軸上兩點(diǎn)x和y之間的距離等于非負(fù)數(shù)|x – y|,用符號(hào)d(x, y)表示,其中“d”是距離的英文單詞distance的首字母。這樣我們可以將任意一個(gè)實(shí)數(shù)的集合A,比如一個(gè)區(qū)間,連同這個(gè)距離d組成的“二元組”(A, d)稱為距離空間。同樣,任意抽象集合X連同一個(gè)定義在其上的距離函數(shù)d,合起來(lái)的(X, d)就稱為一個(gè)距離空間,其中距離函數(shù)d滿足通常名詞距離對(duì)于我們已經(jīng)習(xí)以為常的如下性質(zhì):對(duì)X中任意的元素x, y, z, (1)d(x, y) ≥ 0且d(x, y) = 0當(dāng)且僅當(dāng)x = y; (2)d(x, y) = d(y, x);
(3)d(x, y) ≤ d(x, z) + d(z, y)。
其次,什么叫“完備”的距離空間?在微積分中用兩數(shù)x和y之間的通常距離|x – y|可以定義數(shù)列的收斂性:數(shù)列{xn}收斂到數(shù)x,假如距離數(shù)列{|xn– x|}當(dāng)n趨于無(wú)窮大時(shí)趨向于0。用完全同樣的方式可以定義距離空間(X, d)中元素序列的收斂性:我們說(shuō)X中的序列{xn}收斂到X的一個(gè)元素x,如果距離數(shù)列{d(xn, x)}當(dāng)n趨于無(wú)窮大時(shí)趨向于0。類似地,實(shí)數(shù)集合中的柯西數(shù)列也可直接推廣到距離空間中的序列:X中的序列{xn}被稱為是柯西序列,若雙指標(biāo)數(shù)列{d(xm, xn)} 當(dāng)m和n都趨于無(wú)窮大時(shí)趨向于0。我們知道在實(shí)數(shù)中任何柯西數(shù)列都有極限,但并非每一個(gè)距離空間都有這一性質(zhì),就像有理數(shù)組成的柯西數(shù)列不一定收斂到有理數(shù)那樣。如果一個(gè)距離空間(X, d)中的每一個(gè)柯西序列都有極限,那么(X, d)稱為是完備的。
既然閉區(qū)間是我們大學(xué)時(shí)代就熟悉的一個(gè)代表性完備距離空間,上面關(guān)于壓縮函數(shù)的不動(dòng)點(diǎn)定理的全部證明,只要將絕對(duì)值符號(hào)改為距離符號(hào),完全就可以移植為巴拿赫不動(dòng)點(diǎn)定理的證明,讀者可以自行寫(xiě)出這一證明。巴拿赫不動(dòng)點(diǎn)定理的一個(gè)標(biāo)準(zhǔn)應(yīng)用是常微分方程初值問(wèn)題解的存在唯一性定理證明,這時(shí)初值問(wèn)題的解被表達(dá)成將連續(xù)函數(shù)映成連續(xù)函數(shù)的某個(gè)積分算子的不動(dòng)點(diǎn),這里定義在某個(gè)閉區(qū)間[a, b]上的所有連續(xù)函數(shù)全體構(gòu)成一個(gè)距離空間,它的距離函數(shù)定義為d(f, g) = max{|f(x) – g(x)|: a ≤ x ≤ b}。
7
再回到牛頓迭代法,我們已知它總是局部收斂的,但如果初始點(diǎn)取得距離方程f(x) = 0的解x*太遠(yuǎn)了,那會(huì)有什么結(jié)果?牛頓法非局部的收斂性問(wèn)題是一門(mén)大學(xué)問(wèn),蘇聯(lián)數(shù)學(xué)家康特諾維奇 (Leonid Kantorovich,1912-1988) 于上世紀(jì)中葉發(fā)展了半局部收斂理論,在James M. Ortega和Werner C. Rheinboldt的那本名著中有詳細(xì)的討論。該理論的特點(diǎn)是,即便初始點(diǎn)沒(méi)能選在保證局部收斂的局部收斂域內(nèi),只要某些關(guān)鍵不等式被滿足,就能保證迭代點(diǎn)的序列收斂到方程的解。自然,許多初始點(diǎn)卻滿足不了這些條件,容易構(gòu)造一個(gè)例子,在許多點(diǎn)出發(fā)的牛頓迭代數(shù)列發(fā)散,如下圖所示。
事實(shí)上,讓牛頓法不收斂的那些初始點(diǎn)可以形成復(fù)雜無(wú)比的點(diǎn)集。上世紀(jì)80年代的某個(gè)學(xué)期,康奈爾大學(xué)數(shù)學(xué)教授哈伯德 (John Hubbard,1945-) 在法國(guó)一所大學(xué)度學(xué)術(shù)假,同時(shí)給一年級(jí)新生講授一門(mén)微積分課程。有次他靈光一閃,將自己從事的一部分事業(yè)——復(fù)離散動(dòng)力系統(tǒng)——和計(jì)算數(shù)學(xué)中古老的牛頓法聯(lián)系在一起。復(fù)離散動(dòng)力系統(tǒng),顧名思義,就是迭代復(fù)變函數(shù)看看最終走向如何。
中學(xué)生就已經(jīng)知道像 2 + 3 i這樣的復(fù)數(shù)是什么,這是幾百年前為了迎合求解二次方程 x2+ 1 = 0 的需要不得不創(chuàng)造出來(lái)的“虛無(wú)縹緲”之?dāng)?shù)。這“由實(shí)數(shù)到虛數(shù)”的一個(gè)大跳,解決了許多數(shù)學(xué)大問(wèn)題,例如代數(shù)基本定理——在復(fù)數(shù)范圍內(nèi),每個(gè)代數(shù)方程都有根。復(fù)動(dòng)力系統(tǒng)和分形幾何這兩門(mén)當(dāng)代學(xué)科緊密相連。
教授了太多次微積分課本里介紹的牛頓法,有點(diǎn)厭倦標(biāo)準(zhǔn)教法的哈伯德想換一換花樣。他把目光轉(zhuǎn)向在復(fù)數(shù)平面上用牛頓法解最簡(jiǎn)單的三次方程z3– 1 = 0,即算出1的三個(gè)立方根,分別是實(shí)數(shù)1和兩個(gè)互相共軛的復(fù)數(shù)(-1 + i√3)/2 和(-1 - i √3)/2。這三個(gè)根在復(fù)平面上形成一個(gè)等邊三角形。任取一個(gè)復(fù)數(shù)作為初始點(diǎn),他讓學(xué)生們看看牛頓法將引向三個(gè)根中的哪一個(gè)。這個(gè)創(chuàng)造性的習(xí)題給學(xué)生鋪下了一條發(fā)現(xiàn)之路!
自然,根據(jù)牛頓法的局部收斂性,當(dāng)初始點(diǎn)取得靠近三根之一時(shí),迭代點(diǎn)復(fù)數(shù)列將收斂到那個(gè)根。但是,哈伯德讓學(xué)生用計(jì)算機(jī)編程找出復(fù)平面上哪些初始點(diǎn)將走到第一個(gè)根,哪些點(diǎn)趨向于第二個(gè)根,哪些點(diǎn)會(huì)導(dǎo)致第三個(gè)根。這三類初始點(diǎn)分別用三種不同的顏色區(qū)別開(kāi)來(lái)。在粗糙的選點(diǎn)下,牛頓法迭代的最終性態(tài)果然如他所猜把平面分成三個(gè)扇形,但隨著選點(diǎn)越來(lái)越精細(xì),他和學(xué)生們發(fā)現(xiàn)這三個(gè)區(qū)域的分界線越來(lái)越不清楚:三種顏色互相纏繞,只要兩種顏色靠近一些,第三種顏色便乘虛而入,擠進(jìn)來(lái)夾在它們中間,就好像紅黃藍(lán)三股繩絞在一起彼此糾纏不清。這又引起一連串新的自相似的涌入,似乎沒(méi)有哪個(gè)點(diǎn)可以分開(kāi)任意兩種顏色。就這樣,美國(guó)數(shù)學(xué)教授哈伯德和修其課程的法國(guó)大學(xué)生們意外地發(fā)現(xiàn)了已經(jīng)廣泛使用了幾百年的牛頓法所制造的分形圖。
當(dāng)然,這個(gè)漂亮的牛頓分形圖令研究動(dòng)力系統(tǒng)的學(xué)者興高采烈,卻令冀望算法收斂的計(jì)算數(shù)學(xué)家愁眉苦臉,因?yàn)樗麄兛吹郊幢阆衽nD法這樣優(yōu)秀的迭代法,不產(chǎn)生收斂迭代序列的那些初始點(diǎn),看上去是如此的復(fù)雜!從而,在計(jì)算數(shù)學(xué)領(lǐng)域,迭代法的收斂性一直是引人注目的課題。
審核編輯:劉清
-
壓縮機(jī)
+關(guān)注
關(guān)注
11文章
680瀏覽量
79498 -
微積分
+關(guān)注
關(guān)注
1文章
26瀏覽量
8855
原文標(biāo)題:計(jì)算數(shù)學(xué)中的函數(shù)迭代
文章出處:【微信號(hào):bdtdsj,微信公眾號(hào):中科院半導(dǎo)體所】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
在開(kāi)源的hbird-e-sdk中,怎么用軟件實(shí)現(xiàn)三角函數(shù)的計(jì)算,有沒(méi)有數(shù)學(xué)函數(shù)庫(kù)可以調(diào)用?
用MATLAB進(jìn)行函數(shù)迭代
應(yīng)當(dāng)用多少位來(lái)表示測(cè)量或計(jì)算數(shù)據(jù)?
一種潮流計(jì)算數(shù)學(xué)模型及其潮流控制的模擬方法
如何使用工具鏈中自帶的數(shù)學(xué)函數(shù)呢
隱函數(shù)、方程求根、不動(dòng)點(diǎn)和迭代
工程電磁場(chǎng)數(shù)值計(jì)算數(shù)值分析的數(shù)值基礎(chǔ)
![工程電磁場(chǎng)數(shù)值<b class='flag-5'>計(jì)算數(shù)</b>值分析的數(shù)值基礎(chǔ)](https://file.elecfans.com/web2/M00/49/C1/pYYBAGKhvFmARJpfAAAs1KhcuFs709.png)
FPGA數(shù)學(xué)基礎(chǔ)分析及與CORDIC算法計(jì)算方式對(duì)比
![FPGA<b class='flag-5'>數(shù)學(xué)</b>基礎(chǔ)分析及與CORDIC算法<b class='flag-5'>計(jì)算</b>方式對(duì)比](https://file1.elecfans.com//web2/M00/A6/EB/wKgZomUMQUWAcMTTAAAS4oJ27Uo098.jpg)
進(jìn)化算法在歷史計(jì)算數(shù)據(jù)中應(yīng)用
簡(jiǎn)單的數(shù)學(xué)運(yùn)算計(jì)算數(shù)學(xué)函數(shù)的方法CORDIC的詳細(xì)資料概述
![簡(jiǎn)單的<b class='flag-5'>數(shù)學(xué)運(yùn)算計(jì)算數(shù)學(xué)</b><b class='flag-5'>函數(shù)</b>的方法CORDIC的詳細(xì)資料概述](https://file.elecfans.com/web1/M00/51/ED/pIYBAFsPahqAUm3xAABWW_sdRVE545.png)
計(jì)算機(jī)數(shù)學(xué)教程之《計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)》電子教材計(jì)算機(jī)的必備數(shù)學(xué)基礎(chǔ)免費(fèi)下載
計(jì)算數(shù)據(jù)是通過(guò)什么輸入的?
數(shù)學(xué)建模中的常用算法詳細(xì)介紹
![<b class='flag-5'>數(shù)學(xué)</b>建模<b class='flag-5'>中</b>的常用算法詳細(xì)<b class='flag-5'>介紹</b>](https://file.elecfans.com/web1/M00/C1/23/o4YBAF8VOVqAXIsHAANUuKHaEx0808.png)
評(píng)論