Fredholm-alternatíva

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

A Fredholm-alternatíva a lineáris egyenlőségrendszerek megoldhatóságáról szól, és bizonyítékot szolgáltat arra az esetre, ha az egyenletrendszer megoldhatatlan.

A tétel[szerkesztés]

Az primál rendszernek akkor és csak akkor van megoldása, ha nincs y duális megoldás, . Azaz a b vektor vagy benne van az A altérben, vagy elválasztható tőle egy y normálisú, az origón átmenő hipersíkkal. Ekkor a hipersík tartalmazza az alteret, de a vektort nem.

A bizonyítás teljes indukcióval működik. Ha az A mátrixnak egy sora van, akkor könnyű a bizonyítás. Ha nullmátrixról van szó, akkor szintén egyszerű. Feltehető tehát, hogy A nem nullmátrix, és legalább két sora van.

Ekkor sor-és oszlopcserékkel elérhető, hogy a1,1 nem nulla. Az egyenletek nem nulla számmal való szorzása és az egyik egyenlet egy másikhoz való hozzáadása nem változtatja meg sem a primál, sem a duál probléma megoldhatóságát. Így elvégezhető a Gauss-elimináció egy lépése.

Az első egyenletet a1,1-gyel leosztva feltehető, hogy a mátrix első oszlopában az első elem 1, és a többi nulla. Töröljük el most az első sort. Ennek a mátrixnak kevesebb sora van, ezért alkalmazható rá az indukciós feltevés: vagy duálisa megoldható.

Ha van x1, akkor az első koordináta választható úgy, hogy az első egyenlet is teljesüljön. Ha az y1 duális megoldás létezik, akkor elé nullát írva az eredeti egy duál megoldását kapjuk. Tehát a primál vagy a duál feladat megoldható.

Mindkettő nem oldható meg; különben lenne, ami ellentmondás.

Jellemzés[szerkesztés]

A tétel fenti alakjában nem látszik, hogy mégis mi áll a megoldhatóság hátterében. Egy nem közvetlen bizonyítás erre is választ ad.

Tétel: A következők ekvivalensek:

  1. az rendszernek van megoldása
  2. az A mátrix rangja nem változik attól, hogy új oszlopként hozzávesszük a b vektort
  3. nincs y, amire

Bizonyítás:

2.→1. Vegyük A rangnyi oszlopát. A kibővített mátrix rangja ugyanekkora, ezért b lineárisan függ ezektől az oszlopoktól, így A oszlopaitól is.

1.→3. Legyen x,y olyan, hogy és . Ezekből kapjuk, hogy .

A nehéz irány a 3.→2.:

Tegyük fel indirekt, hogy a kibővített mátrix rangja nagyobb. Válasszuk ki ennek a lehető legtöbb független sorát, és legyen az általuk alkotott részmátrix. A1 sorai lineárisan összefüggnek, hiszen A -nak nincs ennyi lineárisan független sora. Van tehát egy y1 vektor, hogy , de az mátrixszal szorozva az eredmény nem lesz nulla, hiszen sorai lineárisan függetlenek. Ezért sem lesz egyenlő nullával. Az y1 vektort nulla koordinátákkal kiegészítve egy olyan y vektort kapunk, ami ellentmond a 3. feltételnek.

Források[szerkesztés]