Resolvendo repetidamente

Estou usando o MATLAB para resolver um problema que envolve resolver a cada passo do tempo, em que b muda com o tempo. No momento, estou conseguindo isso usando o MATLAB :$\mathbf{A} \mathbf{x}=\mathbf{b}$$\mathbf{b}$mldivide

x = A\b

Eu tenho a flexibilidade de fazer quantas pré-computações forem necessárias, por isso estou me perguntando se existe um método mais rápido e / ou mais preciso do que isso mldivide. O que normalmente é feito aqui? Obrigado a todos!

A coisa mais óbvia que você pode fazer é pré-calcular

[L,U] = lu(A) ~ O (n ^ 3)

Então você apenas calcula

x = U \ (L \ b) ~ O (2 n ^ 2)

Isso reduziria enormemente o custo e o tornaria mais rápido. A precisão seria a mesma.

Realizamos alguns laboratórios de informática extensivos em nossos cursos de computação científica sobre esse tópico. Para os cálculos "pequenos" que fizemos lá, o operador de barra invertida do Matlab sempre foi mais rápido do que qualquer outra coisa, mesmo depois de otimizarmos nosso código o máximo possível e reorganizarmos todas as matrizes de antemão (por exemplo, com Reverse Cuthill McKee solicitando matrizes esparsas) .

Você pode conferir uma de nossas instruções de laboratório . A resposta à sua pergunta é abordada (em breve) na página 4.

Um bom livro sobre o assunto foi escrito, por exemplo, por Cheney .

$A$$n\times n$ $Ax_i = b_i$$i=1\dots m$$m$

V = inv(A);
...
x = V*b;

$O(n^3)$inv(A)$O(n^2)$V*b$m$

>> n = 5000;
>> A = randn(n,n);
>> x = randn(n,1);
>> b = A*x;
>> rcond(A)
ans =
   1.3837e-06
>> tic, xm = A\b; toc
Elapsed time is 1.907102 seconds.
>> tic, [L,U] = lu(A); toc
Elapsed time is 1.818247 seconds.
>> tic, xl = U\(L\b); toc
Elapsed time is 0.399051 seconds.
>> tic, [L,U,p] = lu(A,'vector'); toc
Elapsed time is 1.581756 seconds.
>> tic, xp = U\(L\b(p)); toc
Elapsed time is 0.060203 seconds.
>> tic, V=inv(A); toc
Elapsed time is 7.614582 seconds.
>> tic, xv = V*b; toc     
Elapsed time is 0.011499 seconds.
>> [norm(xm-x), norm(xp-x), norm(xl-x), norm(xv-x)] ./ norm(x)
ans =
   1.0e-11 *
    0.1912    0.1912    0.1912    0.6183

$A^{-1}$$LU$$m>125$

Algumas notas

Para análise de estabilidade e erro, consulte os comentários a essa resposta diferente , especialmente a de VictorLiu.

$m\ll n$

O tempo foi realizado com o Matlab R2011b em um computador de 12 núcleos com uma média de carga UNIX razoavelmente constante de 5; melhor tic, tochorário de três sondas.

Dê uma olhada nesta pergunta , as respostas mostram que mldivideé bastante inteligente e também oferece sugestões sobre como ver o que o Matlab usa para resolver A\b. Isso pode lhe dar uma dica sobre as opções de otimização.

O uso da barra invertida é mais ou menos equivalente a inv(A)*B, se você o estiver codificando livremente, o último pode ser mais intuitivo. Eles são praticamente os mesmos (apenas diferentes na maneira como a computação é realizada), embora você deva verificar a documentação do Matlab para obter esclarecimentos.

Para responder sua pergunta, a barra invertida geralmente é boa, mas depende das propriedades da matriz de massa.