云计算-结构矩阵计算及在数字图像复原中的应用.pdf

摘要

摘 要

结构线性系统在数学、科学计算和工程中的不同领域都有广泛的应用, 如: 偏

微分方程、信号与图像处理、排队网络、积分方程、时间序列分析、控制论等等.

特别是在实际应用中日益增长的复杂性的驱动下, 设计快速的数值可靠的算法求解

大规模结构问题已变得日益重要. 这方面最主要的挑战是需要发展速度快与数值精

度高的算法, 但这两个要求常常不可兼得, 以至于在许多情况下, 怎样设计快速的数

值可靠的算法求解大规模结构线性方程组依然是一个关键问题. 本文首先考虑了大

型结构线性方程组的高性能算法求解问题.

的Toeplitz线性系统的一些结果, 讨论分析了CSS迭代的收敛性以及参数的选取,

简单的数值测试结果验证了CSS迭代法的有效性.

研究了改进的T. Chan预条件共轭梯度方法求解Toeplitz线性系统, 特别是得到

了系数矩阵为Hermitian对称正定时的一些重要结果. 讨论了改进的T. Chan预条件

共轭梯度方法求解Toeplitz线性系统的运算量, 并分析了它的收敛性问题. 给出的数

值结果验证了该预条件方法是有效的.

图像复原是去除或者减轻观察图像中的退化的过程. 数学上, 图像复原模型可

以用一个离散的病态问题描述Kf + η = g, 其中, 大型的结构矩阵K表示模糊现象,

向量g表示观察的噪声模糊图像, 向量η代表噪声. 给定g, K, 某些情况下, 还给定一

些噪声的统计信息, 图像复原的目的是恢复得到原始图像f的一个近似图像. 通常情

数(PSF)是否对称, 张量积近似的方法成功应用到全对称边界条件的图像复原问题.

I

摘要

应该指出的是, 当真实PSF的尺寸很小时, 张量积近似算法的复杂性是小的, 因为实

现该算法的所有计算都是通过在大矩阵里的左上角小矩阵的计算来完成的.

研究了全局Krylov方法求解病态的图像复原问题. 结合一个基于差异原理的停

止准则, 全局Krylov方法可以充当一种好的正则化方法求图像复原问题. 为了加速

全局迭代方法的收敛性, 在该方法重启前, 将计算的近似解投影到非负矩阵的集合

上. 一些来自图像复原问题的数值仿真验证了全局迭代方法的有效性.

研究了一种特别的Hermitian和反-Hermitian分裂(SHSS)迭代方法求解图像复原

Structured linear systems frequently arise in a variety of applications in different

fields of mathematics, scientific computing and engineering, such as partial differential

equations, signal and image processing, queueing networks, integral equations, time-

series analysis and control theory, etc. The design of fast and numerically reliable al-

gorithms for large-scale problems with structure has become an increasingly important

activity, especially in recent years, driven by the ever-increasing complexity of practical

applications. The major challenge in this area is to develop algorithms that blend speed

and numerical accuracy. These two requirements often have been regarded as competitive,

requires no multiplications and O(n

linear systems of the generalized Pascal matrices are also considered.

The results about the centrosymmetric and skew-centrosymmetric splitting(CSS) it-

erative method for solving the positive definite Toepltiz linear systems are presented. The

analysis about the convergence and the choice of the parameter of the presented method

is given. Some simple numerical results show the effectiveness of the CSS iteration.

A modified T. Chan’s preconditioner for solving Toeplitz linear systems with the pre-

conditioned conjugate gradient (PCG) method is developed. Especially, some important

results when the matrices are Hermitian positive definite Toeplitz matrices are derived.

vector representing the observed image, and η is a vector representing noise. Restoration

methods attempt to recover an approximation to the original image f, given g, K, and, in

some cases, statistical information about the noise. Often K is severely ill-conditioned,

and g is corrupted with noise. Thus, standard techniques to solve Kf = g are likely to

produce solutions that are highly corrupted with noise. In general, a regularization method

can address these problems efficiently. One may employ it to compute the approximate

solutions that are less sensitive to noise than the naive solution. The dissertation also

The use of the whole-sample symmetric boundary conditions (BCs) in image restora-

tion is considered. The blurring matrices constructed from the point spread func-

tions (PSFs) for the BCs have block Toeplitz-plus-PseudoHankel with Toeplitz-plus-

PseudoHankel blocks structures. Regardless of symmetric properties of the PSFs, a tech-

nique of Kronecker product approximations is successfully applied to restore images with

the whole-sample symmetric BCs. It is noted that when the size of the true PSF is small,

the computational complexity of the algorithm obtained for the Kronecker product ap-

proximation of the resulting matrix is very small, since all calculations in the algorithm

are implemented only at the upper left corner submatrices of the big matrices.

The global Krylov methods for ill-posed image restoration problem are proposed.

A special Hermitian and skew-Hermitian splitting (SHSS) iterative method is estab-

lished for solving the linear systems from image restoration. The approach is based on an

augmented system formulation. The convergence and operation cost of the SHSS iterative

method for image restoration problems are discussed. The optimal parameter minimizing

the spectral radius of the iteration matrix is derived. Finally, the successive overrelaxation

(SOR) acceleration scheme for the SHSS iterative method is discussed.