Sturm tétele

A matematika , pontosabban az elemzés , a tétel a Sturm , székhelye 1829 által Charles Sturm , lehetővé teszi, hogy kiszámítja a száma különböző valós gyökereit egy polinom függvény szerepel az adott intervallumban. A megfelelő hatékony számítási módszert Sturm algoritmusnak nevezzük .

Sturm lakosztály

Adunk magunknak egy $P = x n + a n - 1 x n - 1 + ... + a 1 x + a 0$ polinomot . A $P$ polinom Sturm szekvenciája vagy Sturm lánca a $P$ $0$ $,$ $P$ $1$ $, ...,$ $P$ $m$ polinomok véges szekvenciája . Indukcióval épül fel:

$P 0 = P$ ;
$P 1 = P$ 'ahol $P'$ a -származék a $P$ , vagyis a polinom $P „= nx n - 1 + ... + a 1$ ;
Az $i \geq 2$ , $P i$ az ellentéte a maradék elosztjuk $P i - 2$ által $P i - 1$ .
A konstrukció az utolsó, nulla nélküli polinomnál áll meg.

Ennek a szekvenciának a megszerzéséhez kiszámítjuk a köztes maradékokat, amelyeket úgy kapunk meg, hogy Euclid algoritmusát alkalmazzuk $P 0-ra$ és annak $P 1$ származékára :

{\ displaystyle {\ begin {mátrix} P_ {0} & = & P_ {1} Q_ {1} & - & P_ {2} \\ P_ {1} & = & P_ {2} Q_ {2} & - & P_ {3} \\\ vdots & \ vdots & \ vdots & \ vdots & \ vdots \\ P_ {m-2} & = & P_ {m-1} Q_ {m-1} & - & P_ {m } \\ P_ {m -1} & = & P_ {m} Q_ {m} & - & 0 \\\ end {mátrix}}}

Ha $P-$ nek csak különálló gyökei vannak, akkor az utolsó tag nem nulla konstans. Ha ez a kifejezés nulla, $P$ több gyököt ismer be, és ebben az esetben Sturm tételét alkalmazhatjuk a $T 0 , T 1 , ..., T m - 1 , 1$ szekvencia felhasználásával $,$ amelyet a $P 1 , P$ elosztásával kapunk $.$ $2$ $, ...,$ $P$ $m$ $- 1$ által $P m$ .

A tétel állítása

A száma különböző valós gyöke egy intervallum $[ a , b ]$ egy polinom a valós együtthatók , amelyek $egy$ és $b$ nem gyökerek, egyenlő a számos változás a jele a Sturm szekvencia határait ezen intervallum.

Formálisabban foglalja bele $σ ( ξ )$ a $jelváltozások$ számát (a nulla nem számít változás jelének) az alábbiakba

{\ displaystyle P (\ xi), P_ {1} (\ xi), P_ {2} (\ xi), \ ldots, P_ {m} (\ xi)}

Sturm tétele szerint két valós $a$ , $b$ , $a < b szám esetén$ , ahol $a$ és $b$ nem $P$ gyökei, az $[ a , b ]$ intervallumban a gyökerek száma :

{\ displaystyle \ sigma (a) - \ sigma (b) ~}

. Demonstráció

Bemutatót adunk referenciaként.

Példa

Tegyük fel, hogy meg akarjuk tudni a gyökerek számát a $p ( x ) = x 4 + x 3 - x -1$ polinom bizonyos intervallumában . Az első két kifejezés kiszámításával kezdjük.

{\ displaystyle {\ begin {aligned} p_ {0} (x) & = p (x) = x ^ {4} + x ^ {3} -x-1 \\ p_ {1} (x) & = p '(x) = 4x ^ {3} + 3x ^ {2} -1 \ end {igazítva}}}

Elosztjuk $p 0$ által $p 1$ megkapjuk a maradék $- 3 / 16. x 2 - 3 / 4 x - 15 / 16.$ , És szorozni $-1$ jutunk $p 2 ( x ) = 3 / 16. x 2 + 3 / 4 x + 15 / 16.$ . Ezután elosztjuk $p 1$ által $p 2$ és szaporodnak a fennmaradó részt pedig $-1$ , megkapjuk $p 3 ( x ) = -32 x -64$ . Ezután elosztjuk $p 2-$ t $p 3-$ mal, és a fennmaradó részt megszorozzuk $-1-vel$ , így $p 4 ( x ) = - 3 / 16.$ .

Végül a $P$ polinom Sturm szekvenciája a következő:

{\ displaystyle p_ {0} (x) = x ^ {4} + x ^ {3} -x-1}

{\ displaystyle p_ {1} (x) = 4x ^ {3} + 3x ^ {2} -1}

{\ displaystyle p_ {2} (x) = {\ tfrac {3} {16}} x ^ {2} + {\ tfrac {3} {4}} x + {\ tfrac {15} {16}}}

{\ displaystyle p_ {3} (x) = - 32x-64}

{\ displaystyle p_ {4} (x) = - {\ tfrac {3} {16}}}

Az összes gyökér számának megállapításához, pl. közötti $-\infty$ és + $\infty$ , értékeljük $p 0 , p 1 , p 2 , p 3 ,$ és $p 4$ a $-\infty$ és jelölje a megfelelő jelek sorozata: $+ - + + -$ . Ez tartalmazza a három jel változások ( $+$ a $-$ , majd $-$ a $+$ , akkor $+$ a $-$ ). Ugyanezt tesszük a + $\infty$ -ben is, és megkapjuk a $+ + + - - -$ jelek sorozatát , amely csak előjelváltozást tartalmaz. Szerint a Sturm-tétel, a teljes száma gyökerei polinom $P$ jelentése $3 - 1 = 2$ tudjuk ellenőrizni a megjegyzéssel, hogy a $p ( x ) = x 4 + x 3 - X - 1$ beépül $( x 2 - 1) ( x 2 + x + 1)$ , ahol azt látjuk, hogy $x 2 - 1-$ nek két gyöke van ( $-1$ és $1$ ), míg $x 2 + x + 1-$ nek nincs valódi gyöke.

Alkalmazások

Tudjuk használni ezt a tételt, hogy kiszámítja a teljes száma a különböző valós gyöke, választott a határokat $a$ és $b$ , hogy minden igazi gyökerei az intervallum $[ a , b ]$ : például $[ a , b ] = [- M , M ]$ alkalmas, a kívánt módon:

{\ displaystyle M = 1 + {\ max} _ {i = 0} ^ {n-1} | a_ {i} |}

vagy .

{\ displaystyle M = \ max \ bal (1, \ sum _ {i = 0} ^ {n-1} | a_ {i} | \ jobb)}

Használhatjuk ezt a tételt bármely polinom gyökereinek megtalálásához is dichotómiával, és ezáltal optimalizálhatunk minden polinom kritériumot (a származék gyökereinek megkeresésével).

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia " Sturm-tétel " című cikkéből származik ( lásd a szerzők felsorolását ) .

C. Sturm, „ A numerikus egyenletek felbontásáról ”, Matematikai és fizikai tudományok , VI. Kötet, Párizs, 1835. o. 271-318
Edouard Callandreau, „ Híres matematikai problémák ”, Albin Michel kiadás , Párizs, 1949, 1 kötet, 478p

(in) Peter Bürgisser Michael Clausen és Amin Shokrollahi , algebrai bonyolultság elmélet , Springer Science & Business Media,2013. március 14, 618 p. ( ISBN 978-3-662-03338-8 , online olvasás ) (3.10. Gyakorlat, 93. o.).
[PDF] Sandrine Caruso, „Suite de Sturm. " .
További példákat az Egyenletelmélet (matematika) című cikkben talál .
Lásd Lagrange tételét a polinomokról .
(in) Holly P. Hirst és Wade T. Macey , " Burkolat Roots polinomok " , The College matematika Journal , MAA , vol. 28, n o 4,1997. szeptember, P. 292-295 ( DOI 10.2307 / 2687152 ).