Quais são os sintomas de mau condicionamento ao usar métodos diretos?

Suponha que temos um sistema linear e não sabemos nada sobre seu condicionamento e não temos informações preliminares sobre a solução. Aplicamos cegamente a eliminação gaussiana e obtemos alguma solução . É possível determinar se esta solução é confiável (isto é, que o sistema está bem condicionado) sem uma análise preliminar completa da matriz ? A magnitude dos pivôs fornece informações confiáveis? $x$

E, geralmente, quais são as principais diretrizes para a detecção de maus condicionamentos "on the fly"?

linear-solver condition-number conditioning faleichik
fonte

Respostas:

Quando uma matriz está mal condicionada ? Depende da precisão da solução que você procura, tanto quanto "a beleza está nos olhos de quem vê" ...

Pode ser que sua pergunta seja melhor reformulada, pois existem estimadores de número de condição baratos e robustos com base na fatoração da ? $LU$

Supondo que você esteja interessado no problema real geral (denso, não simétrico) na aritmética de dupla precisão, sugiro que você use o solucionador especialista LAPACK DGESVX, que fornece uma estimativa de condição na forma de seu recíproco, . Como bônus, você também tem outras vantagens, como equilíbrio / balanceamento de equações, refinamento iterativo, limites de erro para frente e para trás. A propósito, o mau condicionamento patológico ( ) é sinalizado como um erro por . $\text{RCOND}\approx 1/\kappa(A)$ $\kappa(A) > 1/\epsilon$ INFO>0

Entrando em mais detalhes, o LAPACK estima o número da condição na norma 1 (ou -norm se você estiver resolvendo ) via DGECON . O algoritmo subjacente é descrito no gramado 36: "Soluções triangulares robustas para uso na estimativa de condições" . $\infty$ $A^T x = b$

Tenho que confessar que não sou especialista na área, mas minha filosofia é: "se é bom o suficiente para o LAPACK, é para mim".

Stefano M
fonte

A solução de um sistema de equações mal condicionado com uma matriz da norma 1, no lado direito aleatório da norma 1, terá com alta probabilidade uma norma da ordem do número da condição. Assim, o cálculo de algumas dessas soluções dirá o que está acontecendo.

Arnold Neumaier
fonte

Isso é realmente o que o DGECON está fazendo, com a delicadeza adicional de refinar iterativamente a direção da pesquisa para maximizar o resultado e usar um solucionador triangular personalizado (não os BLAS) para não ter as coisas distorcidas por erros de aproximação. O custo computacional do DGECON é, portanto, comparável ao seu teste simples. +1 por lembrar-nos do significado simples de normas matriciais e número de condição. Deve ser interessante descobrir se o DGECON é realmente mais robusto em uma simples verificação aleatória.

Stefano M

que o número da condição de resolver

coincide com o número da condição de computação

basta apenas multiplicar a matriz em escala com esses vetores aleatórios em vez da solução real

A x = b

$Ax=b$

A x

$Ax$

A x = b

$Ax=b$

faleichik

A

$A$

‖ A ‖ = 1

$\| A \| = 1$

κ (A) = ‖ A ‖ \cdot ‖ A^{- 1} ‖ = ‖ A^{- 1} ‖

$\kappa(A) = \| A \| \cdot \| A^{-1} \| = \| A^{-1} \|$

A

$A$

A x

$Ax$

‖ A ‖

$\| A \|$

‖ A^{- 1} ‖

$\| A^{-1} \|$

É quase impossível saber se o seu sistema está mal condicionado a partir de apenas um resultado. A menos que você tenha alguma previsão sobre o comportamento do seu sistema (ou seja, saiba qual deve ser a solução), não há muito o que dizer de uma única solução.

Dito isso, você pode ganhar mais informação se você resolver mais de um sistema com o mesmo . Suponha que você tenha um sistema no formato . Para um A específico que você não tem conhecimento prévio sobre seu condicionamento, é possível executar o seguinte teste: $A$ $Ax=b$

Resolva para um vetor específico do lado direito . $Ax=b$ $b$
Perturbar seu vetor do lado direito por onde é muito pequeno em comparação com . $b_{new}=b+\mathbf{\varepsilon}$ $||\mathbf{\epsilon}||$ $||b||$
Resolva . $Ax_{new}=b_{new}$
Se o seu sistema estiver bem condicionado, sua nova solução deverá estar bastante próxima da antiga (por exemplo, deve ser pequeno). Se você observar uma mudança drástica na sua nova solução (ou seja, é grande), seu sistema provavelmente está mal condicionado. $||x-x_{new}||$ $||x-x_{new}||$

Pode ser necessário resolver vários sistemas lineares com diferentes vetores do lado direito para fornecer uma melhor indicação sobre se o sistema está mal condicionado. Obviamente, esse processo é um pouco caro ( operações para a primeira solução e operações para cada solução sucessiva, supondo que o seu solucionador direto salve seus fatores). Se sua matriz A é bastante pequena, isso não é um problema. Se for grande, talvez você não queira fazer isso. Em vez disso, é melhor calcular o número da condiçãoem uma norma conveniente. $\Theta(n^3)$ $\Theta(n^2)$ $||A||\cdot||A^{-1}||$

Paulo
fonte

Seu

alegação é extremamente longe da verdade. Mesmo que seja denso, pode ser fatorado uma vez com trabalho e cada solução requer apenas trabalho.

Θ (k n^{3})

$\Theta(kn^3)$

A

$A$

A

$A$

O (n^{3})

$O(n^3)$

O (n^{2})

$O(n^2)$

22612 Jack Poulson

@JackPoulson: Você está absolutamente certo ... acho que me esqueci completamente disso. Não se preocupe :) Vou atualizar minha resposta

Paul

Também se poderia avaliar o resíduo da solução resultante? Desde

escalas como

uma quase singular

pode dar a mesmo residual significativo se a sua solução é muito ruim.

| | A x - b | |

$||Ax - b ||$

| | A | | \cdot | | x | |

$||A||\cdot||x||$

A

$A$

Reid.Atcheson

@ Reid.Atcheson: Na verdade não. A solução aproximada para um sistema mal condicionado ainda pode produzir um pequeno resíduo. Isso realmente não fornece nenhuma indicação de quão longe está da verdadeira solução.

Paul

‖ ε ‖

$\|\varepsilon\|$

‖ b ‖

$\|b\|$