Kondicionování (digitální analýza)
V numerické analýze , disciplíně matematiky , podmínění měří závislost řešení numerické úlohy na datech úlohy, aby se ověřila platnost řešení vypočítaného s ohledem na tato data. Ve skutečnosti data numerického problému obecně závisí na experimentálních měřeních a jsou tak poznamenána chybami.
Nejčastěji se jedná o číselnou veličinu.
Obecněji lze říci, že kondicionování spojené s problémem je měřítkem obtížnosti numerického výpočtu problému. Problém s nízkou kondicí se říká, že je dobře kondicionován, a problém s nízkou kondicí se říká, že je špatně kondicionovaný .
Podmínka problému
Buď problém . Nechť je také narušená proměnná s , kde ε je přesnost stroje. Podmínkou k problému je pak nejmenší číslo takové, že:
P:Rne→R{\ displaystyle \ mathrm {P}: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}X^i=Xi(1+εi){\ displaystyle {\ hat {x}} _ {i} = x_ {i} (1+ \ varepsilon _ {i})}|εi|<ε{\ displaystyle | \ varepsilon _ {i} | <\ varepsilon}
|P(X^)-P(X)||P(X)|⩽kε+Ó(ε).{\ displaystyle {\ frac {| \ mathrm {P} ({\ hat {x}}) - \ mathrm {P} (x) |} {| \ mathrm {P} (x) |}} \ leqslant k \ varepsilon + o (\ varepsilon).}Problém P je dobře podmíněn, pokud k není příliš velký vzhledem k . Jinak je tento problém P špatně podmíněn.
ε{\ displaystyle \ varepsilon}
Podle N. Highama se zdá, že pojem podmíněnosti představil Alan Turing, který například definoval podmínění čtvercové matice velikosti n z Frobeniovy normy :
VS(NA)=1ne⋅‖NA‖⋅‖NA-1‖{\ displaystyle \ mathrm {C} (\ mathrm {A}) = {\ frac {1} {n}} \ cdot \ | \ mathrm {A} \ | \ cdot \ | \ mathrm {A} ^ {- 1 } \ |}
Podmínění matice
Podmíněnost invertovatelné matice A vzhledem k podřízené normě , která je uvedena, je definována vzorcem:
||⋅||{\ displaystyle || \ cdot ||}
κ(NA)=‖NA-1‖‖NA‖{\ displaystyle \ kappa (\ mathrm {A}) = \ Zelená \ mathrm {A} ^ {- 1} \ Zelená \, \ Zelená \ mathrm {A} \ Zelená}.
Protože se předpokládá, že norma je podřízená, je podmíněnost větší než 1:
κ(NA)⩾1.{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant 1.}Všimněte si, že prázdná matice 0 × 0 je její vlastní inverzní a že její norma je nulová bez ohledu na vybranou normu. Jeho kondicionování je tedy podle této definice 0. Někteří však definují cond () 0 × 0 = 1, protože nulová lineární mapa má dokonalou přesnost (tedy skóre 1) a tato prázdná matice je identita, všechny matice jednotek mají podmínku 1.
Pro lineární systém A x = b , kde daty jsou matice A a vektor druhého prvku b , dává kondicionování vazbu relativní chyby spáchané na řešení x, když jsou data A nebo b narušena. Může se ukázat, že tento terminál je velmi velký, takže chyba, která by z něj mohla vzniknout, činí digitální řešení nepoužitelným.
Balení závisí na použité normě. Pro vesmírnou normu ℓ 2 , uvedenou ∥⋅∥ 2 , máme:
κ(NA)=σmax(NA)σmin(NA){\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {\ sigma _ {\ max} (\ mathrm {A})} {\ sigma _ {\ min} (\ mathrm {A})}}}kde σ max a σ min jsou singulární hodnoty maximální a minimální z A . Tudíž :
- pokud je normální , pak kde λ max a λ min jsou maximální a minimální vlastní hodnoty z A ;
κ(NA)=|λmax(NA)||λmin(NA)|{\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {| \ lambda _ {\ max} (\ mathrm {A}) |} {| \ lambda _ {\ min} (\ mathrm {A}) |}}}
- pokud A je unitární , pak .
κ(NA)=1{\ displaystyle \ kappa (\ mathrm {A}) = 1}
Pro prostor normy pásmy ∞ , označený ∥⋅∥ ∞ , jestliže A je ne singulární dolní trojúhelníková matice (tj. ∀ i , ii ≠ 0 ), potom:
κ(NA)⩾maxi(|naii|)mini(|naii|).{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant {\ frac {\ max _ {i} (| a_ {ii} |)} {\ min _ {i} (| a_ {ii} |)}} .}
Chyba při zvyšování vzorců
V následujících vzorcích se předpokládá, že se výpočty provádějí s nekonečnou přesností , tj. Narušené systémy jsou řešeny přesně.
Uvažujeme dva případy v závislosti na tom, zda jde o druhý člen b nebo matici A, která není přesně známa.
Případ, kdy se druhý člen liší
Efektivní výpočet inverze systému A x = b , kde je matice A známa s přesností a kde je hodnota druhého prvku b , předpokládá se, že není nula, ovlivněna chybou , způsobí teoretickou relativní chybu na řešení x zvýšeno o
Δb{\ displaystyle \ Delta b}‖ΔX‖/‖X‖{\ displaystyle \ | \ Delta x \ | / \ | x \ |}
‖ΔX‖‖X‖⩽κ(NA)‖Δb‖‖b‖{\ displaystyle {\ frac {\ Zelená \ Delta x \ Zelená} {\ Zelená x \ Zelená}} \ leqslant \ kappa (\ mathrm {A}) {\ frac {\ Zelená \ Delta b \ Zelená} {\ Zelená b \Zelená }}}.
Případ, kdy se matice liší
Pokud matice A podstoupí modifikaci , má člověk nárůst chyby ve srovnání s výpočtem s přesnou maticí A danou
ΔNA{\ displaystyle \ Delta \ mathrm {A}}
‖ΔX‖‖X+ΔX‖⩽κ(NA)‖ΔNA‖‖NA‖{\ 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}}}.
Příklad špatně podmíněné matice
Nechť je matice
NA=(7111102652811386936){\ displaystyle \ mathrm {A} = {\ začátek {pmatrix} 7 & 1 & 11 & 10 \\ 2 & 6 & 5 & 2 \\ 8 & 11 & 3 & 8 \\ 6 & 9 & 3 & 6 \ \\ end {pmatrix}}},
a vektor
b=(29153024){\ displaystyle b = {\ začátek {pmatrix} 29 \\ 15 \\ 30 \\ 24 \\\ konec {pmatrix}}}.
Rozlišení systému A x = b dává
X=(1111){\ displaystyle x = {\ začátek {pmatrix} 1 \\ 1 \\ 1 \\ 1 \\\ konec {pmatrix}}}.
Pokud dosadíme za druhý člen b druhý narušený člen
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 \\\ konec {pmatrix}} = {\ begin {pmatrix} 29 {,} 1 \\ 14 {,} 9 \\ 30 {,} 1 \\ 23 {,} 9 \\\ end {pmatrix}}},
odpovídající řešení x ' bude
X′=NA-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}}.}Relativní chyby b a x jsou 0,004 a 3,4108, v uvedeném pořadí, což představuje přibližně 860násobné zvýšení relativní chyby. Toto číslo je ve stejném pořadí jako kondicionování matice A, které je 1425 (kondicionování se bere ve vztahu k maticové normě vyvolané euklidovskou normou ).
R4{\ displaystyle \ mathbb {R} ^ {4}}
Dodatky
Poznámka
-
F. Kwok - Numerická analýza (Ženevská univerzita)
-
(en) Nicholas J. Higham , Přesnost a stabilita numerických algoritmů , Soc. Ind. Appl. Matematika.,1996, 688 s. ( ISBN 0-89871-355-2 ) , str. 126
-
J. Todd , Programování v numerické matematice , sv. 7, Besançon, Editions du CNRS,1968, 392 s. , 16 × 25 cm ( ISBN 978-2-222-01037-1 ) , „O podmíněných číslech“, s. 141-159
-
(in) Carl de Boor, „ Prázdné cvičení “ [PDF] (zpřístupněno 31. května 2018 )
-
Toto je například volba softwaru Scilab od verze 5.3 do 6.0, viz „ Prázdná matice (Scilab 5.3.0) “ , na help.scilab.org ,26. ledna 2011(přístup 4. června 2018 ) a „ Empty matrix (Scilab 6.0.1) “ , na help.scilab.org ,12. února 2018(zpřístupněno 4. června 2018 ) .
Související články
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">