METODY OBLICZENIOWE INFORMATYKI  LABORATORIUM
materiały pomocnicze
Ćwiczenie 3
Rozwiązywanie układów równań liniowych.
UKA
ADY RÓWNAC
LINIOWYCH
Układ m równań liniowych o n niewiadomych ma postać:
a11x1 + a12 x2 + ... + a1n xn = b1
Å„Å‚
ôÅ‚a x1 + a22 x2 + ... + a2n xn = b2
ôÅ‚
21
òÅ‚............................................
ôÅ‚
ôÅ‚am1x1 + am2 x2 + ... + amn xn = bm
ół
Powyższy układ może też zostać zapisany w równoważnej postaci macierzowej:
A Å" X = B
Macierz A nazywana jest macierzą współczynników:
a11 a12 ... a1n
îÅ‚ Å‚Å‚
ïÅ‚a a22 ... a2n śł
21
ïÅ‚ śł
A =
ïÅ‚ śł
... ... ... ...
ïÅ‚a am2 ... amn śł
ðÅ‚ m1 ûÅ‚
Macierz X  macierzÄ… niewiadomych (wektorem niewiadomych):
x1
îÅ‚ Å‚Å‚
ïÅ‚x śł
2
ïÅ‚ śł
X =
ïÅ‚ śł
...
ïÅ‚x śł
ðÅ‚ n ûÅ‚
Macierz B  macierzą wyrazów wolnych (wektorem wyrazów wolnych):
b1
îÅ‚ Å‚Å‚
ïÅ‚b śł
2
ïÅ‚ śł
B =
ïÅ‚ śł
...
ïÅ‚b śł
ðÅ‚ m ûÅ‚
UKA
AD N RÓWNAC
LINIOWYCH O N NIEWIADOMYCH
Najprostszym przypadkiem powyższego układu równań jest układ n równań liniowych o n
niewiadomych ( m = n ). Wówczas liczba równań jest zgodna z liczbą niewiadomych. Macierz
współczynników jest macierzą kwadratową stopnia równego liczbie niewiadomych.
a11x1 + a12 x2 + ... + a1n xn = b1
Å„Å‚
ôÅ‚a x1 + a22 x2 + ... + a2n xn = b2
ôÅ‚
21
òÅ‚............................................
ôÅ‚
ôÅ‚an1x1 + an2 x2 + ... + ann xn = bn
ół
a11 a12 ... a1n
îÅ‚ Å‚Å‚
ïÅ‚a a22 ... a2n śł
21
ïÅ‚ śł
A =
ïÅ‚ śł
... ... ... ...
ïÅ‚a an2 ... ann śł
ðÅ‚ n1 ûÅ‚
x1
îÅ‚ Å‚Å‚
ïÅ‚x śł
2
ïÅ‚ śł
X =
ïÅ‚ śł
...
ïÅ‚x śł
ðÅ‚ n ûÅ‚
b1
îÅ‚ Å‚Å‚
ïÅ‚b śł
2
ïÅ‚ śł
B =
ïÅ‚ śł
...
ïÅ‚b śł
ðÅ‚ n ûÅ‚
Zgodnie z twierdzeniem Cramera układ n równań liniowych o n niewiadomych posiada dokładnie
jedno rozwiązanie, gdy wyznacznik det A macierzy współczynników jest różny od zera (macierz
współczynników jest macierzą nieosobliwą). Rozwiązanie to jest określone wzorami:
det A1
x1 =
det A
det A2
x2 =
det A
...
det An
xn =
det A
gdzie det A , j = 1,2,..., n , sÄ… wyznacznikami macierzy uzyskanymi z macierzy A przez zastÄ…pienie
j
w niej j-tej kolumny kolumną wyrazów wolnych.
ROZWI
ZYWANIE UKA
ADU N RÓWNAC
LINIOWYCH O N NIEWIADOMYCH
METOD
ELIMINACJI GAUSSA
Najczęściej stosowaną metodą numerycznego rozwiązywania układów równań liniowych jest
metoda eliminacji Gaussa. Rozwiązywanie układu tą metodą przebiega w dwóch etapach: najpierw
układ równań sprowadzany jest do postaci trójkątnej:
a11x1 + a12 x2 + ... + a1n xn = b1
Å„Å‚
ôÅ‚
a22 x2 + ... + a2n xn = b2
ôÅ‚
òÅ‚
...........................
ôÅ‚
ôÅ‚
ann xn = bn
ół
a następnie niewiadome wyznaczane są ze wzorów:
bn
xn =
ann
bi - ain xn - ... - aii+1xi+1
xi =
aii
gdzie: i = n -1, n - 2,...,1.
Etap pierwszy nazywany jest etapem eliminacji zmiennych.
Dany jest układ równań liniowych:
(1 (1 ( (
Å„Å‚
a11) x1 + a12) x2 + ... + a11) xn = b11)
n
ôÅ‚
(1 (1 ( (
a21) x1 + a22) x2 + ... + a21) xn = b21)
ôÅ‚
n
òÅ‚
ôÅ‚............................................
(1) ( (1 (
ôÅ‚a x1 + an1) x2 + ... + ann) xn = bn1)
ół n1 2
Odejmując od i-tego wiersza układu (i = 2,3,..., n ) wiersz pierwszy pomnożony przez:
ai(1)
1
(1
a11)
otrzymuje się układ:
(2) (2) (2)
Å„Å‚
a11 x1 + a12 x2 + ... + a1n xn = b1(2)
ôÅ‚
(2 ( (
a22) x2 + ... + a22) xn = b22)
ôÅ‚
n
òÅ‚
.....................................
ôÅ‚
( (2 (
ôÅ‚
an2) x2 + ... + ann) xn = bn2)
ół 2
Wyeliminowana została w ten sposób pierwsza niewiadoma x1 z równań leżących w wierszach
o numerach i = 2,3,..., n . Podobnie eliminuje się niewiadomą x2 z równań leżących w wierszach
o numerach i = 3,4,..., n , odejmując od i-tego wiersza (i = 3,4,..., n ) wiersz drugi pomnożony przez:
ai(2)
2
.
(2
a22)
Postępując dalej w analogiczny sposób otrzymuje się przekształcone układy równań:
A(3) Å" X = B(3) ,
A(4) Å" X = B(4) ,
...
i po ( n -1) eliminacjach uzyskuje się trójkątny układ równań:
A(n) Å" X = B(n)
o postaci:
(n) (n) (n) (n)
Å„Å‚
a11 x1 + a12 x2 + ... + a1n xn = b1
ôÅ‚
(n ( (
a22) x2 + ... + a2n) xn = b2n)
ôÅ‚
n
òÅ‚
..........................
ôÅ‚
(n (
ôÅ‚
ann) xn = bn2)
ół
Etap drugi nazywany jest postępowaniem odwrotnym. Otrzymany po przekształceniu układ równań
rozwiązuje się zgodnie z podanymi wcześniej wzorami.
Podstawowa postać metody Gaussa nie jest niezawodna. Przyjmując za elementy podstawowe
(k
w macierzach A(k ) , k = 1,2,..., n elementy leżące na przekątnej diagonalnej - akk ) , może okazać się,
że któryś z tych elementów będzie równy zero, przez co nie jest możliwa dalsza eliminacja
zmiennych (element podstawowy jest to element macierzy A, za pomocą którego eliminuje się
zmienną z dalszych równań). Dlatego też stosuje się pewną modyfikację metody eliminacji Gaussa,
zwaną częściowym wyborem elementu podstawowego. Stosując tą modyfikację wybiera się
z elementów k-tej kolumny w k-tej macierzy ten element, który ma największy moduł. Przez
zmianę kolejności wierszy w macierzy można uzyskać element podstawowy leżący na przekątnej
diagonalnej macierzy.
ROZWI
ZYWANIE UKA
ADÓW RÓWNAC
LINIOWYCH W ÅšRODOWISKU MATLAB
Zalecanym sposobem rozwiÄ…zywania ukÅ‚adu równaÅ„ o postaci A Å" X = B w Å›rodowisku MATLAB
jest użycie operatora \ lewostronnego dzielenia macierzy. Poszukiwany wektor X uzyskuje się jako
wynik dzielenia: X = A \ B . Dla ukÅ‚adu równaÅ„ o postaci X Å" A = B należy zastosować operator /
prawostronnego dzielenia macierzy: X = A / B .
IMPLEMENTACJA METODY ELIMINACJI GAUSSA W J
ZYKU C++
class Wektor
{
double *wektor;
int liczbaelementow;
...
}
class Macierz
{
Wektor **macierz;
int liczbawierszy;
int liczbakolumn;
...
}
Mając zdefiniowane klasy: Macierz oraz Wektor oraz przyjmując, że A jest obiektem klasy Macierz
(macierz współczynników), B jest obiektem klasy Wektor (wektor wyrazów wolnych) oraz X jest
obiektem klasy Wektor (wektor niewiadomych) procedura wykonujÄ…ca eliminacjÄ™ zmiennych ma
postać:
for(i=0; i {
wsp=0.0;
for(j=i+1; j {
wsp=(*A.macierz[j])[i]/(*A.macierz[i])[i];
(*A.macierz[j])=(*A.macierz[j])-(*A.macierz[i])*wsp;
B[j]=B[j]-B[i]*wsp;
}
}
Obliczanie niewiadomych przebiega w następujący sposób:
for(i=a.liczbawierszy-1; i>-1; i--)
{
s=0.0;
for(j=a.liczbawierszy-1; j>i-1; j--)
{
x[i]=0;
s=s+(*a.macierz[i])[j]*x[j];
}
x[i]=(b[i]-s)/(*a.macierz[i])[i];
}
FUNKCJE ÅšRODOWISKA MATLAB WYKONUJ
CE OPERACJE NA MACIERZACH
Funkcja Parametry Działanie
rank(A)
A  macierz Obliczanie rzÄ…du macierzy
det(A)
A  macierz kwadratowa Obliczanie wyznacznika
macierzy kwadratowej
lu(A)
A - macierz Wyznaczanie macierzy L
i U takich, że L * U = A
inv(A)
A  macierz Wyznaczanie odwrotności
macierzy
size(A)
A  macierz Wyznaczanie rozmiaru
macierzy (liczby wierszy
oraz liczby kolumn)
ZADANIA
Zad.1.
Napisz program w wybranym języku programowania służący do rozwiązywania układów równań
liniowych metodÄ… eliminacji Gaussa.
Zad. 2.
Napisz skrypt dla środowiska MATLAB służący do rozwiązania metodą Cramera następujących
układów równań:
x1 + 2x2 + 3x3 + 4x4 = 11
Å„Å‚
ôÅ‚2x + 3x2 + 4x3 + x4 = 12
ôÅ‚
1
a)
òÅ‚3x + 4x2 + x3 + 2x4 = 13
1
ôÅ‚
ôÅ‚4x1 + x2 + 2x3 + 3x4 = 14
ół
2x1
Å„Å‚ - x2 + x3 - x4 = 1
ôÅ‚2x - x2 - 3x4 = 2
ôÅ‚
1
b)
òÅ‚3x - x3 + x4 = -3
1
ôÅ‚
ôÅ‚2x1 + 2x2 - 2x3 + 5x4 = -6
ół
Zad. 3.
Wykorzystując środowisko MATLAB rozwiąż następujące układy równań liniowych:
2x1 + 2x2 - x3 + x4 = 7
Å„Å‚
ôÅ‚x - x2 + x3 - x4 = -2
ôÅ‚
1
a)
òÅ‚x + x2 + x3 + x4 = 10
1
ôÅ‚
ôÅ‚4x1 + 3x2 - 2x3 - x4 = 0
ół
3a + b + c + 2d = 3
Å„Å‚
ôÅ‚3a + 2b + 3c + 5d = 0
ôÅ‚
b)
òÅ‚6a + 5b + c + 5d = -2
ôÅ‚
ôÅ‚3a + 2b + 3c + 7d = -2
ół