Kondicionálás (digitális elemzés)
A numerikus elemzés során a matematika diszciplínája , a kondicionálás méri a numerikus feladat megoldásának függését a probléma adataitól, annak érdekében, hogy ellenőrizze az ezekre az adatokra számított megoldás érvényességét. Valójában egy numerikus probléma adatai általában a kísérleti méréstől függenek, ezért hibákat okoznak.
Leggyakrabban ez egy numerikus mennyiség.
Általánosságban elmondható, hogy a problémához kapcsolódó kondicionálás a probléma numerikus kiszámításának nehézségét méri. Az alacsony kondicionálású problémáról azt mondják, hogy jól kondicionált, és a magas kondicionáló problémáról azt mondják, hogy rosszul kondicionált .
Probléma kondicionálása
Vagy probléma . Legyen egy zavart változó is , ahol ε a gép pontossága. Ekkor a probléma k feltétele a legkisebb szám, amely:
P:Rnem→R{\ displaystyle \ mathrm {P}: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R}}
x^én=xén(1+εén){\ displaystyle {\ hat {x}} _ {i} = x_ {i} (1+ \ varepsilon _ {i})}
|εén|<ε{\ displaystyle | \ varepsilon _ {i} | <\ varepsilon}![| \ varepsilon _ {i} | <\ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b4ae34e06fad0fbc2da9c59f3ed3e8f5bea919c)
|P(x^)-P(x)||P(x)|⩽kε+o(ε).{\ displaystyle {\ frac {| \ mathrm {P} ({\ hat {x}}) - \ mathrm {P} (x) |} {| \ mathrm {P} (x) |}} \ leqslant k \ varepsilon + o (\ varepsilon).}![{\ displaystyle {\ frac {| \ mathrm {P} ({\ hat {x}}) - \ mathrm {P} (x) |} {| \ mathrm {P} (x) |}} \ leqslant k \ varepsilon + o (\ varepsilon).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff6c506b1949b05186301bccd9eb139f056f0cb0)
A P feladat jól kondicionált, ha k értéke nem túl nagy . Egyébként ez a P probléma rosszul kondicionált.
ε{\ displaystyle \ varepsilon}![\ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
N. Higham szerint úgy tűnik, hogy a kondicionálás fogalmát Alan Turing vezette be, aki például az n méretű négyzetmátrix kondicionálását definiálta a Frobenius-normától :
VS(NÁL NÉL)=1nem⋅‖NÁL NÉL‖⋅‖NÁL NÉL-1‖{\ displaystyle \ mathrm {C} (\ mathrm {A}) = {\ frac {1} {n}} \ cdot \ | \ mathrm {A} \ | \ cdot \ | \ mathrm {A} ^ {- 1 } \ |}![{\ displaystyle \ mathrm {C} (\ mathrm {A}) = {\ frac {1} {n}} \ cdot \ | \ mathrm {A} \ | \ cdot \ | \ mathrm {A} ^ {- 1 } \ |}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee5519de56016793b9ff1b6fd0f7017189b8aea4)
Mátrix kondicionálása
A kondicionáló egy invertálható mátrix Egy viszonyítva alárendelt norma , jegyezni az alábbi képlet határozza meg:
||⋅||{\ displaystyle || \ cdot ||}![|| \ cdot ||](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2a8825e088ae7b4fff88ab0c551f54fa13b93d1)
κ(NÁL NÉL)=‖NÁL NÉL-1‖‖NÁL NÉL‖{\ displaystyle \ kappa (\ mathrm {A}) = \ Zöld \ mathrm {A} ^ {- 1} \ Zöld \, \ Zöld \ mathrm {A} \ Zöld}![{\ displaystyle \ kappa (\ mathrm {A}) = \ Zöld \ mathrm {A} ^ {- 1} \ Zöld \, \ Zöld \ mathrm {A} \ Zöld}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea19ae0acce39aba08ecd4555720a636a0b1d149)
.
Mivel feltételezzük, hogy a norma alárendelt, a feltétel nagyobb, mint 1:
κ(NÁL NÉL)⩾1.{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant 1.}![{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant 1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e57ad980d423351d5c44dd6f5379e9c9f50738b)
Vegye figyelembe, hogy az üres 0 × 0 mátrix saját inverze, és a normája nulla a választott normától függetlenül. Kondicionálása tehát e meghatározás szerint 0. Vannak, akik definiálják a cond () 0 × 0 = 1 értéket, mert a null lineáris térkép tökéletes pontossággal rendelkezik (tehát 1-es pontszámot kap), és ez az üres mátrix identitás, az egység mátrixainak mindegyike 1 feltételű.
A lineáris rendszer A X = b , ahol az adatok a mátrix A , és a vektort a második tag b , a kondicionálás ad kötött a relatív hiba elkövetett a megoldást x , ha az adatok egy vagy b zavarja. Kiderülhet, hogy ez a terminál nagyon nagy, így az abból fakadó hiba használhatatlanná teszi a digitális megoldást.
A csomagolás az alkalmazott szabványtól függ. A ℓ 2 térnormára , amelyet megjegyezünk ∥⋅∥ 2 , akkor:
κ(NÁL NÉL)=σmax(NÁL NÉL)σmin(NÁL NÉL){\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {\ sigma _ {\ max} (\ mathrm {A})} {\ sigma _ {\ min} (\ mathrm {A})}}}![{\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {\ sigma _ {\ max} (\ mathrm {A})} {\ sigma _ {\ min} (\ mathrm {A})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9fefb40f8c6f6d6d58d579c349d9f99cbd22f3d)
ahol σ max és σ min a szinguláris értékek maximális és minimális a A . Következésképpen:
- ha A jelentése normális , akkor , ahol λ max és λ min a maximális és minimális sajátértékei a A ;
κ(NÁL NÉL)=|λmax(NÁL NÉL)||λmin(NÁL NÉL)|{\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {| \ lambda _ {\ max} (\ mathrm {A}) |} {| \ lambda _ {\ min} (\ mathrm {A}) |}}}![{\ displaystyle \ kappa (\ mathrm {A}) = {\ frac {| \ lambda _ {\ max} (\ mathrm {A}) |} {| \ lambda _ {\ min} (\ mathrm {A}) |}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62979910ca732a161eaf140250edef221255b072)
- ha A jelentése egységes , majd a .
κ(NÁL NÉL)=1{\ displaystyle \ kappa (\ mathrm {A}) = 1}![{\ displaystyle \ kappa (\ mathrm {A}) = 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75c67f5339e79850372663eb00310bc49f916080)
A ℓ ∞ térnormának , amelyet ∥⋅∥ ∞-nek jelölünk , ha A nem egyes számú alsó háromszögmátrix (azaz ∀ i , a ii ≠ 0 ), akkor:
κ(NÁL NÉL)⩾maxén(|nál nélénén|)minén(|nál nélénén|).{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant {\ frac {\ max _ {i} (| a_ {ii} |)} {\ min _ {i} (| a_ {ii} |)}} .}![{\ displaystyle \ kappa (\ mathrm {A}) \ geqslant {\ frac {\ max _ {i} (| a_ {ii} |)} {\ min _ {i} (| a_ {ii} |)}} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74a461de13072561a4257911a1d4123989525bc4)
Hiba a képletek növelésével
A következő képletekben feltételezzük, hogy a számításokat végtelen pontossággal hajtják végre , vagyis a zavart rendszereket pontosan megoldják.
Úgy véljük, két esetben, attól függően, hogy a második tagja b vagy a mátrix A , amely nem pontosan ismert.
Eset, ahol a második tag változik
A hatékony kiszámítása az inverzió a rendszer A X = b , ahol a mátrix egy ismert a pontosság és ha ez az érték a második tag b , feltételezzük, hogy nem lehet nulla, egy téves , fog egy elméleti relatív hiba az x megoldáson x-el nőtt
Δb{\ displaystyle \ Delta b}
‖Δx‖/‖x‖{\ displaystyle \ | \ Delta x \ | / \ | x \ |}![\ | \ Delta x \ | / \ | x \ |](https://wikimedia.org/api/rest_v1/media/math/render/svg/b48c75695330337e4635a0a6b13c53ffa9e32919)
‖Δx‖‖x‖⩽κ(NÁL NÉL)‖Δb‖‖b‖{\ displaystyle {\ frac {\ Green \ Delta x \ Green} {\ Green x \ Green}} \ leqslant \ kappa (\ mathrm {A}) {\ frac {\ Green \ Delta b \ Green} {\ Green b \ Zöld}}}![{\ displaystyle {\ frac {\ Green \ Delta x \ Green} {\ Green x \ Green}} \ leqslant \ kappa (\ mathrm {A}) {\ frac {\ Green \ Delta b \ Green} {\ Green b \ Zöld}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d95a4d8d2b72ab10f9159feb06625d1d32d354e)
.
Eset, ahol a mátrix változik
Ha a mátrix Egy megy módosítását , az egyik a növekedés a hiba képest számítás a pontos mátrixot A által adott
ΔNÁL NÉL{\ displaystyle \ Delta \ mathrm {A}}![{\ displaystyle \ Delta \ mathrm {A}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/192bc9175028758a0cba0f43c1b0a0e22c0d38ea)
‖Δx‖‖x+Δx‖⩽κ(NÁL NÉL)‖ΔNÁL NÉL‖‖NÁL NÉL‖{\ 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}}}![{\ 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/192d05c083a5ef5eed3f5df5b79255350cbbb707)
.
Példa egy rosszul kondicionált mátrixra
Legyen a mátrix
NÁL NÉL=(7111.10.26.5.28.11.38.6.9.36.){\ displaystyle \ mathrm {A} = {\ begin {pmatrix} 7 & 1 & 11 & 10 \\ 2 & 6 & 5 & 2 \\ 8 & 11 & 3 & 8 \\ 6 & 9 & 3 & 6 \ \\ end {pmatrix}}}![{\ displaystyle \ mathrm {A} = {\ begin {pmatrix} 7 & 1 & 11 & 10 \\ 2 & 6 & 5 & 2 \\ 8 & 11 & 3 & 8 \\ 6 & 9 & 3 & 6 \ \\ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49717cd75ef41fd11cccf8aabcad050d7ab6bbe1)
,
és a vektor
b=(29.153024.){\ displaystyle b = {\ begin {pmatrix} 29 \\ 15 \\ 30 \\ 24 \\\ end {pmatrix}}}![{\ displaystyle b = {\ begin {pmatrix} 29 \\ 15 \\ 30 \\ 24 \\\ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6bb6bdc44f8f8b362e9452627707ac476e69ff1)
.
Az A x = b rendszer felbontása megadja
x=(1111){\ displaystyle x = {\ begin {pmatrix} 1 \\ 1 \\ 1 \\ 1 \\\ end {pmatrix}}}![{\ displaystyle x = {\ begin {pmatrix} 1 \\ 1 \\ 1 \\ 1 \\\ end {pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a19bc031a88df379ab4cda1a76abc2015cead389)
.
Ha helyettesítjük a b második tagot, a második zavart tagot
b′=b+(0,1-0,10,1-0,1)=(29.,114,9.30,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}}}![{\ 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b34d5effa5788e0b658ba1c0738d088e27ada775)
,
a megfelelő x ' megoldás lesz
x′=NÁL NÉL-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}}.}![{\ displaystyle x '= \ mathrm {A} ^ {- 1} b' \ simeq {\ begin {pmatrix} 6 {,} 222 \\ 0 {,} 133 \\ 1 {,} 633 \\ - 3 { ,} 256 \\\ end {pmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91d6e156c564db9f3f96d26053e6f2582ffca017)
B és x relatív hibája 0,004, illetve 3,4108, ami a relatív hiba körülbelül 860-szoros növekedését jelenti. Ez a szám az ugyanabban a sorrendben, mint a kondicionáló A mátrix A , amely 1425 (a kondicionáló vesszük képest nyomnorma által indukált euklideszi normája a ).
R4{\ displaystyle \ mathbb {R} ^ {4}}![\ mathbb {R} ^ {4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4abb9b9dab94f7b25a4210364f0f9032704bfb9)
Függelékek
jegyzet
-
F. Kwok - Numerikus elemzés (Genfi Egyetem)
-
(en) Nicholas J. Higham , pontosságát és stabilitását Numerikus Algoritmusok , Soc. Ind. Appl. Math.,1996, 688 p. ( ISBN 0-89871-355-2 ) , p. 126.
-
J. Todd , Programozás a numerikus matematikában , vol. 7, Besançon, Editions du CNRS,1968, 392 p. , 16 × 25 cm ( ISBN 978-2-222-01037-1 ) , „Feltételes számokkal”, p. 141-159
-
(in) Carl de boer, " Egy üres gyakorlat " [PDF] (elérhető május 31, 2018 )
-
Ez például a Scilab szoftver választása az 5.3 és 6.0 verziók között, lásd: “ Üres mátrix (Scilab 5.3.0) ” , help.scilab.org ,2011. január 26(megtekintve 2018. június 4-én ) és „ Üres mátrix (Scilab 6.0.1) ” , a help.scilab.org oldalon ,2018. február 12(megtekintve : 2018. június 4. ) .
Kapcsolódó cikkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">