Language: English
ISBN/ISSN: 9787030367532
Published on: 2013-04
Hardcover
E?ective Condition Number
In this beginning chapter,new computational formulas are provided for the exective condition number Cond e?,and new error bounds involved in both Cond and Cond e? are derived. A theoretical analysis is provided to support some conclusions in Banoczi et al. [14]. For the linear algebraic equations solved by Gaussian elimination (GE) or the QR factorization (QR),the direction of the right-hand vector is insigniˉcant for the solution errors,but such a conclusion is invalid for the ˉnite di- ?erence method for Poisson0s equation. The e?ective condition number is important to the numerical partial di?erential equations,because the discretization errors are dominant. The materials of this chapter are adapted from [95,127,134,138,218].
1.1 Introduction
The deˉnition of the traditional condition number was given in Wilkinson [227], and then used in many books and papers. To solve the overdetermined system of the linear algebraic equations Fx = b,the traditional condition number in the 2-norm is deˉned by Cond = ?1=?n,where ?1 and ?n are the maximal and the minimal singular values of matrix F,respectively. The condition number is used to provide the bounds of the solution errors from the perturbation of both matrix F and vector b. The new computational formulas are derived in this chapter for the e?ective condition numbers,denoted by Cond e?,Cond E and Cond EE. The Cond e? denotes the enlarged factor of the solution errors over the residual errors. For further application,in this chapter we also derive the new error bound involved in both Cond and Cond e?. In this new bound,the Cond and the Cond e? denote basically the enlarged factors of the errors over the perturbation errors of matrix F and vector b,respectively. Hence,when the matrix and the vector errors are dominant,Cond and Cond e? will play an important role,respectively.
First,we apply Cond e? to the linear algebraic equations,and a theoretical jus- ti- cation is given to support some conclusions in [14]. For the solution errors of the algebraic equations by Gaussian elimination (GE) or the QR factorization (QR),the direction of the right-hand vector is insigniˉcant. Then we apply Cond e? to the numerical partial di?erential equations (PDE) and the Tre?tz method (TM) for Poisson0s equation. Since the discretization errors are dominant,the e?ective condi- tion number is important. Moreover,since the TM solution is highly accurate,the small e?ective condition number well explains the high accuracy of the solutions, and strengthens the collocation Tre?tz method (CTM) in [155],where only error bounds and numerical experiments are provided without the stability analysis. It is explored in this chapter and the entire book that the huge Cond is often mislead-ing,but the e?ective condition number is the appropriate criterion for the stabilityanalysis.
Here let us illustrate the references of the condition number and the e?ective con-dition number. The traditional condition number Cond was ˉrst given in Wilkinson [227],and then used in many textbooks,such as Strang [197],Atkinson [3],Schwarz [191],Datta [44],Gill et al. [65],Golub and van Loan [66],Stewart [195],Horn and Johnson [90],Sun [199],Wang et al. [212],and Higham [88]. The condition num-ber for eigenvalues is introduced in Parlett [180] and Frayss?e and Toumazou [61], and there are more discussions in Gulliksson and Wedin [71],and Elsner et al. [55]. The Cond is applied to the numerical partial di?erential equations in Strang and Fix [198],Quarteroni and Valli [184] and Li [115]. On the other hand,the e?ective condition number was deˉned and studied in Chan and Foulser [27]. However,its algorithm was ˉrst proposed in Rice [186] in 1981,but the natural condition number was called. Only a few reports,such as Christiansen and Hansen [37],Christiansen and Saranen [38],Banoczi et al. [14],and Axelsson and Kaporin [7,8],follow the line of the e?ective condition number. The error estimates for the solution of the linearal gebraic system in Brezinski [20] are also related to the e?ective condition number.Recently,the new computational formulas of e?ective condition number have been studied and applied to symmetric and positive deˉnite matrices,which are obtained from Poisson0s equation by the ˉnite di?erence method (FDM) in [127].
Preface
Acknowledgments
Chapter 1 Effective Condition Number
1.1 Introduction
1.2 Preliminary
1.3 Symmetric Matrices
1.3.1 Deffnitions of Effective condition numbers
1.3.2 A posteriori computation
1.4 Overdetermined Systems
1.4.1 Basic algorithms
1.4.2 Reffnements of (1.4.10)
1.4.3 Criteria
1.4.4 Advanced reffnements
1.4.5 Effective condition number in p-norms
1.5 Linear Algebraic Equations by GE or QR
1.6 Application to Numerical PDE
1.7 Application to Boundary Integral Equations
1.8 Weighted Linear Least Squares Problems
1.8.1 Effective condition number
1.8.2 Perturbation bounds
1.8.3 Applications and comparisons
Chapter 2 Collocation Trefftz Methods
2.1 Introduction
2.2 CTM for Motz's Problem
2.3 Bounds of Effective Condition Number
2.4 Stability for CTM of Rp=1
2.5 Numerical Experiments
2.5.1 Choice of Rp
2.5.2 Extreme accuracy of D0
2.6 GCTM Using Piecewise Particular Solutions
2.7 Stability Analysis of GCTM
2.7.1 Trefftz methods
2.7.2 Collocation Trefftz methods
2.8 Method of Fundamental Solutions
2.9 Collocation Methods Using RBF
2.10 Comparisons Between Cond_eff and Cond
2.10.1 CTM using particular solutions for Motz's problem
2.10.2 MFS and CM-RBF
2.11 A Few Remarks
Chapter 3 Simpliffed Hybrid Trefftz Methods
3.1 The Simpliffed Hybrid TM
3.1.1 Algorithms
3.1.2 Error analysis
3.1.3 Integration approximation
3.2 Stability Analysis for Simpliffed Hybrid TM
Chapter 4 Penalty Trefftz Method Coupled with FEM
4.1 Introduction
4.2 Combinations of TM and Adini0s Elements
4.2.1 Algorithms
4.2.2 Basic theorem
4.2.3 Global superconvergence
4.3 Bounds of Cond_eff for Motz's Problem
4.4 Effective Condition Number of One and Inffnity Norms
4.5 Concluding Remarks
Chapter 5 Trefftz Methods for Biharmonic Equations with Crack Singularities
5.1 Introduction
5.2 Collocation Trefftz Methods
5.2.1 Three crack models
5.2.2 Description of the method
5.2.3 Error bounds
5.3 Stability Analysis
5.3.1 Upper bound for σmax(F)
5.3.2 Lower bound for σmin(F)
5.3.3 Upper bound for Cond_eff and Cond
5.4 Proofs of Important Results Used in Section 5.3
5.4.1 Basic theorem
5.4.2 Proof of Lemma 5.4.3
5.4.3 Proof of Lemma 5.4.4
5.5 Numerical Experiments
5.6 Concluding Remarks
Chapter 6 Finite Difference Method
6.1 Introduction
6.2 Shortley-Weller Difference Approximation
6.2.1 A Lemma
6.2.2 Bounds for Cond EE
6.2.3 Bounds for Cond_eff
Chapter 7 Boundary Penalty Techniques of FDM
7.1 Introduction
7.2 Finite Difference Method
7.2.1 Shortley-Weller Difference approximation
7.2.2 Superconvergence of solution derivatives
7.2.3 Bounds for Cond_eff
7.3 Penalty-Integral Techniques
7.4 Penalty-Collocation Techniques
7.5 Relations Between Penalty-Integral and Penalty-Collocation Techniques
7.6 Concluding Remarks
Chapter 8 Boundary Singularly Problems by FDM
8.1 Introduction
8.2 Finite Difference Method
8.3 Local Reffnements of Difference Grids
8.3.1 Basic results
8.3.2 Nonhomogeneous Dirichlet and Neumann boundary conditions
8.3.3 A remark
8.3.4 A view on assumptions A1-A4
8.3.5 Discussions and comparisons
8.4 Numerical Experiments
8.5 Concluding Remarks
Chapter 9 Finite Element Method Using Local Mesh Refinements
9.1 Introduction
9.2 Optimal Convergence Rates
9.3 Homogeneous Boundary Conditions
9.4 Nonhomogeneous Boundary Conditions
9.5 Intrinsic View of Assumption A2 and Improvements of Theorem 9.4.1
9.5.1 Intrinsic view of assumption A2
9.5.2 Improvements of Theorem 9.4.1
9.6 Numerical Experiments
Chapter 10 Hermite FEM for Biharmonic Equations
10.1 Introduction
10.2 Description of Numerical Methods
10.3 Stability Analysis
10.3.1 Bounds of Cond
10.3.2 Bounds of Cond_eff
10.4 Numerical Experiments
Chapter 11 Truncated SVD and Tikhonov Regularization
11.1 Introduction
11.2 Algorithms of Regularization
11.3 New Estimates of Cond and Cond_eff
11.4 Brief Error Analysis
Appendix Deffnitions and Formulas
A.1 Square Systems
A.1.1 Symmetric and positive deffnite matrices
A.1.2 Symmetric and nonsingular matrices
A.1.3 Nonsingular matrices
A.2 Overdetermined Systems
A.3 Underdetermined Systems
A.4 Method of Fundamental Solutions
A.5 Regularization
A.5.1 Truncated singular value decomposition
A.5.2 Tikhonov regularization
A.6 p-Norms
A.7 Conclusions
Epilogue
Bibliography
Index
