Page 56 - MATINF Nr. 1

56 L. Deaconu

Elementele tabelului vor fi precizate ˆın cadrul algoritmului.

◦
Pasul 1 Generarea tabelului. Primul tabel se completeaz˘a astfel:
1. Prima linie x 1 , x 2 , . . . , x n este doar o notat , ie pentru coloanele asociate necunoscutelor
sistemului. Ea nu se modific˘a pe parcursul algoritmului.
2. A doua linie j 1 , j 2 , . . . , j n se completeaz˘a cu 0, j l = 0, ∀l ∈ 1, n. Ea se completeaz˘a cu
elemente nenule la fiecare pas.
3. Coloana din stˆanga cu elementele i 1 , i 2 , . . . , i m are init , ial toate elementele nule, i k = 0,
0
0
0
∀k ∈ 1, m . La primul pas avem m = m. Se completeaz˘a cu elemente nenule la fiecare
pas al algoritmului.
4. Zona central˘a cont , ine elementele matricei sistemului. La primul tabel (k = 0) avem
[0]
a = a ij , ∀i ∈ 1, m, ∀j ∈ 1, n.
ij
[0]
5. Coloana din dreapta se completeaz˘a cu termenii liberi ai sistemului. Avem b i = b i ,
∀i ∈ 1, m.
◦
0
Pasul 2 Prelucrarea tabelului. La pasul k, (k ∈ 1, m ), parcurgem urm˘atoarele etape:
[k−1] [k−1] [k−1] [k−1]
1. C˘aut˘am, ˆın linia a , a , . . . , a , . . . , a din zona central˘a, un element nenul.
k1 k2 kl kn
Dac˘a g˘asim, ˆıl numim pivot, identific˘am coloana ˆın care se afl˘a (notat˘a x l ˆın tabelul de
[k−1]
mai sus) s , i trecem la pasul urm˘ator. Dac˘a avem a kq = 0, ∀q ∈ 1, n, atunci:
[k−1]
(a) dac˘a b k = 0 elimin˘am linia k deoarece corespunde unei ecuat , ii care este o
combinat , ie liniar˘a a ecuat , iilor precedente s , i care nu conteaz˘a ˆın rezolvarea sistemului.
ˆ 0 0 0
In acest caz num˘arul ecuat , iilor se mics , oreaz˘a cu 1, m ← m − 1. Dac˘a avem k ≤ m ,
◦
relu˘am etapa 1, altfel trecem la Pasul 3 .
[k−1]
(b) dac˘a b 6= 0 algoritmul se opres , te. Sistemul este incompatibil.
k
ˆ
2. In coloana din stˆanga, punem i [k] = l, unde x l este coloana ˆın care a fost identificat pivotul.
k
0
Celelalte elemente r˘amˆan ca la pasul precedent, i [k] = i [k−1] , ∀p ∈ {1, 2, . . . , m } \ {k}.
p
p
ˆ
3. In linia a doua, punem j l [k] = k s , i j [k] = j [k−1] , ∀q ∈ {1, 2, . . . , n} \ {l}.
q
q
4. Elementele din linia care cont , ine pivotul se ˆımpart la pivot:
[k−1] [k−1]
a b
[k] kq [k] k
a kq = [k−1] , ∀q ∈ 1, n, b k = [k−1] .
a a
kl kl
[k]
Evident a = 1.
kl
[k]
5. Celelalte elemente din coloana x l , ˆın care se afl˘a pivotul, vor fi egale cu 0, a pl = 0,
0
∀p ∈ {1, 2, . . . , m } \ {k}.
6. Toate elementele care nu au fost ˆınlocuite ˆın etapele 2-5 se determin˘a folosind regula
dreptunghiului:
a
a [k−1] [k−1] − a [k−1] [k−1] a [k−1] [k−1]
a
a
pl
kq
pl
kl
pq
kq
a [k] = = a [k−1] − ,
pq [k−1] pq [k−1]
a kl a kl
0
∀p ∈ {1, 2, . . . , m } \ {k}, ∀q ∈ {1, 2, . . . , n} \ {l}.
◦
0
◦
7. Dac˘a k < m , cres , tem valoarea lui k cu 1 s , i relu˘am Pasul 2 , altfel trecem la Pasul 3 .
◦
Pasul 3 Recuperarea solut , iei. Sistemul este compatibil:
0
0
1. determinat, dac˘a m = n. Solut , ia este x l = b [m ] , 1 ≤ l ≤ n.
j [m 0 ]
l