Autor Tema: Costo operativo de calcular inversa

0 Usuarios y 1 Visitante están viendo este tema.

14 Marzo, 2012, 12:24 pm
Leído 3063 veces

nma

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola Buenas, soy nuevo en el foro y haber si me pueden ayudar con este ejercicio, que llevo un montón de tiempo dándole vueltas a la cabeza y por más veces que pienso que lo tengo resuelto, al final no llego a ningún lado xD.

El enunciado es este:

"Deducir que el costo en flops de calcular la inversa de una matriz A de orden n es \( {n}^{ 3}  \) flops. Recuerde que

\( \sum_{j = 1}^n   \)\( {j}^{2 }=\frac{(2n+1)(n+1)n}{ 6} \)  "

Por si alguno no entiende lo que es un flop, simplemente es la forma de llamarlo a una multiplicación o división.

Voy a poner mis razonamientos y las cosas que he hecho:

- Para calcular la inversa de A he pensado que se podía hacer a través de la factorización LU, es decir, A=LU,  \( {A}^{ -1}={(LU)}^{-1 }={U}^{-1 }{L}^{-1 }     \)

por tanto, si lo hacemos de esta manera solo necesitaremos saber los flops de calcular la inversa de U, la inversa de L y la multiplicación de ellas, sin embargo, calcular la inversa de U me resulta un tanto liosa y complicada a pesar de que es triangular superior.

- Después he pensado en resolverlo mediante un sistema AX=I, donde X sería una matriz incógnita con las mismas dimensiones de A e I sería la identidad. Sin embargo, habría que resolver un montón de ecuaciones o reducir a forma escalonada (que eso es lo que he hecho por último)

- Como ya he dicho, he utilizado el mismo razonamiento anterior pero reduciendo A a forma escalonada, es decir,
AX=I          (A=LU)

LUX=I

\( UX={L}^{-1 }I  \)

\( UX={L}^{-1 } \)

De esta manera se podría utilizar la sustitución regresiva para cada columna incógnita de X.

Para calcular \( {L}^{-1 } \) hay que tener en cuenta que es \( {M}_{( n-1)},...,{M}_{(2) },{M}_{(1) }  \) que son las matrices que al multiplicar a A por la izquierda dan como resultado la matriz U. Por tanto, \( {L}^{-1 } \) se puede conseguir sin más que hacer la correspondiente multiplicación. Según mis cálculos, el costo de obtener esta matriz es de \( {n}^{2 }  \) flops (no sé si estará bien)

Después, para calcular U, según pone en mis apuntes, el costo de obtenerlo es de \( \frac{{n}^{3 }-n }{3 }  \) flops (aunque todavía no sé muy bien por qué es así).

Por último, resolver el sistema \( UX={L}^{-1 } \) supongo que costará lo mismo que cuesta calcuar U, por tanto, el costo final de calcular la inversa sería:

\( \frac{{n}^{3 }-n }{3 }+\frac{{n}^{3 }-n }{3 }+{n}^{2 }=\frac{2{n}^{3 }-2n+3{n}^{2 }  }{ 3}   \) flops, lo cual dista bastante de lo que "dice" el enunciado que debe salir.

Espero que alguien pueda ayudarme

Muchas gracias,

Un Saludo :D

14 Marzo, 2012, 12:50 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Mi impresión es que el enunciado debiera de decir que el cálculo de la inversa es de orden \( n^3 \). Tengo serias dudas de que con ningún método se consiga en exactamente en \( n^3 \) operaciones.

 ¿El flop es cualquier operación o sólo mutliplicación y división?.

Saludos.

14 Marzo, 2012, 12:57 pm
Respuesta #2

nma

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola,
yo he pensado también eso, que se refiera a que debe ser de orden \( n^3 \) pero no sé qué pensar, porque por ejemplo, el costo de obtener b' a través de resolver el sistema Lb'=b, donde b es Ax=b y L es de la factorización LU, es de \( n^2 \), es decir, es un número exacto.

En cuanto a lo del flop, sí, según mis apuntes, un flop es únicamente una multiplicación o división ;)

Un Saludo

14 Marzo, 2012, 12:57 pm
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Mi impresión es que el enunciado debiera de decir que el cálculo de la inversa es de orden \( n^3 \).

Es lo que te dice el_manco. El cálculo de la inversa (casi por cualquier algoritmo) es \( O(n^3) \), pero una estimación de la cantidad exacta de operaciones que demanda es muy variable. Depende de muchas cosas. Ahí tendrías que especificar concretamente cuál es el método y exactamente cómo estás considerando un FLOP, que es tu unidad de medida.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

14 Marzo, 2012, 01:13 pm
Respuesta #4

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola,
yo he pensado también eso, que se refiera a que debe ser de orden \( n^3 \) pero no sé qué pensar, porque por ejemplo, el costo de obtener b' a través de resolver el sistema Lb'=b, donde b es Ax=b y L es de la factorización LU, es de \( n^2 \), es decir, es un número exacto.

Bueno, depende. Por ejemplo, si consideras un FLOP = 1 suma + 1 multiplicación (que es como se hace habitualmente), el algoritmo de sustitución hacia adelante lleva \( \displaystyle \sum_{i=1}^n (i-1)=\frac{n(n-1)}{2} \) que no es exactamente \( n^2 \). Pero todo depende de cómo se defina el FLOP.

En cuanto a lo del flop, sí, según mis apuntes, un flop es únicamente una multiplicación o división ;)

Es raro que lo hayan definido así. Porque sea el algoritmo que sea, necesitas hacer sumas y tomando el FLOP de la manera en que lo hicieron en tu curso, esa operación no está siendo considerada. ¿Cómo dedujeron que la sustitución hacia delante demandaba exactamente \( n^2 \) operaciones?
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

14 Marzo, 2012, 01:34 pm
Respuesta #5

nma

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
¿Cómo dedujeron que la sustitución hacia delante demandaba exactamente \( n^2 \) operaciones?

Ups...me he equivocado en esto xD. Lo que vale \( n^2 \) flops es obtener x de Ux=b', contando además los flops que se han gastado en obtener b' de Lb'=b

Esta es la página de mis apuntes, en concreto, el tema que tratamos está en la página 8
http://www.matematicaaplicada2.es/data/pdf/1328895429_1121288057.pdf

Un Saludo :D