Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Thuật toán khử gauss trong giải hệ phương trình tuyến tính
23/10/2008

Lịch sử phát triển của loài người đã cho thấy rằng, con người luôn mong muốn tìm ra những phương pháp và công cụ, để phục vụ cho công việc tính toán đầy “cực khổ” của mình. Và con người đã thực sự đạt được những thành tựu to lớn. Nhà toán học người Pháp Laplace đã nói rằng: “việc phát minh ra Lôgarit (bảng Lôgarit) đã kéo dài tuổi thọ của các nhà tính toán”. Nhưng mãi cho đến khi phát minh ra máy tính điện tử, con người mới thật sự có được một công cụ hỗ trợ tính toán đắc lực và hiệu quả. Ngày nay hầu hết các công việc tính toán phức tạp trong khoa học kỹ thuật đều do máy tính đảm nhiệm. Do đó việc tìm ra và cài đặt cho máy tính những thuật toán tốt là một yêu cầu thực tế. Một trong những tính toán cơ bản và hay gặp là giải hệ phương trình tuyến tính (HPTTT).


Một HPTTT được định nghĩa là hệ gồm m phương trình đại số bậc nhất đối với n ẩn số có dạng như sau:


Hệ phương trình (I) còn được viết dưới dạng ma trận như là:AX=B (II)

Trong đó ma trận A được gọi là ma trận Hệ Số, ma trận B được gọi là ma trận vế phải, còn ma trận X là ma trận ẩn. Khi số phương trìnhbằng số ẩn (m=n) và định thức của ma trận hệ số ?0 (Det(A)?0),ta gọi hệ phương trình trên là hệ Cramer. Thông thường chúng ta hay làm việc với hệ Cramer, nên ở đây ta chỉ quan tâm đến hệ Cramer và nói đến HPTTT ta mặc định hiểu là hệ Cramer.

Để giải HPTTT chúng ta có nhiều phương pháp, được chia làm hai loại. Các phương pháp trực tiếp hay phương pháp giải chính xác và các phươngpháp gián tiếp hay phương pháp lặp. Thuật toán khử Gauss là một phương pháp giải HPTTT trực tiếp và hẳn là đã rất quen thuộc với mỗi chúng ta. Nó là một phương pháp tốt, thích hợp để cài đặt trên máy tính, được khám phá ra cách đây khoảng 160 năm. Khử Gauss là một thuật toán đã được cài đặt sẵn trongcác thư viện chương trìnhcủa hầu hết các ngôn ngữ lập trình bậc cao phổ dụng như APL hay BASIC. Với các HPTTT có số phương trình nhỏ, con người có thể áp dụng thuật toán Gauss và cho ra kết quả. Nhưng với những HPTTT có số phương trình lớn hoặc rất lớn rõ ràng con người cần đến sự trợ giúp của Máy Tính. Bây giờ chúng ta sẽ tìm hiểu cách cài đặt thuật toán khử Gauss trên ngôn ngữ lập trình Pascal. Với mục đích tạo ra một chương trình giải các HPTTT lớn phục vụ cho học tập và nghiên cứu, và quan trọng hơn là rèn luyện kỹ năng cài đặt các thuật toán toán học. Tư tưởng chính của thuật toán Gauss là bằng các phép biến đổi tương đương:

1) Nhân hai vế một phương trình của HPTTT với cùng một số khác 0.

2) Cộng một phương trình với phương trình khác sau khi nhân phương trình đó với một số.

3) Đổi vị trí hai phương trình trong HPTTT cho nhau.

Đưa HPTTT đã cho về hệ tam giác trên, rồi giải HPTTT tam giác trên.


Sau đây là chương trình cài đặt của thuật toán Gauss trên Free Pascal. Free Pascal là là trình biên dịch được chọn lựa, để chương trình có tốc độ thi hành nhanh và dữ liệu lớn. Vì số ẩn của HPTTT lớn nên ta tạo và chỉnh sửa dữ liệu trong một tệp văn bản. Dữ liệu vào từ tệp văn bản Gauss.inp, gồm dòng đầu chứa một nguyên Nlà số ẩn hay số phương trình của hệ. N dòng tiếp theo mối dòng gồm N+1 số nguyên biểu diễn ma trận hệ số và ma trận vế phải của HPTTT. Kết quả được ghi ra màn hình, nếu hệ có nghiệm thì lưu vào tệp Gauss.out gồm N dòng, dòng thứ i ghi nghiệm thứ i của HPTTT.


ProgramGiai_He_Cramer;

UsesCrt;

Const Max=1000;{So Phuong trinh lon nhat la 1000 }

Flag:byte=0;

TypeMatran_Heso=Array[1..max,1..max] of Real;

Matran_Vephai=Array[1..max] of Real;

vara:Matran_Heso; b:matran_Vephai; n:integer;

{--------------------------------------------------------------------}

Procedure Nhap;

{Thu tuc nhap du lieu tu tep van ban ! }

var f:Text; i,j:Integer;

begin

Assign(f,'Gauss.inp');

Reset(f);

Readln( f,n);

For i:=1 to n do

Begin

For j:=1 to n do

Read(f,a[i,j]);

Readln(f,b[i]) ;

End;

Close(f);

End;

{----------------------------------------------------------------------}

ProcedureDoicot(i,j:integer);

{thu tuc lam nhiem vu doi vi tri hai cot cho nhau !}

Var k:integer;tg:real;

begin

for k:=1 to n do

begin

tg:=a[k,i];

a[k,i]:=a[k,j];

a[k,j]:=tg;

end;

end;

{--------------------------------------------------------------------}

Procedure Nhanhang(i:Integer ; num:Real);

{ Thu tuc lam nhiem vu nhan mot hang voi mot so !}

Var j:integer;

Begin

For j:=i to n do

a[i,j]:=a[i,j]*num;

b[i]:=b[i]*num;

End;

{ --------------------------------------------------------------------}

ProcedureSuly(i,j:integer);

{ thu yuc lam nhiem vu su ly hai hang i va j ! }

Var k:integer;key:real;

Begin

Key:=a[j,i];

For k:=i to n do

a[j,k]:=a[i,k] * key-a[j,k];

b[j]:=b[i]*key-b[j];

End;

{ --------------------------------------------------------------------}

Procedure Khugauss;

{ Thu tuc lam nhiem vu dua HPTTT ban dau ve dang he tam giac tren}

Var i,j,cs:integer;

Begin

For i:=1 to n do

Begin

cs:=i;

While ( a[cs,cs]=0 ) and (cs<=n) do cs:=cs+1;

If cs>n then

Begin

If b[i]<>0 then flag:=1

Else

flag:=2 ;

End

Else

Begin

If cs<>i then doicot(i,cs);

Nhanhang(i,1/a[i,i]);

For j:=i+1 to n do

Suly(i,j);

End;

End;

End;

{--------------------------------------------------------------------}

Procedure Hienthi;

{Thu tuc nay lam nhiem vu hien thi ma tran he so va ve phai cua HPTTT !}

Var i,j:integer;

Begin

Writeln;

Writeln(' Ma tran ve he so va ve phai sau khi khu gause la : ');

Writeln('Ax=B');

For i:=1 to n do

Begin

For j:=1 to n do

Write(a[i,j]:6:1);

Writeln('=',b[i]:6:1);

End;

End;

{--------------------------------------------------------------------}

Procedure Inngiem;

{Thu tuc nay lam nhiem vu in ngiem cua HPTTT !}

Var i:integer;

f:text;

Begin

Assign(f,'Gauss.out');

Rewrite(f);

For i:=1 to n do

Begin

Writeln('ngiem x',i,'= ',b[i]:0:6);

Writeln(f,b[i]:0:6);

End;

Close(f);

End;

{--------------------------------------------------------------------}

Procedure Giahe;

{thu tuc kiem tra ket qua khu Gauss va giai he tam giac tren}

Var i,j:integer;

Begin

If flag=1 then

Write(' He phuong trinh vo nghiem ! ')

Else

If flag=2 then

Write(' He phuong trinhsuy bien ! nen co vo so nghiem ! ')

Else

Begin

For i:=n-1 downto 1 do

Begin

For j:=i+1 to n do

b[i]:=b[i]-a[i,j]*b[j];

End;

Inngiem;

End;

End;

{--------------------------------------------------------------------}

Begin { Main }

Clrscr;

Nhap;

Khugauss;

Hienthi;

Giahe;

Readln;

End.

Các bạn thân mến! Thật đáng ngạc nhiên khi chương trình trên có thể giải được những HPTTT với số ẩn lên đến 1000 chỉ trong nháy mắt (khoảng 30 giây với máy P4 2.6GHz). Hi vọng rằng các bạn sẽ cải tiến và áp dụng hiệu quả nó vào trong công việc học tập. Mình rất mong được sự đóng góp và trao đổi ý kiến của các bạn gần xa!

Bùi Văn Tân :   Mỹ Phúc – Mỹ Lộc – NamĐịnh
Email : Tanbv_it@yahoo.comOR Tanbv_it@prepaid.vnn.vn
ĐT : 0350.818364 OR0912611550
URL của bài viết này::http://www.vnschool.net/modules.php?name=News&file=article&sid=2573
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn