3. A reduced row echelon alak

A mátrix redukált sor echelon alakja (RRE alak) (Reduced Row Echelon Form – RREF) a következő feltételeket teljesíti:

  • Minden nem csupa 0-ból álló sor legelső nem 0 eleme 1-es (ezt vezető 1-esnek nevezzük).

Ha egy sor vezető 1-ese az r-edik oszlopban van, akkor

  • az r-edik oszlop össze többi eleme 0.

  • a későbbi sorok vezető 1-esei az r-edik oszloptól jobbra kell legyenek

A csak nulla elemeket tartalmazó sorok a mátrix aljára csoportosítottak.

Egy mátrix RRE alakja egyértelmű.

Az alábbi mátrix egy példa a reduced row echelon alakra:

[10204013010001200000]MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaadmaabaqbaeqabqqbaaaaaeaacaaIXaaabaGaaGimaaqaaiaaikdaaeaacaaIWaaabaGaaGinaaqaaiaaicdaaeaacaaIXaaabaGaaG4maaqaaiaaicdaaeaacaaIXaaabaGaaGimaaqaaiaaicdaaeaacaaIWaaabaGaaGymaaqaaiaaikdaaeaacaaIWaaabaGaaGimaaqaaiaaicdaaeaacaaIWaaabaGaaGimaaaaaiaawUfacaGLDbaaaaa@49C2@ (F.38)

Látható, hogy ez az alak a Gauss eliminációnál tárgyalt elemi műveletekkel előállítható.

Az LS-SVM redukciójánál (az LS2-SVM support vektorainak meghatározásához) a RRE alakot biztosító algoritmust egészítjük ki. Az algoritmus során figyeljük a pivot elem értékét és amennyiben az egy általunk meghatározott εMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiqbew7aLzaafaaaaa@3AC7@ tolerancia értéknél kisebb, az adott oszlopot kinullázzuk (nem vesszük figyelembe). Az algoritmus menete – melynek alapja a részleges pivotolással végzett Gauss-Jordan elimináció – az alábbi. Iteratívan lépdeljünk végig a mátrix főátlója mentén:

1. Legyen j az első nem csupa nulla oszlop indexe.

2. Határozzuk meg a j-edik oszlopban az ijMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadMgacqGHLjYScaWGQbaaaa@3CB7@ sorindexű elemek közül a legnagyobbat. Jelöljük ezt az elemet p-vel.

3. Ha pεMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadchacqGHKjYOcuaH1oqzgaqbaaaa@3D71@ (ahol εMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiqbew7aLzaafaaaaa@3AC7@a tolerancia érték) akkor nullázzuk ki az oszlop alsó részét (a jMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadQgaaaa@36D8@ -edik oszlop azon elemeit, melyekre a sorindex ijMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadMgacqGHLjYScaWGQbaaaa@3CB7@ );

egyébként jegyezzük meg az oszlop indexét, mert bázis, és ha i>jMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadMgacqGH+aGpcaWGQbaaaa@3BF9@ cseréljük fel a p elemet tartalmazó sort a j-edik sorral. Így az oszlop legnagyobb eleme, p – az ún. generáló elem, ami egyben az i-edik sor balról első nem nulla eleme, a pivot elem – a főátlóba kerül. Osszuk el ezt a sort p-vel, ezáltal p helyére 1 kerül, és vonjuk ki ennek a sornak megfelelő konstans-szorosait a többi sorból, hogy ezáltal kinullázzuk a többi sor j-edik pozícióban lévő elemeit.

4. Növeljük meg j-t: j=j+1MathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadQgacqGH9aqpcaWGQbGaey4kaSIaaGymaaaa@3D95@ és folytassuk az egész eljárást a második lépéstől.

Ez az eljárás visszaadja az εMathType@MTEF@5@5@+=feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqkLspw0le9v8qqaqFD0xXdHaVhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiqbew7aLzaafaaaaa@3AC7@ tolerancia értelmében lineárisan független oszlopok listáját (azaz az LS2-SVM-ben használt szupport vektorokat).