Дәріс конспекті. Дәріс тақырыбы:Кері жүрісті Гаусс әдісінің алгоритмі

Дәріс тақырыбы: Кері жүрісті Гаусс әдісінің алгоритмі. Кері жүріссіз Гаусс әдісінің алгоритмі (Жордан схемасы). Шешу дәлдігіне әсер ететін факторлар.

Ах = b түріндегі n сызықты алгебралық теңдеулер жүйесін алгоритм бойынша шешу екі этаптан тұрады.

Бірінші этапта (тура жүріс) n бір типті қадамдарға дейінгі бастапқы жүйе жүйенің коэффициенттер матрицасы жоғарғы үшбұрышты болатындай түрлендіріледі, яғни оның бас диагоналынан төмен орналасқан барлық элементтер нөлге тең болады.

Екінші этапта (кері жүріс) белгісіздердің мәндері кезектесіп х_n -нен x₁ -ге дейін анықталады.

Тура жүріс кезінде орындалатын операциялардың тізбектелуі:

Бірінші қадамда бастапқы теңдеулер жүйесінде

a₁₁х₁ + а₁₂х₂ + … + а_1nx_n = b₁

a₂₁х₁ + а₂₂х₂ + … + а_2nx_n = b₂

……………………………..

a_n1х₁ + а_n2х₂ + … + а_nnx_n = b_n

бірінші теңдеу a₁₁ -ге бөлінеді. Әрі қарай х₁ келесі теңдеулерден (i = 2, ..., n) бірінші теңдеуді а_i1 -ге көбейтіп, і -ші теңдеуден алынып тасталуы арқылы анықталады. Нәтижесінде А⁽¹⁾ коэффициенттер матрицасымен теңдеулер жүйесі алынады:

х₁ + а₁₂⁽¹⁾х₂ + … + а_1n⁽¹⁾x_n = b₁⁽¹⁾

0 + а₂₂⁽¹⁾х₂ + … + а_2n⁽¹⁾x_n = b₂⁽¹⁾

……………………………..

0 + а_n2⁽¹⁾х₂ + … + а_nn⁽¹⁾x_n = b_n⁽¹⁾

мұнда a_1j⁽¹⁾ = a_1j/a₁₁; b₁⁽¹⁾ = b₁/a₁₁;

a_ij⁽¹⁾ = a_ij – a_i1a_1j⁽¹⁾; b_i⁽¹⁾ = b_i – a_i1b₁⁽¹⁾

i, j = 2, …, n.

Бірінші қадамның операцияларының орындалуы жетекші деп аталатын а₁₁ элементі нөлден өзгеше болуы қажет.

Екінші қадамда а₂₂⁽¹⁾ жетекші элементі деп қолданылып, бірінші қадамдағы сәйкес операцияларды орындау арқылы x₂ -ні 3,...n теңдеулерінен алынып тасталады. Нәтижесінде жүйе келесі түрге келтіріледі: А⁽²⁾х = b⁽²⁾.

Үшінші және келесі қадамдар сәйкес түрде орындалады.

k қадамында A^(k) матрицасының және b^(k) бағанының мәндері келесі өрнектерден анықталады:

a_kj^(k) = a_kj^(k-1)/a_kk^(k-1); b_k^(k) = b_k^(k-1)/a_kk^(k-1);

a_ij^(k) = a_ij^(k-1) – a_ik^(k-1)a_kj^(k); b_i^(k) = b_i^(k-1) – a_ik^(k-1)b_k^(k);

i, j = k + 1, …, n

Тура тәсілде жетекші элементтер болып тізбектеліп а₁₁, а₂₂⁽¹⁾, а₃₃⁽²⁾, …, а_nn^(n-1) болады және олардың нөлден өзгеше болуы есептелу процесінің орындалу шарты болып табылады.

n қадамдарының орындалу нәтижесінде келесі теңдеулер жүйесі құралады:

х₁ + а₁₂⁽¹⁾х₂ +…+ а_1(n-2)⁽¹⁾х_n-2 + а_1(n-1)⁽¹⁾х_n-1 + а_1n⁽¹⁾х_n = b₁⁽¹⁾

х₂ +…+ а_1(n-2)⁽²⁾х_n-2 + а_1(n-1)⁽²⁾х_n-1 + а_1n⁽²⁾х_n = b₁⁽²⁾

………………………………………………………….

х_n-2 + а_(n-2)(n-1)^(n-2)х_n-1 + а_(n-2)n^(n-2)х_n = b_n-2^(n-2)

х_n-1 + а_(n-1)n^(n-1)х_n = b_n-1^(n-1)

х_n = b_n⁽ⁿ⁾

Кері жүрістегі этапта х_n -нен х₁ -ге дейінгі ізделетін белгісіздер анықталады.

Кері жүріссіз Гаусс тәсілінің алгоритмі (Жордан схемасы)

n бейсызықты алгебралық теңдеулер жүйесін бұл алгоритм арқылы шешу бір этапта орындалады, нәтижесінде А коэффициенттер матрицасы n бір типті қадамдардан кейін бірлік матрицаға келтіріледі, яғни теңдеулер жүйесі оң жағындағы бағанының түрлендірілуі нәтижесінде алынған сәйкес элементтерге тең ізделетін белгісіздерге қатысты шешіледі.

Бірінші қадамда есептеулер кері жүрісті Гаусс әдісінің алгоритміндегідей орындалады.

Нәтижесінде алынған А⁽¹⁾х = b⁽¹⁾ түрлендірілген теңдеулер жүйесі матрицасының бірінші бағанының бірінші элементі бірге тең, ал қалған элементтері нөлге тең болуымен сипатталады.

Екінші қадамда, алдыңғы алгоритмдегідей, жетекші элемент ретінде А⁽¹⁾ матрицасының екінші бағанның диагоналды элементі таңдалады, яғни а₂₂⁽¹⁾. Қосымша А⁽¹⁾ матрицасының а₁₂⁽¹⁾ элементі нөлге айналатындай бірінші жолы түрлендіріледі.

Кез-келген (k) қадамдағы операцияның орындалуы оның (а_kk^(k)) диагоналды элементі бірге тең болатындай, ал диагоналды емес (а_jk^(k), j¹k) элементтері нөлге тең болатындай k бағанының түрлендірілуіне сәйкес келеді.

K қадамындағы жүйенің коэффициенттерін есептеу формулалары кері жүрісті Гаусс тәсілінің алгоритміндегідей түрде болады, бұл жерде тек A(k) матрицасы барлық жолдарының элементтері әр қадамда есептелетіндіктен, і жолы индексінің өзгеру диапазонымен ғана ерекшеленеді.

Демек, A^(k) матрицасының және b^(k) бағанының k қадамындағы элементтері келесі өрнектермен анықталады:

a_kj^(k) = a_kj^(k-1)/a_kk^(k-1); b_k^(k) = b_k^(k-1)/a_kk^(k-1);

a_ij^(k) = a_ij^(k-1) – a_ik^(k-1)a_kj^(k); b_i^(k) = b_i^(k-1) – a_ik^(k-1)b_k^(k);

i = 1, …, n; j ¹ k; j = k + 1, …, n

A^(n-1) матрицасының соңы бағанының элементтері және b^(n-1) бағанының барлық элементтері есептелетін (k = n) соңғы қадамның орындалуы нәтижесінде A⁽ⁿ⁾=1 матрицасы алынады, демек бұл кезде x=b⁽ⁿ⁾.

Есептеу дәлдігіне әсер ететін факторлар

Қарастырылған Гаусс әдісін қолдану жеткілікті дәлдіктегі шешімді алуға мүмкіндік бере бермейді, немесе мүлдем мүмкіндік бермейді. Мұндай үлкен қателіктердің пайда болуына келесілер себеп болады:

- есептеу нәтижелерін жуықтау;

- бастапқы берілгендердің дәл болмауы, бұл бірқатар жағдайда есептеу дәлдігінің елеулі төмендеуіне әкеледі.

Есептеу нәтижелерін жуықтау. Гаусс әдісі бойынша есептеу a_kk^(k) жетекші элементінің нөлден өзгеше болуын талап етеді.

Есептеу барысында А матрицасы элементтерінің тізбектеліп есептелуіне сәйкес есептеулерсіз жетекші элементтердің мәндері толық болмайды.

Белгілі бір қадамда дәл есептеулер орындаған кезде жетекші элемент нөлге тең болуы немесе жуықтауды орындаған кезде жетекші элемент нөлге жақын болуы мүмкін.

Бірінші жағдайда шешімді алу мүмкін емес болып табылады, ал екінші жағдайда – жетекші элементте салмақты мәндердің болмауына байланысты (мәндері бір-біріне жақын екі шаманы бір-бірінен алып тастаған кезде) келесі есептеулердің қателігі елеулі түрде үлкен бола алады.

Жуықтау кезінде нәтижелердің елеулі қателіктерін болдырмау үшін (оның себебі жетекші элементтің нөлге жақындығы бола алады) дәл есептеулер кезінде шешімді алу мүмкін болу үшін (жетекші элемент нөлге тең болған кезде) күрделірек есептеу схемасын қолдану ұсынылады, бұл кезде әр k қадамында жетекші элемент ретінде абсолюттік шамасы бойынша a_ij^(k-1) (i, j = k, ..., n) ең үлкен элемент таңдалады.

Мұндай есептеу схемасы бас элемент схемасы деп аталады.

Әр k қадамында a_ij^(k-1) (i, j = k, ...., n) мәндерінен абсолюттік шамасы бойынша ең үлкен а_макс элементін таңдап, А^(k-1) матрицасының жолдары мен бағандарын және b^(k-1) бағанының элементтерін а_макс элементі элемента a_kk^(k-1) жетекші элементтің орнын алатындай ауыстырып қою қажет, тек содан кейін ғана есептеулерді жалғастыруға болады.

Бас элемент схемасын программалық орындау күрделілігіне байланысты практикада оның модификациялары қолданылады да алынатын нәтижелерінің дәлдігі бойынша шамалы ғана төмен болады, бірақ қарапайым программалаумен және есептеу уақытының аздығымен сипатталады.

Бұл модификацияларда k қадамында жетекші элемент ретінде k бағанының (i = k, ..., n; j = k), не k жолының (i = k; j = k, ..., n), не бас диагоналдың (i = j = k, …, n) абсолюттік шамасы бойынша ең үлкен a_ij^(k-1) элементі таңдалады. Кез-келген модификацияны таңдау нақты техникалық есеп үшін А матрицасының ерекшеліктерімен анықталады.

Бастапқы берілгендердің дәл болмауы. Инженерлік есептерді шешу барысында бастапқы берілгендер белгілі бір қателікпен белгілі болады, бұл қателіктер өлшеудің немесе жүйенің және оның режимдерінің параметрлерін есептеудің шектік дәлдігімен анықталады.

Нақты техникалық есептер үшін сызықты алгебралық теңдеулерді шешу барысында алынатын нәтижелердің салыстырмалы қателігі бастапқы берілгендердің қателіктерімен шамалас келеді.

Бірақ бастапқы берілгендердің қателіктері, яғни А және b матрицалары элементтерінің мәндері, шешімнің елеулі қателіктеріне әкелетін жағдайлар бола алады.

Оған себеп теңдеулер жүйесі коэффициенттер матрицасының жеткіліксіз келісілгендігі болып табылады, және көрсеткіші А матрицасы анықтауышы мәнінің аздығы болып табылады.

D анықтауышының аздығы белгілі Адамар бағалауымен D_макс салыстыру арқылы анықталады: .

Техникалық есептерді есептеудің практикасында А матрицасының жеткіліксіз келісілгендігі есептің математикалық сипатталуының дұрыс еместігіне, немесе жүйенің қарастырылатын күйінің өзгешелігі (мысалы, орын алу шарты бойынша шектіге жақын орныққан режимін есептеу кезінде) байланысты.

Бірінші жағдайда шешімді алу үшін есептік техникалық мәніне сәйкес дұрыс математикалық сипатталуы қажет, ал екінші жағдайда Гаусс әдісінен басқа тәсілдерді қолдану қажет.

Электрлік жүйенің орныққан режимінің сызықты теңдеулерінің ерекшелігі. Орныққан режимдерді есептеу мәселелерін орындау кезінде кездесетін сызықты алгебралық теңдеулердің келесі сипаттамалы ерекшеліктері болады:

- көптеген жағдайда теңдеулер жүйесінің коэффициенттер матрицасы толығымен толтырылмаған болады, яғни матрицада нөлдік элементтер саны көп болады.

Түйіндері көп электрлік жүйелердің күрделі алмастыру схемалары үшін түйіндік өткізгіштік матрицасында нөл емес элементтердің саны шамамен 4n құрайды, ал қалғаны нөлге тең болады;

- А матрицасының диагоналды элементтері нөл болмайды және, әдетте, абсолюттік шамасы бойынша сәйкес жолдың (бағанның) диагоналды емес элементтерінен көп болады;

- сызықты түйіндік теңдеулерді және сызықтандырылған бейсызықты теңдеулерді қолданған кезде жүйенің коэффициенттер матрицасы симметриялы болады.

ЭЕМ-де Гаусс әдісін орындағанда осы ерекшеліктерді ескерген кезде, қажетті жады көлемін және есептеу уақытын төмендету арқылы программаның есептеу тиімділігін елеулі арттыруға мүмкіндік береді.

А матрицасының аз толтырылуын ескеру. А матрицасында нөлдік элементтер санының көптігінде операциялар тек нөлдік емес элементтермен орындалатын және ЭЕМ жадысында тек осы элементтер сақталатын алгоритмді және Гаусс әдісі үшін программаны құру керек.

Бірақ Гаусс әдісінің тура жүрісі қадамдарын орындау кезінде А^(k) матрицасында жаңа нөлдік емес элементтер пайда болады, яғни матрицаның толықтырылуы жоғарылайды.

Бұл, біріншіден, А бастапқы матрицасының толық емес толықтырылуын ескерумен байланысты жадының және есептеу уақытының үнемделуін жоққа шығара алады.

Матрицаның аз толтырылуын ескергеннен эффект елеулі бола алатындықтан, Гаусс әдісінің тура жүрісі процесінде А^(k) матрицасының толығуының минималды жоғарылауын қамтамасыз ететіндей алгоритмді құру қажет.

Егер Гаусс әдісінің тура жүрісінің бір k қадамын қарастырса, онда А^(k) матрицасының k нөмірінен үлкен жолдардың барлығында нөлдік элементтердің саны k жолында ең аз болған кезде толықтырылудың ең аз жоғарылауы орын алады.

Егер бұл шарт орындалмаса, онда сәйкес түрде k -дан n -ға дейінгі нөмірлі теңдеулердің орналасуын өзгерту қажет.

Бірақ әр қадамда бұл критерийді қолдану тура жүрістің n қадамында жадының және есептеу уақытының максимум үнемделуін қамтамасыз ететінін білдірмейді.

ЭЕМ-де орныққан режимдерді есептеу программаларында нөмірлеу алгоритмі логикалық операциялар негізінде орындалады, демек үлкен машиналық уақытты қажет етпейді.

Жүйенің берілген алмастыру схемасы үшін мұндай нөмірлеу режимді есептеу бастағанша бір рет қана орындалады, себебі теңдеуді шешудің итерациялық процесінің әр қадамында матрицаның элементтері өзгерсе де, құрылымы өзгеріссіз қалады.

Матрицаның диагоналды элементтерінің басымдылығын ескеру. Сызықты алгебралық теңдеулер жүйесін шешу барысында есептеу және есептеу дәлдігін қамтамасыз ету кезінде А матрицасының аз ғана толықтырылуын сақтау шарты негізінде теңдеулердің нөмірленуінің және белгісіздердің тізбектелуі таңдалады.

Есептеу дәлдігін қамтамасыз ету шарты бас элемент схемасын қолдану кезінде орындалады.

Жалпы жағдайда берілген шарттардың әрқайсысымен анықталатын теңдеулердің нөмірлеу тізбегі әр түрлі бола алады.

Электрэнергетикалық есептердің шешімдері көрсетіп тұрғандай, жоғары есептеу дәлдігін қамтамасыз ету үшін А матрицасының диагоналды элементтерінің басымдылығына байланысты диагоналды элементтердің құрамын өзгертпейтін теңдеулердің кез-келген нөмірленуі бола алады, яғни екі жолдың ауыстырылуымен сол бағандардың да ауыстырылуы орындалуы қажет.

Сондықтан теңдеулердің және белгісіздердің нөмірленуін А матрицасының аз толықтырылуын ескеру шарты бойынша ғана орындауға болады.

А матрицасының симметриялығын ескеру. А матрицасы симметриялы болған кезде, кері жүрісті Гаусс әдісінің алгоритмін қолдана отырып, ЭЕМ-нің қажетті жады және есептеу көлемін қосымша төмендетуге болады.

Мұндай үнемдеу мүмкіндігі тура жүрістің әр қадамында а_ij^(k) (i, j = k+1, …, n) элементтерімен саналатын А^(k) матрицаның квадраттық блогы да симметриялы болатынымен анықталады.

Демек, А симметриялы матрица кезінде оның жоғарғы немесе төменгі үшбұрыштық бөлігіне ғана сүйену жеткілікті, ал бұл жадының, сол сияқты есептеу мөлшерін де азайтады.

Негізгі әдебиет 1[1-100],

Қосымша әдебиет 1 [430-440]

Бақылау сұрақтары:

1. Кері жүрісті Гаусс тәсілі.

2. Жордан схемасы.

3. Адамар бағалауын қолдану.

4. А матрицасының симметриялығын ескеру.

5. Матрицаның диагоналды элементтерінің басымдылығын ескеру.

Не нашли, что искали? Воспользуйтесь поиском: