不動點演演算法

又稱固定點演演算法。所謂不動點，是指將一個給定的區域A,經某種變換ƒ(x),映射到A時，使得成立的那種點。最早出現的不動點理論是布勞威爾定理(1912)：設A為Rn中的一緊緻凸集, ƒ為將A映射到A的一連續函數，則在A中至少存在一點x，使得。其後，角谷靜夫於1941年將此定理推廣到點到集映射上去。設對每一 ，ƒ(x)為A的一子集。若ƒ(x)具有性質：對A上的任一收斂序列，若 且，則有如此的ƒ(x)稱為在A上半連續，角谷靜夫定理：設A為Rn中的一緊緻凸集，對於任何，若ƒ(x)為A的一非空凸集，且ƒ(x)在A上為上半連續，則必存在,使。J.P.紹德爾和J.勒雷又將布勞威爾定理推廣到巴拿赫空間。

不動點定理在代數方程、微分方程、積分方程、數理經濟學等學科中皆有廣泛的應用。例如，關於代數方程的基本定理，要證明必有一根，只須證明在適當大的圓 內函數有一不動點即可；在運籌學中，不動點定理的用途至少有二：一為對策論中用來證明非合作對策的平衡點的存在和求出平衡點；一為數學規劃中用來尋求數學規劃的最優解。對於一個給定的凸規劃問題：，在此,ƒ和皆為中的凸函數。通過適當定義一個函數φ,可以證明：若上述問題的可行區域非空，則φ的不動點即為該問題的解。

在1964年以前，所有不動點定理的證明都是存在性的證明，即只證明有此種點存在。1964年，C.E.萊姆基和 J.T.Jr.豪森對雙矩陣對策的平衡點提出了一個構造性證明。1967年，H.斯卡夫將此證法應用到數學規劃中去。其後，不動點定理的構造性證明有了大的發展和改進。

H.斯卡夫的證明是基於一種所謂本原集，後來的各種發展皆基於某種意義下的三角剖分。現以n 維單純形Sn為例來說明這一概念，在此,。

對每一i, 將區間依次分為m1,m2…等分，是給定的一列正整數。

對於固定的i,過分點依次作平行於的平面。這些平面將Sn分成若干同樣大小的n維三角形。它們的全體作成的集 Gi,稱為Sn的一三角剖分。設ƒ(x)為 的一連續函數，

定義 。

由於ƒ(x)和x皆在Sn上，若有則顯然有,即x為ƒ(x)的一不動點。

對每一點賦與標號。由著名的施佩納引理，在Gi中必存在一三角形σi，它的n個頂點yi(k)的標號分別為使得(時,收斂成一個點,。因 的標號為,因而即x為所求的不動點。因此，求 的不動點問題就化為求 的問題。為了計算上的效果，除了上述的標號法之外，還有標準整數標號法、向量標號法等等。關於如何求σi，有變維演演算法、三明治法、同倫演演算法、變維重始法等等，通過適當定義，可將上之Sn改為Rn或Rn中之一凸集。求一凸函數在一凸集上的極值問題也可化為求不動點問題。一般說來，這條途徑適用於維數不高但問題中出現的函數較為複雜的情況。

參考書目

A.J.J.TalmanVariable Dimension Fixed Point Algorithms and Triangulations, Mathematisch Centrum, Amsterdam, 1980.