Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Hỗ trợ trực tuyến
Hỗ trợ kỹ thuật
(Bùi Văn Khoa)
Trang thông tin hỗ trợ khách hàng
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới
 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (700 bài viết)
  • Sản phẩm mới (215 bài viết)
  • Dành cho Giáo viên (549 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (156 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (127 bài viết)
  • Hỗ trợ khách hàng (486 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (183 bài viết)
  • Thông tin khuyến mại (79 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (70 bài viết)
  • Cùng học (92 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (78 bài viết)
  • School@net 15 năm (154 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (124 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (363 bài viết)
  • Các vấn đề giáo dục (1210 bài viết)
  • Bài học trực tuyến (1037 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (275 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (180 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 7
    Thành viên: 0
    Tổng cộng: 7
     
    Số người truy cập
    Hiện đã có 54206163 lượt người đến thăm trang Web của chúng tôi.

    Thuật toán khử gauss trong giải hệ phương trình tuyến tính

    Ngày gửi bài: 23/10/2008
    Số lượt đọc: 7172

    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

    School@net (Theo THNT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (04) 62511017 - Fax: (04) 62511081
    Email: school.net@hn.vnn.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.