论文摘要
在非线性实代数系统的高效能算法研究领域中,求解非线性多项式方程组是一类十分重要的问题.本文针对求解非线性多项式方程组的混合算法做了深入研究。文中首次将结式运算与基于slope形式的Hansen-Sengupta算法相结合,建立了新的求解非线性多项式方程组的混合算法,并从理论上证明了该算法的正确性,说明了算法的终止性.通过数值实验说明了混合算法的高效率.本文还将所建立的混合算法用于解决实代数几何中的实际问题.在实代数几何领域,许多问题都可以被转化为代数不等式的证明.特别地,构造性的几何定理往往被转化为根式不等式的证明.不等式的证明一直都是一个困难的课题,主要原因在于其相关算法依赖于实代数与实几何,其计算复杂度会随着维数的增加而快速增长.本文针对组合几何中一个不等式猜想的证明,建立了半机械化算法.同时针对根式不等式证明建立了基于数值和符号算法的混合算法.本文的创新点可以归结如下:●基于多项式方程组根的界,改进并实现了求解非线性多项式系统的subdivision数值算法,同时建立和证明了隔离实根的有效数字表达与隔离区间的宽度精度之间的关系●基于符号算法、数值算法等,建立了求解非线性多项式方程组的混合算法（HybridMethod算法）.分析给出了混合算法以及全部子算法的正确性的理论证明并说明了算法的终止性.在Maple以及Visual C++9.0平台上编写了混合算法的通用程序.通过文献中的若干例子以及随机生成的稠密、稀疏多项式算例验证了算法的正确性和有效性.实验结果表明,混合算法能够有效提高求解非线性多项式方程组的效率,为后续计算奠定了基础.●在实代数几何中,求代数剖分及其样本点的算法是一个基本问题,它对于求解和证明许多与多项式方程、不等式等相关的问题都起到了重要的作用,同时还能够给出实代数函数具体解的形式.本文基于临界点原理以及所建立的混合算法等,建立了寻找平面剖分样本点的ISP算法.在Maple平台上建立了相应的通用程序.利用该算法与经典的PCAD算法对若干算例进行了实验,结果表明对于同等条件下ISP算法能够有效地减少冗余样本点的个数,提高效率.●研究了组合几何中一个与Heilbronn三角形问题有关的全局最优化问题.由于算法的复杂度等原因,直接使用机械化算法较为困难.文中首先将问题转化为一个半代数集,利用保面积仿射变换和微小扰动等方法减少系统中的自由变量以及多余的不等式条件,简化了问题.然后利用机械化算法证明了猜想在n=8时的正确性,并对n=9时的情形进行了探讨.●构造性几何定理往往能够转化为一类含根式不等式的证明.目前关于这方面的工作常见的方法有量词消去（QE）法以及降维算法.本文基于符号和数值算法,建立了一个证明根式不等式的混合算法.该算法分为数值算法（Numeric）和符号算法（symbolic）两部分.Numeric算法通过Hansen-Sengupta算子寻找有限多的样本点,然后通过区间运算来逐一验证这些样本点处不等式是否成立.如果在此过程中,Numeric算法失败,那么转而使用符号算法.最后,对全文的工作进行了总结,在现有工作的基础上对未来工作进行了展望,期望能够将本文所建立的算法以及结果加以推广,应用到更广阔的领域处理更多的问题.
论文目录
相关论文文献
标签：非线性多项式方程组论文; 实根隔离论文; 区间估值论文; 算法论文; 平面代数剖分论文; 三角形论文; 根式不等式论文;