Метод Гаусса — Зайделя є класичним ітераційним методом розв'язку системи лінійних рівнянь.
Постановка задачі
Візьмемо систему: , де
Або
І покажемо, як її можна розв'язати за допомогою методу Гаусса — Зайделя.
Метод
Щоб пояснити зміст методу, перепишемо задачу у вигляді:
Тут в -му рівнянні ми перенесли в праву частину всі члени, що містять , для . Отримана система може бути представлена:
- ,
де в прийнятих позначеннях D означає матрицю, у якої на головній діагоналі стоять відповідні елементи матриці A, а всі інші — нулі; тоді як матриці U та L містять верхню і нижню трикутні частини A, на головній діагоналі яких нулі.
Ітеративний процес в методі Гаусса — Зайделя будується за формулою
після вибору відповідного початкового наближення .
Метод Гаусса — Зайделя можна розглядати як модифікацію методу Якобі. Основна ідея модифікації полягає в тому, що нові значення використовуються тут одразу ж у міру отримання, в той час як у методі Якобі вони не використовуються до наступної ітерації:
де
Таким чином i-й компонент -го наближення обчислюється за формулою:
Умова збіжності
Наведемо достатню умову збіжності методу.
Теорема. Нехай , де – матриця, обернена до . Тоді при довільному виборі початкового наближення :
|
Умова завершення
Умова завершення ітераційного процесу Гаусса — Зайделя при досягненні точності у спрощеній формі має вигляд:
Точніша умова завершення ітераційного процесу має вигляд
і потребує більше обчислень. Добре підходить для розріджених матриць.
Приклад алгоритму на С++
// Умова завершення bool converge(double *xk, double* xkp) { bool b = true; for (int i = 0; i < n; i++) { if (fabs(xk[i]-xkp[i]) > eps) { b = false; break; } } return b; } while(!converge(x,p)) { for(int i = 0; i < n; i++) { var = 0; for(int j = 0; j < n; j++) { if(j != i) var += (a[i][j]*x[j]); } p[i] = x[i]; x[i]=(b[i] - var)/a[i][i]; } }
Примітки
Див. також
- Геометрична прогресія
- (Гаусса — Зайделя)
- Метод простої ітерації
- Метод Якобі
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Metod Gaussa Zajdelya ye klasichnim iteracijnim metodom rozv yazku sistemi linijnih rivnyan Postanovka zadachiVizmemo sistemu A x b displaystyle A vec x vec b de A a 11 a 1 n a n 1 a n n b b 1 b n displaystyle A left begin array ccc a 11 amp ldots amp a 1n vdots amp ddots amp vdots a n1 amp ldots amp a nn end array right quad vec b left begin array c b 1 vdots b n end array right Abo a 11 x 1 a 1 n x n b 1 a n 1 x 1 a n n x n b n displaystyle left begin array rcl a 11 x 1 ldots a 1n x n amp amp b 1 amp amp a n1 x 1 ldots a nn x n amp amp b n end array right I pokazhemo yak yiyi mozhna rozv yazati za dopomogoyu metodu Gaussa Zajdelya MetodShob poyasniti zmist metodu perepishemo zadachu u viglyadi a 11 x 1 a 12 x 2 a 13 x 3 a 1 n x n b 1 a 21 x 1 a 22 x 2 a 23 x 3 a 2 n x n b 2 a n 1 1 x 1 a n 1 2 x 2 a n 1 n 1 x n 1 a n 1 n x n b n 1 a n 1 x 1 a n 2 x 2 a n n 1 x n 1 a n n x n b n displaystyle left begin array lcr a 11 x 1 amp amp a 12 x 2 a 13 x 3 ldots a 1n x n b 1 a 21 x 1 a 22 x 2 amp amp a 23 x 3 ldots a 2n x n b 2 ldots amp amp a n 1 1 x 1 a n 1 2 x 2 ldots a n 1 n 1 x n 1 amp amp a n 1 n x n b n 1 a n1 x 1 a n2 x 2 ldots a n n 1 x n 1 a nn x n amp amp b n end array right Tut v j displaystyle j mu rivnyanni mi perenesli v pravu chastinu vsi chleni sho mistyat x i displaystyle x i dlya i gt j displaystyle i gt j Otrimana sistema mozhe buti predstavlena L D x U x b displaystyle mathrm L mathrm D vec x mathrm U vec x vec b de v prijnyatih poznachennyah D oznachaye matricyu u yakoyi na golovnij diagonali stoyat vidpovidni elementi matrici A a vsi inshi nuli todi yak matrici U ta L mistyat verhnyu i nizhnyu trikutni chastini A na golovnij diagonali yakih nuli Iterativnij proces v metodi Gaussa Zajdelya buduyetsya za formuloyu L D x k 1 U x k b k 0 1 2 displaystyle mathrm L mathrm D vec x k 1 mathrm U vec x k vec b quad k 0 1 2 ldots pislya viboru vidpovidnogo pochatkovogo nablizhennya x 0 displaystyle vec x 0 Metod Gaussa Zajdelya mozhna rozglyadati yak modifikaciyu metodu Yakobi Osnovna ideya modifikaciyi polyagaye v tomu sho novi znachennya x i displaystyle vec x i vikoristovuyutsya tut odrazu zh u miru otrimannya v toj chas yak u metodi Yakobi voni ne vikoristovuyutsya do nastupnoyi iteraciyi x 1 k 1 c 12 x 2 k c 13 x 3 k c 1 n x n k d 1 x 2 k 1 c 21 x 1 k 1 c 23 x 3 k c 2 n x n k d 2 x n k 1 c n 1 x 1 k 1 c n 2 x 2 k 1 c n n 1 x n 1 k 1 d n displaystyle left begin array ccccccccccc x 1 k 1 amp amp c 12 x 2 k amp amp c 13 x 3 k amp amp ldots amp amp c 1n x n k amp amp d 1 x 2 k 1 amp amp c 21 x 1 k 1 amp amp c 23 x 3 k amp amp ldots amp amp c 2n x n k amp amp d 2 ldots amp amp amp amp amp amp amp amp amp amp x n k 1 amp amp c n1 x 1 k 1 amp amp c n2 x 2 k 1 amp amp ldots amp amp c n n 1 x n 1 k 1 amp amp d n end array right de c i j a i j a i i d i b i a i i i 1 n displaystyle c ij frac a ij a ii quad d i frac b i a ii quad i 1 ldots n Takim chinom i j komponent k 1 displaystyle k 1 go nablizhennya obchislyuyetsya za formuloyu x i k 1 j 1 i 1 c i j x j k 1 j i 1 n c i j x j k d i i 1 n displaystyle x i k 1 sum j 1 i 1 c ij x j k 1 sum j i 1 n c ij x j k d i quad i 1 ldots n Umova zbizhnostiNavedemo dostatnyu umovu zbizhnosti metodu Teorema Nehaj A 2 lt 1 displaystyle mathrm A 2 lt 1 de A 2 L D 1 U L D 1 displaystyle mathrm A 2 mathrm L mathrm D 1 mathrm U quad mathrm L mathrm D 1 matricya obernena do L D displaystyle mathrm L mathrm D Todi pri dovilnomu vibori pochatkovogo nablizhennya x 0 displaystyle vec x 0 metod Gausa Zejdelya zbigayetsya shvidkist zbizhnosti metodu dorivnyuye shvidkosti zbizhnosti geometrichnoyi progresiyi zi znamennikom q A 2 displaystyle q mathrm A 2 spravdzhuyetsya ocinka pohibki x k x q k x 0 x displaystyle vec x k vec x q k vec x 0 vec x Umova zavershennyaUmova zavershennya iteracijnogo procesu Gaussa Zajdelya pri dosyagnenni tochnosti e displaystyle varepsilon u sproshenij formi maye viglyad x k 1 x k e displaystyle parallel x k 1 x k parallel leq varepsilon Tochnisha umova zavershennya iteracijnogo procesu maye viglyad A x k b e displaystyle parallel Ax k b parallel leq varepsilon i potrebuye bilshe obchislen Dobre pidhodit dlya rozridzhenih matric Priklad algoritmu na S Umova zavershennya bool converge double xk double xkp bool b true for int i 0 i lt n i if fabs xk i xkp i gt eps b false break return b while converge x p for int i 0 i lt n i var 0 for int j 0 j lt n j if j i var a i j x j p i x i x i b i var a i i PrimitkiMETOD GAUSA ZEJDELYa POYaSNENNYa DODATKI PRIKLADI NAUKA warbletoncouncil ukr Procitovano 11 lyutogo 2021 Filip Lyudvig Zejdel 1821 1896 nimeckij astronom ta matematik Karl Fridrih Gaus 1777 1855 nimeckij matematik astronom ta fizikDiv takozhGeometrichna progresiya Gaussa Zajdelya Metod prostoyi iteraciyi Metod Yakobi