Wyklad 1

Równania liniowe

Niech zadany jest liniowy układ M równań o N niewiadomych o współczynnikach 𝑎𝑖𝑗, 𝑏𝑖 (𝑖 = 1,2, . . , 𝑀) (𝑗 = 1,2, . . , 𝑁) rzeczywistych lub zespolonych:

Jeżeli w układzie N = M, tj. macierz 𝑨 jest macierzą kwadratową, to układ równań posiada tyle samo równań, co niewiadomych. Jeżeli ponadto wyznacznik tego układu jest różny od zera, to posiada on jednoznaczne rozwiązanie: 𝒙 = 𝑨^-1𝒃.

Jeżeli w układzie (1) M ≥ N, to układ jest nadokreślony i jako jego pseudorozwiązanie określa się taki wektor kolumnowy x, który minimalizuje normę wektora residuów.

𝒓 = 𝑨𝒙 − 𝒃 (2)

Oznaczając przez 𝑟𝑖 składowe wektora 𝒓, jego normę możemy zdefiniować np.:

‖𝒓‖ = ∑𝑟𝑖² (3)

Metody bezpośrednie rozwiązywania układów równań liniowych

Metoda bezpośredniego rozwiązywania układu N równań liniowych i N niewiadomych o współczynnikach rzeczywistych lub zespolonych:

przy pominięciu błędów zaokrągleń daje dokładne rozwiązanie po skończonej liczbie kroków.

Rozwiązywanie układu równań liniowych metodą Gaussa

Najważniejszą z metod bezpośrednich jest metoda eliminacji Gaussa. Polega ona na kolejnej eliminacji niewiadomych w pewien systematyczny sposób prowadzący do układu trójkątnego, który można już łatwo rozwiązać.

Załóżmy, że istnieje jednoznaczne rozwiązanie układu liniowego (4). Eliminację Gaussa można interpretować jako wyznaczanie ciągu macierzy 𝑨 = 𝑨(1), 𝑨2, ..., 𝑨(𝑁) i wektorów 𝒃 = 𝒃(1), 𝒃2, ..., 𝒃(𝑁), gdzie macierz 𝑨(𝒊) = [𝑎𝑘𝑙(𝑖)] ma postać:

Konstrukcja elementów: macierzy w ciągu macierzowym 𝑨(𝑖) oraz wektorów w ciągu 𝒃(𝑖) ma następującą postać:

który, jak zostanie pokazane poniżej, można rozwiązać metodą postępowania wstecz.

Implementacje metod eliminacji Gaussa dokonuje się stosując bezpośredni wzory (6),(7) i (8). Dla uniknięcia katastrofalnego błędu, jaki pojawiłby się w obliczeniach w i-tym kroku przy 𝑎𝑖𝑖 (𝑖) = 0 (patrz wzór (8)), zastosowano częściowy wybór elementu głównego, polegający na wyborze maksymalnego modułu spośród elementów i-tej kolumny macierzy 𝑨 (𝑖) , począwszy od i-tego wiersza: