不确定线性系统的随机解 [英] Random solutions of undetermined linear systems

问题描述

考虑一个未确定的线性方程组Ax=b.

我想找到一组向量x_1, ..., x_n，使它们全部求解Ax=b，并且它们之间的差异应尽可能大.

I would like to find a set of vectors x_1, ..., x_n such that they all solve Ax=b and they are as different between each other as possible.

第二部分实际上并不那么重要；我对每次调用它都会返回Ax=b的随机解的算法感到满意.

The second part is actually less important; I would be happy with an algorithm that returns a random solution of Ax=b every time I call it.

我知道scipy.sparse.linalg.lsqr和numpy.linalg.lstsq返回欠定线性系统Ax=b的稀疏解(以最小二乘法表示)，但是我并不关心解的性质；我只想要Ax=b的任何解决方案，只要可以生成很多不同的解决方案即可.

I know that scipy.sparse.linalg.lsqr and numpy.linalg.lstsq return a sparse solution (in terms of least squares) of an underdetermined linear system Ax=b, but I don't care about the properties of the solution; I just want any solution of Ax=b, as long as I can generate a bunch of different solutions.

实际上，scipy.sparse.linalg.lsqr和numpy.linalg.lstsq应该遵循一个迭代过程，从一个解决方案跳到另一个解决方案，直到找到最小平方最小的解决方案为止.那么，是否有一个python模块可以让我在没有特定目标的情况下在解决方案之间跳转并返回它们?

In fact, scipy.sparse.linalg.lsqr and numpy.linalg.lstsq should follow an iterative process that jumps from a solution to an other until they find a solution that seems to be the minimum in terms of least squares. Well, is there a python module that lets me jump between solutions without a particular objective, and returns them?

推荐答案

对于欠定系统 A·x = b ，您可以计算系数矩阵的空空间 A .空空间 Z 是一组基本矢量，跨越了 A 的子空间，使得 A·Z = 0 .换句话说， Z 的列是与 A 中的所有行正交的向量.这意味着对于 x' 到 A·x = b 的任何解决方案em> ，然后 x' + Z·c 向量 c .

For the underdetermined system A·x = b you can compute the null space of your coefficient matrix A. The null space, Z, is a set of basis vectors spanning a subspace of A such that A·Z = 0. In other words, the columns of Z are vectors that are orthogonal to all of the rows in A. This means that for any solution x' to A·x = b, then x' + Z·c must also be a solution for any arbitrary vector c.

因此，如果您想对 A·x = b 的随机解进行抽样，则可以以下:

So if you wanted to sample random solutions to A·x = b then you could do the following:

1. 找到任何解决方案 x' 到 A·x = b .您可以使用 np.linalg.lstsq ，该解决方案找到了一种将 x' 的L2范数最小化的解决方案.
2. 找到 A 的空空间. 上一个问题介绍了许多不同的方法.
3. 对随机矢量 c 进行采样，然后计算 x' + Z· c .这将是 A·x = b 的解决方案.

1. Find any solution x' to A·x = b. You could do this using np.linalg.lstsq, which finds a solution that minimizes the L2 norm of x'.
2. Find the null space of A. There are a number of different ways to do this, most of which are covered in this previous question.
3. Sample a random vector c, and compute x' + Z·c. This will be a solution to A·x = b.

例如:

import numpy as np
from scipy.linalg import qr


def qr_null(A, tol=None):
    """Computes the null space of A using a rank-revealing QR decomposition"""
    Q, R, P = qr(A.T, mode='full', pivoting=True)
    tol = np.finfo(R.dtype).eps if tol is None else tol
    rnk = min(A.shape) - np.abs(np.diag(R))[::-1].searchsorted(tol)
    return Q[:, rnk:].conj()


# An underdetermined system with nullity 2
A = np.array([[1, 4, 9, 6, 9, 2, 7],
              [6, 3, 8, 5, 2, 7, 6],
              [7, 4, 5, 7, 6, 3, 2],
              [5, 2, 7, 4, 7, 5, 4],
              [9, 3, 8, 6, 7, 3, 1]])
b = np.array([0, 4, 1, 3, 2])

# Find an initial solution using `np.linalg.lstsq`
x_lstsq = np.linalg.lstsq(A, b)[0]

# Compute the null space of `A`
Z = qr_null(A)
nullity = Z.shape[1]

# Sample some random solutions
for _ in range(5):
    x_rand = x_lstsq + Z.dot(np.random.rand(nullity))
    # If `x_rand` is a solution then `||A·x_rand - b||` should be very small
    print(np.linalg.norm(A.dot(x_rand) - b))

示例输出:

3.33066907388e-15
3.58036167305e-15
4.63775652864e-15
4.67877015036e-15
4.31132637123e-15

c 向量的空间是无限的-您必须对如何采样这些向量做出选择.

The space of possible c vectors is infinite - you'll have to make some choice as to how you want to sample these.

这篇关于不确定线性系统的随机解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！