Cómo elegir un método para resolver ecuaciones lineales

31

Que yo sepa, hay 4 formas de resolver un sistema de ecuaciones lineales (corríjame si hay más):

  1. Si la matriz del sistema es una matriz cuadrada de rango completo, puede usar la Regla de Cramer;
  2. Calcule el inverso o el seudoinverso de la matriz del sistema;
  3. Utilice métodos de descomposición matricial (la eliminación de Gauss o Gauss-Jordan se considera descomposición de LU);
  4. Use métodos iterativos, como el método de gradiente conjugado.

De hecho, casi nunca desea resolver las ecuaciones utilizando la regla de Cramer o calculando el inverso o seudoinverso, especialmente para matrices de altas dimensiones, por lo que la primera pregunta es cuándo usar métodos de descomposición y métodos iterativos, respectivamente. Supongo que depende del tamaño y las propiedades de la matriz del sistema.

La segunda pregunta es, a su entender, qué tipo de métodos de descomposición o métodos iterativos son más adecuados para cierta matriz del sistema en términos de estabilidad numérica y eficiencia.

Por ejemplo, el método de gradiente conjugado se usa para resolver ecuaciones donde la matriz es simétrica y definida positiva, aunque también se puede aplicar a cualquier ecuación lineal convirtiendo Ax=b en ATAx=ATb . También para una matriz definida positiva, puede usar el método de descomposición Cholesky para buscar la solución. Pero no sé cuándo elegir el método CG y cuándo elegir la descomposición de Cholesky. Creo que es mejor que usemos el método CG para matrices grandes.

Para las matrices rectangulares, podemos usar la descomposición QR o SVD, pero nuevamente no sé cómo elegir una de ellas.

Para otras matrices, ahora no sé cómo elegir el solucionador apropiado, como matrices hermitianas / simétricas, matrices dispersas, matrices de banda, etc.

chaohuang
fuente
1
Hola @chaohuang, ¡y bienvenido a SciComp! Es posible que desee ver esta discusión: scicomp.stackexchange.com/questions/81/…
Paul
Hola @Paul, gracias por tus comentarios, ¿ese hilo es solo sobre matrices dispersas o alguna matriz?
chaohuang
66
Su pregunta tiene un alcance enorme y puede ser demasiado amplia para el formato de preguntas y respuestas que tenemos aquí en el intercambio de pila ... ¿hay alguna clase particular de sistema de matriz que le interese?
Paul
3
@chaohuang Hay numerosos libros sobre este tema. Esta pregunta es un poco como preguntarle a un médico cómo eligen los tratamientos "en general". Si desea hacer una pregunta que no sea específica para una determinada clase de problemas, debe hacer el trabajo para familiarizarse lo suficiente con el campo para hacer algo preciso. De lo contrario, explique el problema específico que le preocupa.
Jed Brown
2
De las preguntas frecuentes: si puede imaginar un libro completo que responda a su pregunta, está preguntando demasiado. Hay revistas completas y cientos de libros, asociados con esta pregunta.
David Ketcheson

Respuestas:

45

Ax=b

Ax~

  1. x~x~x~x<103x
  2. ¿ Qué tan rápido lo necesitas? La única métrica relevante aquí es la hora del reloj en su máquina: un método que se adapta perfectamente en un gran grupo podría no ser la mejor opción si no tiene una de esas, pero sí tiene una de esas nuevas tarjetas brillantes de Tesla.

Como no existe un almuerzo gratis, por lo general, debe decidir una compensación entre los dos. Después de eso, comienza a mirar la matriz (y su hardware) para decidir sobre un buen método (o más bien, el método para el que puede encontrar una buena implementación). (Observe cómo evité escribir "mejor" aquí ...) Las propiedades más relevantes aquí sonA

  • La estructura : ¿es simétrica? ¿Es denso o escaso? Congregado?A
  • Los valores propios : ¿son todos positivos (es decir, es positivo definido)? ¿Están agrupados? ¿Algunos de ellos tienen una magnitud muy pequeña o muy grande?A

Con esto en mente, debe buscar la literatura (enorme) y evaluar los diferentes métodos que encuentre para su problema específico. Aquí hay algunos comentarios generales:

  • Si realmente necesita (casi) precisión de máquina para su solución, o si su matriz es pequeña (por ejemplo, hasta filas), es difícil superar los métodos directos, especialmente para sistemas densos (ya que en este caso, cada multiplicación de matriz será , y si necesita muchas iteraciones, esto podría no estar muy lejos de que necesita un método directo). Además, la descomposición LU (con pivote) funciona para cualquier matriz invertible, a diferencia de la mayoría de los métodos iterativos. (Por supuesto, si es simétrico y positivo definido, usaría Cholesky).1000O(n2)O(n3)A

    Esto también es cierto para las matrices dispersas (grandes) si no tiene problemas de memoria: las matrices dispersas en general no tienen una descomposición LU dispersa, y si los factores no encajan en la memoria (rápida), estos métodos se vuelven inutilizables.

    Además, los métodos directos han existido por mucho tiempo, y existe software de muy alta calidad (por ejemplo, UMFPACK, paperas, SuperLU para matrices dispersas), que automáticamente se puede explotar la estructura de bandas de .A

  • Si necesita menos precisión o no puede usar métodos directos, elija un método de Krylov (por ejemplo, CG si es simétrico positivo definido, GMRES o BiCGStab si no) en lugar de un método estacionario (como Jacobi o Gauss-Seidel): estos generalmente funcionan mucho mejor, ya que su convergencia no está determinada por el radio espectral de sino por (la raíz cuadrada) del número de condición y no depende de la estructura de la matriz. Sin embargo, para obtener un rendimiento realmente bueno del método Krylov, debe elegir un buen preacondicionador para su matriz, y eso es más un oficio que una ciencia ...AA

  • Si en repetidas ocasiones necesita resolver sistemas lineales con la misma matriz y diferentes lados a la derecha, los métodos directos aún pueden ser más rápidos que los métodos iterativos, ya que solo necesita calcular la descomposición una vez. (Esto supone una solución secuencial; si tiene todos los lados derechos al mismo tiempo, puede usar los métodos de bloqueo de Krylov).

Por supuesto, estas son solo pautas muy generales: para cualquiera de las afirmaciones anteriores, es probable que exista una matriz para la cual lo contrario sea cierto ...

Como solicitó referencias en los comentarios, aquí hay algunos libros de texto y documentos de revisión para comenzar. (Ninguno de estos, ni el conjunto, es exhaustivo; esta pregunta es demasiado amplia y depende demasiado de su problema particular).

Christian Clason
fuente
2
¡Me gusta tu analogía del destornillador!
Paul
@chaohuang Si esto respondió su pregunta, debería aceptarla. (Si no fue así, siéntase libre de señalar lo que falta).
Christian Clason el
@ChristianClason lo aceptó. Estaba esperando y esperando que alguien pudiera arrojar algo de luz sobre el tema de las matrices rectangulares. Como ha pasado mucho tiempo, supongo que nunca habrá una respuesta así :(
chaohuang
@chaohuang Gracias. Si todavía está interesado en las matrices rectangulares, debe plantear una pregunta (vinculada) sobre "Cómo elegir un método para resolver sistemas sobredeterminados".
Christian Clason
Aquí una referencia sobre el uso de métodos iterativos para resolver grandes sistemas dispersos de ecuaciones lineales.
chaohuang