0.1
0.1.1
Numerické riešenie systémov lineárnych rovníc
Úvod
Sústavou n lineárnych rovníc o n neznámych (a tými sa budeme výhradne za,
oberat) rozumieme systém
a11 x1 + a12 x2 + : : : + a1n xn
=
b1 ;
a21 x1 + a22 x2 + : : : + a2n xn
=
b2 ;
an1 x1 + an2 x2 + : : : + ann xn
=
(1)
:::
bn :
,
Systém môµzeme reprezentovat maticovou rovnicou
Ax = b;
(2)
n
faij gij=1
kde A =
je matica sústavy, x je vektor neznámych a b je st´lpcový
vektor pravých strán.
De…nícia 1 Vektor x0 sa nazýva riešenie systému (??), práve vtedy, ak vyhovuje maticovej rovnici (2), tj. platí
Ax0 = b:
Poznámka 1 Z predošlých kurzov lineárnej algebry je nám známe, µze existuje
práve jedno riešenie x0 systému (??), a to iba v prípade µze, existuje inverzná
matica A 1 ku matici systému A; a tá existuje iba vtedy ak je matica A regulár,
na, tj. det A 6= 0, resp. hodnost matice A je rovná n, h(A) = n.
0.1.2
Iteraµcné metódy na riešenie sústav lineárnych rovníc
,
,
Pri pouµzití iteraµcnej metódy nebudeme hl adat presné riešenie, ale istú iteraµcnú
,
postupnost, ktorá konverguje ku presnému riešeniu. Ide de facto o ten istý
postup ako pri metóde prostej iterácie pri riešení nelineárnych rovníc, ibaµze
,
,
,
namiesto postupnosti µcísiel budeme teraz hl adat postupnost n-tíc.
Jacobiho metóda
Princíp Jacobiho metódy si ukáµzeme na systéme 3
Majme sústavu troch roníc o troch neznámych
3.
a11 x1 + a12 x2 + a13 x3
= b1 ;
a21 x1 + a22 x2 + a23 x3
= b2 ;
a31 x1 + a32 x2 + a33 x3
= b2 ;
1
vyjadrime si zarámované premenné
(k+1)
=
b1
a12 x2
(k+1)
=
b2
a21 x1
(k+1)
=
b2
a31 x1
x1
x2
x3
(k)
a13 x3
(k)
=a11 ;
(k)
a23 x3
(k)
=a22 ;
(k)
a32 x2
(k)
=a33 :
,
Týmto spôsobom sme dostali iteraµcnú postunost Jacobiho metódy
x(k+1) = ' x(k) :
h
i
(0)
(0)
(0)
Na zaµciatok zvolíme poµciatoµcnú aproximáciu x(0) = x1 ; x2 ; : : : ; xn ,dosadíme
,
do iteraµcného vztahu a dostávame x(1) = ' x(0) , etc. aµz pokým proces
neukonµcíme (napr. od istého desatinného miesta sa hodnoty iteraµcnej postupnosti nemenia).
Pozrime sa na problematiku, trochu všeobecnejšie. Rozloµzme si maticu sústavy A na tri matice: striktne dolnotrojuholníková matica LS , diagonálna matica D a striktne hornotrojuholníková matica US
0
0
LS = @ 0
0
a12
0
0
1
a13
a23 A ;
0
0
a11
D=@ 0
0
0
a22
0
1
0
0 A;
a33
0
0
US = @ a21
a31
0
0
a32
V takomto prípade môµzeme naše vyjadrenie zarámovaných premenných za,
písat nasledovne
Ax = b;
(LS + D + US ) x = b;
Dx = b (LS + US ) x;
x=D
1
[b (LS + US ) x] :
,
Tento vztah je všeobecným tvarom Jacobyho metódy
h
i
x(k+1) = D 1 b (LS + US ) x(k) ;
,
zapísaný v zloµzkovom tvare ju môµzeme zapísat
(k+1)
xi
1
=
aii
bi
i 1
X
k=1
(k)
aik xk
n
X
k=i+1
2
(k)
aik xk
!
;
i = 1; 2; : : : ; n:
1
0
0 A:
0
,
Doteraz sme sa nezaoberali, tým kedy bude iteraµcný proces konvergovat
,
akedy naopak nebude. Pre tieto úµcely je tné zaviest nasledujúci pojem.
De…nícia 2 Matica A sa nazýva riadkovo resp. st´lpcovo diagonálne dominantná práve vtedy, ak platí
jaii j >
2
n
X
j=1;j6=i
4resp. jajj j >
jaij j ;
n
X
i=1;i6=j
i = 1; 2; : : : ; n;
3
i = 1; 2; : : : ; n5 :
jaij j ;
Poznámka 2 To µci je matica riadkovo resp. st´lpcovo diagonálne dominantná
znamená, to µze jej diagonálna prvky sú väµcšie ako suma ostatných prvkov v
príslušnom riadku resp. st´lpca :
Veta 1 Ak je matica diagonálne dominantná potom Jacobiho metóda konverguje vµzdy.
Príklad 1 Jacobiho metódou riešte sústavu:
15x1
x2 + 2x3
=
30;
2x1
10x2 + x3
=
23;
x1 + 3x2 + 18x3
=
22:
,
Matica sústavy je zrejme diagonálne dominantná, preto môµzeme prikroµcit
,
ku jej riešeniu. Vyjadríme si iteraµcný vztah
(k+1)
=
30 + x2
(k+1)
=
23
(k+1)
=
x1
x2
x3
(k)
22
(k)
=15;
(k)
= ( 10) ;
2x3
(k)
2x1
(k)
x1
x3
(k)
3x2
=18:
,
Pre poµciatoµcnú aproximáciu x0 = [0; 0; 0] dostávame nasledovnú postupnost
r
0
1
2
3
4
(r)
x1
0
2
2:0096
1:9918
2:0000
(r)
x2
0
2:3
2:0222
1:9930
2:0013
(r)
x3
0
1:2222
0:9500
0:9968
1:0007
,
S prenostou " = 0:01 dostávame riešenie sústavy x4 = [2; 2; 1] :
3
Gauss-Seidelova metoda
,
Vyjadrenie iteraµcného vztahu Jacobiho metódy
(k+1)
=
b1
a12 x2
(k+1)
=
b2
a21 x1
(k+1)
=
b2
a31 x1
x1
x2
x3
(k)
a13 x3
(k)
a23 x3
(k)
a32 x2
(k)
=a11 ;
(k)
=a22 ;
(k)
=a33 :
si upravíme, a to takým spôsobom, µze v druhom riadku, kde prvý koe…(k)
(k+1)
cient x1 nahradíme uµz vypoµcítaným koe…cientom x1
. Takto by sme mohli
,
,
,
pokraµcovat a vyjadrit iteraµcné vztahy za pouµzitia uµz vypoµcítaných presnejších
hodnôt
(k+1)
=
b1
a12 x2
(k+1)
=
b2
a21 x1
(k+1)
=
b2
a31 x1
x1
x2
x3
(k)
(k)
a13 x3
=a11 ;
(k+1)
a23 x3
(k)
(k+1)
a32 x2
=a22 ;
(k+1)
=a33 :
Toto je podstata Gauss-Seidelovej metódy.
,
Vo všeobecnosti môµzeme Gauss-Seidelovu metódu zapísat ako
Ax = b;
(LS + D + US ) x = b;
(LS + D) x + US x
= b;
(LS + D) x
=
(b US x) ;
x
=
(LS + D)
1
x(k+1)
=
(LS + D)
1
(b US x) ;
b US x(i) :
V zloµzovom zápise
(k+1)
xi
1
=
aii
bi
i 1
X
n
X
(k+1)
aik xk
k=1
(k)
aik xk
k=i+1
!
Príklad 2 Gauss-Seidelovou metódou riešte sústavu:
6x1 + 2x2
3x3
=
10;
x1 + 4x2
2x3
=
6;
3x1 + 2x2
7x3
=
4
4:
;
i = 1; 2; : : : ; n:
Matica sústavy je zrejme diagonálne dominantná, a preto vyjadríme iteraµcný
,
vztah
(k+1)
=
10
(k+1)
=
6
(k+1)
=
4 + 3x1 + 2x2
x1
x2
x3
(k)
(k)
2x2
3x3
(k)
(k)
x1 + 2x3
(k)
(k)
=6;
=4;
=7:
,
Pre poµciatoµcnú aproximáciu x0 = [0; 0; 0] dostávame nasledovnú postupnost
r
0
1
2
3
4
5
6
(r)
x1
0:0000
1:6667
2:1032
2:0656
2:0192
2:0031
1:9999
(r)
x2
0:0000
1:0833
1:7718
1:9731
2:0054
2:0041
2:0013
(r)
x3
0:0000
1:5952
1:9790
2:0204
2:0098
2:0025
2:0003
,
S prenostou " = 0:01 dostávame riešenie sústavy x6 = [2; 2; 2] :
5
Download

0.1 Numerické riešenie systémov lineárnych rovníc