operaciones mínimas para resolver una matriz tridiagonal

Question

$ A \in \mathbb{R}^{n x n} $ de una matriz tridiagonal y $b \in \mathbb{R}^{n}$

Cuál es el menor número de enunciados aritméticos en función de n para resolver $A*x = b$ ?

$$ \left( \begin{matrix} a_{1,1} & a_{1,2} & 0 & \ldots & 0\\ a_{2,1} & a_{22} & a_{2,3} & \ldots & \vdots\\ 0 & a_{3,2} & \ddots &\ddots & 0\\ \vdots & \ddots & \ddots & \ddots & a_{n-1,n}\\ 0 & \ldots & 0 & a_{n,n-1} & a_{n,n} \end{matrix} \right) $$

para LU en matriz tridiagonal 4x4 necesito 3 a cero operaciones -> n-1 para la descomposición LU

Eliminación gaussiana: $((n-1)n(n+1))/3 + ((n-1)n)/2$ restas/multiplicaciones y $(n(n+1))/2$ divisiones.

¿Son correctos los primeros pasos?

¿Cuál es la solución correcta?

Gracias.

Answer 1

Para un sistema de bandas de tamaño $N$ con ancho de banda $B$ el coste es $\mathcal{O}(B^2 N)$ .

Para un sistema triangular de tamaño $N$ con ancho de banda $B$ el coste es $\mathcal{O}(N^2)$ .

Para un sistema lineal denso completo de tamaño $N$ el coste es $\mathcal{O}(N^3)$ .

En general, nunca se debe hacer una eliminación gaussiana ingenua cuando se tiene alguna estructura de dispersión.

Aquí hay un enlace con los costes para diferentes matrices dispersas

Answer 2

No del todo: utilizar la eliminación gaussiana de forma ingenua acaba aumentando drásticamente el número de pasos necesarios. La eliminación gaussiana ingenua tiene en cuenta la eliminación de todos los elementos no diagonales. Pero aquí, ¡ya están despejadas todas las diagonales menos dos!

Como esto tiene el aspecto de una pregunta de tarea en un curso de análisis numérico, no daré una respuesta explícita. (Si se trata de una pregunta de deberes, deberías etiquetarla como tal). Pero diré que es posible resolver el sistema en menos de 6n (incluso 5n, si eres ingenioso) operaciones. Eso no es $n^2$ ¡!

HINT Ahora, para llegar a la solución, piensa en modificar la Eliminación Gaussiana para no intentar eliminar los valores vacíos. Pruébalo con una matriz de 5 por 5 o algo así, y cuenta cuántas operaciones necesitas entonces.