Research on Numerical Methods for Solving Nonlinear Systems and Their Applications

本文首先提出了求解非线性电路的一种有效同伦方法，并证明了其对描述非线性电路的修正节点方程的全局收敛性。该方法能够有效地求解10000元以上双极模拟集成电路，并具有全局收敛性的理论保证。我们进一步利用新的同伦函数和有效的初始解算法，提出了一种改进的同伦方法，其效率比上述方法高得多。接下来，我们提出了一种利用对偶单纯形法求分段线性电阻电路所有解的有效算法。使用该算法，在实际计算时间内，可以找到所有大规模问题的解，包括变量数为2000和线性区域数为1000^{2000}的问题，这是该领域的一个显着发展。我们还提出了基于spice的路径跟踪电路求解非线性问题的数值方法。路径跟踪电路（PFC）是解决电路模拟器SPICE上的非线性问题的电路。在PFC的方法中，数值方法的公式用电路来描述，用SPICE来求解。使用PFC，无需编程的数值分析是可能的，并且在SPICE中实现的各种技术将使数值分析非常有效。在这个项目中，我们将同伦方法的PFC应用于各种非线性问题，并证明了同伦方法是全局收敛的。这种方法使SPICE适用于更广泛的科学问题。

In this project, we first proposed an efficient homotopy method for solving nonlinear circuits, and prove its global convergence property for modified nodal equations that describe nonlinear circuits. By this method, bipolar analog integrated circuits with more than 10000 elements were solved efficiently with the theoretical guarantee of global convergence. We further proposed an improved version of the homotopy method using a new homotopy function and an effective initial solution algorithm, which is much more efficient than the above method.We next proposed an efficient algorithm for finding all solutions of piecewise-linear resistive circuits using the dual simplex method. Using this algorithm, all solutions of large scale problems, including those where the number of variables is 2000 and the number of linear regions is 1000^{2000}, could be found in practical computation time, which is a remarkable development in this field.We also proposed SPICE-oriented numerical methods for solving nonlinear problems using path following circuits. The path following circuits (PFC's) are circuits for solving nonlinear problems on the circuit simulator SPICE. In the method of PFC's, formulas of numerical methods are described by circuits, which are solved by SPICE. Using PFC's, numerical analysis without programming is possible, and various techniques implemented in SPICE will make the numerical analysis very efficient. In this project, we applied the PFC's of the homotopy method to various nonlinear problems where the homotopy method is proven to be globally convergent. This approach makes SPICE applicable to a broader class of scientific problems.