第２６卷第１ １期 ２００６年１１月 计算机应用
Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ Ｖ０Ｉ．２６ Ｎｏ．１ｌ
ＮＯＶ．２ｏ０６
文章编号：１００１—９０８１（２００６）１１—２７０１—０３
基于函数迭代系统的３一Ｄ分形插值算法
王梦，金文标
（重庆邮电大学计算机图形图像研究所，重庆４０００６５）
（ｃｑｗｍｅｎｇ＠ｌ６３．ｃｏｒｎ；ｊｉｎｗｂ＠ｃｑｕｐｔ．ｅｄｕ．ｃｎ） 摘要：提出了一种新的分形插值算法，通过矩形剖分上的采样数据点构建分形插值曲面。该算
法保证分形插值时的边界连续性，而且对于初始数据集没有任何对称性限制。所构建的分形插值曲
面整体上保持原始数据的主要特征，局部上具备自相似的特点。实验结果表明算法的有效性和低时
间复杂度，有利于分形插值的实际应用。
关键词：分形插值；迭代函数系统；矩形剖分；对称性
中图分类号：ＴＰ３１７．４ 文献标识码：Ａ
Ａ ３一Ｄ ｆｒａｃｔａｌ ｉｎｔｅｒｐｏｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｔｅｒａｔｅｄ ｆｕｎｃｔｉｏｎ ｓｙｓｔｅｍ
ＷＡＮＧ Ｍｅｎｇ，ＪＩＮ Ｗｅｎ ｂｉａｏ
（１ｍｔｉｔ￣ｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｃｈｏｎｇｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｐｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ ４０００６５，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｍｅｔｈｏｄ ｗａｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｃｏｎｓｔｒｕｃｔｉｎｇ ｆｒａｃｔａｌ ｉｎｔｅｒｐｏｌａｔｉｏｎ ｓｕｒｆａｃｅｓ ｔｈｒｏｕｇｈ ｐｏｉｎｔｓ ｓａｍｐｌｅｄ ｏｎ ｒｅｃｔａｎｇｕｌａｒ ｌａｔｔｉｃｅｓ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｇｕａｒａｎｔｅｅｄ ｔｈｅ ｂｏｕｎｄａｒｙ ｃｏｎｔｉｎｕｉｔｙ ａｎｄ ｃａｎｃｅｌｅｄ ｓｙｍｍｅｔｒｙ ｒｅｓｔｒｉｃｔｉｏｎ ｏｎ ｔｈｅ ｉｎｉｔｉａｌ ｄａｔａ ｓｅｔ．
迭代方法也称为滚动方法。Bai是一个过程，其中变量Du的旧值用于重现新值。
迭代算法是解决计算机问题的基本方法。它利用了运算速度快的特点，并且适合重复操作，因此计算机可以重复执行一组指令（或某些步骤）。每次执行指令组（或这些步骤）时，都会从变量的原始值中得出一个新值。迭代方法分为精确迭代和近似迭代。
典型的迭代方法（例如二分法和牛顿迭代）属于近似迭代。
扩展数据：
对于区间[a，b]和f（a）·f（b）<0上的连续函数y=f（x），通过连续除以函数f（x）零点所在的区间，间隔的两个端点逐渐接近零点，然后获得零点的近似值称为二分法。
令[a，b]为R的封闭区间。连续二等分方法将创建以下区间序列（[an，BN]），如下所示：A0=a，B0=B，并且对于任何自然数n，[an+1，BN+1]等于[an，cn]或等于[cn，BN]，其中CN表示[an，BN]的中点。
方法介绍
迭代法是一类利用递推公式或循环算法通过构造序列来求问题近似解的方法。例如，对非线性方程，利用递推关系式，从开始依次计算，来逼近方程的根的方法，若仅与有关，即，则称此迭代法为单步迭代法，一般称为多步迭代法；对于线性方程组，由关系从开始依次计算来过近方程的解的方法。若对某一正整数，当时，与k无关，称该迭代法为定常迭代法，否则称之为非定常迭代法。称所构造的序列为迭代序列。
设问题的解空间为
n} , 2, 1,i , X x|) x, , x,x{(Aiin21
● 形式迭代算法
求一个解的形式迭代算法：
算法 BACKTRACKITER1
输入:集合X1 , X2 ,…, Xn 的清楚的或隐含的描述。
输出：解向量(x1, x2,…, xn) (一个解)。若无解，则输出“no
solution”。
flag=false //用flag标记问题是否有解。
k=1
x1=X1中第一个元素的前一个元素
while k>=1 and not flag
while Xk未被穷举 and not flag
xk= Xk中的下一个元素
if (x1, x2,…, xk)满足解的约束条件 then
if k=n then flag=true //(x1, x2,…, xn)是一个解
else //(x1, x2,…, xk)是部分解
k=k+1
xk= Xk中第一个元素的前一个元素
end if
end if //否则，剪枝 end while
k=k-1 //回溯
end while
if flag then output (x1, x2,…, xn)
//输出一个解
else output “no solution” //输出无解
end BACKTRACKITER1
求所有解的形式迭代算法：
算法 BACKTRACKITER2
输入：集合X1 , X2 ,…, Xn 的清楚的或隐含的描述。
输出：所有解(x1, x2,…, xn)。若无解，则输出“no solution”。
最优化问题的算法迭代格式
最优化问题的算法迭代格式
最优化问题是指在一定的条件下，寻找使某个目标函数取得极值（最大值或最小值）的变量取值。解决最优化问题的方法有很多种，其中较为常见的是迭代法。本文将介绍几种常用的最优化问题迭代算法及其格式。
一、梯度下降法
梯度下降法是一种基于负梯度方向进行搜索的迭代算法，它通过不断地沿着目标函数的负梯度方向进行搜索，逐步接近极值点。该方法具有收敛速度快、易于实现等优点，在许多应用领域中被广泛使用。
1. 算法描述
对于目标函数 $f(x)$，初始点 $x_0$ 和学习率 $\alpha$，梯度下降算法可以描述为以下步骤：
- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；
- 更新当前点 $x_k$ 为 $x_{k+1}=x_k-\alpha\nabla f(x_k)$； - 如果满足停止条件，则输出结果；否则返回第 1 步。
2. 算法特点
- 沿着负梯度方向进行搜索，能够快速收敛；
- 学习率的选择对算法效果有重要影响；
- 可能会陷入局部极小值。
二、共轭梯度法
共轭梯度法是一种基于线性方程组求解的迭代算法，它通过不断地搜索与当前搜索方向共轭的新搜索方向，并在该方向上进行一维搜索，逐步接近极值点。该方法具有收敛速度快、内存占用少等优点，在大规模问题中被广泛使用。
1. 算法描述
对于目标函数 $f(x)$，初始点 $x_0$ 和初始搜索方向 $d_0$，共轭梯度算法可以描述为以下步骤：
- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；
- 如果满足停止条件，则输出结果；否则进行下一步；
- 计算当前搜索方向 $d_k$； - 在当前搜索方向上进行一维搜索，得到最优步长 $\alpha_k$；
- 更新当前点为 $x_{k+1}=x_k+\alpha_k d_k$；
- 计算新的搜索方向 $d_{k+1}$；
- 返回第 2 步。
