algoritmo rápido para resolver sistema de ecuaciones lineales

Question

Tengo un sistema de ecuaciones lineales, $Ax=b$, con las ecuaciones de $N$ y $N$ incógnitas ($N$ grande) si estoy interesado en la solución para sólo una de las incógnitas, ¿cuáles son los mejores enfoques?

por ejemplo, asumir N = 50, 000 y queremos la solución $x_1$ a través de $x_{100}$ solamente. ¿hay cualquier truco que no requiere $O(n^{3})$ (o (inversión de la matriz)) para?

Answer 1

strang, gilbert - álgebra lineal y sus aplicaciones 3 ª edición 16 de la página en el pie de página se menciona que la complejidad se había caído ya ha caído por debajo de $O(Cn^{2.376})$ en la fecha de redacción de 1988, aunque a $C$ es tan grande que hace que el algoritmo práctico para la mayoría de la matriz de tamaños en la práctica de hoy. No se menciona el nombre del algoritmo, aunque.

personal de adivinar: no estoy seguro acerca de la solución para una sola de las variables, pero no creo que se puede reducir la complejidad como que, dado que todo el sistema está acoplado.

Answer 2

A menos que su matriz es escaso o estructurados (e.g. Vandermonde, Hankel o los otros nombre de familias de matriz que admite un método de solución rápida), no hay muchas esperanzas de hacer las cosas mejores que $O(n^3)$ esfuerzo. Incluso si uno fuera a restringir el mismo a la solución de una de las 50.000 variables, Cramer exigirá computación dos determinantes para su respuesta y el esfuerzo para calcular un determinante es comenzar con al menos tanta como descomposición/invertir una matriz.

Answer 3

Hay una manera de reducir la complejidad y hacer que el sistema de solución en paralelo. Se llama Diakoptics (un método inventado por Gabriel Kron). Los métodos de uso principal es para las grandes redes eléctricas que tienen pocas interconexiones como redes de energía. Pero usted debe ser capaz de adaptarse.

La complejidad (para el caso de abajo) se reduce de $O(n^3)$ $O(2(\frac{n}{2})^3)$o $O(\frac{1}{4}n^3)$, el impacto puede ser mucho mayor si el sistema se divide en varios subsistemas. Para el caso de la complejidad ($s$-subsysems, $c$-puntos de interconexión) $O(c^3)+O((\frac{n^3}{s²}))$, si los sistemas se divide en equitativamente tamaño de los subsistemas. No estoy seguro acerca de la notación para múltiples variables, pero usted debe conseguir el punto.

En resumen:

Supongamos que usted tiene un $N \times N$ sistema, digamos que se puede dividir el sistema en dos sistemas con 1 punto de conexión(plus referencia cuando se mira en los sistemas eléctricos). Los puntos de conexión se $m$$n$. Vamos a suponer que estos sistemas son del tamaño de $N_1=N/2$ $N_2=N/2$ (para simplicitys bien). Ahora debe resolver por separado.

$\mathbf A_1^{-1}=\mathbf B_1$

$\mathbf A_2^{-1}=\mathbf B_2$

El siguiente paso es poner de nuevo juntos, que se realiza con la ayuda de los llamados "Thevenin de la Matriz"(en nuestro caso es 1$\times$1). Usted puede buscar la exacta principio de órdenes superiores(más puntos de conexión), pero para este ejemplo se ve como: \begin{align} \mathbf{B_{TH}}=B_{1mm}+B_{2nn}-2B_{mn} \end{align} Para nuestro caso tenemos $B_{mn}=0$. Ahora tenemos las soluciones $x_1$ $x_2$ para formar los coeficientes $b_{th}$.

$\mathbf x_{th}=x_{1m}-x_{2n}$

$\mathbf b_{p}=\mathbf{B_{TH}}^{-1} \mathbf x_{th}$

\begin{align} \mathbf b_{th}=\begin{bmatrix}0&\cdots&b_{p}&\cdots&-b_{p}&\cdots&0 \end{bmatrix}^T \end{align}

El $\mathbf b_{th}$ matriz sólo tiene un valor distinto de cero elementos en$m$$N/2 +n$. Ahora por fin podemos encontrar la solución a $x_n$ para el conjunto del sistema: \begin{align} \mathbf x_n=\begin{bmatrix}x_1\\x_2 \end{bmatrix}\begin{bmatrix}B_1&0\\0&B_2 \end-{bmatrix}\begin{bmatrix}b_{th} \end{bmatrix} \end{align}

Estoy más acostumbrado a la notación de ingeniería con $Z, I, U$ y así sucesivamente, de modo de excusa para no-símbolo estándar de uso.