Factorización de Doolittle - Historial de revisiones

Herraiz: /* Ventajas del método de Doolittle */

2013-10-02T12:57:47Z

‎Ventajas del método de Doolittle

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/mat/public_html/w/includes/diff/DairikiDiff.php on line 434

Herraiz: /* Resolución de un sistema lineal */

2013-10-02T12:53:51Z

‎Resolución de un sistema lineal

Herraiz: /* Ventajas del método de Doolittle */

2013-09-26T14:52:47Z

‎Ventajas del método de Doolittle

Herraiz: /* Métodos de resolución de sistemas lineales */

2013-07-29T15:38:18Z

‎Métodos de resolución de sistemas lineales

Herraiz en 17:23 30 jun 2013

2013-06-30T17:23:08Z

Herraiz: /* Ventajas del método de Doolittle */

2013-06-28T14:49:45Z

‎Ventajas del método de Doolittle

Herraiz: /* Métodos de factorización */

2013-06-28T14:49:15Z

‎Métodos de factorización

Herraiz: /* Ventajas del método de Doolittle */

2013-06-28T14:45:17Z

‎Ventajas del método de Doolittle

Herraiz: /* Descripción del método */

2013-06-28T14:44:17Z

‎Descripción del método

Herraiz en 14:43 28 jun 2013

2013-06-28T14:43:51Z

@@ Línea 100: / Línea 100: @@
 El procesador se encarga de realizar las diferentes operaciones matemáticas, y la memoria contiene los valores de las variables y de los resultados de las operaciones. Existen diferentes maneras de organizar el procesador y la memoria en un ordenador. A las diferentes maneras de organizar (y al tipo de operaciones que puede realizar el procesador) se las conoce como  [[Arquitectura de un ordenador|''arquitectura'']].
-Los ordenadores modernos se organizan todos usando la denominada ''arquitectura de von Neumann''<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann architecture] (Wikpiedia EN)</ref>. En esta arquitectura, la memoria y el procesador están conectados por medio de un ''bus'', que se encarga de pasar la información entre el ordenador y la memoria. El bus actúa de cuello de botella en el sistema. Por muy rápido que sea el procesador, si no puede recibir los datos que necesita para trabajar al ritmo adecuado, entonces la velocidad de cómputo estará limitada.
+Los ordenadores modernos se organizan todos usando la denominada ''arquitectura de von Neumann''<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann architecture] (Wikpiedia EN)</ref>. En esta arquitectura, la memoria y el procesador están conectados por medio de un ''bus'', que se encarga de pasar la información entre el ordenador y la memoria. En esta arquitectura, toda la información que se transfiere entre los diferentes elementos del ordenador pasa a través del ''bus'', y se comunica a todos los elementos. Cada elemento toma la información que va dirigida a él, e ignora cualquier información dirigida a otro elemento.
 Para solucionar los problemas del cuello de botella del bus<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture#Von_Neumann_bottleneck von Neumann bottleneck] (Wikipedia EN)</ref> en los ordenadores más recientes existen dos tipos de memoria: la memoria principal y la caché. La caché está conectada al procesador por un bus mucho más ancho y rápido. A su vez, la caché organiza la información para ir requiriendo datos de la memoria principal y mantener siempre datos en la caché para que el procesador los pueda usar sin tener que esperar a que estén disponibles. Esta jerarquía de memorias mejora el rendimiento, sobre todo en aplicaciones gráficas de escritorio. No se pensó como una mejora para potenciar el cálculo numérico, pero puede aprovecharse para elegir métodos optimizados para este tipo de arquitecturas.

@@ Línea 71: / Línea 71: @@
 === Resolución de un sistema lineal ===
-La aplicación más directa de la factorización LU es la resolución de sistemas lineales. Al transformar la matriz del sistema en un producto de matrices triangulares, el sistema de ecuaciones puede transformarse en dos sistemas triangulares, que son muy sencillos de resolver en un ordenador.
+La aplicación más directa de la factorización LU es la resolución de sistemas lineales. Al transformar la matriz del sistema en un producto de matrices triangulares, el sistema de ecuaciones puede transformarse en dos sistemas triangulares, que son muy sencillos de resolver en un ordenador usando el algoritmo de sustitución hacia atrás.
 Si tenemos el sistema de ecuaciones <math>Ax = b</math>, podemos cambiarlo por <math>LUx=b</math>. Pero <math>Ux</math> será también un vector columna, por lo que nos queda por un lado que <math>Ly=b</math>, y por otro que <math>Ux=y</math>. Ambos son sistemas triangulares. Resolvemos el primero para obtener <math>y</math>, y a continuación el segundo para obtener la solución buscada <math>x</math>.

@@ Línea 98: / Línea 98: @@
 Los ordenadores cuenta con diferentes elementos como procesador, memoria, disco duro, puertos USB, unidades de DVD. En el cálculo numérico, los dos elementos fundamentales que deciden si el cálculo se realizará antes o después son el procesador y la memoria.
-El procesador se encarga de realizar las diferentes operaciones matemáticas, y la memoria contiene los valores de las variables y de los resultados de las operaciones. Existen diferentes maneras de organizar el procesador y la memoria en un ordenador. A las diferentes maneras de organizar (y al tipo de operaciones que puede realizar el procesador) se las conoce como  ''arquitectura''.
+El procesador se encarga de realizar las diferentes operaciones matemáticas, y la memoria contiene los valores de las variables y de los resultados de las operaciones. Existen diferentes maneras de organizar el procesador y la memoria en un ordenador. A las diferentes maneras de organizar (y al tipo de operaciones que puede realizar el procesador) se las conoce como  [[Arquitectura de un ordenador|''arquitectura'']].
 Los ordenadores modernos se organizan todos usando la denominada ''arquitectura de von Neumann''<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture von Neumann architecture] (Wikpiedia EN)</ref>. En esta arquitectura, la memoria y el procesador están conectados por medio de un ''bus'', que se encarga de pasar la información entre el ordenador y la memoria. El bus actúa de cuello de botella en el sistema. Por muy rápido que sea el procesador, si no puede recibir los datos que necesita para trabajar al ritmo adecuado, entonces la velocidad de cómputo estará limitada.

@@ Línea 9: / Línea 9: @@
 Los métodos exactos proporcionan una solución exacta del sistema. A pesar de ser considerados métodos numéricos, el procedimiento no es una aproximación a la solución, sino la solución en sí. En la mayoría de las ocasiones es preferible usar estos métodos. Sin embargo, en ocasiones no es posible aplicarlos (por ejemplo, con matrices mal condicionadas), o puede ser más costoso usarlos por las propiedades de las matrices (por ejemplo, matrices ''sparse'', que contienen muchos ceros). En estos casos, un método iterativo proporciona una solución aproximada del sistema.
-En cuanto a los métodos exactos, pueden intentar resolver el sistema directamente, o usando sus factores. El método de ''Doolittle'' es un método de factorización LU denominado ''compacto'', porque es sencillo de programar y requiere poca memoria una vez implementado en el ordenador. Existen muchos métodos compactos de factorización de matrices, y suelen diferir en el tratamiento que hacen de los elementos de la diagonal de las matrices <math>L</math> y/o <math>U</math>. En concreto, el método de Doolittle genera una matriz <math>L</math> que tiene <math>1</math> en todos los elementos de la diagonal. Este método proporciona una ventaja de cálculo en ordenadores modernos, que cuentan con memoria caché además de la memoria principal. En este tipo de arquitecturas de ordenador, la secuencia en la que se realizan los cálculos puede ser más importante que la cantidad de cálculos que se realizan. El método de Doolittle tiene una secuencia de operaciones óptima para ejecutarse en un ordenador con memoria caché.
+En cuanto a los métodos exactos, pueden intentar resolver el sistema directamente, o usando sus factores. El método de ''Doolittle'' es un método de factorización LU denominado ''compacto'', porque es sencillo de programar y requiere poca memoria una vez implementado en el ordenador. Existen muchos métodos compactos de factorización de matrices, y suelen diferir en el tratamiento que hacen de los elementos de la diagonal de las matrices <math>L</math> y/o <math>U</math>. En concreto, el método de Doolittle genera una matriz <math>L</math> que tiene <math>1</math> en todos los elementos de la diagonal. Este método proporciona una ventaja de cálculo en ordenadores modernos, que cuentan con memoria caché además de la memoria principal. En este tipo de [[Arquitectura de un ordenador|arquitecturas de ordenador]], la secuencia en la que se realizan los cálculos puede ser más importante que la cantidad de cálculos que se realizan. El método de Doolittle tiene una secuencia de operaciones óptima para ejecutarse en un ordenador con memoria caché.
 Los métodos de factorización LU se pueden usar para resolver sistemas lineales, entre otras [[#Aplicaciones_del_m.C3.A9todo|aplicaciones]].

← Revisión anterior		Revisión del 17:23 30 jun 2013
Línea 103:		Línea 103:

	Para solucionar los problemas del cuello de botella del bus<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture#Von_Neumann_bottleneck von Neumann bottleneck] (Wikipedia EN)</ref> en los ordenadores más recientes existen dos tipos de memoria: la memoria principal y la caché. La caché está conectada al procesador por un bus mucho más ancho y rápido. A su vez, la caché organiza la información para ir requiriendo datos de la memoria principal y mantener siempre datos en la caché para que el procesador los pueda usar sin tener que esperar a que estén disponibles. Esta jerarquía de memorias mejora el rendimiento, sobre todo en aplicaciones gráficas de escritorio. No se pensó como una mejora para potenciar el cálculo numérico, pero puede aprovecharse para elegir métodos optimizados para este tipo de arquitecturas.		Para solucionar los problemas del cuello de botella del bus<ref>[http://en.wikipedia.org/wiki/Von_Neumann_architecture#Von_Neumann_bottleneck von Neumann bottleneck] (Wikipedia EN)</ref> en los ordenadores más recientes existen dos tipos de memoria: la memoria principal y la caché. La caché está conectada al procesador por un bus mucho más ancho y rápido. A su vez, la caché organiza la información para ir requiriendo datos de la memoria principal y mantener siempre datos en la caché para que el procesador los pueda usar sin tener que esperar a que estén disponibles. Esta jerarquía de memorias mejora el rendimiento, sobre todo en aplicaciones gráficas de escritorio. No se pensó como una mejora para potenciar el cálculo numérico, pero puede aprovecharse para elegir métodos optimizados para este tipo de arquitecturas.
−

	Tradicionalmente, la diferencia entre la velocidad de cómputo con un método u otro radicaba en la ''complejidad'' del método, es decir, en la cantidad de operaciones que tiene que realizar. Sin embargo, al introducir una memoria caché, que tiene una comunicación mucho más rápida con el procesador, la secuencia de operaciones es ahora también un parámetro fundamental para determinar la velocidad de cómputo.		Tradicionalmente, la diferencia entre la velocidad de cómputo con un método u otro radicaba en la ''complejidad'' del método, es decir, en la cantidad de operaciones que tiene que realizar. Sin embargo, al introducir una memoria caché, que tiene una comunicación mucho más rápida con el procesador, la secuencia de operaciones es ahora también un parámetro fundamental para determinar la velocidad de cómputo.

@@ Línea 111: / Línea 111: @@
 En estas situaciones, si el procesador tiene siempre en la caché los valores que necesita, irá más rápido que si tiene que ir pidiendo valores a la memoria principal. Por la manera en que funciona esta arquitectura, la caché siempre contendrá los valores necesarios para una operación, y los valores resultantes de la operación. Esta característica es precisamente la que explota el método de Doolittle. Cada vez que calculamos un valor de <math>u_{ij}</math>, podemos calcular el valor de <math>l_{ij}</math> correspondiente. Pero para calcular el siguiente valor de <math>u_{ij}</math> necesitamos el valor de <math>l_{ij}</math> que acabamos de calcular. Gracias a esta característica del método, se minimizan las peticiones de datos a la memoria principal, y aunque el número de operaciones es el mismo, su ejecución suele ser más rápida. Las ganancias de tiempo de ejecución son del orden del 50% en el mejor de los casos.
-Esta ventaja es más difícilmente explotable desde MATLAB u Octave UPM, ya que son lenguajes de muy alto nivel, y es imposible controlar si los datos se guardan en caché o no. Además, al ser entornos de programación, realizan muchas otras operaciones ocultas que también requieren del uso de la caché, por lo que no está claro que se aproveche totalmente la caché con este método. En cualquier caso, por [[Prog32:_Matrices,_bucles_y_vectorización|la manera en la que funcionan MATLAB y Octave]] podemos facilitar la reutilización de la caché recorriendo siempre las matrices primero en columnas, tal y como se hace en la implementación del método mostrada arriba.
+Esta ventaja es más difícilmente explotable desde MATLAB u Octave UPM, ya que son lenguajes de muy alto nivel, y es imposible controlar si los datos se guardan en caché o no. Además, al ser entornos de programación, realizan muchas otras operaciones ocultas que también requieren del uso de la caché, por lo que no está claro que se aproveche totalmente la caché con este método. En cualquier caso, por [[Prog32:_Matrices,_bucles_y_vectorización|la manera en la que funcionan MATLAB y Octave]] podemos facilitar la reutilización de la caché recorriendo siempre las matrices primero en columnas, tal y como se hace en [[#Implementación en código MATLAB|la implementación del método mostrada arriba]].
 {{ Referencias }}

@@ Línea 1: / Línea 1: @@
 En álgebra lineal, se conoce por factorización LU de matrices<ref>[http://en.wikipedia.org/wiki/LU_decomposition LU decomposition] (Wikipedia EN)</ref> al proceso que a partir de una matriz cuadrada <math>A</math> halla dos matrices triangulares inferior y superior, tal que <math>A = L U</math>, donde <math>L</math> es la matriz triangular inferior (L de ''lower'') y <math>U</math> es la matriz triangular superior (U de ''upper''). Existen muchos métodos numéricos para obtener estas matrices <math>L</math> y <math>U</math>, y su obtención tiene aplicaciones en la resolución de sistemas lineales, cálculo de determinantes y en el cálculo de matrices inversas. En este artículo estudiamos el método de ''Doolittle'' para obtener estas matrices. Este método tiene la particularidad que hace que la diagonal de la matriz <math>L</math> sea unitaria.
-== Métodos de factorización ==
+== Métodos de resolución de sistemas lineales ==
 Para resolver sistemas de ecuaciones lineales numéricamente  existen dos grandes familias de métodos:
@@ Línea 9: / Línea 9: @@
 Los métodos exactos proporcionan una solución exacta del sistema. A pesar de ser considerados métodos numéricos, el procedimiento no es una aproximación a la solución, sino la solución en sí. En la mayoría de las ocasiones es preferible usar estos métodos. Sin embargo, en ocasiones no es posible aplicarlos (por ejemplo, con matrices mal condicionadas), o puede ser más costoso usarlos por las propiedades de las matrices (por ejemplo, matrices ''sparse'', que contienen muchos ceros). En estos casos, un método iterativo proporciona una solución aproximada del sistema.
-En cuanto a los métodos exactos para factorizar una matriz, existen también diferentes tipos de métodos. El método de ''Doolittle'' es un método denominado ''compacto'', porque es sencillo de programar y requiere poca memoria una vez implementado en el ordenador. Existen muchos métodos compactos de factorización de matrices, y suelen diferir en el tratamiento que hacen de los elementos de la diagonal de las matrices <math>L</math> y/o <math>U</math>. En concreto, el método de Doolittle genera una matriz <math>L</math> que tiene <math>1</math> en todos los elementos de la diagonal. Este método proporciona una ventaja de cálculo en ordenadores modernos, que cuentan con memoria caché además de la memoria principal. En este tipo de arquitecturas de ordenador, la secuencia en la que se realizan los cálculos puede ser más importante que la cantidad de cálculos que se realizan. El método de Doolittle tiene una secuencia de operaciones óptima para ejecutarse en un ordenador con memoria caché.
+En cuanto a los métodos exactos, pueden intentar resolver el sistema directamente, o usando sus factores. El método de ''Doolittle'' es un método de factorización LU denominado ''compacto'', porque es sencillo de programar y requiere poca memoria una vez implementado en el ordenador. Existen muchos métodos compactos de factorización de matrices, y suelen diferir en el tratamiento que hacen de los elementos de la diagonal de las matrices <math>L</math> y/o <math>U</math>. En concreto, el método de Doolittle genera una matriz <math>L</math> que tiene <math>1</math> en todos los elementos de la diagonal. Este método proporciona una ventaja de cálculo en ordenadores modernos, que cuentan con memoria caché además de la memoria principal. En este tipo de arquitecturas de ordenador, la secuencia en la que se realizan los cálculos puede ser más importante que la cantidad de cálculos que se realizan. El método de Doolittle tiene una secuencia de operaciones óptima para ejecutarse en un ordenador con memoria caché.
 == Descripción del método ==

@@ Línea 90: / Línea 90: @@
 == Ventajas del método de Doolittle ==
-[[Archivo:Vonneumann.png|320px|miniaturadeimagen|derecha|Arquitectura de von Neumann]]
+[[Archivo:Vonneumann.png|320px|miniaturadeimagen|derecha|Arquitectura de von Neumann (el bus es un cuello de botella)]]
-[[Archivo:Cache.png|320px|miniaturadeimagen|derecha|Arquitectura de von Neumann con jerarquía de memorias (caché y memoria principal)]]
+[[Archivo:Cache.png|320px|miniaturadeimagen|derecha|Arquitectura de von Neumann con jerarquía de memorias (caché y memoria principal, aliviando el cuello de botella)]]
 Los ordenadores cuenta con diferentes elementos como procesador, memoria, disco duro, puertos USB, unidades de DVD. En el cálculo numérico, los dos elementos fundamentales que deciden si el cálculo se realizará antes o después son el procesador y la memoria.

@@ Línea 29: / Línea 29: @@
 Para seguir calculando filas de <math>U</math> es necesario conocer los valores de <math>L</math>. Si nos movemos por debajo de la diagonal, <math>j\leq i</math>, tendremos que <math>\min(i,j)=j</math>, y obtenemos
-<math>\displaystyle l_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1} l_{ik} u_{kj}}{u_{jj}}</math>
+<math>\displaystyle l_{ij} = \frac{\displaystyle a_{ij} - \sum_{k=1}^{j-1} l_{ik} u_{kj}}{u_{jj}}</math>
 Por tanto, podemos calcular <math>\displaystyle l_{i1} = \frac{a_i}{u_{11}}</math>, es decir, hemos calculado ya la primera columna de <math>L</math>. Al conocer la primera columna de <math>L</math> podemos intentar calcular la siguiente fila de <math>U</math>. Al terminar una fila de <math>U</math>, ya conocemos los elementos para calcular la siguiente columna de <math>L</math>. Aplicando sucesivamente este método, obtendremos de manera completa las matrices <math>L</math> y <math>U</math>.

← Revisión anterior		Revisión del 14:43 28 jun 2013
Línea 1:		Línea 1:
−	~~{{ Beta }}~~
−
	En álgebra lineal, se conoce por factorización LU de matrices<ref>[http://en.wikipedia.org/wiki/LU_decomposition LU decomposition] (Wikipedia EN)</ref> al proceso que a partir de una matriz cuadrada <math>A</math> halla dos matrices triangulares inferior y superior, tal que <math>A = L U</math>, donde <math>L</math> es la matriz triangular inferior (L de ''lower'') y <math>U</math> es la matriz triangular superior (U de ''upper''). Existen muchos métodos numéricos para obtener estas matrices <math>L</math> y <math>U</math>, y su obtención tiene aplicaciones en la resolución de sistemas lineales, cálculo de determinantes y en el cálculo de matrices inversas. En este artículo estudiamos el método de ''Doolittle'' para obtener estas matrices. Este método tiene la particularidad que hace que la diagonal de la matriz <math>L</math> sea unitaria.		En álgebra lineal, se conoce por factorización LU de matrices<ref>[http://en.wikipedia.org/wiki/LU_decomposition LU decomposition] (Wikipedia EN)</ref> al proceso que a partir de una matriz cuadrada <math>A</math> halla dos matrices triangulares inferior y superior, tal que <math>A = L U</math>, donde <math>L</math> es la matriz triangular inferior (L de ''lower'') y <math>U</math> es la matriz triangular superior (U de ''upper''). Existen muchos métodos numéricos para obtener estas matrices <math>L</math> y <math>U</math>, y su obtención tiene aplicaciones en la resolución de sistemas lineales, cálculo de determinantes y en el cálculo de matrices inversas. En este artículo estudiamos el método de ''Doolittle'' para obtener estas matrices. Este método tiene la particularidad que hace que la diagonal de la matriz <math>L</math> sea unitaria.