Matrices e inversas de Pascal – El bucle DO

Matrices e inversas de Pascal – El bucle DO


Algunas matrices son tan especiales que tienen nombres. La matriz de identidad es la más conocida, pero muchas llevan el nombre de un investigador que las estudió, como las matrices de Hadamard, Hilbert, Sylvester, Toeplitz y Vandermonde. Este artículo trata sobre la matriz de Pascal, que se forma a partir de elementos del triángulo de Pascal.

Como mencioné anteriormente, el triángulo de Pascal tiene muchas propiedades interesantes. Al insertar el triángulo de Pascal en los elementos de una matriz, hay dos formas de hacerlo. La primera es usar una matriz triangular inferior L: poner el triángulo de Pascal en los elementos triangulares inferiores y ceros en los elementos triangulares superiores. A esta matriz triangular la llamo Matriz Pascal de primera clase. La segunda es usar una matriz P completa para la cual la i_ésima antidiagonal es la i_ésima fila del triángulo de Pascal. A esta matriz completa la llamo Matriz Pascal de segunda clase. Estas dos definiciones se muestran a continuación para matrices de Pascal con N = 8 filas:

Curiosamente, estas dos matrices están estrechamente relacionadas. Anteriormente discutí que la matriz completa (que es simétrica) tiene una factorización de Cholesky y que la factorización es exactamente P = LLt. ¡Eso es bastante asombroso!

Por qué es importante la factorización de Cholesky

He escrito sobre la geometría de la transformada de Cholesky y cómo correlaciona y descorrelaciona variables en aplicaciones estadísticas. Pero desde la perspectiva del álgebra lineal numérica, las factorizaciones de matrices son útiles porque nos permiten resolver ciertos problemas de manera eficiente. Por ejemplo, si tiene una matriz simétrica P, puede usar la raíz de Cholesky para resolver el sistema lineal P*v = b resolviendo dos sistemas lineales:

  • Resuelve L w = b para el vector w.
  • resolver Lt v = w para el vector v, que también es la solución de P v = b.

En el lenguaje SAS IML, puede usar la función TRISOLV para resolver sistemas lineales. Usan diferentes banderas para decirle a la función TRISOLV si debe resolver un triángulo inferior o superior, así:

b = {-4, 24, 150, 528, 1452, 3432, 7293, 14300};
v1 = solve(P, b);         /* general solution: solve P*v = b */
 
/* If you have Cholesky root (P=L*L`), you can use TRISOLV */
w = trisolv(4, L, b);     /* solve L *w = b for w */
v = trisolv(3, L, w);     /* solve L`*v = w for v */
print v1 v;

Como muestra el resultado, las dos formas diferentes de resolver el problema producen soluciones similares. Cuando llama a la función SOLVE, en realidad realiza una descomposición interna y resuelve dos sistemas de triángulos, por lo que los dos realizan cálculos similares, aunque el método SOLVE no explota la simetría de la matriz de Pascal.

Una inversa explícita para la matriz de Pascal

Algunas matrices tienen nombres porque tienen propiedades matemáticas sorprendentes. Ya hemos visto que las matrices de Pascal (del segundo tipo) tienen raíces de Cholesky, que también son matrices de Pascal (del primer tipo). Pero, ¿sabía que puede escribir explícitamente la matriz inversa para las matrices de Pascal del primer tipo? La siguiente figura muestra la inversa de las matrices pascales de 8 x 8 8 del primer tipo:

La figura muestra que el inverso de L se parece a L mismo, excepto que los signos de ciertos elementos son negativos. Si G es la matriz inversa, entonces G[i,j] = L[i,j] (-1)yo + j donde i=1,2,3,… es el índice de fila y j=1,2,3,… es el índice de columna. Hay varias formas de formar la matriz inversa de L. Las siguientes declaraciones producen una «matriz de signos» H definida por H[i,j] = (-1)yo + j. La matriz inversa para L es la multiplicación por elementos de L y H de la siguiente manera:

/* There is an EXACT inverse for L */
i = row(P);         /* n x n matrix where i_th row equals i */
j = col(P);         /* n x n matrix where j_th col equals j */
Sign = (-1)##(i+j); /* n x n sign matrix +/-1 */
Linv = Sign#L;
print Linv[F=5. r=rname c=cname L="Inverse of L"];

La matriz se ha mostrado anteriormente. Puedes resolver el sistema P v = b directamente usando la inversa de las raíces de Cholesky y dos resultados conocidos del álgebra lineal:

  • El inverso del producto es igual al (inverso) producto del inverso: inv(A*B) = inv(B)*inv(A)
  • La inversa de la transpuesta es igual a la transpuesta de la inversa: inv(A`) = inv(A)`

Al juntar estos resultados, se obtiene un método directo para resolver un sistema lineal que involucra una matriz de Pascal, de la siguiente manera:

/* The inverse of the product equals the (reversed) product of the inverses.
   The inverse of the transpose equals the transpose of the inverse.
   To solve P*v = b, use
   v = inv(L*L`)*b = inv(L`)*inv(L)*b = (inv(L))`*inv(L)*b */
v = Linv`*Linv*b;
print v;

El vector solución es idéntico a las soluciones de otros métodos. Sin embargo, si tiene una fórmula explícita para el inverso, puede resolver un sistema lineal que involucre una matriz de Pascal sin hacer álgebra lineal numérica. Para una matriz de Pascal (segundo tipo) Puede construir las raíces de Cholesky sin hacer álgebra lineal, ya que las raíces son la matriz de Pascal de primer tipo. Además, puede construir explícitamente el inverso de las raíces de Cholesky sin hacer álgebra lineal. Al juntar estos hechos, puede resolver sistemas lineales que involucran matrices de Pascal usando solo la multiplicación de matrices.

resumen

Es posible que nunca necesite resolver un sistema de ecuaciones lineales que incluya una matriz de Pascal, pero hay algunos principios generales que los programadores estadísticos pueden aprender de este artículo:

  • Si tiene una matriz con una estructura especial, explote esta estructura. Los ejemplos incluyen matrices simétricas, en bandas, tridiagonales y especiales «nombradas». A menudo, puede resolver sistemas lineales de manera más eficiente utilizando un solucionador específico en lugar de un solucionador general.
  • Si su matriz es una matriz «nombrada», consulte la literatura para ver si hay alguna fórmula especial que pueda usar para escribir la forma de una raíz cuadrada o una matriz inversa directamente. Esto puede conducir a una forma eficiente de resolver sistemas lineales.
  • Con un lenguaje de matriz interactivo como SAS/IML, puede implementar fórmulas matemáticas en unas pocas líneas de código.

Para obtener más información sobre las matrices de Pascal, consulte Edelman, A. y Strang, G. (2004) «Pascal Matrices», El mensual matemático estadounidense.

Related post

Gráficas de apalancamiento parcial: el bucle DO

Gráficas de apalancamiento parcial: el bucle DO

Para un modelo de regresión lineal, esta es una herramienta de diagnóstico útil pero infrautilizada. Gráfica de palanca de regresión parcial.…
NFT Spotlight: La Capilla Sixtina Subterránea por Pascal Boyart

NFT Spotlight: La Capilla Sixtina Subterránea por Pascal Boyart

Tenga en cuenta que la siguiente revisión no constituye una recomendación de compra para los NFT discutidos y que el propio…
una estrategia prometedora para configurar matrices de nanocables para supercondensadores ultraestables

una estrategia prometedora para configurar matrices de nanocables para…

29 de abril de 2022 (Noticias de Nanowerk) El material de electrodo autoportante sin aglutinante tiene mejor capacidad de almacenamiento de…

Leave a Reply

Tu dirección de correo electrónico no será publicada.