本站原创
摘 要：为了求得非线性方程组所有精确解，根据元胞自动机的特点构造了求解非线性方程组的全局收敛算法。在该算法中，将非线性方程组解的理论搜索空间划分为离散搜索空间，将离散搜索空间定义为元胞空间；离散搜索空间的每个点就是一个元胞，而一个元胞对应着非线性方程组的一个试探解；元胞的状态由其空间位置及位置修正量构成。将元胞空间划分为若干个非空子集，所有元胞的状态从一个非空子集转移到另一个非空子集的状态演化过程实现了元胞空间对理论搜索空间的搜索。在元胞状态演化过程中，元胞从一个状态转移到另一个状态的状态转移概率可以计算出来；元胞演化过程中的每个状态对应于有限Markov链上的一个状态。利用可归约随机矩阵的稳定性条件证明了该算法具有全局收敛性。仿真实例表明该算法是高效的。
关键词：非线性方程组；元胞自动机；全局收敛性
：A
Cellular automata method for solving nonlinear systems of
equations and its global convergence proof
LU Qiu-qin*， YANG Shao-min， HUANG Guang-qiu
School of Management， Xi’an University of Architecture and Technology， Xi’an Shaanxi 710055， China
Abstract：
To get all the accurate solutions to Nonlinear Systems of Equations （NSE）， the algorithm with global convergence was constructed for solving NSE based on the characteristics of Cellular Automata （CA）. In the algorithm， the theoretical search space of NSE was d
英文关键词 Key words：
Nonlinear System of Equation （NSE）； Cellular Automata （CA）； global convergence
0 引言
非线性方程组求解一直是工程应用中的难点问题。多年来，人们对非线性方程组的求解进行了大量研究，提出了许多有用的算法，如符号计算法、消元法、数值迭代法[2-3]和进化计算方法[4-6]等。数值迭代法是最常用的方法之一，但数值迭代法均以Newton-Raphson迭代法（NR法）为基础[1-3]。NR法具有局部二阶收敛性，且收敛速较快。但NR法有一些弱点[2-3]：NR法对初值的选择较为敏感，要给出收敛到精确解的初值目前还没有理论指导；每步迭代都要计算Jacobi矩阵并求解线性方程组，工作量较大；当Jacobi矩阵奇异或接近奇异时，NR法的计算将无法进行。近年来，进化计算方法已应用于非线性方程组的求解，并取得了较好的成效。进化计算方法包括遗传算法、粒子群算法、鱼群算法、蚁群算法和遗传退火算法等。用这些方法求解非线性方程组的共同点是将非线性方程组转化为无约束最优化问题[4～6]。
元胞自动机（Cellular Automata，CA）模型[7]自1951年冯·诺伊曼提出以来，得到了广泛关注，对CA算法的研究与应用已经渗透到多个应用领域[8]。由于非线性方程组的求解过程是一个不断进行简单重复迭代的过程，而CA作为一种数学上离散的模型系统，用于自组织系统演变过程的研究具有天然的优势。因此，将CA用于非线性方程组的求解是可行的。作为一种新型的求解非线性方程组的算法，CA一方面具有对非线性方程组解的初值和求解参数选择不敏感、不需要非线性方程可微、求解算法鲁棒性强和易实现等诸多优点；另一方面，本文已证明CA用于非线性方程组的求解具有全局收敛性，这是很多进化算法无法拥有的优点。因此，本文提出的基于CA的非线性方程组求解算法，无论非线性方程组的初值、求解过程参数如何选择，均可在理论上确保求解过程收敛到非线性方程组的所有精确解上。
关键词：非线性方程组；元胞自动机；全局收敛性
：A
Cellular automata method for solving nonlinear systems of
equations and its global convergence proof
LU Qiu-qin*， YANG Shao-min， HUANG Guang-qiu
School of Management， Xi’an University of Architecture and Technology， Xi’an Shaanxi 710055， China
Abstract：
To get all the accurate solutions to Nonlinear Systems of Equations （NSE）， the algorithm with global convergence was constructed for solving NSE based on the characteristics of Cellular Automata （CA）. In the algorithm， the theoretical search space of NSE was d
摘自：毕业论文的格式www.udooo.com
ivided into the discrete space， the discrete space was defined as the cellular space； each point in the discrete space was a cell in the cellular space， and each cell was a trial solution of NSE； a cellular state consisted of position and increment of position. The cellular space was divided into many nonempty subsets， and states evolution of all cells from one nonempty subset to another realized the search of the cellular space on the theoretical search space. During evolution process of all cells， each cells transition probability from one position to any another position could be simply calculated； each state of cells during evolution corresponded to a state of a finite Markov chain. The stability condition of a reducible stochastic matrix was used to prove the global convergence of the algorithm. The case study shows that the algorithm is efficient.英文关键词 Key words：
Nonlinear System of Equation （NSE）； Cellular Automata （CA）； global convergence
0 引言
非线性方程组求解一直是工程应用中的难点问题。多年来，人们对非线性方程组的求解进行了大量研究，提出了许多有用的算法，如符号计算法、消元法、数值迭代法[2-3]和进化计算方法[4-6]等。数值迭代法是最常用的方法之一，但数值迭代法均以Newton-Raphson迭代法（NR法）为基础[1-3]。NR法具有局部二阶收敛性，且收敛速较快。但NR法有一些弱点[2-3]：NR法对初值的选择较为敏感，要给出收敛到精确解的初值目前还没有理论指导；每步迭代都要计算Jacobi矩阵并求解线性方程组，工作量较大；当Jacobi矩阵奇异或接近奇异时，NR法的计算将无法进行。近年来，进化计算方法已应用于非线性方程组的求解，并取得了较好的成效。进化计算方法包括遗传算法、粒子群算法、鱼群算法、蚁群算法和遗传退火算法等。用这些方法求解非线性方程组的共同点是将非线性方程组转化为无约束最优化问题[4～6]。
元胞自动机（Cellular Automata，CA）模型[7]自1951年冯·诺伊曼提出以来，得到了广泛关注，对CA算法的研究与应用已经渗透到多个应用领域[8]。由于非线性方程组的求解过程是一个不断进行简单重复迭代的过程，而CA作为一种数学上离散的模型系统，用于自组织系统演变过程的研究具有天然的优势。因此，将CA用于非线性方程组的求解是可行的。作为一种新型的求解非线性方程组的算法，CA一方面具有对非线性方程组解的初值和求解参数选择不敏感、不需要非线性方程可微、求解算法鲁棒性强和易实现等诸多优点；另一方面，本文已证明CA用于非线性方程组的求解具有全局收敛性，这是很多进化算法无法拥有的优点。因此，本文提出的基于CA的非线性方程组求解算法，无论非线性方程组的初值、求解过程参数如何选择，均可在理论上确保求解过程收敛到非线性方程组的所有精确解上。