中文摘要：

无Jacobian矩阵的牛顿-Krylov子空间方法是求解非线性方程组问题的一类常用算法，然而如何在无Jacobian矩阵的情况下构造合适的预条件一直是该方法中的难点。本研究将着重研究基于自动微分的双边着色技术计算稀疏Jacobian矩阵的某一特定部分的非零元，以这些非零元为基础构造合适的预条件，加速每一步牛顿迭代中Krylov子空间方法的收敛。同时，针对稠密的Jacobian矩阵，推广双边着色技术并配合扩展的牛顿法并行化求解非线性方程组问题。最后，本研究将利用最优化问题中梯度与Hessian矩阵的特殊结构使用自动微分构造无Hessian矩阵的牛顿-Krylov子空间算法中的预条件，提高其求解的效率。本研究项目将应用图论知识与自动微分技术，解决在一般情况下JFNK与HFNK方法中预条件的构造问题，从而得到一类适用范围广、计算精度高、收敛速度快的求解非线性问题的JFNK/HFNK方法。

结论摘要：

我们已经顺利完成青年基金项目的任务。 在系数矩阵部分非零元素的计算方面，利用稀疏Jacobian矩阵的非零元素结构，提出了双边着色技术计算Jacobian矩阵中的非零元素，同时针对Jacobian矩阵中出现的重复元素，提出了针对重复元素的着色方法，从而进一步降低计算的工作量；在稀疏Jacobian矩阵非线性方程组求解方面，提出了一种基于Jacobian部分非零元素的显式预条件构造方法的Krylov子空间方法，并成功将该方法应用于求解电力系统中潮流计算的非线性问题；在稠密Jacobian矩阵非线性问题求解方面，提出了多重迭代的Jacobian-free Krylov子空间方法，该方法不受Jacobian矩阵结构的影响，能够广泛的应用于一般非线性问题的求解。同时，我们还将该方法推广到最优化问题的求解上，并且在金融衍生品定价等方面取得了很好的计算效果。青年基金项目在研期间，申请人在国际知名杂志，如 SIAM Scientific Computing， IEEE Transaction on Power Systems，Data Mining and Knowledge Discovery，IET Communications, Numerical Algorithms, Optimization Methods and Software,Pattern Recognition， Journal of Derivatives，Quantitative Finance，Journal of Computational Finance上发表论文10篇。