Solução explícita numericamente estável de sistema linear pequeno

11

Eu tenho um sistema linear não homogêneo

A x = b

$Ax=b$

onde é uma matriz real com . O espaço nulo de é garantido como de dimensão zero, portanto a equação possui um inverso exclusivo . Como o resultado entra no lado direito de uma ODE, que pretendo resolver usando um método adaptativo, é importante que a solução seja suave em relação às pequenas variações dos elementos de e . Devido a esse requisito e à pequena dimensionalidade, pensei em implementar fórmulas explícitas para $A$ $n\times n$ $n\leq 4$ $A$ $x=A^{-1} b$ $A$ $b$ $A^{-1} b$ . Os elementos podem ser exatamente zero ou assumir valores muito diferentes. Minha pergunta é se isso faz sentido para você e se existem expressões estáveis conhecidas para isso. Estou codificando em C para sistemas x86.

linear-algebra ode highsciguy
fonte

Sei que chega muito tarde, mas eis a minha sugestão: como é sabido que a eliminação gaussiana com rotação total é estável, pode fazer sentido codificar o algoritmo para tamanhos pequenos. A rotação complica a matéria, pois existem maneiras de escolher os pivôs sucessivos, levando a conjuntos diferentes de fórmulas; você pode reduzir essa complexidade trocando o que precisa ser trocado, reduzindo o número de casos para .

(n!)^{2}

$(n!)^2$

(n!)^{2}

$(n!)^2$

1^{2} + 2^{2} + \dots n^{2}

$1^2+2^2+\cdots n^2$

Yves Daoust

6

Antes de implementar fórmulas explícitas, eu me perguntava: "vale a pena?":

Vale a pena gastar o tempo escrevendo, depurando e validando essas fórmulas explícitas enquanto você pode facilmente vincular ao BLAS + LAPACK que usa a eliminação gaussiana clássica?
Você espera ganhar estabilidade? Eu não acho que programar fórmulas explícitas (como a regra de Cramer) lhe proporcionará melhor estabilidade, pelo contrário.
Você espera ganhar velocidade? Você já perfilou todo o seu programa? Que fração do tempo é gasta na solução desses sistemas 4x4?
Qual é a probabilidade de que, em um ano, você melhore seu modelo e precise de 5 equações em vez de 4?

Meu conselho: use a combinação BLAS / LAPACK primeiro, veja se funciona, analise o programa inteiro, peça a um aluno para implementar fórmulas explícitas (desculpe, sendo sarcástico aqui) e faça uma comparação em velocidade e robustez.

GertVdE
fonte

O esforço necessário para implementá-lo é de cerca de 15 minutos, porque simplesmente insiro uma matriz geral 1x1, 2x2, 3x3 e 4x4 em um CAS (Maple para mim) e o inverto. Ele retornará um resultado explícito (semelhante ao C) (supostamente baseado na regra de Cramer). Seu segundo ponto é exatamente a minha preocupação. No resultado, haverá produtos de ordem superior dos elementos da matriz. Obviamente, isso pode gerar erros devido ao 'quase cancelamento' dos diferentes termos. Mas a questão é, se é possível escrever o resultado de uma forma em que isso não ocorra. A velocidade não é a principal preocupação neste local.

highsciguy

6

O único resultado inverso explícito que conheço é a Regra de Cramer , que recentemente demonstrou ser computável em (como a eliminação gaussiana; insegura da constante na frente do fator principal, Apesar). $\mathcal{O}(n^{3})$

A matriz inversa de é uma função suave de , desde que , e a solução é certamente uma função suave de , desde que o lado direito do ODE seja suave função de e você evita casos em que é deficiente na classificação, eu acho que seu lado direito seria suave. (Aqui, entendo suave como "pelo menos duas vezes continuamente diferenciável".) $A$ $A$ $\det(A) \neq 0$ $x$ $b$ $x$ $A$

Para ser seguro, provavelmente é melhor garantir que também não seja numericamente deficiente em classificação (ou seja, não possua valores singulares pequenos). $A$

O problema com a Regra de Cramer é que suas propriedades de estabilidade são desconhecidas, exceto (que é estável para a frente, mas não para trás). (Veja Precisão e estabilidade de algoritmos numéricos , 2ª edição, por N. Higham.) Não é considerado um algoritmo confiável; A eliminação gaussiana com giro parcial (GEPP) é favorecida. $n = 2$

Eu esperaria que o problema de usar o BLAS + LAPACK para executar o GEPP em uma solução ODE fosse qualquer diferenciação finita usada em um método ODE implícito. Eu sei que as pessoas resolveram programas lineares como parte de uma avaliação do lado direito e, como o fizeram de maneira ingênua (apenas conectaram o programa linear ao lado direito, chamando um algoritmo simplex), reduziram bastante a precisão de seus solução computada e aumentou substancialmente o tempo necessário para resolver o problema. Um colega meu descobriu como resolver esses problemas de uma maneira muito mais eficiente e precisa; Vou ter que olhar para ver se a publicação dele já foi lançada. Você pode ter um problema semelhante, independentemente de optar por usar o GEPP ou a Regra do Cramer.

Se houver alguma maneira de calcular uma matriz jacobiana analítica para o seu problema, convém fazer isso para evitar algumas dores de cabeça numéricas. Será mais barato avaliar, e provavelmente mais preciso, do que uma aproximação por diferença finita. Expressões para a derivada da matriz inversa podem ser encontradas aqui, se você precisar delas. Avaliar a derivada da matriz inversa parece exigir pelo menos duas ou três soluções lineares do sistema, mas todas elas terão a mesma matriz e diferentes lados do lado direito, portanto, não seria consideravelmente mais caro que um único sistema linear resolver.

E se houver alguma maneira de comparar sua solução computada com uma solução com valores de parâmetros conhecidos, eu faria isso, para que você possa diagnosticar se encontrou alguma dessas armadilhas numéricas.

Geoff Oxberry
fonte

Quando você escreve suave aqui, quer dizer que também é suave quando avaliado com precisão finita, ou seja, estável (foi o que tentei dizer). Veja também meu comentário à resposta de GertVdE. Penso que posso excluir matrizes quase singulares (suponho que, nesses casos, a análise do meu problema físico deva ser reformulada).

highsciguy

1

Quero dizer "é pelo menos duas vezes continuamente diferenciável". Eu acho que o mapa inverso da matriz é infinitamente continuamente diferenciável para todos os que .

A

$A$

det (A) \neq 0

$\det(A) \neq 0$

Geoff Oxberry

Seu comentário sobre 'diferenciação finita usada em um método ODE implícito' se aplica a mim. Como a dimensão de é muito menor que a dimensão do meu sistema ODE (essa matriz surge apenas no mapeamento de algumas variáveis), a robustez é muito mais importante nesse estágio do que a velocidade. Em particular, uma vez que, na fase de desenvolvimento, nunca saberei onde os erros numéricos encontrados se não garantir que componentes individuais sejam seguros.

n

$n$

A

$A$

highsciguy

-2

Não tenho certeza de que possa ajudar, mas acho que quando você fala sobre solução estável, você está falando sobre métodos de aproximação. Quando você calcula as coisas explicitamente, a estabilidade não tem sentido. Isso quer dizer que você deve aceitar uma solução aproximada se quiser ganhar estabilidade.

ctNGUYEN
fonte

5

A aproximação de ponto flutuante (arredondamento, cancelamento etc.) conta todos quando se trata de estabilidade. Mesmo se você tiver uma fórmula para a resposta, precisará determinar se ela pode ser calculada com precisão na aritmética de precisão finita.

Bill Barth

Não vejo esta resposta tão negativa quanto os outros parecem vê-la. Obviamente, a questão da estabilidade existe também para resultados explícitos. Mas acredito que o ctNGUYEN só queria dizer que uma solução aproximada, como a expansão em uma pequena quantidade, pode realmente ser mais precisa do que o resultado explícito completo que, penso, está correto. Em certo sentido, peço soluções explícitas que tratem casos tão difíceis, de modo que a fórmula seja sempre estável.

highsciguy

Solução explícita numericamente estável de sistema linear pequeno

Respostas: