Seja resolver o sistema linear Ax=b pelo método da Eliminação de Gauss, com estratégia de pivoteamento parcial:
se M=underseti, jmá|ai j| 1 <= i, j <= n, prove que, após o primeiro estágio, |ai j^(1)| <= 2 M.

Passo 1

O enunciado pede para mostrar que, ao resolver o sistema linear Ax=b pelo método de Gauss com pivoteamento parcial, onde
M = max1<= i,j<= nl|aij|r,
depois do primeiro estágio (eliminação na primeira coluna) todos os coeficientes atualizados aij^(1) satisfazem
l|aij^(1)r|<= 2M
O conteúdo de teoria que vamos usar é o pivoteamento parcial e a desigualdade triangular para estimar o tamanho dos novos elementos.

Passo 2

Aplicamos pivoteamento parcial na coluna 1: escolhemos uma linha p tal que
l|ap1r| = max1<= i<= nl|ai1r|
Se pneq1, permutamos as linhas 1 e p. Dessa escolha segue imediatamente que, para todo i,
l|ap1r|>= l|ai1r|

Passo 3

Para cada i=2,dots,n definimos o multiplicador
elli = ai1ap1
Como l|ai1r|<= l|ap1r|, vem
l|ellir| ;=;l|ai1r|l|ap1r|;<= 1

Passo 4

Após usar elli para zerar a entrada (i,1), os novos elementos da submatriz de linhas e colunas 2 a n são
aij^(1) = aij ;-;elli,apj, j=2,dots,n
Pela desigualdade triangular e pelo fato de l|aijr|<= M e l|apjr|<= M, temos
l|aij^(1)r| ;<=; l|aijr| ;+;l|ellir|,l|apjr| ;<=; M + 1cdot M ;=;2M

Resposta

Após o primeiro estágio de eliminação com pivoteamento parcial, vale
boxedl|aij^(1)r|<= 2M

Exercícios relacionados