Eliminação de Gauss-Jordan

Na matemática , mais precisamente na álgebra linear , a eliminação de Gauss-Jordan , também chamada de método do pivô gaussiano , em homenagem a Carl Friedrich Gauss e Wilhelm Jordan , é um algoritmo para determinar as soluções de um sistema de equações lineares , para determinar o posto de uma matriz ou para calcular o inverso de uma matriz invertível (quadrada). Quando aplicamos a eliminação Gaussiana a uma matriz, obtemos sua forma reduzida em escala .

História

Este método é conhecido por matemáticos chineses desde pelo menos o que eu st  século AD. É referenciado no livro chinês Jiuzhang suanshu ( Os nove capítulos sobre arte matemática ), do qual constitui o oitavo capítulo, sob o título "Fang cheng" (o arranjo retangular). O método é apresentado por meio de dezoito exercícios. Em seu comentário datado de 263 , Liu Hui atribui a paternidade Ts'ang Chang, chanceler do imperador da China II ª  século aC.

Na Europa, este método foi descoberto e apresentado em forma moderna no XIX th  século . Em 1810, Carl Friedrich Gauss apresentou seu método dos mínimos quadrados em um livro que estudava o movimento do asteróide Pallas . No artigo 13 deste livro, ele descreve um método geral de resolução de um sistema de equações lineares que constitui a essência do método do pivô. Em 1888, Wilhelm Jordan publicou um livro de geodésia especificando como usar esse método e adotando uma notação ligeiramente diferente. É graças a este último livro que esse método se espalhou pelo Ocidente. É conhecido hoje com o nome de eliminação de Gauss-Jordan ou método do pivô de Gauss .

Algoritmo

Operações

O algoritmo de Gauss-Jordan produz a matriz em escala reduzida de uma matriz usando operações de linha elementares . Três tipos de operações elementares são usados:

• Troca de duas linhas;
• Multiplicação de uma linha por um escalar diferente de zero;
• Adicionando o múltiplo de uma linha a outra linha.

Pseudo-código

Let Ser uma matriz A de dimensões n × m  ;

O algoritmo de Gauss-Jordan é o seguinte:

Gauss-Jordan r = 0 (r est l'indice de ligne du dernier pivot trouvé) Pour j de 1 jusqu'à m (j décrit tous les indices de colonnes) | Rechercher max(|A[i,j]|, r+1 ≤ i ≤ n). Noter k l'indice de ligne du maximum | (A[k,j] est le pivot) | Si A[k,j]≠0 alors (A[k,j] désigne la valeur de la ligne k et de la colonne j) | | r=r+1 (r désigne l'indice de la future ligne servant de pivot) | | Diviser la ligne k par A[k,j] (On normalise la ligne de pivot de façon que le pivot prenne la valeur 1) | | Si k≠r alors | | | Échanger les lignes k et r (On place la ligne du pivot en position r) | | Fin Si | | Pour i de 1 jusqu'à n (On simplifie les autres lignes) | | | Si i≠r alors | | | | Soustraire à la ligne i la ligne r multipliée par A[i,j] (de façon à annuler A[i,j]) | | | Fin Si | | Fin Pour | Fin Si Fin Pour Fin Gauss-Jordan

Exemplo.

Começamos da matriz

NO=(2-10-12-10-12){\ displaystyle \ mathrm {A} = {\ begin {pmatrix} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \ end {pmatrix}}}

É uma matriz real, então o módulo de um coeficiente é seu valor absoluto.

• Primeira iteração, j = 1 (e r = 0):
  • passo 1.1: procuramos na primeira coluna da matriz o valor máximo dos valores absolutos dos coeficientes. Vale a pena 2, localizado em (1, 1), de modo que k = 1,
  • etapa 1.2.1: r = 1,
  • passo 1.2.2: r = k , não há troca,
  • passo 1.2.3: dividimos a linha 1 por A (1, 1) = 2, ou seja ,(1-1/20){\ displaystyle {\ begin {pmatrix} 1 e -1 / 2 e 0 \ end {pmatrix}}}
  • passo 1.2.4:
    • linha i = 2, temos A (2, 1) = -1; nós calculamos ,
      (-12-1)-(-1)×(1-1/20)=(03/2-1){\ displaystyle {\ begin {pmatrix} -1 & 2 & -1 \ end {pmatrix}} - (- 1) \ times {\ begin {pmatrix} 1 & -1 / 2 & 0 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 3/2 & -1 \ end {pmatrix}}}
    • linha i = 3, temos A (3, 1) = 0, então a linha não é modificada,
  • a matriz é então  ;
    NO′=(1-1/2003/2-10-12){\ displaystyle \ mathrm {A} '= {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & 3/2 & -1 \\ 0 & -1 & 2 \ end {pmatrix}}}
• segunda iteração, j = 2 (e r = 1):
  • passo 2.1: buscamos nas linhas 2 a 3 da segunda coluna o valor máximo em valor absoluto. Este é 3/2, localizado em (2, 2),
  • etapa 2.2.1: r = 2,
  • passo 2.2.2: r = k , não há troca.
  • passo 2.2.3: dividimos a linha 2 por A '(2, 2) = 3/2, ou seja ,(01-2/3){\ displaystyle {\ begin {pmatrix} 0 & 1 e -2 / 3 \ end {pmatrix}}}
  • passo 2.2.4:
    • linha i = 1, temos A '(1, 2) = -1/2; nós calculamos ,
      (1-1/20)-(-1/2)×(01-2/3)=(10-1/3){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \ end {pmatrix}} - (- 1/2) \ times {\ begin {pmatrix} 0 & 1 & -2 / 3 \ end {pmatrix }} = {\ begin {pmatrix} 1 & 0 & -1 / 3 \ end {pmatrix}}}
    • linha i = 3, temos A '(3, 2) = -1; nós calculamos ,
      (0-12)-(-1)×(01-2/3)=(004/3){\ displaystyle {\ begin {pmatrix} 0 & -1 & 2 \ end {pmatrix}} - (- 1) \ times {\ begin {pmatrix} 0 & 1 & -2 / 3 \ end {pmatrix}} = { \ begin {pmatrix} 0 & 0 & 4/3 \ end {pmatrix}}}
  • a matriz é então  ;
    NO″=(10-1/301-2/3004/3){\ displaystyle \ mathrm {A} '' = {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 4/3 \ end {pmatrix}} }
• terceira iteração, j = 3 (e r = 2):
  • passo 3.1: o pivô da terceira coluna, terceira linha é 4/3. Então k = 3
  • etapa 3.2.1: r = k,
  • passo 3.2.2: não há linha para trocar,
  • passo 3.2.3: dividimos a linha 3 por A '' (3, 3) = 4/3, torna-se (001){\ displaystyle {\ begin {pmatrix} 0 & 0 & 1 \ end {pmatrix}}}
  • passo 3.2.4:
    • linha i = 1, temos A '' (1, 3) = -1/3. A última etapa cancela esse coeficiente.
    • linha i = 2, temos A '' (2, 3) = -2/3. A última etapa cancela esse coeficiente.
  • a matriz é então escalonada reduzida.
    NO‴=(100010001){\ displaystyle \ mathrm {A} '' '= {\ begin {pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \ end {pmatrix}}}

Estabilidade numérica

A primeira seção do algoritmo, ou seja, a troca de linha com o maior valor de pivô, visa melhorar a estabilidade numérica do algoritmo. Esta etapa tenta minimizar os erros de arredondamento cumulativos que causam instabilidade numérica. Essa estratégia geralmente permite remediar essa instabilidade, mesmo que possamos dar contra-exemplos.

Complexidade algorítmica

A complexidade algorítmica assintótica de eliminação gaussiana é O ( n 3 ) ( notações de Landau ): n × n é o tamanho da matriz e o número de instruções a serem executadas é proporcional a n 3 . Este algoritmo pode ser usado em um computador para sistemas com milhares de incógnitas e equações . No entanto, o algoritmo de Strassen , que está em O ( n 2.807 ), tem melhor complexidade algorítmica assintótica.

A complexidade algorítmica do pivô gaussiano permanece O ( n 3 ) quando a matriz é esparsa. Na verdade, vamos dar um n × n matriz dos quais apenas k n entradas são não-zero, mas cujas entradas são regularmente distribuídos ao longo das linhas e colunas, então durante o algoritmo pivot de Gauss o número médio de valores diferentes de zero em um a linha irá de k para 2k e então de 3k para n . Portanto, descobrimos que o número de instruções é da ordem de nn (n-1) / 2 .

Calculando o inverso de uma matriz quadrada

A eliminação de Gauss-Jordan pode ser usada para inverter uma matriz quadrada se ela for invertível . Para fazer isso, criamos uma matriz com n linhas e 2 n colunas fazendo fronteira com a matriz A pela matriz identidade I n , que gera uma matriz aumentada  (in) denotada [A | I] . Se a matriz de entrada for invertível, o algoritmo de Gauss-Jordan é aplicado à matriz aumentada. A matriz final é da forma [I | A −1 ] e contém o inverso da matriz inicial em sua seção direita.

Exemplo

Vamos supor a seguinte matriz:

NO=(2-10-12-10-12){\ displaystyle \ mathrm {A} = \ left ({\ begin {array} {rrr} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \ end {array}} \ direito)}

Para encontrar o inverso desta matriz, devemos gerar a matriz aumentada [A | I] como segue:

[NO|eu]=(2-10100-12-10100-12001){\ displaystyle [\ mathrm {A} | \ mathrm {I}] = \ left ({\ begin {array} {rrr | rrr} 2 & -1 & 0 & 1 & 0 & 0 \\ - 1 & 2 & -1 & 0 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 & 1 \ end {array}} \ right)}

Aplicando o algoritmo de Gauss-Jordan, obtemos a matriz aumentada em sua seguinte forma em escala reduzida:

[eu|B]=(10034121401012112001141234){\ displaystyle [\ mathrm {I} | \ mathrm {B}] = \ left ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & {\ frac {3} {4}} & {\ frac {1} {2}} & {\ frac {1} {4}} \\ [3pt] 0 & 1 & 0 & {\ frac {1} {2}} & 1 & {\ frac {1} { 2}} \\ [3pt] 0 & 0 & 1 & {\ frac {1} {4}} & {\ frac {1} {2}} & {\ frac {3} {4}} \ end {array }} \ direito)} Demonstração

Como antes, o primeiro pivô está na primeira linha. Na etapa 2.2.3, a primeira linha torna-se

(1-1/201/200){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \ end {array}} \ right)}

A etapa 2.2.4 torna-se:

• linha i = 2, temos A (2, 1) = -1; nós calculamos  ;
  (-12-1010)-(-1)×(1-1/201/200)=(03/2-11/210){\ displaystyle ({\ begin {array} {rrr | rrr} -1 & 2 & -1 & 0 & 1 & 0 \ end {array}}) - (- 1) \ times ({\ begin {array} { rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \ end {array}}) = ({\ begin {array} {rrr | rrr} 0 & 3/2 & -1 & 1 / 2 e 1 e 0 \ end {array}})}
• linha i = 3, temos A (3, 1) = 0, a linha não é modificada.

Então nós temos

(1-1/201/20003/2-11/2100-12001){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 3/2 & -1 & 1/2 & 1 & 0 \\ 0 & -1 & 2 & 0 & 0 & 1 \ end {array}} \ right)}

Para a segunda iteração, permutamos as linhas 2 e 3 e dividimos a nova linha 2 por 2, ou seja, na etapa 2.2.3:

(1-1/201/2000-1/21001/203/2-11/210){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \\ 0 & -1 / 2 & 1 & 0 & 0 & 1 / 2 \\ 0 & 3/2 & -1 & 1/2 & 1 & 0 \ end {array}} \ right)}

Na etapa 2.2.4:

• linha i = 1, temos A (1, 3) = 0, a linha não é modificada;
• linha i = 3, temos A (3, 3) = -1; nós calculamos  ;
  (03/2-11/210)-(-1)×(0-1/21001/2)=(0101/211/2){\ displaystyle ({\ begin {array} {rrr | rrr} 0 & 3/2 & -1 & 1/2 & 1 & 0 \ end {array}}) - (- 1) \ times ({\ begin { array} {rrr | rrr} 0 & - 1/2 & 1 & 0 & 0 & 1/2 \ end {array}}) = ({\ begin {array} {rrr | rrr} 0 & 1 & 0 & 1 / 2 & 1 & 1/2 \ end {array}})}

Então nós temos

(1-1/201/2000-1/21001/20101/211/2){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \\ 0 & -1 / 2 & 1 & 0 & 0 & 1 / 2 \\ 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {array}} \ right)}

Para a terceira iteração, dividimos a linha 3 por 1, a matriz permanece inalterada no passo 2.2.3.

Na etapa 2.2.4:

• linha i = 1, temos A (1, 2) = -1/2; nós calculamos  ;
  (1-1/201/200)-(-1/2)×(0101/211/2)=(1003/41/21/4){\ displaystyle ({\ begin {array} {rrr | rrr} 1 & -1 / 2 & 0 & 1/2 & 0 & 0 \ end {array}}) - (- 1/2) \ times ({\ begin {array} {rrr | rrr} 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {array}}) = ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & 3/4 e 1/2 e 1/4 \ end {array}})}
• linha i = 2, temos A (2, 2) = -1/2; nós calculamos  ;
  (0-1/21001/2)-(-1/2)×(0101/211/2)=(0011/41/23/4){\ displaystyle ({\ begin {array} {rrr | rrr} 0 & -1 / 2 & 1 & 0 & 0 & 1/2 \ end {array}}) - (- 1/2) \ times ({\ begin {array} {rrr | rrr} 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {array}}) = ({\ begin {array} {rrr | rrr} 0 & 0 & 1 & 1/4 e 1/2 e 3/4 \ end {array}})}

Então nós temos

(1003/41/21/40011/41/23/40101/211/2){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\ 0 & 0 & 1 & 1/4 & 1/2 & 3/4 \\ 0 & 1 & 0 & 1/2 & 1 & 1/2 \ end {array}} \ right)}.

Uma permutação final das linhas 2 e 3 nos dá

(1003/41/21/40101/211/20011/41/23/4){\ displaystyle \ left ({\ begin {array} {rrr | rrr} 1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\ 0 & 1 & 0 & 1/2 & 1 & 1 / 2 \\ 0 & 0 & 1 & 1/4 & 1/2 & 3/4 \ end {array}} \ right)}.

A seção esquerda da matriz é a matriz identidade, demonstrando que A é invertível. A seção 3x3 à direita, ou seja, a matriz B, é o inverso de A.

Caso Geral

Realizar uma operação elementar O nas n linhas de uma matriz equivale a multiplicá-la à esquerda pela matriz elementar (invertível) G s  : = O ( I n ).

Ao notar O 1 , ..., O s as operações elementares que realizamos em A , e G s = O s ( I n ) as matrizes elementares associadas, acaba-se assim, na seção esquerda, na matriz

eunão=(Os∘...∘O1)(NO)=Gs...G1NO{\ displaystyle \ mathrm {I} _ {n} = (O_ {s} \ circ \ ldots \ circ O_ {1}) (A) = G_ {s} \ ldots G_ {1} A}

e no da direita, na matriz

B=(Os∘...∘O1)(eunão)=Gs...G1.{\ displaystyle B = (O_ {s} \ circ \ ldots \ circ O_ {1}) (\ mathrm {I} _ {n}) = G_ {s} \ ldots G_ {1}.}

Assim, B é não singular e BA = I n , então B -1 = A e A -1 = B .

Resolvendo um sistema de equações lineares

A eliminação de Gauss-Jordan pode resolver um sistema de equações AX = B, onde A é uma matriz n × m de classificação r , B é um vetor fixo e X o vetor desconhecido. Nós criar uma mesa com n linhas e m + 1 colunas, que fazem fronteira com a matriz A pelo vector de B. Nós reduzir a matriz em forma dimensionado reduzida.

Se os pivôs da matriz em escala reduzida associada com (A | B) estão localizados apenas nas primeiras m colunas (que é sempre o caso se r = n  ) e têm o índice de coluna k 1 , ..., k r  , então o último coluna fornece uma solução particular, obtida tomando todos os seus termos zero exceto aqueles localizados na linha do índice k i e para os quais damos o valor do termo localizado na linha i da última coluna, i variando de 1 a r .

Obtemos a solução geral do sistema adicionando a esta solução particular qualquer elemento do kernel de A. Isso é obtido atribuindo valores arbitrários aos coeficientes de X localizados em um índice de linha diferente de k i , e determinando os coeficientes localizados nas linhas do índice k i de forma a satisfazer o sistema (o que é fácil, dada a forma escalonada da matriz).

Se o último pivô da matriz em escala reduzida associada a (A | B) estiver na última coluna, não haverá solução.

Se a matriz A for quadrada invertível (ou seja, o sistema é Cramer), então obtemos na última coluna a solução única X do sistema.

Variante: no algoritmo anterior, se nos limitarmos a obter uma matriz escalonada (não reduzida), obtemos uma matriz triangular superior. Resta "voltar" para encontrar os valores dos coeficientes de X.

Exemplo 1 (detalhado)

Seja o sistema de equações lineares:

{x-y+2z=53x+2y+z=102x-3y-2z=-10{\ displaystyle \ left \ {{\ begin {array} {* {7} {c}} x & - & y & + & 2z & = & 5 \\ 3x & + & 2y & + & z & = & 10 \\ 2x & - & 3y & - & 2z & = & - 10 \ \\ end {array}} \ right.}

Estabelecemos a matriz correspondente:

(1-125321102-3-2-10){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ 3 & 2 & 1 & 10 \\ &&& \\ 2 & -3 & -2 & -10 \ end {array}} \ right)}

Começamos com a coluna 1. O pivô é o máximo em valor absoluto entre 1, 3 e 2, ou seja, 3:

(1-125(3)21102-3-2-10){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ (3) & 2 & 1 & 10 \\ &&& \\ 2 & -3 & - 2 e -10 \ end {array}} \ right)}

Como esse pivô não é zero, dividimos a linha onde ele está localizado (ou seja, linha 2) pelo pivô:

(1-125(1)23131032-3-2-10){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & -1 & 2 & 5 \\ &&& \\ (1) & {\ frac {2} {3}} & {\ frac {1 } {3}} & {\ frac {10} {3}} \\ &&& \\ 2 & -3 & -2 & -10 \ end {array}} \ right)}

Trocamos as linhas 1 e 2:

((1)23131031-1252-3-2-10){\ displaystyle \ left ({\ begin {array} {ccc | c} (1) & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} { 3}} \\ &&& \\ 1 & -1 & 2 & 5 \\ &&& \\ 2 & -3 & -2 & -10 \ end {array}} \ right)}

Agora analisamos as linhas diferentes daquela do pivô. Linha 2, temos A (2, 1) = 1. Calculamos
(1-125)-(1)×(12313103)=(0-535353){\ displaystyle {\ begin {pmatrix} 1 & -1 & 2 & 5 \ end {pmatrix}} - (1) \ times {\ begin {pmatrix} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & - {\ frac {5} {3}} & {\ frac { 5} {3}} & {\ frac {5} {3}} \ end {pmatrix}}}

Linha 3, temos A (3, 1) = 2. Calculamos
(2-3-2-10)-(2)×(12313103)=(0-133-83-503){\ displaystyle {\ begin {pmatrix} 2 & -3 & -2 & -10 \ end {pmatrix}} - (2) \ times {\ begin {pmatrix} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & - {\ frac {13} {3}} & - { \ frac {8} {3}} & - {\ frac {50} {3}} \ end {pmatrix}}}

Substituímos as linhas 2 e 3 assim calculadas:

((1)23131030-5353530-133-83-503){\ displaystyle \ left ({\ begin {array} {ccc | c} (1) & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} { 3}} \\ &&& \\ 0 & - {\ frac {5} {3}} & {\ frac {5} {3}} & {\ frac {5} {3}} \\ &&& \\ 0 & - {\ frac {13} {3}} & - {\ frac {8} {3}} & - {\ frac {50} {3}} \ end {array}} \ right)}

Vamos para a coluna 2. O pivô é o máximo em valor absoluto entre e , ou seja  : -53{\ displaystyle - {\ frac {5} {3}}}-133{\ displaystyle - {\ frac {13} {3}}}-133{\ displaystyle - {\ frac {13} {3}}}

(123131030-5353530(-133)-83-503){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3} } \\ &&& \\ 0 & - {\ frac {5} {3}} & {\ frac {5} {3}} & {\ frac {5} {3}} \\ &&& \\ 0 & \ left (- {\ frac {13} {3}} \ right) & - {\ frac {8} {3}} & - {\ frac {50} {3}} \ end {array}} \ right)}

Como esse pivô não é zero, dividimos a linha onde ele está localizado (ou seja, linha 3) pelo pivô:

(123131030-5353530(1)8135013){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3} } \\ &&& \\ 0 & - {\ frac {5} {3}} & {\ frac {5} {3}} & {\ frac {5} {3}} \\ &&& \\ 0 & (1 ) & {\ frac {8} {13}} & {\ frac {50} {13}} \ end {array}} \ right)}

Trocamos as linhas 2 e 3:

(123131030(1)81350130-535353){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3} } \\ &&& \\ 0 & (1) & {\ frac {8} {13}} & {\ frac {50} {13}} \\ &&& \\ 0 & - {\ frac {5} {3} } & {\ frac {5} {3}} & {\ frac {5} {3}} \ end {array}} \ right)}

Agora analisamos as linhas diferentes daquela do pivô. Linha 1, temos A (1, 2) = . Nós calculamos23{\ displaystyle {\ frac {2} {3}}}
(12313103)-(23)×(018135013)=(10-1131013){\ displaystyle {\ begin {pmatrix} 1 & {\ frac {2} {3}} & {\ frac {1} {3}} & {\ frac {10} {3}} \ end {pmatrix}} - \ left (\ textstyle {\ frac {2} {3}} \ right) \ times {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} & {\ frac {50} {13} } \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \ end {pmatrix}}}

Linha 3, temos A (3, 2) = . Nós calculamos-53{\ displaystyle - {\ frac {5} {3}}}
(0-535353)-(-53)×(018135013)=(00351310513){\ displaystyle {\ begin {pmatrix} 0 & - {\ frac {5} {3}} & {\ frac {5} {3}} & {\ frac {5} {3}} \ end {pmatrix}} - \ left (- \ textstyle {\ frac {5} {3}} \ right) \ times {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} & {\ frac {50} { 13}} \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & {\ frac {35} {13}} & {\ frac {105} {13}} \ end {pmatrix}}}

Substituímos as linhas 1 e 3 assim calculadas:

(10-11310130(1)813501300351310513){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \\ &&& \\ 0 & (1) & {\ frac {8} {13}} & {\ frac {50} {13}} \\ &&& \\ 0 & 0 & {\ frac {35} {13}} & {\ frac {105 } {13}} \ end {array}} \ right)}

Vamos para a coluna 3. O pivô é  : 3513{\ displaystyle {\ frac {35} {13}}}

(10-113101301813501300(3513)10513){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \\ &&& \\ 0 & 1 & {\ frac {8} {13}} & {\ frac {50} {13}} \\ &&& \\ 0 & 0 & \ left ({\ frac {35} {13}} \ right) & { \ frac {105} {13}} \ end {array}} \ right)}

Como esse pivô não é zero, dividimos a linha onde ele está localizado (ou seja, linha 3) pelo pivô:

(10-113101301813501300(1)3){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \\ &&& \\ 0 & 1 & {\ frac {8} {13}} & {\ frac {50} {13}} \\ &&& \\ 0 & 0 & (1) & 3 \ end {array}} \ right)}

Como este pivô já está na linha 3, não há necessidade de trocar de linha.

Agora analisamos as linhas diferentes daquela do pivô. Linha 1, temos A (1, 3) = . Nós calculamos-113{\ displaystyle - {\ frac {1} {13}}}
(10-1131013)-(-113)×(0013)=(1001){\ displaystyle {\ begin {pmatrix} 1 & 0 & - {\ frac {1} {13}} & {\ frac {10} {13}} \ end {pmatrix}} - \ left (- \ textstyle {\ frac {1} {13}} \ right) \ times {\ begin {pmatrix} 0 & 0 & 1 & 3 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 0 & 1 \ end {pmatrix }}}

Linha 2, temos A (2, 3) = . Nós calculamos813{\ displaystyle {\ frac {8} {13}}}
(018135013)-(813)×(0013)=(0102){\ displaystyle {\ begin {pmatrix} 0 & 1 & {\ frac {8} {13}} & {\ frac {50} {13}} \ end {pmatrix}} - \ left (\ textstyle {\ frac { 8} {13}} \ right) \ times {\ begin {pmatrix} 0 & 0 & 1 & 3 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 1 & 0 & 2 \ end {pmatrix}} }

Substituímos as linhas 1 e 2 assim calculadas:

(100101020013){\ displaystyle \ left ({\ begin {array} {ccc | c} 1 & 0 & 0 & 1 \\ &&& \\ 0 & 1 & 0 & 2 \\ &&& \\ 0 & 0 & 1 & 3 \ end {array}} \ right)}

Todas as colunas à esquerda da barra vertical foram processadas. Estamos na presença de uma matriz em escala reduzida, com a matriz identidade de um lado e o valor das variáveis ​​do outro. A solução do sistema de equações é, portanto:

{x=1y=2z=3{\ displaystyle \ left \ {{\ begin {array} {ccc} x & = & 1 \\ y & = & 2 \\ z & = & 3 \\\ end {array}} \ right.}

Exemplo 2

Seja o sistema de equações lineares:

{x1+2x2+2x3-3x4+2x5=32x1+4x2+x3-5x5=-64x1+8x2+5x3-6x4-x5=0-x1-2x2-x3+x4+x5=1{\ displaystyle \ left \ {{\ begin {array} {* {11} {c}} x_ {1} & + & 2x_ {2} & + & 2x_ {3} & - & 3x_ {4} & + & 2x_ {5} & = & 3 \\ 2x_ {1} & + & 4x_ {2} & + & x_ {3} &&& - & 5x_ {5} & = & - 6 \\ 4x_ {1} & + & 8x_ {2} & + & 5x_ {3} & - & 6x_ {4} & - & x_ {5} & = & 0 \\ - x_ {1} & - & 2x_ {2} & - & x_ {3} & + & x_ {4} & + & x_ {5} & = & 1 \ end {array}} \ right.}

A matriz em escala reduzida associada a é . (122-3232410-5-6485-6-10-1-2-1111){\ displaystyle \ left ({\ begin {array} {ccccc | c} 1 & 2 & 2 & -3 & 2 & 3 \\ 2 & 4 & 1 & 0 & -5 & -6 \\ 4 & 8 & 5 & ​​-6 & -1 & 0 \\ - 1 & -2 & -1 & 1 & 1 & 1 \ end {array}} \ right)}(1201-4-5001-234000000000000){\ displaystyle \ left ({\ begin {array} {ccccc | c} 1 & 2 & 0 & 1 & -4 & -5 \\ 0 & 0 & 1 & -2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \ end {array}} \ right)}

Os pivôs estão localizados nas colunas de índice 1 e 3. Uma solução particular é, portanto :, que corresponde ao vetor: x1=-5,x3=4,x2=x4=x5=0{\ displaystyle x_ {1} = - 5, x_ {3} = 4, x_ {2} = x_ {4} = x_ {5} = 0}(-50400){\ displaystyle \ left ({\ begin {array} {ccc} -5 \\ 0 \\ 4 \\ 0 \\ 0 \ end {array}} \ right)}

Exemplo 3

Seja o sistema de equações lineares:

{x1+2x2+2x3-3x4+2x5=32x1+4x2+x3-5x5=-64x1+8x2+5x3-6x4-x5=0-x1-2x2-x3+x4+x5=2{\ displaystyle \ left \ {{\ begin {array} {* {11} {c}} x_ {1} & + & 2x_ {2} & + & 2x_ {3} & - & 3x_ {4} & + & 2x_ {5} & = & 3 \\ 2x_ {1} & + & 4x_ {2} & + & x_ {3} &&& - & 5x_ {5} & = & - 6 \\ 4x_ {1} & + & 8x_ {2} & + & 5x_ {3} & - & 6x_ {4} & - & x_ {5} & = & 0 \\ - x_ {1} & - & 2x_ {2} & - & x_ {3} & + & x_ {4} & + & x_ {5} & = & 2 \ end {array}} \ right.}

A matriz em escala reduzida associada a é . (122-3232410-5-6485-6-10-1-2-1112){\ displaystyle \ left ({\ begin {array} {ccccc | c} 1 & 2 & 2 & -3 & 2 & 3 \\ 2 & 4 & 1 & 0 & -5 & -6 \\ 4 & 8 & 5 & ​​-6 & -1 & 0 \\ - 1 & -2 & -1 & 1 & 1 & 2 \ end {array}} \ right)}(1201-40001-230000001000000){\ displaystyle \ left ({\ begin {array} {ccccc | c} 1 & 2 & 0 & 1 & -4 & 0 \\ 0 & 0 & 1 & -2 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \ end {array}} \ right)}

Não há solução.

determinando

Este algoritmo também permite calcular o determinante de uma matriz  :

det(NO)=(-1)p.∏j=⁡1não(NO[k,j]){\ displaystyle \ det (A) = (- 1) ^ {p}. \ prod _ {j \ mathop {=} 1} ^ {n} (A [k, j])}

com p o número de permutações de linha e o pivô anotado na etapa j do algoritmo. NO[k,j]{\ displaystyle A [k, j]}

Se um dos pivôs for zero, o determinante da matriz será zero e não poderá ser invertido.

Exemplo

Começamos da matriz

NO=(2-100-12-12-1){\ displaystyle \ mathrm {A} = {\ begin {pmatrix} 2 & -1 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

É uma matriz real, então o módulo de um coeficiente é seu valor absoluto.

Procuramos o pivô na coluna 1:

((2)-100-12-12-1){\ displaystyle {\ begin {pmatrix} (2) & - 1 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

Dividimos a linha 1 por 2 para obtermos um 1 na diagonal:

(1-1/200-12-12-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ - 1 & 2 & -1 \ end {pmatrix}}}

Modificamos as linhas 2 e 3 por combinações lineares com a linha 1 para obter zeros na primeira coluna (exceto diagonal):

(1-1/200-1203/2-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ 0 & 3/2 & -1 \ end {pmatrix}}}

Procuramos o pivô na coluna 2:

(1-1/200-120(3/2)-1){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & -1 & 2 \\ 0 & (3/2) & - 1 \ end {pmatrix}}}

Trocamos as linhas 2 e 3:

(1-1/200(3/2)-10-12){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & (3/2) & - 1 \\ 0 & -1 & 2 \ end {pmatrix}}}

Dividimos a linha 2 por (3/2) para obtermos 1 na diagonal:

(1-1/2001-2/30-12){\ displaystyle {\ begin {pmatrix} 1 & -1 / 2 & 0 \\ 0 & 1 & -2 / 3 \\ 0 & -1 & 2 \ end {pmatrix}}}

Modificamos as linhas 1 e 3 por combinações lineares com a linha 2 para obter zeros na segunda coluna (exceto diagonal):

(10-1/301-2/3004/3){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 4/3 \ end {pmatrix}}}

Procuramos o pivô na coluna 3:

(10-1/301-2/300(4/3)){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & (4/3) \ end {pmatrix}}}

Dividimos a linha 3 por (4/3) para obtermos 1 na diagonal:

(10-1/301-2/3001){\ displaystyle {\ begin {pmatrix} 1 & 0 & -1 / 3 \\ 0 & 1 & -2 / 3 \\ 0 & 0 & 1 \ end {pmatrix}}}

Modificamos as linhas 1 e 2 por combinações lineares com a linha 3 para obter zeros na terceira coluna (exceto diagonal), a matriz é então:

(100010001){\ displaystyle {\ begin {pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \ end {pmatrix}}}

que é reduzido.

O determinante da matriz, portanto, vale a pena . (-1)1×2×32×43=-4{\ displaystyle (-1) ^ {1} \ times 2 \ times {\ frac {3} {2}} \ times {\ frac {4} {3}} = - 4}

Notas

1. Gauss 1810 .
2. Jordan 1888 .
3. Althoen e McLaughlin 1987 .
4. Adaptado de Beezer 2014 , p.  30
5. Ver, por exemplo, os comentários de Patrick Lascaux e Raymond Théodor, Matric numerical analysis aplicada à arte do engenheiro , t.  1: Métodos diretos [ detalhe das edições ], p.  228 .

Referências

• Steven C. Althoen e Renate McLaughlin , “  Gauss-Jordan Reduction: A Brief History  ”, Amer. Matemática. Mês. , vol.  94,1987, p.  130-142.

• Robert A. Beezer , Um Primeiro Curso de Álgebra Linear , University of Puget Sound,2014( leia online ).

• Carl Friedrich Gauss , Disquisitio de elementis ellipticis Palladis ,1810.

• Wilhelm Jordan , Handbuch der Vermessungskunde , vol.  1, Metzler,1888.

• Joseph-Louis Lagrange , Misturas de Torino ,1759.

Artigos relacionados

• Algoritmo de escalonamento em um anel euclidiano
• Decomposição LU
• Decomposição QR
• Eliminação de Fourier-Motzkin , generalização do método para sistemas de desigualdades lineares
• Fatoração de Cholesky

Link externo

Método de pivô gaussiano em math-linux.com