Chương 1: TỔNG QUAN ĐỀ TÀI Chương 2: CƠ SỞ LÝ THUYẾT - Cơ sở lý luận cho việc xây dựng một hệ thống thông tin: Lý thuyết tổ chức cấu trúc dữ liệu và thuật toán. Chương 3: TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN - Tiến hành xây dựng thuật toán. Chương 4: CHƯƠNG TRÌNH VÀ KẾT QUẢ Chương 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 6 Đồ án lập trình tính toán 1. TỔNG QUAN ĐỀ TÀI Đề tài giải hệ phương trình tuyến tính là một chủ đề quan trọng trong toán học và ứng dụng của nó rất rộng lớn trong nhiều lĩnh vực khác nhau như: kỹ thuật, khoa học máy tính, kinh tế,….Một hệ phương trình tuyến tính là một tập hợp các phương trình tuyến tính mà mỗi phương trình trong đó chứa các biến số chỉ có bậc một.
Giải hệ phương trình tuyến tính đòi hỏi sự hiểu biết về nhiều kỹ thuật toán học, trong đó phương pháp ma trận là một trong những phương pháp phổ biến nhất. Một số kỹ thuật khác bao gồm phương pháp Gauss, phương pháp Jacobi, phương pháp Gauss- Seidel, phương pháp Cramer, phương pháp giảm dư,…. Ngoài ra, trong ứng dụng thực tế, giải hệ phương trình tuyến tính còn thường được áp dụng trong các bài toán liên quan đến tối ưu hóa, phân tích dữ liệu và mô hình hóa các hệ thống động.Ngôn ngữ lập trình: Nhóm tác giả sử dụng ngôn ngữ lập trình C.Cơ sở dữ liệu: Để lưu giữ ma trận và kết quả sau khi tính toán, nhóm tác giả sử dụng tệp txt để trữ thông tin danh sách sinh viên và khi cần sử dụng thì nhóm tác giả cần phải đọc file và xử lý bằng các thuật toán phù hợp.Giao diện người dùng: Ở dự án này ta sử dụng màn hình console để hiển thị giao diện mà ta thao tác sử dụng.Thuật toán: Sử dụng các thuật toán biến đổi về ma trận bậc thang, phương pháp giải hệ phương trình: phương pháp Gauss, phương pháp Gauss-Seidel, phương pháp Cramer, phương pháp giảm dư.Xóa cột ở vị trí sau vị trí m/2, sau đó thực hiện tính toán. Ý tưởng ◆ Viết hàm tìm nghiệm của ma trận bằng phương pháp Gauss - Jordan: ■ Biến đổi ma trận thành ma trận bậc thang.
■ Tìm nghiệm của ma trận. ◆ Viết hàm tìm nghiệm của ma trận bằng phương pháp Gauss-Seidel: 7 Đồ án lập trình tính toán ■ Biến đổi phương trình về dạng: B = {bij}n ■ Xét điều kiện hội tụ của ma trận. ■ Cho hệ phương trình xấp xỉ nghiệm ban đầu: ■ Tổng quát nghiệm, xét tiêu chuẩn hội tụ tuyệt đối. ■ Tìm nghiệm của ma trận.
◆ Viết hàm tìm nghiệm của ma trận bằng phương pháp Cramer: ■ Tính định thức của ma trận. ■ Tìm nghiệm của ma trận. ◆ Viết hàm tìm nghiệm của ma trận bằng phương pháp giảm dư: ■ Biến đổi phương trình về dạng của phương pháp. ■ Xét điều kiện hội tụ của phương pháp.
■ Cho vectơ nghiệm ban đầu. ■ Thực hiện quá trình lặp nghiệm cho đến khi đạt tiêu chuẩn hội tụ. ■ Tìm nghiệm của ma trận. 8 Đồ án lập trình tính toán 2.
Phương pháp Gauss-Jordan: Phương pháp khử Gauss-Jordan là một phương pháp để giải hệ phương trình đại số tuyến tính ở dạng ma trận. Đây là phương pháp được phát triển dựa trên phương pháp khử Gauss. Mục tiêu: biến đổi ma trận về dạng ma trận đường chéo để giải ma trận mà không cần phải qua bước tính định thức nào. Điều kiện hội tụ (Gauss-Seidel): Mặc dù phương pháp này có thể áp dụng cho bất kỳ ma trận nào, không chứa phần tử 0 (không) trên các đường chéo, nhưng tính hội tụ chỉ xảy ra nếu ma trận hoặc là ma trận đường chéo trội, hoặc là ma trận đối xứng đồng thời xác định dương.
*Hệ phương trình có ma trận lặp B thỏa mãn 1 trong các trường hợp sau: Thì quá trình hội tụ sẽ đến nghiệm 9 Đồ án lập trình tính toán Ngoài ra, nhóm tác giả tìm hiểu, để có thể giải hệ phương trình bằng phương pháp Gauss-Seidel thì cần phải thỏa điều kiện ma trận đang xét là ma trận chéo trội. Ma trận đường chéo trội là ma trận thỏa mãn các điều kiện sau: Phần tử được gọi là phần tử trội. Định thức: Xét ma trận vuông cấp n: Với mỗi số hạng aij (số hạng nằm ở hàng i và cột j), ma trận nhận được từ A bằng cách bỏ đi hàng thứ I và cột thứ j được gọi là ma trận bù của A đối với số hạng aij, ký hiệu là Aij. Ví dụ: Cho ma trận vuông cấp 3: Ta có thể thành lập các ma trận bù cấp 2, chẳng hạn.
Định nghĩa định thức ma trận vuông: 10 Đồ án lập trình tính toán Định thức của ma trận A Mn, ký hiệu det(A) hay |A|, là số thực được định nghĩa bằng quy nạp theo n như sau: ● Với n = 1, nghĩa là A = a11, thì det(A) = a11. ● Với n ≥ 2, A = (aij)nxn, thì: det(A) = (-1)1+1a11det(A11)+(-1)1+2a22det(A12)+…+(-1)1+na1ndet(A1n) Định lý khai triển định thức theo một hàng hay một cột bất kỳ: Cho ma trận A = (aij)nxn, 1 ≤ io, j0 ≤ n, Khi đó: Công thức (1.1) gọi là công thức khai triển theo hàng i0 và công thức (1.2) là công thức khai triển theo cột j0. Ví dụ: Tính định thức: Tính định thức của ma trận A. Chúng ta khai triển định thức này theo hàng 1: Các tính chất của định thức: a.
Ví dụ: 11 Đồ án lập trình tính toán b. Đổi chỗ hai hàng (hai cột) của định thức cho nhau thì định thức đổi dấu. Khi nhân các phần tử của một hàng (một cột) với cùng một số k thì định thức được nhân lên k lần. Khi tất cả các phần tử của một hàng (một cột) có dạng tổng của 2 số hạng thì định thức có thể phân tích thành tổng của hai định thức sau: e.
Định thức sẽ bằng không nếu thỏa mãn một trong các điều kiện sau: - Có một hàng (một cột) gồm toàn là số không. - Có hai hàng (hai cột) giống nhau. - Có một hàng (một cột) tỉ lệ với nhau. Định thức của ma trận sẽ không thay đổi nếu nhân k vào một hàng (một cột) rồi đem cộng vào một hàng khác (cột khác).
Định thức của ma trận tam giác bằng tích các phần tử chéo. Nếu 2 ma trận vuông cấp n thì det(A. Nếu A là ma trận vuông cấp n thì det(kA) = kn. Rút nhân tử chung của 1 hàng, 1 cột ra ngoài định thức.
Phương pháp Cramer: Hệ phương trình Cramer là hệ phương trình tuyến tính có số phương trình bằng số ẩn số và định thức của ma trận các hệ số khác 0. Ví dụ: cho hệ phương trình 12 Đồ án lập trình tính toán Hệ phương trình có 3 phương trình, 3 ẩn và det(A) = 7 khác 0 nên nó là hệ phương trình Cramer. Ngoài phương pháp chung là phương pháp khử ẩn liên tiếp Gauss đã trình bày ở phần trên, đối với hệ Cramer có thêm 2 phương pháp sau: I.Phương pháp 1: Dùng ma trận nghịch đảo A-1 để giải phương trình ma trận: AX =B X = A-1B II.Phương pháp II: Dùng định thức (công thức Cramer). Xét Ai, i = là ma trận nhận được từ A bằng cách thay cột thứ I bằng cột các hệ số tự do.
Khi đó, hệ Cramer có nghiệm duy nhất: Ví dụ: Cho hệ phương trình tuyến tính: Dùng định thức (công thức Cramer) để tìm nghiệm của hệ phương trình: Nghiệm của hệ phương trình là: 13 Đồ án lập trình tính toán 2. Điều kiện xét hội tụ phương pháp giảm dư: Nhóm tác giả đã tìm hiểu và tương tự như phương pháp Gauss-Seidel, điều kiện của ma trận đầu vào là ma trận chéo trội. Ma trận chéo trội đã được nhóm tác giả tìm hiểu và trình bày ở mục 3 - Điều kiện hội tụ phương pháp Gauss- Seidel. Phương pháp chỉ thực hiện được khi các phần tử trên chéo chính phải khác 0 (không).
Ngoài ra, quá trình hội tụ không phụ thuộc vào xấp xỉ nghiệm ban đầu, mà chỉ phụ thuộc vào bản chất hệ phương trình. Mọi hệ phương trình có giá trị riêng λ ≥ 1 đều hội tụ đến nghiệm một cách nhanh chóng. Nếu các phần tử aii càng lớn hơn cá phần tử khác trên cùng dòng bao nhiêu thì quá trình hội tụ càng nhanh. Thiết kế giao diện: Thiết kế giao diện đơn giản, trực quan, phù hợp với mọi người sử dụng.
TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 3. Phát biểu bài toán Bài toán đề tài giải hệ phương trình tuyến tính bằng phương pháp lặp đơn gồm các chức năng sau: 1. Tạo ma trận A kích thước nxm với M = N+1 bằng danh sách liên kết kép. Xóa bớt một phần tử sau vị trí thứ M/2.
Nhập vào mảng B, sau đó thực hiện giải hệ phương trình tuyến tính bằng các phương pháp lặp đơn. Đầu vào (input) bài toán gồm - Đọc vào N danh sách liên kết từ file DAYSO.IN (trong file DAYSO.IN gồm hàng , mỗi hàng gồm M phần tử số, M=N+1. Mỗi hàng này tương ứng là một danh sách liên kết. -Thực hiện xóa bớt ở mỗi danh sách liên kết một phần tử sau phần tử thứ n/2 (làm tròn nếu lẻ).
- Kết quả sau khi thực hiện ở câu b), chúng ta nhận được danh sách liên kết, mỗi danh sách liên kết có phần tử. Biết rằng các phần tử này là các giá trị được biểu diễn theo trận sau (mỗi danh sách tương ứng mỗi hàng của ma trận). Hãy tìm nghiệm 14 Đồ án lập trình tính toán của hệ phương trình bằng các phương pháp lặp đơn với (B là mảng một chiều bất kỳ nhập vào). Đầu ra (output) của chương trình: - Hiển thị kết quả là ma trận A với kích thước nxm, với m=n+1 và lưu kết quả ra file RESULT1.
- Hiển thị kết quả nghiệm của hệ phương trình tuyến tính và lưu kết quả ra file RESULT2. Cấu trúc dữ liệu Nhóm tác giả sử dụng cấu trúc dữ liệu danh sách liên kết kép, mảng (danh sách liên kết đặc) để giải quyết bài toán trên. Ta định nghĩa các thành phần sau: #define MAX_SIZE 100 #define MAX_REPE 80 #define esp 0.001 typedef struct Node *List; typedef struct Node *Position; typedef struct ArrayList *Matrix; 1. “Node”: struct định nghĩa mỗi nút trong danh sách liên kết đôi bao gồm: data - dữ liệu của 1 nút, con trỏ *next và *prev của 1 nút để xác định các nút trước và sau trong một dãy bao gồm các danh sách liên kết.
“ArrayList”: struct định nghĩa một hàng bao gồm dãy các danh sách liên kết trong một hàng. Bao gồm: max_size: là kích thước của 1 hàng ma trận được tạo khi lấy dữ liệu từ n đề bài cho trước, List *PointToHeaderNode: là con trỏ được định nghĩa bằng 1 struct Node.