Giải hệ phương trình tuyến tính bằng ngôn ngữ lập trình c

TRƯỜNG ĐẠI HỌC VINH KHOA TOÁN HỌC --- NGUYỄN THỊ BÍCH NGỌC GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH BẰNG NGÔN NGỮ LẬP TRÌNH C KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHUYÊN NGÀNH TOÁN - TIN HỌC ỨNG DỤNG

TRƯỜNG ĐẠI HỌC VINH KHOA TOÁN HỌC

-

NGUYỄN THỊ BÍCH NGỌC GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH BẰNG NGÔN NGỮ LẬP TRÌNH C

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHUYÊN NGÀNH TOÁN - TIN HỌC ỨNG DỤNG

TRƯỜNG ĐẠI HỌC VINH KHOA TOÁN HỌC -

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH BẰNG

NGÔN NGỮ LẬP TRÌNH C

Người hướng dẫn : ThS Nguyễn Thanh Diệu

Người thực hiện : Nguyễn Thị Bích Ngọc

Lớp : 49B - Toán - Tin học ứng dụng

Mục lục

Mở đầu 2

Chương 1 Giải đúng hệ phương trình bằng phương pháp Gauss 4

1.1 Ý tưởng 4

1.2 Nội dung phương pháp 5

1.3 Kiểm tra quá trình tính nghiệm 6

1.4 Khối lượng tính 9

1.5 Thuật toán, sơ đồ khối và chương trình 10

Chương 2 Phương pháp giải gần đúng hệ phương trình 16

2.1 Khái niệm 16

2.2 Phương pháp lặp đơn 16

2.3 Phương pháp dây đen 25

2.4 Đưa hệ thống phương trình tuyến tính về dạng thỏa mãn điều kiện hội tụ của phương pháp lăp đơn hoặc phương pháp lặp dây đen 32

2.5 Phương pháp Gauss – Seidel 34

Kết luận 40

Tài liệu tham khảo 41

MỞ ĐẦU

Trong các mô hình kinh tế, y học, sinh hoc và khoa học kỹ thuật thường dẫn đến bài toán giải hệ phương trình tuyến tính Đã có rất nhiều các phương pháp giải đúng hệ phương trình tuyến tinh, chẳng hạn như phương pháp Gauss, Cramer, Choleky… Tuy nhiên, trong trường hợp số ẩn lớn thì việc tính toán trở nên phức tạp Khi đó, việc giải đúng hệ phương trình gặp phải khó khăn Không những thế, các hệ phương trình thường có được từ thực nghiệm nên hệ số của nó thường là những số gần đúng Nên việc giải đúng hệ phương trình trong trường hợp này không những khó thực hiện mà còn không

có ý nghĩa thực tế Trong trường hợp đó, thay vì giải đúng hệ phương trình người ta tìm cách giải gần đúng hệ phương trình tuyến với sai số cho phép với việc tính toán đơn giản hơn

Ngày nay, với sự phát triển của công nghệ thông tin, có rất nhiều ngôn ngữ lập trình hỗ trợ chúng ta trong việc tính toán có thể kể đến các ngôn ngữ lập trình như: Pascal, C, C++ , C# …

Trên cơ lý thuyết giải giải gần đúng hệ phươngng trình và các ngôn ngữ lập trình quen thuộc, chúng tôi chọn đề tài nghiên cứu cho khóa luận là

“phương pháp giải hệ phương trình bằng ngôn ngữ lập trình C” Mục đích

của khóa luận là viết chương trình giải hệ phương trình bằng ngôn ngữ C

Ngoài phần mở đầu và tài liệu tham khảo, Khóa luận được chia làm hai chương

Chương I Phương pháp giải đúng hệ phương trình Nội dung chính của chương

này là nghiên cứu về phương phap Gauss - một phương pháp giải hệ phương trình

có nghiệm đúng và cài đặt thuật toán trên máy tính bằng ngôn ngữ C

như: phương pháp lặp đơn, phương pháp dây đen, phương pháp lặp Gauss – Seidel và cài đặt thuật toán các phương pháp đó bằng ngôn ngữ lập trình C

Khóa luận được thực hiện tại trường Đại học Vinh, dưới sự hướng dẫn

của ThS.Nguyễn Thanh Diệu Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy

về sự nhiệt tình hướng dẫn đã dành cho em trong suốt quá trình hình thành khóa luận Nhân dịp này em xin trân trọng cảm ơn Ban chủ nhiệm khoa Toán, các thầy cô giáo trong khoa Toán trường Đại học Vinh, gia đình và bạn bè đã tạo điều kiện thuận lợi để em được học tập và hoàn thành khóa luận

Mặc dù đã có nhiều cố gắng, song khóa luận không tránh khỏi những thiếu sót Em mong nhận được những ý kiến đóng góp của các thầy, cô giáo

và các bạn đọc để khóa luận được hoàn thiện hơn

Sinh viên

Nguyễn Thị Bích Ngọc

CHƯƠNG I.

GIẢI ĐÚNG HỆ PHƯƠNG TRÌNH PHƯƠNG

PHÁP GAUSS

1.1 Ý tưởng của phương pháp

nghiệm đúng của hệ phương trình sau một số hữu hạn những phép tính sơ cấp (với giả thiết không sai có sai số làm tròn)

trình Khi ma trận hệ số không có gì đặc biệt (A không suy biến) Người ta thường dùng phương pháp này khi ma trận hệ số “đầy”

Cho hệ phương trình:













































1 , 2

2 1 1

1 , 2 2

2 22 1 21

1 , 1 1

2 12 1 11

n n nn n n n n n n n n a x a x a x a a x a x a x a a x a x a x a (1.1) 1.1.1 Bước thuận Dùng phép biến đổi tương đương đưa hệ (1.1) về dạng tam giác trên như sau:                     1 , ) 1 ( 1 , 2 ) 1 ( 2 3 ) 1 ( 23 2 ) 0 ( 1 , 1 ) 0 ( 1 3 ) 0 ( 13 2 ) 0 ( 12 1

n n

n n n

n n n

b x

b x b x

b x

b x b x

b x b x

1.1.2 Bước ngược

Tìm từ hệ (1.2) x n , x n 1, , x1

Các công thức tính toán:

 ( 1)

) 1 ( ) 1 (

kk

11 a

a 

1.2 Nội dung phương pháp

Để đơn giản ta thực hiện giải hệ phương trình bằng phương pháp Gauss với n=4 Ta có hệ phương trình:

) 0 ( 35 4 ) 0 ( 34 3 ) 0 ( 33 2 ) 0 ( 32 1 ) 0 ( 31

) 0 ( 25 4 ) 0 ( 24 3 ) 0 ( 23 2 ) 0 ( 22 1 ) 0 ( 21

) 0 ( 15 4 ) 0 ( 14 3 ) 0 ( 13 2 ) 0 ( 12 1 ) 0 ( 11

a x a x a x a x a

a x a x a x a x a

a x a x a x a x a

a x a x a x a x a

a

a

b j  j

trình đầu) của hệ phương trình (1.3) ta được:

) 1 ( 35 4 ) 1 ( 34 3 ) 1 ( 33 2 ) 1 ( 32

) 1 ( 25 4 ) 1 ( 24 3 ) 1 ( 23 2 ) 1 ( 22

a x a x a x a

a x a x a x a

a x a x a x a

(1.3’)

1 1 1 ) 1 (

2 b x b x b

Trong đó (1)

22

) 1 ( 2 ) 1 ( 2

) 2 ( 35 4 ) 2 ( 34 3 ) 2 ( 33

a x a x a

a x a x a

2 ) 1 ( 2 ) 1 ( 1 ) 2 (

a

a

b j  j

phương trình đầu) ở hệ (1.3”) ta được:

) 3 ( 45 4 ) 3 (

44 x a

3 ) 2 ( 13 ) 2 ( 1 ) 3 (

1j a j a b j

a  

- Từ (1.3”’) ta tìm được :

) 3 ( 45 ) 3 ( 44

) 3 ( 45

3 b b x

x  

3 ) 1 ( 23 4 ) 1 ( 24 ) 1 ( 25

2 b b x b x

x   

2 ) 0 ( 12 3 ) 0 ( 13 4 ) 0 ( 14 ) 0 ( 15

1 b b x b x b x

x    

1.3 Kiểm tra quá trình tính nghiệm

Để kiểm tra quá trình tính ta dùng tổng kiểm tra

0 ( 6

i ij

như một vế phải mới của hệ thống phương trình (1.3) và xét hệ phương trình:

) 0 ( 6 4

1

) 0 (

i j

1

) 0 ( )

0 ( 5

4

1

) 0 ( 4

1

) 0 ( 4

1

) 0 (

) 1 (

j

i ij j

ij i

j ij j

j ij j

j j

ij

a a a

a

a x

a x

x a

Vì đối với mỗi phần tử của cột tổng ta đều thực hiện những phép tính giống như đối với những phần tử của cột ở bên trái cột tổng và nằm trong cùng một hàng và phân tử của cột tổng, nên nếu không có sai số tính toán thì những phần tử của cột tổng phải bằng tổng những phần tử a bên trái tổng Hiện tượng này được dùng để kiểm tra quá trình thuận Quá trình ngược kiểm tra bằng hệ thức (1.9)

a( 0 ) 22

a( 0 ) 32

a( 0 ) 42

a( 0 ) 13

a( 0 ) 23

a( 0 ) 33

a( 0 ) 43

a( 0 ) 14

a( 0 ) 24

a( 0 ) 34

a( 0 ) 44

a( 0 ) 15

a( 0 ) 25

a( 0 ) 35

a( 0 ) 45

a( 0 ) 16

a( 0 ) 26

a( 0 ) 36

a( 1 ) 32

a( 1 ) 42

a( 1 ) 23

a( 1 ) 33

a( 1 ) 43

a( 1 ) 24

a( 1 ) 34

a( 1 ) 44

a( 1 ) 25

a( 1 ) 35

a( 1 ) 45

a( 1 ) 26

a( 1 ) 36

a( 1 ) 46

a( 2 ) 33

a( 2 ) 43

a( 2 ) 34

a( 2 ) 44

a( 2 ) 35

a( 2 ) 45

a( 2 ) 36

a( 2 ) 46

*Nhận xét:

1 Sơ đồ Gauss có thể giải hệ phương trình n ẩn (n > 4)

aji thì căn cứ vào công thức (1.4), (1.5) và (1.6) ta thấy a( 1 )

) 1 ( 34 ) 1 ( 33 ) 1 ( 32

) 1 ( 24 ) 1 ( 23 ) 1 ( 22

a a a

a a a

a a a

) 2 ( 34 ) 2 ( 33

a a

a a

1 (n n

n

+ Phép cộng hoặc trừ

6

) 5 2 )(

1 (n n

n

Vậy số phép toán cần thực hiện:

Sn=

6

) 5 2 )(

1 ( 2

) 1 ( 6

) 5 2 )(

1 (n n n n n n n

) 5 2 )(

1 (

=

6

7 9

1 (n n

1 (n n

1 ( 2

) 1 ( 6

) 1 )(

1 (n n n n  n n n

) 1 )(

1 (

Biến đổi A thành A’ (ma trận tam giác trên)

j = i + 1, …, n

s = s - a ij x j

IER = 1

2 Chương trình giải hệ phương trình bằng phương pháp Gauss

printf("\n nhap n = "); scanf("%d", &n);

printf("\nnhap he so cua phuong trinh :\n");

printf("ma tran vua nhap:");

for(i = 1; i <= n; i + +) {

printf("%3f", a[i][j]);

} // bien doi ma tran he so ve ma tran tam giac tren

{

for(k = 1; i < n; k + +) for(i = k + 1; i < n + 1; i + +) {

if(a[k][k] != 0) p[i] = a[i][k] / a[k][k];

for(j = k + 1; j < n; j + +) a[i][j] - = p[i] * a[k][j];

a[i][n+1] - = p[i] * a[k][n+1];

} printf("\n");

printf("ma tran tam giac tren");

for(i = 1; i <= n; i + +) {

printf("\n");

for(j = 1; j <= n + 1; j + +) printf("%3f", &a[i][j]);

} // tim nghiem theo qua trinh nguoc

for(i = n; i >= 1; i - -)

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

for(j = i + 1; j < n + 1; j + +)

s - = a[i][j] * x[j];

CHƯƠNG II

CÁC PHƯƠNG PHÁP GIẢI GẦN ĐÚNG HỆ

PHƯƠNG TRÌNH

2.1 Ý tưởng chung

- Phương pháp lặp là phương pháp mà cho nghiệm đúng X của hệ phương

những nghiệm gần đúng

là nghiệm gần đúng của hệ phương trình, do đó ta chỉ nhận được nghiệm gần đúng với một sai số có thể ước lượng được

- Phương pháp lặp thường dùng khi ma trận A là ma trận “thưa”

34 33 32 31

24 23 22 21

14 13 12 11

2.2.2 Nội dung phương pháp

- Để giải hệ phương trình (2.2) ta cho một vector, gọi là vector xấp xỉ đầu, ký

- Vector X (k) gọi là vector thứ k Nếu dãy những cặp vector lặp X (0) , X (1) ,…,

2.2.3 Sự hội tụ của phương pháp lặp

Định lý 2 2.3 Nếu || || p <1 thì quá trình lặp (2.3) hội tụ về nghiệm của hệ (2.1) theo chuẩn p với bất kì X0 ban đầu

) ( ) (

) (      

ij k

E S

S    Theo tính chất chuẩn ma trận thì

q p q

) (

) (

ij k

S S

Theo tính chất của chuẩn ta có:

) 0 ( )

( )

0 ( )

( )

(

X S

S S X S

S

X k    k   k    k     k

p k

p p

k p k

X S

S S

p p

k p p

X k = X k1 + u

Từ đó ta suy ra :

X k+1 - X k =  (X k - X k-1 )

Với số nguyên dương r nào đó ta xét:

||(x) -(y)|| p = ||(X - Y)|| p || || p ||X - Y||

2.2.5 Điểm dừng của phương pháp lặp đơn

bước lặp k cần thực hiện phải thỏa mãn bất đẳng thức sau:

p p

||

||

ln :

- x i = b i + a ij * x j.

- In nghiệm (x i ) n*1.

- End

2.2.6.2 Sơ đồ khối

char tt;

while (1)

{

printf("\n nhap n = "); scanf("%d", &n);

printf("\nnhap he so cua phuong trinh :\n");

printf("%3f", &a[i][j]);

} printf("\n nhap ma tran b\n");

for(i = 1; i <= n; i + +)

//tim nghiem

for(i = 1; i < n; i + +) s[i] = a[1][1];

x[i] = b[i];

for(i = 1; I < n; i + +) for(j = 1; j < n; j + +) s[i] += a[i][j];

if(max(abs(s[i])) < 1) {

for(i = 1; i < n; i + +) for(j = 1; j < n; j + +) x[i] = b[i] + a[i][j] * x[i-1];

} //in nghiem

printf("\n nghiem cua he la\n");

for(i = 1; i <= n; i + +) printf("\n%.3f\n", x[i]);

printf("\n tiep tuc hay khong(c/n)\n");

n n

2 22

21

1 12

2 1

ij x

1

 , (i=1,…,n)

2.3.2 Nội dung phương pháp

Tự cho một vector gọi là vector gọi là vector xấp xỉ đầu, ký hiệu là

j x

2

) ( 2



X( 1 ) 1

i

j

k j

ij x

1

) (

- Nếu dãy những vector x (0) , x (1) , …, x (k) , …có giới hạn thì giới hạn ấy là

nghiệm của hệ phương trình (2.2)

2.3.3 Sự hội tụ của phương pháp

Do phương pháp dây đen là biến dạng của phương pháp lặp đơn nên điều kiện hội tụ của phương pháp dây đen hoàn toàn giống với phương pháp lặp đơn hay là:

2.3.4 Đánh giá sai số của nghiệm gần đúng

của hệ phương trình (2.2) người ta sử dụng công thức sau:

a ; qi = 



n

j ij

1 ( 





1 ( 

- Sau khi tính xong x(k 1 )

i nữa và có thể đặt x(k 1 )

i

- Phương pháp lặp dây đen có ưu điểm hơn phương pháp lặp đơn khi n lớn

2.3.5 Thuật toán và chương trình

{

if(a[i] > max) max = a[i];

printf("\n nhap n = "); scanf("%d", &n);

printf("\nnhap he so cua phuong trinh :\n");

printf("%3f", &a[i][j]);

} printf("\n nhap ma tran b\n");

for(i = 1; i <= n; i + +)

printf("\n%f", b[i]);

//tim nghiem

for(i = 1; i < n; i + +) s[i] = a[i][1];

x[i] = b[i];

for(i = 1; i < n; i + +) for( j = 1; j < n; j + +) s[i] += a[i][j];

if(max(abs(s[i])) < 1) {

for( i = 1; i < n; i + +) for( j = 1; j < i - 1; j + +) tong1 + = a[i][j] * x[j];

for( i = 1; i < n; i + +) for( j = i; j < n; j + +) tong2 + = a[i][j] * x[j];

for( i = 1; i < n; i + +)

for( j = 1; j < n; j + +) x[i] = tong1 + tong2 + b[i];

} //in nghiem

printf("\n nghiem cua he la\n");

for(i = 1; i <= n; i ++) printf("\n%.3f\n", x[i]);

printf("\n tiep tuc hay khong(c/n)\n");

2.4.1 Ý tưởng

Ở mục 2 và mục 3 ta đã biết, muốn giải một hệ phương trình Ax = B bằng

phương pháp lặp đơn hoặc phương pháp dây đen ta phải đưa về dạng tương

1

 <1

, x (2) , …, x (n)nhận được từ phương pháp lặp đơn hoặc phương pháp dây đen sẽ hội tụ đến nghiệm duy nhất của hệ phươn trình đã

Đối với hệ phương trình ban đầu:

Phương pháp lặp đơn hoặc phương pháp lặp dây đen sẽ hội tụ nếu điều kiện sau thỏa mãn:

ij

a 

i j ij

Khi đó ta có thể đưa hệ phương trình ban đầu về dạng:

x =   x

Khi đó nếu hệ phương trình Ax = B đã cho bất kì thì bằng cách dùng

những biến đổi sơ cấp thích hợp ta có thể đưa hệ về dạng thỏa mãn điều kiện (2.13)

2.4.2 Nội dung thực hiện

- Lấy những phương trình ở hệ Ax = B mà các hệ số của chúng thỏa mãn

điều kiện (2.13)

- Sắp xếp các phương trình ấy vào các hàng của hệ phương trình mới sao cho hệ số có trị tuyệt đối lớn nhất của mỗi phương trình chính là phần tử nằm trên đường chéo chính của ma trận hệ số của phương trình mới

- Từ những phương trình đã và chưa được dùng đến của hệ phương trình ban đầu ta thành lập những tổ hợp tuyến tính, độc lập tuyến tính để tạo ra những phương trình thỏa mãn nguyên tắc lựa chọn nêu trên

- Xếp các phương trình đó vào những vị trí thích hợp của những hàng còn lại của hệ phương trình mới

- Sau đó ta dùng phương pháp lặp đơn hoặc lặp dây đen giải hệ phương trình mới suy ra nghiệm của phương trình ban đầu

Chú ý:

Ở hệ phương trình mới mỗi phương trình được dùng ở hệ phương trình ban đầu phải có mặt trong tổ hợp tuyến tính để tạo nên một phương trình nằm trong hàng còn lại của hệ thống phương trình mới

2.5 Phương pháp Gauss – Seidel

2.5.1 Ý tưởng và nội dung phương pháp

- Định nghĩa ma trận đường chéo trội:

đây được thỏa mãn:

i = 1 ,n 

j i ij

a < a ii

j = 1 ,n 

i ij

ij x

a + 

i j j

j i





có  < 1

2.5.2 Sự tồn tại của phương pháp

Phương pháp Gauss – Seidel hội tụ:

2.5.3 Thuật toán,sơ đồ khối và chương trình

2.5.3.1 Thuật toán:

Bước 5: Cho i chạy từ 1 đến n

Bước 6: Kiểm tra i = 1 hay không?

Bước 12: Kết thúc chương trình

2.5.3.2 Sơ đồ khối

printf("\n nhap n="); scanf("%d",&n);

printf("\n nhap he so cua phuong trinh :\n");

for(i = 1; i <= n; i + +)

{

scanf("%f", &a[i][j]);

} for(i = 1; i <= n; i + +) {

printf("%3f", &a[i][j]);

} printf("\n nhap ma tran x\n");

piv = a[i][i];

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

y = x[i];

for(i = 1; i <= n; i + +) printf("\n%.3f\n", x[i]);

printf("\n tiep tuc hay khong(c/n)\n");

tt = getch();

if(tt! = 'c') break;

} }

Kết luận

Khóa luận đạt được các kết quả sau:

- Hệ thống hóa các kiến thức về giải đúng và giải gần đúng hệ phương trình tuyến tính

- Viết thuật toán và sơ đồ khối đối với phương pháp Gauss giải đúng hệ phương trinh, đối với phương pháp lặp đơn, lặp Dây đen, lặp Gauss- Seildel

Tài liệu tham khảo

[1] Nguyễn Thanh Thủy-Tạ Tuấn Anh, Nhập môn ngôn ngữ C

NXB Khoa học kỹ thuật, 2005

[2] Phạm Văn Ất, Lập trình C NXB Khoa hoc kỹ thuật

[3] Trần Xuân Sinh, Phương pháp tính , Khoa Toán – Đại học Vinh

[4] Dương Thủy Vỹ, Giáo trình phương pháp tính , NXB Khoa học và kỹ

thuật 2005

[5] Phạm Kỳ Anh, Giải tích số , NXB Đại học quốc gia Hà Nội,1998