生成与一组向量线性无关的随机向量 [英] Generating random vector that's linearly independent of a set of vectors

问题描述

我正在尝试提出一种算法，该算法将允许我生成一个随机的 N 维实值向量，该向量与一组已生成的向量线性无关.我不想强迫它们正交，只是线性无关.我知道 Graham-Schmidt 存在于正交化问题中，但是否有一种更弱的形式只给你线性无关的向量?

I'm trying to come up with an algorithm that will allow me to generate a random N-dimensional real-valued vector that's linearly independent with respect to a set of already-generated vectors. I don't want to force them to be orthogonal, only linearly independent. I know Graham-Schmidt exists for the orthogonalization problem, but is there a weaker form that only gives you linearly independent vectors?

推荐答案

Step 1. Generate random vector vr.

Step 1. Generate random vector vr.

步骤 2. 将 vr 复制到 vo 并更新如下:对于 v1、v2 中每个已经生成的向量 v... vn，减去vo在vi上的投影.

Step 2. Copy vr to vo and update as follows: for every already generated vector v in v1, v2... vn, subtract the projection of vo on vi.

结果是一个与 v1, v2... vn 跨越的子空间正交的随机向量.如果那个子空间是一个基，那么它当然是零向量:)

The result is a random vector orthogonal to the subspace spanned by v1, v2... vn. If that subspace is a basis, then it is the zero vector, of course :)

可以根据vr的范数与vo的范数的比较来判断初始向量是否线性无关.非线性独立向量的 vo 范数为零或接近零(某些数值精度问题可能使其成为几倍 epsilon 数量级的非零小数，这可以以依赖于应用程序的方式进行调整).

The decision of whether the initial vector was linearly independent can be made based on the comparison of the norm of vr to the norm of vo. Non-linearly independent vectors will have a vo-norm which is zero or nearly zero (some numerical precision issues may make it a small nonzero number on the order of a few times epsilon, this can be tuned in an application-dependent way).

伪代码:

vr = random_vector()
vo = vr
for v in (v1, v2, ... vn):
    vo = vo - dot( vr, v ) / norm( v )
if norm(vo) < k1 * norm(vr):
    # this vector was mostly contained in the spanned subspace
else:
    # linearly independent, go ahead and use

这里 k1 是一个很小的数，可能是 1e-8 到 1e-10?

Here k1 is a very small number, 1e-8 to 1e-10 perhaps?

您也可以通过 vr 和子空间之间的 角度:在这种情况下，将其计算为 theta = arcsin(norm(vo)/norm(vr)).显着不同于零的角度对应于线性无关向量.

You can also go by the angle between vr and the subspace: in that case, calculate it as theta = arcsin(norm(vo) / norm(vr)). Angles substantially different from zero correspond to linearly independent vectors.

这篇关于生成与一组向量线性无关的随机向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！