如何找到近似奇异矩阵的逆? [英] How to find an inverse of a nearly singular matrix?

问题描述

我正在实现使用C ++和CUDA的算法.但是，当我试图找到特殊矩阵的逆矩阵时，我遇到了麻烦.此矩阵具有以下功能:

1. 它是一个方阵(假设:(m+3)x(m+3),m>0)；
2. 它的转置矩阵是它的自身；
3. 其主要对角线必须为零；
4. 它的右下角必须有一个3x3的零矩阵；
5. 您可以考虑以下形式的矩阵:H = [A，B; B'，0];

我尝试了一些方法，但都失败了:

1. 伪逆矩阵:

   我最初使用matlab并尝试使用inv(H'* H)时出现错误或警告: 警告:矩阵对于工作精度很重要 或 矩阵接近奇异或缩放不良

2. 一些近似方法:

   参考资料在这里:逼近我发现了两种方法:Gauss-Jordan消除和Cholesky分解.当我在Matlab中尝试chol时，出现以下错误: 错误:矩阵必须是正定的

有人可以给我一些建议吗?

解决方案

最好了解一些有关您的特定问题的信息，特别是如果您需要反过来的本身或如果您只需要反转线性方程组.我会尽力为您提供这两种情况的指导.

让我首先考虑一下您的矩阵几乎是奇异的，因此您的系统是病态的.

确定近似奇异矩阵的逆数

正如上面的评论和答案所阐明的那样，寻找几乎单数的矩阵的逆是没有意义的.有意义的是构造矩阵的 regularized 逆.您可以通过对矩阵进行光谱分解(奇异值分解或SVD)来做到这一点.更详细地讲，您可以构造奇异系统，删除最小有效奇异值(它们是矩阵近乎奇异行为的来源)，然后使用奇异值和向量形成近似逆.当然，在这种情况下， A * A_inv 仅会给出单位矩阵的近似值.

如何在GPU上完成此操作?首先，我想说用C ++或CUDA实现SVD算法绝非易事.您应根据需要的精度选择多种技术，例如确定奇异值.无论如何，Matlab都有一组在GPU上运行的线性代数函数.另外， CULA 和岩浆是两个提供SVD计算例程的库.另外，您可以考虑使用 Arrayfire ，它还提供了线性代数例程，包括SVD.

反转几乎单一的系统

在这种情况下，您应该考虑使用某种 Tikhonov 正则化，包括将线性系统的求逆公式化为优化问题并添加正则化项，这可能取决于您已经了解的未知特征.

对于上述两种情况，我建议阅读一些理论.这本书

M.Bertero，P.Boccacci，成像逆问题简介

如果必须找到近似逆或将线性系统显式求逆，将很有用.

I am realizing an algorithm using C++ and CUDA. But I got into trouble when I tried to find an inverse of a special matrix. This matrix has following features:

1. it is a square matrix (suppose: (m+3)x(m+3),m>0);
2. its transpose matrix is its self;
3. its main diagonal must be zeros;
4. it must have a 3x3 zero matrix on the bottom right corner;
5. you can consider this matrix in this form:H = [A ,B ;B' ,0];

I have tried some methods but all failed:

1. pseudo-inverse matrix:

   I used matlab at first and got error or warning when I tried to use inv(H'*H): Warning: Matrix is singular to working precision or matrix is close to singular or badly scaled

2. some approximation methods:

   the reference material is here:approximation I found two methods:Gauss-Jordan elimination and Cholesky decomposition.when I tried chol in matlab, i get following error:Matrix must be positive definite

can anybody give me some suggestions?

解决方案

It would be good to know some more information on your specific problem and, in particular, if you need the inverse per se or if you need to just invert a linear system of equations. I will try to give you directions for both the cases.

Let me start from the consideration that that your matrix is nearly singular and so your system is ill-conditioned.

DETERMINING THE INVERSE OF A NEARLY SINGULAR MATRIX

As it has been clarified in the comments and answers above, seeking the inverse of a nearly singular matrix is meaningless. What makes sense is to construct a regularized inverse of your matrix. You can do that by resorting to the spectral decomposition (Singular Value Decomposition, or SVD) of your matrix. More in detail, you can construct the singular system, remove the least significant singular values which are the source for the nearly singular behavior of the matrix, and then use the singular values and vectors to form an approximate inverse. Of course, in this case A*A_inv will only give an approximation of the identity matrix.

How can this be done on GPU? First, let me say that implementing an SVD algorithm in C++ or CUDA is by no means an easy task. There are several techniques among which you should choose depending on the accuracy you need, for example, to determine the singular values. Anyway, Matlab has a set of linear algebra functions working on GPU. Also, CULA and Magma are two libraries offering SVD calculation routines. Also, you can consider using Arrayfire which also offers linear algebra routines, including the SVD.

INVERTING A NEARLY SINGULAR SYSTEM

In this case, you should consider using some sort of Tikhonov regularization, which consists to formulating the inversion of the linear system as an optimization problem and adding a regularization term, which may depend on the features you already know about your uknowns.

For both the cases above, I recommend reading some theory. The book

M. Bertero, P. Boccacci, Introduction to Inverse Problems in Imaging

would be useful either if you have to find an approximate inverse or if you have the explicitly invert the linear system.

这篇关于如何找到近似奇异矩阵的逆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！