Álgebra Linear Computacional

Aula 22: Análise de Erros na Solução de Sistemas Lineares

Heitor S. Ramos
ramosh@dcc.ufmg.br

Créditos

Important

Esses slides são fortemente baseados no livro do prof. Frederico Ferreira Campos, Filho.

Malcondicionamento

Sistema linear \(Ax = b\)

\(A = \begin{bmatrix} 1 & 0,99 \\ 0,99 & 0,98 \end{bmatrix}\) e \(b= \begin{bmatrix} 1,99 \\ 1,97 \end{bmatrix}\)

Solução exata: \(x = \begin{bmatrix}1&1\end{bmatrix}^\top\)
Vetor \(\tilde{b}=\begin{bmatrix}1,99 & 1,98\end{bmatrix}^\top \approx b\)
Solução exata de \(Ay = \tilde{b} = \begin{bmatrix}100 & -99\end{bmatrix}^\top\)
Seja a matriz \[ \tilde{A} = \begin{bmatrix} 1 & 0,99 \\ 0,99 & 0,99 \end{bmatrix} \approx A \]
Solução exata de \(\tilde{A}z=b = \begin{bmatrix}2 & -1/99\end{bmatrix}^\top\)
Matriz \(A\) é quase singular (\(\text{det}(A) = -10^{-4}\))
Sistema linear malcondicionado

Interpretação geométrica do malcondicionamento

Sistema linear \(Ax = b\)

\(A = \begin{bmatrix} 1 & 0,99 \\ 0,99 & 0,98 \end{bmatrix}\) e \(b= \begin{bmatrix} 1,99 \\ 1,97 \end{bmatrix}\)

Solução exata: \(x = \begin{bmatrix}1&1\end{bmatrix}^\top\)
Vetor \(\tilde{b}=\begin{bmatrix}1,99 & 1,98\end{bmatrix}^\top \approx b\)
Solução exata de \(Ay = \tilde{b} = \begin{bmatrix}100 & -99\end{bmatrix}^\top\)
Duas retas definidas por um sistema linear
Duas retas são quase coincidentes
Deslocamento no ponto de interseção

Problemas do malcondicionamento

Solução exata de \(Ax = b\): \(x=\begin{bmatrix}1&1\end{bmatrix}\)
Resíduo para \(\tilde{x} = \begin{bmatrix}0,9 & 1,1\end{bmatrix}^\top\) \[ \tilde{r} = b-A\tilde{x} = \begin{bmatrix}1,99\\ 1,97\end{bmatrix} - \begin{bmatrix}1 & 0,99 \\ 0,99 & 0,98\end{bmatrix}\begin{bmatrix}0,9 \\ 1,1\end{bmatrix} \] \[ \tilde{r} = \begin{bmatrix}10^{-3}\\ 10^{-3}\end{bmatrix} \]
Vetor \(\tilde{x} \neq x\), mas \(\tilde{r} \approx 0\)
Resíduo não é bom indicador de exatidão da solução quando o sistema é malcondicionado
Instabilidade da solução
Se \(A\) e/ou \(b\) forem medidas experimentais

Singularidade da matriz

Medir singularidade de \(A\) pelo determinante não constitui boa prática
\(\text{det}(A) \approx 0\) não indica necessariamente a ocorrência de malcondicionamento
Por exemplo \[ A = \begin{bmatrix} 0,001 & 0,001 \\ -0,001 & 0,001\end{bmatrix} \]
\(\text{det}(A) = 2\cdot 10^{-6}\) e é muito bem condicionada
Seu determinante é pequeno porque seus elementos são pequenos

Número de condição

\[ \text{condição}(A) = \kappa(A) = \Vert A\Vert \Vert A^{-1}\Vert \]

Sendo \(\Vert \cdot \Vert\) uma norma matricial qualquer
O valor de \(\kappa(A)\) depende da norma utilizada
Por exemplo \[ \kappa_2(A) = \begin{cases} \frac{\lambda_{max}}{\lambda_{min}}, \text{ se } A = A^\top \\ \frac{\sigma_{max}}{\sigma_{min}}, \text{ se } A \neq A^\top \end{cases} \]
\(\lambda(A^{-1})= \lambda^{-1}(A)\)
Sistema \(Ax = b\) é malcondicionado se \(\kappa(A) \gg 1\)

Exemplo de número de condição

Calcular \(\kappa_2(A)\) e \(\kappa_2(B)\) para

\[ A = \begin{bmatrix} 1 & 0,99 \\ 0,99 & 0,98 \end{bmatrix} \] e \[ B = \begin{bmatrix} 5 & 3 & 0 \\ -1 & 8 & 6 \\ 4 & 2 & 9 \end{bmatrix} \]

Usando a definição aterior de \(\kappa_2\), temos

\[\lambda(A) = \begin{bmatrix}19801& -5,0504\cdot 10^{-5}\end{bmatrix}\]

\[ \kappa_2(A) = \frac{\vert 1,9801\vert}{\vert -5,0504\cdot 10^{-5}\vert} = 3,9206\cdot 10^4 \] e \[ \lambda(B^\top B) = \begin{bmatrix}1,7423\cdot 10^2 & 3,7222\cdot 10^1 & 2,4548\cdot 10^1\end{bmatrix} \] \[ \kappa_2(B) = \sqrt{\frac{1,7423\cdot 10^2}{2,4548\cdot 10^1}} = 2,6641 \]

Com \(A\): sistema linear malcondicionado
Com \(B\): bem condicionado

Exemplo clássico de malcondicionamento

Matriz de Hilbert de ordem \(n\)

\[ H_n = \frac{1}{i+j-1}, i,j=1,2,\ldots,n \]

Exemplo

\(H2 = \begin{bmatrix}1&1/2 \\ 1/2 & 1/3\end{bmatrix}\) e \(H_3 = \begin{bmatrix}1 & 1/2 & 1/3 \\ 1/2 & 1/3 & 1/4 \\ 1/4 & 1/4 & 1/5\end{bmatrix}\)

Code

import numpy as np

H = np.array([1, 1/2, 1/3, 1/4,
             1/2, 1/3, 1/4, 1/5, 
             1/3, 1/4, 1/5, 1/6, 
             1/4, 1/5, 1/6, 1/7]).reshape((4,4))
np.linalg.inv(H)

print("Norma infinito de H: ", np.linalg.norm(H,np.inf))
print("Norma infinito de H^-1: ", np.linalg.norm(np.linalg.inv(H), np.inf))

Norma infinito de H:  2.083333333333333
Norma infinito de H^-1:  13619.999999998996

Considerando que \(\Vert H_4\Vert_\infty \approx 2,0833\) e \(\Vert H_4^{-1}\Vert_\infty \approx 13620\)
\(H_4\) é malcondicionada \[ \kappa_\infty(H_4) = \Vert H_4\Vert_\infty \Vert H_4^{-1}\Vert_\infty = 2,0833\cdot 13620 = 28375 \gg 1 \]

Normas-\(\infty\) e número de condição das matrizes de Hilbert

n	\(\Vert H_n\Vert_\infty\)	\(\Vert H_n^{-1}\Vert_\infty\)	\(\kappa_\infty(H_n)\)
1	\(1,00000\)	\(1,00000\cdot10^{0}\)	\(1,00000\cdot10^{0}\)
2	\(1,50000\)	\(1,80000\cdot10^{1}\)	\(2,70000\cdot10^{1}\)
3	\(1,83333\)	\(4,08000\cdot10^{2}\)	\(7,48000\cdot10^{2}\)
4	\(2,08333\)	\(1,36200\cdot10^{4}\)	\(2,83750\cdot10^{4}\)
5	\(2,28333\)	\(4,13280\cdot10^{5}\)	\(9,43656\cdot10^{5}\)
6	\(2,45000\)	\(1,18654\cdot10^{7}\)	\(2,90703\cdot10^{7}\)
7	\(2,59286\)	\(3,79965\cdot10^{8}\)	\(9,85195\cdot10^{8}\)
8	\(2,71786\)	\(1,24631\cdot10^{10}\)	\(3,38728\cdot10^{10}\)
9	\(2,82897\)	\(3,88712\cdot10^{11}\)	\(1,09965\cdot10^{11}\)
10	\(2,92897\)	\(1,20716\cdot10^{13}\)	\(3,53574\cdot10^{13}\)

Sensibilidade da solução

Sistema \(Ax=b\) e \(\delta b\) sendo uma pequena perturbação em \(b\)
Modificação \(\delta b\) na solução \(x=A^{-1}b\) satisfaz

\[\delta x = A^{-1} \delta b\]

Propriedade das normas consistentes:

\[ \Vert A\Vert\Vert x\Vert \ge \Vert b\Vert \] e \[ \Vert \delta x \Vert \le \Vert A^{-1}\Vert \Vert \delta b\Vert \]

Combinando

\[ \frac{\Vert \delta x\Vert}{\Vert x\Vert} \le \Vert A\Vert \Vert A^{-1}\Vert \frac{\Vert \delta b\Vert}{\Vert b\Vert} \] \[ \frac{\Vert \delta x\Vert}{\Vert x\Vert} \le \kappa(A)\frac{\Vert \delta b\Vert}{\Vert b\Vert} \]

Limite superior ao erro relativo na solução \(x\)
Número de condição \(\kappa(A)\)

Exemplo

Verificar a sensibilidade para o sistema \(Ax=b\) com

\(A = \begin{bmatrix}1&0,99\\ 0,99 & 0,98\end{bmatrix}\), \(b = \begin{bmatrix}1,99 \\ 1,97\end{bmatrix}\) e \(\delta b= \begin{bmatrix}0\\ 0,01\end{bmatrix}\)

Sejam \(x = \begin{bmatrix}1 & 1\end{bmatrix}^\top\), \(\kappa_2(A) = 3,9206\cdot 10^4\) , \(\Vert b\Vert_2 = 2,8002\) e \(\Vert \delta b\Vert = 10^{-2}\)
Limite superior ao erro relativo em termos da norma-2 \[ \frac{\Vert \delta x\Vert_2}{\Vert x\Vert_2} \le \kappa_2(A)\frac{\Vert \delta b\Vert_2}{\Vert b\Vert_2} = 3,9206\cdot 10^{4}\frac{10^{-2}}{2,8002} \] \[ \frac{\Vert \delta x\Vert_2}{\Vert x\Vert_2} \le 1,4001\cdot 10^{2} \]
Com \(\delta b\), a solução \(x\) variou de \(\begin{bmatrix}1&1\end{bmatrix}^\top\) para \(\begin{bmatrix}100 & -99\end{bmatrix}^\top\)
Temos que \(\delta x = \begin{bmatrix}100-1 & -99-1\end{bmatrix}^\top\), ou seja, \(\Vert \delta x\Vert_2 = 1,4072\cdot 10^2\)
Sendo \(\Vert x\Vert_2 =1,4142\), na realidade, o erro relativo cometido foi de \[ \frac{\Vert \delta x\Vert_2}{\Vert x\Vert_2} = \frac{1,4072\cdot 10^2}{1,4142} = 9,9505\cdot 1 \]

Perturbação na matriz dos coeficientes

Seja \[ (A+\delta A)(x+\delta x)= b \]

\[ Ax + A\delta x + \delta Ax + \delta A \delta x = b \]

\[ A\delta x = -\delta A(x+\delta x) \]

Tomando as normas consistentes

\[ \Vert \delta x\Vert \le \Vert A^{-1}\Vert \Vert \delta A\Vert \Vert x + \delta x\Vert \] ou

\[ \frac{\delta x}{x + \delta x}\le \kappa(A)\frac{\Vert \delta A\Vert}{\Vert A\Vert} \]

Maior malcondicionamento de \(Ax =b\): maior a influência de \(\delta A\) em \(A\) na solução \(x\)
Coeficientes de \(A\) conhecidos com precisão de quatro decimais e número de condição \(10^3\): solução \(x\) pode ter precisão de uma decimal

Exemplo

Verificar a perturbação na matriz dos coeficientes para o sistema \(Ax =b\), com

\(A = \begin{bmatrix}1&0,99\\ 0,99 & 0,98\end{bmatrix}\), \(b = \begin{bmatrix}1,99 \\ 1,97\end{bmatrix}\) e \(\delta A= \begin{bmatrix}0 & 0\\0& 0,01\end{bmatrix}\)

Sejam \(\kappa_2(A) = 3,9206\cdot 10^4\), \(\Vert \delta A\Vert_2=10^{-2}\) e \(\Vert A\Vert_2 = 1,9801\)
Erro relativo em termos da norma-2

\[ \frac{\Vert\delta x\Vert_2}{\Vert x + \delta x\Vert} \le \kappa_2(A)\frac{\Vert\delta A\Vert_2}{\Vert A\Vert_2} = 1,9206\cdot 10^4\frac{10^{-2}}{1,9801} \]

\[ \frac{\Vert\delta x\Vert_2}{\Vert x + \delta x\Vert} \le 1,9800\cdot 10^2 \]

Com a perturbação \(\delta A\), x variou de \(x=\begin{bmatrix}1&1\end{bmatrix}^\top\) para \(\tilde{x} = \begin{bmatrix}2&-1/99\end{bmatrix}^\top\)
Variação na solução \(\delta x = \begin{bmatrix}2-1 & -1/99 -1\end{bmatrix}^\top\)
Erro relativo real

\[ \frac{\Vert\delta x\Vert_2}{\Vert x + \delta x\Vert} = \frac{1,4214}{2,0000} = 7,1070\cdot 10^{-1} \]

Resumo de sistemas lineares

Os sistemas lineares podem ser:

Singulares vs Não-singulares
- Sistemas singulares podem admitir infinitas soluções ou nenhuma solução
- Sistemas não-singulares admitem solução única
Bem condicionados vs Malcondicionados
- O condicionamento está relacionado a como erros numéricos são propagados
Sistemas lineares quadrados vs retangulares
- Sistemas retangulares podem ser sobre ou sub determinados. Esses sistemas, quando apresentam infinitas soluções, devem ser resolvidos minimizando a norma-2 (método dos mínimos quadrados)

Métodos estudados no curso

Métodos exatos:
- Eliminação de Gauss
- Decomposição LU
  - Maneira sistemática que mantém semelhanças com o método de eliminação de Gauss
  - Muito útil para calcular determinante de matrizes
- Decomposição Cholesky
  - Quando a matriz dos coeficientes é positiva definida
  - Muito útil para calcular determinante de matrizes
- Pseudoinversa de Moore-Penrose
  - Útil para solucionar problema de mínimos quadrados com matrizes de posto baixo (Ver sistemas retangulares)
- Decomposição QR
  - Útil quando a matriz tem posto cheio
Métodos iterativos estacionários (aproximados):
- Método de Jacobi
- Método de Gauss-Seidel
- Método da Sobre-relaxação sucessiva
  - importante estudar a análise de convergência desses métodos