visszavezetéssel

A visszavezetéssel (back-substitution) egy lineáris egyenletrendszer megoldásának módszere, amely akkor alkalmazható, ha a koefficiens mátrix Gauss-elimináció után felső háromszögű alakban van. Ilyenkor a megoldást nem a teljes rendszer kiolvasásával kezdjük, hanem a legutolsó, legfelső sorból indulva végzünk visszafelé számolást a változók felé.

Eljárásának lényege: ha az Ax = b rendszert egy felső háromszögű A mátrix írja le, akkor x_n = b_n / a_nn. Ezt követően k = n−1-től 1-ig haladva számoljuk ki x_k-et: x_k = (b_k − sum_{j=k+1}^{n} a_kj x_j) / a_kk. Fontos feltétel, hogy minden a_kk nem legyen 0, egyébként pivotálás szükséges. Ha az elimináció során nem alakítható ki tisztán felső háromszögű forma, a visszavezetés csak a megfelelő átalakítás után használható.

Példa: egy 3×3-as felső háromszögű rendszer legyen Σ. Az A és b így néz ki: A = [3 2 −1; 0 4 5; 0 0 2], b = [5, 6, 4]. Ekkor x3 = 4/2 = 2; x2 = (6 − 5·x3)/4 = (6 − 10)/4 = −1; x1 = (5 − 2·x2 − (−1)·x3)/3 = (5 + 2 − 2)/3 = 3. Tehát x = [3, −1, 2].

Kapcsolódó témák közé tartozik a Gauss-elimináció, az LU-dekompozíció és a pivotálás. Az eljárás időkomplexitása általában O(n^2) a háromszögű megoldásokra, és központi szerepet játszik a lineáris algebrában, a számítógépes numerikában és a mérnöki alkalmazásokban.

---