Gerando Matrizes Definidas Positivas Simétricas Usando Índices

8

Eu estava tentando executar casos de teste para CG e preciso gerar:

matrizes definidas positivas simétricas
de tamanho> 10.000
DENSA COMPLETA
Usando apenas índices de matriz e, se necessário, 1 vetor (Como $A(i,j) = \dfrac{x(i) - x(j)}{(i+j)}$ )
Com número de condição menor que 1000.

Eu tentei:

Gerando matrizes aleatórias usando A=rand(N,N)e, em seguida, A'Apara torná-lo Sym. PD. [Isso aumenta o número da condição]
Usando o vetor appraoch como mostrado, mas não consigo obter uma função (x,i,j)que garanta o Sym e o PD.

Depois de muita experimentação, criei:

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

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

Mas isso é PD até cerca de 500x500.

XLATMR . [Com toda a classificação e redimensionamento, é muito difícil de entender. Especialmente porque eu não consigo entender a álgebra linear subjacente]

Alguém pode me dar uma função em x (vetor) ei, j (índices) que atenda aos requisitos acima?

linear-algebra Inquérito
fonte

1

Tente adicionar um número grande

(na ordem do número da condição) às entradas diagonais da sua matriz. Isso equivale a adicionar

a cada um dos seus valores próprios e deve melhorar o número da condição.

α

$\alpha$

α

$\alpha$

Aron Ahmadia 28/03/12

@AronAhmadia, funciona de forma brilhante! Obrigado! No entanto, qual número grande devo adicionar? Eu tentei o próprio N e funcionou até 5000x5000 (apenas simulações concluídas), usando a+N*eye(N,N)garantirá que funcionará para todos os valores além de 5000? Você pode converter seu comentário em uma resposta?

Inquérito

10

Para obter uma matriz definida positiva densa com o número de condição barato, escolha uma matriz diagonal cuja diagonal consiste em números de (que serão os valores próprios), com e escolhido pelo menos uma vez e um vetor . Em seguida, aplique uma transformação de similaridade, por meio de transformações de Householder, para formar a matriz , em que $c$ $D$ $[1,c]$ $1$ $c$ $u$ $A:=(I-tuu^T)D(I-tuu^T)$ . $t=2/u^Tu$

Para formar essa matriz com operações , calcule , , em operações e, em seguida, como . (Se você escolher $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)$

$D$

$\alpha$ $A$ $\alpha$ $\alpha=\|A\|$

Arnold Neumaier
fonte

Isto é perfeito!

Inquérito

Como devo alterar o algoritmo para fornecer matrizes quando forneço os valores de eigen? Por exemplo, eu quero uma matriz não simétrica com valores próprios 1,-1,2,-2...50,-50.

Inquérito 31/03

1

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

$D=Diag(-50:50)$ na receita acima fornece esses autovalores, mas com essa opção a matriz agora é simétrica indefinida, e o CG não resolveria esse problema. E no seu comentário você ainda pede uma matriz não simétrica, pois o CG também não se aplica. Talvez seja melhor fazer uma nova pergunta com o que exatamente você deseja.

Arnold Neumaier 31/03

3

Tente adicionar um número grande (na ordem da norma da matriz) às entradas diagonais da sua matriz. Isso equivale a adicionar a cada um dos seus autovalores e deve melhorar o número da condição reduzindo a diferença entre os autovalores maiores e menores. $\alpha$ $\alpha$

Aron Ahmadia
fonte

1

Para referência, consulte en.wikipedia.org/wiki/Tikhonov_regularization

Emre

2

Eu não tenho certeza de como você faria isso com apenas um vetor, mas com dois vetores aleatórios e de tamanho , você pode produzir uma matriz semi-definida positiva via onde é uma rotação no plano dos eixos e . $x$ $\theta$ $N$

U = \prod_{i} R_{i} (θ_{i}) A = U diag (abs (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$

Se você deseja melhorar o número da condição, pode adicionar um valor positivo fixo a e redimensionar, se necessário. $x$

Último folego
fonte

Sinto muito, mas minha matemática ainda não é tão boa assim. Does denote transposição? O que significa rotação no plano? Além disso, armazenar 2 vetores será um pouco caro, mas ainda assim, esse visual é muito interessante.

U^{*}

$U^*$

Inquérito

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)$ é a matriz de rotação. denota a matriz transposta conjugada complexa (assumindo que tudo é real, é apenas a transposição).

U^{*}

$U^\ast$

Death Breath

2

Uma maneira totalmente diferente de fazer isso seria assim: considere um vetor aleatório , então é uma matriz de classificação um com autovalores iguais a zero e autovalor estritamente positivo igual a com vetor próprio . Também é simétrico. $x$ $A=xx^T$ $N-1$ $\|x\|^2$ $x$

Para construir uma matriz SPD densa, adicione muitas dessas matrizes de classificação 1. Em outras palavras, se você possui vetores (por exemplo, vetores aleatórios), então é SPD se e se os vetores forem linearmente independentes (se eles não são linearmente independentes, então é semidefinido positivo). Você pode verificar se seus vetores (ou os primeiros vetores que você desenha do processo aleatório) são linearmente independentes usando a ortogonalização sucessiva de Gram-Schmidt, mas também é provável que você obtenha uma matriz SPD se simplesmente escolher vetores $M$ $x_i$

A = \sum_{i = 1}^{M} x_{i} x_{i}^{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
fonte

Gerando Matrizes Definidas Positivas Simétricas Usando Índices

Respostas: