Fatoração de Cholesky

é definida positiva.

A resolução de sistemas lineares em que a matriz dos coeficientes é simétrica e definida positiva é frequente em aplicações. Veremos que tais matrizes podem ser fatoradas na forma:

A = GG^t

onde

G: n \times n

é uma matriz triangular inferior com elementos da diagonal estritamente positivos. Esta fatoração é conhecida como fatoração de Cholesky. Para um caso geral é difícil verificar se uma matriz é definida positiva, uma vez que não temos uma caracterização simples. Na prática utilizamos a fatoração de Cholesky para esta verificação.

Teorema 1: Se uma matriz

A: n \times n

é definida positiva, então

A

é inversível e sua inversa é também definida positiva.

Demonstração: AQUI.

Teorema 2: Se

A:n \times n

é não singular, então

A^tA

é simétrica definida positiva.

Demonstração: AQUI.

Definição: O posto linha (coluna) de uma matriz

A:m \times n

é o número máximo de linhas (colunas) linearmente independentes de

A

. Pode-se mostrar que o posto linha é igual ao posto coluna e denotamos então o posto de

A

por

posto(A)

. Uma matriz

A:m \times n

tem posto completo se

posto(A) = min\left\lbrace m, n\right\rbrace

, isto é, se o posto é o maior valor possível.

Teorema 3: Sejam

B:n \times m

uma matriz com

m \leq n

posto(B) = m

, e

A:n \times n

uma matriz definida positiva. Então,

B^tAB

é definida positiva.

Demonstração: AQUI.

Definição: Seja

A:n\times n

uma matriz. As submatrizes principais

A_k, k = 1, ..., n

A

são as matrizes

k \times k

consistindo nas primeiras k linhas e colunas de

A

.

Teorema 4: Se

A:n \times n

é uma matriz definida positiva, então suas submatrizes principais

A_k, k = 1, ..., n

, são definidas positivas.

Demonstração: AQUI.

Exemplo 2: Considere a seguinte matriz definida positiva:

A = \left[\begin{array}{ccc} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 5 \end{array}\right]

Construímos as matrizes:

B_1 = \left[\begin{array}{c} 1 \\ 0 \\ 0 \end{array}\right], \;\;\; B_2 = \left[\begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{array}\right], \;\;\; B_3 = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]

Note que as submatrizes principais

A_k, k = 1,2,3

A

são:

A_1 = B_1^tAB_1 = \left[\begin{array}{c} 2 \end{array}\right], \;\;\; A_2 = B_2^tAB_2 = \left[\begin{array}{cc} 2 & 0 \\ 0 & 1 \end{array}\right], \;\;\; A_3 = B_3^tAB_3 = \left[\begin{array}{ccc} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 5 \end{array}\right]

que também são definidas positivas.

Teorema 5: Se

A: n \times n

é uma matriz definida positiva, então os elementos da diagonal de

A

são estritamente positivos, ou seja,

a_{ii} > 0, i = 1, ..., n

.

Demonstração: AQUI.

Voltar ao Topo.

Fatoração de Cholesky

Teorema 6 (Fatoração de Cholesky): Seja

A:n \times n

uma matriz simétrica.

A

é definida positiva se, e somente se, existe uma única matriz

G: n \times n

triangular inferior com elementos da diagonal estritamente positivos, tal que

A = GG^t

.

Demonstração:

(\Rightarrow)

A

é definida positiva, pelo Teorema 4 temos que suas submatrizes

A_k, k = 1, ..., n

, também são definidas positivas e, pelo Teorema 1 temos que elas são não singulares. Dessa forma, as hipóteses do Teorema sobre a existência e unicidade da fatoração LU se verificam para a matriz

A

e, portanto, existem e são únicos os fatores L e U tais que

A = LU

, com U triangular superior e L triangular inferior com diagonal unitária.

Temos que

det(A) = det(LU) = det(L)det(U)

. Como

A

é definida positiva ela é não singular e, portanto,

det(A) \neq 0

. Consequentemente,

det(U) \neq 0

e daí que

u_{ii} \neq 0, i = 1, ..., n

, uma vez que U é triangular superior e seu determinante é o produto dos elementos da diagonal. Dessa forma, é possível separar o fator U em

U = D\bar{U}

, escrevendo a fatoração:

A = LU = LD\bar{U}

onde D é uma matriz diagonal com elementos da diagonal iguais a

d_{ii} = u_{ii}

\bar{U}

tem entradas

\bar{u}_{ij} = \frac{u_{ij}}{u_{ii}}

.

Como

A

é simétrica então

LD\bar{U}

é simétrica e, como D é diagonal ela também é simétrica, assim temos:

(LD\bar{U})^t = LD\bar{U} \Leftrightarrow \bar{U}^tD^tL^t = LD\bar{U} \Leftrightarrow \bar{U}^tDL^t = LD\bar{U}

Como a fatoração LU é única, segue que

\bar{U} = L^t

. A matriz

L^t

é triangular superior com diagonal unitária e assim possui posto completo e é não singular. Então, para cada

y \in R^n

existe

x \in R^n

tal que

y = L^tx

e se

y \neq 0

então

x \neq 0

. Portanto, dado

y \in R^n

y \neq 0

, temos:

y^tDy = (L^tx)^tD(L^tx) = x^t(LDL^t)x = x^tAx > 0

A última desigualdade segue do fato que

A

é definida positiva. Portanto, a matriz D é também definida positiva e, pelo Teorema 5 os elementos da diagonal de D são estritamente positivos. Então, podemos escrever D como

D = \hat{D}\hat{D}

onde

\hat{D}

é diagonal com entradas da diagonal:

\hat{d}_{ii} = \sqrt{d_{ii}}

. Observe que podemos também, por exemplo, tomar a raiz quadrada negativa, mas para manter a unicidade, na fatoração de Cholesky convencionamos tomar a raiz quadrada positiva. Chamando

G = L\hat{D}

, temos:

A = LDL^t = L\hat{D}\hat{D}L^t = GG^t

Obtendo assim a fatoração de Cholesky:

A = GG^t

, onde o fator

G

é triangular inferior com diagonal estritamente positiva, denominado fator de Cholesky da matriz

A

(\Leftarrow)

Supondo agora que existe o fator

G

triangular inferior com diagonal estritamente positiva, tal que

A = GG^t

, observe que

G^t

é triangular superior com diagonal estritamente positiva e, portanto, é não singular. Pelo Teorema 2 segue que

(G^t)^tG^t = GG^t = A

é simétrica definida positiva.

Voltar ao Topo.

Cálculo do Fator de Cholesky

Usando a ideia da demonstração do Teorema 6, calculamos o fator de Cholesky

G

através da fatoração LU de

A

. No entanto, podemos obter o fator

G

diretamente pela equação matricial

A = GG^t

, sem precisar calcular os fatores L e U, reduzindo assim o número de operações necessárias.

Dada uma matriz

A: n \times n

simétrica e definida positiva, o fator

G: n \times n

triangular inferior com diagonal estritamente positiva será obtido a partir da equação matricial:

A = GG^t \Leftrightarrow \left[ \begin{array}{cccc} a_{11} & a_{21} & \cdots & a_{n1} \\ a_{21} & a_{22} & \cdots & a_{n2} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array}\right] = \left[ \begin{array}{cccc} g_{11} & & & \\ g_{21} & g_{22} & & \\ \vdots & \vdots & \ddots & \\ g_{n1} & g_{n2} & \cdots & g_{nn} \end{array}\right] \;\left[ \begin{array}{cccc} g_{11} & g_{21} & \cdots & g_{n1} \\ & g_{22} & \cdots & g_{n2} \\ & & \ddots & \vdots \\ & & & g_{nn} \end{array}\right]

Usamos aqui o fato que

A

é simétrica e, portanto,

a_{ij} = a_{ji}

. O cálculo é realizado por colunas. Considerando a coluna 1 de

A

, temos:

\left[ \begin{array}{c} a_{11} \\ a_{21} \\ \vdots \\ a_{n1} \end{array}\right] = G\; \left[ \begin{array}{c} g_{11} \\ 0 \\ \vdots \\ 0 \end{array}\right] = \left[ \begin{array}{c} g_{11}^2 \\ g_{21}g_{11} \\ \vdots \\ g_{n1}g_{11} \end{array}\right]

Assim:

g_{11} = \sqrt{a_{11}}

g_{j1} = \frac{a_{j1}}{g_{11}}

j = 2, ..., n

. Observe que só podemos tirar a raiz quadrada de

a_{11}

pois os elementos da diagonal de

A

são estritamente positivos, uma vez que

A

é definida positiva. Considerando a coluna 2 de

A

, temos:

\left[ \begin{array}{c} a_{21} \\ a_{22} \\ a_{32} \\ \vdots \\ a_{n2} \end{array}\right] = G \;\left[ \begin{array}{c} g_{21} \\ g_{22} \\ 0 \\ \vdots \\ 0 \end{array}\right] = \left[ \begin{array}{c} g_{11}g_{21} \\ g_{21}^2 + g_{22}^2 \\ g_{31}g_{21} + g_{32}g_{22} \\ \vdots \\ g_{n1}g_{21} + g_{n2}g_{22} \end{array}\right]

Assim:

g_{21}^2 + g_{22}^2 = a_{22} \Rightarrow g_{22} = \sqrt{a_{22} - g_{21}^2}

g_{j1}g_{21} + g_{j2}g_{22} = a_{j2} \Rightarrow g_{j2} = \frac{a_{j2} - g_{j1}g_{21}}{g_{22}}

j = 3, ..., n

, uma vez que os elementos

g_{j1}

já foram calculados. Seguimos com o mesmo raciocínio para as demais colunas e para obter a coluna k de

G

consideramos a equação matricial:

\left[ \begin{array}{c} a_{k1} \\ a_{k2} \\ \vdots \\ a_{kk} \\ a_{(k+1)k} \\ \vdots \\ a_{nk} \end{array}\right] = G \;\left[ \begin{array}{c} g_{k1} \\ g_{k2} \\ \vdots \\ g_{kk} \\ 0 \\ \vdots \\ 0 \end{array}\right]

Assim, teremos:

a_{kk} = g_{k1}^2 + g_{k2}^2 + ... + g_{kk}^2

e então:

g_{kk} = \sqrt{a_{kk} - \sum_{i=1}^{k-1}g_{ki}^2}

a_{jk} = g_{j1}g_{k1} + g_{j2} g_{k2} + ... + g_{jk}g_{kk}

j = (k+1), ..., n

. Como os elementos

g_{ik}, i = 1, ..., (k-1)

já foram calculados, temos:

g_{jk} = \frac{a_{jk} - \sum_{i=1}^{k-1}g_{ji} g_{ki}}{g_{kk}}

Observe que podemos realizar essa última divisão pois os elementos da diagonal de

G

são estritamente positivos e para obtermos

g_{kk}

temos que ter

a_{kk} - \sum_{i=1}^{k-1}g_{ki}^2 > 0

, mas isso ocorre pois

a_{kk} > 0

, uma vez que

A

é definida positiva, e

g_{kk}^2 > 0

. Dessa forma, como

a_{kk} = g_{k1}^2 + g_{k2}^2 + ... + g_{kk}^2

temos que

a_{kk} > \sum_{i=1}^{k-1}g_{ki}^2

. Assim, calculamos todas as colunas de

G

e obtemos a fatoração

A = GG^t

.

Algoritmo (Fatoração de Cholesky): Dada

A:n \times n

simétrica definida positiva, o fator de Cholesky

G:n \times n

tal que

A = GG^t

pode ser obtido através do seguinte algoritmo:
Algoritmo.

A fatoração de Cholesky requer em torno de

\frac{n^3}{3}

operações, o que é aproximadamente metade do número de operações necessárias na fase de eliminação da fatoração LU. Se em alguma etapa tivermos

s \leq 0

, o processo será interrompido e, consequentemente, saberemos que a matriz

A

não é definida positiva.

Exemplo 3: Considere a seguinte matriz:

A = \left[ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 8 & 12 \\ 3 & 12 & 27 \end{array} \right]

Vamos calcular a fatoração de Cholesky de

A

, verificando se ela é definida positiva:

A = GG^t \Leftrightarrow \left[ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 8 & 12 \\ 3 & 12 & 27 \end{array} \right] = \left[ \begin{array}{rrr} g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ g_{31} & g_{32} & g_{33} \end{array} \right] \;\left[ \begin{array}{rrr} g_{11} & g_{21} & g_{31} \\ 0 & g_{22} & g_{32} \\ 0 & 0 & g_{33} \end{array} \right]

A primeira coluna de

G

é obtida através da equação:

\left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right] = G\; \left[ \begin{array}{c} g_{11} \\ 0 \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}^2 \\ g_{21}g_{11} \\ g_{31}g_{11} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & \sqrt{1} \\ g_{21}g_{11} & = & 2 \\ g_{31}g_{11} & = & 3 \end{array}\right. \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & 1 \\ g_{21} & = & 2 \\ g_{31} & = & 3 \end{array}\right.

A segunda coluna de

G

é obtida através da equação:

\left[ \begin{array}{c} 2 \\ 8 \\ 12 \end{array} \right] = G\; \left[ \begin{array}{c} g_{21} \\ g_{22} \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}g_{21} \\ g_{21}^2 + g_{22}^2 \\ g_{31}g_{21} + g_{32}g_{22} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11}g_{21} & = & 2 \\ g_{21}^2 + g_{22}^2 & = & 8 \\ g_{31}g_{21} + g_{32}g_{22} & = & 12 \end{array}\right. \Rightarrow

\Rightarrow \left\lbrace \begin{array}{rrc} g_{22} & = & \sqrt{8 - 2^2} \\ g_{32} & = & \frac{12 - 6}{g_{22}} \end{array}\right. \Rightarrow \left\lbrace \begin{array}{rrr} g_{22} & = & 2 \\ g_{32} & = & 3 \end{array}\right.

E por fim, a terceira coluna de

G

é obtida através da equação:

\left[ \begin{array}{c} 3 \\ 12 \\ 27 \end{array} \right] = G\; \left[ \begin{array}{c} g_{31} \\ g_{32} \\ g_{33} \end{array} \right] = \left[ \begin{array}{c} g_{11}g_{31} \\ g_{21}g_{31} + g_{22}g_{32} \\ g_{31}^2 + g_{32}^2 + g_{33}^2 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11}g_{31} & = & 3 \\ g_{21}g_{31} + g_{22}g_{32} & = & 12 \\ g_{31}^2 + g_{32}^2 + g_{33}^2 & = & 27 \end{array}\right.

Da última equação temos:

g_{33} = \sqrt{27 - g_{31}^2 - g_{32}^2} = \sqrt{27 - 9 - 9} = \sqrt{9} \Rightarrow g_{33} = 3

Portanto, obtemos a fatoração:

A = GG^t \Leftrightarrow \left[ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 8 & 12 \\ 3 & 12 & 27 \end{array} \right] = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 2 & 0 \\ 3 & 3 & 3 \end{array} \right] \;\left[ \begin{array}{rrr} 1 & 2 & 3 \\ 0 & 2 & 3 \\ 0 & 0 & 3 \end{array} \right]

E assim, a matriz

A

é definida positiva.

Exemplo 4: Considere a seguinte matriz:

A = \left[ \begin{array}{rrr} 1 & 1 & 2 \\ 2 & 1 & 2 \\ 0 & 1 & 4 \end{array} \right]

Vamos calcular a fatoração de Cholesky de

A

, verificando se ela é definida positiva:

A = GG^t \Leftrightarrow \left[ \begin{array}{rrr} 1 & 1 & 2 \\ 2 & 1 & 2 \\ 0 & 1 & 4 \end{array} \right] = \left[ \begin{array}{rrr} g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ g_{31} & g_{32} & g_{33} \end{array} \right] \;\left[ \begin{array}{rrr} g_{11} & g_{21} & g_{31} \\ 0 & g_{22} & g_{32} \\ 0 & 0 & g_{33} \end{array} \right]

A primeira coluna de

G

é obtida através da equação:

\left[ \begin{array}{c} 1 \\ 2 \\ 0 \end{array} \right] = G \;\left[ \begin{array}{c} g_{11} \\ 0 \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}^2 \\ g_{21}g_{11} \\ g_{31}g_{11} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & \sqrt{1} \\ g_{21}g_{11} & = & 2 \\ g_{31}g_{11} & = & 0 \end{array}\right. \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & 1 \\ g_{21} & = & 2 \\ g_{31} & = & 0 \end{array}\right.

A segunda coluna de

G

é obtida através da equação:

\left[ \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right] = G\; \left[ \begin{array}{c} g_{21} \\ g_{22} \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}g_{21} \\ g_{21}^2 + g_{22}^2 \\ g_{31}g_{21} + g_{32}g_{22} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11}g_{21} & = & 1 \\ g_{21}^2 + g_{22}^2 & = & 1 \\ g_{31}g_{21} + g_{32}g_{22} & = & 1 \end{array}\right. \Rightarrow

\Rightarrow \left\lbrace \begin{array}{rrc} g_{22} & = & \sqrt{1 - 2^2} \\ g_{32} & = & \frac{1}{g_{22}} \end{array}\right. \Rightarrow \left\lbrace \begin{array}{rrc} g_{22} & = & \sqrt{-3} \\ g_{32} & = & \frac{1}{g_{22}} \end{array}\right.

Observe que neste caso, não existe um valor real

g_{22}

tal que

g_{22} = \sqrt{-3}

. Portanto, não podemos obter a fatoração de Cholesky da matriz

A

e concluímos que a matriz não é definida positiva.

Exemplo 5: Considere a seguinte matriz:

A = \left[ \begin{array}{rrr} 1 & 1 & 0 \\ 1 & 2 & -1 \\ 0 & -1 & 3 \end{array} \right]

Vamos calcular a fatoração de Cholesky de

A

, verificando se ela é definida positiva:

A = GG^t \Leftrightarrow \left[ \begin{array}{rrr} 1 & 1 & 0 \\ 1 & 2 & -1 \\ 0 & -1 & 3 \end{array} \right] = \left[ \begin{array}{rrr} g_{11} & 0 & 0 \\ g_{21} & g_{22} & 0 \\ g_{31} & g_{32} & g_{33} \end{array} \right]\; \left[ \begin{array}{rrr} g_{11} & g_{21} & g_{31} \\ 0 & g_{22} & g_{32} \\ 0 & 0 & g_{33} \end{array} \right]

A primeira coluna de

G

é obtida através da equação:

\left[ \begin{array}{c} 1 \\ 1 \\ 0 \end{array} \right] = G\; \left[ \begin{array}{c} g_{11} \\ 0 \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}^2 \\ g_{21}g_{11} \\ g_{31}g_{11} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & \sqrt{1} \\ g_{21}g_{11} & = & 1 \\ g_{31}g_{11} & = & 0 \end{array}\right. \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11} & = & 1 \\ g_{21} & = & 1 \\ g_{31} & = & 0 \end{array}\right.

A segunda coluna de

G

é obtida através da equação:

\left[ \begin{array}{r} 1 \\ 2 \\ -1 \end{array} \right] = G\; \left[ \begin{array}{c} g_{21} \\ g_{22} \\ 0 \end{array} \right] = \left[ \begin{array}{c} g_{11}g_{21} \\ g_{21}^2 + g_{22}^2 \\ g_{31}g_{21} + g_{32}g_{22} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11}g_{21} & = & 1 \\ g_{21}^2 + g_{22}^2 & = & 2 \\ g_{31}g_{21} + g_{32}g_{22} & = & -1 \end{array}\right. \Rightarrow

\Rightarrow \left\lbrace \begin{array}{rrc} g_{22} & = & \sqrt{2 - 1^2} \\ g_{32} & = & \frac{-1}{g_{22}} \end{array}\right. \Rightarrow \left\lbrace \begin{array}{rrr} g_{22} & = & 1 \\ g_{32} & = & -1 \end{array}\right.

E por fim, a terceira coluna de

G

é obtida através da equação:

\left[ \begin{array}{r} 0 \\ -1 \\ 3 \end{array} \right] = G\; \left[ \begin{array}{c} g_{31} \\ g_{32} \\ g_{33} \end{array} \right] = \left[ \begin{array}{c} g_{11}g_{31} \\ g_{21}g_{31} + g_{22}g_{32} \\ g_{31}^2 + g_{32}^2 + g_{33}^2 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrr} g_{11}g_{31} & = & 0 \\ g_{21}g_{31} + g_{22}g_{32} & = & -1 \\ g_{31}^2 + g_{32}^2 + g_{33}^2 & = & 3 \end{array}\right.

Da última equação temos:

g_{33} = \sqrt{3 - g_{31}^2 - g_{32}^2} = \sqrt{3 - 1} \Rightarrow g_{33} = \sqrt{2}

Portanto, obtemos a fatoração:

A = GG^t = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & -1 & \sqrt{2} \end{array} \right] \;\left[ \begin{array}{rrr} 1 & 1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & \sqrt{2} \end{array} \right]

E assim, a matriz

A

é definida positiva.

Voltar ao Topo.

Resolução de Sistemas Lineares Utilizando a Fatoração de Cholesky

Considere

Ax = b

um sistema linear cuja matriz

A

dos coeficientes é simétrica definida positiva. Então, podemos obter o fator de Cholesky

G

triangular inferior com diagonal estritamente positiva, tal que

A = GG^t

. Dessa forma, temos que

Ax = b \Leftrightarrow (GG^t)x = b

e a resolução do sistema linear segue da resolução dos seguintes sistemas triangulares:

(i)

Gy = b

(ii)

G^tx = y

Exemplo 6: Considere o seguinte sistema linear:

\left\lbrace \begin{array}{ccccccc} 1x_1 & + & 1x_2 & & & = & 1 \\ 1x_1 & + & 2x_2 & - & 1x_3 & = & 1 \\ & - & 1x_2 & + & 3x_3 & = & 2 \end{array}\right.

Note que a matriz dos coeficientes desse sistema é a mesma matriz

A

do Exemplo 5, já sabemos que ela é simétrica definida positiva e conhecemos sua fatoração de Cholesky:

A = GG^t = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & -1 & \sqrt{2} \end{array} \right] \;\left[ \begin{array}{rrr} 1 & 1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & \sqrt{2} \end{array} \right]

Dessa forma, o sistema

Ax = b \Leftrightarrow (GG^t)x = b

pode ser resolvido através de dois sistemas triangulares:

Gy = b

G^tx = y

. Para o primeiro sistema temos:

Gy = b \Leftrightarrow \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & -1 & \sqrt{2} \end{array} \right] \;\left[ \begin{array}{r} y_1 \\ y_2 \\ y_3 \end{array} \right] = \left[ \begin{array}{r} 1 \\ 1 \\ 2 \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} y_1 & & & & & = & 1 \\ y_1 & + & y_2 & & & = & 1 \\ & - & y_2 & + & \sqrt{2}y_3 & = & 2 \end{array}\right. \Rightarrow \left\lbrace \begin{array}{rrr} y_1 & = & 1 \\ y_2 & = & 0 \\ y_3 & = & \sqrt{2} \end{array}\right.

Considerando agora o segundo sistema triangular, temos:

G^tx = y \Leftrightarrow \left[ \begin{array}{rrr} 1 & 1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & \sqrt{2} \end{array} \right] \;\left[ \begin{array}{r} x_1 \\ x_2 \\ x_3 \end{array} \right] = \left[ \begin{array}{r} 1 \\ 0 \\ \sqrt{2} \end{array} \right] \Leftrightarrow \left\lbrace \begin{array}{rrrrrrr} x_1 & + & x_2 & & & = & 1 \\ & & x_2 & - & x_3 & = & 0 \\ & & & & \sqrt{2}x_3 & = & \sqrt{2} \end{array}\right. \Rightarrow \left\lbrace \begin{array}{rrr} x_1 & = & 0 \\ x_2 & = & 1 \\ x_3 & = & 1 \end{array}\right.

Portanto, a solução do sistema linear original é

(x_1, x_2, x_3) = (0, 1, 1)

.

Voltar ao Topo.

Última Atualização: 02/02/2016.