Zakres zagadnień
Algebra
1 Macierze w fotografii cyfrowej
Układy równań liniowych
2 Układy równań liniowych
3 Postać macierzowa układu równań liniowych
Adam Dąbrowski
4 Macierz rozszerzona
Politechnika Poznańska
Wydział Informatyki i Zarządzania
5 Twierdzenie Kroneckera-Capellego
Katedra Sterowania i Inżynierii Systemów
Pracownia Układów Elektronicznych i Przetwarzania Sygnałów
6 Minory i rząd macierzy
7 Rozwiązywanie układów równań liniowych
31 stycznia 2009
8 Kwadratowe układy równań  wzory Cramera
9 Jednorodne układy równań
10 Przykład analizy prostego obwodu elektrycznego
11 Trójkątne układy równań liniowych
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 1 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 2 / 55
Duże tablice liczb w technice Macierze w fotografii cyfrowej
Matryce aparatów cyfrowych Nikon
Macierze w fotografii cyfrowej
Na obecnym przez
roczu pokazano matrycę aparatu Nikon D200. Obie
przedstawione matryce są wykonane w technologii CCD (ang. charge
coupled device) w standardzie Nikon DX, tzn. mają wymiary: 23.6 � 15.8
We współczesnej technice stosuje się przyrządy, które rejestrują
mm. Rejestrują macierze zawierające 3872 � 2592 = 10 036 224 liczb (tzw.
i przechowują macierze (dwuwymiarowe tablice liczb) o dużych rozmiarach.
pikseli, ściślej  peli), a właściwie 10.92 mln peli brutto.
Dobrym przykładem są monitory komputerowe, monitory telewizyjne oraz
Trzy takie macierze, odpowiadające trzem składowym RGB (red 
matryce cyfrowych aparatów fotograficznych. Na tytułowym przez
roczu
czerwony, green  zielony, blue  niebieski) tworzą dopiero właściwą
pokazano matrycę aparatu cyfrowego Nikon D80. Na obecnym zdjęciu ten
fotografię cyfrową zapisywaną np. w formacie tzw.  bitmapy .
aparat jest przedstawiony wraz z typowymi akcesoriami.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 3 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 4 / 55
Macierze w fotografii cyfrowej Macierze w fotografii cyfrowej
Przetwarzanie sygnału w aparacie cyfrowym Nikon D200 Wzór mozaikowy Bayera
Nad matrycą jest umieszczona płytka mozaikowego filtru optycznego RGB, Macierz liczb zarejestrowanych podczas wykonywania zdjecia aparatem
dzięki której połowa peli matrycy rejestruje składową zieloną (G), 1/4  cyfrowym jest nazywana fotografią w tzw. formacie RAWa
czerwoną (R) i 1/4  niebieską (B)a. Aparat cyfrowy rejestruje więc W tym miejscu ten wywód musimy niestety przerwać i wrócić do węziej
zaledwie 1/3 danych potrzebnych do utworzenia fotografii, a 2/3 oblicza rozumianej algebry. Na dalszy ciąg, na wykładzie z Technik Telewizyjnych
poprzez interpolację, np. uzupełniając brakujące dane poprzez wartości i Multimedialnych, zapraszam Tych z Państwa, którzy wybiorą specjalność
średnie sąsiednich zarejestrowanych peli.
MULTIMEDIA
a
Te proporcje odzwierciedlają fakt, że ludzki wzrok jest najbardziej czuły na barwę
a
zieloną. Wyraz  raw oznacza w języku angielskim  surowy , czyli nieprzetworzony.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 5 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 6 / 55
Układy równań liniowych Postać macierzowa układu równań liniowych
Definicje macierzy
Układ równań liniowych
W celu uzyskania postaci macierzowej rozważanego układu równań
Układ m równań liniowych z n niewiadomymi xl, l = 1, 2, . . . , n, to zestaw liniowych definiujemy nastepujące macierze (i wektory)
m kombinacji liniowych z tymi elementami, przyrównanych do zadanych
elementów bk, k = 1, 2, . . . , m. Elementy bk są nazywane wyrazami Macierz Wektor Wektor wyrazów
wolnymi, w odróżnieniu od skalarów akl, które z kolei nazywa się współczynników niewiadomych wolnych
współczynnikami układu równań
Ą# ń# Ą# ń# Ą# ń#
ż# a11 a12 � � � a1n x1 b1
ó#
�# a11x1 + a12x2 + � � � + a1nxn = b1
�#
a21 a22 � � � a2n Ą# ó# x2 Ą# ó# b2 Ą#
ó# Ą# ó# Ą# ó# Ą#
�#
�#
ó# Ą# ó# Ą# ó# Ą#
a21x1 + a22x2 + � � � + a2nxn = b2 A = x = b =
. .
.
ó# Ą# ó# Ą# ó# Ą#
. . .
.
.
Ł# Ś# Ł# . Ś# Ł# . Ś#
�# ......................................... ...
�#
�#
�#
am1 am2 � � � amn xn bm
am1x1 + am2x2 + � � � + amnxn = bm
Równanie macierzowe
Rozwiązaniem układu jest każda uporządkowana n-tka elementów xl, która
Stosując powyższe oznaczenia rozważany układ równań przyjmuje postać
spełnia wszystkie zapisane powyżej równania, czyli przekształca je
równania macierzowego
wrówności.
Ax = b
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 7 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 8 / 55
Macierz rozszerzona Istnienie i jednoznaczność rozwiązań
Definicja macierzy rozszerzonej
Twierdzenie Kroneckera-Capellego
Układ równań liniowych jest w pełni określony poprzez macierz
Niech elementy macierzy rozszerzonej układu równań liniowych neleżą do
współczynników A (nazywaną również macierzą główną układu) oraz przez
ciała nieskończonego (np. liczb rzeczywistych lub liczb zespolonych). W
wektor wyrazów wolnych b. Macierz B powstająca przez ich połączenie w
tym ciele ten układ równań ma rozwiązanie wtedy i tylko wtedy, gdy rząd
jedną macierz B =[A|b] nosi nazwę macierzy rozszerzonej układu i także
macierzy głównej jest równy rzędowi macierzy rozszerzonej.
jednoznacznie określa ten układ równań
Jeżeli rzędy te są przy tym równe liczbie niewiadomych, to ten układ ma
dokładnie jedno rozwiązanie.
Macierz Macierz
Jeżeli rzędy te są równe, lecz mniejsze od liczby niewiadomych, to ten
główna rozszerzona
układ ma nieskończenie wiele rozwiązań zależnych od n - r parametrów,
Ą# ń# Ą# ń#
przy czym n  liczba niewiadomych, r  rząd macierzy głównej i macierzy
a11 a12 � � � a1n a11 a12 � � � a1n b1
ó# rozszerzonej.
a21 a22 � � � a2n Ą# ó# a21 a22 � � � a2n b2 Ą#
ó# Ą# ó# Ą#
ó# Ą# ó# Ą#
A = B = Rozważany układ równań liniowych nie ma rozwiązań (jest sprzeczny), jeśli
. .
ó# Ą# ó# Ą#
. .
. .
Ł# Ś# Ł# Ś#
rzędy macierzy głównej i macierzy rozszerzonej układu są różne.
am1 am2 � � � amn am1 am2 � � � amn bm
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 9 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 10 / 55
Alfred Capelli Przypomnienie pojęć rzędu i minora macierzy
Definicja rzędu macierzy
Oznaczmy przez c1, c2, . . . , cn kolumny macierzy A, czyli
A =[c1, c2, . . . , cn] .
Rzędem macierzy A (oznaczanym rank A) nazywamy wymiar przestrzeni
liniowej rozpiętej na jej kolumnach, czyli
rank A = dim span {c1, c2, . . . , cn} .
Alfred Capelli urodził się 5. sierpnia 1855 r. w Mediolanie (w roku śmierci
Adama Mickiewicza, tam, gdzie nasz wieszcz utworzył polski legion)
Definicja minora macierzy
a zmarł 28. stycznia 1910 r. w Neapolu. Był profesorem w uniwersytetach
Minorem macierzy A nazywamy wyznacznik M macierzy kwadratowej M
w Palermo i w Neapolu.
otrzymanej z macierzy A poprzez skreślenie pewnej liczby jej wierszy
Na marginesie: Przyczyna śmierci Adama Mickiewicza jest nieznana, choć
i pewnej liczby jej kolumn. Stopień macierzy M jest nazywany stopniem
prawdopodobnie była nią azjatycka odmiana cholery. Celem legionu Mickiewicza
minora M.
było uczestnictwo w walkach z Austrią o wyzwolenie Włoch.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 11 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 12 / 55
Wyznaczanie rzędu macierzy Wyznaczanie rzędu macierzy
Twierdzenie Twierdzenie
Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera
minora tej macierzy. minora tej macierzy.
Przykład Przykład
Ą# ń# Ą# ń#
1 1 3 1 1 1 3 1
ó# Ą# ó# Ą#
2 1 0 -1 2 1 0 -1
ó# Ą# ó# Ą#
A = ó# Ą# A = ó# Ą#
Ł# 3 2 3 0 Ś# Ł# 3 2 3 0 Ś#
-1 0 3 2 -1 0 3 2


1 1 1 1

|1| = 1 = 0 , = -1 = 0 |1| = 1 = 0 , = -1 = 0


2 1 2 1


1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1


2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0 2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0


3 2 3 3 2 0 -1 0 3 -1 0 2 3 2 3 3 2 0 -1 0 3 -1 0 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 13 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 14 / 55
Wyznaczanie rzędu macierzy Wyznaczanie rzędu macierzy
Twierdzenie Twierdzenie
Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera
minora tej macierzy. minora tej macierzy.
Przykład Przykład
Ą# ń# Ą# ń#
1 1 3 1 1 1 3 1
ó# Ą# ó# Ą#
2 1 0 -1 2 1 0 -1
ó# Ą# ó# Ą#
A = ó# Ą# A = ó# Ą#
Ł# 3 2 3 0 Ś# Ł# 3 2 3 0 Ś#
-1 0 3 2 -1 0 3 2


1 1 1 1

|1| = 1 = 0 , = -1 = 0 |1| = 1 = 0 , = -1 = 0


2 1 2 1


1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1


2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0 2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0


3 2 3 3 2 0 -1 0 3 -1 0 2 3 2 3 3 2 0 -1 0 3 -1 0 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 15 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 16 / 55
Wyznaczanie rzędu macierzy Wyznaczanie rzędu macierzy
Twierdzenie Twierdzenie
Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera
minora tej macierzy. minora tej macierzy.
Przykład Przykład
Ą# ń# Ą# ń#
1 1 3 1 1 1 3 1
ó# Ą# ó# Ą#
2 1 0 -1 2 1 0 -1
ó# Ą# ó# Ą#
A = ó# Ą# A = ó# Ą#
Ł# 3 2 3 0 Ś# Ł# 3 2 3 0 Ś#
-1 0 3 2 -1 0 3 2


1 1 1 1

|1| = 1 = 0 , = -1 = 0 |1| = 1 = 0 , = -1 = 0


2 1 2 1


1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1


2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0 2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0


3 2 3 3 2 0 -1 0 3 -1 0 2 3 2 3 3 2 0 -1 0 3 -1 0 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 17 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 18 / 55
Wyznaczanie rzędu macierzy Wyznaczanie rzędu macierzy
Twierdzenie Twierdzenie
Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera Rząd macierzy jest równy maksymalnemu stopniowi różnego od zera
minora tej macierzy. minora tej macierzy.
Przykład Przykład
Ą# ń# Ą# ń#
1 1 3 1 1 1 3 1
ó# Ą# ó# Ą#
2 1 0 -1 2 1 0 -1
ó# Ą# ó# Ą#
A = ó# Ą# A = ó# Ą# , zatem rank A = 2
Ł# 3 2 3 0 Ś# Ł# 3 2 3 0 Ś#
-1 0 3 2 -1 0 3 2


1 1 1 1

|1| = 1 = 0 , = -1 = 0 |1| = 1 = 0 , = -1 = 0


2 1 2 1


1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1


2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0 2 1 0 =0, 2 1 -1 =0, 2 1 0 =0, 2 1 -1 =0


3 2 3 3 2 0 -1 0 3 -1 0 2 3 2 3 3 2 0 -1 0 3 -1 0 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 19 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 20 / 55
Zastosowanie twierdzenia Kroneckera-Capellego Zastosowanie twierdzenia Kroneckera-Capellego
Sprawdzić istnienie rozwiązania układu równań Tworzymy macierz rozszerzoną
B =[A|b] .
x1 + x2 + 3x3 + x4 = 2
Ponieważ
2x1 + x2 - x4 = 3
rank A = rank B = 2 = 4 - 2
3x1 + 2x2 + 3x3 = 5
rozpatrywany układ równań ma rozwiązania, które zależą od 4 - 2 = 2
-x1 + 3x3 + 2x4 = -1
parametrów. Stąd, że


Ten układ równań zapisujemy w postaci 1 1


= -1 = 0

2 1
Ax = b
wynika, że wystarczy rozwiązać układ równań
przy czym
x1 + x2 + 3x3 + x4 = 2
Ą# ń# Ą# ń# Ą# ń#
1 1 3 1 x1 2 2x1 + x2 - x4 = 3
ó# Ą# ó# Ą# ó# Ą#
2 1 0 -1 x2 3
ó# Ą# ó# Ą# ó# Ą#
czyli
A = ó# Ą# , x = ó# Ą# , b = ó# Ą#
Ł# 3 2 3 0 Ś# Ł# x3 Ś# Ł# 5 Ś#
x1 + x2 = -3x3 - x4 + 2
-1 0 3 2 x4 -1
2x1 + x2 = x4 + 3
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 21 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 22 / 55
Rozwiązywanie układów równań liniowych Rozwiązywanie kwadratowego układu równań liniowych
Kwadratowy układ równań liniowych
Uwagi
Jeżeli n = m (liczba niewiadomych n jest równa liczbie równań m), to
Do rozwiązania układu Ax = b prowadzi sekwencja przekształceń
układ równań nazywamy kwadratowym. Układ ten ma jedno rozwiązanie
A-1Ax = A-1b
wtedy i tylko wtedy, gdy macierz główna A układu jest nieosobliwa, czyli
ma wyznacznik różny od zera (det A = 0), czyli ma maksymalny rząd

x = A-1b
(równy n), czyli istnieje macierz odwrotna A-1.
Rozwiązanie możemy zapisać w postaci
W środowisku Matlab wyrażenie A-1b zapisuje się jako A\b
Alternatywnie powyższy układ równań można zapisać jako
x = A-1b
x A = b
a jego rozwiązanie  jako
Uwaga
Zapis
x = b A -1
x = bA-1
W systemie Matlab wyrażenie b A -1 należy zapisać jako b /A
jest błędny ze względu na nieprzemienność mnożenia macierzy.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 23 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 24 / 55
Rozwiązywanie kwadratowego układu równań liniowych Gabriel Cramer
Wzory Cramera
Oznaczmy przez Al macierz powstałą przez zastąpienie l-tej kolumny
macierzy głównej A układu n równań o n niewiadomych
Ax = b
wektorem wyrazów wolnych b, czyli
Ą# ń#
a11 a12 � � � a1(l-1) b1 a1(l+1) � � � a1n
ó#
a21 a22 � � � a2(l-1) b2 a2(l+1) � � � a2n Ą#
ó# Ą#
ó# Ą#
Al =
ó# . . Ą#
. .
. .
Ł# Ś#
Gabriel Cramer urodził się 31. lipca 1704 r.w Genewie. Od dzieciństwa
an1 an2 � � � an(l-1) bn an(l+1) � � � ann
wykazywał zdolności matematyczne. Doktorat uzyskał już w wieku 18 lat.
Główne wyniki, dzięki którym jest do dziś sławny, uzyskał w wieku lat
l-tą niewiadomą xl można obliczyć za pomocą następującego wzoru
40-tu.
Cramera
Gabriel Cramer zmarł 4. stycznia 1752 r. w Bagnols na południu Francji.
det Al
xl = , det A = 0 , l = 1, 2, . . . , n

det A
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 25 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 26 / 55
Zastosowanie wzorów Cramera Zastosowanie wzorów Cramera
Stosując wzory Cramera do układu równań
Wprowadzając parametry ą i �, rozwiązanie rozpatrywanego układu
równań
x1 + x2 = -3x3 - x4 + 2
2x1 + x2 = x4 + 3
x1 + x2 + 3x3 + x4 = 2
2x1 + x2 - x4 = 3
otrzymuje się

3x1 + 2x2 + 3x3 = 5

-3x3 - x4 + 2 1


-x1 + 3x3 + 2x4 = -1
x4 + 3 1

x1 = = 3x3 + x4 - 2 + x4 + 3 = 3x3 + 2x4 + 1

1 1
ma postać


2 1
x1 = 3ą + 2� + 1


1
-3x3 - x4 + 2
x2 = -6ą - 3� + 1

2 x4 + 3
x3 = ą
-x4 - 3 - 6x3 - 2x4 + 4 = -6x3 - 3x4 + 1
x2 = =

1 1

x4 = �


2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 27 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 28 / 55
Rozwiązania jednorodnego układu równań liniowych Przykład analizy prostego obwodu elektrycznego
V3

Przykład
R5 R6
Jednorodny układ równań liniowych

Wobwodzie elektrycznympokazanymna


Układ równań liniowych Ax = b nazywamy jednorodnym, gdy wszystkie
V1 rysunku obok znamy wszystkie rezystancje


wyrazy wolne tego układu są równe zeru, tzn. gdy b = 0.

R1 R3 R1, R2, . . . , R6 oraz napięcie z
ródła
U2 - U1, a nawet potencjały U1 i U2 obu
Jednorodny układ równań liniowych ma zawsze rozwiązanie zerowe




węzłów, do których jest dołączone to
x = 0.


U1 R2 V2 z
ródło.
Kwadratowy liniowy układ jednorodny ma rozwiązania niezerowe


Należy obliczyć nieznane potencjały
wtedy i tylko wtedy, gdy wyznacznik macierzy głównej A jest równy





R4 V1, V2, V3 pozostałych węzłów tego
zero.


obwodu.
U2
Zadanie to wykonamy tzw.  metodą
potencjałów węzłowych .
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 29 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 30 / 55
Analiza obwodów elektrycznych Analiza obwodów elektrycznych
Gustav Robert Kirchhoff
Prawa Kirchhoffa i prawo Ohma
W celu przeprowadzenia analizy obwodu elektrycznego należy wykorzystać
tzw. prawa Kirchhoffa i prawo Ohma.
Pierwsze prawo Kirchhoffa: suma wszystkich prądów wypływających z
każdego węzła obwodu elektrycznego jest równa zeru.
Drugie prawo Kirchhoffa: suma wszystkich napięć wzdłuż dowolnej
drogi zamkniętej w obwodzie elektrycznym jest równa zeru.
Prawo Ohma: napięcie na zaciskach rezystora jest proporcjonalne do
przepływającego przez ten rezystor prądu. Współczynnik
Gustav Robert Kirchhoff urodził się 12. marca 1824 r. w Królewcu, zmarł
proporcjonalności nosi nazwę rezystancji.
17. paz
dziernika 1887 r. w Berlinie.
Kirchhoff badał zjawiska elektryczne, elektromechaniczne, mechaniczne
Ueaga
(np. sprężystość ciał, mechanikę płynów), cieplne i optyczne. Jest twórcą
Dzięki temu, że posługujemy się potencjałami węzłów, spełniamy drugie podstaw fizyki matematycznej. Sformułował prawa opisujące zjawiska w
prawo Kirchhoffa. Ograniczymy się więc do pierwszego prawa, wypisując obwodach elektrycznych, tzw.  prawa Kirchhoffa oraz prawo
odpowiednie równania dla wezłów z uwzględnieniem prawa Ohma. promieniowania ciał w zależności od temperatury.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 31 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 32 / 55
Analiza obwodów elektrycznych Analiza obwodów elektrycznych
Gustav Robert Kirchhoff
Georg Simon Ohm
Kirchhoff wraz z Robertem Bunsenem wydobył z zapomnienia i docenił
wagę jednego z największych odkryć ludzkości, jakim jest przekształcenie
Fouriera, 35 lat po śmierci Jean a Baptiste a Joseph a Fouriera w 1830 r.
Dzięki dokonaniom Fouriera Kirchhoff i Bunsen opracowali metodę analizy
spektralnej (spektroskopię), za pomocą której odkryli dwa nowe
Georg Simon Ohm urodził się 16. marca 1787 r. w Erlangen, a zmarł 7.
pierwiastki: rubid i cez.
lipca 1854 r. w Monachium.
Kirchhoff był członkiem Berlińskiej, Paryskiej i Petersburskiej Akademii
Był profesorem fizyki na Politechnice w Norymberdze w latach 1833-1849
Nauk, a także  profesorem fizyki na uniwersytetach we Wrocławiu
i na Uniwersytecie w Monachium po roku 1849.
(1850-1854), Heidelbergu (1854-1875) i Berlinie (od 1876 r. do śmierci).
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 33 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 34 / 55
Analiza obwodów elektrycznych Przykład analizy prostego obwodu elektrycznego
Georg Simon Ohm
V3

Przykład
R5 R6

Z pierwszego prawa Kirchhoffa, po



V1 zastosowaniu prawa Ohma, wynikają


następujące równania:

R1 R3




V1 - U1 V1 - U2 V1 - V2
+ + = 0

R1 R2 R3
U1 R2 V2
Ohm zajmował się badaniem zjawisk elektrycznych i akustycznych. W



1826 r. sformułował i udowodnił tzw.  prawo Ohma opisujące związek
V2 - V1 V2 - U2 V2 - V3






+ + = 0
pomiędzy napięciem elektrycznym a natężeniem prądu elektrycznego w R4

R3 R4 R6


przewodniku. Badał także nagrzewanie się przewodników pod wpływem
V3 - U1 V3 - V2
U2
prądu elektrycznego. Na jego cześć jednostce rezystancji nadano nazwę
+ = 0
R5 R6
Ohm [&!].
W 1843 r. odkrył, że proces słyszenia polega na rozkładzie dz
więków na
składowe harmoniczne.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 35 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 36 / 55
Przykład analizy prostego obwodu elektrycznego Przykład analizy prostego obwodu elektrycznego
V3
V3


Przykład
Przykład
R5 R6
R5 R6

Po uporządkowaniu otrzymuje się podane


Zależności te można zapisać w następującej



V1 poniżej zależności:


V1 postaci macierzowej:




R1 R3
R1 R3


YV = J







U1 R2 V2

U1 R2 V2 przy czym




Ą# ń#

1 1 1 1



+ + - 0

R4 R3


R4 ó# R1 R21 R3 1 1 1 1 Ą#


Y = - + + - Ś#

Ł#
R3 R3 R4 R6 R6

1 1 1
U2
0 - +
U2
R6 R5 R6

1 1 1 1 U1 U2
+ + V1 - V2 = +
Ą# ń# Ą# ń#
R1 R2 R3 R3 R1 R2
U1 U2

+
V1
1 1 1 1 1 U2 R1 R2
- V1 + + + V2 - V3 = ó# ó# Ą#
U2
R3 R3 R4 R6 R6 R4
V = V2 Ą# , J =
Ł# Ś# Ł# Ś#
R4
1 1 1 U1
U1
- V2 + + V3 =
V3
R6 R5 R6 R5
R5
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 37 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 38 / 55
Reguły tworzenia macierzy admitancyjnej Y Reguły tworzenia wektora wyrazów wolnych J
V3
Przykład

V3
R5 R6 Reguły tworzenia macierzy admitancyjnej

(konduktancyjneja) Y: Przykład


R5 R6

V1
Reguły tworzenia wektora wyrazów
k-ty element głównej przekątnej



macierzy admitancyjnej jest sumą V1 wolnych J:

R1 R3

admitancji (konduktancji) gałęzi

k-ty element wektora wyrazów

R1 R3
incydentnych z k-tym węzłem,
wolnych jest prądem wstrzykiwanym



U1 R2 V2

elementy w k-tym wierszu i l-tej (dopływającym) do k-tego węzła ze


U1 R2 V2 z
ródeł energii elektrycznej.


kolumnie oraz w l-tym wierszu i k-tej



R4

kolumnie macierzy admitancyjnej są







R4
przeciwne do sumy admitancji
U2


(konduktancji) gałęzi incydentnych z
U2
węzłami k-tym i l-tym.
a
Konduktancja jest odwrotnością rezystancji.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 39 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 40 / 55
Trójkątne układy równań liniowych Trójkątne układy równań liniowych
Dolnotrójkątny układ równań
Dolnotrójkątny układ równań
Dolnotrójkatna macierz G jest równa
Rozważmy układ równań
Ą# ń#
g11 0 0 � � � 0
g11y1 = b1
ó# Ą#
g21 g22 0 � � � 0
g21y1 + g22y2 = b2 ó# Ą#
ó# Ą#
.
ó# Ą#
g31y1 + g32y2 + g33y3 = b3 .
G = ó# g31 g32 g33 � � � . Ą# .
. ó# Ą#
.
. .
ó# . Ą#
.
. .
Ł# .
0 Ś#
gn1y1 + gn2y2 + gn3y3 + � � � + gnnyn = bn
gn1 gn2 gn3 � � � gnn
W formie macierzowej ten układ zapisujemy jako
Układ równań
Gy = b
Gy = b
ma jednoznaczne rozwiązanie wtedy i tylko wtedy, gdy wszystkie elementy
przy czym macierz G jest dolnotrójkatna.
głównej przekątnej macierzy G są różne od zera.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 41 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 42 / 55
Dolnotrójkątny układ równań liniowych Dolnotrójkątny układ równań liniowych
Algorytm podstawiania w przód Założenia
Pisząc program komputerowy, realizujący algorytm podstawiania w przód
Dolnotrójkątny układ równań liniowych rozwiązujemy za pomocą
(w tzw. wersji wierszowej) należy zauważyć, że parametr b1 jest
algorytmu podstawiania w przód
wykorzystywany wyłącznie przy obliczaniu niewiadomej y1, b2  przy
b1
obliczaniu y2 itd. Ogólnie, po obliczeniu niewiadomej yk, parametr bk nie
y1 =
g11
jest już potrzebny. Zatem obliczany wektor y może być zapisany w pamięci
b2 - g21y1
y2 = w miejsce wektora b. Zmienne yk nie są więc w ogóle potrzebne.
g22
b3 - g31y1 - g32y2
y3 =
Algorytm podstawiania w przód
g33 ,
.
. for k = 1, . . . , n
.
Ą#
k-1
if gkk = 0, set error flag, exit
bk - gkiyi
i=1
ó#
yk =
for i = 1, . . . , k - 1 (nie wykonywane, jeśli k = 1)
ó#

gkk
ó#
. Ł# bk �! bk - gkibi
.
.
bk �! bk/gkk
exit
przy czym zakładamy, że gkk = 0, k = 1, 2, . . . , n.

Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 43 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 44 / 55
Algorytm podstawiania w przód Algorytm podstawiania w przód
Koszt obliczeniowy
Koszt obliczeniowy algorytmów określa się, badając sposób
przyrastania liczby operacji wraz ze wzrostem wymiaru problemu,
czyli podając tzw. złożoność obliczeniową algorytmu.
Koszt obliczeniowy
Ten problem można uprościć do analizy liczby tzw. flopów. Jeden flop
Poza pętlą wewnetrzną parametr gkk jest n razy porównywany z
(ang. floating-point operation) składa się z jednego mnożenia
zerem oraz jest wykonywanych n dzieleń.
zmiennoprzecinkowego i z jednego dodawania (odejmowania)
Niezależnie od kosztu obliczeniowego tych operacji, całkowity koszt
zmiennoprzecinkowego.
ich wykonania rośnie liniowo wraz z wymiarem problemu n, a zatemw
k-ta wewnętrzna pętla  for algorytmu podstawiania w przód zawiera
porównaniu z liczbą n2/2 jest do pominięcia.
k - 1 flopów
Reasumując, można przyjąć, że
Pętla wewnętrzna jest wykonywana n razy w pętli zewnętrznej
koszt obliczeniowy algorytmu podstawiania w przód to n2/2 flopów.
(k = 1, . . . , n), czyli całkowita liczba flopów wykonywanych w pętli
wewnętrznej, to
n(n - 1) n2
0 + 1 + 2 + � � � +(n - 1) = H"
2 2
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 45 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 46 / 55
Dolnotrójkątny układ równań liniowych Dolnotrójkątny układ równań liniowych
Przypadek szczególny
Załóżmy, że b1 = b2 = � � � = bk = 0, czyli
Rekursywny algorytm podstawiania w przód

k 0 k y1
Zapiszmy dolnotrójkątny układ równań
b = , y = ,
n - k b2 n - k y2
Gy = b
k n - k

jako
k G11 0

G = .
g11 0 y1 b1
n - k G21 G22
= .
Ć
%

w
b
Azatem

G11 0 y1 0 Ć
przy czym %
, w
i b są wektorami o n - 1 elementach, a 
jest macierzą
= .
G21 G22 y2 b2
kwadratową stopnia n - 1.
Stąd y1 = 0 i do rozwiązania pozostaje jedynie układ
G22y2 = b2 o koszcie (n - k)2/2 flopów.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 47 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 48 / 55
Dolnotrójkątny układ równań liniowych Dolnotrójkątny układ równań liniowych
Algorytm podstawiania w przód w wersji kolumnowej
Rekursywny algorytm podstawiania w przód
Algorytm rekursywny można wyrazić w tzw. nierekursywnej postaci
Rozwiązanie układu równań Gy = b, czyli
kolumnowej, używając przy tym tej samej tablicy pierwotnie do

Ć �
g11 0 y1 b1 przechowywania b, następnie b, b, etc., a ostatecznie y.
= .
Ć
%

w
b
for i = 1, . . . , n
Ą#
if gii = 0, set error flag, exit
można zapisać za pomocą następującego algorytmu rekursywnego
ó#
bi �! bi/gii (to jest yi )
ó#
ó#
y1 = b1/g11
for k = i + 1, . . . , n (nie wykonywane, jeśli i = n)
Ł#

� Ć
b = b - %
y1
bk �! bk - gkibi
�
rozwiązać 
w
= b
exit
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 49 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 50 / 55
Algorytm podstawiania w przód w wersji kolumnowej Algorytm podstawiania w przód w wersji kolumnowej
Przykład
Następnie należy rozwiązać układ równań
Przykład
�

w
= b
Rozwiązać układ równań

Ą# ń# Ą# ń# Ą# ń#
5 0 0 y1 15 -4 0 y2 -8
=
ó# Ą# ó# ó# Ą#
2 Ś# Ł# Ś# Ł# Ś#
Ł# -4 0 y2 Ą# = -2 2 3 y3 7
1 2 3 y3 10
y2 = -8/ - 4 = 2
za pomocą algorytmu podstawiania w przód w wersji kolumnowej.
� Ć
� Ć Ć
b = b - %
y2 =[7] - [2]2 =[3]
y1 = 15/5 = 3
[3][y3] =[3] czyli y3 = 3/3 = 1

-2 2 -8
� Ć Ostatecznie
b = b - %
y1 = - 3 = Ą# ń#
10 1 7
3
ó# Ą#
y = 2 .
Ł# Ś#
1
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 51 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 52 / 55
Trójkątne układy równań liniowych Górnotrójkątny układ równań liniowych
Górnotrójkątny układ równań
Rozważmy układ równań Algorytm podstawiania wstecz
Górnotrójkątne układy równań liniowych rozwiązuje się za pomocą
u11x1 + u12x2 + � � � + u1(n-1)xn-1 + u1nxn = y1
algorytmu podstawiania wstecz, tj. poczynając od ostatniego
u22x2 + � � � + u2(n-1)xn-1 + u2nxn = y2
równania i cofając się kolejno do równania pierwszego.
.
.
. .
.
.
Analogicznie jak w przypadku algorytmu podstawiania w przód
u(n-1)(n-1)xn-1 + u(n-1)nxn = yn-1
istnieją dwie wersje algorytmu podstawiania wstecz: wersja wierszowa
unnxn = yn
i wersja kolumnowa (w tym wersja rekursywna).
Koszt obliczeniowy algorytmu podstawiania wstecz to oczywiście
W formie macierzowej ten układ zapisujemy jako
n2/2 flopów, tak samo jak w przypadku algorytmu podstawiania
Ux = y , wprzód.
przy czym macierz U jest górnotrójkątna.
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 53 / 55 Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 54 / 55
Życzenia z okazji Świąt Bożego Narodzenia
pięknych prezentów pod choinką,
wspaniałej atmosfery Świąt Bożego Narodzenia,
nowych sił i zapału do nauki w Nowym Roku 2009!
Adam Dąbrowski (Politechnika Poznańska) Algebra 31 stycznia 2009 55 / 55