báo cáo chủ đề 8 phương pháp gauss

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.18 MB, 25 trang )

Trang 1<div class="page_container" data-page="1">

VIỆN TOÁN NG DỨỤNG VÀ TIN H C Ọ

</div>Trang 2<div class="page_container" data-page="2">

Lời nói đầu

hơn trong cách sử dụng.

</div>Trang 3<div class="page_container" data-page="3">

3.2. Nghi m c a h ệ ủ ệ phương trình tuyến tính...4

3.3. Biến đổi tương đương...4

</div>Trang 4<div class="page_container" data-page="4">

Hệ phương trình tuyến tính và khái niệm cơ bản

a11x1 + a12 2 + ... + a1n n = b x x 1

a21x1 + a22x2 + ... + a2nxn = b (1.1) 2 ... am1x1 + am2 2 + ... +amn n = bm x x

Trong đó, các hệ số aij, bi thuộc trường K. Trong phạm vi báo cáo ta coi K R. T ≡ ừ đây ta có các định nghĩa sau:

a. Các h s c a hệ ố ủ ệ phương trình lập thành m t ma tr n A, g i là ộ ậ ọ

A = a a ... a 21222n ... a a ... am1m2mn

tự do g i là ọ ma tr n m r ng c a hậ ở ộ ủ ệ:

a11 a ... a b 121n1 𝐴 = a a ... a b 21222n2... a a ... a bm1m2mnm

</div>Trang 5<div class="page_container" data-page="5">

4

c. Ma trận B thu đượ ừ cột hệ s tc t ố ự do, gọi là ma trận hệ s t ố ự

B = b 2 ... b m

trình, thì hệ phương trình đấy có th viể ết dướ ại d ng: A.X = B (1.2)

Từ đây về sau, ta sử dụng dạng trên để biểu diễn hệ phương trình là ch y u. ủ ế

Mỗi nghi m cệ ủa hệ phương trình (1.2) là mộ ộ s p tht b ắ ứ tự (c ,c ,...c12n) thỏa mãn t t c ấ ả các phương trình của hệ (1.2) được thỏa mãn khi thay các n xẩ i tương ứng bởi c i

M t hộ ệ phương trình có thể có duy nh t nghi m, vơ s nghi m ấ ệ ố ệhoặc vô nghi m. ệ

Hai hệ phương trình được gọi là tương đương nếu hai h ệ

</div>Trang 6<div class="page_container" data-page="6">

Các phép biến đổi sơ cấp c a hủ ệ phương trình là các phép biến đổi:

a. Nhân một phương trình nào đó của h v i m t s khác 0. ệ ớ ộ ố b. C ng vào mộ ột phương trình nào đó của h v i mệ ớ ột phương trình khác đã nhân với một số khác 0.

c. Đổi chỗ hai phương trình của h . ệTừ đây, ta có thể rút ra một số nhận xét sau:

- Các phép biến đổi sơ cấp c a hủ ệ phương trình tương ứng v i ớcác phép bi n ế đổi trên hàng c a ma tr n m r ng c a h . ủ ậ ở ộ ủ ệ

- Khi th c hi n các phép biự ệ ến đổi sơ cấp, ta thu được m t h ộ ệ

M t hộ ệ phương trình Cramer là mộ ệ phương trình mà số ẩt h n bằng số phương trình và định thức của ma trận hệ số khác không.

Từ đây, ta có thể phát biểu định lý Cramer.

nghiệm. Chứng minh:

</div>Trang 7<div class="page_container" data-page="7">

6 A.X=B

Do đây là hệ phương trình Cramer nên ta có: det(A) ≠ 0

Như v y t n t i ma tr n nghậ ồ ạ ậ ịch đảo c a A là ủ 𝐴−1.Nhân c hai v ả ếcủa hệ phương trình ban đầu với 𝐴−1ta được:

𝑋 = 𝐴−1.𝐵

Như vậy hệ phương trình đã cho có nghiệm duy nhất là: 𝑋 = 𝐴−1.𝐵

b. Định lý Kronecker – Capelli và các hệ quả

Trong định lý này, ta sẽ nêu ra điều kiện để một hệ phương trình t ng qt có nghiổ ệm, cũng như các hệ qu xung quanh. ả

a11x1 + a12 2 + ... + a1n n = b x x 1 a21x1 + a22 2 + ... + a2n n = b x x 2

... am1x1 + am2 2 + ... +amn n = b x x m

Có nghi m khi và ch khi h ng c a ma tr n h s b ng h ng c a ệ ỉ ạ ủ ậ ệ ố ằ ạ ủma tr n m r ng. ậ ở ộ

Từ đây, ta rút ra hai hệ quả quan trọng sau:

</div>Trang 8<div class="page_container" data-page="8">

Hệ qu 1.2.1ả : N u h ế ệ phương trình (1.1) với n ẩn có 𝑟𝐴 = 𝑟A= thì 𝑛hệ có nghi m duy nh t. ệ ấ

Chứng minh:

Giả sử hệ có = 𝑟𝐴 𝑟A= 𝑛 . Khi đó tồn tại định thức con cơ sở ủ c a của M (định th c con khác 0), c A và ứ ả A. Bây giờ chúng ta s chẽ ứng minh r ng m i dòng c a ằ ỗ ủ A khác với n dòng đầu tiên là t h p tuy n ổ ợ ế

hệ phương trình:

a11x1 + a12 2 + ... + a1n n = b x x 1 a21x1 + a22 2 + ... + a2n n = b x x 2

... A xn1 1 + an2 2 + ... +ann n = b x x n

Do M ≠ 0 nên hệ này là một hệ Cramer, vì vậy nó có nghiệm duy nhất theo định lý Cramer.

vào n - 𝑟𝐴 tham s . ốChứng minh:

Gi sả ử 𝑟𝐴 = 𝑟A < n. Kí hiệu M là định thức con cơ sở ủ c a A và A.

A. Do đó:

</div>Trang 9<div class="page_container" data-page="9">

8

a a ... a 11121rM = a a ... a 21222r

... a a ... a r1 r2r

Bởi vì mỗi dòng thứ i của A, là tổ ợ h p tuyến tính của r dịng đầu tiên nên hệ đã cho tương đương với:

𝑎11𝑥1 + 𝑎12𝑥2 + + ⋯ 𝑎1𝑛𝑥𝑛 = 𝑏1− 𝑎1( +1)𝑟 𝑥(𝑟+1) − ⋯ − 𝑎1𝑛 𝑛𝑥 𝑎21𝑥1 + 𝑎22𝑥2 + + ⋯ 𝑎2𝑛𝑥𝑛 = 𝑏2− 𝑎2( +1)𝑟 𝑥(𝑟+1) − ⋯ − 𝑎2𝑛 𝑛𝑥 (1.3) ...…

𝑎𝑟1𝑥1 + 𝑎𝑟2𝑥2 + + ⋯ 𝑎𝑟𝑟𝑥𝑟 = 𝑏𝑟 − 𝑎𝑟(𝑟+1) (𝑟+1) − 𝑥 ⋯ 𝑎𝑟𝑛𝑥n − Đây là một hệ phương trình Cramer r phương trình r ẩn , 𝑥1 𝑥2, …, . 𝑥𝑟Với mỗi bộ giá tr (ị 𝑐𝑟+1, … , 𝑐𝑛) của các n (ẩ 𝑥𝑟+1, … , ) ta đượ𝑥𝑛 c m t ộnghiệm của (1.3) là (𝑐1, … , 𝑐𝑟). Khi đó (𝑐1, 𝑐2, … , 𝑐𝑟, 𝑐𝑟+1, … , 𝑐𝑛) là nghiệm của (1.1).

trình vơ nghi m ho c có vơ s nghi m. ệ ặ ố ệ

</div>Trang 10<div class="page_container" data-page="10">

Phương pháp Gauss

4.1. Ý tưởng phương pháp:

Phương pháp Gauss (Gauss Elimination) là một phương pháp

ma trận hình thang (Row echelon form), sau đó sẽ ả ần lượ ừ gi i l t t ng

ở dưới sẽ đơn giản hơn (ít ẩn hơn), và khi đó việc tìm t ng giá tr c a ừ ị ủẩn thỏa mãn hệ phương trình sẽ ễ dàng hơn. d

Như đã nói ở trên, phương pháp Gauss là việc th c hi n nh ng ự ệ ữphép biến đổi tương đương trên ma trận m r ng c a hở ộ ủ ệ phương trình tuyến tính, hoặc phép thế để gi i hả ệ phương trình này. Và ở đây, tôi

*Cho ma tr n ậ

E : a111x1 + a12x2 + ... + a1n n = b x 1

E : a221x1 + a22x2 + ... + a2nxn = b2 (4.1) ...

En: am1x1+ am2x2 + ... + amnxn = bm - Ta tách hệ phương trình trên thành d ng ma trạ ận:

</div>Trang 11<div class="page_container" data-page="11">

10 A.X = B Trong đó:

]; B = [𝑏1

𝑎11𝑥1 + 𝑎12𝑥2 + ⋯ + 𝑎1𝑛 𝑛 = 𝑥 𝑎1.𝑛+1

𝑎22𝑥2 + ⋯ + 𝑎2𝑛𝑥𝑛 = 𝑎2. +1𝑛 (4.3) …………

𝑎m𝑛𝑥𝑛 = 𝑎m. +1𝑛

</div>Trang 12<div class="page_container" data-page="12">

Trong đó các phần tử ở cột n+1 tương ứng với , 𝑏1 𝑏2, … , 𝑏m. +) Quy trình ngh ch: ị

T h (4.3) giừ ệ ải ra ta được x ; x ; ... x b ng phép th d n và k t nn-11 ằ ế ầ ếquả đó cho ta nghiệm của hệ phương trình (4.1).

Một số ví dụ: VD1: Gi i hpt: ả

x + 2y + z t = 1 – 2x + 3y 5z + t = 2 – 3x+ 5y 4z =3 –

Ta t o ra ma tr n b sung ạ ậ ổ 𝐴 :

1 2 1 −1 12 3 −5 1 23 5 −4 0 3)

Biến đổi về ma trận bậc thang 𝐴′ (10 −1 −72 1 −1 13 0

) Ta lần lượt giải ra được:

x = 1 + 13t1 – 5t 2 y = -7t + 3t 12 z = t 1

t = t 2

</div>Trang 13<div class="page_container" data-page="13">

12 VD2: Gi i hpt: ả

x + y + z = 3 2x y + 2z = 3 – – x 3y 3z = 5 – – –

4.3.Thuật toán và code:

Ta t o ra ma tr n b sung ạ ậ ổ 𝐴 :

2 −1 2 −31 −3 −3 −5)

Biến đổi về ma trận bậc thang 𝐴′ (

) Ta l n ầ lượt giải ra được: x = 1 y = 3 z = 1 −

</div>Trang 14<div class="page_container" data-page="14">

- Sau khi d ng vịng lừ ặp thì có được v ị trí đầu tiên c a ma tr n ủ ậkhác 0 (a[i][j] ≠ 0 v i j bé nh t, i bé nh t) ớ ấ ấ

- Nếu i ≠ 1 thì đảo hàng i và 1.

// Biến đổi về ma trận bậc thang

voidmatranbacthang() { inti = 1, = j1

// Đi tìm phần tử khác 0 đầu tiên (đi từ trên xuống dưới, trái sang phải)

while (ISZERO( [ ][a i j])) { ++; i

(ifi == + ) { m1

i = ; 1j++; ifj == + ) { n2

countzeros(); return;

} // Duyệt đến phần tử cuối cùng mà vẫn chưa thấy thì ma trận A là ma trận 0

} }

cout<<"Vi tri dau tien khac 0: "<<i<< " "<< << jendl; if ( != ) i1daohang(, );

Bước 2: Bắt đầ ặ ừ ộu l p t c t th j vứ ừa tìm đượ ởc trên - Vịng l p for tặ ừ j tìm đượ ở bước 1, tăng j đến n+1: c

+ Vòng l p vặ ới hàng i, i = 2 đến i = m, n u aế [i][j] khác 0 thì bắt đầu tìm hàng k để khử hàng hiện tại:

1. Kh i t o m t bi n flag = false ở ạ ộ ế 2. vòng l p for k = i ặ – 1 đến k = 1:

N u aế [k][j] khác 0 và a[k][0] = j 1 thì gán flag = –true và thốt vịng l p. ặ

3. N u flag = true thì: ế a. gán ratio = a[i][j] / a[k][j]

</div>Trang 15<div class="page_container" data-page="15">

14

b. Ch y vòng lạ ặp for z = j đến z = n+1, gán a[i][z] = a[i][z] – ratio*a[k][z]

4. Sau khi kh xong c t, s p x p l i hàng thành d ng ử ộ ắ ế ạ ạbậc thang.

// In ma tr n sau m i l n kh c t và sau khi biậ ỗ ầ ử ộ ến đổi.

// Bắt đầu lặp từ cột thứ j vừa tìm được ở trên đến n

for (; j <= + ; ++) { n1j

for ( = ; <= ; i2im i++) {

// Nếu a[i][j] khác 0 ta bắt đầu khử

if (!ISZERO( [ ][a i j])) {

intk; // Tìm hàng k để a[k][j] khác 0 và a[k][l] = 0 với mọi l<j

boolflag = false;

for ( = - k i1; >= ; --) {k1k // Tìm từ hàng i-1 trở lên

(!ifISZERO(a[k j][]) && [ak][0] == - ) { j1

flag = true; // Đã có hàng k thỏa mãn

break; } }

(!ifflag) continue; //Nếu khơng tìm thấy k ta tiếp tục tăng i // Lấy hàng i trừ đi aij/akj lần hàng k và gán cho hàng i

Sau đó bắt đầu sắp xếp

Vòng l p for t ặ ừ z = i đến z < m Gán MIN = z,

</div>Trang 16<div class="page_container" data-page="16">

vòng l p for t ặ ừ k = z + 1 đến k ≤ m, nếu a[k][0] < a[MIN][0] thì cho MIN = k, sau khi tìm được hàng có s s 0 nh nh t là hàng MIN ố ố ỏ ấđổi ch hàng aỗ [MIN] với hàng a [z]

// Sắp xếp lại thứ tự các hàng từ hàng i theo tăng dần số số 0 ở đầu bằng sắp xếp lựa chọn

voidsapxeplaihang(inti = 1) { intMIN;

countzeros( );i // Cập nhật lại số số 0

for (intz = ; < ; i z m z++) { MIN z = ;

for ( = + ; <= ; intk z1km k++) (ifa[ ][k0] < a MIN[][0]) MIN k = ; daohang(MIN, z);

}

+) Quy trình ngh ch: ị

Phần 1: Xác định loại nghi m ệ

Vòng l p for tặ ừ i = m đến 1, n u aế [i][0] = n (hàng i full 0) thì: Giảm rank A, nếu a[i][n+1] = 0 thì gi m rank ả 𝐴

ngược lại thì hàng i có phần t khác 0, d ng vịng lặp và ta có ử ừrank A.

N u rank A = rank ế 𝐴 < n là Vô s nghi m ố ệ N u rank A = rank ế 𝐴 = n là Nghi m duy nh t ệ ấ Còn l i là Vô nghiạ ệm. → In ra “vô nghiệm”.

// Xác định hệ có nghiệm duy nhất, vơ số nghiệm hay vô nghiệm

intxacdinhloainghiem() {

intrankA m rankAn m = , = ; // rank A va rank A ngang

for (inti = ; >= ; --) { m i1i

(ifa[ ][i0] == ) {n // Số số 0 ở hàng i == n tức là hàng full 0

</div>Trang 17<div class="page_container" data-page="17">

16

rankA--;

ifISZERO( [ ][a i n + ])) 1rankAn--; // Giá trị ở cột bổ sung

} elsebreak; }

ifrankA == rankAn && rankA n < ) returnrankA; // Vô số nghiệm

ifrankA == rankAn && rankA == ) nreturn -1; // Nghiệm duy nhất

return -2; // Vô nghiệm

// Kiểm tra nghiệm trong trường hợp hệ có nghiệm duy nhất

boolkiemtra(double , *intoffset = 0boolparam = false) { ifstreamfi checkfile();

fi>> m>>n

for (inti = ; < ; 0i m i++) { doubletmp = 0.0, aij0.0; for ( = ; < ; ++) { intj0j n j

fi>> ; aij

tmp += * aijx j[ + + 1offset]; }

fi>>aij;

((ifparam && !ISZERO(tmp)) || (!param && fabs(tmp - aij) > 1e-6)) returnfalse;

</div>Trang 18<div class="page_container" data-page="18">

} fi.close(); returntrue; }

// Giải nghiệm trong trường hợp có nghiệm duy nhất

voidgiainghiemduynhat() { double *x = newdouble[n + ](); 1

for (inti = ; >= ; --) { n i1i

x i[] = a i[ ][n + ]; 1

for ( = ; > ; --) intj n j i jx i[ ] -= x j[] * a i[ ][j]; x i[] /= a i i[ ][];

}

cout<<"He co nghiem duy nhat"<< endl;

for (inti = ; <= ; ++) 1in icout<<"x_"<<i<<" = "<<x i[] << endl; ifkiemtra(x)) cout<< endl <<"---> True"<< endl;

else cout<< endl <<"---> False"<< endl; };

+ Vô s nghi m: ố ệ

- T o m t m ng 2 chiạ ộ ả ều lưu nghiệm x m i dòng là 1 vector ỗnghiệm

Vòng l p for tặ ừ i = 0 đến i < n thì x[i+1][i] = 1 - Bi u di n n này qua n khác: ể ễ ẩ ẩ

Cho i = rank A, bắt đầu ch y t ạ ừ hàng i đến hàng 1 cho j = a[i][0], k = 0, a = aij[i][j+1]

Gán vector nghi m x = vector 0 ệ j x[0][j] = a[i][n+1] / a ij

Khi k ≤ n, nếu k khác j+1 thì x[k][j] = x[j][k] – a[i][k] / aij, tăng k.

– Th ẩn này vào ẩn kia (x biế i ểu diễn qua x v i i < j) j ớ

</div>Trang 19<div class="page_container" data-page="19">

18 Vòng l p for tặ ừ i = 0 đến i < n,

Vòng l p for tặ ừ j = i +2 đến j ≤ n, nếu x[j][i] khác 0 thì cho tmp = x[j][i],

vòng l p for tặ ừ z = 0 đến z = n (th x vào x ) ế ji x[z][i] = x[z][i] + tmp*x[z][j-1] x[j][i] = x[j][i] – tmp

Cuối cùng thu được các vector nghiệm Sau đó in ra nghiệm

Gói ki m tra l i nghi m. ể ạ ệ

// Giải nghiệm trong trường hợp vô số nghiệm

voidgiainghiemtongquat(intrankA) { double ** ; x

// Tạo một ma trận lưu nghiệm

= xnewdouble *[n1];

for (inti = ; <= ; ++) 0in ix[] = newdouble[n](); for (inti = ; < ; 0i n i++) x[ + 1][i] = 1

cout<<"Rank A: "<<rankA<< endl;

// Biểu diễn ẩn này qua ẩn khác (x1 = 0 -2x2 - 3x3 - 3.5x4)

inti = rankA; while (i >= ) { 1

</div>Trang 20<div class="page_container" data-page="20">

for (intz = 0; <= ; ++) zn zx z[ ][i] = x z i[ ][] + tmp x * [ ][z j - 1]; // Thế xj vào xi

x j i[ ][] = x j[ ][i] - tmp; // Phải trừ đi vì xi = bi + ai*xi + ...,\

nếu ai = 1 (xi được chọn làm tham số) thì sau vịng lặp for trên xij = ai + tmp,\

nếu ai = 0 (xi được biểu diễn qua ẩn khác) thì sau vịng for xij = tmp,\

cả 2 trường hợp đều cần trừ đi tmp để đúng với hệ số

}

// In nghiệm

for (inti = ; < ; 0i n i++) {

cout<<"x_"<

cout<< " "<< showpos <<x[j i][ ] << noshowpos <<"x_"<< ; j

cout<<endl; }

// Kiểm tra lại nghiệm

2x1 – x + 2x = 23 –3 x1 – 3x2 – 3x = 5 3 –

</div>Trang 22<div class="page_container" data-page="22">

Ví d 3: Ví d th hi n thuụ ụ ể ệ ật toán đã giải quyết được vấn đề hệ không full hạng.

x + 2x + 3x + 5x = 0 12342x1 + 4x + 6x + 7x = 0 2343x1 + 6x + 5x + 4x = 0 234

Ví d 4: Ví d th hi n thuụ ụ ể ệ ật toán đã sửa đượ ỗ ắc l i s p x p l i ma ế ạtrận v d ng bề ạ ậc thang.

x + 2x + 3x + 4x + 5x + 7x = 7 123456 2x + 4x + 6x + x1234 – 2x + 3x = 3 56 3x + 6x + 7x + 4x1234 – 8x + 6x = 6 56 4x + 8x + 10x + x1234 – 15x +2x = 256

</div>Trang 23<div class="page_container" data-page="23">

22

+) Ở đây ta nêu ra mộ ố đặc điểt s m của phương pháp Gauss: - Là một phương pháp giải đúng nghiệm c a hủ ệ phương trình - Chia ra làm hai bướ Bước: c thuận và bước ngh ch ị

- Ý tưởng đơn giản, tuy nhiên vi c cách xệ ử lí để đưa ra nghiệm lại khá ph c t p khi có khá nhiứ ạ ều trường hợp đặc bi t. ệ

+) Ưu điểm:

- Có th s d ng gi i h v i sể ử ụ ả ệ ớ ố phương trình và ẩn khơng cố định. - Có th gi i cể ả ả phương trình có định thức = 0

- Khối lượng phép tính nh v i h n ỏ ớ ệ ẩn n phương trình: N = 𝑛3 (n2+3n−1 ố) s phép nhân ( chia)

C = 𝑛2 (2n2+3n−5) số phép cộng ( trừ)

+) Nhược điểm: khi giải nghiệm ta phải chia cho aii(k) ≈ 0 thì nghiệm s g p sai sẽ ặ ố lớn

+) So sánh với các phương pháp khác:

- Sai s tính tốn khuố ếch đại hơn so với phương pháp

phần tử trội.

hiệu để giải đúng những hệ phương trình tuyến tính có kích thước

</div>Trang 24<div class="page_container" data-page="24">

nhỏ. Tuy vậy, nó cũng có mộ ố h n ch v tt s ạ ế ề ốc độ, khả năng thực hiện song song, … Do vậy, nó thường được sử dụng ở những hệ có

đượ ực l a ch n vì nh ng l i ích v tọ ữ ợ ề ốc độ mà nó mang lại.

</div>

báo cáo chủ đề 8 phương pháp gauss

<b>VIỆN TOÁN NG D</b>Ứ<b>ỤNG VÀ TIN H C </b>Ọ

<b>Lời nói đầu </b>

<b> </b>Phương pháp Gauss

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về