Метод Гаусса — Жордана використовується для розв'язання систем лінійних алгебраїчних рівнянь, знаходження оберненої матриці, знаходження координат вектора у заданому базисі, відшукання рангу матриці. Метод є модифікацією методу Гаусса. Названий на честь Карла Фрідріха Гаусса та німецького математика та геодезиста Вільгельма Йордана.
Алгоритм
- Обирається перша зліва колонка, що містить хоч одне ненульове значення.
- Якщо верхнє число у цій колонці — нуль, то обмінюється увесь перший рядок матриці з іншим рядком матриці, де у цій колонці нема нуля.
- Усі елементи першого рядка діляться на верхній елемент обраної колонки.
- Від рядків, що залишились, віднімається перший рядок, помножений на перший елемент відповідного рядка, з метою отримання нуля в першому елементі кожного рядка (крім першого).
- Далі, повторюємо ці операції із матрицею, отриманою з початкової матриці після викреслювання першого рядка та першого стовпчика.
- Після повторення операцій n − 1 разів отримаємо верхню трикутну матрицю.
- Віднімаємо від передостаннього рядка останній рядок, помножений на відповідний коефіцієнт, щоб у передостанньому рядку залишилась лише 1 на головній діагоналі.
- Повторюємо попередній крок для наступних рядків. У результаті отримуємо одиничну матрицю і рішення на місці (над ним необхідно виконувати ті самі перетворення).
Розгорнутий алгоритм для знаходження оберненої матриці
Нехай дано:
Прямий хід (алгоритм утворення нулів під головною діагоналлю)
- Поділимо перший рядок матриці А на
отримаємо:
, j — стовпець матриці А.
- Повторюємо дії для матриці I, за формулою:
, s — стовпець матриці I.
Отримаємо:
- Будемо утворювати 0 у першому стовпці:
.
- Повторюємо дії для матриці І, за формулами :
Отримаємо:
- Продовжуємо виконувати аналогічні операції використовуючи формули :
за умови, що
- Повторюємо дії для матриці І, за формулами :
за умови, що .
Отримаємо:
Зворотний хід (алгоритм утворення нулів над головною діагоналлю)
Використаємо формулу: , при умові, що
.
Повторюємо дії для матриці І, за формулою , за умови, що
.
Остаточно отримуємо:
Приклад
Розв'яжемо систему рівнянь:
Запишемо її у вигляді матриці 3×4, де останній стовпчик є вільним членом:
Виконаємо такі дії:
- До рядка 2 додамо: -4 * рядок 1.
- До рядка 3 додамо: -9 * рядок 1.
Отримаємо:
- До рядка 3 додамо: -3 * рядок 2.
- Рядок 2 ділимо на -2
- До рядка 1 додамо: -1 * рядок 3.
- До рядка 2 додамо: -3/2 * рядок 3.
- До рядка 1 додамо: -1 * рядок 2.
У правому стовпчику отримаємо рішення:
.
Джерела
Посилання
- Lipschutz, Seymour, and Lipson, Mark. «Schaum's Outlines: Linear Algebra». Tata McGraw-hill edition. Delhi 2001. pp. 69-80.
- Algorithm for Gauss-Jordan elimination in Python
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Metod Gaussa Zhordana vikoristovuyetsya dlya rozv yazannya sistem linijnih algebrayichnih rivnyan znahodzhennya obernenoyi matrici znahodzhennya koordinat vektora u zadanomu bazisi vidshukannya rangu matrici Metod ye modifikaciyeyu metodu Gaussa Nazvanij na chest Karla Fridriha Gaussa ta nimeckogo matematika ta geodezista Vilgelma Jordana AlgoritmObirayetsya persha zliva kolonka sho mistit hoch odne nenulove znachennya Yaksho verhnye chislo u cij kolonci nul to obminyuyetsya uves pershij ryadok matrici z inshim ryadkom matrici de u cij kolonci nema nulya Usi elementi pershogo ryadka dilyatsya na verhnij element obranoyi kolonki Vid ryadkiv sho zalishilis vidnimayetsya pershij ryadok pomnozhenij na pershij element vidpovidnogo ryadka z metoyu otrimannya nulya v pershomu elementi kozhnogo ryadka krim pershogo Dali povtoryuyemo ci operaciyi iz matriceyu otrimanoyu z pochatkovoyi matrici pislya vikreslyuvannya pershogo ryadka ta pershogo stovpchika Pislya povtorennya operacij n 1 raziv otrimayemo verhnyu trikutnu matricyu Vidnimayemo vid peredostannogo ryadka ostannij ryadok pomnozhenij na vidpovidnij koeficiyent shob u peredostannomu ryadku zalishilas lishe 1 na golovnij diagonali Povtoryuyemo poperednij krok dlya nastupnih ryadkiv U rezultati otrimuyemo odinichnu matricyu i rishennya na misci nad nim neobhidno vikonuvati ti sami peretvorennya Rozgornutij algoritm dlya znahodzhennya obernenoyi matriciNehaj dano A a11a12 a1na21a22 a2n an1an2 ann aii 0I 10 001 0 00 1 displaystyle A begin pmatrix a 11 amp a 12 amp cdots amp a 1n a 21 amp a 22 amp cdots amp a 2n vdots amp vdots amp ddots amp vdots a n1 amp a n2 amp cdots amp a nn end pmatrix quad a ii neq 0 quad I begin pmatrix 1 amp 0 amp cdots amp 0 0 amp 1 amp cdots amp 0 vdots amp vdots amp ddots amp vdots 0 amp 0 amp cdots amp 1 end pmatrix Pryamij hid algoritm utvorennya nuliv pid golovnoyu diagonallyu Podilimo pershij ryadok matrici A na a11 displaystyle a 11 otrimayemo a1j1 a1ja11 displaystyle a 1j 1 frac a 1j a 11 j stovpec matrici A Povtoryuyemo diyi dlya matrici I za formuloyu b1s1 b1sa11 displaystyle b 1s 1 frac b 1s a 11 s stovpec matrici I Otrimayemo A 1a121 a1n1a21a22 a2n an1an2 ann I b1110 001 0 00 1 displaystyle A begin pmatrix 1 amp a 12 1 amp cdots amp a 1n 1 a 21 amp a 22 amp cdots amp a 2n vdots amp vdots amp ddots amp vdots a n1 amp a n2 amp cdots amp a nn end pmatrix qquad I begin pmatrix b 11 1 amp 0 amp cdots amp 0 0 amp 1 amp cdots amp 0 vdots amp vdots amp ddots amp vdots 0 amp 0 amp cdots amp 1 end pmatrix Budemo utvoryuvati 0 u pershomu stovpci a2j1 a2j a1j1a21 anj1 anj a1j1an1 displaystyle a 2j 1 a 2j a 1j 1 a 21 dots a nj 1 a nj a 1j 1 a n1 Povtoryuyemo diyi dlya matrici I za formulami b2s1 b2s b1s1a21 bns1 bns b1s1an1 displaystyle b 2s 1 b 2s b 1s 1 a 21 dots b ns 1 b ns b 1s 1 a n1 Otrimayemo A 1a121 a1n10a221 a2n1 0a2n1 ann1 I b1110 0b2111 0 bn110 1 displaystyle A begin pmatrix 1 amp a 12 1 amp cdots amp a 1n 1 0 amp a 22 1 amp cdots amp a 2n 1 vdots amp vdots amp ddots amp vdots 0 amp a 2n 1 amp cdots amp a nn 1 end pmatrix qquad I begin pmatrix b 11 1 amp 0 amp cdots amp 0 b 21 1 amp 1 amp cdots amp 0 vdots amp vdots amp ddots amp vdots b n1 1 amp 0 amp cdots amp 1 end pmatrix Prodovzhuyemo vikonuvati analogichni operaciyi vikoristovuyuchi formuli aijk aijkaiiaijk aijk 1 akjkaikk 1 displaystyle a ij k frac a ij k a ii qquad a ij k a ij k 1 a kj k a ik k 1 za umovi sho k 1 n i k 1 n j 1 n displaystyle k 1 to n i k 1 to n j 1 to n Povtoryuyemo diyi dlya matrici I za formulami bikk bikkaiibisk bisk 1 bkskaikk 1 displaystyle b ik k frac b ik k a ii qquad b is k b is k 1 b ks k a ik k 1 za umovi sho k 1 n i k 1 n s 1 n displaystyle k 1 to n i k 1 to n s 1 to n Otrimayemo A 1a121 a1n101 a2n2 00 1 I b1110 0b212b222 0 bn1nbn2n bnnn displaystyle A begin pmatrix 1 amp a 12 1 amp cdots amp a 1n 1 0 amp 1 amp cdots amp a 2n 2 vdots amp vdots amp ddots amp vdots 0 amp 0 amp cdots amp 1 end pmatrix qquad I begin pmatrix b 11 1 amp 0 amp cdots amp 0 b 21 2 amp b 22 2 amp cdots amp 0 vdots amp vdots amp ddots amp vdots b n1 n amp b n2 n amp cdots amp b nn n end pmatrix Zvorotnij hid algoritm utvorennya nuliv nad golovnoyu diagonallyu Vikoristayemo formulu aijk 1 aijk 1 aijkaiki displaystyle a ij k 1 a ij k 1 a ij k a ik i pri umovi sho k n 1 i 1 k 1 j 1 n displaystyle k n to 1 i 1 to k 1 j 1 to n Povtoryuyemo diyi dlya matrici I za formuloyu bisk 1 bisk 1 biskaiki displaystyle b is k 1 b is k 1 b is k a ik i za umovi sho k n 1 i 1 k 1 s 1 n displaystyle k n to 1 i 1 to k 1 s 1 to n Ostatochno otrimuyemo A 10 001 0 00 1 I A 1 displaystyle A begin pmatrix 1 amp 0 amp cdots amp 0 0 amp 1 amp cdots amp 0 vdots amp vdots amp ddots amp vdots 0 amp 0 amp cdots amp 1 end pmatrix qquad I A 1 PrikladRozv yazhemo sistemu rivnyan a b c 04a 2b c 19a 3b c 3 displaystyle left begin array ccccccl a amp amp b amp amp c amp amp 0 4a amp amp 2b amp amp c amp amp 1 9a amp amp 3b amp amp c amp amp 3 end array right Zapishemo yiyi u viglyadi matrici 3 4 de ostannij stovpchik ye vilnim chlenom 111 0421 1931 3 displaystyle begin pmatrix 1 amp 1 amp 1 amp amp 0 4 amp 2 amp 1 amp amp 1 9 amp 3 amp 1 amp amp 3 end pmatrix Vikonayemo taki diyi Do ryadka 2 dodamo 4 ryadok 1 Do ryadka 3 dodamo 9 ryadok 1 Otrimayemo 1 1 1 00 2 3 10 6 8 3 displaystyle begin pmatrix 1 amp 1 amp 1 amp amp 0 0 amp 2 amp 3 amp amp 1 0 amp 6 amp 8 amp amp 3 end pmatrix Do ryadka 3 dodamo 3 ryadok 2 Ryadok 2 dilimo na 2 111 00132 12001 0 displaystyle begin pmatrix 1 amp 1 amp 1 amp amp 0 0 amp 1 amp 3 over 2 amp amp 1 over 2 0 amp 0 amp 1 amp amp 0 end pmatrix Do ryadka 1 dodamo 1 ryadok 3 Do ryadka 2 dodamo 3 2 ryadok 3 110 0010 12001 0 displaystyle begin pmatrix 1 amp 1 amp 0 amp amp 0 0 amp 1 amp 0 amp amp 1 over 2 0 amp 0 amp 1 amp amp 0 end pmatrix Do ryadka 1 dodamo 1 ryadok 2 100 12010 12001 0 displaystyle begin pmatrix 1 amp 0 amp 0 amp amp 1 over 2 0 amp 1 amp 0 amp amp 1 over 2 0 amp 0 amp 1 amp amp 0 end pmatrix U pravomu stovpchiku otrimayemo rishennya a 12 b 12 c 0 displaystyle a frac 1 2 b frac 1 2 c 0 DzherelaPosilannyaLipschutz Seymour and Lipson Mark Schaum s Outlines Linear Algebra Tata McGraw hill edition Delhi 2001 pp 69 80 Algorithm for Gauss Jordan elimination in Python