臺灣博碩士論文加值系統

在此篇論文裡，我們研究多重網格法應用在延續法中，來解非線性橢圓特徵值問題，並且討論利用雙重網格法來解定義在L型曲域的線性特徵值問題。我們首先用有限元素法將偏微分方程離散化，在多重網格法的V-循環，W-循環以及完全的多重網格V-循環中，使用Lanczos法、MINRES和SYMMLQ作為其中的鬆弛法。我們比較這些鬆弛法在多重網格中的效益。我們亦討論雙重網格-中央差分法在L型的區域中解線性特徵值問題。由數值的結果中我們可以知道 Lanczos法是相當有效的。最後我們將所得結果繪製成圖表並做結論。

We study multigrid methods in the context of continuation methods for semilinear elliptic eigenvalue problems, where the Lanczos method, the MINRES and the SYMMLQ are used as linear solvers.
The semilinear elliptic eigenvalue problems are discretized by six-node triangular elements.
We compare the efficiency of these linear solvers in the context of multigrid V-cycle, W-cycle and the full multigrid V-cycle (FMG) schemes.
Next, we study the two-grid centered difference discretization scheme for the eigenvalue problem defined on an L-shaped domain.
Our numerical results show that the accuracy of computed eigenpairs is improved efficiently.
Moreover, compared with the performance of (preconditioned) MINRES and SYMMLQ, the (preconditioned) Lanczos algorithm is still very competitive.

Contents
1.Introduction 1
2.A brief review of the Preconditioned Lanczos type algorithms 2
3.The finite-element method 7
4.V-cycle, W-cycle and full multigrid V-cycle methods 10
5.Two-grid discretization schemes and domain decomposition 13
6.Numerical results 16
7.Conclusions 18
List of tables 19
List of figures 24
References 27

1. Allgower EL, Georg K. Numerical path following. In Handbook of Numerical Analysis,
Ciarlet PG, Lions JL(eds), vol. 5. North-Holland: Amsterdam, 1997.
2. Bank RE, Chan TF. PLTMGC: A multigrid continuation package for solving parametrized
nonlinear elliptic systems. SIAM J. Sci. Stat. Comput. 1986; 7:540—559.
3. Bolstad JH, Keller HB. A multigrid continuation method for elliptic problems with folds.
SIAM Journal on Scientific and Statistical Computing 1986; 7:1081—1104.
4. Book DL, Fisher S, McDonald BE. Steady-state distributions of interacting discrete vortices.
Physical Review Letters 1975; 34:4—8.
5. Brandt A. Multi-level adaptive solutions to boundary value problems. Mathematics of
Computation 1977; 31:333—390.
6. Briggs WL, Henson VE, McCormic SF. A Multigrid Tutorial (2nd edn). SIAM Publications:
Philadelphia, 2000.
7. Brown PN, Walker HF. GMRES on (nearly) singular systems. SIAM Journal on Matrix
Analysis and Applications 1997; 18:37—51
8. Chan TF, Keller HB. Arc-length continuation and multi-grid techniques for nonlinear
elliptic eigenvalue problems. SIAM J. Sci. Stat. Comput. 1982; 3:173—194.
9. Chang S-L, Chien C-S. A multigrid-Lanczos algorithm for the numerical solutions of nonlinear
eigenvalue problems. International J. Bifurcation and Chaos 2003; 13:1217—1228.
10. Chang S.-L, Chien C-S, Jeng B.-W. Implementing two-grid centered difference discretization
schemes with Lanczos type algorithms. preprint.
11. Chien C-S,Weng Z-L, Shen C-L. Lanczos type methods for continuation problems. Numer.
Linear Algebra Appl. 1997; 4:23—41.
12. Chien C-S, Chang S-L. Application of the Lanczos algorithm for solving the linear systems
that occur in continuation problems. Numer. Linear Algebra Appl. 2003; 10:335—355.
13. Chien C-S, Jeng B-W. Two-grid discretization schemes for eigenvalue problems. preprint.
14. Chien C-S, Jeng B-W. Symmetry reductions and a posteriori finite element error estimators
for bifurcation problems. Inter. J. Bifurcation and Chaos. 2005. to appear.
15. Chien C-S, Jeng B-W., Gu.Y.-P. A two-grid centered difference discretization scheme for
large-scale eigenvalue problems. preprint.
16. Desa C, Irani KM, Ribbens CJ, Watson LT, Walker HF. Preconditioned iterative methods
for homotopy curve tracking. SIAM J. Sci. Stat. Comput. 1992; 13:30—46.
17. Dul FA. MINRES and MINERR are better than SYMMLQ in eigenpair computations.
SIAM J. Sci. Comput. 1998; 19:1767—1782.
18. Golub GH, van der Vorst HA. Eigenvalue computation in the 20th century. J. Comput.
Appl. Math. 2000; 123:35—65.
19. Hackbusch W. Multigrid Methods and Applications. Springer-Verlag: Berlin, 1985.
20. Keller HB. Lectures on Numerical Methods in Bifurcation Problems. Springer-Verlag:
Berlin, 1987.
21. Lanczos C. An iteration method for the solution of the eigenvalue problems of linear differential
and integral operators. Journal of Research of the National Bureau of Standards
1950; 45:255—282.
22. Lui SH, Golub GH. Homotopy method for the numerical solution of the eigenvalue problem
of self-adjoint partial differential operators. Numer. Algorithms 1995; 10:363—378.
23. Mittelmann HD, Weber H. Multi-grid solution of bifurcation problems. SIAM Journal on
Scientific and Statistical Computing 1985; 6:49—85.
24. Paige CC. The computation of eigenvalues and eigenvectors of very large matrices. Ph.
D. Thesis, University of London 1971.
25. Paige CC, Saunders MA. Solution of sparse indefinite systems of linear equations. SIAM
J. Numer. Anal. 1975; 12:617—629.
26. Saad Y, Schultz MH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric
linear systems. SIAM J. Sci. Stat. Comput. 1986; 7:856—869.
27. Sleijpen GLG, van der Vorst HA, Modersitzki J. Differences in the effects of rounding
errors in Krylov solvers for symmetric indefinite linear systems. SIAM J. Matrix Anal.
Appl. 2000; 22:726—751.
28. Walker HF. An adaption of Krylov subspace methods to path following problems. SIAM
J. Sci. Comput. 1999; 21:1191—1198.
29. Weber H. Multigrid bifurcation iteration. SIAM Journal on Numerical Analysis 1985;
22:262—279.
30. Xu J., A novel two-grid method for semilinear elliptic equations, SIAM J. Sci. Comput.,
15(1994), pp.231—237.
31. Xu J., Some Two-grid Finite Element Methods. Contemp. Math. 1994; 157:79—87.
32. Xu J., Zhou A. A two-grid discretization scheme for eigenvalue problems. Math. Comput.
1999; 70:17—25.