Predavanje MatR.9: Linearni sistemi. Gauß-Jordanova eliminacija

Linearni sistem lahko krajše zapišemo kot Ax=b, kjer je A\in M_{m\times n}(\mathbb R), x\in\mathbb R^n in b\in\mathbb R^m. Razširjena matrika linearnega sistema je [A \mid b]= [A^{(1)}\; A^{(2)} \; \cdots A^{(n)} \; b].

Zgled: Oglejmo si ponovno zgled od prejsnjic. \begin{bmatrix} 3 & 1 & -1 & | & 8 \\ 1 & -1 & 1 & | & 4 \\ 1 & 1 & -1 & | & 2\end{bmatrix}\sim\begin{bmatrix}1 & -1 & 1 & | & 4 \\ 1 & 1 & -1 & | & 2\\ 3 & 1 & -1 & | & 8\end{bmatrix} \sim \begin{bmatrix}1 & -1 & 1 & | & 4 \\ 0 & 2 & -2 &|& -2 \\ 0 & 4 & -4 & | & -4\end{bmatrix}\sim\begin{bmatrix}1 & -1 & 1 & | & 4 \\ 0 & 1 & -1 &|& -1\end{bmatrix}\sim\begin{bmatrix}1 & 0 & 0 & | & 3 \\ 0 & 1 & -1 &|& -1\end{bmatrix}. To je linearni sistem \begin{bmatrix} 1 & 0 & 0 & | & 3 \\ 0 & 1 & -1 &|& -1\end{bmatrix}\cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix} 3 \\ -1\end{bmatrix}. Njegova resitev je torej x_1=3, x_2-x_3=-1.

Posluzevali smo se 3 t.i. elementarnih vrsticnih operacij:

  1. i-to vrstico matrike pomnozimo z nenicelnim skalarjem;
  2. i-to vrstico matrike pomnozeno z nenicelnim skalarjem pristejemo j-ti vrstici;
  3. zamenjamo i-ti in j-to vrstico.

Pri resevanu linearnih sistemov studiramo matrike. Prikazanemu postopku pravimo Gauß-Jordanova eliminacija. Matrika, ki jo dobimo na koncu, pa je vrsticno kanonicna forma (VKF).

III.2. Elementarne matrike

Definicija: Naj bo A=\begin{bmatrix} A_{(1)} \\ \vdots \\ A_{(m)}\end{bmatrix}\in M_{m\times n}(\mathbb R). Trije osnovni tipi elementarnih vrsticnih operacij na A so:

  1. \begin{bmatrix} A_{(1)} \\ \vdots\\ A_{(i)} \\ \vdots \\ A_{(m)}\end{bmatrix} \to \begin{bmatrix} A_{(1)} \\ \vdots\\ \lambda A_{(i)} \\ \vdots \\ A_{(m)}\end{bmatrix};
  2. \begin{bmatrix} A_{(1)} \\ \vdots\\ A_{(i)} \\ \vdots \\ A_{(j)} \\ \vdots \\ A_{(m)}\end{bmatrix} \to \begin{bmatrix}A_{(1)} \\ \vdots\\ A_{(i)} \\ \vdots \\ A_{(j)}+\lambda A_{(i)} \\ \vdots \\ A_{(m)}\end{bmatrix};
  3. \begin{bmatrix} A_{(1)} \\ \vdots\\ A_{(i)} \\ \vdots \\ A_{(j)} \\ \vdots \\ A_{(m)}\end{bmatrix} \to \begin{bmatrix}A_{(1)} \\ \vdots\\ A_{(j)} \\ \vdots \\ A_{(i)} \\ \vdots \\ A_{(m)}\end{bmatrix}.

Kaj se zgodi, ko te tipe uporabimo na identicni matriki?

  1. I \to E_i(\lambda) = \begin{bmatrix} 1 \\ & \ddots \\ & & \lambda \\ & & & \ddots \\ & & & & 1\end{bmatrix}=E_{11}+E_{22}+\cdots+\lambda E_{ii}+\cdots+E_{mm};
  2. I\to E_{ij}(\lambda)=I + \lambda E_{ji};
  3. I\to P_{ij}=I-E_{ii}-E_{jj}+E_{ij}+E_{ji}.

Elementarne vrsticne operacije na matrikah je dejansko mnozenje s temi elementarnimi matrikami z leve strani.

Trditev: Elementarne matrike so obrnljive.

Izrek: Dan je linearni sistem Ax=b, kjer je A\in M_{m\times n}(\mathbb R), x\in\mathbb R^n in b\in\mathbb R^m. Naj bo P\in M_m(\mathbb R) obrnljiva matrika in A'=PA, b'=Pb. Tedaj imata linearna sistema Ax=b in A'x=b' enako mnozico resitev.

Sistema, ki imata enako mnozico resitev, sta ekvivalentna.

Posledica: Naj bo \begin{bmatrix} A & | & b\end{bmatrix} razsirjena matrika sistema Ax=b. Ce matriko \begin{bmatrix} A' & | & b'\end{bmatrix} dobimo iz \begin{bmatrix} A & | & b\end{bmatrix} s pomocjo elementarnih vrsticnih operacij, potem sta sistema Ax=b in A'x=b' ekvivalentna.

Vsako matriko A lahko s pomocjo elementarnih vrsticnih operacij preoblikujemo v naslednjo obliko, ki ji recemo vrsticna kanonicna forma:

  • v vsaki nenicelni vrstici je prvi nenicelni element z leve enak 1;
  • ce je i-ta vrstica nicelna, potem so vse naslednje vrstice nicelne;
  • prvi nenicelni element z leve v (i+1)-ti vrstici je bolj desno kot prvi nenicelni element v i-ti vrstici;
  • ce je v j-tem stolpcu kak prvi nenicelni element neke vrstice, potem je to v j-tem stolpcu edini nenicelni element.

Vsak prvi nenicelni element vrstice v VKF imenujemo pivot.

Algoritem za iskanje VKF (Gauß-Jordanova eliminacija): postavi i=1, j=1.

Korak 1:

  • ce je v j-tem stolpcu kak element v vrsticah i+1,i+2,\ldots,m neniceln in je a_{ij}=0, zamenjaj i-to vrstico s k-to vrstico, da bo novi a_{ij}\neq 0;
  • pomnozi i-to vrstico z \frac 1{a_{ij}}, da bo novi element (pivot) enak a_{ij}=1;
  • pristej i-to vrstico pomnozeno z -a_{kj} h k-ti vrstici, da bo a_{kj}=0 za vsak k=i+1,i+2,\ldots, m.

Postavi i\to i+1 (premakni se v novo vrstico in doloci nov j) ter ponovi korak 1.

Korak 2:

  • vrstice s pivotom pristej k predhodnim vrsticam, da bo pivot edini nenicelni element v svojem stolpcu.
This entry was posted in Matrični račun (FNM), Pedagoško delo, Slovenščina. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s