Reach Us
+32-10-28-02-25

**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

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.

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

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.

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].

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.

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òR^{n×n} with entries

Methods | ||
---|---|---|

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 | ||
---|---|---|

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 | ||
---|---|---|

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 | ||
---|---|---|

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 | ||
---|---|---|

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.

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.

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.

- Rump SM (2003) Structured perturbations Part II: component-wise distances. SIAM Journal on Matrix Analysis and Applications 25: 31-56.
- Higham DJ, Higham NJ (1992) Backward error and condition of structured linear systems. SIAM Journal on Matrix Analysis 13:162-176.
- Gohberg I, Koltracht I (1993) Mixed, componentwise, and structured condition numbers.SIAM Journal on Matrix Analysis and Application 14:688-704.
- Castanon JA (2012) On 1 Minimization for Ill-Conditioned Linear Systems with Piecewise Polynomial Solutions.Rice University, USA.
- FazlollahS (2013) A New Method For Solving Ill-Conditioned Linear System.OpusculaMathematica. 33: 337-344.
- Xinjie Li, Gongsheng Li(2012)A Note on Solving High-order Hilbert Matrix Equation by Tikhonov Regularization. Journal of Information & Computational Science9:1957-1966.
- ZahraV,BehrouzD (2013) On the solution of ill-conditioned systems of Linearequations. Journal of Expert Systems 2: 15-36.
- Halko N, Martinsson NPG, Tropp JA (2011) Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. Society for Industrial and Applied Mathematics53: 217-288
- Mayo A (1984) The Fast Solution of Poisson’s and the Biharmonic Equations on Irregular Regions.SIAM J Numer Anal 21: 285-299.
- Chang XW, Paige CC, Stewart GW (1997) Perturbation Analyses for the QR Factorization. SIAM J Matrix Anal &Appl 18: 775-791.
- Lathauwer LD, Moor B, Vandewalle J (2000) A Multilinear Singular Value DecompositionSIAM. J Matrix Anal &Appl 21: 1253-1278.
- Masafumi H,HiroyukiK, Pan J, Faloutsos C(2005) A ComparativeStudyof FeatureVector-BasedTopic Detection SchemesforText Streams.Proceedings of the2005International Workshop on Challenges in WebInformation Retrieval andIntegrationWIRI’05, Japan.
- Won YY, Wenwu C, Tae-SangC(2005)Applied NumericalMethodUsingMatlab.

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

- Algebraic Geometry
- Analytical Geometry
- Axioms
- Complex Analysis
- Differential Equations
- Fourier Analysis
- Hamilton Mechanics
- Integration
- Noether's theorem
- Physical Mathematics
- Quantum Mechanics
- Quantum electrodynamics
- Relativity
- Riemannian Geometry
- Theoretical Physics
- Theory of Mathematical Modeling
- Topology
- mirror symmetry
- vector bundle

- Total views:
**9362** - [From(publication date):

June-2016 - Feb 28, 2020] - Breakdown by view type
- HTML page views :
**9177** - PDF downloads :
**185**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2020-21