Gauss-Jordan Elimináció

A=(({{1, 1}, {1, -1}}));b={.5,.1};

LinearSolve[A,b]

Det[A]

Minors[A,1]

Minors[A,2]

Bal felső főminorok: olyan almátrixok determinánsai, melyeknél rendre az {1,2,…,j} sorokat és oszlopokat tartjuk meg.

(Subscript[M, j])=Det[(({{(Subscript[a, 11]), (Subscript[a, 12]), ..., (Subscript[a, 1j])}, {(Subscript[a, 21]), (Subscript[a, 22]), ..., (Subscript[a, 2j])}, {..., ..., ..., ...}, {(Subscript[a, j1]), (Subscript[a, j2]), ..., (Subscript[a, jj])}}))]

|({{(Subscript[a, 11]), (Subscript[a, 12])}, {(Subscript[a, 21]), (Subscript[a, 22])}})|=?

Det[Take[(({{3, -4, 5}, {-3, 2, 1}, {6, 8, -1}})),2,2]]

Minors[(({{3, -4, 5}, {-3, 2, 1}, {6, 8, -1}})),2][[1,1]]

MatrixForm[Inverse[A]]

MatrixRank[A]

NullSpace[{{1,1},{1,1}}]

MatrixForm[ConjugateTranspose[{{1,2+I},{1-3I,2}}]]

Gauss elimináció (alapalgoritmus) [1]

(Subscript[a, 11])(Subscript[x, 1])+(Subscript[a, 12])(Subscript[x, 2])+…+(Subscript[a, 1n])(Subscript[x, n])=(Subscript[b, 1])
 (Subscript[a, 21])(Subscript[x, 1])+(Subscript[a, 22])(Subscript[x, 2])+…+(Subscript[a, 2n])(Subscript[x, n])=(Subscript[b, 2])
 ...
 (Subscript[a, n1])(Subscript[x, 1])+(Subscript[a, n2])(Subscript[x, 2])+…+(Subscript[a, nn])(Subscript[x, n])=(Subscript[b, n])

Változók száma egyenlő az egyenletek számával. A rendszer elsőfokú algebrai rendszer.
 Cél: a megoldásvektor hatékony meghatározása.

(EU)

Az alábbi sorátalakítások nem változtatják meg a megoldásvektort(/megoldásteret):

1a) (Subscript[s, j])←α (Subscript[s, j ])(α≠0)
2a) (Subscript[s, j])↔(Subscript[s, k ])(j≠k)
3a) (Subscript[s, j])←(Subscript[s, j])-α (Subscript[s, k])

A Gauss elimináció alapalgoritmusa

Csak szabályos lineáris egyenletrendszer,  összes balfelső főminor nemzéró; (Subscript[∀, j])(Subscript[M, j])≠0 .
a) fázis: nullázás (A/b)~(U|b') 3a) típusú sorátalakításokkal

Csak a kibővített együtthatómátrixszal dolgozunk. Célunk egy felső trianguláris  mátrix kialakítása sorátalakításokkal úgy, hogy a rendszerhez tartozó megoldásvektor ne változzon.
Ezt a fázist j lépésre osztjuk. A j-edik lépésben  a főátlóban lévő pivot elemmel ((Subscript[a, jj])) nullázunk a j-edik oszlopban csak a főátló alatt. A már kinullázott elemek nem változnak!

b) fázis: visszahelyettesítés (↑)

Az U felső trianguláris együtthatómátrixú rendszer megoldása egyszerűen az utolsó egyenletből indulva visszahelyettesítéssel történik.  3x3-as esetben például
(Subscript[u, 33])(Subscript[x, 3])=(Subscript[b, 3])'⟹ (Subscript[x, 3])=(Subscript[b, 3])'/(Subscript[u, 33]) ...

3(Subscript[x, 1])-4(Subscript[x, 2])+5(Subscript[x, 3])=-1
-3(Subscript[x, 1])+2(Subscript[x, 2])+(Subscript[x, 3])=1
6(Subscript[x, 1])+8(Subscript[x, 2])-(Subscript[x, 3])=35

Black-Box: a LinearSolve paranccsal kapjuk a megoldásvektort (LinearSolve[A,b]).

LinearSolve[(({{3, -4, 5}, {-3, 2, 1}, {6, 8, -1}})),{-1,1,35}]

White-Box:
A Gauss-eliminációval ezt a (({{2}, {3}, {1}}))megoldást az alábbi lépésekben érjük el:
a)

(({{3, -4, 5, -1}, {-3, 2, 1, 1}, {6, 8, -1, 35}}))~(({{3, -4, 5, -1}, {0, -2, 6, 0}, {0, 16, -11, 37}}))~(({{3, -4, 5, -1}, {0, -2, 6, 0}, {0, 0, 37, 37}}))

[(1) (Subscript[a, 11])≠0, s2←s2+s1, (2) s3←s3-2s1] , [(3) s3←s3+8s2]
b) (Subscript[x, 3])=1⟹(Subscript[x, 2])=3⟹(Subscript[x, 1])=2

LinearSolve[(({{3, -4, 5}, {0, -2, 6}, {0, 0, 37}})),{-1,0,37}]

LinearSolve[(({{3, -4, 5}, {-3, 2, 1}, {6, 8, -1}})),{-1,1,35}]

∀j (Subscript[M, j])≠0⟹  Gauss elimináció alapalgoritmusa meghatározza az x megoldásvektort.

(Subscript[M, n])=Det[A]≠0⟹  Módosított Gauss elimináció algoritmusa meghatározza az x megoldásvektort.

Műveletigény: ~2/3(n^3)

(Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3])=7
4(Subscript[x, 1])+3(Subscript[x, 2])+4(Subscript[x, 3])=8
9(Subscript[x, 1])+3(Subscript[x, 2])+4(Subscript[x, 3])=3

a)
(({{1, 1, 1, 7}, {4, 3, 4, 8}, {9, 3, 4, 3}}))~(({{1, 1, 1, 7}, {0, -1, 0, -20}, {0, -6, -5, -60}}))~(({{1, 1, 1, 7}, {0, -1, 0, -20}, {0, 0, -5, 60}}))

[(1) (Subscript[a, 11])≠0, s2←s2-4s1, (2) s3←s3-9s1,...]
b) (Subscript[x, 3])=60/(-5)=-12, -(Subscript[x, 2])=-20⟹ (Subscript[x, 2])=20, (Subscript[x, 1])=-1

Ellenőrzés

{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}/.Solve[{(Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3])==7,4(Subscript[x, 1])+3(Subscript[x, 2])+4(Subscript[x, 3])==8,9(Subscript[x, 1])+3(Subscript[x, 2])+4(Subscript[x, 3])==3},{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}][[1]]

LinearSolve[(({{1, 1, 1}, {4, 3, 4}, {9, 3, 4}})),{7,8,3}]

{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}/.Solve[{(Subscript[x, 1])+(Subscript[x, 2])+(Subscript[x, 3])==7,0(Subscript[x, 1])-(Subscript[x, 2])+0(Subscript[x, 3])==-20,0(Subscript[x, 1])+0(Subscript[x, 2])-5(Subscript[x, 3])==60},{(Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3])}][[1]]

LinearSolve[(({{1, 1, 1}, {0, -1, 0}, {0, 0, -5}})),{7,-20,60}]

Gauss elimináció (részleges főelemkiválasztás) [1]

Az algoritmusnak ez a módosított változata minden nemszinguláris együtthatóhmátrix esetén működik. 
Ha bizonyos pivotlelemek nullák, akkor sorcserékkel hozunk helyükre nemzéró elemeket.
Megjegyzés: Numerikus szempontok miatt akkor is szükség lehet rá, ha (Subscript[M, j])≠0.

Mutassuk meg, hogy az alábbi példában nem minden balfelső főminor nemzéró és oldjuk meg a rendszert a módosított algoritmussal.

(({{1, 2, 5, 4}, {2, 4, 8, 9}, {-6, 3, -7, 9.5}})) M1≠0, M2=0, M3≠0

(({{1, 2, 5, 4}, {2, 4, 8, 9}, {-6, 3, -7, 9.5}}))~(({{1, 2, 5, 4}, {0, 0, -2, 1}, {0, 15, 23, 33.5}})) (Subscript[~,  (s2↔s3)sorcsere])(({{1, 2, 5, 4}, {0, 15, 23, 33.5}, {0, 0, -2, 1}}))

LinearSolve[(({{1, 2, 5}, {0, 15, 23}, {0, 0, -2}})),{4,33.5,1}]

LinearSolve[(({{1, 2, 5}, {2, 4, 8}, {-6, 3, -7}})),{4,9,9.5}]

Itt: M1=0

LinearSolve[(({{0, 2, -3}, {-2, 1, 2}, {2, 0, 1}})),{4,-6,0}]

Jordan elimináció (Inverz) [1]

X az A∈(ℝ^(n,n)) (multiplikatív) inverze, ha A X=X A=(Subscript[I, n])a, hol (Subscript[I, n])az nxn-es egységmátrix.

A invertálható ⟺ A nemszinguláris.

Jordan elimináció:

Nemszinguláris A négyzetes mátrix az input.
Algoritmus:
(A|(Subscript[I, n]))~…~((Subscript[I, n])|(A^(-1))) 1a)-2a)-3a) típ. sorátalakításokkal
 A j-edik lépésben  a főátlóban lévő normált pivot elemmel ((Subscript[a, jj])) nullázunk a j-edik oszlopban a főátló alatt és felett is.

(A^(-1))=?, ha A=(({{3, 4}, {1, 2}}));

A=(({{3, 4}, {1, 2}}));

Elemi átalakítások az (A|I) mátrixon

(({{3, 4, 1, 0}, {1, 2, 0, 1}}))~(({{1, 4/3, 1/3, 0}, {1, 2, 0, 1}}))~(({{1, 4/3, 1/3, 0}, {0, 2/3, -1/3, 1}}))~(({{1, 4/3, 1/3, 0}, {0, 1, -1/2, 3/2}}))~(({{1, 0, 1, -2}, {0, 1, -1/2, 3/2}}))

Black-Box: Built–in Mathematica függvény

Inverse[A]//MatrixForm

Jordan elimináció minden nemszinguláris mátrix esetén meghatározza effektíven az inverzmátrix elemeit.

Jordan elimináció müveletigénye: ~2(n^3)

(A2^(-1))=? Megoldás: Jordan elimináció

A2=(({{1, 2}, {3, 5}}));

EA2=(A2|I2)
s2⟵s2-3s1

EA2=(({{1, 2, 1, 0}, {3, 5, 0, 1}}));

(({{1, 0}, {-3, 1}})).EA2//MatrixForm

(({{1, 0}, {0, -1}})).(({{1, 0}, {-3, 1}})).EA2//MatrixForm

(({{1, -2}, {0, 1}})).(({{1, 0}, {0, -1}})).(({{1, 0}, {-3, 1}})).EA2//MatrixForm

Megfelelő elimináló/permutáló/normáló mátrixokal való balról szorzás

Inverse[A2]//MatrixForm

(B^(-1))=?

B=(({{1, 1, 1}, {3, 1, 2}, {9, 1, 4}}));

B nemszinguláris

Det[B]

Inverse[B]//MatrixForm

Szimultán egyenletrenszer megoldás:  a Az Ax=e2 megoldása a 2. oszlopvektor!

LinearSolve[B,{0,1,0}]

Az első elimináció eredeménye

BE1=(({{1, 1, 1, 1, 0, 0}, {3, 1, 2, 0, 1, 0}, {9, 1, 4, 0, 0, 1}}));

LL1=(({{1, 0, 0}, {-3, 1, 0}, {-9, 0, 1}}));

LL1.BE1//MatrixForm

N1=(({{1, 0, 0}, {0, -1/2, 0}, {0, 0, 1}}));

N1.LL1.BE1//MatrixForm

Fejezzzük be az előző feladat megoldását.