Antes de começar, é importante alertar o leitor que este não é um artigo com o intuito de ensinar o teorema de Laplace. Aqui, faço uma análise do teorema do ponto de vista computacional. Caso você precise de um artigo para aprender o teorema, procure outra fonte.
Índice
Introdução
O teorema de Laplace (Laplace Expansion, em inglês) permite calcular o determinante de matrizes de qualquer ordem através de uma expansão em cofatores. Na prática, o cálculo do determinante é realizado calculando-se os determinantes de matrizes de ordem inferior. Por exemplo, o determinante de uma matriz de ordem cinco é calculado a partir dos determinantes de cinco matrizes de ordem quatro.
O intuito deste texto é analisar a complexidade do teorema na resolução de determinantes. Tal análise faz uso de conceitos um tanto avançados de Cálculo Diferencial, portanto é importante ter noções de Cálculo para compreender o artigo.
Inicialmente, é feita uma rápida revisão sobre o teorema com o intuito de compreendê-lo. Depois, faço uma análise das chamadas recursivas necessárias para computar um determinante através do teorema. Em seguida, apresento a equação de recorrência do algoritmo e resolvo-a considerando dois casos distintos. Por fim, realizo algumas observações finais.
Compreendendo o Teorema de Laplace
Conforme mencionado, o teorema de Laplace utiliza uma expansão em cofatores para calcular determinantes.
O cofator de um elemento $a_{ij}$ de uma matriz $A$ é o produto do fator $(-1)^{i+j}$ pelo determinante da matriz obtida eliminando a linha $i$ e coluna $j$ de $A$. Por exemplo, considere a matriz
$$A=\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}.$$
O cofator de $1$ é dado por
$$(-1)^{1+1}\det \left|4\right| = 4.$$
Observação: quando a matriz possui um único elemento, o seu determinante é o próprio elemento.
O cálculo de determinantes através do teorema de Laplace é realizado seguindo os seguintes passos (algoritmo):
- escolha uma linha (ou coluna) da matriz;
- multiplique cada elemento da linha (ou coluna) escolhida pelo seu respectivo cofator;
- some os resultados obtidos. A soma será o determinante.
Aplicando o teorema em $A$, escolhendo a linha 1, temos
$$\det A = 1\times(-1)^{1+1}\det\left|4\right| + 2\times(-1)^{1+2}\det\left|3\right| = 4 - 6 = -2$$
Façamos o mesmo para a matriz a seguir:
$$B = \begin{bmatrix}1 & 0 & 4\\2 & -1 & 3\\9 & -2 & 0\end{bmatrix}.$$
Vamos escolher a coluna 1 para os cálculos:
$$\begin{align*}\det B = &1\times(-1)^{1+1}\det\begin{bmatrix}-1 & 3\\-2 & 0\end{bmatrix}+\\&2\times(-1)^{2+1}\det\begin{bmatrix}0 & 4\\-2 & 0\end{bmatrix}+\\&9\times(-1)^{3+1}\det\begin{bmatrix}0 & 4\\-1 & 3\end{bmatrix}\end{align*}$$
$$\det B = 1\times 6 + (-2)\times 8+ 9\times 4 = 6 - 16 + 36 = 26.$$
No primeiro caso, para calcular o determinante da matriz, que era de ordem 2, tivemos que calcular dois determinantes de matrizes de ordem 1. No segundo caso, como a matriz era de ordem três, então tivemos que calcular três determinantes de matrizes de ordem 2.
Isto é, para calcular o determinante de uma matriz de ordem $n$, é necessário calcular $n$ determinantes de matrizes de ordem $n - 1$.
Observe que o algoritmo é recursivo, pois para resolver o problema precisamos recorrer à própria definição do problema. Em outras palavras, precisamos calcular determinantes para resolver determinantes (essa frase ficou estranha, mas acho que deu para entender).
O caso básico da recursão ocorre quando temos que calcular o determinante de matrizes de ordem igual 1, pois o determinante é o único elemento das matrizes.
É claro, pode-se "otimizar" esse caso básico, como veremos na próxima seção.
Analisando o Algoritmo do Teorema de Laplace
Utilizando a notação $M_i$ para denotar uma matriz de ordem $i$, vamos analisar as chamadas recursivas do algoritmo.
Se $i=2$, temos:
Ou seja, para calcular $\det \left|M_2\right|$, precisamos calcular dois determinantes de ordem 1.
Se $i=3$, temos que calcular três determinantes de ordem 2 e, em seguida, precisamos calcular 2 determinantes de ordem 1, para cada matriz de ordem 2.
Se $i = 4$, temos que calcular quatro determinantes de ordem 3. Em seguida, calculamos três determinantes de ordem 2, para cada matriz de ordem 3. Por fim, calculamos dois determinantes de ordem 1, para cada matriz de ordem 2.
A quantidade de determinantes de ordem 1 que precisamos calcular aumenta à medida que a ordem da matriz cresce. Na prática, essa quantidade é igual ao fatorial da ordem da matriz. Por exemplo, para uma matriz de ordem 5, teríamos 120 determinantes de ordem 1 ($5!=120$).
Mesmo que seja feita uma ``otimização'' no algoritmo com a Regra de Sarrus, que permitiria o cálculo direto de determinantes de ordem 3, não fará diferença para matrizes de ordem mais alta. A quantidade de de determinantes de ordem 3 (que seria o novo caso básico) seria $\cfrac{n!}{3!}$, onde $n$ é a ordem da matriz. Obviamente, podemos calcular determinantes de ordem um e dois de forma direta também.
Apenas essa análise superficial é suficiente para concluir que o cálculo de determinantes através do teorema de Laplace é um processo custoso do ponto de vista computacional.
Podemos concluir também que a sua complexidade é de no mínimo $O(n!)$ (pois consideramos apenas os determinantes das matrizes de ordem 1, desprezando o custo das demais chamadas recursivas), que é pior do que a complexidade exponencial.
Na prática, veremos que a complexidade no tempo é de fato $O(n!)$.
A Equação de Recorrência do Algoritmo
Vamos representar o custo para o cálculo de determinantes de matrizes de ordem um por $c_0$.
Se $T(n)$ é a complexidade no tempo para o cálculo do determinante de uma matriz de ordem $n$, então
$$T(1) = c_0\quad\text{caso básico}.$$
Por sua vez, para calcular o determinante de uma matriz de ordem $n$, precisamos calcular o determinante de $n$ matrizes de ordem $n-1$. Em termos de $T(n)$, temos
$$T(n) = nT(n-1)+f(n),$$
onde $f(n)$ é o custo por chamada recursiva.
Isto é,
$$T(n)=\begin{cases}c_0,\quad\text{se }n=1\\T(n) = nT(n-1)+f(n),\quad\text{se }n>1\end{cases}.$$
Resolvendo a Equação de Recorrência
Se $f(n)$ fosse igual a zero, então teríamos
$$T(n) = c_0n!\quad\text{se }f(n)=0.$$
Esse valor é o custo total para o cálculo dos determinantes das matrizes de ordem um. Por outro lado, para $f(n)$ qualquer, precisamos expandir a expressão $T(n)$ para eliminar a recorrência:
$$\begin{align*}T(n) = nT(n-1) + f(n)\\T(n) = n\underbrace{\left[(n-1)T(n-2)+f(n-1)\right]}_{T(n-1)}+ f(n)\\T(n) = n(n-1)T(n-2)+nf(n-1)+f(n)\\T(n) = n(n-1)\underbrace{\left[(n-2)T(n-3)+f(n-2)\right]}_{T(n-2)} + nf(n-1)+f(n)\\T(n) = n(n-1)(n-2)T(n-3)+n(n-1)f(n-2)+nf(n-1)+f(n)\end{align*}$$
Observe os termos com $T(n)$:
$$\begin{align*}n(n-1)(n-2)T(n-3) = \frac{n!}{(n-3)!}T(n-3)\\n(n-1)T(n-2) = \frac{n!}{(n-2)!}T(n-2)\\nT(n-1) = \frac{n!}{(n-1)!}T(n-1).\end{align*}$$
Ou seja, se continuarmos expandindo, então teremos
$$\frac{n!}{(n-k)!}T(n-k).$$
Esse é o termo geral para as expressões com $T(n)$. A constante $k$ será determinada mais adiante.
Em relação às expressões com $f(n)$, temos
$$\begin{align*}f(n) = \frac{n!}{(n-0)!}f(n-0)\\nf(n-1) = \frac{n!}{(n-1)!}f(n-1)\\n(n-1)f(n-2) = \frac{n!}{(n-2)!}f(n-2).\end{align*}$$
Neste caso, o termo geral é igual a
$$\frac{n!}{(n-i)!}f(n-i).$$
Porém, os termos se somam conforme expandimos a expressão, portanto
$$\sum_{i=0}^{k-1}\frac{n!}{(n-i)!}f(n-i).$$
A constante $k$ dos termos com $T(n)$ inicia com 1 e o índice $i$ começa com 0. Por isso, temos $k-1$ no somatório. Isto é, foi necessário realizar um deslocamento do índice.
Combinando as expressões, temos
$$T(n) = \frac{n!}{(n-k)!}T(n-k) + \sum_{i=0}^{k-1}\frac{n!}{(n-i)!}f(n-i).$$
A constante $k$ é determinada pelo caso básico, pois é nele que as chamadas recursivas cessam (assim como a expansão $T(n)$).
$$\begin{align*}T(n-k) = T(1)\\n-k = 1\\k = n-1.\end{align*}$$
Portanto,
$$\begin{align*}T(n) = \frac{n!}{(n-(n-1))!}T(n-(n-1)) + \sum_{i=0}^{n-1-1}\frac{n!}{(n-i)!}f(n-i)\\T(n) = n!\underbrace{T(1)}_{c_0} + \sum_{i=0}^{n-2}\frac{n!}{(n-i)!}f(n-i)\\T(n) = c_0n! + n!\sum_{i=0}^{n-2}\frac{f(n-i)}{(n-i)!}.\end{align*}$$
O fator $n!$ foi retirado do somatório no último passo porque ele não depende de $i$.
Enquanto o primeiro termo (à esquerda) representa o custo para o cálculo dos determinantes de ordem um (caso básico), o segundo termo (à direita) representa o custo total das chamadas recursivas, isto é, quando não é o caso básico. Observe que o mesmo possui um fator $n!$. É claro, tudo depende da função de custo $f(n)$.
Primeira Análise: Custo Linear
A quantidade de operações aritméticas cresce linearmente em função de $n$, a cada chamada recursiva. Por exemplo, quando $n=3$, temos duas somas ($n-1$), seis multiplicações ($2n$) e três potenciações ($n$). Além disso, temos as somas nos expoentes, ou seja, mais três somas. Portanto,
$$f(n) = c_1(2n-1)+2c_2n+c_3n.$$
$c_1$ é o custo de uma soma, $c_2$ é o custo de uma multiplicação e $c_3$ é o custo de uma potenciação. Simplificando, temos:
$$f(n) = (2c_1+2c_2+c_3)n - c_1.$$
Já que o que realmente importa é a ordem de crescimento de $f(n)$, então vamos considerar que $f(n)=cn$, onde $c$ é uma constante suficientemente grande. Substituindo na fórmula de $T(n)$, obtemos
$$\begin{align*}T(n) = c_0n! + n!\sum_{i=0}^{n-2}\frac{c(n-i)}{(n-i)!}\\T(n) = c_0n! + cn!\sum_{i=0}^{n-2}\frac{(n-i)}{(n-i)!}.\end{align*}$$
Agora, basta resolver o somatório
$$\sum_{i=0}^{n-2}\frac{(n-i)}{(n-i)!} = \sum_{i=0}^{n-2}\frac{1}{(n-i-1)!}.$$
Deslocando o índice, temos
$$\sum_{i=1}^{n-1}\frac{1}{\left[n-(i-1)-1\right]!} = \sum_{i=1}^{n-1}\frac{1}{(n-i)!}.$$
O primeiro termo da série é $\cfrac{1}{(n-1)!}$ e o último termo é igual a 1. Isto é, os termos da série formam uma sequência crescente com limite superior igual a 1. Podemos inverter a ordem da soma
$$\sum_{i=1}^{n-1}\frac{1}{(n-i)!} = \sum_{i=1}^{n-1}\frac{1}{i!}.$$
A vantagem é que os termos da série não dependem mais de $n$ diretamente. Entretanto, eu particularmente não conheço uma maneira de representar essa série por meio de funções elementares.
É fácil de ver que o valor dessa série não cresce muito à medida que $n$ cresce (observe no gráfico a seguir que ela converge para uma constante), então é conveniente analisar o que acontece quando $n$ tende ao infinito.
Tomando o limite da série para $n$ tendendo ao infinito, temos
$$\lim_{n\rightarrow\infty}\sum_{i=1}^{n-1}\frac{1}{i!} = \sum_{i=1}^{\infty}\frac{1}{i!}.$$
A série infinita à direita é similar à fórmula da Série de Taylor
$$g(x) = \sum_{i=0}^{\infty}\frac{g^{(i)}(x_0)}{i!}(x-x_0)^i.$$
Se tomarmos $x_0=0$ e $x=1$, então obtemos
$$g(1) = \sum_{i=0}^{\infty}\frac{g^{(i)}(0)}{i!}.$$
Eu troquei $f(x)$ por $g(x)$ para não causar confusão com a função de custo $f(n)$.
Se fizermos $g(x) = e^{x}$, então
$$\begin{align*}e^1 = \sum_{i=0}^{\infty}\frac{e^0}{i!}\\e = \sum_{i=0}^{\infty}\frac{1}{i!}.\end{align*}$$
Expandindo o primeiro termo da série, obtemos
$$e = 1+\sum_{i=1}^{\infty}\frac{1}{i!}.$$
Logo,
$$\sum_{i=1}^{\infty}\frac{1}{i!}=e-1= 1,718...$$
Com isso, concluímos que a série inicial nunca ultrapassará a constante $e-1$, isto é
$$\sum_{i=0}^{n-2}\frac{(n-i)}{(n-i)!} \leq e-1.$$
Podemos ainda fazer a aproximação
$$\sum_{i=0}^{n-2}\frac{(n-i)}{(n-i)!} \approx e-1.$$
Logo,
$$\begin{align*}T(n) = c_0n! + c(e-1)n!\\T(n) = \left[c_0 + c(e-1)\right]n!.\end{align*}$$
Portanto, $T(n) = O(n!)$ ou ainda $T(n)=\Theta(n!)$.
Segunda Análise: Custo Cúbico
Na análise anterior, consideramos apenas o custo das operações aritméticas. Entretanto, ao implementar o teorema em alguma linguagem de programação, geralmente é preciso alocar memória para as matrizes utilizadas no cálculo do cofatores.
Como são $n$ matrizes e precisamos realizar uma varredura completa na matriz original para cada uma delas, então o custo é proporcional a uma função cúbica: $f(n) = O(n^3)$. Isso porque uma varredura numa matriz de ordem $n$ tem custo proporcional a $n^2$.
Vamos tomar $f(n) = cn^3$, onde $c$ é uma constante suficientemente grande. Substituindo, na série de $T(n)$, temos:
$$\sum_{i = 0}^{n-2}\frac{c(n-i)^3}{(n-i)!} = c\sum_{i = 0}^{n-2}\frac{(n-i)^3}{(n-i)!}.$$
Observe os termos da série
$$\sum_{i = 0}^{n-2}\frac{(n-i)^3}{(n-i)!} = \frac{n^3}{n!}+\frac{(n-1)^3}{(n-1)!}+\ldots+\frac{3^2}{3!} + \frac{2^2}{2!}.$$
Ou seja, podemos reescrever a série da seguinte forma:
$$\sum_{i = 2}^{n}\frac{i^3}{i!}.$$
Realizando algumas simplificações, temos
$$\begin{align*}\sum_{i = 2}^{n}\frac{i^3}{i!}&=\sum_{i = 2}^{n}\frac{i\times i^2}{i\times(i-1)!}\\&=\sum_{i = 2}^{n}\frac{i^2}{(i-1)!}\\&=\sum_{i = 1}^{n-1}\frac{(i+1)^2}{i!}\\&=\sum_{i = 1}^{n-1}\frac{i^2+2i+1}{i!}\\&=\sum_{i = 1}^{n-1}\frac{i^2}{i!}+2\sum_{i = 1}^{n-1}\frac{i}{i!}+\sum_{i = 1}^{n-1}\frac{1}{i!}.\end{align*}$$
Assim como na análise anterior, vamos tomar o limite $n\rightarrow\infty$, pois o valor da série em questão também converge para uma constante à medida que o valor de $n$ aumenta:
$$\lim_{n\rightarrow\infty}\sum_{i = 2}^{n}\frac{i^3}{i!}=\sum_{i = 2}^{\infty}\frac{i^3}{i!}=\sum_{i = 1}^{\infty}\frac{i^2}{i!}+2\sum_{i = 1}^{\infty}\frac{i}{i!}+\sum_{i = 1}^{\infty}\frac{1}{i!}$$
Já sabemos o resultado da última série, pois foi calculado na seção anterior:
$$\sum_{i = 1}^{\infty}\frac{1}{i!} = e-1.$$
Vamos resolver a primeira série:
$$\begin{align*}\sum_{i = 1}^{\infty}\frac{i^2}{i!}&=\sum_{i = 1}^{\infty}\frac{i}{(i-1)!}\\&=\sum_{i = 0}^{\infty}\frac{i+1}{i!}\\&=\sum_{i = 0}^{\infty}\frac{i}{i!}+\underbrace{\sum_{i = 0}^{\infty}\frac{1}{i!}}_{=e}\\&=\sum_{i = 1}^{\infty}\frac{i}{i!} + e\\&=e+\sum_{i = 1}^{\infty}\frac{i}{i\times(i-1)!}\\&=e+\sum_{i = 1}^{\infty}\frac{1}{(i-1)!}\\&=e+\sum_{i = 0}^{\infty}\frac{1}{i!}\\&=e+e=2e.\end{align*}$$
Por fim, vamos resolver a segunda série:
$$2\underbrace{\sum_{i=1}^{\infty}\frac{i}{i!}}_{=e} = 2e$$
Observe que reaproveitamos o cálculo anterior. Finalmente, o valor da série será
$$\sum_{i=2}^{\infty} \frac{i^3}{i!} = 2e+2e+e-1=5e-1=12,59...$$
Ou seja, mesmo com $f(n)=cn^3$, que tem ordem de crescimento maior que $cn$, a série convergiu para uma constante ao tomarmos o limite assintótico da série original. A constante em questão é maior do que a constante do caso linear. E deveria ser, afinal o crescimento de uma função cúbica é maior do que o crescimento de uma função linear.
Sem mais delongas, concluímos que $T(n)=O(n!)$, ou ainda, $T(n)=\Theta(n!)$, que é o mesmo resultado da seção anterior. Entretanto, é importante ter em mente que as notações Teta e Big-O apenas nos dão informações do comportamento assintótico. Obviamente, se o algoritmo possui um custo por chamada recursiva proporcional a $n^3$, então ele é pior do que a mesma versão do algoritmo com custo por chamada recursiva linear.
Considerações Finais
Após essa extensa análise, chegamos a já conhecida complexidade do teorema de Laplace, que é de $O(n!)$. Um fato notável é que essa complexidade não se alterou quando consideramos o custo para a gerar as matrizes do cálculo dos cofatores.
Esse resultado apenas reforça o quão inviável o teorema é para calcular determinantes num computador. A complexidade não muda mesmo otimizando o algoritmo com as regras que permitem o cálculo direto de determinantes de ordem dois e três.
É claro, sabe-se que quanto mais zeros a linha (ou coluna) escolhida para o cálculo possui, mais fácil será calcular o determinante. Entretanto, este é um caso bem particular. Além disso, para aproveitarmos essa característica, devemos procurar tal linha (ou coluna), caso ela exista, o que representa mais custo computacional.
A única vantagem aparente é que o teorema de Laplace é um método numericamente estável para computar determinantes. Mesmo assim, não compensa utilizá-lo num contexto prático. Existem algoritmos que, apesar de terem problemas de estabilidade numérica, são bem mais rápidos e têm complexidade polinomial.
Por fim, tenha em mente que a análise exposta aqui é puramente computacional. O fato do teorema ser ineficiente não significa que ele seja ruim ou inútil. O teorema de Laplace é um dos teoremas mais importantes da Álgebra Linear. Com ele, por exemplo, você consegue facilmente provar que o determinante de uma matriz triangular é igual ao produto dos elementos da diagonal principal, e este resultado é essencial para o cálculo de determinantes em tempo polinomial.
Referências
- [1] DANTE, L. R. Matemática: volume único. 1 ed. São Paulo: Ática, 2005.
- [2] FELIPE, H. Teorema de Laplace em Java. Acesso em 19 de agosto de 2017.
- [3] IEZZI, G. et al. Fundamentos de Matemática Elementar: Sequências, Matrizes, Determinantes, Sistemas. 2 ed. São Paulo: Editora Atual, 1977.
- [4] WEISSTEIN, E. W. Determinant Expansion by Minors. Acesso em 19 de agosto de 2017.
- [5] WEISSTEIN, E. W. Taylor Series. Acesso em 19 de agosto de 2017.
Observação
Se você tiver problemas para ler o artigo, isto é, se as fórmulas matemáticas não carregarem, você pode ler a versão em PDF aqui: Artigo em PDF.
Agradeço imensamente o esforço colocado para explicar esse tópico e produzir um artigo com tamanha qualidade. Embora todos saibam que o teorema é inviável para matrizes maiores, falando computacionalmente, é sempre bom saber as razões para esta complexidade.
ResponderExcluirObrigado!
Excluir