大型稀疏非线性方程组的一类不精确Newton法的任务书.docx

大型稀疏非线性方程组的一类不精确Newton法的任务书
任务书
题目：大型稀疏非线性方程组的一类不精确Newton法
导师：XXX
任务背景：
在工程和科学计算中，向量和矩阵的稀疏性应用非常广泛。然而，稀疏矩阵的数值计算是一种具有挑战性的任务，并且已经成为一个独立领域的研究方向。非线性方程组求解是数值计算的一个基本问题，它存在广泛的应用，如多元函数极值问题、物理学中方程的求解等。虽然Newton法在进行非线性方程组求解时非常有效，但是在处理大型稀疏矩阵时遇到很大的问题。为了解决这一问题，不精确Newton法因其简单和高效而被广泛使用。
任务要求：
1.了解求解大型稀疏非线性方程组的常见算法，如Newton法、Broyden法等。并且深入掌握不精确Newton法的求解原理，分析其优劣以及适用范围。
2.了解稀疏矩阵的存储方式，学习稀疏矩阵的运算，掌握传统算法如稠密矩阵存储的LU分解方式对于稀疏矩阵的不适用性。
3.初步了解一些高效的稀疏矩阵存储方式及其相关的操作，如CRS、CCS、ELL、BELL、JDS等。
4.实践中实现一个不精确Newton法算法，利用Matlab或者C++等语言，分别采取以上不同的稀疏矩阵存储方式实现，对比SolidLU分解、UMFPACK等方法的性能以及精度。
5.研究不同的预估算法，如拟牛顿等，对于不精确Newton法的影响。对比精确Newton法和不精确Newton法在不同的预估算法下的准确性和速度。
6.通过实践完整地理解和掌握不精确Newton方法在大型稀疏非线性方程组求解中应用的优点和局限性，进一步分析对其进行改进的可能。
任务计划：
第1个月：阅读相关论文，掌握基础算法、矩阵存储方式和传统算法的缺陷。分析原始算法的数值求解过程和优缺点。
第2-3个月：实现不精确Newton法的算法并将其与传统算法对比。分别采用CRS、CCS、ELL、BELL、JDS等不同的稀疏矩阵存储方式进行实现，并记录时间和空间的使用情况。将实现结果分别记录下来并对比实验。
第4个月：尝试使用拟牛顿等预估算法对实现的不精确Newton方法进行改进。对比精确Newton法和不精确Newton法在不同的预估算法下的准确性和速度。对比分析得到的实验结果并在实验报告中分析结果。
第5个月：对比研究究竟为何不精确通量牛顿方法中的不精确度会产生这样的泛化效果，是否是由于减少了数值计算的精度，也可能是因为数学期望的误差降低了过度拟合的风险，对不同案例进行实验，并在实验报告中说明结果。
第6个月：总结和分析实验结果，撰写实验报告，并进行答辩。
参考文献：
1.Z.Bai,X.Li,andJ.W.Demmel,OnComputingSparseLUFactorization,ACMTransactionsonMathematicalSoftware,vol.28,March2002,pp.1–23.
2.G.H.GolubandC.F.vanLoan,Matrixcomputations,thirdedition,JohnHopkinsUniversityPress,Baltimore,1996.
3.N.H.XiuandS.Boyd,“FastMIMOdecod-ingalgorithmswithlowmemoryrequirements”,ProceedingsofIEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing,Orlando,Florida,2002.
4.W.W.HagerandH.Zhang,“Anewactivesetalgorithmforboxconstrainedoptimization”,SIAMJournalonOptimization,vol.13,no.3,pp.653–676,2002.
5.R.FreundandN.M.Nachtigal,“QMR:Aquasi-minimalresidualmethodfornon-Her-mitianlinearsystems”,NumericalMathematics,vol.60,pp.315–339,1991.
6.D.W.TowsleyandP.Varshney,“Investi-gationofalternatingdirectionalgorithmsforsolvingsystemsoflinearequations”,IEEETransactionsonSignalProcessing,vol.48,no.9,pp.2470–2481,2000.