Resolução de $Ax=b$

Nesta secção, vamos apresentar uma forma de resolução da equação $Ax=b$, fazendo uso da factorização $PA=LU$ estudada atrás. Vejamos de que forma essa factorização é útil no estudo da equação.

Considere a equação $\left[\begin{array}{ccc} 1&2&3\\ 0&4&5\\ 0&0&6\end{array}\right]\left[\begin... ... x_2 x_3\end{array}\right]=\left[\begin{array}{c}7 8 9\end{array}\right]$. O sistema associado escreve-se como $\left\{ \begin{array}{r} x_1+2x_2+3x_3 =7\\ 4x_2+5x_3=8\\ 6x_3=9\end{array}\right.$. Calculando o valor de $x_3$ pela última equação, este é substituido na segunda equação para se calcular o valor de $x_2$, que por sua vez são usados na primeira equação para se obter $x_1$. Procedeu-se à chamada substituição inversa para se calcular a única (repare que a matriz dada é invertível) solução do sistema. Em que condições se pode usar a substituição inversa? Naturalmente quando a matriz dada é triangular superior com elementos diagonais não nulos. Mas também noutros casos. Considere a equação matricial $\left[\begin{array}{ccc} 1&2&3\\ 0&0&4\end{array}\right]\left[\begin{array}{c}x_1 x_2 x_3\end{array}\right]=\left[\begin{array}{c}5 6\end{array}\right]$. A matriz do sistema não é quadrada, mas o método da susbstituição inversa pode ainda ser aplicado. O sistema associado é $\left\{ \begin{array}{r} x_1+2x_2+3x_3 =5\\ 4x_3=6\end{array}\right.$, donde $x_3=\frac{3}{2}$, e $x_1$ dependerá do valor de $x_2$. A solução geral do sistema é $(x_1,x_2,x_3)=(5-\frac{9}{2}-2x_2,x_2,\frac{3}{2})=(5-\frac{9}{2},0,\frac{3}{2})+x_2(-2,1,0)$. Mais à frente veremos qual a importância de escrevermos a solução na última forma apresentada. É fácil constatar que a substituição inversa é aplicável desde que a matriz do sistema seja uma matriz escada de linhas. A estatégia na resolução da equação irá, portanto, passar pela matriz escada obtida por Gauss, para depois se aplicar a substituição inversa. Desde que o sistema seja possível, claro.

Considere o sistema $Ax=b$ e a factorização $PA=LU$. Ou seja, $U=L^{-1}PA$. Recorde que $L^{-1}P$ reflecte as operações elementares efectuadas nas linhas de $A$ por forma a se obter a matriz escada, percorrendo os passos do AEG. Multiplique ambos os membros de $Ax=b$, à esquerda, por $L^{-1}P$ para obter $L^{-1}PA=L^{-1}Pb$. Como $U=L^{-1}PA$ tem-se que $Ux=L^{-1}Pb$, e daqui podemos aplicar a substituição inversa... depois de se determinar o termo independente $L^{-1}Pb$. Recorde que $L^{-1}P$ reflecte as operações elementares efectuadas nas linhas de $A$, de modo que para se obter $L^{-1}Pb$ basta efectuar essas mesmas operações elementares, pela mesma ordem, nas linhas de $b$. Por forma a simplificar o raciocínio e evitar possíveis enganos, esse processo pode ser efectuado ao mesmo tempo que aplicamos o AEG nas linhas de A. Consideramos, para esse efeito, a matriz aumentada do sistema $\left[\begin{array}{c\vert c}A&b\end{array}\right]$, aplicamos o AEG para se obter a matriz $\left[\begin{array}{c\vert c}U &c\end{array}\right]$, onde $U$ é matriz escada de linhas e $c=L^{-1}Pb$. Se o sistema for possível, aplica-se a substituição inversa a $Ux=c$.

As soluções de $Ax=b$ são exactamente as mesmas de $Ux=c$, e por este facto dizem-se equações equivalentes, e os sistemas associados são equivalentes. De facto, se $v$ é solução de $Ax=b$ então $Av=b$, o que implica, por multiplicação à esquerda por $L^{-1}P$ que $L^{-1}PAv=L^{-1}Pb$, ou seja, que $Uv=c$. Por outro lado, se $Uv=c$ então $LUv=Lc$ e portanto $PAv=Lc$. Ora $c=L^{-1}Pb$, e portanto $Lc=Pb$. Obtemos então $PAv=Pb$. Como $P$ é invertível, segue que $Av=b$ e $v$ é solução de $Ax=b$.

Visto determinar as soluções de $Ax=b$ é o mesmo que resolver $Ux=c$, interessa-nos, então classificar este último.

Como exemplo, considere a equação $\left[\begin{array}{ccc}1&2&3\\ 0&0&0\end{array}\right]\left[\begin{array}{c}x_1 x_2 x_3\end{array}\right]=\left[\begin{array}{c}4 5\end{array}\right]$. A segunda equação do sistema associado reflete a igualdade $0=5$, o que é impossível. A equação é impossível já que não tem soluções. A matriz aumentada associada à equação é $\left[\begin{array}{ccc\vert c} 1&2&3&4\\ 0&0&0&5\end{array}\right]$. Repare que a característica da matriz $A$ é 1 enquanto que a caratacterística da matriz aumentada $[A\vert b]$ é 2.

Como é fácil verificar, a característica da matriz a que se acrescentou linhas ou colunas é não inferior à característica da matriz inicial. Por consequência, $\mathrm{car}(A)\le \mathrm{car}([A\vert b])$.

Teorema 3.2.1   A equação matricial $Ax=b$ é consistente se e só $\mathrm{car}(A)=\mathrm{car}\left(\left[\begin{array}{c\vert c}A & b\end{array}\right]\right)$.

Considere $PA=LU$ e $c=L^{-1}Pb$. A equação $Ax=b$ é equivalente à equação $Ux=c$, e portanto $Ax=b$ tem solução se e só se $Ux=c$ tem solução. Tal equivale a dizer que o número de linhas nulas de $U$ iguala o número de linhas nulas de $[U\vert c]$. De facto, o número sendo o mesmo, por substituição inversa é possível obter uma solução de $Ux=c$, e caso o número seja distinto então obtemos no sistema associado a igualdade $0=c_i$, para algum $c_i \ne 0$, o que torna $Ux=c$ impossível. Se o número de linhas nulas de $U$ iguala o de $[U\vert c]$ então o número de linhas não nulas de $U$ iguala o de $[U\vert c]$.

Octave
Considere a equação matricial $Ax=b$ onde $A=\left[\begin{array}{ccc} 2& 2& 1\\ 1& 1 & \frac{1}{2}\end{array}\right]$ e $b=\left[\begin{array}{c} -1 1\end{array}\right]$. A equação é consistente se e só se $\mathrm{car}(A)=\mathrm{car}([A\vert b])$

> A=[2 2 1; 1 1 0.5]; b=[-1; 1];
> rank(A)
ans = 1
> [L,U,P]=lu(A)
L =

  1.00000  0.00000
  0.50000  1.00000

U =

  2  2  1
  0  0  0

P =

  1  0
  0  1

Portanto, $\mathrm{car}(A)=1$.

> rank([A b])
ans = 2
> Aaum =

   2.00000   2.00000   1.00000  -1.00000
   1.00000   1.00000   0.50000   1.00000
> [Laum,Uaum,Paum]=lu(Aaum)
Laum =

  1.00000  0.00000
  0.50000  1.00000

Uaum =

   2.00000   2.00000   1.00000  -1.00000
   0.00000   0.00000   0.00000   1.50000

Paum =

  1  0
  0  1

Ora a caraterística da matriz aumentada é 2, pelo que $Ax=b$ é inconsistente.

Dada a equação $A\left[\begin{array}{c}x_1 x_2 \vdots x_n \end{array}\right]=b$, considere $U\left[\begin{array}{c}x_1 x_2 \vdots x_n \end{array}\right]=c$ equivalente à primeira fazendo uso da factorização $PA=LU$ da forma habitual. A incógnita $x_i$ diz-se incógnita básica se a coluna $i$ de $U$ tem pivot. Uma incógnita diz-se livre se não for básica. A nulidade de $A$, $\mathrm{nul}(A)$, é o número de incógnitas livres na resolução de $Ax=0$.

Octave
Na equação $Ax=b$, com $A=\left[\begin{array}{ccc} 2 & 2 & 1 1 & 1 & -1\end{array}\right],x= \left[\... ...x_2 x_3 \end{array}\right],b=\left[\begin{array}{c}-1 1 \end{array}\right]$, obtemos a decomposição

> A=[2 2 1; 1 1 -1]; b=[-1; 1];
> [L,U,P]=lu(A)
L =

  1.00000  0.00000
  0.50000  1.00000

U =

   2.00000   2.00000   1.00000
   0.00000   0.00000  -1.50000

P =

  1  0
  0  1

Repare que $\mathrm{car}(A)=2$. Ora $2=\mathrm{car}(A) \le \mathrm{car}([A\vert b])\le 2$, já que a característica de uma matriz é não superior ao seu número de linhas e ao seu número de colunas. Segue que $\mathrm{car}([A\vert b])=2$. A equação $Ax=b$ é, portanto, consistente. Façamos, então, a classificação das incógnitas $x_1,x_2,x_3$ em livres e em básicas. Atente-se à matriz escada de linhas $U$ apresentada atrás. As colunas $1$ e $3$ têm como pivots, respectivamente, $2$ e $-\frac{3}{2}$. As incógnitas $x_1$ e $x_3$ são básicas. Já $x_2$ é livre pois a coluna $2$ de $U$ não tem pivot.

Qual o interesse neste tipo de classificação das incógnitas? A explicação é feita à custa do exemplo anterior. A equação $Ax=b$ é equivalente à equação $Ux=c$, com $U=\left[\begin{array}{ccc} 2 &2&1 0&0&-\frac{3}{2}\end{array}\right],c=\left[\begin{array}{c}-1 \frac{3}{2}\end{array}\right]$.

Octave
Com os dados fornecidos,

> [Laum,Uaum,Paum]=lu([A b])
Laum =

  1.00000  0.00000
  0.50000  1.00000

Uaum =

   2.00000   2.00000   1.00000  -1.00000
   0.00000   0.00000  -1.50000   1.50000

Paum =

  1  0
  0  1

Podemos, agora, aplicar o método da substituição inversa para obter as soluções da equação. Esse método é aplicado da seguinte forma:

1. obtem-se o valor das incógnitas básicas $x_i$ no sentido sul $\rightarrow$norte,
2. as incógnitas livres comportam-se como se de termos independentes se tratassem.

Para conveniência futura, a solução é apresentada na forma

$$\left[\begin{array}{c} x_1 x_2 \vdots x_n \end{array}\righ... ...]+ \dots x_{i_k} \left[\begin{array}{c} ? ? \vdots ? \end{array}\right]$$

onde $x_{i_\ell}$ são as incógnitas livres.

Voltando ao exemplo, recorde que se obteve a equação equivalente à dada

$$\left[\begin{array}{ccc} 2 &2&1 0&0&-\frac{3}{2}\end{array}\rig... ...x_3\end{array}\right]=\left[\begin{array}{c}-1 \frac{3}{2}\end{array}\right].$$

Resolvendo a última equação correspondente, obtemos o valor da incógnita básica $x_3$. De facto, $-\frac{3}{2} x_3=\frac{3}{2}$ implica $x_3=-1$. Na equação $2x_1+2x_2 +x_3= -1$, o valor de $x_3$ é conhecido (bastando-nos, portanto, fazer a substituição) e a incógnita $x_2$ é livre, comportando-se então como termo independente. Já $x_1$ é básica, e resolve-se a equação em relação a esta. Obtemos $x_1=\frac{-2x_2}{2}=-x_2$. Para cada escolha de $x_2$ obtemos outo valor para $x_1$. A solução geral é da forma

$$(x_1,x_2,x_3)=(-x_2,x_2,-1)= (0,0,-1)+x_2(-1,1,0),$$

onde $x_2$ varia livremente em ${\mathbb{K}}$.

Num sistema possível, a existência de incógnitas livres confere-lhe a existência de várias soluções, e portanto o sistema é possível indeterminado. Ora, se o número de incógnitas é $n$ e se $k$ delas são básicas, então as restantes $n-k$ são livres. Recorde que o número de incógnitas iguala o número de colunas da matriz do sistema, e que a característica de uma matriz é igual ao número de pivots. Existindo, no máximo, um pivot por coluna, e como o número das colunas com pivots é igual ao número de incógnitas básicas, segue que a característica da matriz é igual ao número de incógnitas básicas. A existência de incógnitas livres é equivalente ao facto de existirem colunas sem pivot, ou seja, do número de colunas ser estritamente maior que a característica da matriz. De facto, as incógnitas livres são, em número, igual ao número de colunas sem pivot.

Teorema 3.2.2   A equação consistente $Ax=b$, onde $A$ é $m \times n$, tem uma única solução se e só se $\mathrm{car}(A)=n$.

Corolário 3.2.3   Um sistema possível de equações lineares com menos equações que incógnitas é indeterminado.

Recorde que o número de incógnitas livres é o número de colunas sem pivot na resolução de um sistema possível $Ax=b$. Por outro lado, a nulidade de $A$, $\mathrm{nul}(A)$, é o número de incógnitas livres que surgem na resolução de $Ax=0$. Recorde ainda que a característica de $A$, $\mathrm{car}(A)$, é o número de pivots na implementação de Gauss, que por sua vez é o número de colunas com pivot, que iguala o número de incógnitas básicas na equação $Ax=0$. Como o número de colunas de uma matriz iguala o número de incógnitas equação $Ax=0$, e estas se dividem em básicas e em livres, correspondendo em número a, respectivamente, $\mathrm{car}(A)$ e $\mathrm{nul}(A)$, temos o resultado seguinte:

Teorema 3.2.4   Para $A$ matriz $m \times n$,

$$n=\mathrm{car}(A)+\mathrm{nul}(A).$$

O resultado seguinte descreve as soluções de uma equação possível $Ax=b$ à custa do sistema homogéneo associado (ou seja, $Ax=0$) e de uma solução particular $v$ de $Ax=b$.

Teorema 3.2.5   Sejam $Ax=b$ uma equação consistente e $v$ uma solução particular de $Ax=b$. Então $w$ é solução de $Ax=b$ se e só se existir $u\in N(A)$ tal que $w=v+u$.

Suponha $v,w$ soluções de $Ax=b$. Pretende-se mostrar que $w-v \in N(A)$, ou seja, que $A(w-v)=0$. Ora $A(w-v)=Aw-Av=b-b=0$. Basta, portanto, tomar $u=w-v$.

Reciprocamente, assuma $v$ solução de $Ax=b$ e $u$ solução de $Ax=0$. Pretende-se mostrar que $w=v+u$ é solução de $Ax=b$. Para tal, $Aw=A(v+u)=Av+Au=b+0=b$.

Ou seja, conhecendo o conjunto das soluções de $Ax=0$ e uma solução particular de $Ax=b$, conhece-se o conjunto das soluções de $Ax=b$.

Octave
Considere a equação matricial $Ax=b$, com $A=\left[\begin{array}{ccc} 9 & -2 & 4 \\ 6 & -5 & 0 \\ -12 & -1 & -8 \end{array}\right]$ e $b=\left[\begin{array}{c} 3 5 -1\end{array}\right]$. O sistema é consistente, já que $\mathrm{car}(A)=\mathrm{car}([A \vert b])=2$:

> rank ([A b])
ans = 2
> rank (A)
ans = 2

Sendo a característica de $A$ igual a 2 e tendo a matriz 3 colunas, então existe uma, e uma só, incógnita livre na resolução de $Ax=b$. Façamos, então, a divisão das incógnitas em livres e básicas. Para tal, determina-se a matriz escada de linhas obtida da matriz aumentada $[A\vert b]$:

> [Laum,Uaum,Paum]=lu([A b])
Laum =

   1.00000   0.00000   0.00000
  -0.50000   1.00000   0.00000
  -0.75000   0.50000   1.00000

Uaum =

  -12.00000   -1.00000   -8.00000   -1.00000
    0.00000   -5.50000   -4.00000    4.50000
    0.00000    0.00000    0.00000    0.00000

Paum =

  0  0  1
  0  1  0
  1  0  0

Se $x=(x_1,x_2,x_3)$, as incógnitas básicas são $x_1$ e $x_2$, enquanto que $x_3$ é incógnita livre.

Como vimos do resultado anterior, conhecendo uma solução particular de $Ax=b$, digamos, $v$, e conhecendo $N(A)$, ou seja, o conjunto das soluções de $Ax=0$, então as soluções de $Ax=b$ são da forma $v+u$, onde $u\in N(A)$. Uma solução particular pode ser encontrada tomando a incógnita livre como zero. Ou seja, considerando $x_3=0$. A sunbstituição inversa fornece o valor das incógnitas básicas $x_1,x_2$:

> x2=Uaum(2,4)/Uaum(2,2)
x2 = -0.81818
> x1=(Uaum(1,4)-Uaum(1,2)*x2)/Uaum(1,1)
x1 = 0.15152

Este passo pode ser efectuado, de uma forma mais simples, como

> A\b
ans =

   0.31235
  -0.62518
  -0.26538

Resta-nos determinar $N(A)$:

> null (A)
ans =

   0.44012
   0.52814
  -0.72620

O vector $u$ que nos é indicado significa que $N(A)$ é formado por todas a colunas da forma $\alpha u$. Se, por ventura, nos forem apresentados vários vectores v1 v2 ... vn, então os elementos de $N(A)$ escrevem-se da forma $\alpha_1 v_1 +\alpha_2 v_2 +\dots +\alpha_n v_n$.

Considere, agora, a matriz

> A=[2 2 2 0; 1 1 2 2];

Esta matriz tem característica 2, como se pode verificar à custa da factorização $PA=LU$:

> [L,U,P]=lu(A)
L =

  1.00000  0.00000
  0.50000  1.00000

U =

  2  2  2  0
  0  0  1  2

P =

  1  0
  0  1

A nulidade é 2, pelo que existem 2 incógnitas livres na resolução de $A\left[\begin{array}{cccc} x_1 & x_2 & x_3 & x_4\end{array}\right]^T =0_{2\times 1}$. As incógnitas livres são as correspondentes à colunas de $U$ que não têm pivot; no caso, $x_2$ e $x_4$. O sistema associado à equação $Ux=0$ é $\left\{ \begin{array}{r} 2x_1+2x_2+2x_3=0\\ x_3+2x_4=0\end{array}\right.$. Resolvendo o sistema em relação à incógnitas básicas $x_1,x_3$, e por substituição inversa, obtemos $x_3=-2x_4$, que por sua vez fornece, substituindo na primeira equação, $x_1=\frac{1}{2} \left( -2x_2 +4x_4\right)= -x_2+2x_4$. Ou seja, a solução geral de $Ax=0$ é

$$(x_1,x_2,x_3,x_4)=(-x_2+2x_4,x_2,-2x_4,x_4)=x_2(-1,1,0,0)+x_4(2,0,-2,1).$$

Sem nos alongarmos em demasia neste assunto, o Octave, como já foi referido, contém uma instrução que calcula o núcleo de uma matriz:

> null(A)
ans =

  -0.71804  -0.35677
   0.10227   0.79524
   0.61577  -0.43847
  -0.30788   0.21924

O resultado apresentado indica os vectores que decrevem o conjunto $N(A)$: todo o elemento de $N(A)$ se escreve como soma de múltiplos dos dois vectores apresentados. Mais, os vectores fornecidos são ortogonais entre si e têm norma 1.

> null(A)(:,1)'*null(A)(:,2)
ans =  6.2694e-17
> null(A)(:,1)'*null(A)(:,1)
ans = 1.0000
> null(A)(:,2)'*null(A)(:,2)
ans = 1