第4讲-3 分形插值曲线

第六章分形插值曲线分形几何实际上是大自然几何，分形插值函数当然可以去描绘大自然中那些美不胜收的场景，如险峻的华山、妖媚的鲜花、甚至鬼斧神工的云南石林等等．不仅如此，分形插值函数也为拟合经验数据提供了一个新的途径虽然它不足以“最小二乘”去拟合(射流，火箭等)喷嘴处的时间温度曲线，也如同传统几何一样难以分析由仪器读出来的脑电压，但它确能用于拟合下面的经验数据，即Hausdorff度量空间中的数据，原因是分形插值函数的图形被看成是紧的。分形插值函数与初等函数一样也具有其本身的几何特征，它能科学地用“公式”来表示，也能快速地被计算出来．主要的差别在于它的分形特征，如它有非整的维数，它是针对集合而非针对点的．6.1分形插值函数6.1.1分形插值原理传统的数学插值函数或曲线拟合函数都是用一组基函数的线性组合来表示的，通常用的基函数为多项式，有理函数或三角函数等初等函数，而分形插值函数这里是用迭代函数系统来实现的．定义6.7一个数据集合是形如NiRyxii,2,1,0;),(2的点集，其中Nxxxx210(6.2.1)对应于这个数据集合的插值函数是一个连续函数RxxfN],[:0使得Niyxfii,,2,1,0,)((6.2.2)点2),(Ryxii称为插值点，函数f内插该数据且f的图形穿过插值点．例6.1函数xxg1)(显然是数据集{(0，1)，(1，2)}的插值函数，那么是否可用一个迭代函数系统来做插值呢?考虑IFS212,;WWR,其中W1,210100121yxyxW2,021100121yxyx令G为其吸引子，则由]1,0[x，得1()0,12Wx,2()12,1Wx由[1,2]y得1()1,32Wy,2()3/2,2Wy,于是G是联结(0，1)和(1，2)的曲线，换言之，G是区间[0，1]上的插值函数f的图像．例6.2设NiRyxii,2,1,0;),(2是数据集，RxxfN],[:0是插值于该数据集的连续函数，且在每个小区间),,2,1(,1Nixxii上是直线段，形如Nixxxxxxxyyyxfiiiiiiii,,1,,),()(11111.一般我们称这样的函数f(x)为分段线性函数(见图6.4)．注意到第三章提到的随机中点位移法能把一条线段变成一条分形曲线，因此该方法就能对分段线性函数进行分形插值，只是其插出来的函数图形因其随机性而不易控制函数图形的凹凸性．从图6.4中的图像出发进行分形插值，可以得到一条分形曲线．实际上它就是IFSN,,;212的吸引子G，其中NnfeyxcayxWnnnnn,,2,1,10不难算出（令0xxlN）)(11nnnxxla)(11nnnyylc)(101nnNnxxxxleNnyxyxlfnnNn,,2,1),(101并且G是2R上的非空紧集，满足：)(1GWGnNn上面两例说明一个IFS可作为一个插值变换。但分形插值不是一般的数据插值，它插值得到的曲线必须是一条分形曲线。换言之，插值曲线的任一段都必须(如果需要的话)是一条无处可微曲线。由分形的自相似性特征，加上nWW的任意次迭代，这是可以做到的。设函数序列01))(()(nnnxTfxf收敛到映射T的一个不动点，则图6.5显示的就是这种分形插值原理。图中A，B，C是插值数据的三个点，如果把)(0xf表示为AC线段，则)(1xf得到的就是两线段的分段插值函数，)(2xf则是图右上方轮廓线ADBEC的四条线段，)(3xf是图上第二排左边轮廓线的八条线段……另外，ADB，BEC与原ABC具有某种相似性，且每次迭代后得到的一系列双倍三角形都与原来那个三角形具有某种相似性。折线ABC是两线段曲线，它应有两个仿射变换W1和W2去分别映射线段AB和BC，得到线段W1（AB）=AD，W1（BC）=BE，W2（AB）=DB，W2（BC）=EC，设W＝W1UW2，则)(limABCWnn就是图中曲线的轮廓。一般说来，对于数据集Niyxii,,1,0:),(应有N个仿射变换，见图6.6。图中K是1FS的吸引子，且)()()()(4321KWKWKWKWK6.1.2分形插值方法令数据集Niyxii,,1,0:),(给定，下面推导如何构造出R2上的IFS，它的吸引子G是内插数据的连续函数RxxfN],[:0的图像考虑IFS},,2,1,:{2NnWRn，其中Ｗn是具有如下形式的仿射变换：,0nnnnnnfeyxdcayxW(6.2.3)且1100nnnyxyxW和nnNNnyxyxW(6.2.4)式(6.2.3)中0nb是保证了各小区间函数的不交迭。式(6.2.4)具体写为nnNnNnnnnnnnNnnnnyfydxcyfydxcxexaxexa10010例6.3求一个形如｛R2;W1,W2｝，其中W1、W2是R2中的仿射变换，其吸引子是插值于｛(0，0)，(1，1)，(2，4)｝的分形曲线。解：将数据代入式(6.2.6)，得111112222212,0,1/22,0,1/2,1,3/22,1aecdfaecdf其中，120,1dd为任意实数．但由于原数据恰恰经过2yx曲线。因此如令nnnnnfxdxcexa22)(，n＝1，2，并将计算到的数据代入，便得到d1＝d2＝41，此时cl＝0，c2＝1．这时IFS的吸引子是二次函数。这正是一个IFS的吸引子也有不是分形的例子。nd虽然是个自由参量，但其对分形插值的结果影响甚大。nd的取值不同直接影响到插值结果的形态、复杂程度及分形维数。定理6.6设N为大于1的正整数，{R2;NnWn,,2,1,}是伴随于数据集Nnyxnn,,1,0:),(的IFS，垂直定比因子nd满足01,1,2,,ndnN，则存在一个R2上等价于Euclid的度量d，使得这个IFS对应于d是压缩的，特别地，存在唯一一个非空紧集GR2，使得01(){,()):[,]}NnNnGWGxfxxxx式中RxxfN],[:0是连续函数且满足Nnyxfnn,,1,0,)(证明：定义R2上的一个度量d为.0,)),(),,((21212211yyxxyxyxd显然当1时即为Manhattan度量，它与Euclid度量等价。令n{1,2,…,N},nnne,c,a和fn如方程式（6.2.6）所示，则21212121212121212221112211)()()()),(),,(()),(),,((yydxxcayydxxcxxayydxxcxxafydxcexafydxcexadyxWyxWdnnnnnnnnnnnnnnnnnnnnn注意到1)2(,111nnnndNxxLa及，假如021Nccc，可选1,并令max{,}1nnnkad,有)),(),,(()),(),,((22112211yxyxkdyxWyxWdnn否则可选择,},,2,1:2max{},,2,1:1min{NncNnann得到)),(),,((},max{)()),(),,((2211212121212211yxyxdyyxxyydxxcayxWyxWdnnnnn式中,1},,2,1:max{1)},,2,1:max{1(21NndNnann这证明确实存在一个使Wn对于这个d来说是压缩映射，从而由压缩映射定理，存在该IFS的一个吸引子，使得).(1GWGnNn为了证明定理中的第二个等式，可设F表示连续函数RxxfN],[:0边界条件NNyxfyxf)(,)(00的集合，并定义F上的度量为,,]},[:)()(max{),(0Fgf，xxxxgxfgfdN则),(dF是一个完备的度量空间．令nnnnfeca和,,仍如方程式(6.2.6)所示，再定义一个映射T：nnnnnfxlfdxlcxTf))(()())((11],[0Nxxx,n=1,2,…,N,(6.2.7)其中],[],[:10nnnnxxxxl是一个可逆变换，形如nnnexaxl)(不难验证nNnnnnnnxxlxxlaexxl)(,)(,/)()(101由于f,nl和1nl都是连续函数，所以Tf也在),(1nnxx上连续,在内插点121,,,Nxxx上，))((nxTf有两种定义1111111))(()())((nnnnnnnnfxlfdxlcxTf(6.2.8)或nnnnnnnnfxlfdxlcxTf))(()())((11因Nnnnnxxlxxl)(,)(1011,故有1,,2,1,))((NnyfydxcxTfnnNnNnn或1,,2,1,))((10101NnyfydxcxTfnnnnn在边界上1011101110))(()())((yxlfdxlcxTf010101)(yyxfdxcNNNNNNNyyxfdxcxTf)())((这里,计算))((0xTf时用了式(6.2.8),计算))((NxTf时用了式(6.2.9).上面结果表明,算子T确实把F映射到了自身且满足插值条件。再者,对任意f,Fg,Nn,,2,1，当nnxxx,1时，))(())(())(())((11xlgxlfdxTgxTfnnn),(gfddn令1maxnd则),(),(gfdTgTfd这说明T是压缩的。由于),(dF是完备度量空间，则由压缩映射定理，在F上存在惟一不动点，亦即存在函数Ff,使],[),())((0NxxxxfxTf这个f可通过T的迭代得到ffTnn)(lim0前已证NnyxTfnn,,2,1,))((,所以该f经过所有插值数据点．设T的不动点为G~(即f的图像),并且注意到xexalnnn)(1,所以NnxxxfxfdxcexaTfNnnnnn,,2,1],,[,)())((0(6.2.10)这隐含着NnnGWG1)~(~但因G~是2R上的非空紧集且由非空紧集G的唯一性，最终得到GG~式(6.2.10)表明，映射T等价于作为分形插值的迭代函数系统IFS．定义6.8表示定理6.6中IFS图像的函数)(xf称为伴随于数据集Niyxii,,1,0:),(的分形插值函数．定理6.6证明中引入的映射Tf的迭代过程就是图6.6所展示的))(()(1xTfxfnn．初始函数)(0xf是条直线段，序列)(1xfn最终收敛到分形插值函数)(xf，后者即是映射T的不动点，整幅图像)(xf(图6.6所显示的最终轮廓)可以看作是带凝聚集的IFS的吸引子，这个凝聚集就是)(0xf的图像．所以归根结底，我们是用映射T构造了分形插值函数，这其中包含了两层意思：(1)我们可以把IFS的理论应用到分形插值函数，特别是用IFS的算法去算分形插值函数；用拼贴定理去找出分形插值函数与给定数据的近似程度，当然是用Hausdorf度量去讨论插值的精度。(2)把分形插值函数看作是仿射变换的吸引子，这就提供了描述一类重要函数和集合的普通语言．定义6.9(双曲IFS)在一个带有数据集的迭代函数系统IFSNnWRn,,1,