Condicionamento (análise digital)
Na análise numérica , disciplina da matemática , o condicionamento mede a dependência da solução de um problema numérico dos dados do problema, a fim de verificar a validade de uma solução calculada com relação a esses dados. Na verdade, os dados de um problema numérico dependem em geral de medições experimentais e são, portanto, marcados por erros.
Na maioria das vezes, é uma quantidade numérica.
De forma mais geral, pode-se dizer que o condicionamento associado a um problema é uma medida da dificuldade de cálculo numérico do problema. Diz-se que um problema de baixo condicionamento é bem condicionado e um problema de alto condicionamento que é mal condicionado .
Condicionamento de um problema
Qualquer um é um problema . Seja também uma variável perturbada , com , onde ε é a precisão da máquina. Então, a condição k do problema é o menor número tal que:
P:Rnão→R{\ displaystyle \ mathrm {P}: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}x^eu=xeu(1+εeu){\ displaystyle {\ hat {x}} _ {i} = x_ {i} (1+ \ varepsilon _ {i})}|εeu|<ε{\ displaystyle | \ varepsilon _ {i} | <\ varepsilon}
|P(x^)-P(x)||P(x)|⩽kε+o(ε).{\ displaystyle {\ frac {| \ mathrm {P} ({\ hat {x}}) - \ mathrm {P} (x) |} {| \ mathrm {P} (x) |}} \ leqslant k \ varejpsilon + o (\ varepsilon).}O problema P está bem condicionado se k não for muito grande em relação a . Caso contrário, este problema P é mal condicionado.
ε{\ displaystyle \ varepsilon}
De acordo com N. Higham, parece que a noção de condicionamento foi introduzida por Alan Turing que, por exemplo, definiu o condicionamento de uma matriz quadrada de tamanho n a partir da norma de Frobenius por:
VS(NO)=1não⋅‖NO‖⋅‖NO-1‖{\ displaystyle \ mathrm {C} (\ mathrm {A}) = {\ frac {1} {n}} \ cdot \ | \ mathrm {A} \ | \ cdot \ | \ mathrm {A} ^ {- 1 } \ |}
Condicionando uma matriz
O condicionamento de uma matriz invertível A em relação a uma norma subordinada , observada, é definido pela fórmula:
||⋅||{\ displaystyle || \ cdot ||}
κ(NO)=‖NO-1‖‖NO‖{\ displaystyle \ kappa (\ mathrm {A}) = \ Green \ mathrm {A} ^ {- 1} \ Green \, \ Green \ mathrm {A} \ Green}.
Como se assume que a norma é subordinada, o condicionamento é maior que 1:
κ(NO)⩾1{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant 1.}Observe que a matriz 0 × 0 vazia é sua própria inversa e que sua norma é zero, independentemente da norma selecionada. Seu condicionamento é, portanto, 0 de acordo com esta definição. No entanto, alguns definem cond () 0 × 0 = 1 porque o mapa linear nulo tem precisão perfeita (portanto, uma pontuação de 1) e essa matriz vazia é uma identidade, todas as matrizes unitárias tendo um condicionamento de 1.
Para o sistema linear A x = b , onde os dados são a matriz A e o vetor do segundo membro b , o condicionamento dá um limite do erro relativo cometido na solução x quando os dados A ou b são perturbados. Pode acontecer que este terminal seja muito grande, de forma que o erro que poderia resultar dele inutilize a solução digital.
A embalagem depende do padrão utilizado. Para a norma espacial ℓ 2 , observada ∥⋅∥ 2 , temos então:
κ(NO)=σmax(NO)σmin(NO){\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {\ sigma _ {\ max} (\ mathrm {A})} {\ sigma _ {\ min} (\ mathrm {A})}}}onde σ max e σ min são os valores singulares máximo e mínimo de uma . Consequentemente :
- se A é normal , então onde λ max e λ min são os autovalores máximo e mínimo de A ;
κ(NO)=|λmax(NO)||λmin(NO)|{\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {| \ lambda _ {\ max} (\ mathrm {A}) |} {| \ lambda _ {\ min} (\ mathrm {A}) |}}}
- se A for unitário , então .
κ(NO)=1{\ displaystyle \ kappa (\ mathrm {A}) = 1}
Para a norma espacial ℓ ∞ , denotada por ∥⋅∥ ∞ , se A for uma matriz triangular inferior não singular (ou seja, ∀ i , a ii ≠ 0 ), então:
κ(NO)⩾maxeu(|noeueu|)mineu(|noeueu|).{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant {\ frac {\ max _ {i} (| a_ {ii} |)} {\ min _ {i} (| a_ {ii} |)}} .}
Fórmulas de aumento de erro
Nas fórmulas a seguir, os cálculos são assumidos para serem feitos com precisão infinita , ou seja, os sistemas perturbados são resolvidos com exatidão.
Consideramos dois casos, dependendo se é o segundo membro b ou a matriz A que não é precisamente conhecida.
Caso em que o segundo membro varia
O cálculo efetivo da inversão do sistema A x = b , onde a matriz A é conhecida com precisão e onde o valor do segundo membro b , assumido não ser zero, está viciado por um erro , produzirá um erro relativo teórico na solução x aumentado em
Δb{\ displaystyle \ Delta b}‖Δx‖/‖x‖{\ displaystyle \ | \ Delta x \ | / \ | x \ |}
‖Δx‖‖x‖⩽κ(NO)‖Δb‖‖b‖{\ displaystyle {\ frac {\ Green \ Delta x \ Green} {\ Green x \ Green}} \ leqslant \ kappa (\ mathrm {A}) {\ frac {\ Green \ Delta b \ Green} {\ Green b \Verde }}}.
Caso onde a matriz varia
Se a matriz A sofre uma modificação de , tem-se um aumento do erro em comparação com o cálculo com a matriz exata A dada por
ΔNO{\ displaystyle \ Delta \ mathrm {A}}
‖Δx‖‖x+Δx‖⩽κ(NO)‖ΔNO‖‖NO‖{\ displaystyle {\ frac {\ Vert \ Delta x \ Vert} {\ Vert x + \ Delta x \ Vert}} \ leqslant \ kappa (\ mathrm {A}) {\ frac {\ Vert \ Delta \ mathrm {A } \ Green} {\ Green \ mathrm {A} \ Green}}}.
Um exemplo de uma matriz mal condicionada
Deixe a matriz ser
NO=(7111102652811386936){\ displaystyle \ mathrm {A} = {\ begin {pmatrix} 7 & 1 & 11 & 10 \\ 2 & 6 & 5 & 2 \\ 8 & 11 & 3 & 8 \\ 6 & 9 & 3 & 6 \ \\ end {pmatrix}}},
e o vetor
b=(29153024){\ displaystyle b = {\ begin {pmatrix} 29 \\ 15 \\ 30 \\ 24 \\\ end {pmatrix}}}.
A resolução do sistema A x = b dá
x=(1111){\ displaystyle x = {\ begin {pmatrix} 1 \\ 1 \\ 1 \\ 1 \\\ end {pmatrix}}}.
Se substituir o segundo membro b o segundo membro perturbado
b′=b+(0,1-0,10,1-0,1)=(29,114,930,123,9){\ displaystyle b '= b + {\ begin {pmatrix} 0 {,} 1 \\ - 0 {,} 1 \\ 0 {,} 1 \\ - 0 {,} 1 \\\ end {pmatrix}} = {\ begin {pmatrix} 29 {,} 1 \\ 14 {,} 9 \\ 30 {,} 1 \\ 23 {,} 9 \\\ end {pmatrix}}},
a solução correspondente x ' será
x′=NO-1b′≃(6,2220,1331.633-3.256).{\ displaystyle x '= \ mathrm {A} ^ {- 1} b' \ simeq {\ begin {pmatrix} 6 {,} 222 \\ 0 {,} 133 \\ 1 {,} 633 \\ - 3 { ,} 256 \\\ end {pmatrix}}.}Os erros relativos de b e x são 0,004 e 3,4108, respectivamente, o que representa uma multiplicação de cerca de 860 do erro relativo. Este número é da mesma ordem do condicionamento da matriz A, que é 1425 (o condicionamento é considerado em relação à norma da matriz induzida pela norma euclidiana em ).
R4{\ displaystyle \ mathbb {R} ^ {4}}
Apêndices
Observação
-
F. Kwok - Análise Numérica (Universidade de Genebra)
-
(en) Nicholas J. Higham , Accuracy and Stability of Numerical Algorithms , Soc. Ind. Appl. Matemática.,1996, 688 p. ( ISBN 0-89871-355-2 ) , p. 126
-
J. Todd , Programação em Matemática Numérica , vol. 7, Besançon, Editions du CNRS,1968, 392 p. , 16 × 25 cm ( ISBN 978-2-222-01037-1 ) , “Números de condição”, p. 141-159
-
(em) Carl de Boor, " Um exercício vazio " [PDF] (acessado em 31 de maio de 2018 )
-
Esta é, por exemplo, a escolha do software Scilab das versões 5.3 a 6.0, consulte “ Matriz vazia (Scilab 5.3.0) ” , em help.scilab.org ,26 de janeiro de 2011(acessado em 4 de junho de 2018 ) e “ Matriz vazia (Scilab 6.0.1) ” , em help.scilab.org ,12 de fevereiro de 2018(acessado em 4 de junho de 2018 ) .
Artigos relacionados
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">