Tài liệu Kinh tế: Sử dụng ngôn ngữ lập trình python cài đặt các thuật toán

Hướng dẫn cài đặt thuật toán giải tích số bằng Python cho ngành Khoa học dữ liệu, ứng dụng thực tế trong chương trình đào tạo đại học.

• Người hướng dẫn: TS. Chu Binh Minh
• Trường học: Trường Đại Học Kinh Tế - Kỹ Thuật Công Nghiệp
• Chuyên ngành: Khoa Học Dữ Liệu
• Đề tài: Sử dụng ngôn ngữ lập trình python cài đặt các thuật toán trong học phần giải tích số trong chương trình đào tạo ngành khoa học dữ liệu của trường đại học kinh tế kỹ thuật công nghiệp
• Loại tài liệu: Luận văn nghiên cứu sinh viên
• Năm xuất bản: 2023
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về Ngôn ngữ Lập trình Python

Python là một ngôn ngữ lập trình mã nguồn mở, được thiết kế với cú pháp đơn giản và dễ học. Đây là lựa chọn hoàn hảo cho các sinh viên ngành khoa học dữ liệu và kỹ thuật công nghiệp. Lập trình Python cung cấp khả năng xử lý dữ liệu mạnh mẽ với các thư viện chuyên biệt như NumPy, Matplotlib và Pandas. Sử dụng cài đặt Python trong chương trình đào tạo giúp sinh viên nắm vững các thuật toán giải tích số một cách thực tiễn. Python hỗ trợ multiple paradigm lập trình, từ hướng đối tượng đến hàm số, giúp lập trình viên linh hoạt trong quá trình phát triển ứng dụng.

1.1. Tổng quan về Python và ứng dụng

Python được ưa chuộng trong giáo dục và nghiên cứu khoa học vì tính linh hoạt. Lập trình Python cung cấp các công cụ để cài đặt các thuật toán phức tạp một cách hiệu quả. Ngôn ngữ này hỗ trợ xử lý dữ liệu lớn, tạo đồ thị, và phân tích số học. Các sinh viên ngành công nghệ thông tin có thể áp dụng Python để giải quyết các bài toán thực tiễn trong học phần giải tích số.

1.2. Cài đặt và cấu hình môi trường Python

Cài đặt Python bao gồm tải phiên bản mới nhất từ python.org và cấu hình biến môi trường. Sinh viên cần thiết lập các thư viện cần thiết như NumPy, Matplotlib để cài đặt các thuật toán. Sử dụng trình quản lý gói pip giúp dễ dàng cài đặt các thư viện bổ sung. Để lập trình Python hiệu quả, nên sử dụng các IDE như PyCharm hoặc Jupyter Notebook cho phép kiểm tra từng bước.

II. Các Thuật toán Giải phương trình với Python

Giải tích số là lĩnh vực quan trọng trong khoa học dữ liệu, tập trung vào cài đặt các thuật toán để tìm nghiệm gần đúng. Lập trình Python cho phép thực hiện các phương pháp số như tìm kiếm gia tăng, phương pháp chia đôi, dây cung và tiếp tuyến. Mỗi thuật toán có ưu nhược điểm riêng, phù hợp với các loại phương trình khác nhau. Sử dụng Python để cài đặt những phương pháp này giúp sinh viên hiểu sâu hơn về nguyên lý toán học. Các thuật toán giải phương trình này là nền tảng cho các ứng dụng kỹ thuật phức tạp.

2.1. Phương pháp chia đôi và dây cung

Phương pháp chia đôi là thuật toán đơn giản để tìm nghiệm thực, hoạt động bằng cách liên tục chia đôi khoảng chứa nghiệm. Lập trình Python để cài đặt phương pháp này giúp sinh viên nắm bắt nguyên lý cơ bản. Phương pháp dây cung sử dụng đường thẳng nối hai điểm để xấp xỉ hàm số. Cả hai thuật toán đều yêu cầu mã nguồn đơn giản và dễ kiểm chứng.

2.2. Phương pháp tiếp tuyến và lặp đơn

Phương pháp tiếp tuyến (Newton-Raphson) hội tụ nhanh nhưng yêu cầu tính đạo hàm. Lập trình Python để cài đặt thuật toán này cần chú ý đến độ chính xác của đạo hàm số. Phương pháp lặp đơn là cách tiếp cận tổng quát hơn, có thể áp dụng rộng rãi. Sinh viên cần hiểu điều kiện hội tụ để lựa chọn thuật toán phù hợp.

III. Giải hệ phương trình đại số tuyến tính

Giải hệ phương trình đại số tuyến tính là nội dung trọng tâm trong giải tích số. Lập trình Python hỗ trợ cài đặt các thuật toán như Gauss, phân rã LU, và các phương pháp lặp Jacobi, Gauss-Seidel. Phương pháp Gauss với chiến lược phần tử trội cải thiện độ ổn định tính toán. Thuật toán phân rã LU phân tách ma trận thành tích của hai ma trận tam giác. Các phương pháp lặp phù hợp cho hệ phương trình lớn và thưa. Sử dụng Python để cài đặt những phương pháp này giúp sinh viên áp dụng vào bài toán thực tế.

3.1. Phương pháp Gauss và phân rã LU

Phương pháp Gauss là thuật toán kinh điển để giải hệ phương trình tuyến tính thông qua khử Gauss. Lập trình Python để cài đặt phương pháp này đòi hỏi xử lý ma trận hiệu quả. Phân rã LU tách ma trận hệ số thành L và U, cho phép giải nhanh nhiều hệ cùng ma trận hệ số. Cải tiến phương pháp bằng chiến lược chọn phần tử trội giúp tránh lỗi làm tròn.

3.2. Phương pháp lặp Jacobi và Gauss Seidel

Phương pháp lặp Jacobi xấp xỉ nghiệm bằng cách lặp, phù hợp cho hệ phương trình lớn. Lập trình Python để cài đặt thuật toán này tương đối đơn giản. Phương pháp Gauss-Seidel cải tiến Jacobi bằng cách sử dụng giá trị mới ngay khi tính toán, hội tụ nhanh hơn. Phương pháp Gradient liên hợp là thuật toán tiên tiến cho các ma trận đối xứng dương xác định.

IV. Nội suy và Tính gần đúng Tích phân

Nội suy là kỹ thuật ước lượng giá trị hàm tại các điểm chưa biết dựa trên dữ liệu đã có. Lập trình Python cho phép cài đặt các thuật toán nội suy như Lagrange, Newton, và Neville một cách hiệu quả. Phương pháp bình phương nhỏ nhất xấp xỉ dữ liệu bằng đa thức hoặc hàm phi tuyến. Tính gần đúng tích phân sử dụng các thuật toán như hình thang, Simpson, Romberg, và cầu phương Gaussian. Các phương pháp này tìm đạo hàm gần đúng và tích phân xác định. Lập trình Python để cài đặt những công cụ này thiết yếu cho sinh viên khoa học dữ liệu.

4.1. Phương pháp nội suy Lagrange và Newton

Phương pháp Lagrange xây dựng đa thức nội suy dựa trên các điểm dữ liệu. Lập trình Python để cài đặt thuật toán này cần tính toán các hệ số Lagrange. Phương pháp Newton sử dụng sai phân chia để xây dựng đa thức hiệu quả hơn. Thuật toán Neville tính giá trị nội suy mà không cần xây dựng toàn bộ đa thức, tiết kiệm tính toán.

4.2. Tích phân số và đạo hàm gần đúng

Phương pháp hình thang xấp xỉ tích phân bằng cách chia khoảng thành các hình thang nhỏ. Lập trình Python để cài đặt các phương pháp tích phân số giúp xử lý hàm phức tạp. Phương pháp Simpson sử dụng parabol, cho độ chính xác cao hơn. Phương pháp Romberg kết hợp nhiều lần tính toán để cải thiện kết quả. Cầu phương Gaussian chọn trọng số và nút tối ưu cho độ chính xác tối đa.

Trích đoạn nội dung tài liệu

Chương I giới thiệu tống quan về sai số, cách viết xáp xi cũng như sai số phát sinh trong quá trình tính toán. Năm chương còn lại đề cập đến 5 lĩnh vực cụ thê trong toán 25 học tính toán. Mục đích của chương này sẽ sử dụng ngôn ngữ lap trinh Python cai dat các thuật toán trong các chương 2, 3, 4, 5, 6 của học phản Giải tích số. Việc này sẽ giúp các em sinh viên có thê rèn luyện kỹ năng lập trình cũng như hiểu các thuật toán này một cách sâu sắc hơn.

Sir dung Python cai đặt các thuật toán trong chương 2 của học phan Giải tích số: Giải gần đúng nghiệm thực của phương trình Chương 2 học phan Giái tích só đề cập đến việc xấp xi nghiệm thực cho phương trình, đây là cơ sở để giải quyết nhiều bài toán trong kinh tế và kỹ thuật. Hầu hết các phương trình đều không có công thức giải tích đề tính nghiệm đúng. Hơn nữa, ngay cả khi một vài phương trình có công thức tính nghiệm đúng thì quá trình tính toán Các công thức này sẽ phát sinh sai số do quy tròn hoặc do tính toán nên kết quả cuôi cùng sẽ là giá trị gần đúng của nghiệm. Do vậy, việc xây dựng thuật toán đề tính nghiệm gần đúng cho mỗi phương trình là rất cần thiết.

Các phương pháp xấp xi nghiệm cho phương trình được chia làm 2 lớp là các phương pháp khoảng và các phương pháp mở. Nếu đã biết một khoảng chứa nghiệm Cua phương trình thì các phương pháp khoảng sẽ tìm được khoảng con đủ nhỏ chứa nghiệm. Các phương pháp khoảng được giới thiệu trong chương trình Giải tích số là phương pháp Tìm kiếm gia tăng và phương pháp Chia đôi. Các phương pháp khoảng có ưu điểm đơn giản nhưng độ chính các và tính ôn định không cao.

Do vậy, các phương pháp khoáng thường được sử dụng để giải sơ bộ cho bài toán tìm nghiệm xấp xi cho phương trình đề tìm khoảng đủ nhỏ mà hàm só thoả mãn một vài tính chất cần thiết. Khi đó, các phương mở sẽ tiếp tục thực hiện phản việc còn lại. Các phương pháp mở là nhóm các phương pháp tận dụng dáng điệu của đường cong để đưa ra công thức lặp xấp xi nghiệm cho hợp lý. Do vậy, nêu so với các phương pháp khoảng thì các phương pháp mở có độ chính xác cao hơn.

Ba phương pháp mở được giới thiệu trong chương trình là phương pháp Dây cung, phương pháp Tiếp tuyến và phương pháp Lặp đơn. Sử dụng Python để cài đặt cho phương pháp tìm kiếm gia tăng Xét phương trình f(x) =0,x € [a, bị. Giả sử ta biết phương trình có nghiệm a € [a, b] nhung 46 dài đoạn [ø, b] chưa đủ nhỏ. Phương pháp Tìm kiếm gia tăng sẽ giúp tìm một đoạn con có chiều đài đủ nhỏ A, cua [a, b] chứa nghiệm của phương trình.

Các bước được thực hiện như sau: Phương pháp Tìm kiếm gia tăng. Output: [x,, x] chia nghiém. Thuật toán dừng (vì khoáng tìm kiếm vượt ra ngoài [a, b]). Nêu ƒ(x;)ƒf(œ;) <0 thì dừng thuật toán.

Nếu ƒ(x¡)ƒŒ¿) > 0 thi x1 := x, va quay lai Buée 1. Ham trong chuong trinh sau thyc hién tim khoang [x,,x,] voi cac tham s6 dau vào là hàm f(x), can dưới, cận trên a, b và số gia đx. ## module rootsearch eS ™ x1,x2 = rootsearch(f,a,b,dx). WY Searches the interval (a,b) in increments dx for the bounds (x1,x2) of the smallest root of f(x).

FF Returns xl = x2 = None ifno roots were detected. A DD from numpy import sign def rootsearch(f,a,b,dx): œ xl =a; fl = f(a) ® x2 =a+dx; 2 = f2) co — ll while sign(fl) == sign(f2): ifx1 >=b: return None,None xl =x2; fl = x2 =xl + dx; f2 = x2) else: 16 return x1,x2 Ví dụ: Sử dụng tìm kiếm gia tăng với A, = 0.2, tìm khoán chứa 0-điểm dương nhỏ nhat cua f(x) = x3 — 10x? +5, Dinh nghia ham f va truyén tham số vào rootsearch(fa.b,dx) 1 đeff{x): return x**3 - 10.2) 3 print(‘Khoang chua nghiem =[',x1,',’,x2,"]') Két qua la: Khoang chua nghiem =[ 0.8 | 27 Phương pháp tìm kiếm gia tăng có ưu điểm đơn giản nhưng độ chính xác thấp vì có sai số không quá A„. Nếu A, lớn thì sai sô sẽ lớn và có thể bỏ sót nghiệm. Ngược lại, nếu A„ nhỏ thì quá trình tìm kiếm sẽ tôn nhiều thời gian.

Phương pháp Chia đôi được trinh bảy sau đây sẽ có độ chính xác và hiệu quả cao hơn. Sử dụng Python để cài đặt cho phương pháp chia đôi Xét phương trình f(x) =0,x € [a, b] Giả sử phuong trinh co nghiém a € [a,b] nhung d6 dai doan [a, b] chua du nho. Phương pháp chia đôi sẽ giúp tìm khoảng con của [a, b] có chứa nghiệm bằng cách lặp lại việc chia đôi liên tiếp khoảng chứa nghiệm đã biết. Sau mỗi lần lặp, độ dài của khoảng chứa nghiệm sẽ giảm đi một nửa.

Quá trình lặp sẽ dừng lại đến khi tìm được đoạn con đủ nhỏ. Thường thì quá trình lặp sẽ dừng sau khi tìm được khoảng con có độ dài nhỏ hơn sai số cho trước (ký hiệu e, hoặc tol). Qua trình tính toán cụ thê được minh hoạ bằng thuật toán sau. Phương pháp chia đôi.

Output: Nghiém xap xi (x, + x,)/2. Ngược lại: xị := 4a. Néu Err < tol: Dung thuat toan. Két ludn nghiém x4p xi (x, + x,)/2.

Ngugc lai: Quay lai Bue 1. Ham _bisection(£,x1,x2,switch=0,tol=1.0e-9) cho nghiém xap xi bang phuong phap chia ddi voi f, x,,x, 1a ham và các tham số cho trước. Sai số tol mặc định là 10 ?. Switch = 1 nếu không tìm được nghiệm.

Chương trinh Python: 1 ## module bisection 2 " root =bisection(f,x1,x2,switch=0,tol=1. Finds a root of f(x) = 0 by bisection. 4 The root must be bracketed in (x1,x2). 5 Setting switch = 1 returns root = None if 6 f(x) increases upon bisection.

7 28 8 import math 9 import error 10 from numpy import sign 11 def bisection(f,x1,x2,switch=1 ,tol=1.0e-9): 12 fl=Ñxl) 13 if fl == 0.0: return x2 16 if sign(fl) == sign(£2): 17 error.err(‘Root is not bracketed’) 18 n= int(math.5*(xI + x2); £3 = Ñx3) 21 if (switch =— L) and (abs(f3) > abs(f1)) \ 22 and (abs(f3) > abs(f2)): 23 return None 24 if £3 == 0.0: return x3 25 if sign(2)!= sign(f3): xl = x3; fl = 6 26 else: x2 = x3; 2 = f3 27 return (xl + x2)/2.0 Do mãi lần lặp độ dài đoạn chứa nghiệm sẽ giảm một nửa nên sau 7 lần lặp thì độ dài đoạn chứa nghiệm sẽ giảm 2" lần so với độ dài đoạn [a, b] ban đầu. Do đó, ta có sai số tuyệt đối của phương pháp được tính bởi b-a |x. — xy] < Qn Phương pháp Dây cung có độ chính xác thấp nhưng rất ôn định và thực hiện tính toán mà không yêu cầu điều kiện về hàm số. Do vậy, phương pháp chia đôi thường được áp dụng để xấp xỉ nghiệm khi ta chưa có nhiều thông tin về dáng điệu của hàm số hoặc thực hiện bước giải sơ bộ.

Tức là tìm khoảng con đủ nhỏ để hàm số thoả mãn một sô điều kiện mà các phương pháp chính xác cao yêu câu. Sử dụng Python để cài đặt cho phương pháp dây cung Để có được công thức xấp xi nghiệm có độ chính xác cao, các phương pháp phải tận dung dang diéu cua ham f(x) dé dua ra công thức lặp cho phù hợp. Các phương pháp này được gọi là các phương pháp mở. Chương trình Giải tích số giới thiệu ba phương pháp mở là phương pháp dây cung, phương pháp tiếp tuyến và phương pháp 29 lặp đơn.

Trong ba phương pháp này, phương pháp dây cung và phương pháp tiếp tuyến sẽ hội tụ nêu phương trình thoả mãn hai giả thiết sau: (g1): Tồn tại nghiệm ø e [a, b]; (gt2): ƒ,ƒ' không đổi dấu trên [a, b]. Các giá thiết (gtl) và (gt2) là các điều kiện tương đối chặt cho mỗi bài toán trong thực tế. Để giải quyết vấn đề này, các phương pháp khoảng được sử dụng kết hợp với các phương pháp mở. Quá trình giải thường sẽ được chia thành hai giai đoạn liên tiếp.

Giai đoạn đầu thực hiện giải sơ bộ bằng các phương pháp khoảng đề tìm được khoảng chứa nghiệm đủ nhỏ mà các (gt1) và (gt2) thỏa mãn. Giai đoạn tiếp theo sẽ sử dụng các phương pháp mở để xấp xi nghiệm cho phương trình với độ chính xác cao. Mục này sẽ trình bày phương pháp dây cung xấp xỉ nghiệm cho phương trình cũng như chương trình Python cải đặt cho thuật toán. Giả sử phương trình thoả mãn (gt1) và (g2) với f (x) > 0, f(x) > 0, Vx € [a,b] (minh hoạ như Hình 2.

Ta thấy nghiệm ø của phương trình là giao của cung AB với Ox. Ý tưởng của phương pháp dây cung là nghiệm đúng #, là giao của dây cung Ab, sẽ được xấp xỉ bởi xị¡ là giao của dây cung AB. Do dây cung AB là đường thẳng là đa thức bậc nhất nên việc tìm x¡ sẽ dễ hơn rất nhiều so với việc tìm ø. Cụ thể, với xạ = a ta có ƒ@) xX, = Xo — Xo).

f(b)— f(%) Qua trình tương tự sẽ được thực hiện lặp lại để thu được các nghiệm xấp xi tốt hơn. Một số bước lặp được minh họa trong Hình 2. 1 Hình minh họa phương pháp dây cung Quá trình lặp trong trường hợp đang xét thì điểm B không thay đối, tuy nhiên một sô trường hợp khác thì điểm A sẽ không thay đối. Do vậy, trước khi thực hiện lặp, tại bước khởi tạo ta cần xác định điểm có định xz„„ và giá trị bắt đầu xạ.

Để dãy nghiệm xấp xỉ xạ,x¡,. ngày càng gần z (dãy {x„} hội tụ về ø) thì dãy điểm này phải nằm 30 “phía trong” cung AB, do vậy nếu hàm số lõm (ƒ (+) > 0) thì điểm cô định phải nằm bên trên Øx và ngược lại. Từ đó suy ra tung độ của điểm có định và ƒ“{x) phải cùng dấu, tức là ƒ(xz¿„)ƒ ”(xz„) > 0. Ta sẽ kiểm tra điều kiện này để chọn x;z„„ một trong hai $6 a, b.

So con lại sẽ gán cho giá trị ban đầu xạ. Thuật toán tim dây cung cụ thê như sau. Phương pháp dây cung. Output: Nghiém xap xi x).

Ngược lại xr¡„ = b,X9 = a. Tính XI = Xo — ƒ(Xr¡„)T— ƒŒq) *rix Xo) Bước 3. Tính Err = |x, — xl. Nếu Err < tol: Dừng thuật toán.

Nghiệm xấp xỉ #¡. Ngược lại: xạ := #¡, quay lại Bước 2. Sai số của phương pháp dây cung sau Ø lần lặp được xác định bởi công thức x, -al< x, —Xol,m =min |f,M =max |f'|. | Ị |S | Ị ol in IF.

ax If | Tuc la, sai $6 cua buéc lap thir n sé duoc tinh bang tich cua mot hang so (M — m)/m với độ chênh với vòng lặp trước.