Mana personīgā lapa – šeit.

Adrese komentāriem: Karlis.Podnieks@lu.lv

Algebra:
Lineāru vienādojumu sistēmas

Kārlis Podnieks, LU profesors
Lekcijas

 This work is licensed under a Creative Commons License and is copyrighted © 2009-2011 by  me, Karlis Podnieks.

Literatūra

[1] E-kursa materiāli (latviešu valodā).

[2] A. G. Kurošs. Vispārīgās algebras kurss. Nauka, Maskava, 1971 (vai cita gada izdevums). Pieejama tiešsaistē šeit (krievu valodā).

[3] System of linear equationsWikipediaātram pārskatam, ja tēma jau zināma.

[4] WolframAlphaaprēķiniem tiešsaistē.

Divi vienādojumi ar diviem nezināmajiem

Visa tā lielā teorija, ko tūlīt studēsim, ir izaugusi no ļoti vienkārša uzdevuma.

Atcerēsimies skolas laiku:

2x+3y=5

2x−3y=1

Trīs metodes (var iznākt daļskaitļi):

a) Metode: jautājiet WolframAlpha:
{2x+3y=5, 2x
3y=1}
{x+2y+3z=1, 2x+2y+z=3, 3x+3y+5z=4}

b) "Izteikt x ar y": x=(5−3y)/2; (5−3y)−3y=1; 4=6y; y=2/3; x=3/2.

c) "Saskaitīt, lai pazūd": 4x=6; x=3/2; y=(2x−1)/3=2/3.

Bet kāda tam jēga?

Kāpēc to ir vērts zināt un prast?

1) "Optimizācijas uzdevums". Atrast skaitļus x, y ar vislielāko summu, kam izpildās divi nosacījumi:
2x+3y≤5;
2x−3y≤1. [Bilde ar taisnes x=y=C bīdīšanu.]
Uzdevuma atrisinājums būs punkts, kurā krustojas taisnes 2x+3y=5; 2x−2y=1, t.i. mūsu jau izpētītās vienādojumu sistēmas:
2x+3y=5;
2x−3y=1
atrisinājums.

Reālos optimizācijas uzdevumos mainīgo skaits ir lielāks – pat simtos un tūkstošos. Tad ir jārisina attiecīgi lielākas vienādojumu sistēmas.

2) "Dator-modelēšana". PKikusts.EXE – programma, kas modelē gāzes molekulu kustību. Kā tādu uzrakstīt?

Skats no augšas: objekts kustas pa taisnu līniju, priekšā ir siena, kurā punktā tas atsitīsies? Koordinātes, sienas vienādojums, objekta trajektorijas vienādojums, kā atrast krustpunktu?

Trīs situācijas

x+5y=1

x+5y=3

Nav neviena atrisinājuma. Kāpēc? Sauksim to par nesavietojamu (pretrunīgu, nekonsistentu) vienādojumu sistēmu.


2x+3y=5

2x−3y=1

Ir tikai viens atrisinājums: x=3/2; y=2/3. Sauksim to par savietojamu un noteiktu sistēmu.


3x−y=1

6x−2y=2

Bezgalīgi daudz atrisinājumu: x=t; y=3t−1. Kāpēc? Sauksim to par savietojamu un nenoteiktu sistēmu. Pavisam nenoteikta jau nu tā nav...

3 vienādojumi, 3 nezināmie

(a) x+2y+3z=1;
(b) 2x+2y+z=3;
(c) 3x+3y+5z=4.

Metode: jautājiet WolframAlpha:
{x+2y+3z=1, 2x+2y+z=3, 3x+3y+5z=4}

Metode "izteikt un ievietot"...

Metode "izdalīt, pareizināt un atņemt" – izslēdzam vispirms x, tad – y:

d) (b−2a) −2y−5z=1;
e) (c−3a) −3y−4z=1.

f) (d/2) y+(5/2)z= 1/2;
g)
(e+3f) (4+3*5/2)z= 13/2; jeb (7/2)z=1/2;
h)
(g/(7/2)) z=1/7;
y=
1/2(5/2)z=1/7;
x=1
2y3z=12/7.

To tad sauc arī par Gausa metodi jeb izslēgšanas metodi (Gaussian Elimination). Šo metodi ir visvieglāk vispārināt, t.i. piemērot 4- un vairāku vienādojumu sistēmām – un “iemācīt” datoram!

Carl Friedrich GaussWikipedia(1777-1855) – viens no visu laiku izcilākajiem matemātiķiem.

Droši vien, pats Kārlis Frīdrihs Gauss nemaz tik ļoti nepriecātos, uzzinot, ka viņam piedēvē tik vienkāršu metodi, kas pie tam ķīniešiem bija zināma jau 2. gs. pmē. (sk. Gaussian EliminationWikipedia)

Gausa metode:
uzlabotā tehnikā uz tāfeles

Risinot sistēmas ar lielāku nezināmo skaitu, vienādojumu pārrakstīšana kļūst apgrūtinoša. Taču bez tās var iztikt:

(a) x+2y+3z=1;
(b) 2x+2y+z=3;
(c) 3x+3y+5z=4.

1

2

3

1

2

2

1

3

3

3

5

4

> atņemam (b)−2(a) un (c)−3(a)

1

2

3

1

0

2

5

1

0

3

4

1

> dalām (b) ar −2

1

2

3

1

0

1

5/2

1/2

0

3

4

1

> piekaitām (c)+3(b)

1

2

3

1

0

1

5/2

1/2

0

0

7/2

1/2

> dalām (c) ar 7/2

1

2

3

1

0

1

5/2

1/2

0

0

1

1/7

Ievērojiet, ka iegūtā tabula ir “trīsstūrveida”. Esam ieguvuši ekvivalentu sistēmu:

x+2y+3z=1;
y+(5/2)z=
1/2;
z=
1/7,

no kuras viegli atrodam nezināmo vērtības:

z= 1/7;

y= 1/2(5/2)z = 1/7;
x=1
2y3z =12/7.

s vienādojumi, n nezināmie

Kā vispārīgā veidā pierakstīt s lineārus vienādojumus ar n nezināmajiem?

ax+by=c;
dx+ey=f.

Būs jāpierod pie jauniem apzīmējumiem:

a11x1+a12x2=b1;
a21x1+a22x2=b2.

Lasām "a viens viens", nevis

"a vienpadsmit", utt.

a11x1+a12x2+a13x3=b1;
a21x1+a22x2+a23x3=b2;
a31x1+a32x2+a33x3=b3.

Daži no koeficientiem var būt nulles, piemēram:

a11x1+a12x2+a13x3=b1;
.......... a22x2+a23x3=b2;
.................... a33x3=b3.

Šeit a21=a31=a32=0.

Sekojot šiem paraugiem, uzrakstiet paši vispārīgu 4 vienādojumu sistēmu ar 4 nezināmajiem.

Tagad visvispārīgākais gadījums –
s vienādojumi, n nezināmie:

a11x1+a12x2+ ... + a1nxn=b1;
a21x1+a22x2+ ... + a2nxn=b2;
...
as1x1+as2x2+ ... + asnxn=bs.

Koeficients aij (i-tais vienādojums, j-ais koeficients pie xj). Brīvais loceklis bi.

Pie šiem apzīmējumiem būs jāpierod.

Gausa metode vispārīgajā gadījumā

Kā to izstāstīt? Un kā to noprogrammēt?

No piemēriem mēs jau zinām, ka Gausa metode ir veidota no šādiem elementāriem soļiem:

a) Izdalām vienādojuma abas puses ar kādu skaitli C (kas nav nulle).

b) No viena vienādojuma V1 atņemam otru V2, pareizinātu ar kādu skaitli D, un rezultātu V1D*V2 liekam V1 vietā.

Ko darīt, ja šajā operācijā rodas vienādojums 0=0? Tad operāciju b) nemaz neizpildām, bet vienādojumu V1 vienkārši atmetam. Kāpēc tā?

Ko darīt, ja šajā operācijā rodas vienādojums 0=2 vai tml.? Tad vienādojumi V1 un V2 nav savietojami, un tāpēc nav savietojama arī visa sistēma. Tad tālāk vairāk nekas nav jādara.

Dažos gadījumos nākas izmantot vēl divas vienkāršas operācijas:

c) Divus vienādojumus apmainīt vietām.

d) Divus nezināmos apmainīt vietām.

Piemērs:

0x+2y+3z=4,
2x+3y+4z=5,
3x+4y+5z=6.

Divi varianti: vai nu pārvietojam vienādojumus

2x+3y+4z=5,
0x+2y+3z=4,
3x+4y+5z=6,

vai arī pārvietojam nezināmos:

2y+0x+3z=4,
3y+2x+4z=5,
4y+3x+5z=6.

[Vienādojumu sistēmās visos vienādojumos nezināmos ir pieņemts sakārtot vienādā secībā.]

Ar operāciju c) un d) palīdzību mēs vienmēr varam panākt, ka sistēmas kreisajā augšējā stūrī ir nezināmais ar nenulles koeficientu. Tālāk, šim koeficientam arī lietosim operāciju a).

Vienādojumu skaits sistēmā operācijās a), b), c), d) nemainās vai samazinās.

Vienādojumu sistēmas atrisinājums sakārtota skaitļu virkne: (c1, c2, ..., cn), ko ieliekot (x1, x2, ..., xn) vietā, visi s vienādojumi izpildās.

Jēdziens par ekvivalentām vienādojumu sistēmām (abām der vai neder vieni un tie paši atrisinājumi).

Lemma. Ja lineāru vienādojumu sistēma S2 ir iegūta no sistēmas S1 ar operāciju a), b), c), d) palīdzību (jebkurā secībā, ar atkārtojumiem), tad abas sistēmas ir ekvivalentas.

Pierādījums. Matemātikas cienītājiem – pavisam viegls.

Trīsstūrveida un trapecveida sistēmas.

Piemērs trīsstūrveida sistēmai (visi diagonāles koeficienti ir 1, sistēmas pēdējā vienādojumā ir viens nezināmais):

x1+a12x2+a13x3=b1; ← a11=1;
.......... x2+a23x3=b2; ← a21=0; a22=1;
.................... x3=b3; ← a31=a32=0; a33=1.

x+2y+3z=7;
0x+y+2z=4;
0x+0y+z=3.

Trīsstūrveida sistēmai ir tieši viens atrisinājums, ko var ļoti viegli aprēķināt.

Piemērs trapecveida sistēmai (visi diagonāles koeficienti ir 1, bet sistēmas pēdējā vienādojumā ir vairāk par vienu nezināmo):

x1+a12x2+a13x3=b1; ← a11=1;
.......... x2+a23x3=b2; ← a21=0; a22=1.

Pat ja a23=0, tad x3 varam ņemt patvaļīgu vērtību, bet x2 var būt tikai viena vērtība b2. Tātad arī šai gadījumā sistēmai būs bezgalīgi daudz atrisinājumu.

x+2y+3z=7;
0x+y+2z=4.

Trapecveida sistēmai jebkura gadījumā ir bezgalīgi daudz atrisinājumu, ko var viegli aprēķināt.

Trīsstūrveida un trapecveida sistēmu apvienotā definīcija – ABĀM:

a) visiem i, j, ja i>j, tad koeficients aij=0;

b) kā arī visiem i: aii=1.

Kā Gausa metode darbojas vispārīgajā gadījumā?

Ja vajag, vienādojumus pārkārtojam: sākumā ar operācijām c) vai d) izbīdām kreisajā augšējā stūrī vienādojumu vai nezināmo xi, pie kura koeficients nav nulle.

Tad pirmajam vienādojumam izpildām operāciju a), lai koeficients pie xi kļūtu vienāds ar 1.

Tad vairākkārt izpildām operāciju b), izslēdzot xi no otrā, trešā utt. vienādojumiem. Pēc tam pirmo vienādojumu “atliekam malā”.

Tālāk, ja vajag, ar c), d) izbīdām diagonāles otrajā vietā vienādojumu vai nezināmo xj, pie kura koeficients nav nulle.

Utt.

Katrā tādā solī vienādojumu un nezināmo skaits samazinās par 1. Tā turpinām, līdz vienādojumi un/vai nezināmie izbeidzas, un operācijas a, b, c, d pielietot vair snav iespējams.

Kāds var būt Gausa metodes rezultāts?

Darbojoties ar Gausa metodi, darbu nobeidzot, ir iespējami tikai 3 varianti.

1.variants – beigās rodas trīsstūris:

...

..... x3 + 3x4 + 2x5 = 6;

............. x4 + 2x5 = 3;

...................... x5 = 2.

Un vairāk vienādojumu nav. Tad risinām "atpakaļ":
x
5=2; x4= 1; x4=5; utt.

Tātad saskaņā ar mūsu Lemmu, šai gadījumā sistēmai ir viens un tikai viens atrisinājums (savietojama un noteikta sistēma).

2.variants beigās rodas trapece.

...

.....x3 + 2x4 + x5 = 4

..............x4 +3x5 = 5

Un vairāk vienādojumu nav. Tad risinām "atpakaļ":
x5=t; x4=53t; utt.

Tātad saskaņā ar mūsu Lemmu, šai gadījumā sistēmai ir bezgalīgi daudz atrisinājumu (savietojama un nenoteikta sistēma). Kā izskatās nenoteiktas sistēmas atrisinājumu formulas vispārīgajā gadījumā?

3.variants – darbs beidzies (operācijas a, b, c, d pielietot vairs nav iespējams), bet aiz pēdējā iegūtā “normālā” vienādojuma (kam pirmā nezināmā koeficients ir 1) ir palikuši vēl viens vai vairāki vienādojumi.

Tad visi šie palikušie vienādojumi ir formā 0=b (ja kreisajā puse būtu palicis kaut viens nenulles koeficients, tad mēs to varētu apstrādāt ar operācijām c, d, a).

Ja visos palikušajos vienādojumos c=0, tad tos visus var atmest, un mēs nonākam pie 1. vai 2.varianta.

Ja kādā no palikušajiem vienādojumiem c0, tad tas ir neizpildāms vienādojums. Tad saskaņā ar mūsu Lemmu, šai gadījumā sistēmai nav neviena atrisinājuma (nesavietojama sistēma).

Piemērs: ...........0 = 2; ← neizpildāms.

Esam pierādījuši teorēmu:

Teorēma. Jebkuru savietojamu lineāru vienādojumu sistēmu ar Gausa metodes palīdzību var pārveidot ekvivalentā trīsstūrveida vai trapecveida sistēmā. Nesavietojamai sistēmai, Gausa metodes darba laikā parādās vienādojums 0=c, kur c0.

Vienādojumu skaits un nezināmo skaits

Secinājumi no Gausa metodes:

1) Ja s=n (vienādojumu ir tikpat cik nezināmo) tad ir iespējami visi varianti: sistēma vai nu ir nesavietojama, vai arī atrisinājumu skaits ir viens vai bezgalīgi daudz. Kāpēc?

2) Ja s<n (vienādojumu ir mazāk nekā nezināmo), tad sistēma nav noteikta. Tā vai nu ir nesavietojama, vai arī tai ir bezgalīgi daudz atrisinājumu. Kāpēc? Piemērs – 3 v. un 4 n.

3) Ja s>n (vienādojumu ir vairāk nekā nezināmo) tad tad tajā ir vismaz s−n atkarīgu vienādojumu! Kāpēc? Piemērs – 5 v. un 4 n. Ir iespējami visi varianti: sistēma vai nu ir nesavietojama, vai arī atrisinājumu skaits ir viens vai bezgalīgi daudz.

Homogenas sistēmas

Definīcija: visi brīvie locekļi ir nulles.

x+2y+3z=0;
2x+2y+z=0;
3x+3y+5z=0.

Nulles atrisinājums homogenai sistēmai der vienmēr: (0, 0, 0), t.i. tās vienmēr ir savietojamas.

Ja lietojam Gausa metodi, kas var iznākt? Trīsstūris (tad der tikai nulles atrisinājums) vai trapece (tad sistēmai ir arī bezgalīgi daudz nenulles atrisinājumu). Kāpēc?

Datoriķiem: Gausa metodei
nepieciešamais programmas darbības laiks

Sk. Gaussian EliminationWikipedia.

Ja n lineāru vienādojumu sistēmu ar n nezināmajiem risina ar Gausa metodi, tad pavisam iznāk izpildīt aptuveni n2 dalīšanas operāciju, aptuveni n3 reizināšanas un aptuveni n3 atņemšanas operāciju.

Uzdevums. Saskaitiet precīzāk operācijas, kas jāizpilda, risinot s vienādojumu sistēmu ar n nezināmajiem. Jāiegūst formula

Tas nozīmē, ka izmantojot datorus, ar Gausa metodi var sekmīgi risināt sistēmas, kurās ir līdz tūkstotim vienādojumu un nezināmo.

Bet ja vienādojumu skaits sniedzas miljonos, tad būs jāizmanto citas metodes. Par tām sk. to pašu Gaussian EliminationWikipedia.

Datoriķiem: vēl viena problēma...

Gaussian EliminationWikipedia te varat izlasīt par vēl vienu problēmu: Gausa metodē atņemšanas operācijas mijas ar dalīšanām.

Piemērs:

x+y=1;
x+1,001y=2;

Atņemot:

0,001y=1;
y=1000.

Ja 1,001 būtu radies noapaļošanas rezultātā, t.i. īstenībā tur ir skaitlis no 1,0005 līdz 1,0015, tad īstā y vērtība ir robežās no 666 līdz 2000.

Ja atņemšanas rezultātā rodas ļoti mazs skaitlis, ar kuru pēc tam ir jādala, tad tas stipri palielina rēķināšanas kļūdas. Tāpēc praktiskai lietošanai Gausa metodi vajag vēl vairāk pilnveidot... Kā?