Trudny układ równań

Axis · Post autor: **Axis** » 16 mar 2009, o 21:21

\(\displaystyle{ \begin{cases} 2x _{1}+5x _{2}-3x _{3}+4x _{4}=8 \\ 7x _{1}+6x _{2}-5x _{3}+7x _{4}=15 \\ 9x _{1}+8x _{2}+6x _{3}-5x _{4}=18 \\4x _{1} -7x _{2} +8x _{3} +3x _{4} =8 \end{cases}}\)
Sprawdziłem czy to jest układ Cramera i owszem jest (m=n i rzA=n). A ponieważ rzA=rzU więc układ ma dokładnie jedno rozwiązanie. W odpowiedziach jest napisane że \(\displaystyle{ x _{1}= x _{2}= x _{3}= x _{4}=1}\)
Obliczyłem jak na razie tylko \(\displaystyle{ x _{1}}\), ale zajęło mi to dosyć sporo czasu. Na koniec bowiem wychodzą spore liczby: \(\displaystyle{ x _{1}= \frac{detA _{1} }{detA}= \frac{-3459}{-3459}=1}\). Zatem wyznaczenie wszystkich niewiadomych tym sposobem nawet z użyciem kalkulatora byłoby dosyć czasochłonne Czy jest zatem jakaś inna metoda pozwalająca obliczyć ten układ omijając kłopotliwe rachunki? Może trzeba coś zauważyć? Ja zauważyłem że suma współczynników stojących przy zmiennych w jednym wierszu jest równa wartości wyrazu wolnego który znajduje się w tymże wierszu. Ale jak to można wykorzystać? Może jest jakaś zależność której nie znam? Bardzo Was proszę o pomoc (i to w miarę szybko bo na jutro jest mi to potrzebne)
Będę wdzięczny za wszelkie wskazówki

pozdrawiam

Crizz · Post autor: **Crizz** » 16 mar 2009, o 21:55

Nie bardzo się znam na algebrze liniowej, ale czy przypadkiem z liniowości wyznacznika nie wynika, że dowolną kolumnę macierzy można zastąpić kolumną składająca się z sum dotychczasowych wierszy macierzy i wtedy wyznacznik tej macierzy się nie zmienia? Twoje spostrzeżenie jest kluczowe i wynika z niego, że \(\displaystyle{ detA_{1}=detA_{2}=...=detA}\), czyli ze wzorów Cramera wyjdzie automatycznie \(\displaystyle{ x_{1}=x_{2}=...=1}\).

Axis · Post autor: **Axis** » 16 mar 2009, o 23:10

Hmm nie znałem tej własności liniowości wyznacznika. Faktycznie, znając tę zasadę wystarczy tylko policzyć detA i następnie przyrównać otrzymaną wartość do\(\displaystyle{ detA _{1},\ detA _{2},\ detA _{3}\ i \ detA _{4}}\)

Dzięki i pozdrawiam

Mariusz M · Post autor: **Mariusz M** » 17 mar 2009, o 06:52

Najlepiej zastosować metodę eliminacji Gaussa
albo metodę rozkładu LU

W metodzie eliminacji Gaussa za pomocą operacji elementarnych na wierszach
takich jak
dodanie wierszy
pomnożenie wiersza przez skalar
zamiana wierszy
sprowadzić układ równań do postaci trójkątnej
następnie rozwiązać za pomocą podstawień
Wyznacznik jest równy zero gdy wybrany wiersz jest kombinacją
liniową innych wierszy

W metodzie rozkładu LU należy rozłożyć macierz główną układ
na iloczyn macierzy LU=PA

L-macierz dolnotrójkątna
U-macierz górnotrójkątna
P-macierz permutacji (obrazuje ilość przestawień wierszy)
jeżeli nie było przestawień macierz permutacji jest jednostkowa
macierz permutacji pomocna jest np w ustaleniu znaku wyznacznika
A-macierz główna układu

Rozkładu LU można dokonać w ten sposób
Ułożyć układ równań na podstawie wzoru na iloczyn macierzy
Układ ten można łatwo rozwiązać metodą podstawiania
przy czym przyjęło się że rozwiązuje go w ten sposób
Naprzemiennie wyznacza się wiersz macierzy U i kolumnę macierzy L

Mając macierze L i U rozwiązujemy
układ dwóch trójkątnych równań macierzowych

Złożoność obliczeniowa zarówno metody eliminacji Gaussa jak i metody rozkładu LU wynosi

\(\displaystyle{ O \left( n^3\right)}\)

gdzie n to ilość równań

Metoda eliminacji Gaussa jak i metoda rozkładu LU
nadają się do obliczenia wyznacznika

Macierz rozkładu LU wygląda następująco

\(\displaystyle{ \left[\begin{array} {c c c c} { 2 & 5 & -3 & 4 & \frac{7}{2} & - \frac{23}{2} & \frac{11}{2} & -7 & \frac{9}{2} & \frac{29}{23} & \frac{289}{23} &- \frac{326}{23} & 2 & \frac{34}{23} & \frac{135}{289} & \frac{3459}{289} } \end{array}\right]}\)

Elementy macierzy L to elementy poniżej głównej przekątnej
Elementy macierzy U to elementy na głównej przekątnej i elementy powyżej głównej przekątnej
Na głównej przekątnej macierzy L są same jedynki

Crizz · Post autor: **Crizz** » 17 mar 2009, o 17:32

Chodziło mi o to, że np:
\(\displaystyle{ det \left[\begin{array} {c c c c} { 8 & 5 & -3 & 4 & 15 & 6 & -5 & 7 & 18 & 8 & 6 & -5 & 8 & -7 &8 & 3 } \end{array}\right] = det \left[\begin{array} {c c c c} { 2 & 5 & -3 & 4 & 7 & 6 & -5 & 7 & 9 & 8 & 6 & -5 & 4 & -7 &8 & 3 } \end{array}\right] + det \left[\begin{array} {c c c c} { 6 & 0 & 0 & 0 & 8 & 0 & 0 & 0 & 9 & 0 & 0 & 0 & 4 & 0 & 0 & 0 } \end{array}\right]}\)

To wynika z liniowości wyznacznika względem każdego wiersza macierzy. Wyznacznik tej drugiej macierzy jest równy zeru, bo ma ona zawsze co najmniej dwie takie same kolumny (to z kolei wynika ze skośnej symetryczności wyznacznika). Możesz zapisać taką równość dla każdego z liczonych wyznaczników.

Axis · Post autor: **Axis** » 17 mar 2009, o 21:52

Wow, faktycznie zadziwiająco proste i efektywne!
A masz pomysł na coś takiego:
\(\displaystyle{ \begin{cases} 3x+4y-7z+6u=2 \\ 2x-y-19z+5u=7\\4x+9y+5z-7u=6 \end{cases}}\)
Jak widać od razu nie jest to układ Cramera (m różne od n). Sprawdziłem zatem rzędy macierzy współczynników i macierzy uzupełnionej. Wyszło mi że rzA=rzU=3<n=4 zatem układ posiada nieskończenie wiele rozwiązań zależnych od 1 (4-3) parametru przyjmującego dowolne wartości zawierające się w zbiorze liczb rzeczywistych. Rachunki znowu są skomplikowane a dodatkowo występuje jeszcze parametr. Jak ominąć to żmudne i czasochłonne liczenie? Jestem pewny że trzeba coś zauważyć lecz niestety tym razem nic nie dostrzegam

Mariusz M · Post autor: **Mariusz M** » 18 mar 2009, o 08:21

Axis pisze:Wow, faktycznie zadziwiająco proste i efektywne!
A masz pomysł na coś takiego:
\(\displaystyle{ \begin{cases} 3x+4y-7z+6u=2 \\ 2x-y-19z+5u=7\\4x+9y+5z-7u=6 \end{cases}}\)
Jak widać od razu nie jest to układ Cramera (m różne od n). Sprawdziłem zatem rzędy macierzy współczynników i macierzy uzupełnionej. Wyszło mi że rzA=rzU=3<n=4 zatem układ posiada nieskończenie wiele rozwiązań zależnych od 1 (4-3) parametru przyjmującego dowolne wartości zawierające się w zbiorze liczb rzeczywistych. Rachunki znowu są skomplikowane a dodatkowo występuje jeszcze parametr. Jak ominąć to żmudne i czasochłonne liczenie? Jestem pewny że trzeba coś zauważyć lecz niestety tym razem nic nie dostrzegam

Trzeba znaleźć podmacierz kwadratową o niezerowym wyznaczniku
Niepotrzebne równania skreślić (w tym przypadku nie ma takiej potrzeby)
Nadmiarowe niewiadome we wszystkich równaniach (niewiadome nie należące do wybranej podmacierzy kwadratowej ) przenieść do macierzy wyrazów wolnych. Następnie użyć metody eliminacji Gaussa albo metody rozkładu LU

W eliminacji Gaussa musisz wyzerować tylko trzy niewiadome
Jeżeli zastosujesz postępowanie wstecz lub wprzód otrzymasz wynik

Jeżeli chcesz tylko za pomocą eliminacji rozwiązać ten układ musisz wyzerować sześć niewiadomych

Metoda eliminacji Gaussa

\(\displaystyle{ \begin{cases} 3x+4y+6u=2+7z \\ 2x-y+5u=7+19z\\4x+9y-7u=6-5z \end{cases}}\)

\(\displaystyle{ \begin{cases} 3x+4y+6u=2+7z \\ 2x-y+5u=7+19z\\6x+8y-2u=13+14z \end{cases}}\)

\(\displaystyle{ \begin{cases} 3x+4y+6u=2+7z \\ 6x-3y+15u=21+57z\\6x+8y-2u=13+14z \end{cases}}\)

\(\displaystyle{ \begin{cases} -6x-8y-12u=-4-14z \\ 6x-3y+15u=21+57z\\6x+8y-2u=13+14z \end{cases}}\)

\(\displaystyle{ \begin{cases} 3x+4y+6u=2+7z \\ \qquad -11y+3u=17+43z\\ \qquad \qquad -14u=9 \end{cases}}\)

\(\displaystyle{ u=- \frac{9}{14}}\)

\(\displaystyle{ -11y=17+43z+ \frac{27}{14}= \frac{\left(265+602z\right)}{14}}\)

\(\displaystyle{ y=-\frac{\left(265+602z\right)}{154}}\)

\(\displaystyle{ 3x=2+7z+ \frac{54}{14}+4 \frac{265+602z}{154}}\)

\(\displaystyle{ 3x=\frac{28+54+98z}{14}+ \frac{1060+2408z}{154}}\)

\(\displaystyle{ 3x=\frac{82+98z}{14}+ \frac{1060+2408z}{154}}\)

\(\displaystyle{ 3x=\frac{ 11\left(82+98z \right) +1060+2408z}{154}}\)

\(\displaystyle{ 3x=\frac{ 902+1078z +1060+2408z}{154}}\)

\(\displaystyle{ 3x=\frac{ 1962+3486z}{154}}\)

\(\displaystyle{ x=\frac{ 654+1162z}{154}}\)

\(\displaystyle{ \begin{cases} x= \frac{654+1162z}{154} \\ y=- \frac{\left(265+602z\right)}{154}\\u= -\frac{99}{154}\\z=z \end{cases}}\)

Axis · Post autor: **Axis** » 18 mar 2009, o 09:44

Aha czyli rozumiem że dużych liczb nie da się uniknąć

Mariusz M · Post autor: **Mariusz M** » 18 mar 2009, o 10:06

Można wybrać taką podmacierz kwadratową aby wyznacznik był co do wartości bezwzględnej najbliższy zeru ale różny od zera
Czasami nie da się uniknąć dużych liczb Zresztą to czy liczba jest duża to rzecz względna

Jeżeli wybierasz wariant eliminacji Gaussa
eliminowanie do macierzy trójkątnej to
elementy możesz zerować za pomocą operacji elementarnych takich jak
dodanie wiersza do innego wiersza
pomnożenie wiersza przez skalar
(przy liczeniu wyznacznika ta operacja powoduje pomnożenie wyznacznika przez ten skalar)
zamiana wierszy (przy obliczaniu wyznacznika zamiana wierszy zmienia znak wyznacznika)

Zerować elementy można mnożąc przez macierze ortogonalne (np obroty Givensa)

Macierz ortogonalna A musi spełniać warunek

\(\displaystyle{ AA^{T}=I}\) gdzie

\(\displaystyle{ A}\) macierz ortogonalna

\(\displaystyle{ A^{T}}\) transpozycja macierzy A

\(\displaystyle{ I}\) macierz jednostkowa

Axis · Post autor: **Axis** » 19 mar 2009, o 18:52

Ja obliczyłem na piechotę z twierdzenia Kroneckera-Capellego i wyszedł mi następujący wynik:

\(\displaystyle{ \begin{cases} x=a, \ a \in R \\ y = \frac{557-662a}{1162}\\ z= \frac{-654+154a}{1162}\\u= \frac{291-608a}{1162} \end{cases}}\)

A więc różni się trochę od Twojego mariuszm.....

Mariusz M · Post autor: **Mariusz M** » 19 mar 2009, o 22:18

Axis pisze:Ja obliczyłem na piechotę z twierdzenia Kroneckera-Capellego i wyszedł mi następujący wynik:

\(\displaystyle{ \begin{cases} x=a, \ a \in R \\ y = \frac{557-662a}{1162}\\ z= \frac{-654+154a}{1162}\\u= \frac{291-608a}{1162} \end{cases}}\)

A więc różni się trochę od Twojego mariuszm.....

Nie jest wykluczone że obaj rozwiązaliśmy poprawnie tylko że ja wybrałem inną podmacierz kwadratową
(tą o mniejszym wyznaczniku)