228(10): 35 - 41
TNU Journal of Science and Technology
NEWTON - KRYLOV - NEDZHIBOV METHOD SOLUTIONS TO A SYSTEM OF NONLINEAR EQUATIONS WITH QUADRATIC CONVERGENCE RATE
Lai Van Trung, Quach Thi Mai Lien* TNU - University of Information and Communication Technology
ARTICLE INFO
ABSTRACT
Received:
Revised:
05/5/2023
Published:
05/5/2023
KEYWORDS
Iterative formula Quaternary convergence Nonlinear equations system Third-order Newton-Krylov method Newton-Krylov-Nedzhibov method
22/3/2023 Many problems in practical and engineering applications lead to finding solutions to a system of nonlinear equations with large numbers of variables and equations. The problem of finding the exact solution to a system of nonlinear equations is not always feasible, especially for large-scale systems. Therefore, finding approximate solutions to this class of equations is great importance. Since the appearance of the Newton's method, there have been many methods proposed by scientists to address this issue with the support of computer software. Research and development of improved methods for this algorithm are always of interest and focus for scientists. In this paper, we investigate the problem of finding approximate solutions to a system of nonlinear equations using the Newton-Krylov-Nedzhibov method. The convergence of the iterative method can only be confirmed through practical experiments. Using the properties of Krylov space and the properties of the mapping that satisfies the Lipschitz condition, we prove the convergence of the method. Moreover, we present the solution to a nonlinear equation system using Mathlab software.
PHƢƠNG PHÁP NEWTON – KRYLOV- NEDZHIBOV GIẢI HỆ PHƢƠNG TRÌNH PHI TUYẾN VỚI TỐC ĐỘ HỘI TỤ BẬC BỐN Lại Văn Trung, Quách Thị Mai Liên* Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên
THÔNG TIN BÀI BÁO
TÓM TẮT
Ngày hoàn thiện: 05/5/2023
Ngày đăng: 05/5/2023
TỪ KHÓA
Công thức lặp Hội tụ bậc bốn Hệ phương trình phi tuyến Phương pháp Newton-Krylov bậc ba Phương pháp Newton-Krylov- Nedzhibov
Ngày nhận bài: 22/3/2023 Nhiều bài toán trong thực tế và trong kỹ thuật thường dẫn đến việc tìm nghiệm của một hệ phương trình phi tuyến với số ẩn và số phương trình lớn. Vấn đề tìm nghiệm chính xác của hệ phương trình phi tuyến không phải lúc nào cũng thực hiện được, đặc biệt là lớp các hệ phương trình có số ẩn và số phương trình lớn. Vì vậy, việc tìm nghiệm gần đúng lớp các hệ phương trình này là rất cần thiết. Kể từ khi phương pháp Newton xuất hiện đã có rất nhiều phương pháp được các nhà khoa học đưa ra để giải quyết vấn đề này dưới sự hỗ trợ của các phần mềm máy tính. Việc nghiên cứu và đưa ra các phương pháp cải tiến cho thuật toán này luôn được các nhà khoa học quan tâm, nghiên cứu. Trong bài báo này chúng tôi nghiên cứu việc tìm nghiệm gần đúng của hệ phương trình phi tuyến bằng phương pháp Newton-Krylov-Nedzhibov. Sự hội tụ của phương pháp lặp chỉ được khẳng định bằng thực nghiệm. Bằng cách sử dụng các tính chất của không gian Krylov và các tính chất của ánh xạ thoả mãn điều kiện Lipschitz chúng tôi chứng minh cho sự hội tụ của phương pháp. Ngoài ra, chúng tôi còn trình bày việc giải số một hệ phương trình phi tuyến dựa trên phần mềm Mathlab.
DOI: https://doi.org/10.34238/tnu-jst.7592 * Corresponding author. Email: qtmlien@ictu.edu.vn
http://jst.tnu.edu.vn 35 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
1. Giới thiệu
Xét hệ phương trình phi tuyến
, (1)
trong đó với là các hàm phi tuyến ( ).
Năm 1685, Newton công bố công thức giải phương trình phi tuyến và đến năm
1690 Raphson đã công bố công thức lặp để tìm nghiệm xấp xỉ của phương trình được gọi là phương pháp Newton – Raphson. Từ đó, đã có nhiều nhà khoa học quan tâm, nghiên cứu và đưa ra nhiều công thức lặp với tốc độ hội tụ bậc hai, trong đó phải kể đến phương pháp Newton [1], phương pháp Chebyshev, Halley [2] và một số phương pháp lặp hội tụ cấp 3 được trình bày trong [3] - [9]. Tuy nhiên các phương pháp này đều mắc phải độ phức tạp tính toán cao khi số phương trình và số ẩn của hệ lớn. Để khắc phục hạn chế này, bằng cách tiếp cận khác, Krylov đưa ra một phương pháp để giải gần đúng hệ phương trình phi tuyến (1) như sau: Xét hệ phương trình:
. (2)
Phương pháp Newton-Krylov là phương pháp tìm nghiệm gần đúng của hệ phương trình (2) với điều kiện
,
với gọi là điều kiện ràng buộc.
Thuật toán Newton-Krylov: 1. Lấy và .
2. Cho và làm theo các bước sau:
• Chọn
• Áp dụng một phương pháp lặp để tìm nghiệm của hệ
Quá trình trên sẽ dừng lại khi điều kiện sau được thỏa mãn
.
• Hiệu chỉnh .
Năm 2008, G.H. Nedzhibov đã đề xuất một phương pháp giải gần đúng hệ phương trình phi tuyến (1) với tốc độ hội tụ bậc bốn [10], được gọi là phương pháp Newton-Krylov-Nedzhibov. Phương pháp Newton-Krylov-Nedzhibov với công thức lặp như sau:
(3)
và trong đó
Từ công thức (3) ta xây dựng được công thức lặp sau: (4)
và
(5)
http://jst.tnu.edu.vn 36 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
với và .
từ hệ phương trình (4), (5).
Ta sử dụng thuật toán Newton-Krylov tìm nghiệm gần đúng Sự hội tụ và tốc độ hội tụ của phương pháp chỉ được suy ra từ kết quả thực nghiệm. Trong bài báo này chúng tôi trình bày chứng minh sự hội tụ của phương pháp Newton-Krylov- Nedzhibov với tốc độ hội tụ bậc bốn. Cấu trúc của bài báo gồm 4 phần, phần thứ nhất của bài báo là phần Giới thiệu, Phần 2 trình bày chứng minh sự hội tụ của phương pháp, Phần 3 trình bày kết quả thực nghiệm và Phần 4 là phần Kết luận.
2. Sự hội tụ của phƣơng pháp Newton-Krylov-Nedzhibov
Trước hết chúng tôi xét hai Định lý quan trọng sau, được trình bày trong [11].
Định lý 2.1 Cho , trong đó là ma trận đơn vị. Nếu thì tồn tại và
Hơn nữa, nếu khả nghịch và thì khả nghịch và
Định lý 2.2. Cho ánh xạ khả vi liên tục trên một tập lồi, mở và
, khi đó với mọi ta có
Tiếp theo chúng tôi trình bày sự hội tụ của phương pháp Newton-Krylov- Nedzhibov và chứng minh sự hội tụ của công thức lặp.
Định lý 2. 3 (Sự hội tụ của công thức Newton-Krylov-Nedzhibov) Cho khả vi
liên tục trên một tập lồi mở . Giả sử tồn tại và thoả mãn
tồn tại, và Khi đó tồn tại
số thoả mãn với mỗi dãy xác định bởi công thức (3) hội tụ
đến .
Đặt với
Đặt khi đó
Từ với , do là Lipschitz tại nên ta có
Theo Định lý 2.1 ta có khả nghịch và
http://jst.tnu.edu.vn 37 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
Từ ta suy ra
Áp dụng Định lý 2.2, ta có
Suy ra .
Do và là Lipschitz tại nên ta có
Áp dụng Định lý 2.1 ta có khả nghịch và
Ta có
.
và là Lipschitz tại nên ta có Từ
Áp dụng Định lý 2.1 ta có khả nghịch và
Ta có
http://jst.tnu.edu.vn 38 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
Ta lại có, nên
Từ là Lipschitz tại nên ta có
Áp dụng Định lý 2.1 ta có khả nghịch và
, khi đó Đặt
Từ và là Lipschitz tại nên bằng cách đánh giá tương tự ta có
Áp dụng Định lý 2.1 ta có khả nghịch và
Từ định nghĩa của ta có Do đó
Áp dụng Định lý 2.2 ta có
http://jst.tnu.edu.vn 39 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
Suy ra
Chứng minh tương tự ta có , từ đó suy ra
Bằng quy nạp ta chứng minh được và , do đó
hội tụ đến
3. Kết quả thực nghiệm
Trong phần này, chúng tôi sử dụng Matlab để tìm nghiệm gần đúng của hệ thông qua công
thức lặp (3) với sai số không vượt quá . Ví dụ: Giải gần đúng hệ phương trình bằng phương pháp Newton-Krylov- Nedzhibov.
(5)
Chọn giá trị ban đầu , sau khi thực hiện 3 bước lặp với thời gian chạy
(s) chúng tôi thu được nghiệm gần đúng của hệ phương trình (5) là
.
Mã code : % Khởi tạo giá trị ban đầu x = [1; 0; 2; 0]; maxIter = 1000; tol = 1e-6; iter = 0; tic % bắt đầu đo thời gian chạy của toàn bộ chương trình while iter < maxIter F = [x(1)^3*x(3) + x(4)*x(2)^2*x(2)^2 - 14; x(1)^2*x(3) + x(2)^2*x(4) - 5; x(1)*x(3) + x(2)*x(4) - 2; x(1) + x(4) - 1]; normF = norm(F); if normF < tol fprintf('Converged after %d iterations\n', iter); break; end J = jacobian(x); delta = krylovNedzhibov(-F,J); x = x + delta; iter = iter + 1;
http://jst.tnu.edu.vn 40 Email: jst@tnu.edu.vn
228(10): 35 - 41
TNU Journal of Science and Technology
end toc % kết thúc đo thời gian chạy của toàn bộ chương trình fprintf('Solution: x1=%f, x2=%f, x3=%f, x4=%f\n', x(1), x(2), x(3), x(4)).
4. Kết luận
Bài báo đã trình bày phương pháp Newton-Krylov- Nedzhibov với tốc độ hội tụ bậc bốn. Đây là một cải tiến của phương pháp Newton-Krylov và là một kết quả rất cần thiết để chúng tôi có thể giải quyết các bài toán quan trọng trong các nghiên cứu về lý thuyết mạch của chúng tôi.
TÀI LIỆU THAM KHẢO/ REFERENCES
