Metody obliczeniowe
Semestr II
Metody numeryczne - sposoby rozwiÄ…zania
zadania matematycznego za pomocÄ… operacji
na liczbach
1. Rozwiązywanie układów równań liniowych. Metody bezpośrednie i iteracyjne.
2. Sposoby rozwiązywania równań nieliniowych, zagadnienie optymalizacji.
3. Aproksymacja i interpolacja, pojęcie modelu regresji.
4. Wzory przybli\onego ró\niczkowania i całkowania.
5. Metoda Monte Carlo.
6. Przykłady zastosowania metod obliczeniowych w zadaniach in\ynierskich.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 2
Literatura
A. Bjorck, G. Dahlquist,
Metody numeryczne, PWN, Warszawa 1983.
Z. Fortuna, B. Macukow, J. WÄ…sowski,
Metody numeryczne, WNT, Warszawa 2005.
J. Stoer, R. Bulirsch,
Wstęp do metod numerycznych I-II, PWN 1990
A. Brozi,
Scilab, Nakom 2007
S. Rosłaniec,
Wybrane metody numeryczne z przykładami zastosowań w zadaniach
in\ynierskich, Oficyna Wydawnicza Politechniki Warszawskiej, 2002.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 3
Portale internetowe
" http://www.put.poznan.pl/~albert.kubzdela
" http://www.ikb.poznan.pl/zaklady/komp/
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 4
Metody obliczeniowe
" wykład nr 1
metody rozwiązywania układów równań
liniowych
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 5
Pojęcie układu równań liniowych
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ôÅ‚
a21x1 + a22x2 +L+ a2nxn = b2
ôÅ‚
òÅ‚
L
ôÅ‚
ôÅ‚am1x1 + am2x2 +L+ amnxn = bm
ół
" Układ powy\szy nazywamy układem m równań liniowych o n niewiadomych.
" Skalary ai, j nazywamy współczynnikami układu, skalary bi to wyrazy wolne.
" Rozwiązaniem układu nazywamy dowolną n-kę (r1, r2, ..., rn), które po
podstawieniu w miejsce xi do powy\szych równań dają równości prawdziwe
(sprawdzenie poprawności rozwiązania podstawienie n-ki (r1, r2, ..., rn) do lewych
stron równań i porównanie z wyrazami wolnymi).
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 6
Przykład układu równań
przykład układu dwóch równań z trzema niewiadomymi:
2x1 + x2 + x3 = 2
Å„Å‚
òÅ‚
x2 - 2x3 = -4
ół
Odpowiednio:
a1,1 = 2, a1,2 = 1, a1,3 = 1, a2,1 = 0, a2,2 = 1, a2,3 = -2;
wyrazami wolnymi sÄ… liczby 2 i -4.
x1
îÅ‚ Å‚Å‚
2 1 1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚x śł
2
ïÅ‚0 1 - 2śł Å" ïÅ‚ śł = ïÅ‚- 4śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
ïÅ‚ śł
3
ðÅ‚x ûÅ‚
Układ ten ma nieskończenie wiele rozwiązań, jednym z nich
jest trójka: x1 = 0, x2 = 0, x3 = 2.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 7
Zapis macierzowy układu równań liniowych
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
Postać równania
ôÅ‚
macierzowego:
a21x1 + a22x2 +L+ a2nxn = b2
ôÅ‚
òÅ‚
L
ôÅ‚
ôÅ‚am1x1 + am2x2 +L+ amnxn = bm
ół
a11 a12 L a1n x1 b1
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚a
a22 L a2n śłïÅ‚x2 śł ïÅ‚b2 śł
21
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
= Ò! [A]x = b
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
L L L L L L
ïÅ‚a
am2 L amn śłïÅ‚xn śł ïÅ‚bm śł
ðÅ‚ m1 ûÅ‚ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 8
Zapis macierzowy układu równań liniowych
a11 a12 L a1n x1 b1
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
Postać równania ïÅ‚a
a22 L a2n śłïÅ‚x2 śł ïÅ‚b2 śł
21
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
= Ò! [A]x = b
macierzowego:
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
L L L L L L
ïÅ‚a
am2 L amn śłïÅ‚xn śł ïÅ‚bm śł
ðÅ‚ m1 ûÅ‚ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Z danym układem równań związane są dwie wa\ne macierze.
macierz główna układu równań macierz rozszerzona
(macierz współczynników): (powstaje z macierzy głównej przez
dołączenie do niej kolumny wyrazów
a11 a12 L a1n
îÅ‚ Å‚Å‚
wolnych:
ïÅ‚a
a11 a12 L a1n b1
îÅ‚ Å‚Å‚
a22 L a2n śł
21
ïÅ‚ śł
A = ïÅ‚a
a22 L a2n b2 śł
ïÅ‚ śł 21
L L L L
ïÅ‚ śł
Arozszerz. =
ïÅ‚ śł
ïÅ‚ śł
L L L L
am2 L amn ûÅ‚
ðÅ‚am1
ïÅ‚ śł
am2 L amn bm ûÅ‚
ðÅ‚am1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 9
Istnienie rozwiązania układu równań
RzÄ…d macierzy
Rzędem macierzy A (rank(A), rz(A) ) nazywamy największą liczbę
liniowo niezale\nych wektorów kolumnowych w macierzy A.
Skończony układ wektorów {w1,...,wn}nazywamy układem liniowo niezale\nym,
gdy a1w1+ ... +anwn `" 0 jeśli skalary a1,...,an nie wszystkie są równe zero
`"
`"
`"
2 1 1 2 1 3
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 3
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚0 1 - 2śł, B = ïÅ‚0 1 1śł
ïÅ‚0śł ïÅ‚1śł ïÅ‚1śł
A =
+ =
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ ïÅ‚ śł
ðÅ‚1 1 1 śł ðÅ‚1 1 2ûÅ‚ ïÅ‚
ûÅ‚
ðÅ‚1śł ïÅ‚ ûÅ‚ ðÅ‚2śł
ûÅ‚ ðÅ‚1śł ïÅ‚ ûÅ‚
rank(A) = 3 rank(B) = 2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 10
Istnienie rozwiązania układu równań
RzÄ…d macierzy
Sprawę rozwiązalności układu równań wyjaśnia Twierdzenie
Kroneckera-Capellego:
Układ równań liniowych ma rozwiązanie wtedy i tylko wtedy,
gdy rząd macierzy głównej jest równy rzędowi macierzy
rozszerzonej.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 11
Rząd macierzy - przykłady
" układ równań posiadający rozwiązanie:
2 x1 + x + x3 = 2
Å„Å‚
2 1 1 2 1 1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2
ôÅ‚
ïÅ‚0 1 - 2śł, ïÅ‚0 1 - 2 - 4śł
x - 2 x3 = - 4
A = Arozszerzona =
2
òÅ‚
ïÅ‚ śł ïÅ‚ śł
ôÅ‚
ïÅ‚ ïÅ‚
x1 + x + x = 2
ðÅ‚1 1 1 śł ðÅ‚1 1 1 2 śł
ûÅ‚ ûÅ‚
ół 2 3
rank(A) = 3 rank(Arozszerzona ) = 3
T T
2 * [1 - 2 1] = [2 - 4 2]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 12
Rząd macierzy - przykłady
" układ równań posiadający rozwiązanie:
2 x1 + x + x3 = 2
Å„Å‚
2 1 1 2 1 1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2
ôÅ‚
ïÅ‚0 1 - 2śł, ïÅ‚0 1 - 2 - 4śł
x - 2 x3 = - 4
A = Arozszerzona =
2
òÅ‚
ïÅ‚ śł ïÅ‚ śł
ôÅ‚
ïÅ‚ ïÅ‚
x1 + x + x = 2
ðÅ‚1 1 1 śł ðÅ‚1 1 1 2 śł
ûÅ‚ ûÅ‚
ół 2 3
rank(A) = 3 rank(Arozszerzona ) = 3
T T
2 * [1 - 2 1] = [2 - 4 2]
" układ równań nie posiadający rozwiązania:
2 1 2 1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 x1 + x = 2
Å„Å‚
A = Arozszerzona =
2
ïÅ‚4 2śł, ïÅ‚4 2 5śł
òÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
4 x1 + 2 x = 5
ół 2
rank(A) = 1 rank(Arozszerzona ) = 2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 13
Typy układów równań liniowych
" Układ jednorodny
Je\eli wszystkie wyrazy wolne są równe 0, to układ równań nazywamy
jednorodnym. Układ jednorodny ma zawsze rozwiązanie.
" Układ kwadratowy
Je\eli n = m układ równań nazywamy kwadratowym.
" rank(A) < rank ([A,b]) brak rozwiÄ…zania;
" rank(A) = rank ([A,b]) < n nieskończenie wiele rozwiązań;
" rank(A) = rank ([A,b]) = n dokładnie jedno rozwiązanie.
(wówczas wyznacznik macierzy A jest ró\ny od zera)
a11 a12 L a1n x1 b1
a11x1 + a12x2 +L+ a1nxn = b1 îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
Å„Å‚
ïÅ‚a
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
a22 L a2n śłïÅ‚x2 śł ïÅ‚b2 śł
21
ôÅ‚
21
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
=
òÅ‚
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
L L L L L L
L
ôÅ‚
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
an2 L ann ûÅ‚ðÅ‚xn ûÅ‚ ðÅ‚bn ûÅ‚
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ðÅ‚an1
ół
[A]x = b, det A `" 0
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 14
Metody rozwiązywania układów równań liniowych
a11x1 + a12x2 = b1
Å„Å‚
òÅ‚a x1 + a22x2 = b2
ół 21
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
ôÅ‚
21
, n = 3,...,20
òÅ‚
L
ôÅ‚
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
ôÅ‚
21
, n = 20,...
òÅ‚
L
ôÅ‚
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 15
Metody rozwiązywania układów równań liniowych
" bezpośrednie (dokładne)
metody które przy braku błędów zaokrągleń dają dokładne rozwiązanie po
skończonej liczbie przekształceń układu wejściowego
" du\a efektywność dla układów o macierzach pełnych
" du\e obcią\enie pamięci
" mo\liwa niestabilność ze względu na błędy zaokrągleń
" iteracyjne
polegają na konstrukcji nieskończonego ciągu wektorów, zbie\nych do
szukanego rozwiÄ…zania,
x(0) x(1) x(2) ...
" efektywne dla macierzy rzadkich, du\ych rozmiarów
" stosunkowo niedu\e obcią\enie pamięci
" problemy ze zbie\nością
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 16
Metody bezpośrednie sposoby rozwiązań
" Przy u\yciu macierzy odwrotnej
" Wzory Cramera
" Układ równań z macierzą trójkątną
" Eliminacja Gaussa
" Rozkłady trójkątne macierzy
" Metoda sprzę\onych gradientów
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 17
Metody bezpośrednie
" Przy u\yciu macierzy odwrotnej
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 18
Metody bezpośrednie sposoby rozwiązań
" Przy u\yciu macierzy odwrotnej
UkÅ‚ad równaÅ„ A · x =b, znajÄ…c macierz odwrotnÄ… mo\na
rozwiązać:
A · x = b
A-1·A · x = A-1· b
x = A-1· b
x = inv(A) * b
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 19
Metody bezpośrednie wykorzystanie macierzy odwrotnej
Przykład (wykorzystanie arkusza kalkulacyjnego MS Excel)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 20
Metody bezpośrednie wykorzystanie macierzy odwrotnej
Przykład (wykorzystanie arkusza kalkulacyjnego MS Excel)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 21
Metody bezpośrednie wykorzystanie macierzy odwrotnej
Przykład (wykorzystanie arkusza kalkulacyjnego MS Excel)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 22
Metody bezpośrednie sposoby rozwiązań
" Wzory Cramera
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 23
Wzory Cramera
Gustaw Kramer ?
Gabriel Cramer
1704-1752
Wybrane fakty z \yciorysu
1722 uzyskuje doktorat,
1724 obejmuje katedrÄ™ matematyki w Genewie,
1727 1729 odbywa dwuletnią podró\ po Europie
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 24
Metody bezpośrednie sposoby rozwiązań
" Wzory Cramera
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 25
Metody bezpośrednie sposoby rozwiązań
" Wzory Cramera
UkÅ‚ad równaÅ„ A · x =b o macierzy nieosobliwej A ma dokÅ‚adnie
jedno rozwiÄ…zanie postaci
det(Ak )
xk = k =1,..., n
det(A)
macierz Ak powstaje z macierzy A przez zastÄ…pienie k-tej kolumny
przez wektor b
Cechy metody
" oszczędność pamięci
" bardzo du\y nakład obliczeń (w praktyce nie do zastosowania dla
du\ych układów równań)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 26
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1
ôÅ‚
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
ôÅ‚
ôÅ‚
...
òÅ‚
ôÅ‚
un-1,n-1xn-1 + un-1,nxn = bn-1
ôÅ‚
ôÅ‚
unnxn = bn
ół
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 27
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1 Å„Å‚l11x1 = b1
ôÅ‚ ôÅ‚l x1 + l22x2 = b2
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
21
ôÅ‚ ôÅ‚
ôÅ‚
ôÅ‚...
...
òÅ‚
òÅ‚
ôÅ‚
un-1,n-1xn-1 + un-1,nxn = bn-1 ôÅ‚ln-1,1x1 + ln-1,2x2 +...+ln-1,n-1xn-1 = bn-1
ôÅ‚
ôÅ‚
ôÅ‚
unnxn = bn
ôÅ‚
ół n1
ółl x1 + ln2x2 +...+ln,n-1xn-1 + lnnxn = bn
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 28
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1 Å„Å‚l11x1 = b1
ôÅ‚ ôÅ‚l x1 + l22x2 = b2
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
21
ôÅ‚ ôÅ‚
ôÅ‚
ôÅ‚...
...
òÅ‚
òÅ‚
ôÅ‚
un-1,n-1xn-1 + un-1,nxn = bn-1 ôÅ‚ln-1,1x1 + ln-1,2x2 +...+ln-1,n-1xn-1 = bn-1
ôÅ‚
ôÅ‚
ôÅ‚
unnxn = bn
ôÅ‚
ół n1
ółl x1 + ln2x2 +...+ln,n-1xn-1 + lnnxn = bn
bn b1
xn = x1 =
unn
l11
n
i -1
ëÅ‚ öÅ‚
ëÅ‚ öÅ‚
1
1
xi = bi -
ìÅ‚
xi = bi -
ìÅ‚
"u x ÷Å‚ i = n - 1,n - 2,...,1
ij j "l x ÷Å‚ i = 2,3,...,n
ij j
uii
íÅ‚ Å‚Å‚ lii
j =i +1 íÅ‚ Å‚Å‚
j =1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 29
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1
x(n)= b(n)/u(n,n)
ôÅ‚
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
ôÅ‚
ôÅ‚
...
òÅ‚
ôÅ‚
un -1,n-1xn-1 + un-1,nxn = bn-1
ôÅ‚
ôÅ‚
unnxn = bn
ół
bn
xn =
unn
n
ëÅ‚ öÅ‚
1
xi = bi -
ìÅ‚
"u xj÷Å‚ i = n - 1,n - 2,...,1
ij
uii
íÅ‚ Å‚Å‚
j =i +1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 30
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1
x(n)= b(n)/u(n,n)
ôÅ‚
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
ôÅ‚
for i=[n-1:-1:1]
ôÅ‚
...
òÅ‚
ôÅ‚
x(i)= b(i)
un -1,n-1xn-1 + un-1,nxn = bn-1
ôÅ‚
ôÅ‚
unnxn = bn
ół
bn
xn =
unn
n
ëÅ‚ öÅ‚
1
xi = bi -
ìÅ‚
"u xj÷Å‚ i = n - 1,n - 2,...,1
ij
uii
íÅ‚ Å‚Å‚
j =i +1
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 31
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1
x(n)= b(n)/u(n,n)
ôÅ‚
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
ôÅ‚
for i=[n-1:-1:1]
ôÅ‚
...
òÅ‚
ôÅ‚
x(i)= b(i)
un -1,n-1xn-1 + un-1,nxn = bn-1
ôÅ‚
ôÅ‚
unnxn = bn
ół
for j=[i+1:n]
x(i)=x(i)-u(i,j)*x(j)
bn
xn =
unn
end
n
ëÅ‚ öÅ‚
1
xi = bi -
ìÅ‚
"u xj÷Å‚ i = n - 1,n - 2,...,1
ij
uii
íÅ‚ Å‚Å‚
j =i +1
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 32
Metody bezpośrednie sposoby rozwiązań
" układ równań z macierzą trójkątną
metoda rozwiązania podstawianie wstecz (wprzód)
Å„Å‚u11x1 + u12x2 +...+u1,n-1xn-1 + u1nxn = b1
x(n)= b(n)/u(n,n)
ôÅ‚
u22x2 +...+u2,n-1xn-1 + u2nxn = b2
ôÅ‚
for i=[n-1:-1:1]
ôÅ‚
...
òÅ‚
ôÅ‚
x(i)= b(i)
un -1,n-1xn-1 + un-1,nxn = bn-1
ôÅ‚
ôÅ‚
unnxn = bn
ół
for j=[i+1:n]
x(i)=x(i)-u(i,j)*x(j)
bn
xn =
unn
end
n
ëÅ‚ öÅ‚
1
xi = bi -
ìÅ‚
"u xj÷Å‚ i = n - 1,n - 2,...,1
ij x(i)=x(i)/u(i,i)
uii
íÅ‚ Å‚Å‚
j =i +1
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 33
Metody bezpośrednie sposoby rozwiązań
" Eliminacja Gaussa
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 34
Carl Friedrich Gauss 1777-1855
" matematyk, fizyk, astronom, geodeta
jedno z pierwszych odkryć:
podanie konstrukcji siedemnastokÄ…ta foremnego przy u\yciu cyrkla i linijki
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 35
Metody bezpośrednie Eliminacja Gaussa
" sprowadzenie układu do równowa\nego układu
postaci trójkątnej eliminacja zmiennych
" rozwiązanie układu trójkątnego postępowanie
odwrotne
a11x1 + a12x2 + a13x3 + ...+ a1nxn = b
a11x1 + a12x2 +...+ a1nxn = b1 Å„Å‚
Å„Å‚
ôÅ‚
ôÅ‚a x1 + a22x2 +...+ a2nxn = b2
(1 (1 ( (
a22)x2 + a23)x3 + ...+ a21)xn = b21)
ôÅ‚
ôÅ‚
21
n
Ò!
Ò!
Ò!
Ò!
òÅ‚ òÅ‚
... ...
ôÅ‚ ôÅ‚
(n (
ôÅ‚an1x1 + an2x2 +...+ annxn = bn ôÅ‚
ann-1)xn = bnn-1)
ół
ół
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 36
Eliminacja Gaussa - przykład
Układ równań zapisujemy w postaci macierzy rozszerzonej układu
1 1 1 -1 x1 2
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 1 1 -1 2
îÅ‚ Å‚Å‚
ïÅ‚
ïÅ‚
1 -1 -1 1śłïÅ‚x2 śł ïÅ‚0śł
1 -1 -1 1 0śł
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
= ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
2 1 -1 2 x3 9
ïÅ‚ śł
2 1 -1 2 9
ïÅ‚ ïÅ‚
ïÅ‚
3 1 2 -1śłðÅ‚x4 śł ïÅ‚7śł
ðÅ‚ ûÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
3 1 2 -1 7śł
ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 37
Eliminacja Gaussa - przykład
I krok
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚
1 -1 -1 1 0śł 0 - 2 - 2 2 - 2śł
ïÅ‚ śł ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
2 1 -1 2 9 0 -1 - 3 4 5
ïÅ‚ ïÅ‚ śł
3 1 2 -1 7śł 0 - 2 -1 2 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 38
Eliminacja Gaussa - przykład
I krok
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚
1 -1 -1 1 0śł 0 - 2 - 2 2 - 2śł
ïÅ‚ śł ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
2 1 -1 2 9 0 -1 - 3 4 5
ïÅ‚ ïÅ‚ śł
3 1 2 -1 7śł 0 - 2 -1 2 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
ai1
(
aij1) = aij - a1 j
i = 2,...,4
a11
ai1
j = 1,...,4
bi(1) = bi - b1
a11
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 39
Eliminacja Gaussa - przykład
I krok
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚
1 -1 -1 1 0śł 0 - 2 - 2 2 - 2śł
ïÅ‚ śł ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
2 1 -1 2 9 0 -1 - 3 4 5
ïÅ‚ ïÅ‚ śł
3 1 2 -1 7śł 0 - 2 -1 2 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
II krok
ïÅ‚ ïÅ‚
0 - 2 - 2 2 - 2śł 0 - 2 - 2 2 - 2śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
0 -1 - 3 4 5 0 0 - 2 3 6
ïÅ‚ śł ïÅ‚ śł
0 - 2 -1 2 1 0 0 1 0 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 40
Eliminacja Gaussa - przykład
I krok
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚
1 -1 -1 1 0śł 0 - 2 - 2 2 - 2śł
ïÅ‚ śł ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
2 1 -1 2 9 0 -1 - 3 4 5
ïÅ‚ ïÅ‚ śł
3 1 2 -1 7śł 0 - 2 -1 2 1
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
II krok
ïÅ‚ ïÅ‚
0 - 2 - 2 2 - 2śł 0 - 2 - 2 2 - 2śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
0 -1 - 3 4 5 0 0 - 2 3 6
ïÅ‚ śł ïÅ‚ śł
0 - 2 -1 2 1 0 0 1 0 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 1 1 -1 2 1 1 1 -1 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
III krok
ïÅ‚ ïÅ‚
0 - 2 - 2 2 - 2śł 0 - 2 - 2 2 - 2śł
ïÅ‚ śł ïÅ‚ śł
Ò!
Ò!
Ò!
Ò!
ïÅ‚ śł ïÅ‚ śł
0 0 - 2 3 6 0 0 - 2 3 6
ïÅ‚ śł ïÅ‚ śł
0 0 1 0 3 0 0 0 1.5 6
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Wykonując postępowanie odwrotne, znajdujemy rozwiązanie x = [1, 2, 3, 4]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 41
Metody bezpośrednie Eliminacja Gaussa
1. Eliminacja zmiennych
Krok 1 Zakładamy, \e
a11 `" 0
z pozostałych n-1 równań eliminujemy zmienną x1 odejmując od i-tego równania (i=2,3,...,n)
równanie pierwsze
pomno\one przez
Å„Å‚a11x1 + a12x2 +...+a1nxn = b1
ai1
(
1
ôÅ‚ ( ( (
a22)x2 +...+a21)xn = b21) aij1) = aij - a11 a1 j
ai1 ôÅ‚
n
li1 = òÅ‚
ai1
...
a11
ôÅ‚
bi(1) = bi - b1
1
( ( (
a11
ôÅ‚
an1)x2 +...+ann)xn = bn1)
ół 2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 42
Metody bezpośrednie Eliminacja Gaussa
1. Eliminacja zmiennych
Krok 1 Zakładamy, \e
a11 `" 0
z pozostałych n-1 równań eliminujemy zmienną x1 odejmując od i-tego równania (i=2,3,...,n)
równanie pierwsze
pomno\one przez
Å„Å‚a11x1 + a12x2 +...+a1nxn = b1
ai1
(
1
ôÅ‚ ( ( (
a22)x2 +...+a21)xn = b21) aij1) = aij - a11 a1 j
ai1 ôÅ‚
n
li1 = òÅ‚
ai1
...
a11
ôÅ‚
bi(1) = bi - b1
1
( ( (
a11
ôÅ‚
an1)x2 +...+ann)xn = bn1)
ół 2
(
aiii) `" 0
Krok k-ty Zakładamy, \e
z równań n-k eliminujemy zmienną xk odejmując od i-tego równania (i=k+1,...,n) równanie k-te
pomno\one przez
(
aikk -1)
a11x1 + a12x2 + ...+ a1k xk + a1k +1xk +1 + ...+ a1nxn = b1
Å„Å‚
lik =
(
(k ôÅ‚
(1 ( ( ( (
aikk -1) (k -1)
akk -1) ( (
a22)x2 + ...+ a21)xk + a21)+1xk +1 +... +a21)xn = b21)
k k n
ôÅ‚ aijk ) = aijk -1) - akj
(k
akk -1)
ôÅ‚
.........................
ôÅ‚
(
aikk -1) -1)
òÅ‚
(k -1) (k -1) (k -1) ( -1)
bi(k ) = bi(k -1) - bk(k
+1 +1 (k
ôÅ‚ akk xk + akk xk + ...+ akn xn = bkk
akk -1)
ôÅ‚
.........................
ôÅ‚
(k (k (
ôÅ‚ ank ) xk +1 +... + ann)xn = bnk )
ół +1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 43
Metody bezpośrednie Eliminacja Gaussa
1. Eliminacja zmiennych (c.d.)
Po n-1 krokach ostatecznie otrzymujemy kład równań postaci:
a11x1 + a12x2 + a13x3 +...+ a1nxn = b1
Å„Å‚
ôÅ‚ (1 (1 ( (
a22)x2 + a23)x3 +...+ a21)xn = b21)
n
ôÅ‚
ôÅ‚
(2 ( (
a33)x3 +...+ a32)xn = b32)
òÅ‚
n
ôÅ‚
...
ôÅ‚
(n (
ôÅ‚ ann-1)xn = bnn-1)
ół
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 44
Metody bezpośrednie Eliminacja Gaussa
1. Eliminacja zmiennych (c.d.)
Po n-1 krokach ostatecznie otrzymujemy kład równań postaci:
a11x1 + a12x2 + a13x3 +...+ a1nxn = b1
Å„Å‚
ôÅ‚ (1 (1 ( (
a22)x2 + a23)x3 +...+ a21)xn = b21)
n
ôÅ‚
ôÅ‚
(2 ( (
a33)x3 +...+ a32)xn = b32)
òÅ‚
n
ôÅ‚
...
ôÅ‚
(n (
ôÅ‚ ann-1)xn = bnn-1)
ół
2. Postępowanie odwrotne
Rozwiązanie układu równań o trójkątnej macierzy współczynników
(
zakładając, \e , rozwiązanie dla i = n,...,1 otrzymuje się wg
aiii-1) `" 0
wzorów:
n
(i-1)
bi(i-1) -
"a xj
ij
j=i+1
xi =
(
aiii-1)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 45
Metody bezpośrednie Eliminacja Gaussa
wybór elementu podstawowego
" rozwa\my układ równań
2x2 + 2x3 = 1
Å„Å‚
ôÅ‚3x + 3x2
= 3
òÅ‚
1
ôÅ‚
x1 + x3 = 2
ół
" macierz układu jest nieosobliwa, więc istnieje jednoznaczne
rozwiÄ…zanie, ale ...
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 46
Metody bezpośrednie Eliminacja Gaussa
wybór elementu podstawowego
" rozwa\my układ równań
2x2 + 2x3 = 1
Å„Å‚
ôÅ‚3x + 3x2
= 3
òÅ‚
1
ôÅ‚
x1 + x3 = 2
ół
" macierz układu jest nieosobliwa, więc istnieje jednoznaczne
rozwiÄ…zanie, ale ...
" stosujÄ…c eliminacjÄ™ Gaussa, obliczenia zostanÄ… przerwane w kroku
k = 1 gdy\ a11=0.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 47
Metody bezpośrednie Eliminacja Gaussa
wybór elementu podstawowego
" rozwa\my układ równań
2x2 + 2x3 = 1
Å„Å‚
ôÅ‚3x + 3x2
= 3
òÅ‚
1
ôÅ‚
x1 + x3 = 2
ół
" macierz układu jest nieosobliwa, więc istnieje jednoznaczne
rozwiÄ…zanie, ale ...
" stosujÄ…c eliminacjÄ™ Gaussa, obliczenia zostanÄ… przerwane w kroku
k = 1 gdy\ a11=0.
" zmiana kolejności wierszy nie zmienia rozwiązania układu
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 48
Metody bezpośrednie Eliminacja Gaussa
wybór elementu podstawowego
" rozwa\my układ równań
2x2 + 2x3 = 1
Å„Å‚
ôÅ‚3x + 3x2
= 3
òÅ‚
1
ôÅ‚
x1 + x3 = 2
ół
" macierz układu jest nieosobliwa, więc istnieje jednoznaczne
rozwiÄ…zanie, ale ...
" stosujÄ…c eliminacjÄ™ Gaussa, obliczenia zostanÄ… przerwane w kroku
k = 1 gdy\ a11=0.
" zmiana kolejności wierszy nie zmienia rozwiązania układu
" Eliminację mo\na przeprowadzić bez przestawiania wierszy bądz
kolumn gdy macierz A jest macierzÄ…:
n
| aii |e" aij | i, j = 1,..., n
z dominującą przekątną główną, tzn. "|
j=1
j`"i
lub
symetryczna i dodatnio określoną tzn. AT = A i xTA x > 0 dla ka\dego
niezerowego wektora x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 49
Metody bezpośrednie Eliminacja Gaussa
wybór elementu podstawowego
" Elementem podstawowym (głównym) nazywamy ten element
macierzy A, za pomocą którego dokonujemy eliminacji zmiennej z
dalszych równań
" Strategie wyboru elementu podstawowego:
wybór częściowy
wybór pełny
" Strategia z częściowym wyborem elementu podstawowego (metoda Gaussa-
Crouta) jest metodą niezawodną, tzn. zakładając brak błędów obliczeń, nie
nastąpi zatrzymanie procesu obliczeń z powodu dzielenia przez zero, w
przypadku gdy istnieje jednoznaczne rozwiązanie układu
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 50
Metody bezpośrednie Eliminacja Gaussa
wybór częściowy elementu podstawowego
wybiera siÄ™ k jako najmniejszÄ…
liczbę całkowitą dla której
j
akj = max aij
i = j, j +1,...,n
i przestawia siÄ™ wiersze k-ty oraz
j
j-ty
k
akj = max aij
i = j, j +1,...,n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 51
Metody bezpośrednie Eliminacja Gaussa
wybór pełny elementu podstawowego
wybiera siÄ™ k i l jako najmniejsze
liczby całkowite dla których
m
l
akl = max aij
i. j =m,m+1,...,n
m
i przestawia siÄ™ wiersze k-ty i m-ty
oraz kolumny l-tÄ… i m-tÄ…,
k
akl = max aij
i. j =m,m+1,...,n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 52
Metody bezpośrednie Eliminacja Gaussa
w k-tym kroku, dla i = k+1, k+2, ..., n (wiersze) mamy
a(k -1)
ik
(
aijk ) = aij (k -1) - a(k -1) ,... j = k, k +1,..., n
kj
a(k -1)
kk
a(k -1)
ik
bi(k ) = b(k -1) - b(k -1)
i k
a(k -1)
kk
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 53
Metody bezpośrednie Eliminacja Gaussa
w k-tym kroku, dla i = k+1, k+2, ..., n (wiersze) mamy
a(k -1)
ik
(
aijk ) = aij (k -1) - a(k -1) ,... j = k, k +1,..., n
kj
a(k -1)
kk
a(k -1)
ik
bi(k ) = b(k -1) - b(k -1)
i k
a(k -1)
kk
for k= 1:n-1
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 54
Metody bezpośrednie Eliminacja Gaussa
w k-tym kroku, dla i = k+1, k+2, ..., n (wiersze) mamy
a(k -1)
ik
(
aijk ) = aij (k -1) - a(k -1) ,... j = k, k +1,..., n
kj
a(k -1)
kk
a(k -1)
ik
bi(k ) = b(k -1) - b(k -1)
i k
a(k -1)
kk
for k= 1:n-1
for i= k+1:n
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 55
Metody bezpośrednie Eliminacja Gaussa
w k-tym kroku, dla i = k+1, k+2, ..., n (wiersze) mamy
a(k -1)
ik
(
aijk ) = aij (k -1) - a(k -1) ,... j = k, k +1,..., n
kj
a(k -1)
kk
a(k -1)
ik
bi(k ) = b(k -1) - b(k -1)
i k
a(k -1)
kk
for k= 1:n-1
for i= k+1:n
b(i)= b(i)- a(i,k)*b(k)/ a(k,k)
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 56
Metody bezpośrednie Eliminacja Gaussa
w k-tym kroku, dla i = k+1, k+2, ..., n (wiersze) mamy
a(k -1)
ik
(
aijk ) = aij (k -1) - a(k -1) ,... j = k, k +1,..., n
kj
a(k -1)
kk
a(k -1)
ik
bi(k ) = b(k -1) - b(k -1)
i k
a(k -1)
kk
for k= 1:n-1
for i= k+1:n
for j= k:n
a(i,j)= a(i,j)-a(i,k)*a(k,j)/a(k,k)
end
b(i)= b(i)- a(i,k)*b(k)/ a(k,k)
end
end
Zadanie: uzupełnij kod programu o wybór częściowy elementu
podstawowego
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 57
Metody bezpośrednie Eliminacja Gaussa-Jordana
" Odmiana eliminacji Gaussa
Wiersze są normalizowane poprzez dzielenie przez element główny
Kolejna zmienna jest eliminowana z wszystkich równań, a nie tylko z
następnych
Po n krokach eliminacji otrzymuje siÄ™ macierz jednostkowÄ…, czego
efektem jest uzyskanie rozwiÄ…zania w wektorze prawych stron
(1 ( (
(0) (0)
x1 + a12)x2 + ...+ a11)xn = b11)
x1 + a12 x2 + ...+ a1n xn = b1(0)
n
(1 ( (
a21x1 + a22x2 + ...+ a2nxn = b2 a22)x2 + ...+ a21)xn = b21)
n
Ò!
Ò!
Ò!
Ò!
.......................................... ............................
( (1 (
an1x1 + an2x2 +...+ annxn = bn
an1)x2 + ...+ ann)xn = bn1)
2
(2) (2) (2)
x1 + a13 x3+K+ a1n xn = b1 x1 = b1(n-1)
(2 ( ( (
x2 + a23)x3 +K+a22)xn = b22) x2 = b2n-1)
n
Ò!
Ò!
Ò!
Ò!
............................ .......... .......... .........
( (2 ( (
an2)x3 +K+ann)xn = bn2) xn = bnn-1)
3
Zadanie: zapisz kod programu (wykorzystujÄ…c instrukcjÄ™ for) realizujÄ…cy metodÄ™
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 58
Metody bezpośrednie Rozkład trójkątny
" rozwiązanie układu równań A x = b :
jeśli istnieje rozkład trójkątny A = LU to:
LU x = b, U x = y, L y = b.
Twierdzenie:
Niech A będzie macierząn x n. Niech Ak oznacza macierz k x k utworzoną z
elementów początkowych k wierszy i kolumn macierzy A. Jeśli det(Ak) `" 0 dla
k=1,...,n-1 to istnieje jedyny rozkład A=LU taki, \e
" macierz L jest macierzą trójkątną dolną z elementami na głównej przekątnej
równymi 1,
" macierz U jest macierzą trójkątną górną.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 59
Metody bezpośrednie Rozkład trójkątny
" zapamiętując rozkład LU mo\emy szybko rozwiązać wiele układów
ró\niących się wektorem b
Inne zastosowania rozkładu trójkątnego macierzy:
" obliczanie wyznacznika macierzy A
det(A)=det(LU)=det(L)det(U)=det(U)
" wyznaczanie macierzy odwrotnej do A
A-1 = (LU)-1 = U-1 L-1
(odwrotności macierzy trójkątnych oblicza się łatwo)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 60
Metody bezpośrednie Rozkład trójkątny
A = L U
" metoda Doolitle a
a11 a12 K a1n 1 u11 u21 K u1n
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
ïÅ‚a a22 K a2n śł ïÅ‚l 1 śłïÅ‚
u22 K u2n śł
21 21
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
=
ïÅ‚ M M O M śł ïÅ‚ M M O śłïÅ‚ O M śł
ïÅ‚a an2 K ann śł ïÅ‚l ln2 K 1śłïÅ‚
unn śł
ðÅ‚ n1 ûÅ‚ ðÅ‚ n1 ûÅ‚ðÅ‚ ûÅ‚
i =1,...,n
i-1
uij = aij -
"l ukj, j = i,i +1,...,n
ik
k =1
i-1
ëÅ‚
lji = aji - ÷Å‚
ìÅ‚
"l uki öÅ‚ / uii, j = i +1,i + 2,...,n
jk
íÅ‚ k =1 Å‚Å‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 61
Metody bezpośrednie Rozkład trójkątny
A = L U
" metoda Crouta
macierz U posiada jedynki na przekątnej głównej
a11 a12 K a1n l11 1 u21 K u1n
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
ïÅ‚a a22 K a2n śł ïÅ‚l l22 śłïÅ‚
1 K u2n śł
21 21
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
=
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
M M O M M M O O M
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
an2 K ann ûÅ‚ ðÅ‚ln1 ln2 K lnn ûÅ‚ðÅ‚ 1
ðÅ‚an1 ûÅ‚
j =1,...,n
j-1
lij = aij - i = j, j +1,...,n
"l ukj ,
ik
k =1
j-1
ëÅ‚ öÅ‚
ìÅ‚ -
u =
jk "l
ìÅ‚ajk i=1 jiuik ÷Å‚ / ljj , k = j +1, j + 2,...,n
÷Å‚
íÅ‚ Å‚Å‚
Zadanie: zapisz kod programu (funkcjÄ™ SciLaba) realizujÄ…cy metodÄ™ Crouta
WE: macierz A, WY: macierze L, U
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 62
Metody bezpośrednie Rozkład trójkątny
A = L U
Przykład zastosowania metody Doolitle a
1 1 1 1 [0] ? ? ?
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
i =1,..., n
ïÅ‚2 1 2śł = ïÅ‚? 1 śłïÅ‚
? ?śł
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
i-1
ïÅ‚ śł śł
ðÅ‚3 1 1ûÅ‚ ïÅ‚ ? 1 śłïÅ‚
ðÅ‚? ûÅ‚ðÅ‚[0] ?ûÅ‚
uij = aij -
"l ukj , j = i,i +1,..., n
ik
k =1
u1? = a1?, l21 = a21 = 2
i-1
ëÅ‚
u22 = a22 - l21u12 =1
lji = aji - ÷Å‚
ìÅ‚
"l uki öÅ‚ / uii, j = i +1,i + 2,..., n
jk
u23 = a23 - l21u13 = 0
íÅ‚ k =1 Å‚Å‚
a31 a32 - l31u12
l31 = = 3, l32 = = 2
u11 u22
u33 = a33 - l31u13 - l32u23 = -2
1 1 1 1 [0] 1 1 1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
ïÅ‚2 1 2śł = ïÅ‚2 1 śłïÅ‚ śł
-1 0
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
ïÅ‚ śł śł
- 2ûÅ‚
ðÅ‚3 1 1ûÅ‚ ïÅ‚ 2 1 śłïÅ‚
ðÅ‚3 ûÅ‚ðÅ‚[0]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 63
Metody bezpośrednie Rozkład trójkątny
A = L U
Przykład zastosowania metody Doolitle a
1 1 1 1 [0] ? ? ?
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
i =1,..., n
ïÅ‚2 1 2śł = ïÅ‚? 1 śłïÅ‚
? ?śł
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
i-1
ïÅ‚ śł śł
ðÅ‚3 1 1ûÅ‚ ïÅ‚ ? 1 śłïÅ‚
ðÅ‚? ûÅ‚ðÅ‚[0] ?ûÅ‚
uij = aij -
"l ukj , j = i,i +1,..., n
ik
k =1
u1? = a1?, l21 = a21 = 2
i-1
ëÅ‚
u22 = a22 - l21u12 =1
lji = aji - ÷Å‚
ìÅ‚
"l uki öÅ‚ / uii, j = i +1,i + 2,..., n
jk
u23 = a23 - l21u13 = 0
íÅ‚ k =1 Å‚Å‚
a31 a32 - l31u12
l31 = = 3, l32 = = 2
u11 u22
u33 = a33 - l31u13 - l32u23 = -2
1 1 1 1 [0] 1 1 1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚
ïÅ‚2 1 2śł = ïÅ‚2 1 śłïÅ‚ śł
-1 0
ïÅ‚ śł ïÅ‚ śłïÅ‚ śł
ïÅ‚ śł śł
- 2ûÅ‚
ðÅ‚3 1 1ûÅ‚ ïÅ‚ 2 1 śłïÅ‚
ðÅ‚3 ûÅ‚ðÅ‚[0]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 64
Układy równań z macierzami specjalnymi
" A macierz symetryczna, dodatnio określona
j-1
rozkład Cholesky ego
2
l = ajj -
jj "l ,
jk
A = L LT
k =1
j-1
1
lij = (aij -
"l lik ),
jk
l
k =1
jj
j =1,2,...,n
i = j +1, j + 2,...,n
" A macierz symetryczna
jednoznaczny rozkład A = L D LT
D macierz diagonalna
Zadanie: zapisz kod programu (funkcjÄ™ SciLaba, przy u\yciu instrukcji
for) realizujący rozkład Cholesky ego, WE: macierz A, WY: macierz L
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 65
Układy równań analiza rozwiązań przybli\onych
" Ax = b układ równań
" otrzymane przybli\one rozwiÄ…zanie x0
jeśli rozwiązanie jest rozwiązaniem dokładnym to
Ax b = [0]
jeśli nie jest rozwiązaniem dokładnym to obliczamy
wektor residuum
r0 = b Ax0 `" [0]
`"
`"
`"
Jak dobrym przybli\eniem rozwiązania dokładnego jest
wektor x0?
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 66
Norma mierzenie odległości
" x, y liczby rzeczywiste
odległość d=|x y|
" x=(x1,x2), y =(y1,y2), punkty w przestrzeni 2D
odległość
d = (x1 - x2)2 + (y1 - y2)2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 67
Norma mierzenie odległości
" x, y liczby rzeczywiste
odległość d=|x y|
" x=(x1,x2), y =(y1,y2), punkty w przestrzeni 2D
odległość
d = (x1 - x2)2 + (y1 - y2)2
Norma nieujemna funkcja rzeczywistą ||.||: X R, spełniającą
następujące warunki :
1. ||x|| = 0 wtedy i tylko wtedy gdy x = 0
2. ||ax|| = |a|*||x|| dla ka\dej liczby rzeczywistej a"
"R
"
"
3. ||x + y|| d" ||x|| + ||y|| (tzw. nierówność trójkąta).
d"
d"
d"
(odległość elementu przestrzeni liniowej od punktu 0)
Odległość dwóch elementów przestrzeni liniowej x, y
d = || x-y ||
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 68
Norma przykłady
" w przestrzeni Rn,
|| x || " = max | xi |
i =1,..., n
x =(x1,x2,..., xn) " Rn :
n
|| x ||1 = | xi |
"
i =1
1 / p
n n
|| x ||2 = xi 2 , || x || = ( xi p )
" p "
i =1 i =1
" przestrzeni ciągów
|| x || " = sup | xi |,
i =1, 2 ,...
x =(xn)n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 69
Norma przykłady
" macierzowe ( Anm -macierz kwadratowa n=m)
n
|| A || " = max
"| aij |,
i=1,...,n
j=1
a11 a12 .. .. a1n
|| A || = max | aij | îÅ‚ Å‚Å‚
i=1,...,n
ïÅ‚a a22 .. .. a2 śł
j=1,...,n
21 n
ïÅ‚ śł
ïÅ‚ śł
A = .. .. .. .. ..
n n
2
ïÅ‚ śł
|| A ||2 = .. .. .. .. ..
""a
ij
ïÅ‚ śł
i=1 j=1
ïÅ‚an1 an 2 .. .. ann śł
ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 70
Norma przykłady
" w przestrzeni funkcji C[a,b]
f, g " C[a,b]
2.5
|| f || " = sup | f (x) |,
x"[a,b]
2
|| f ||2 = f (x) |2 dx
+"|
[a,b]
1.5
funkcja f
funkcja g
1
|| f - g ||< µ
0.5
0
-0.8 0.2 1.2 2.2 3.2 4.2 5.2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 71
Norma mierzenie odległości
[y]=norm(x [,flag])
" norma macierzowa
" x : wektor lub macierz (rzeczywiste lub zespolone)
" flag : rodzaj normy (domyślnie =2)
" Opis (macierze)
norm(x): norm(x,2) : największa wartość bezwzględna elementu macierzy
norm(x,1): największa suma kolumny
norm(x,'inf'),norm(x,%inf): największa suma wiersza
" wektory
norm(v,p): || . ||p
norm(v): || . ||2
norm(v,'inf'): norma supremalna
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 72
Norma przestrzeń unormowana
Przestrzeń liniowa w której zdefiniowano normę
= przestrzeń unormowana
Stefan Banach
Hugo Steinhaus
Władysław Orlicz
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 73
Układy równań analiza rozwiązań przybli\onych
" Ax = b układ równań
" otrzymane przybli\one rozwiÄ…zanie x0
jeśli rozwiązanie jest rozwiązaniem dokładnym to
Ax b = [0]
jeśli nie jest rozwiązaniem dokładnym to obliczamy
wektor residuum
r0 = b Ax0 `" [0]
`"
`"
`"
Jak dobrym przybli\eniem rozwiązania dokładnego jest
wektor x0?
Oszacowanie przy u\yciu normy (dla rozwiązań x1, x2) :
r1= b Ax1 r2= b Ax2
Jeśli ||r1||<||r2|| to rozwiązanie x1 jest bardziej
dokładne ni\ x2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 74
Układy równań z macierzami specjalnymi
Metoda sprzę\onych gradientów
" A macierz symetryczna
metoda sprzę\onych gradientów
" ustalamy wektor poczÄ…tkowy niewiadomych x
" obliczamy wektor r0 = b Ax, przyjmujemy P0 = r0
" dla i = 0,1,2,..., n-1 obliczamy
|| ri ||2
Ä…i = ,
Pi T APi
xi+1 = xi +Ä…i Pi , ri+1 = ri -Ä…i APi
|| ri+1 ||2
²i = , Pi+1 = ri+1 + ²i Pi
|| ri ||
podczas obliczeń nie następuje przekształcenie macierzy A
(wygodne dla macierzy rzadkich)
zadawalajÄ…cym przybli\eniem jest wektor xi dla pewnego i < n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 75
Układy równań z macierzami specjalnymi
Metoda sprzę\onych gradientów - przykład
1 1 2 -1 x1 5
|| ri ||2
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
Ä…i = ,
ïÅ‚
PiT APi
1 -1 -1 1śłïÅ‚x2 śł ïÅ‚0śł
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
=
xi+1 = xi +Ä…iPi, ri+1 = ri -Ä…i APi
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł
2 -1 -1 2 x3 5
|| ri+1 ||2
ïÅ‚
ïÅ‚-1 1 2 -1śłðÅ‚x4 śł ïÅ‚3śł
²i = , Pi+1 = ri+1 + ²iPi
|| ri ||2
ðÅ‚ ûÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
" wektor poczÄ…tkowy niewiadomych x0 = [1, 1, 1, 1]T
" uzyskiwane kolejne przybli\enia
[ 2.0967742 1. 2.6451613 2.0967742 ]
[ 0.8879310 0.3060345 3.6077586 3.6637931 ]
[ 0.8548387 0.5967742 3.6290323 3.5645161 ]
[ 1. 2. 3. 4. ]
Zadanie: zapisz kod programu (funkcjÄ™ SciLaba) realizujÄ…cy
metodÄ™, WE: macierz A, wektor b, WY: wektor x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 76
Sposoby zapisu macierzy
Profil macierzy rzadkiej
a11 0 .. .. 0
îÅ‚ Å‚Å‚
a11 {1 1}
îÅ‚ Å‚Å‚
ïÅ‚
ïÅ‚a śł
0 a22 .. .. a2n śł
{2 2}
ïÅ‚ śł
22
ïÅ‚ śł
ïÅ‚ śł
A = .. .. .. .. ..
ïÅ‚ śł
Ò! A(sparse ) = an 2 {n 2}
ïÅ‚ śł
ïÅ‚ śł
0 .. .. .. ..
ïÅ‚ śł {2 n}
ïÅ‚a2n śł
ïÅ‚
0 an 2 .. .. ann śł
ïÅ‚ann śł
ðÅ‚ ûÅ‚
{n n}
ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 77
Sposoby zapisu macierzy
Postać blokowa macierzy
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 78
Metody iteracyjne - przykład
Obliczenie pierwiastka kwadratowego
c
c = x2 Ò! = x
x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 79
Metody iteracyjne - przykład
Obliczenie pierwiastka kwadratowego
c c
c = x2 Ò! = x Ò! ( + x) = 2x
x x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 80
Metody iteracyjne - przykład
Obliczenie pierwiastka kwadratowego
c c
c = x2 Ò! = x Ò! ( + x) = 2x Ò!
x x
1 c
x = ( + x)
2 x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 81
Metody iteracyjne - przykład
Obliczenie pierwiastka kwadratowego
c c
c = x2 Ò! = x Ò! ( + x) = 2x Ò!
x x
1 c
x = ( + x)
2 x
x = 1, c = 2
for i= 1:n
1 c
x = (c/x + x)/2
xi+1 = ( + xi) i =1,2,...
end
2 xi
x1 =1
x = 1, c = 2
x2 =1.5
eps = 0.00001
x3 =1.416667
while abs(c-x*x) > eps
x4 =1.414216
x = (c/x + x)/2
end
...
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 82
Metody iteracyjne
rozwiązywania układów równań liniowych
startujÄ… z przybli\enia poczÄ…tkowego x(0)
polegają na konstrukcji nieskończonego ciągu wektorów,
zbie\nych do szukanego rozwiÄ…zania,
x(0) x(1) x(2) ...
liczba operacji wykonywanych w ka\dym kroku iteracyjnym jest
porównywalna z mno\eniem macierzy przez wektor
stosowane w przypadkach gdy macierz A jest du\ych rozmiarów
macierzÄ… rzadkÄ…
problem
" doboru początkowego przybli\enia (często wektor zerowy)
" przerwania procesu iteracyjnego
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 83
Metody iteracyjne
rozwiązywania układów równań liniowych
Przerwanie procesu iteracyjnego
oszacowanie ||x(k+1) - x(k) || < µ
k indeks iteracji
dobre wyniki gdy proces jest szybko zbie\ny
oszacowanie || r(k) || = || A x(k) b || < µ
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 84
Ulepszanie iteracyjne rozwiÄ…zania
(metoda iteracji powtórnej)
dla równania A x = b dany jest rozkład A = L U
wartość obliczona
x
residuum
r = b - Ax
proces iteracyjny
" nale\y przyjąć x(1) := x
x(s), s = 2,3,...
" następnie obliczyć
wg formuł
r(s) = b - Ax(s),
-1
L(U Å""x(s)) = r(s), "x(s) = U L-1r(s)
x(s+1) = x(s) + "x(s)
Zadanie: zapisz kod programu realizujÄ…cy metodÄ™
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 85
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
dla j =1 :
n n n
a11x1 +
"a xk = b1 Ò! a11x1 = b1 -"a xk Ò! x1 = (b1 -"a xk ) / a11
1k 1k 1k
k =2 k =2 k =2
Ó!
n
znane: x(0) =(x1(0),..., xn(0))
x1(1) = (b1 - j = 1
k
"a x(0) ) / a11,
1k
szukane: x(1) =(x1(1),..., xn(1))
k =2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 86
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
// x(1:n,1) rozw. pocz.
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
for m = 1:m_max
m ty krok :
n
xj (m+1) = (bj -
k
"a x(m) ) / ajj , j = 1,2,...,n
jk
k =1,k `" j
znane: x(m) =(x1(m),..., xn(m))
szukane: x(m+1) =(x1(m+1),..., xn(m+1))
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 87
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
// x(1:n,1) rozw. pocz.
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
for m = 1:m_max
for j = 1:n
s = b(j)
m ty krok :
n
xj (m+1) = (bj -
k
"a x(m) ) / ajj , j = 1,2,...,n
jk
k =1,k `" j
znane: x(m) =(x1(m),..., xn(m))
szukane: x(m+1) =(x1(m+1),..., xn(m+1))
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 88
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
// x(1:n,1) rozw. pocz.
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
for m = 1:m_max
for j = 1:n
s = b(j)
m ty krok :
for k = 1:n
n
xj (m+1) = (bj -
k
"a x(m) ) / ajj , j = 1,2,...,n
jk
s = s a(j,k)*x(k,m)
k =1,k `" j
end
znane: x(m) =(x1(m),..., xn(m))
szukane: x(m+1) =(x1(m+1),..., xn(m+1))
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 89
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
// x(1:n,1) rozw. pocz.
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
for m = 1:m_max
for j = 1:n
s = b(j)
m ty krok :
for k = 1:n
n
if k != j then
xj (m+1) = (bj -
k
"a x(m) ) / ajj , j = 1,2,...,n
jk
s = s a(j,k)*x(k,m)
k =1,k `" j
end
end
znane: x(m) =(x1(m),..., xn(m))
szukane: x(m+1) =(x1(m+1),..., xn(m+1))
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 90
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Jacobiego
n
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ajj xj + j = 1,2,...,n,
"a xk = bj ,
jk
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
k =1,k `" j
ôÅ‚
21
òÅ‚
L
ôÅ‚
// x(1:n,1) rozw. pocz.
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
for m = 1:m_max
for j = 1:n
s = b(j)
m ty krok :
for k = 1:n
n
if k != j then
xj (m+1) = (bj -
k
"a x(m) ) / ajj , j = 1,2,...,n
jk
s = s a(j,k)*x(k,m)
k =1,k `" j
end
end
znane: x(m) =(x1(m),..., xn(m))
x(j,m +1) = s/a(j,j)
szukane: x(m+1) =(x1(m+1),..., xn(m+1))
end
end
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 91
Metody iteracyjne rozwiązywania układów równań liniowych
Metoda Jacobiego - przykład
4 1 1 1 x1 13 1 1
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚1 4 1 1śłïÅ‚x2 śł ïÅ‚16śł ïÅ‚1śł ïÅ‚2śł
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł, ïÅ‚ śł, xOK = ïÅ‚ śł
= x(0) =
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
1 1 4 1 x3 19 1 3
ïÅ‚
ïÅ‚1 1 1 4śłðÅ‚x4 śł ïÅ‚22śł ïÅ‚1śł ïÅ‚4śł
ðÅ‚ ûÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2.5 0.90 1.0004535
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚2.88śł ïÅ‚2.14śł ïÅ‚1.9999839śł
ïÅ‚ śł, x(2) = ïÅ‚ śł,..., x(6) = ïÅ‚ śł
x(1) =
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
3.16 3.15 2.999805
ïÅ‚3.37śł ïÅ‚3.95śł ïÅ‚3.9999394śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 92
Metody iteracyjne rozwiązywania układów równań liniowych
Metoda Jacobiego - przykład
0.1 1 1 1 x1 9.1 1 1
îÅ‚ Å‚Å‚îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚1śł ïÅ‚2śł
1 0.1 1 1śłïÅ‚x2 śł ïÅ‚8.2śł
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł, ïÅ‚ śł, ïÅ‚ śł
= x(0) = xOK =
ïÅ‚ śłïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
1 1 0.1 1 x3 7.3 1 3
ïÅ‚ śłïÅ‚ ïÅ‚ śł ïÅ‚ śł
1 1 1 0.1ûÅ‚ðÅ‚x4 śł ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚6.4ûÅ‚ ðÅ‚1ûÅ‚ ðÅ‚4ûÅ‚
61 400201
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ ïÅ‚
- 548śł - 3607298śł
ïÅ‚ śł, x(2) = ïÅ‚ śł,...
x(1) =
ïÅ‚ śł ïÅ‚ śł
4933 32515003
ïÅ‚- 44396śł ïÅ‚- 293E + 08śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 93
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Gaussa-Seidela
a11x1 + a12x2 +L+ a1nxn = b1
Å„Å‚
ôÅ‚a x1 + a22x2 +L+ a2nxn = b2
ôÅ‚
21
òÅ‚
L
ôÅ‚
ôÅ‚an1x1 + an2x2 +L+ annxn = bn
ół
j-1
n
j = 1,2,...,n,
"a xk + ajj xj + "a xk = bj ,
jk jk
k =1 k = j+1
j-1
n
(i+1) (i+1) (i)
j =1,2,...,n, i = 0,1,2...
"a xk + ajj xj + "a xk = bj ,
jk jk
k =1 k = j+1
j-1
n
(i+1) (i)
bj -
"a xk - "a xk
jk jk
k =1 k = j+1
xj (i+1) =
ajj
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 94
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda Gaussa-Seidela jest z reguły szybciej zbie\na ni\ metoda
Jacobiego
" istnieją układy dla których metoda Gaussa-Seidela jest rozbie\na,
a metoda Jacobiego zbie\na
" Metoda Jacobiego i metoda Gaussa-Seidela są zbie\ne jeśli
macierz A jest macierzą ze ściśle dominującą przekątną
główną, tzn.
n
| aii |> i, j = 1,..., n
"| aij |
j=1
j`"i
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 95
Metody iteracyjne
rozwiązywania układów równań liniowych
" metoda nadrelaksacji przyśpieszenie zbie\ności metody Gaussa-
Seidela
modyfikując wzór metody Gaussa-Seidela otrzymujemy
j-1 j-1
n n
(i+1) (i) (i+1) (i)
bj - bj -
"a xk - "a xk "a xk -"a xk + a xj(i)
jk jk jk jk jj
k =1 k = j+1 k =1 k = j
xj (i+1) = = ,
ajj ajj
j = 1,2,..., n, i = 0,1,2...
j-1
n
bj - xk (i+1) - xk (i)
"ajk "ajk
k =1 k = j
rj (i) = , xj (i+1) = xj (i) + rj (i)
ajj
xj (i+1) = xj (i) +Örj (i)
parametr relaksacji É dobrany jest tak, aby zbie\ność metody byÅ‚a jak
É
É
É
najszybsza (jeÅ›li É = 1 to metoda redukuje siÄ™ do metody Gaussa-Seidela
É
É
É
Zadanie: zapisz kod programu realizujÄ…cy metodÄ™ Gaussa-Seidela
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 96
Analiza błędów w układach równań liniowych
Złe uwarunkowanie układu równań
układ równań postaci A x = b
wartość obliczona
x
residuum r = b - Ax
x
wniosek : jeśli oszacowanie r jest małe to jest dobrym rozwiązaniem ?
Przykład
1,2969 0,8648 0,8642
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
A = b =
ïÅ‚0,2161 0,1441śł, ïÅ‚0,1440śł
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
x = [0,9911 - 0,4870]T
T
r =[-10-8 -10-8]
T
rozw. x = [2 - 2]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 97
Przykład złego uwarunkowania zadania
2x + 6y = 8 x =1
Ò!
2x + 6.000000001y = 8.000000001 y = 1
" WE: a11 a12 a21 a22 b1 b2 WY: x,y
2x + 6y = 8 x =10
Ò!
2x + 5.999999999y = 8.000000002 y = -2
2
2
1.5
1.5
1
1
0.5 0.5
0 0
0 2 4 6 8 10 12 0 2 4 6 8 10 12
-0.5 -0.5
-1 -1
-1.5
-1.5
|| A ||= 6
-2
-2
-2.5
-2.5
-3
-3
|| A-1 ||= 3.0E + 08
º (A) =|| A || Å" || A-1 ||
wskaznik uwarunkowania macierzy A
jeśli jest on du\y, to małe zaburzenia względne macierzy Ai wektora bmogą powodować du\e zaburzenia
względne wektora x, zadanie jest zle uwarunkowane
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 98
Zadanie numeryczne
Matematyczny opis powiązań pomiędzy danymi wejściowymi i wyjściowymi
(sposób wyznaczenia wyników na podstawie danych wejściowych).
Zadanie jest dobrze określone jeśli wyniki są jednoznacznie określone dla
przyjętych danych wejściowych
Uwarunkowanie zadania numerycznego
" jak bardzo wynik f( +Dx) ró\ni się od f( )
f(x+D ) f(x)
f( +D ) f( )
f( +D ) f( )
" x dane wejściowe
" f- zadanie numeryczne
" y=f(x ) wynik, D f(x+D ) - f(x)
Dy= f( +Dx) f( )
D f( +D ) f( )
D f( +D ) f( )
"y "x
Jeśli to zadanie jest zle uwarunkowane
*#*#
y x
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 99
Przykład in\ynierski zadanie kratownicy
(metoda równowa\enia węzłów)
1x : Rx + NI + NIII cosÄ… = 0
1y : Ry + NIII sinÄ… = 0
2x : -NI + NII = 0
2y : NV = P
Zadanie: przygotuj arkusz MS Excel
rozwiÄ…zujÄ…cy zadanie kratownicy
(przyjąć długości d12=d23=d24=1,
P = 100kN)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 100
Pojęcie układu równań liniowych
Funkcje SciLaba
" inv() obliczenie macierzy odwrotnej
" linsolve() rozwiązanie układu równań liniowych dowolnej postaci
" lu() rozkład LU eliminacji Gaussa
" chol() rozkład Cholesky'ego
" sparse() formowanie macierzy rzadkich
" full() sformowanie pełnej macierzy w oparciu o profil macierzy
rzadkiej
" lusolve() rozwiązanie układu równań liniowych z macierzą rzadką
" chfact() rozkład Cholesky'ego dla macierzy rzadkich
" chsolve() rozwiązanie układu równań liniowych z macierzą rzadką za
pomocÄ… metody Cholesky'ego
" spchol() rozkład Cholesky'ego dla macierzy rzadkich
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 101
Pojęcie układu równań liniowych
Procedury w języku FORTRAN
( L A P A C K)
( L -A P -A C -K)
( L A P A -C -K)
( L -A P -A -C K)
" LAPACK (Linear Algebra PACKage),
( L A -P -A C K)
LINPACK
( L -A -P A C -K)
biblioteki procedur słu\ących do
rozwiązywania układów równań liniowych i
metody najmniejszych kwadratów
http://www.netlib.org/lapack/
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 102
Podsumowanie
Metody rozwiązywania układów równań liniowych.
" Sformułowanie zagadnienia, podstawowe pojęcia
macierz główna układu, macierz rozszerzona,
twierdzenie Kroneckera-Capellego,
pojecie rzędu macierzy.
" Podział metod rozwiązywania układów równań liniowych:
bezpośrednie
iteracyjne
" Sposoby rozwiązań przy u\yciu metod bezpośrednich
z zastosowaniem macierzy odwrotnej,
za pomocą wzorów Cramera,
układ równań z macierzą trójkątną.
" Eliminacja Gaussa
eliminacja zmiennych,
postępowanie odwrotne,
wybór elementu podstawowego,
metoda eliminacji Gaussa-Jordana,
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 1
Nr: 103
Podsumowanie c.d.
Metody rozwiązywania układów równań liniowych.
" Rozkład trójkątny macierzy
sposób postepowania,
metoda Doolitle a,
metoda Crouta,
rozkład Cholesky ego,
" Metoda sprzę\onych gradientów.
" Metoda wielo-frontalna (metody blokowe)
" Analiza błędów
złe uwarunkowanie układu równań
wskaznik uwarunkowania macierzy A
ulepszanie iteracyjne rozwiązania (metoda iteracji powtórnej)
" Metody iteracyjne
metoda Jacobiego,
metoda Gaussa-Seidela,
metoda nadrelaksacji
Wyszukiwarka
Podobne podstrony:
2008 Metody obliczeniowe 10 D 2008 11 28 20 51 402008 Metody obliczeniowe 01 D 2008 10 1 21 19 292008 Metody obliczeniowe 03 D 2008 10 1 22 5 472008 Metody obliczeniowe 06 D 2008 10 22 20 13 232008 Metody obliczeniowe 02 D 2008 10 1 21 28 52008 Metody obliczeniowe 07 D 2008 10 29 19 28 12008 Metody obliczeniowe 13 D 2008 11 28 20 56 53metody obliczeniowe wykład 2Metody egzamin 10?Prąd Stały Wzory, Twierdzenia, Metody ObliczenioweMetodyka obliczania przepływów i opadów maksymalnychStukow M, Szepietowski B Metody obliczania całekmetody obliczeniowe zad(2639) metody obliczeniowe?9 przepusty w infratrukturze metody obliczeń cz12008 Metody obliczeniowe 08 D 2008 11 11 21 31 58więcej podobnych podstron