alexa On Regularisation and Comparison of Methods for Solving Hilbert Linear Systems | OMICS International
ISSN: 2090-0902
Journal of Physical Mathematics
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

On Regularisation and Comparison of Methods for Solving Hilbert Linear Systems

Azizu S*

Faculty of Mathematical Sciences, Mathematics Department, Navrongo Campus, Ghana

Corresponding Author:
Azizu S
Faculty of Mathematical Sciences
Mathematics Department, Navrongo Campus
Ghana
Tel: +23304113473
E-mail: [email protected]

Received date: March 31, 2016; Accepted date:April 29, 2016; Published date: May 05, 2016

Citation: Azizu S (2016) On Regularisation and Comparison of Methods for Solving Hilbert Linear Systems. J Phys Math 7: 173. doi:10.4172/2090-0902.1000173

Copyright: © 2016 Azizu S. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Visit for more related articles at Journal of Physical Mathematics

Abstract

This paper deals with linear ill-posed problems relating to Hilbert Systems using comparisons of methods (Matlab Backslash, SVD, GMRES, QR, and PCG) including their regularizations. Hilbert systems of varying sizes were investigated and several results on these methods were presented in tabular form based on error and relative error norm. From our numerical results ran on Matlab version 7.01 only QR regularization method is recommended for the solution of Hilbert linear system.

Keywords

Hilbert system; SVD decomposition; GMRES; QR factorisation; Error norm

Introduction

Recently, structured perturbations for linear systems have attracted much attention [1-3]. When solving linear systems of equations, it is important to analyze [4] how small perturbations of the matrix and right-hand side affect the solution. It is widely known that the solutions of linear systems of equations are sensitive [5] to round-off error and always ill-posed [6] to solve a linear system with Hilbert coefficient matrix due to its large condition number. Therefore, stable and efficient algorithms are needed to reduce the ill-posedness and get effective solutions for such kinds of Hilbert matrix equations. It is well known that for a system of equations with an ill-conditioned matrix, an erroneous solution can be obtained which seems to satisfy the system quite well. Various measures [7] of the ill-conditioning of a matrix have been proposed.

Related Works

The Generalized Minimal Residual (GMRES) method computes a sequence of orthogonal vectors with least-squares approach [4]. The Gmres method combines with preconditioning in the solutions of linear systems in order to speed up convergence. This method is useful for general nonsymmetric matrices and the most popular Krylov subspace method applicable to any invertible matrix A. The roster of standard matrix decompositions [8] includes the pivoted QR factorization, the eigenvalue decomposition, and the singular value decomposition (SVD), all of which expose the numerical range of a matrix. SVD and truncated SVD (TSVD) methods were utilized for solving discrete illposed problems [9].

Regularization Method

The standard method to solve ill-conditioned systems known as Regularization has been studied [10]. Regularization methods use known information about the solution for solving ill-conditioned systems. The problem is highly sensitive to small perturbation in the sense that small perturbation in the data cause large changes in the solution.

Singular value decomposition

SVD is very powerful and useful matrix decomposition, particularly in the context of data analysis, reducing transformations of images, and satellite data and is the method of choice for solving most linear least– squares problems. The SVD is intimately related to the familiar theory of diagonalizing a symmetric matrix. The SVD [11] is an extension of the diagonalization of a matrix. The diagonalization of a matrix is applicable only to square matrices and only to those that satisfy a quite demanding condition. SVD is a classical method [12] for extracting feature vectors in data.

QR factorisation

The QR decomposition (also called the QR factorization) of a matrix is a decomposition of the matrix into an orthogonal matrix and a triangular matrix. A QR decomposition of a real square matrix A is a decomposition of A as A=QR. The QR decomposition is valid for rectangular matrices as well square ones. This decomposition can be used for solving n × n linear systems but is also useful in solving overdetermined systems such as those in linear least squares. The decomposition will be used in a general algorithm for finding all eigenvalues and eigenvectors of a matrix. The two approaches [10], matrix and vector equations in QR factorization are powerful general tools and appeared to be applicable to the perturbation analysis of any matrix factorization.

Matlab backslash

To emphasize the distinction between solving linear equations and computing in- verses, Matlab has introduced nonstandard notation [13] using backward slash operator, “\” If A is a matrix of any size and shape and b (the right-hand side vector) is a matrix with as many rows as A, then the matlab backlash can be used to solved the solution vector x in Ax=B.

Generalized minimal residual (GMRES)

The Generalized Minimal Residual (GMRES) method computes a sequence of orthogonal vectors and combines these through leastsquares method. This method combines with preconditioning method to speed up convergence. However, CG requires storing the whole sequence, so that a large amount of storage is needed. For this reason, restarted versions of this method are used. GMRES is the most popular Krylov subspace method applicable to any invertible matrix A.

Preconditioned conjugate gradient (PCG)

The performance of the conjugate gradient [4] method improves when the eigenvalues of matrix A are clustered about a point. This suggests the possibility of preconditioning A by a positive definite matrix M and solving M-1Ax=M-1b. If the eigenvalues of M-1A were clustered the conjugate gradient procedure may con verge at a faster rate. The preconditioned M, should be chosen to minimize the solution time. There are_ however competing priorities. Thus for example the optimal choice of M as far as clustering eigenvalues is concerned is M=A. This choice requires a direct solution of the original system and thus has an extreme cost.

Numerical Experiments and Results

In this paper, we present some numerical results to show the performance of error and relative error=of ill-conditioned linear systems. We ran our algorithm using MATLAB software version 7.0.1 on Intel(R) Pentium (R) CPU P600 @ 1.87GHz 1.87 and Installed Memory (RAM): 4.00GB. With regard to Hilbert system of linear equations using the MATLAB command for the coefficient matrix A and RHS vector b where the exact solution is x=ones (n,1) for the discussion to test for illconditioning of the system, varying sizes(n) of the Hilbert matrix were considered as shown in the Tables 1-5. We started with n=10, n=20, n=30, n=60 and n=120 and in each computation, the matlab backslash, QR, SVD,GMRES, PCG and their regularizations (RMatlab (“\”), RQR RSVD,RGMRES, RPCG) were used to determine the error and relative error of each size of Hilbert matrix. The Hilbert matrix HòRn×n with entries Figure

Methods Figure Figure
Matlab(“\”) 7.8918e-004 2.4956e-004
QR 6.5264 2.0638
SVD 1.7180e+013 5.4329e+012
GMRES 0.0345 0.0109
PCG 3.1623 1.0000
Regularization(R)
R Matlab(“\”) 8.9523 2.8310
RQR 0.2853 0.0902
R SVD 6.6621e+003 2.1068e+003
R GMRES 0.2856 0.0903
R PCG 0.2856 0.0903

Table 1: Hilbert System n=10.

Methods Figure Figure
Matlab(“\”) 66.2923 14.8234
QR 9.1309 2.0417
SVD 1.7847e+018 3.9906e+017
GMRES 0.0325 0.0073
PCG 4.4721 1.0000
Regularization (R)
R Matlab(“\”) 191.6066 42.8445
RQR 0.3890 0.0870
R SVD 1.1806e+004 2.6400e+003
R GMRES 0.3890 0.0870
R PCG 0.3890 0.0870

Table 2: Hilbert System n=20.

Methods Figure Figure
Matlab(“\”) 106.9835 19.5324
QR 11.1001 2.0266
SVD 2.7502e+018 5.0212e+017
GMRES 0.0203 0.0037
PCG 5.4772 1.0000
Regularization (R)
R Matlab(“\”) 7.5318e+003 1.3751e+003
RQR 0.5102 0.0932
R SVD 1.5385e+004 2.8090e+003
R GMRES 0.5103 0.0932
R PCG 0.5103 0.0932

Table 3: Hilbert System n=30.

Methods Figure Figure
Matlab(“\”) 212.1060 27.3828
QR 15.4956 2.0005
SVD 1.0164e+019 1.3121e+018
GMRES 0.0628 0.0081
PCG 7.7460 1.0000
Regularization (R)
R Matlab(“\”) 1.4314e+003 184.7867
RQR 0.7052 0.0910
R SVD 2.4649e+004 3.1821e+003
R GMRES 0.7090 0.0915
R PCG 0.7090 0.0915

Table 4: Hilbert System n=60.

Methods Figure Figure
Matlab(“\”) 5.3477e+003 488.1792
QR 21.1229 1.9282
SVD 4.3154e+019 3.9394e+018
GMRES 0.0665 0.0061
PCG 10.9545 1.0000
Regularization (R)
RMatlab(“\”) 3.0006e+003 273.9158
R QR 0.9843 0.0899
R SVD 3.0943e+004 2.8247e+003
R GMRES 0.9843 0.0899
R PCG 0.9843 0.0899

Table 5: Hilbert System n=120.

Discussions

The tables of the numerical experiments of the Hilbert linear system using varying sizes showed the error and relative error norm of each identified methods. Generally, the error and relative error norms of the regularizations of GMRES are equal in value. Again, from Table 1 the error and relative error norm of regularization of QR factorization has improved the Hilbert linear systems as compared to the other identified methods. Finally, only QR regularization method is recommended for the solution of Hilbert linear system.

Conclusion and Future Work

The regularization methods of Hilbert linear systems has been presented using varying sizes to compare the performance of the identified methods in terms of error and relative error norm. The regularization methods of Matlab, GMRES, SVD and PCG did not improve the reduction of the error and relative error norm of the identified system. We therefore recommended the regularized QR factorization method when solving Hilbert linear system.

Future work to be considered is Vander monde linear system and compares it with the known Krylov sub space methods GMRES and PCG.

References

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Article Usage

  • Total views: 8646
  • [From(publication date):
    June-2016 - May 26, 2018]
  • Breakdown by view type
  • HTML page views : 8496
  • PDF downloads : 150
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2018-19
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

[email protected]

1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Engineering Journals

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

ge[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2018 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version
Leave Your Message 24x7