Tốc độ hội tụ của phương pháp Newton – Krylov bậc ba

 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: https://doi.org/10.34238/tnu-jst.3815 
* Corresponding author. Email: lvtrungsp@gmail.com 
 50 Email: jst@tnu.edu.vn 
 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 
 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 
 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 
 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 
 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