The speed of convergence of the third – oder newton – krylov method

Nội dung text: The speed of convergence of the third – oder newton – krylov method

1. TNU Journal of Science and Technology 226(07): 50 - 55 THE SPEED OF CONVERGENCE OF THE THIRD – ODER NEWTON – KRYLOV METHOD Lai Van Trung*, Quach Thi Mai Lien TNU – University of Information and Communication Technology ARTICLE INFO ABSTRACT Received: 03/12/2020 In recent years, the approximate solution of the system of nonlinear equations has been studied by many scientists, especially the class of Revised: 01/5/2021 systems of nonlinear equations with a large number of equations. The Published: 11/5/2021 third-order Newton - Krylov method solved these systems very well with the speed of cubed of convergence. The convergence of iterated KEYWORDS formula has been proofed, however, its only has been confirmed by experiment. In this article, we will present the speed of convergence Convergence speed of the third-order Newton - Krylov method and give the proof for the Convergence speed of convergence of iterated formula simultaneously. Moreover, the article also presents a consult of experiment to proof for the speed Third-order Newton-Krylov method of convergence of the Newton–Krylov method. Iterative formula Nonlinear equations system TỐC ĐỘ HỘI TỤ CỦA PHƯƠNG PHÁP NEWTON – KRYLOV BẬC BA Lại Văn Trung*, Quách Thị Mai Liên Trường Đại học Công nghệ thông tin & Truyền thông – ĐH Thái Nguyên THÔNG TIN BÀI BÁO TÓM TẮT Ngày nhận bài: 03/12/2020 Những năm gần đây, việc giải gần đúng hệ phương trình phi tuyến được nhiều nhà khoa học quan tâm nghiên cứu, đặc biệt là lớp các hệ Ngày hoàn thiện: 01/5/2021 phương trình phi tuyến có số phương trình lớn. Phương pháp Newton Ngày đăng: 11/5/2021 –Krylov bậc ba giải quyết rất tốt lớp các hệ phương trình này với tốc độ hội tụ bậc ba. Sự hội tụ của công thức lặp đã được chứng minh, TỪ KHÓA tuy nhiên về tốc độ hội tụ của nó chỉ được khẳng định qua thực nghiệm. Trong bài báo này, chúng tôi trình bày về tốc độ hội tụ của Tốc độ hội tụ phương pháp Newton – Krylov bậc ba, đồng thời đưa ra chứng minh Sự hội tụ cho tốc độ hội tụ của công thức lặp. Ngoài ra, bài báo còn trình bày Phương pháp Newton-Krylov bậc ba một kết quả thực nghiệm để minh chứng cho tốc độ hội tụ của phương pháp. Công thức lặp Hệ phương trình phi tuyến DOI: * Corresponding author. Email: lvtrungsp@gmail.com 50 Email: jst@tnu.edu.vn
2. TNU Journal of Science and Technology 226(07): 50 - 55 1. Giới thiệu Xét hệ phương trình phi tuyến Fx 0 , (1) t F f x,f x; ;f x n trong đó 12 n với f:i là các hàm phi tuyến (i12 , , ,n ). Phương pháp Newton được công bố lần đầu tiên vào năm 1685, sau đó được nhiều nhà khoa học phát triển và cải tiến sang giải hệ phương trình phi tuyến với sự hội tụ bậc cao [1]-[3]. Trong [4] đã trình bày phương pháp New – Krylov bậc ba để giải quyết hệ phương trình (1) như sau: Bước 1: Đặt Fxn xxnn1 , (2) 1 1 F x F x F x n2 n n 1 1 và biến đổi công thức (2) thành F x F x F x x x F x (3) n2 n n n1 n n 1 1 Bước 2: Đặt k x F x F x và chuyển phương trình (3) thành n2 n n 1 F x k x F x (4) n n2 n Bước 3: Áp dụng phương pháp Krylov [5] để tìm nghiệm gần đúng kx của phương trình n (4) và viết công thức (3) viết lại như sau F xn k x n s n F x n , (5) với xn1 s n x n . (6) Bước 4: Áp dụng thuật toán Newton-Krylov để tìm nghiệm xn 1 của hệ (5), (6). Sự hội tụ của công thức lặp đã được trình bày trong [4], [5], tuy nhiên tốc độ hội tụ của công thức lặp chỉ được khẳng định qua thực nghiệm. Bài báo này trình bày về tốc độ hội tụ và đưa ra chứng minh cho tốc độ hội tụ của phương pháp. Cấu trúc của bài báo gồm 4 phần: Sau phần giới thiệu là Phần 2, trình bày về tốc độ hội tụ và đưa ra việc chứng minh cho tốc độ hội tụ của công thức lặp; Phần 3 trình bày một số kết quả thực nghiệm; Cuối cùng là phần Kết luận. 2. Tốc độ hội tụ Định nghĩa 2.1 (Tốc độ hội tụ) (Xem [6]) Xét dãy en x n a n , nếu tồn tại một hàm k- k k k 1 n n n k k tuyến tính K L , sao cho en1 Ke n O e n , với en e, ,e và a en là chuẩn Euclid thì xn được gọi là hội tụ đến với tốc độ hội tụ cấp k . Định lý 2.2 (Sự hội tụ của phương pháp Newton-Krylov bậc ba) Cho ánh xạ F: nn khả vi liên tục trên một tập lồi mở D n . Giả sử tồn tại x n và , 0 thỏa mãn 51 Email: jst@tnu.edu.vn
3. TNU Journal of Science and Technology 226(07): 50 - 55 1 1 S x ,r D , Fx tồn tại, Fx và F Lip S x ,r . Khi đó tồn tại số x0 S x , 0 thỏa mãn với mỗi dãy x12 ,x , xác định bởi công thức (2) hội tụ đến x. Định lý 2.3 (Tốc độ hội tụ của phương pháp Newton-Krylov bậc ba) Cho ánh xạ F: nn thỏa mãn các điều kiện của Định lý 2.2 và có đạo hàm đến cấp ba trên D n . Khi đó dãy xn xác định bởi công thức (2) hội tụ đến x với tốc độ hội tụ cấp ba. * Sau đây, chúng tôi đưa ra chứng minh Định lý 2.3. Trong chứng minh này, ta đặt enn=− x x ()*j 1 Fx( ) và Cj==, 1,2,3 j j! Fx ( * ) Để chứng minh Định lý 2.3, ta sẽ chỉ ra có hàm K – tuyến tính sao cho 4 3 en1 Ke n O e n . −1 Trước hết ta viết lại công thức (2) như sau xn+1 =− x n F ( y n) F( x n ), 1 −1 với y=− x F ( x) F( x ). n n2 n n Áp dụng công thức khai triển Taylor của hàm Fx( ) tại x ta có 11234 FxFx( ) =( ) + Fxxx ( )( − ) + Fxxx ( )( − ) + Fxxx ( )( − ) + Oxx − . 2! 3! 11 23 4 Khi đó Fx( nn) = Fxxx ( )( −) + Fxxx ( )( −) + Fxxx ( )( −) + Oxx − 2! 3! 11 23 4 =Fxe ( ) n + Fxe ( ) n + FxeOe ( ) n + n 2! 3! 23 4 =F( x)( en + C23 e n + C e n + O e n ) . Áp dụng công thức khai triển Taylor của hàm Fx ( ) tại ta có 1 2 3 FxFx ( ) = ( ) + Fxxx ( )( −) + Fxxx ( )( −) + Oxx − . 2 1 2 3 Khi đó Fx ( nn) = Fx ( ) + Fxxx ( )( −) + Fxxx ( )( −) + Oxx − 2 *23 =F( x)( I +2 C23 en + 3 C e n + O e n ) . F x e+ C e23 + C e + O e 4 Fx( ) ( )( n23 n n n ) Do đó n = *23 Fx ( n ) F x I+23 C e + C e + O e ( )( 23n n n ) 34 = I −2 Ce + 4 C2 − 3 CeOe 2 + eCeCeOe + 2 + 3 + 2n( 2 3) n n( n 2 n 3 n n ) 2 2 3 4 =en − C2 e n +(2 C 2 − 2 C 3 ) e n + O e n . Fx( n ) 112 2 3 4 Suy ra =en − C2 e n +( C 2 − C 3 ) e n + O e n . 2Fx ( n ) 2 2 52 Email: jst@tnu.edu.vn
4. TNU Journal of Science and Technology 226(07): 50 - 55 1 2 2 3 4 Do đó yn= x + e n + C2 e n −( C 2 − C 3 ) e n + O e n . 2 1 2 3 Ta có Fy ( n) = FxFxyx ( ) + ( )( n −) + Fxyx ( )( n −) + Oyx n − 2 2 3 =FxICyx +23 − + Cyx − + Oe ( ) 23( n) ( n) n 3 3 * 2 2 =F( x) I +2 C2 en + C 2 + C 3 e n + O e n . 4 Fx( ) e+ C e23 + C e + O e 4 Suy ra n = n23 n n n 3 Fy ( n ) 223 I+ C2 en + C 2 + C 3 e n + O e n 4 3 234 2 3 = ICe −2n − Ce 3 n + Oe n e n + Ce 2 n + Ce 3 n + Oe n 4 ( ) 23C3 4 =en − C2 − e n + O e n . 4 −1 Vậy xn+1 =− x n F ( y n) F( x n ) 23C3 4 =xn − e n + C2 − e n + O e n 4 23C3 4 =x + C2 − enn + O e . 4 23C3 4 Do đó en+12= C − e n + O e n , vậy Định lý 2.3 được chứng minh. 4 3. Kết quả thực nghiệm Trong phần này, chúng tôi đưa ra một số ví dụ và bằng cách sử dụng Matlab để tìm nghiệm gần đúng của hệ thông qua công thức lặp (3). Trong các ví dụ này, các bước lặp sẽ dừng lại khi 13 Fxn 10 và chúng tôi cũng đưa ra thời gian chạy của thuật toán. Ví dụ 1 : Giải gần đúng hệ phương trình : x1 x 2 x 3 1 2 x1 x 2 x 3 0 (7) 222 xxx1239 T Ta chọn nghiệm gần đúng ban đầu là x0 1 , 1 , 0 . 1 , sau khi thực hiện 4 bước lặp với thời gian chạy 0. 125 (s) ta được nghiệm gần đúng của hệ (7) là T x2 . 14025812200518 , 2 . 09029464225523 , 0 . 22352512107130 . Mã code : Clear all Syms x1 x2 x3 Format long ; 53 Email: jst@tnu.edu.vn
5. TNU Journal of Science and Technology 226(07): 50 - 55 f = [x1*x2*x3 ; x1+x2-x3*x3; x1*x1+x2*x2+x3*x3]; y = [x1; x2 ;x3]; xn = [1; -1, 0.1]; R = Jacobian(f,y) ; m = 0 ; tic ; While (m<100) a = subs(R, {x1, x2, x3}, {xn(1), xn(2), xn(3)} ; A = a’*a ; B = a’*b ; Tol = 1e^-13 ; z0 = zeros(2 ;1); kn = fom(A, B, z0, tol) ; 1 % (Tính nghiệm gần đúng k(xn) của hệ F xn k xn F xn ) 2 yn = xn + kn; a = subs(R, {x1, x2; x3}, {yn(1), yn(2), yn(3)}); b = -subs(f, {x1, x2, x3}, {xn(1), xn(2), xn(3)}); A = a’*a ; B = a’*b ; Tol = 1e^-13 ; z0 = zeros(2 ;1); kn = fom(A, B, z0, tol) ; % (Tính nghiệm gần đúng sn của hệ F xn k xn sn F xn ) xn = xn + sn; If norm(B)< 1e^-13 breack; else m = m+1; end; end; toc; fprintf(‘Thời gian thực hiện:’); disp(toc); If (m=100) fprintf(‘Không hội tụ sau 100 lần lặp’); else fprintf(‘Số lần lặp là’); m fprintf(‘Nghiệm là’); xn end. Ví dụ 2: Giải gần đúng hệ phương trình : x1 x 3 x 4 x 1 x 4 x 3 0 x x x x x x 0 2 3 4 2 4 3 (8) x1 x 2 x 1 x 3 x 2 x 3 1 x1 x 2 x 4 x 1 x 4 x 2 0 T Bằng cách chọn nghiệm gần đúng ban đầu x0 0 . 5 , 0 . 5 , 0 . 5 , 0 . 3 , sau khi thực hiện ba bước lặp với thời gian chạy 0. 156(s) ta được nghiệm gần đúng của hệ phương trình (8) là 0.,.,.,. 577350269189626 0 577350269189626 0 577350269189626 0 288675134594813 . 4. Kết luận Bài báo đã trình bày về tốc độ hội tụ của phương pháp Newton – Krylov bậc ba để giải hệ phương trình phi tuyến. Đây là kết quả quan trọng để nhóm tác giả tiếp tục xây dựng các công thức lặp cải tiến của phương pháp Newton – Krylov. 54 Email: jst@tnu.edu.vn
6. TNU Journal of Science and Technology 226(07): 50 - 55 TÀI LIỆU THAM KHẢO/ REFERENCES [1] M. T. Darvishi, “A two-step high-order Newton-like method to solve systems of nonlinear equations,” International J. of Pure and Applied Mathematics, vol. 57, no. (4), pp. 543-555, 2009. [2] M. Frontini and E. Sormani, “Third-order methods from quadrature formulae for solving systems of nonlinear equations,” Appl. Math. Comput, vol. 149, pp. 771-782, 2004. [3] M. T. Darvishi and A. Barati, “A fourth-order method from quadrature formulae to solve systems of nonlinearequations,” Appl. Math. Comput, vol. 188, pp. 257-261, 2007. [4] V. T. Lai, P. K. Hoang, M. L. Quach, and V. H. Nguyen, “Solving system of nonlinear equations by the third – oder Newton-Krylov method,” TNU Journal of Science and Technology, vol. 225, no. 06, pp. 405-410, 2020. [5] M. T. Darvishi, and B. –C. Shin, “High –Order Newton – Krylov Methods to Solve systems of Nonlinear Equation,” J.KIAM, vol. 15, no.1, pp. 19 -30, 2011. [6] J. E. Dennis, and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinears. Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. 55 Email: jst@tnu.edu.vn