Macierze - algorytm

Ewa 20
Użytkownik
Użytkownik
Posty: 164
Rejestracja: 18 lut 2007, o 12:55
Płeć: Kobieta
Lokalizacja: Ozimek
Podziękował: 18 razy
Pomógł: 12 razy

Macierze - algorytm

Post autor: Ewa 20 »

Zadanie. Napisać algorytm sprowadzania macierzy do postaci schodkowej.
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Macierze - algorytm

Post autor: miki999 »

Załóżmy, że nasz układ równań wygląda tak:
\(\displaystyle{ \left\{\begin{array}{l}{ a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=a_{1(n+1)} \\ a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}=a_{2(n+1)}\\ .........+.........+...+.........=...........\\ a_{n1}x_{1}+a_{n2}x_{2}+...+a_{nn}x_{n}=a_{n(n+1)}\end{array}}\)

Aby usunąć ze wszystkich wierszy (oprócz 1.) współczynnik przy pierwszej niewiadomej musimy od każdego wiersza odjąć 1. równanie pomnożone przez:
\(\displaystyle{ \frac{a_{21}}{a_{11}}}\)
W ogólnej wersji dla i-tego równania czynnik ten będzie wynosić:
\(\displaystyle{ \frac{a_{i1}}{a_{11}}}\)
Po takiej serii mamy:
\(\displaystyle{ \left\{\begin{array}{l}{ a_{11}x_{1}+ \quad \quad \quad \quad \quad \quad a_{12}x_{2}+...+ \quad \quad \quad \quad \quad a_{1n}x_{n} =a_{1(n+1)} \\ \quad \quad \quad \quad \quad (a_{22}- \frac{a_{21}}{a_{11}}a_{12}) x_{2}+...+(a_{2n}- \frac{a_{21}}{a_{11}}a_{1n})x_{n}=a_{2(n+1)}- \frac{a_{21}}{a_{11}}a_{1(n+1)} \\ \quad \quad \quad \quad \quad ..... \quad \quad \quad \quad \quad \quad +...+........ \quad \quad \quad \quad \quad =...........\\ \quad \quad \quad \quad \quad (a_{n2}- \frac{a_{n1}}{a_{11}}a_{12}) x_{2}+...+(a_{nn}- \frac{a_{n1}}{a_{11}}a_{1n})x_{n}=a_{n(n+1)} - \frac{a_{n1}}{a_{ 11}}a_{1(n+1)} \end{array}}\)

Teraz lecieć w dół kolejne wiersze- analogicznie.

Jak zwykle zagmatwałem

Pozdrawiam.
Ewa 20
Użytkownik
Użytkownik
Posty: 164
Rejestracja: 18 lut 2007, o 12:55
Płeć: Kobieta
Lokalizacja: Ozimek
Podziękował: 18 razy
Pomógł: 12 razy

Macierze - algorytm

Post autor: Ewa 20 »

Problem w tym, że ja wiem jak to zrobić w praktyce, a mam zapisać ogólny algorytm, tak, żeby potem można było do niego napisać program. I o ile samo sprowadzenie macierzy do postaci schodkowej jest łatwe, o tyle zapisanie tego jako listę kroków już nie (przynajmniej dla mnie).
spajder
Użytkownik
Użytkownik
Posty: 735
Rejestracja: 7 lis 2005, o 23:56
Płeć: Mężczyzna
Lokalizacja: Łódź
Podziękował: 2 razy
Pomógł: 133 razy

Macierze - algorytm

Post autor: spajder »

robiłem program na zaliczenie, eliminacja Gaussa-Jordana. Nie jest to dokładnie to, czego szukasz, ale jako jedna z funkcji jest własnie sprowadzenie macierzy kwadratowej do takiej postaci (musisz go przerobić, np. żeby obsługiwał macierze niekwadratowe, dorzucić sortowanie kolumn, bo mój program o to nie dba (to celowe, żeby można było rozwiązać np.:
\(\displaystyle{ \left\{\begin{array}{lllll} & & y &=& 2 \\ x && & = &2\end{array}\right.}\)

tj. z zerami na głównej przekątnej.
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Macierze - algorytm

Post autor: miki999 »

A w jakim języku masz to napisać? Mam gdzieś starą książkę od informatyki, w której, o ile się nie mylę, był napisany właśnie taki program w C++. Jeżeli będziesz chciała to spróbuję odnaleźć tę książkę i przepisać kod.

Pozdrawiam.
Ewa 20
Użytkownik
Użytkownik
Posty: 164
Rejestracja: 18 lut 2007, o 12:55
Płeć: Kobieta
Lokalizacja: Ozimek
Podziękował: 18 razy
Pomógł: 12 razy

Macierze - algorytm

Post autor: Ewa 20 »

To ma być algorytm napisany w tak zwanym pseudokodzie, żeby można go było podpasować do dowolnego kompilatora. Nie musi zawierać takich szczegółów jak deklaracja zmiennych, itp. Chodzi o listę kroków prowadzącą do rozwiązania (np. ewentualne pętle).
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Macierze - algorytm

Post autor: miki999 »

Wygrzebałem ten podręcznik. Program do szukania rozw. układu metodą eliminacji Gaussa.
Lista Kroków jest mniej więcej taka:
1. Pobranie współczynników układu (deklaracja tablicy +pętla)
2. Wyświetlenie tablicy współczynników układu (pętla)

(warunek):
3. Sprawdzenie czy istnieje niebezpieczeństwo dzielenia przez 0 (pętla)
3.1. Sprawdzamy czy w kolejnych wierszach jest liczba różna od 0 w danej kolumnie (pętla)
3.2. Jeżeli w danej kolumnie liczby są równe 0 to koniec programu i wyświetlenie napisu.
(Jeżeli warunek nie został spełniony to):
3.3. Zamiana wierszy miejscami (pętla)
3.4. Eliminacja współczynników (2 pętle)

4. Wypisanie tablicy w postaci schodkowej (pętla)
5. Obliczenie niewiadomych i wpisanie ich do tablicy (2 pętle)
6. Wypisanie rozw. (pętla)

Pozdrawiam.
ODPOWIEDZ