Klasyczna Metoda Eliminacji Gaussa -Jordana nazywana też Naiwną Metodą Eliminacji Gaussa -Jordana wymaga, aby elementy główne
\(\displaystyle{ a^{(k)}_{kk}, \ \ k=1,3,...,n }\) w każdym kroku eliminacji były różne od zera.
Ponadto jeśli wartości mnożników wierszowych \(\displaystyle{ m_{ik} = \frac{a^{(k)}_{ik}}{a^{(k)}_{kk}} }\) są duże, to podczas obliczeń kumulują się
wielkie błędy zaokrągleń.
Stąd konieczna jest modyfikacja tej metody - polegająca na wyborze wiersza głównego w każdym kroku eliminacji i skalowaniu , aby unknąć
narastania błędów obliczeń.
Jaki jest algorytm tej metody ?
Załóżmy, że mamy do rozwiązania układ równań liniowych:
\(\displaystyle{ \left[ \begin{matrix} 1 & 3 & -2 & 4\\ 2 & -3 & 3 & -1\\ -1 & 7 & -4 & 2\\ 3 & -1 & 6 & 2 \end{matrix}\right] \cdot \left[ \begin{matrix} x_{1}\\x_{2}\\x_{3}\\x_{4} \end{matrix} \right] = \left[\begin{matrix} -11\\ 6 \\ -9 \\ 15 \end{matrix} \right].}\)
Na początku przyjmujemy wektor kolejnych indeksów \(\displaystyle{ \vec{d}=[ 1, 2, 3, 4] }\) i wektor skalowany \(\displaystyle{ \vec{c}=[c_{1}, c_{2}, c_{3}, c_{4}] }\)
gdzie:
\(\displaystyle{ c_{i} = \max_{1\leq j \leq 4} |a_{ij}|, \ \ i = 1,2,3,4. }\)
W naszym przykładzie \(\displaystyle{ \vec{c} = [4, 3, 7, 6]. }\)
Następnie definiujemy wektor proprcji:
\(\displaystyle{ \vec{r} = [r_{1}, r_{2}, r_{3}, r_{4} ] }\)
gdzie:
\(\displaystyle{ r_{i} = \frac{|a_{i1}|}{c_{i}}, \ \ i = 1,2,3,4.}\)
W naszym przykładzie \(\displaystyle{ \vec{r} = \left[ \frac{1}{4}, \frac{2}{3}, \frac{1}{7}, \frac{1}{2} \right]. }\)
Wybieramy element największy wektora \(\displaystyle{ \vec{r}. }\) W naszym przykładzie jest to \(\displaystyle{ \frac{2}{3} }\)
Zmieniamy element \(\displaystyle{ 1 }\) z elementem \(\displaystyle{ 2 }\) w wektorze indeksów, otrzymując
Krok 1
\(\displaystyle{ \vec{d} = [2, 1, 3, 4] }\). To oznacza, że wiersz \(\displaystyle{ 2 }\) jest wierszem głównym, za pomocą jego tworzymy zera w pierwszej
kolumnie macierzy układu, stosując eliminację Gaussa-Jordana:
\(\displaystyle{ \left[ \begin{matrix} 0 & \frac{9}{2} & -\frac{7}{2} & \frac{9}{2}\\ 2 & -3 & 3 & -1\\ -0 & \frac{11}{2} & -\frac{5}{2} & \frac{3}{2}\\ 0 & \frac{7}{2} & \frac{3}{2} & \frac{7}{2} \end{matrix}\right] \cdot \left[ \begin{matrix} x_{1}\\x_{2}\\x_{3}\\x_{4} \end{matrix} \right] = \left[\begin{matrix} -14\\ 6 \\ -6 \\ 6 \end{matrix} \right].}\)
Kontynuujemy ten proces
Krok 2
\(\displaystyle{ \vec{r} = \left[ \frac{9}{8}, \frac{11}{14}, \frac{7}{12} \right] }\)
Pierwszy element \(\displaystyle{ \frac{9}{8} }\) jest elementem największym w \(\displaystyle{ \vec{r} }\) - co oznacza , że wektor indeksów \(\displaystyle{
\vec{d} = [2, 1, 3, 4] }\) pozostaje bez zmiany i wiersz pierwszy jest wierszem głównym.
Stosujemy eliminację Gaussa-Jordana - tworząc zera w drugiej kolumnie macierzy:
\(\displaystyle{ \left[ \begin{matrix} 0 & \frac{9}{2} & -\frac{7}{2} & \frac{9}{2}\\ 2 & -3 & 3 & -1\\ 0 & 0 & \frac{16}{9} & -4 \\ 0 & 0 & \frac{38}{9} & 0 \end{matrix}\right] \cdot \left[ \begin{matrix} x_{1}\\x_{2}\\x_{3}\\x_{4} \end{matrix} \right] = \left[\begin{matrix} -14\\ 6 \\ \frac{100}{9} \\ \frac{152}{9} \end{matrix} \right].}\)
Krok 3
\(\displaystyle{ \vec{r} = \left[\frac{16}{63}, \frac{38}{54}\right] }\)
\(\displaystyle{ \frac{38}{54}> \frac{16}{63} }\) - zmieniamy wiersz \(\displaystyle{ 3 }\) z \(\displaystyle{ 4.}\)
Nowy wektor indeksów: \(\displaystyle{ \vec{d} = [2, 1, 4, 3].}\)
Oznacza to, że wiersz \(\displaystyle{ 4 }\) jest wierszem głównym:
\(\displaystyle{ \left[ \begin{matrix} 0 & \frac{9}{2} & -\frac{7}{2} & \frac{9}{2}\\ 2 & -3 & 3 & -1\\ 0 & 0 & 0 & -4 \\ 0 & 0 & \frac{38}{9} & 0 \end{matrix}\right] \cdot \left[ \begin{matrix} x_{1}\\x_{2}\\x_{3}\\x_{4} \end{matrix} \right] = \left[\begin{matrix} -14\\ 6 \\ 4 \\ \frac{152}{9} \end{matrix} \right].}\)
Na koniec stosujemy podstawienia wstecz, otrzymując rozwiązanie układu równań:
\(\displaystyle{ x_{4}= \frac{4}{-4}= -1, }\)
\(\displaystyle{ x_{3}=\frac{1}{\frac{38}{9}}\cdot \frac{152}{9} = 4,}\)
\(\displaystyle{ x_{2} = \frac{1}{\frac{9}{2}}\cdot \left[ -14 + 4\cdot \frac{7}{2} -1\cdot \left(-\frac{9}{2} \right) \right] = 1, }\)
\(\displaystyle{ x_{1}= \frac{1}{\frac{1}{2}} \cdot\left[ 6 + 3-12 -1\right] = -2.}\)
Program w OCTAVE
Kod: Zaznacz cały
function gaussel(A,b)
n=length(b);
x=zeros(n,1);
fprintf('\n')
disp('Macierz rozszerzona =')
augm=[A,b]
for i=1:n
d(i)=i;
smax=0;
for j=1:n
smax=max(smax,abs(A(i,j)));
end
c(i)=smax;
end
for k=1:n-1
max=0;
for i=k:n
R=abs(A(d(i),k))/c(d(i));
if (R>max)
j=i;
max=R;
end
end
dk=d(j);
d(j)=d(k);
d(k)=dk;
for i=k+1:n
m=A(d(i),k)/A(dk,k);
for j=k+1:n
A(d(i),j)= A(d(i),j)-m* A(dk,j);
end
A(d(i),k)=m;
end
end
for k=1:n-1
for i=k+1:n
b(d(i))=b(d(i))-b(d(k))*A(d(i),k);
end
end
x(n)=b(d(n))/A(d(n),n);
for i=n-1:-1:1
S=b(d(i));
for j=i+1:n
S=S-A(d(i),j)*x(j);
end
x(i)=S/A(d(i),i);
end
disp('Wektor skalujący =')
c
disp('Wektor indeksów =')
d
fprintf('Macierz trókątna górna C =')
fprintf('\n')
for i=1:n
M(i,:)=A(d(i),:);
end
for i=1:n
for j=1:n
if(j<i) M(i,j)=0;end
end
end
C=[M,b]
fprintf('\n')
disp('Wektor rozwiązań=')
x
>> A=[1 3 -2 4;2 -3 3 -1;-1 7 -4 2;3 -1 6 2];
>> b=[-11 6 -9 15]';
>> gaussel(A,b)
Macierz rozszerzona =
augm =
1 3 -2 4 -11
2 -3 3 -1 6
-1 7 -4 2 -9
3 -1 6 2 15
Wektor skalujący =
c =
4 3 7 6
Wektor indeksów =
d =
2 1 4 3
Macierz trókątna górna C =
C =
2.0000 -3.0000 3.0000 -1.0000 -14.0000
0 4.5000 -3.5000 4.5000 6.0000
0 0 4.2222 0 4.0000
0 0 0 -4.0000 16.8889
Wektor rozwiązań=
x =
-2
1
4
-1
Rozwiążemy, jeszcze jeden układ równań
\(\displaystyle{ \begin{cases} 0,0002 x_{1} + 1,471x_{2} = 1,473\\ 0,2346 x_{1}-1,317x_{2} = 1,029, \end{cases} }\)
który dla Klasycznej Metody Eliminacji Gaussa-Jordana jest układem źle uwarunkowanym.
Kod: Zaznacz cały
>> A=[0.0002 1.471;0.2346 -1.317];
>> b=[1.473 1.029]';
>> gaussel(A,b)
Macierz rozszerzona =
augm =
2.0000e-04 1.4710e+00 1.4730e+00
2.3460e-01 -1.3170e+00 1.0290e+00
Wektor skalujący =
c =
1.4710 1.3170
Wektor indeksów =
d = 2 1
Macierz trókątna górna C =
C =
0.2346 -1.3170 1.4721
0 1.4721 1.0290
Wektor rozwiązań=
x =
10
1