Tiểu luận Một số phương pháp giải gần đúng và sự hội tụ trong phương pháp dây cung

MỤC LỤC MỞ ĐẦU Trang 2 NỘI DUNG 3 PHƯƠNG PHÁP DÂY CUNG (HAY CÁT TUYẾN) 3 Giải thuật cơ bản 3 Sự hội tụ 3 QUI TẮC ĐIỂM GIỮA 5 Qui tắc điểm giữa 5 Giải thuật cơ bản 8 PHƯƠNG PHÁP KHỬ GAUSS 8 Phương pháp khử Gauss 8 Giải thuật cơ bản 9 KẾT LUẬN 10  MỞ ĐẦU Ngày nay các ngành khoa học nói chung và ngành vật lí nói riêng đã phát triển đến mức độ cao, song song với đó là yêu cầu giải quyết các bài toán lớn, rất phức tạp và đòi hỏi độ chính xác cao. Thay vì đi tìm lời giải tích cho bài toán, ngày nay với sự hỗ trợ đắc lực của máy tính điện tử hiện đại, cộng với các thuật giải số thông minh, ngắn gọn thì việc tìm lời giải số (giải gần đúng) cho các bài toán trở nên đơn giản rất nhiều. Tuy nhiên, khi giải các bài toán bằng phương pháp số điều đáng lưu ý là mức độ sai số (độ hội tụ) của phương pháp, phương pháp nào cho kết quả càng chính xác, sai số nhỏ và tính toán nhanh thì được xem là phương pháp tối ưu hơn. Không có phương pháp nào được xem là tối ưu tuyệt đối, mỗi phương pháp đều có nét đặc trưng riêng của nó, việc dùng phương pháp nào để giải bài toán còn phụ thuộc vào yếu tố khách quan của bài toán và mức độ yêu cầu của công việc. Trong tiểu luận nhỏ này, tôi xin trình bày sự hội tụ của phương pháp dây cung hay cát tuyến (Secant or Chord), phương pháp khử Gauss (Gauss elimination method) trong việc giải gần đúng các phương trình đại số phi tuyến và phương trình đại số tuyến tính và qui tắc điểm giữa trong phương pháp tính gần đúng tích phân.  NỘI DUNG PHƯƠNG PHÁP DÂY CUNG (HAY CÁT TUYẾN) Giải thuật cơ bản Xác lập hàm f(x) và hai lân cận xa, xb cùng với sai số cho phép. Kí hiệu : khoang_sai_so. Nếu fa = f(xa) = 0 thì x = xa là một nghiệm chính xác Þ dừng chương trình. Nếu fb = f(xb) = 0 thì x = xb là một nghiệm chính xác Þ dừng chương trình. Lặp lại các bước sau : Tính , với n = 1, 2, 3… Nếu fn+1 = f(xn+1) = 0 thì x = xn+1 là một nghiêm chính xác Þ xác định nghiệm. Kiểm tra nếu ½xn+1 - xn½≤ ½xn½*khoang_sai_so thì hoặc xn hoặc xn+1 đều có thể được xem là nghiệm gần đúng Þxác định nghiệm. Cho đến khi tìm thấy nghiệm thoả mãn điều kiện đặt ra. Sự hội tụ Khai triển Taylor xung quanh điểm x = x* đối với xn và xn+1 : ; [1] [2] Thay thế các khai triển trên vào công thức lặp của giải thuật Newton-Raphson : Ta có : [3] Biểu thức en+1 chứa cả en và en-1. Từ [3] ta có thể viết lại như sau : [4] Từ [4], suy ra : [5] Thay [5] và [3], ta được : Đồng nhất vế phải của hai phương trình trên, ta tìm được : [6] Nhận xét : Phương pháp trên có bậc không nguyên (con số này gọi là tỉ lệ vàng). Phương pháp dây cung (hay cát tuyến) phân kì nếu f’ triệt tiêu trong lân cận của nghiệm. QUI TẮC ĐIỂM GIỮA Qui tắc điểm giữa Ta khảo sát việc lấy tích phân chuỗi Taylor từ x0 - Dx/2 tới x0 + Dx/2. [7] y f1 f0 O x0 x1 = x0 + Dx x Giá trị của hàm f(x) được xác định tại điểm giữa của mỗi khoảng sai số có thể giảm tương đối so với quy tắc hình thang (hệ số phía trước phần góc là 1/24 đối với quy tắc điểm giữa, trong khi là 1/12 đối với quy tắc hình thang) nhưng bậc gần đúng của phương pháp vẫn giữ nguyên. Qui tắc điểm giữa được minh hoạ bằng hình vẽ 1. Hình vẽ 1. Biểu diễn đồ hoạ qui tắc điểm giữa. Vùng màu xám định nghĩa Qui tắc điểm giữa như là một gần đúng hình chữ nhật với các đường đứt nét chỉ qui tắc hình thang chứa cùng diện tích. Hơn nữa, ta có thể làm giảm sai số khi lấy tích phân từ x0 đến x1 bởi chia nhỏ khoảng này ra thành n bước nhỏ hơn. Kết quả ta có Qui tắc điểm giữa phức hợp : [8] y f1 f0 O x0 x1 = x0 + nDx x Biểu diễn hình học của phương pháp này được chỉ ra trong hình 2. Khi chuyển qua các dạng phức hợp, sự khác nhau giữa qui tắc hình thang và qui tắc điểm giữa không còn nhiều. Hình vẽ 2. Biểu diễn đồ hoạ qui tắc điểm giữa phức. y O x0 x1 = x0 +nDx x Qui tắc điểm giữa có thêm hai ưu điểm nữa so với qui tắc hình thang. Thứ nhất, đối với một số các khoảng con đã cho Qui tắc điểm giữa không đòi hỏi phải sử dụng một tập hợp lớn các giá trị của hàm (số lượng tính toán chỉ bằng một nửa so với qui tắc hình thang). Thứ hai là nó cỏ thể được sử dụng hiệu quả hơn khi tính tích phân gần các điểm kì dị nhưng có khả năng lấy tích phân. Ta có thể thấy hai lợi điểm này trên hình vẽ 3. Hình vẽ 3. Áp dụng qui tắc điểm giữa nơi mà hàm dưới dấu tích phân kì dị có thể làm cho qui tắc hình thang phá sản. Giải thuật cơ bản Xác lập hàm cần tính tích phân f(x), hai biên x0, x1 số điểm cần lấy tích n. Tính Dx = (x1 – x0)/n. For i = 0, 1, 2, … (n-1). Tp = tp + Dxf(x0 + (1 + ½ ) Dx). {Tính tích phân bằng công thức }. PHƯƠNG PHÁP KHỬ GAUSS Phương pháp khử Gauss Khảo sát hệ : a11x1 + a12x2 + a13x3+ … + a1nxn = r1 a21x1 + a22x2 + a23x3+ … + a2nxn = r2 a31x1 + a32x2 + a33x3+ … + a3nxn = r3 ……………………………………… an1x1 + an2x2 + an3x3+ … + annxn = rn Khi tìm nghiệm của hệ phương trình tuyến tính không tầm thường người ta thường làm như sau : Đầu tiên chúng ta chia hàng thứ nhất cho a11 ta được hàng thứ nhất với các giá trị mới ta gọi là hàng thứ nhất #. Sau đó lấy hàng thứ hai trừ đi một hàng mà là kết quả của việc nhân hàng thứ nhất # với yếu tố a21 ; tiếp tục lấy hàng thứ ba trừ đi một hàng mà là kết quả của việc nhân hàng thứ nhất # với yếu tố a31 … và cuối cùng lấy hàng thứ n trừ đi một hàng mà là kết quả của việc nhân với hàng thứ nhất # với yếu tố an1. Kết quả chúng ta có hệ phương trình trên viết dưới dạng ma trận. = Bởi lặp lại quá trình này đối với các hàng từ 3 tới n cùng với việc sử dụng các giá trị mới của các yếu tố nằm trên đường chéo sau khi biến đổi, ta lần lượt thay thế vùng nằm phía dưới đường chéo chính với các số 0. Việc làm tuần tự này gọi là Phép khử Gauss. Cuối cùng ta thu được kết quả : = Giải thuật cơ bản Chúng ta có thể xây dựng giải thuật cho phép khử Gauss ở trên như sau : Xác lập ma trận A, ma trận cột R và bậc của ma trận n. For j = 1, 2, …, n. Tam = aij. rj = rj/tam. For i = j, …, n. Tính aji = aji/tam. For k = j + 1, …, n. For i = j + 1, …, n. Tính aki = aki – akj*aji. Tính rk = rk – akj*rj. Gán akj = 0. {tiếp tục làm bằng phép thay thế ngược để tìm nghiệm}. KẾT LUẬN Trong quá trình tìm nghiệm của phương trình tổng quát nếu ta không thể xác định được nghiệm giải tích dưới dạng một biểu thức giải tích đối với vector thì ta cần tìm các nghiệm nhận các giá trị số . Phương pháp dây cung (hay cát tuyến) được xem là có giải thuật thông minh, ngắn gọn và tốc độ tính toán nhanh so với các phương pháp giải gần đúng phương trình đại số phi tuyến khác. Phương pháp khử Gauss với phép biến đổi linh hoạt, cộng với giải thuật ngắn gọn giúp ta tìm lời giải số cho các hệ phương trình đại số tuyến tính nhanh hơn và chính xác hơn. Trong phương pháp tính gần đúng tích phân, so với qui tắc hình thang, qui tắc điểm giữa có sai số giảm, không đòi hỏi sử dụng tập lớn các giá trị hàm, sử dụng hiệu quả khi tính toán với các điểm kì dị nhưng có khả năng lấy tích phân.