从一个欠定系统中删除无法解方程

我的程序试图解决一个线性方程组。为了做到这一点，它组装矩阵coeff_matrix和矢量value_vector，并采用本征来解决这些问题，如：从一个欠定系统中删除无法解方程

Eigen::VectorXd sol_vector = coeff_matrix 
     .colPivHouseholderQr().solve(value_vector);

的问题是，该系统既可以是大于和小于确定。在前一种情况下，Eigen或者给出了正确或不正确的解决方案，我使用coeff_matrix * sol_vector - value_vector来检查解决方案。

但是，请考虑等式的以下系统：

a + b - c  = 0 
     c - d = 0 
     c  = 11 
     - c + d = 0

在这种特殊情况下，本征正确地解决了三个后一个方程组，但也给出了a和b解决方案。

我想什么来实现的是，仅只有一个解决办法方程将得到解决，其余的人（这里的第一个公式）将在系统中保留。

换句话说，我在寻找，找出一个方法，公式可以在公式中给定系统的及时解决，而不能因为会有不止一个解决方案。

你可以建议实现这一什么好办法？

编辑：请注意，在大多数情况下，矩阵将不是正方形。我在这里增加了一行，只是为了说明过度测定也可能发生。

来源

2012-07-10 Michał Górny

我想你想要的是singular value decomposition (SVD)，它会给你你想要的。经过奇异值分解后，“只有一个解的方程将被求解”，并且解是伪逆。它也会给你零空间（无限解来自哪里）和零空间（不一致来自哪里，即无解）。

来源

2012-07-10 15:36:00 chaohuang

你能指点我一些页面或文件，这将帮助我了解如何使用它？维基百科讲了很多数学... – 2012-07-10 15:51:05

实际上，它需要一个相当的数学来学习SVD，这是线性代数的高潮。我只是搜索了一些介绍，看[这里]（http://stat.asu.edu/~eric/msri/matlab2.pdf）和[here]（http://www.math.pitt.edu/~sussmanm /2071Spring08/lab09/index.html）。 HTH。 – chaohuang 2012-07-10 16:01:25

谢谢。我稍微移动了一些空格并组装了一些我作为解决方案粘贴的东西（因为注释对于实际代码来说并不好）。不知道我是否发明了真正的东西，或者只是一个随机模式。 – 2012-07-10 17:50:38

你需要的是计算系统的决定因素。如果行列式为0，那么你有无数的解决方案。如果行列式很小，解决方案就存在了，但我不相信计算机找到的解决方案（这会导致数值不稳定）。

下面是什么决定一个链接，如何计算呢：http://en.wikipedia.org/wiki/Determinant

需要注意的是高斯消元法也应努力：http://en.wikipedia.org/wiki/Gaussian_elimination 使用这种方法，你最终以0线，如果有无限解决方案的数量。

编辑

万一矩阵不是方形，首先需要提取方阵。有两种情况：

你有比方程更多的变量：那么你有没有解决方案，或无限数量的他们。
你比变量更多的方程：在这种情况下，发现非空行列式的一个子方阵。解决这个矩阵并检查解决方案。如果解决方案不合适，这意味着你没有解决方案。如果解符合，则意味着额外方程线性依赖于提取方程。

在这两种情况下，在检查矩阵的维度之前，只用0删除行和列。

对于高斯消元法，它应该直接与非方阵工作。但是，这次您应该检查非空行（即具有某些非0值的行）的数量是否等于变量的数量。如果它更少，则有无数解决方案，如果更多，则没有任何解决方案。

来源

2012-07-10 14:24:20 PierreBdR

行列式仅在平方矩阵中有效。 – 2012-07-10 14:35:51

@MichałGórny我编辑了非方案的解决方案。但只有矩阵矩阵承认一个独特的解决方案另外，你的例子是一个矩形矩阵。 – PierreBdR 2012-07-10 14:48:46

我的例子也是一个超定矩阵，其中两个变量有独特的解决方案。没有那么简单......顺便说一下，我正在考虑类似的东西，但恐怕所有这些计算都会使解决方案变得非常低效。 – 2012-07-10 15:23:26

基于SVD的评论，我能够做这样的事：

Eigen::FullPivLU<Eigen::MatrixXd> lu = coeff_matrix.fullPivLu(); 

Eigen::VectorXd sol_vector = lu.solve(value_vector); 
Eigen::VectorXd null_vector = lu.kernel().rowwise().sum();

AFAICS，对应于单一的解决方案null_vector行是0 s，而对应的非确定的解决方案的有1小号。我可以在我的所有例子中使用默认的阈值Eigen重现这一点。

但是，我不确定我是否正在做某件事，或者只是注意到一种随机模式。

来源

2012-07-10 17:49:12

如果我正确记住了我的线性代数，它似乎是正确的。我已经在应用线性代数检查中使用了类似的技巧，允许我们使用matlab，但必须逐步制定解决方案。 – 2012-07-29 03:40:56

从一个欠定系统中删除无法解方程

回答

相关问题