Generando matrices simétricas positivas definidas usando índices

8

Estaba tratando de ejecutar casos de prueba para CG y necesito generar:

matrices definidas positivas simétricas
de tamaño> 10,000
DENSIDAD COMPLETA
Usando solo índices de matriz y, si es necesario, 1 vector (como ) $A(i,j) = \dfrac{x(i) - x(j)}{(i+j)}$
Con número de condición inferior a 1000.

Yo he tratado:

Generando matrices aleatorias usando A=rand(N,N)y luego A'Apara convertirlo en Sym. PD. [Esto aumenta el número de condición]
Usando el vector appraoch como se muestra, pero parece que no puedo obtener una función (x,i,j)que garantice Sym y PD.

Después de mucha experimentación, se me ocurrió:

a(it,jt) = (vec(it)+vec(jt))/((it-1)^2+(jt-1)^2);Si $it \neq jt$

a(it,it) = x(it)si $it=jt$

Pero esto es PD hasta aproximadamente 500x500.

XLATMR . [Con todas las calificaciones y escalas, es muy difícil de entender. Especialmente porque no puedo entender el álgebra lineal subyacente]

¿Alguien puede darme una función en x (vector) e i, j (índices) que cumpla con los requisitos anteriores?

linear-algebra Encuesta
fuente

1

Intente agregar un gran número (en el orden del número de condición) a las entradas diagonales de su matriz. Esto es equivalente a agregar a cada uno de sus valores propios y debería mejorar el número de condición.

α

$\alpha$

α

$\alpha$

Aron Ahmadia

@AronAhmadia, ¡funciona genial! ¡Gracias! Sin embargo, ¿qué gran número debo agregar? Intenté N en sí y funcionó hasta 5000x5000 (solo terminé las simulaciones), ¿se a+N*eye(N,N)asegurará de que funcionará para todos los valores más allá de 5000? ¿Puedes convertir tu comentario en una respuesta?

Investigación

10

Para obtener una matriz definida positiva densa con el número de condición bajo costo, elija una matriz diagonal cuya diagonal consista en números de (que serán los valores propios), con y elegidos al menos una vez, y un vector . Luego aplique una transformación de similitud, a través de las transformaciones de Householder, para formar la matriz , donde . $c$ $D$ $[1,c]$ $1$ $c$ $u$ $A:=(I-tuu^T)D(I-tuu^T)$ $t=2/u^Tu$

Para formar esta matriz con operaciones , calcule , , en operaciones y luego como . (Si elige como el vector todo en uno, el número de multiplicaciones necesarias es solo . $O(n^2)$ $v:=Du$ $s:=t^2u^Tv/2$ $w:=tv-su$ $O(n)$ $A$ $A=D-uw^T-wu^T$ $u$ $O(n)$

Tenga en cuenta que el comportamiento de CG depende mucho de la distribución de valores propios, que se puede confirmar fácilmente variando . $D$

(Agregar a una matriz simétrica arbitraria necesita más grande que el valor propio más grande. Esto es difícil de calcular; por lo tanto, habría que elegir , pero el número de condición generalmente será muy pequeño , no es un caso de prueba realista para CG). $\alpha$ $A$ $\alpha$ $\alpha=\|A\|$

Arnold Neumaier
fuente

¡Esto es perfecto!

Investigación

¿Cómo debo cambiar el algoritmo para proporcionarme matrices cuando proporciono los valores propios? Por ejemplo, quiero una matriz no simétrica con valores propios 1,-1,2,-2...50,-50.

Investigación

1

en la receta anterior le da estos valores propios, pero con esta elección la matriz ahora es simétrica indefinida, y CG no resolvería tal problema. Y en su comentario incluso pide una matriz no simétrica, donde el CG tampoco se aplica. Tal vez sea mejor hacer una nueva pregunta con lo que precisamente quieres.

D = D i a g (- 50 : 50)

$D=Diag(-50:50)$

Arnold Neumaier

3

Intente agregar un gran número (en el orden de la norma de la matriz) a las entradas diagonales de su matriz. Esto es equivalente a agregar a cada uno de sus valores propios y debería mejorar el número de condición al reducir la brecha entre los valores propios más grandes y más pequeños. $\alpha$ $\alpha$

Aron Ahmadia
fuente

1

Para referencia, consulte en.wikipedia.org/wiki/Tikhonov_regularization

Emre

2

No estoy seguro de cómo lo haría con un solo vector, pero con dos vectores aleatorios y de tamaño , puede producir una matriz semi-definida positiva a través de $x$ $\theta$ $N$ donde es una rotación en el plano de los ejes y .

U = \prod_{yo} R_{yo} (θ_{yo}) UNA = U diag (abdominales (X)) U^{*}

$U=\prod_i R_i(\theta_i)\\ A=U\mbox{diag}(\mbox{abs}(x)) U^\ast$

R_{i} (\cdot)

$R_i(\cdot)$

i

$i$

i + 1 mod N

$i+1 \mbox{ mod } N$

Si desea mejorar el número de condición, puede agregar un valor positivo fijo a y volver a escalar si es necesario. $x$

Respiro de muerte
fuente

Lo siento, pero mis matemáticas aún no son tan buenas. ¿

denota transposición? ¿Qué significa la rotación en el plano? Además, almacenar 2 vectores será un poco caro, pero aún así, este aspecto le gusta de una manera muy interesante.

U^{*}

$U^*$

Investigación

R_{i} (θ_{i}) = (\begin{matrix} 1 & 0 & \dots \\ 0 & ⋱ \\ \cos θ_{i} & \sin θ_{i} \\ - \sin θ_{i} & \cos θ_{i} \\ 1 \\ ⋱ \end{matrix})

$R_i(\theta_i)=\left(\begin{matrix} 1 & 0 & \cdots \\ 0 & \ddots \\ &&\cos \theta_i & \sin \theta_i \\ & & -\sin \theta_i & \cos \theta_i\\ & & & &1 \\ && & & & \ddots\end{matrix}\right)$

U^{*}

$U^\ast$

2

$x$ $A=xx^T$ $N-1$ $\|x\|^2$ $x$

$M$ $x_i$

UNA = \sum_{yo = 1}^{METRO} X_{yo} X_{yo}^{T}

$A = \sum_{i=1}^M x_i x_i^T$

M \geq N

$M\ge N$

x_{i}

$x_i$

A

$A$

M

$M$

M \geq N

$M\ge N$

M ≫ N

$M \gg N$

Wolfgang Bangerth
fuente

Generando matrices simétricas positivas definidas usando índices

Respuestas: