Solución explícita numéricamente estable de un sistema lineal pequeño

11

Tengo un sistema lineal no homogéneo

A x = b

$Ax=b$

donde es una matriz real con . garantiza que el espacio nulo de es de dimensión cero, por lo que la ecuación tiene un inverso único . Dado que el resultado entra en el lado derecho de una EDO, que tengo la intención de resolver utilizando un método adaptativo, es importante que la solución sea suave con respecto a las pequeñas variaciones de los elementos de y . Debido a este requisito y la pequeña dimensionalidad, pensé implementar fórmulas explícitas para $A$ $n\times n$ $n\leq 4$ $A$ $x=A^{-1} b$ $A$ $b$ $A^{-1} b$ . Los elementos pueden ser exactamente cero o tomar valores muy diferentes. Mi pregunta es si esto tiene sentido para usted y si hay expresiones estables conocidas para esto. Estoy codificando en C para sistemas x86.

linear-algebra ode Highsciguy
fuente

Sé que llega muy tarde, pero aquí está mi sugerencia: como se sabe que la eliminación gaussiana con pivote total es estable, puede tener sentido codificar el algoritmo para los tamaños pequeños. Pivotar complica la materia ya que hay

formas de elegir los pivotes sucesivos, lo que lleva a

conjuntos diferentes de fórmulas; puede reducir esta complejidad intercambiando lo que debe intercambiarse, reduciendo el número de casos a

.

(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, me haría la pregunta: "¿Vale la pena?":

¿Vale la pena pasar el tiempo escribiendo, depurando y validando estas fórmulas explícitas, mientras que podría vincular fácilmente a BLAS + LAPACK que utiliza la eliminación gaussiana clásica?
¿Esperas ganar estabilidad? No creo que programar fórmulas explícitas (como la regla de Cramer) le brinde una mejor estabilidad, por el contrario.
¿Esperas ganar velocidad? ¿Ya perfilaste todo tu programa? ¿Qué fracción de tiempo se dedica a resolver estos sistemas 4x4?
¿Cuál es la probabilidad de que en un año mejore su modelo y necesite 5 ecuaciones en lugar de 4?

Mi consejo: use primero la combinación BLAS / LAPACK, vea si funciona, perfile todo el programa, solicite a un estudiante que implemente fórmulas explícitas (lo siento, es sarcástico aquí) y haga una comparación de velocidad y robustez.

GertVdE
fuente

El esfuerzo que me lleva implementarlo es de aproximadamente 15 minutos, porque simplemente ingreso una matriz general de 1x1, 2x2, 3x3 y 4x4 en un CAS (Maple para mí) y la invierto. Devolverá un resultado explícito (tipo C) (supuestamente basado en la regla de Cramer). Su segundo punto es exactamente mi preocupación. En el resultado habrá productos de orden superior de los elementos de la matriz. Obviamente, esto podría introducir errores debido a la "casi cancelación" de los diferentes términos. Pero la pregunta es, si es posible escribir el resultado en un formulario donde esto no ocurra. La velocidad no es la principal preocupación en este lugar.

highsciguy

6

$\mathcal{O}(n^{3})$

$A$ $A$ $\det(A) \neq 0$ $x$ $b$ $x$ $A$

Para estar seguro, probablemente sea mejor asegurarse de que tampoco sea numéricamente deficiente en rango (es decir, no tenga valores singulares pequeños). $A$

El problema con la regla de Cramer es que sus propiedades de estabilidad son desconocidas, excepto para (que es estable hacia adelante, pero no estable hacia atrás). (Ver Precisión y Estabilidad de Algoritmos Numéricos , 2ª edición, por N. Higham.) No se considera un algoritmo confiable; Se prefiere la eliminación gaussiana con pivote parcial (GEPP). $n = 2$

Esperaría que el problema con el uso de BLAS + LAPACK para llevar a cabo GEPP en una resolución ODE sería cualquier diferencia finita utilizada en un método ODE implícito. Sé que las personas han resuelto programas lineales como parte de una evaluación del lado derecho, y debido a que lo hicieron ingenuamente (solo enchufaron la solución del programa lineal en el lado derecho, llamando a un algoritmo simplex), redujeron en gran medida la precisión de su solución calculada y aumentó considerablemente el tiempo necesario para resolver el problema. Un compañero de laboratorio mío descubrió cómo resolver estos problemas de una manera mucho más eficiente y precisa; Tendré que mirar para ver si su publicación ya ha sido lanzada. Puede tener un problema similar independientemente de si opta por usar GEPP o la Regla de Cramer.

Si hay alguna manera de calcular una matriz analítica jacobiana para su problema, puede hacer eso para ahorrarse algunos dolores de cabeza numéricos. Será más barato de evaluar, y probablemente más preciso, que una aproximación de diferencia finita. Las expresiones para la derivada de la matriz inversa se pueden encontrar aquí si las necesita. La evaluación de la derivada de la matriz inversa parece que tomaría al menos dos o tres soluciones lineales del sistema, pero todas tendrían la misma matriz y diferentes lados a la derecha, por lo que no sería considerablemente más costoso que un solo sistema lineal resolver.

Y si hay alguna forma de comparar su solución calculada con una solución con valores de parámetros conocidos, lo haría, para que pueda diagnosticar si ha encontrado alguno de estos obstáculos numéricos.

Geoff Oxberry
fuente

Cuando escribe suave aquí, quiere decir que también es suave cuando se evalúa con precisión finita, es decir, estable (eso es lo que intenté decir). Vea también mi comentario a la respuesta de GertVdE. Creo que puedo excluir matrices casi singulares (supongo que en tales casos el análisis de mi problema físico debe reformularse).

highsciguy

1

Quiero decir "es al menos dos veces continuamente diferenciable". Creo que el mapa inverso de la matriz es infinitamente continuamente diferenciable para todo tal que .

A

$A$

det (A) \neq 0

$\det(A) \neq 0$

Geoff Oxberry

Su comentario sobre 'la diferencia finita utilizada en un método ODE implícito' se aplica a mí. Dado que la dimensión de es mucho más pequeña que la dimensión de mi sistema ODE (esta matriz surge simplemente en un mapeo de algunas variables), la robustez es mucho más importante en esta etapa que la velocidad. En particular, dado que en la etapa de desarrollo nunca sabré dónde surgen los errores numéricos encontrados si no me aseguro de que los componentes individuales sean seguros.

n

$n$

A

$A$

highsciguy

-2

No estoy seguro de que eso pueda ayudar, pero creo que cuando hablas de una solución estable, estás hablando de métodos de aproximación. Cuando calcula cosas explícitas, la estabilidad no tiene sentido. Eso dice que tienes que aceptar una solución aproximada si quieres ganar en estabilidad.

ctNGUYEN
fuente

55

La aproximación de punto flotante (redondeo, cancelación, etc.) cuenta cuando se trata de estabilidad. Incluso si tiene una fórmula para la respuesta, debe determinar si se puede calcular con precisión en aritmética de precisión finita.

Bill Barth

No veo esta respuesta tan negativa como otros la ven. Por supuesto, el problema de estabilidad existe también para resultados explícitos. Pero creo que ctNGUYEN solo quería decir que una solución aproximada, como la expansión en una pequeña cantidad, en realidad puede ser más precisa que el resultado explícito completo que, creo, es correcto. En cierto sentido, pido soluciones explícitas que traten casos tan difíciles, de modo que la fórmula siempre sea estable.

highsciguy

Solución explícita numéricamente estable de un sistema lineal pequeño

Respuestas: