Lineáris egyenletrendszerek Összeállította: dr. Leitold Adrien egyetemi docens
2008.09.08.
1
Leontieff-modellek
Leontieff-modellek: input-output modellek a gazdaság leírására legyen n féle, egymással összefüggésben lévő ágazat, amelyek mindegyike egy-egy jószágot termel; a saját jószágának termeléséhez minden ágazatnak szüksége van inputra legalább egy másik ágazat jószágából; minden ágazatnak az általa előállított jószágból ki kell elégítenie a többi ágazat igényeit és egy bizonyos külső igényt is (végső kereslet); Lin. egyenletrendszerek
/2
Leonteff-modellek (folyt.)
Adatok: aij: a j-edik jószág egységnyi mennyiségének előállításakor az i-edik jószágból felhasznált mennyiség; (i,j = 1, … ,n) input (vagy termelési) együtthatók bi:az i-edik jószág iránti külső igény; (i = 1, … ,n) végső kereslet Probléma: Mennyit termeljenek az egyes ágazatok az egyes jószágokból, hogy a többi ágazat igényét és a végső keresletet biztosítani tudják? Lin. egyenletrendszerek
/3
Leontieff-modellek (folyt.)
Legyen x1, … ,xn az egyes jószágokból előállított mennyiség. Feltesszük, hogy az input követelmények egyenesen arányosak a megtermelt outputokkal, azaz xj mennyiségű j-edik jószág előállításához az iedik jószágból felhasznált mennyiség: aij⋅xj. Ha az egyes jószágokból x1, … ,xn mennyiségeket állítunk elő, akkor ehhez az i-edik jószágból felhasznált összmennyiség: ai1⋅x1+ ai2⋅x2+…+ ain⋅xn Az i-edik jószágra vonatkozó kereslet és kínálat egyensúlya szerint: xi= ai1⋅x1+ ai2⋅x2+…+ ain⋅xn+bi Lin. egyenletrendszerek
/4
A Leontieff-rendszerek általános alakja
A teljes modell: x1= a11⋅x1+ a12⋅x2+…+ a1n⋅xn+b1 x2= a21⋅x1+ a22⋅x2+…+ a2n⋅xn+b2 ........ xn= an1⋅x1+ an2⋅x2+…+ ann⋅xn+bn Rendezve az egyenletrendszert: (1−a11)⋅x1 − a12⋅x2 − … − a1n⋅xn = b1 − a21⋅x1+(1− a22)⋅x2 − … − a2n⋅xn = b2 …… −an1⋅x1 − an2⋅x2 − … +(1− ann)⋅xn = bn Lin. egyenletrendszerek
/5
Leontieff-modellek (folyt.)
Megjegyzés: A fenti lineáris egyenletrendszer olyan (x1, … , xn) megoldása érdekel bennünket, ahol az xi értékek nemnegatívak.
Lin. egyenletrendszerek
/6
Lineáris egyenletrendszerek általános alakja
Általános (részletes) alak:
a11 ⋅ x1 + ... + a1n ⋅ xn = b1 a21 ⋅ x1 + ... + a2 n ⋅ xn = b2
m egyenlet n ismeretlen: x1, … ,xn
M am1 ⋅ x1 + ... + amn ⋅ xn = bm
Jelölések:
a1n a12 a11 a1 = M , a2 = M , ... , an = M , a a a m1 m2 mn
x1 b1 b = M , x = M x b m n Lin. egyenletrendszerek
/7
Lin. egyenletrendszerek általános alakja (folyt.)
Tömörebb alak:
a1 ⋅ x1 +a2 ⋅ x2 + ... +an ⋅ xn =b
Jelölés: a11 ... a1n M A= M a ... a mn m×n m1
együtthatómátrix
Tömör alak:
A⋅ x = b Lin. egyenletrendszerek
/8
Homogén és inhomogén egyenletrendszerek
Homogén egyenletrendszer: Az A⋅x = b lineáris egyenletrendszert homogénnek nevezzük, ha b = o. Inhomogén egyenletrendszer: Az A⋅x = b lineáris egyenletrendszert inhomogénnek nevezzük, ha b ≠ o. Megjegyzések: Az A⋅x = o homogén lineáris egyenletrendszer mindig megoldható, az x = o megoldásvektort triviális megoldásnak nevezzük. Az A⋅x = b lineáris egyenletrendszert konzisztensnek nevezzük, ha megoldható, inkonzisztensnek, ha nem oldható meg. Lin. egyenletrendszerek
/9
A megoldhatóság feltétele
1.
2.
Lineáris egyenletrendszerek megoldhatóságának szükséges és elégséges feltétele: Az A⋅x = b lin. egyenletrendszer megoldható ⇔ a b vektor előáll az A együtthatómátrix oszlopvektorainak lineáris kombinációjával. Az A⋅x = b lin. egyenletrendszer megoldható ⇔ r (A) = r ([A,b]), ahol [A,b] az egyenletrendszer kibővített mátrixa: a11 ... a1n [ A, b ] = M M a m1 ... amn
b1 M . bm m×( n +1 ) Lin. egyenletrendszerek
/10
Lin. egyenletrendszer megoldása
Lin. egyenletrendszer megoldása : Tegyük fel, hogy az A⋅x = b lin. egyenletrendszer megoldható, azaz r (A) = r ([A,b]) = k. Jelölje Bm×k az A együtthatómátrix k db lin. független oszlopvektorából felépülő mátrixot, továbbá Rm×(n-k) az A együtthatómátrix maradék n-k db oszlopvektorából felépülő mátrixot. A megfelelő indexű ismeretlenek alkossák az xB és xR vektorokat. Ekkor: B⋅xB+ R⋅xR = b Lin. egyenletrendszerek
/11
Lin. egyenletrendszer megoldása (folyt.) Mivel a B oszlopvektorai az A együtthatómátrix oszlopvektorainak egy maximális lin. független részhalmazát képezik, így az R oszlopvektorai és a b vektor előállnak a B oszlopvektorainak lineáris kombinációjával. Ezért van olyan D mátrix és d vektor, melyekre: R = B⋅D és b = B⋅d , ahol:
a D mátrix az R oszlopvektorainak a B oszlopvektoraira vonatkozó koordinátáit tartalmazza, a d vektor a b vektornak a B oszlopvektoraira vonatkozó koordinátáit tartalmazza.
Így: B⋅xB+ B⋅D⋅xR = B⋅d, ebből: B(xB+ D⋅xR− d) = o . Lin. egyenletrendszerek
/12
Lin. egyenletrendszer „megoldó képlete” Innen, mivel B oszlopvektorai lin. függetlenek: xB+ D⋅xR− d = o , azaz: xB = d − D⋅xR
„megoldó képlet”
xB: a kötött ismeretlenek vektora xR: a szabad ismeretlenek vektora
A szabad ismeretlenek számát az egyenletrendszer szabadsági fokának hívjuk.
Lin. egyenletrendszerek
/13
Megoldásvektorok száma
1.
2.
Homogén lin. egyenletrendszer megoldásvektorainak számára vonatkozó állítások: Az A⋅x = o homogén lin. egyenletrendszernek csak triviális megoldása van ⇔ r(A) = n, ahol n az ismeretlenek száma. Az A⋅x = o homogén lin. egyenletrendszernek van triviálistól különböző megoldása is ⇔ r(A) < n, ahol n az ismeretlenek száma. Megjegyzés: ebben az esetben az egyenletrendszernek végtelen sok megoldásvektora van.
Lin. egyenletrendszerek
/14
Homogén-inhomogén egyenletrendszer-pár
Homogén-inhomogén egyenletrendszer megoldáshalmazai közötti kapcsolat: Tekintsük az A⋅x = o és A⋅x = b homogén-inhomogén egyenletrendszer-párt. Jelölje M0 a homogén egyenletrendszer megoldáshalmazát, M az inhomogén egyenletrendszer megoldáshalmazát, x0 az inhomogén egyenletrendszer egy rögzített megoldásvektorát. Ekkor: M = M0+{x0} . Lin. egyenletrendszerek
/15
Lineáris egyenletrendszerek: összefoglalás Homogén lin. e.r.
Inhomogén lin. e.r.
Am×n⋅x = o
Am×n⋅x = b
Nincs megoldás (Az e. r. nem oldható meg.)
-------
r(A) < r([A,b]) M=∅
1 db. megoldásvektor (Az e.r. egyértelműen megoldható.)
r(A) = n M0 = {o}
r(A) = r([A,b]) = n M = {x0}
Végtelen sok megoldásvektor
r(A) < n M0
r(A) = r([A,b]) < n M = M0+{x0}
Megoldásvektorok száma
Lin. egyenletrendszerek
/16
A Cramer-szabály Tekintsük az A⋅x = b lin. egyenletrendszert, ahol az A együtthatómátrix négyzetes: A = [a1 a2 … an]n×n . Legyen D = det(A), D1 = det([b a2 … an]), D2 = det([a1 b … an]), … Dn = det([a1 a2 … b]). Ekkor: D⋅xk = Dk , k = 1, … ,n . Lin. egyenletrendszerek
/17
A Cramer-szabály következményei Következmények: 1. Ha D≠0, akkor az egyenletrendszer egyértelműen megoldható és a megoldásvektor k-adik komponense: xk = Dk / D, k = 1, … ,n. 2. Ha D=0 és valamely k-ra Dk≠0, akkor az egyenletrendszer nem oldható meg. 3. Ha D=D1= … =Dn= 0 és r(A) = r([A,b]), akkor az egyenletrendszernek végtelen sok megoldásvektora van.
(Ebben az esetben a megoldásvektorok előállítására a Cramer-szabály nem alkalmas.) Lin. egyenletrendszerek
/18
A Cramer-szabály következményei (folyt.) 4. Az
A⋅x = o homogén lin. egyenletrendszernek
csak triviális megoldása van ⇔ D≠0 . 5. Az
A⋅x = o homogén lin. egyenletrendszernek
létezik triviálistól különböző megoldása is ⇔ D=0 . (Ebben az esetben az egyenletrendszernek végtelen sok megoldásvektora van, de ezeket a Cramer-szabállyal nem tudjuk előállítani.)
Lin. egyenletrendszerek
/19
