Newton-PCG型算法的效率分析

摘要

基于Dembo,Eisenstat和Steihaug在1982年发现的不精确Newton法定理,近年来人们提出了许多用于不精确Newton法的技巧.最常见的是线性共轭梯度法（CG）.由于CG法的收敛状态强烈的依赖于海色阵的条件数,所以用条件预优共轭梯度法（PCG）替代CG法会得到更好的效果.带有PCG子迭代的不精确Newton法是否比Newton法有效？若它比Newton法有效,那么有效多少？是否有理论支持？数值实验又如何？该文旨在回答以上问题.我们从理论和数值实验两方面证实了Newton-PCG型的算法比Newton法有效,并且从理论上给出了有效的定量化指标.

目录

文摘

英文文摘

声明

1HistoricalBackground

2TheoreticalMeasureofanAlgorithmEvaluation

2.1 Generalized Convergence Q-order

2.2 New Efficiency Index Γ

3ThreeNewNewton-PCGLikeAlgorithms

3.1 Algorithm CF-PCGⅠ

3.2 Algorithm CF-PCGⅡ

3.3 Algorithm CF-PCGⅢ

4TheoreticalEfficiencyAnalysis

4.1 The Analysis of Algorithm CF-PCGI's Efficiency

4.2 The Analysis of Algorithm CF-PCGII's Efficiency

4.3 The Analysis of Algorithm CF-PCGIII's Efficiency

5NumericalExperiments

5.1 Numerical Experiments of Algorithm CPⅠ

5.2 Numerical Experiments of Algorithm CPⅡ

Acknowledgment

Bibliography

Appendix