A Dynamical Tikhonov Regularization for Solving Ill-posed Linear Algebraic Systems
- PDF / 959,200 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 180 Views
A Dynamical Tikhonov Regularization for Solving Ill-posed Linear Algebraic Systems Chein-Shan Liu
Received: 28 March 2011 / Accepted: 26 May 2012 / Published online: 13 June 2012 © Springer Science+Business Media B.V. 2012
Abstract The Tikhonov method is a famous technique for regularizing ill-posed linear problems, wherein a regularization parameter needs to be determined. This article, based on an invariant-manifold method, presents an adaptive Tikhonov method to solve ill-posed linear algebraic problems. The new method consists in building a numerical minimizing vector sequence that remains on an invariant manifold, and then the Tikhonov parameter can be optimally computed at each iteration by minimizing a proper merit function. In the optimal vector method (OVM) three concepts of optimal vector, slow manifold and Hopf bifurcation are introduced. Numerical illustrations on well known ill-posed linear problems point out the computational efficiency and accuracy of the present OVM as compared with classical ones. Keywords Ill-posed linear system · Tikhonov regularization · Adaptive Tikhonov method · Dynamical Tikhonov regularization · Steepest descent method (SDM) · Conjugate gradient method (CGM) · Optimal vector method (OVM) · Barzilai-Borwein method (BBM) Mathematics Subject Classification (2010) 65F10 · 65F22
1 Introduction Consider the following linear system: Bx = b1 ,
(1)
where B ∈ Rn×n is a given matrix, which might be unsymmetric, and x ∈ Rn is an unknown vector. The above equation is sometimes obtained via an n-dimensional discretization of a bounded linear operator equation under an noisy input. We only look for a generalized solution x = B† b1 , where B† is a pseudo-inverse of B in the Penrose sense. When B is C.-S. Liu () Department of Civil Engineering, National Taiwan University, Taipei, Taiwan e-mail: [email protected]
286
C.-S. Liu
severely ill-conditioned and the data are corrupted by noise, we may encounter the problem that the numerical solution of Eq. (1) deviates from the exact one to a great extent. If we only know perturbed input data bδ1 ∈ Rn with b1 − bδ1 ≤ δ, and if the problem is ill-posed, i.e., the range R(B) is not closed or equivalently B† is unbounded, we have to solve the system (1) by a regularization method. A measure of the ill-posedness of Eq. (1) can be performed by using the condition number of B [53]: (2) cond(B) = BF B−1 F , where BF denotes the Frobenius norm of B. For every matrix norm • we have ρ(B) ≤ B, where ρ(B) is a radius of the spectrum of B. The Householder theorem states that for every > 0 and every matrix B, there exists a matrix norm B depending on B and such that B ≤ ρ(B) + . Anyway, the spectral condition number ρ(B)ρ(B−1 ) can be used as an estimation of the condition number of B by cond(B) =
maxσ (B) |λ| , minσ (B) |λ|
(3)
where σ (B) is the collection of all the eigenvalues of B. Turning back to the Frobenius norm we have √ BF ≤ n max |λ|. (4) σ (B)
In particular, for the symmetric case ρ(B)ρ(B−1 ) = B2 B−1 2 . R
Data Loading...
