Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

3.2. Cramer-szabály

3.2. Cramer-szabály

Ebben a pontban olyan speciális egyenletrendszerekről lesz szó, amelyekben megegyezik az ismeretlenek és az egyenletek száma. Az együtthatómátrix ekkor négyzetes, és így létezik determinánsa. Először megmutatjuk, hogy ha ez a determináns nem nulla, akkor az egyenletrendszernek bármilyen jobb oldal mellett pontosan egy megoldása van, és erre a megoldásra determinánsok segítségével képletet is adunk:

3.2.1 Tétel (Cramer-szabály)

Ha A    Tn×n és D=det A≠0, akkor az Ax_=b_ egyenletrendszernek pontosan egy megoldása van. A megoldásban xj=Dj/D, ahol a Dj determinánst úgy kapjuk, hogy D-ben a j-edik oszlop helyére a jobb oldali konstansokat (azaz a b_ vektor komponenseit) írjuk.❶

Például

Bizonyítás: Mivel a feltétel szerint létezik A–1, ezért az Ax_=b_ egyenletrendszert balról A–1-gyel beszorozva ekvivalens egyenletrendszert nyerünk. (Az ekvivalenciát az biztosítja, hogy a kapott egyenletrendszert balról A-val beszorozva ismét az eredeti egyenletrendszerhez jutunk vissza — közben természetesen többször kihasználtuk a mátrixszorzás tulajdonságait.) Így az x_=A-1b_ egyenletrendszer keletkezett, ami „már meg is van oldva”. Ezzel igazoltuk, hogy az eredeti egyenletrendszernek pontosan (ez az) egy megoldása van.

Hátra van még, hogy az x_=A-1b_ megoldást a kívánt alakra hozzuk. A mátrixszorzás szabályai szerint xj éppen az A–1 mátrix j-edik sorának és a b_ vektornak a szorzata. Felhasználva a mátrix inverzére a 2.2.2 Tétel bizonyításában adott képletet, így xj=(1/D)(A1jβ1+…+Anjβn), ahol Alm a D determináns megfelelő előjeles aldeterminánsait jelöli. Mivel a Dj determináns csak a j-edik oszlopában tér el D-től, ezért a j-edik oszlophoz tartozó megfelelő előjeles aldeterminánsok D-ben és Dj-ben azonosak. Ennélfogva Dj-t a j-edik oszlopa szerint kifejtve Dj1A1j+…+βnAnj adódik, tehát xj valóban átírható xj=Dj/D alakba.❷

A Cramer-szabálynak elsősorban elméleti jelentősége van. Az egyenletrendszerek gyakorlati megoldásánál csak ritkán használjuk, hiszen egyrészt eleve csak igen speciális esetekben alkalmazható, másrészt még ekkor is általában jóval több számolást igényel, mint a Gauss-kiküszöbölés (gondoljuk meg, hogy a teljes eredményt adó Gauss-kiküszöbölés ebben az esetben alig tart tovább, mint egyetlen n-edrendű determinánsnak a kiszámítása, a Cramer-szabályhoz pedig n+1 darab ilyen determinánst kell kiszámítani).

Természetesen érdemes a Cramer-szabályra támaszkodni, ha a D és Dj determinánsok egyszerűen meghatározhatók. Hasznát vehetjük akkor is, ha „észreveszünk” egy megoldást és kimutatjuk, hogy D≠0; ekkor ugyanis a fenti tételből tudjuk, hogy a (ki)talált megoldáson kívül több megoldás nem is lehet.

A Cramer-szabály történeti (és középiskolai tanítási) szempontból is érdekes. Ha az α11x112x21, α21x122x22 általános 2 ismeretlenes és 2 egyenletből álló (mondjuk valós) egyenletrendszert (akármilyen módszerrel) megoldjuk, akkor könnyen adódik, hogy (pontosan) akkor van egyértelmű megoldás, ha α11α22–α12α21≠0, és ekkor

Vegyük észre, hogy ez éppen a Cramer-szabály az n=2 esetben. Némi fáradsággal még n=3-ra is kihozhatjuk „kisipari módszerekkel” a megfelelő eredményt. Éppen az ilyen típusú észrevételek indították el a determinánsfogalom kialakulását és alkalmazását a lineáris egyenletrendszerek megoldására.

A Cramer-szabálynál nagyon fontos feltétel, hogy az együtthatómátrix determinánsa ne legyen nulla. Az xj-re felírt képlet D=0 esetén persze eleve értelmetlen, azonban ennél több is igaz; ha D=0, akkor az egyenletrendszernek semmiképpen sem lehet egyértelmű megoldása:

3.2.2 Tétel

Ha A    Tn×n és D=det A=0, akkor az Ax_=b_ egyenletrendszer vagy nem oldható meg, vagy pedig egynél több megoldása van.❶

Bizonyítás: Végezzünk Gauss-kiküszöbölést az Ax_=b_ egyenletrendszerrel, de most a(z esetleg keletkező) csupa nulla sorokat ne hagyjuk el. Ekkor az elemi ekvivalens átalakítások során kapott együtthatómátrixok determinánsa — a determinánsokra vonatkozó elemi tulajdonságok szerint — továbbra is nulla marad. Így az RLA bal oldalának a determinánsa is nulla. Ha az egyenletrendszernek egyértelmű lenne a megoldása, akkor minden oszlopba kerülne vezéregyes, de ekkor az RLA bal oldala az egységmátrix lenne, amelynek a determinánsa nem nulla. Ez az ellentmondás biztosítja, hogy az egyenletrendszernek nem lehet egyértelmű megoldása.❷

Megjegyezzük, hogy a 3.2.2 Tétel bizonyításának mintájára az is igazolható, hogy ha az együtthatómátrix determinánsa nem nulla, akkor az egyenletrendszernek egyetlen megoldása van. (Ekkor már általában nem igaz, hogy a Gauss-kiküszöbölés során kapott együtthatómátrixok determinánsa nem változik, az azonban igaz, hogy sohasem válik nullává.) Ezzel a Cramer-szabály egy részére új bizonyítás adódott („csak” a képletet nem kaptuk meg ily módon).

A fentiek alapján (az ugyanannyi ismeretlent és egyenletet tartalmazó) homogén lineáris egyenletrendszerekre az alábbi eredményt nyerjük:

3.2.3 Tétel

Legyen A    Tn×n Az Ax_=0_ homogén lineáris egyenletrendszernek akkor és csak akkor van nemtriviális megoldása, ha det A=0.❶

Bizonyítás: Ha det A=0, akkor a 3.2.2 Tétel szerint nem lehet egyértelmű megoldás, tehát a triviális megoldáson kívül kell még lennie megoldásnak. Ha det A≠0, akkor a 3.2.2 Tétel utáni megjegyzés (vagy a 3.2.1 Tétel) alapján egyértelmű a megoldás, tehát csak a triviális megoldás létezik.❷

Megjegyezzük, hogy mindezek alapján új (és teljes) bizonyítást nyerhetünk a négyzetes mátrixok invertálhatóságáról és a nullosztókról szóló 2.2.2 és 2.2.5 tételekre is, ezeket a 3.5 pontban tárgyaljuk majd.

A Cramer-szabály egyik alkalmazásaként most egy interpolációs polinomokról szóló tételt igazolunk:

3.2.4 Tétel

Legyenek γ1,…,γn a T test különböző elemei, β1,…,βn pedig tetszőleges T-beli elemek. Ekkor pontosan egy olyan legfeljebb n–1-edfokú fTx polinom létezik (megengedve a foknélküli nulla polinomot is), amelyre fi)=βi, i=1,2,…,n.❶

Bizonyítás: Legyen f01x+…+δn–1xn–1, ekkor a feltétel pontosan a

egyenletrendszert jelenti, ahol a δi-k az ismeretlenek. Az egyenletrendszer determinánsa a V1,…,γn) Vandermonde-determináns, amely a γi-k különbözősége miatt nem nulla. Így a Cramer-szabály alapján az egyenletrendszernek pontosan egy megoldása van.❷

A Cramer-szabály képletét alkalmazva megkaphatjuk magukat a δi együtthatókat, tehát az f polinomot is, azonban — mint említettük — nem biztos, hogy ez a leggyorsabb eljárás f előállítására. Ha szerencsénk van, akkor itt is „kitalálhatjuk” a polinomot, és ezután az egyértelműség miatt már biztosak lehetünk abban, hogy ez az egyetlen megfelelő polinom.

Az f-et (az adott γi „helyekhez” és βi helyettesítési értékekhez tartozó) interpolációs polinomnak nevezzük. Az „interpolációs” jelző arra utal, hogy (nagyon pongyolán fogalmazva) az f polinom valósítja meg azt a „lehető legegyszerűbb” függvényt, amely a γi helyeken előírt βi helyettesítési értékek segítségével határozza meg („iktatja közbe”) a többi helyen felvett értéket. Az f polinom két másik előállítási módjára, valamint egyértelműségének további lehetséges bizonyításaira nézve lásd a 3.2.9–3.2.11 feladatokat.

Feladatok

3.2.1 Oldjuk meg a komplex számok körében az alábbi egyenletrendszert.

 

3.2.2 Oldjuk meg a valós számok körében:

 

3.2.3 Oldjuk meg az alábbi valós egyenletrendszereket, ahol b)-ben αi≠αj, ha ij.

 a) x1+x2++xn=nx1+2x2++nxn=n2x1+2n-1x2++nn-1xn=nn

 b) x1+x2++xn=1α1x1+α2x2++αnxn=βα1n-1x1+α2n-1x2++αnn-1xn=βn-1

3.2.4 Használjuk a 3.2.1 Tétel jelöléseit. Melyek igazak az alábbi állítások közül?

a) Ha D=0, de van olyan j, amelyre Dj≠0, akkor az Ax_=b_ egyenletrendszer nem oldható meg.

b) Ha D=0 és minden j-re Dj=0, akkor az Ax_=b_ egyenletrendszernek egynél több megoldása van.

3.2.5 Legyenek A1, A2    Tn×n invertálható mátrixok, és tekintsük az A1x_=b_ és A2x_=b_ egyenletrendszereket (azonos jobb oldallal). Bizonyítsuk be, hogy

a) pontosan akkor lesz bármilyen b_ esetén a két egyenletrendszernek közös megoldása, ha A1=A2;

b) pontosan akkor nem lesz semmilyen b_0_ esetén sem a két egyenletrendszernek közös megoldása, ha A1A2 is invertálható.

3.2.6

a) Legyen mij, i,j=1,2,…,n olyan n2 darab egész szám, hogy az mij-kből képezett determináns nem osztható 7-tel. Tegyük fel, hogy v1,…,vn olyan egész számok, hogy v1mj1+…+vnmjn bármely j-re osztható 7-tel. Bizonyítsuk be, hogy ekkor minden vi osztható 7-tel.

*b) Hogyan általánosítható a feladat 7 helyett tetszőleges egész számra?

A további feladatok az interpolációs polinomhoz kapcsolódnak. A 3.2.4 Tétel jelöléseit fogjuk használni.

3.2.7 Határozzuk meg azt a legfeljebb harmadfokú f komplex együtthatós polinomot, amelyre

a) f(–1)=12, f(4)=7, f(6)=5, f(9)=2;

b) f(1)=f(–1)=3, f(2)=f(–2)=9;

c) f(1)=i, f(i)=–1, f(–1)=–i, f(–i)=1;

d) f(–1)=f(i)=f(–i)=1, f(1)=9.

3.2.8 Hány olyan pontosan a) n–1-edfokú; b) n-edfokú f polinom van, amely a 3.2.4 Tétel (többi) feltételeit kielégíti?

3.2.9 Adjunk új bizonyítást a 3.2.4 Tételben szereplő f egyértelműségére, arra támaszkodva, hogy egy polinomnak legfeljebb annyi gyöke lehet, mint amennyi a fokszáma.

3.2.10 Newton-féle interpolációs polinom. Adjunk új bizonyítást a 3.2.4 Tételre (azaz f létezésére és egyértelműségére) úgy, hogy f-et a következő alakban keressük:

 

3.2.11 Lagrange-féle interpolációs polinom. Legyen n>1.

a) Keressünk olyan legfeljebb n–1-edfokú Li polinomot, amelyre Lij)=0, ha ji és Lii)=1. [Ez azt jelenti, hogy az interpolációs problémát (először) abban a nagyon speciális esetben oldjuk meg, amikor az előírt helyettesítési értékek egyike 1, az összes többi pedig 0. Az Li-ket (a γi helyekhez tartozó) Lagrange-féle alappolinomoknak nevezzük.]

b) Mutassuk meg, hogy az f=i=1nβiLi polinom megfelel a 3.2.4 Tétel feltételeinek.

M*3.2.12 Legyen n>1.

a) Melyik (jólismert) polinom az (n darab) Li Lagrange-féle alappolinom összege?

b) Legyenek γ1,…,γn különböző valós számok és ν tetszőleges valós. Adjuk meg egyszerűbb alakban az alábbi két valós számot:

 (b1)i=1njiν-γjγi-γj (b2)i=1nji1γi-γj

3.2.13 Melyek igazak az alábbi állítások közül?

a) Ha egy (komplex együtthatós) polinom minden egész helyen egész értéket vesz fel, akkor a polinom egész együtthatós.

b) Ha egy (komplex együtthatós) polinom minden racionális helyen racionális értéket vesz fel, akkor a polinom racionális együtthatós.

*3.2.14 Legyen T véges test. Mutassuk meg, hogy minden Φ:TT függvény polinomfüggvény, azaz van olyan fTx polinom, hogy minden τT-re fτ=Φτ

*3.2.15 Ali Baba a kincset a 40 rablóra akarja hagyni, de fél, hogy azok összevesznek, és ezért olyan módszert szeretne, hogy csak akkor juthassanak hozzá, ha már legalább 25 rabló előre megegyezett, hogyan osztozkodnak. A kincshez vezető útvonalat egy számítógép rejti, ehhez csak úgy lehet hozzáférni, ha valaki bepötyögi a megfelelő jelszót, ami egy (meglehetősen nagy) természetes szám. Ali Baba az Interpol tanácsára egyenként mindegyik rablónak a fülébe súg valamit. Ha bármelyik 25 rabló összefog, akkor meg tudja fejteni a kulcsszámot, de 24-en hiába próbálkoznak, együttesen sem lesz semmilyen információjuk a számról. Mit tanácsolt Ali Babának az Interpol(áció)?