Phương pháp Newton suy rộng cho phương trình không liên tục một biến

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

21
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề xuất phương pháp Newton suy rộng để tìm nghiệm cho phương trình không liên tục. Ở đây, chúng tôi chỉ trình bày phương pháp cho phương trình không liên tục trong không gian một chiều.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp Newton suy rộng cho phương trình không liên tục một biến

UED Journal of Social Sciences, Humanities & Education – ISSN 1859 - 4603 TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC PHƯƠNG PHÁP NEWTON SUY RỘNG Nhận bài: CHO PHƯƠNG TRÌNH KHÔNG LIÊN TỤC MỘT BIẾN 23 – 07 – 2017 Phạm Quý Mườia*, Đỗ Viết Lâna, Dương Xuân Hiệpa, Phan Đức Tuấna và Phan Quang Như Anha Chấp nhận đăng: 25 – 09 – 2017 http://jshe.ued.udn.vn/ Tóm tắt: Trong bài báo này chúng tôi đề xuất phương pháp Newton suy rộng để tìm nghiệm cho phương trình không liên tục. Ở đây, chúng tôi chỉ trình bày phương pháp cho phương trình không liên tục trong không gian một chiều ¡ . Trước hết, chúng tôi đề xuất các hàm nửa trơn xấp xỉ cho các hàm không trơn tương ứng. Sau đó chúng tôi chứng minh một số tính chất cơ bản, cần thiết cho việc chứng minh sự hội tụ phương pháp Newton suy rộng. Tiếp theo, chúng tôi trình bày và chứng minh sự hội tụ của phương pháp Newton suy rộng cho phương trình không liên tục được nghiên trong bài báo này. Cuối cùng, chúng tôi trình bày các kết quả nghiệm số cho một vài ví dụ cụ thể. Các ví dụ số chỉ ra rằng phương pháp Newton suy rộng có tốc độ hội tụ nhanh như phương pháp Newton cổ điển. Từ khóa: phương pháp Newton suy rộng; phương trình không liên tục; đạo hàm Newton; xấp xỉ nửa trơn; nghiệm của phương trình không liên tục. 1. Giới thiệu ¡ vì hàm H  không liên tục tại x =   (xem Hình Trong bài báo này, chúng tôi nghiên cứu phương 1). Vì thế các phương pháp số thông thường như trình không trơn trong [1, 2]: phương pháp dây cung, phương pháp Newton, tựa Newton,... không thể áp dụng được [3, 4, 5, 6].  1  x = H 2  x − f ( x)  (1) s   s hay  1  F ( x) := x − H 2  x − f ( x)  = 0, (2) s  s  trong đó H  : ¡ → ¡ định nghĩa bởi: 0, x  , H  ( x) =   x, x  . Hình 1. (a) Đồ thị hàm H  ( x ) , (b) F ( x) với  = 0.01 Ở đây, s  0 là một số thực cho trước và Trong bài báo này, chúng tôi đề xuất một phương f  C (¡ ) , tức là f là một hàm khả vi liên tục trên ¡ . 1 pháp mới để tìm nghiệm cho phương trình (2) như sau: - Trước hết, các hàm H  và F (không liên tục, Chú ý rằng các hàm H  và F không liên tục trên không khả vi) được xấp xỉ bởi các hàm số P và F tương ứng. aTrường Đại học Sư phạm - Đại học Đà Nẵng - Sau đó, chúng ta thực hiện vòng lặp: Chọn dãy * Liên hệ tác giả Phạm Quý Mười { n }  0, x0  ¡ và tính Email: pqmuoi@ued.udn.vn Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 7, số 3 (2017), 19-25 | 19
Phạm Quý Mười, Đỗ Viết Lân, Dương Xuân Hiệp, Phan Đức Tuấn và Phan Quang Như Anh xn +1 = xn − 1 1 2 .F ( xn ) (3) Giả sử rằng x* − f ( x* )  . Khi đó Fn ( xn ) n s s Chú ý rằng, nếu F là hàm liên tục Lipschitz thì (3)  1  1 2 chính là vòng lặp Newton trơn hóa [3, 4, 5, 6]. Ở đây, H 2  x* − f ( x* )  = x* − f ( x* )  . s   s s s hàm số F được cho ở (2) là hàm không liên tục nên kết quả của chúng tôi là mới và là một sự mở rộng của các 1 2 kết quả trong [3, 4, 5, 6]. Mâu thuẫn này cho ta x* − f ( x* )  . s s Đóng góp chính của bài báo là đưa ra điều kiện cho Lúc này dãy { n } và chứng minh sự hội tụ địa phương của vòng  1  lặp (3) cho phương trình (2) và xem xét một vài ví dụ số x* = H 2  x* − f ( x* )  = 0. s   cụ thể minh họa cho phương pháp. s Bố cục của bài báo như sau: Trong phần hai, chúng Tiếp theo chúng tôi đưa ra một phương pháp xấp xỉ tôi đề xuất các hàm trơn, tương ứng là xấp xỉ của các các hàm số không liên tục H  và F bởi các hàm số hàm không trơn H  và F . Sau đó, chứng minh một vài P và F là các hàm số liên tục và khả vi Newton tính chất của các hàm xấp xỉ này. Những tính chất này (xem Hình 2). là cần thiết cho việc chứng minh sự hội tụ của phương pháp Newton suy rộng được trình bày ở phần tiếp theo. Thật vậy, ta định nghĩa các hàm số P và F như sau Phần ba, chúng tôi trình bày phương pháp Newton suy max{0; − x 2 } − G ( x), x   rộng cho phương trình (3) và chứng minh sự hội tụ của P ( x) = x.e  = , nó. Cuối cùng, chúng tôi trình bày các kết quả số cho  x, x   một số ví dụ cụ thể.  1  F ( x) = x − P2  x − f ( x)  , 2. Xấp xỉ nửa trơn cho hàm không trơn s  s  Trước hết, chúng ta trình bày một tính chất quan  − x2 − * trọng cho nghiệm x của phương trình (2). Tính chất trong đó G ( x) = x.e  . này được phát biểu trong bổ đề sau: Bổ đề 2.1. Cho f  C1 (¡ ) và s  0 . Với mỗi x*  ¡ nếu F ( x* ) = 0 thì một trong hai trường hợp sau xảy ra: (1) x* = 0 . 2 (2) x*  . s Hình 2. (a) Đồ thị hàm P ( x) và (b) Đồ thị hàm Fò ( x) 2 Chứng minh. Giả sử x*  . Ta sẽ chứng với  = 0.01 ,  = 0, 0005 và f ( x) =| x | s minh x* = 0 . Thật vậy, từ F ( x* ) = 0 ta có Trong phần tiếp theo chúng ta sẽ chỉ ra rằng các hàm P và F là các hàm nửa trơn. Để thuận tiện cho người  * 1 *  2 đọc, chúng tôi nhắc lại khái niệm hàm nửa trơn ở đây.  x − s f ( x )  = x  * H 2 . s   s Định nghĩa 2.1. Cho U là một tập mở của D  ¡ và f là một ánh xạ xác định trên D . Ánh xạ 20
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 7, số 3 (2017), 19-25 f :U → ¡ được gọi là khả vi Newton tại x U nếu + Nếu x0   thì với mọi h = 0 đủ bé, ta có tồn tại ánh xạ F : U → L ( D, ¡ ) sao cho x0 + h   . Khi đó | f ( x + h) − f ( x ) − F ( x + h) h | lim =0 (4) P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h h →0 |h| = x0 + h − x0 − 1.h = 0. trong đó L ( D, ¡ ) là tập các phiếm hàm tuyến tính liên tục từ D vào ¡ . Do đó Khi đó F được gọi là một đạo hàm Newton của f | P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h | h→0 → 0. tại x . |h| Định nghĩa 2.2. Cho U là một tập con mở của + Nếu x0   thì với mọi h = 0 đủ bé, ta có D  ¡ và f là một ánh xạ xác định trên D . Ánh xạ x0 + h   . Khi đó f : U → ¡ được gọi là khả vi Newton trên U nếu tồn P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h tại ánh xạ F : U → L ( D, ¡ ) sao cho với mỗi x U , | f ( x + h) − f ( x ) − F ( x + h ) h | = G ( x0 + h) − G ( x0 ) − (G ( x0 )).h lim = 0. (5) h →0 |h| + (G ( x0 )).h − (G ( x0 + h)).h Khi đó hàm số f được gọi là hàm Newton nửa trơn  G ( x0 + h) − G ( x0 ) − (G ( x0 ))h và F được gọi là một đạo hàm Newton của f trên U . + (G ( x0 ))h − (G ( x0 + h)).h . Bổ đề 2.2. Với   0 và f  C (¡ ) ta có: 2 Vì G (.) khả vi liên tục trên ¡ nên (1) P ( x) và F ( x ) là các hàm số liên tục và khả vi Newton trên ¡ với các đạo hàm Newton tương ứng là G ( x0 + h) − G ( x0 ) − (G ( x0 )).h lim = 0, (G ( x)), | x |  h →0 |h| ( )  P ( x) =   , (6) 1, | x |  và (G ( x0 )).h − (G ( x0 + h)).h   2 1 − X s ( x)(G ( X s )), Xs  lim h →0 |h|   s ( F ( x) ) =  . (7)  1 f ( x), 2 = lim (G ( x0 )).h − (G ( x0 + h)).h = 0.  s Xs  h →0 s Từ đó, suy ra  − x2 −  2 x2  ở đây (G ( x)) = e  1 +  là đạo hàm của hàm | P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h |    lim = 0. h→0 |h| 1 số G và X s = X s ( x) = x − f ( x) . + Nếu | x0 |=  tì ta xét các giới hạn một phía. s (2) Với mọi x ¡ ta có Khi h → 0+ và | x0 + h |  thì lim P ( x) = H  ( x), | P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h |  → 0+ lim+ h →0 |h| lim+ F ( x) = F ( x).  →0 | G ( x0 + h) − G ( x0 ) − (G ( x0 + h)).h | = lim+ Chứng minh. (1) Với mỗi x0  ¡ ta có các trường h →0 |h| hợp sau: = 0. 21
Phạm Quý Mười, Đỗ Viết Lân, Dương Xuân Hiệp, Phan Đức Tuấn và Phan Quang Như Anh Khi h → 0+ và | x0 + h |  thì   2 1 − X s ( x)(G ( X s )), Xs  ,   s | P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h | ( F ( x) ) =  lim+  1 f ( x), 2 h →0 |h|  s Xs  . s x0 + h − x0 − h = lim+ = 0. h →0 |h| 2  1 Nếu X s ( x)  thì ( F ( x) ) = f ( x) . Do đó Tương tự ta cũng chứng minh được s s A  B | P ( x + h) − P ( x0 ) − ( P ( x0 + h)).h | 0  ( F ( x) )  lim−  0 = 0. s s h→0 |h| 2  Như vậy ta có Nếu X s ( x)  thì ( F ( x) ) = 1 − X s ( x) M , s | P ( x0 + h) − P ( x0 ) − ( P ( x0 + h)).h | lim = 0. trong đó, M được định nghĩa bởi: h→0 |h| 2 ( X s ( x ) )2 − Vậy P ( x) khả vi Newton và ( P ( x)) được cho s  2 2  1 +  . ( X s ( x) )  . M =e  và bởi (6). Theo công thức đạo hàm Newton của hàm hợp   [3], ta có: 1   lim M = 0 . Hơn nữa X s ( x) = 1 − f ( x) bị chặn nên    →0  1   1  s F ( x) = 1 −  x − f ( x)   P  x − s f ( x)    s      0  0 sao cho   (0;  0 ) ta có:  Áp dụng kết quả (6) ta có ngay kết quả cần chứng minh. 0  1  ( F ( x) )  2 (2) Nếu | x |  thì P ( x) = x = H ( x) .  A  B Đặt m1 = min 1;  và m2 = max 2;  ta luôn Nếu | x |  thì P ( x) = G ( x) .  s  s có 0  m1 | F ( x) | m2 Vì  − x 2  0 nên khi  → 0+ thì G ( x) → 0 . Bổ đề 2.4. Cho x * là một nghiệm của phương trình (2). Như vậy ta có lim+ P ( x) = H  ( x ), x  ¡ .  →0 Khi đó r  0 sao cho x  B( x* , r ) và   0 ta Từ kết quả trên ta có luôn có   1  m1 | x − x* | lim+ F ( x) = lim+  x − P2  x − s f ( x)   | F ( x) − F ( x* ) − F ( x).( x − x* ) | .  →0  →0   s    4 Chứng minh.   0 vì F ( x* ) là đạo hàm của F  1  = x − H 2  x − s f ( x)  . tại x * nên s   Vậy lim+ F ( x) = F ( x) . | F ( x* + h) − F ( x* ) − F ( x* + h).h |  →0 lim =0 h→0 |h| Bổ đề 2.3. Nếu 0  A  f ( x)  B, x  U thì Từ đó suy ra r  0 sao cho h  B (0; r ) \ {0} , ta có  0  0 sao cho   (0;  0 ) ta luôn có | F ( x* + h) − F ( x* ) − F ( x* + h).h | m1 0  m1 | F ( x) | m2 .  . |h| 4 Chứng minh. Theo Bổ đề 2.2, ta có Đặt x = x* + h ta có x  B( x* , r ) và 22
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 7, số 3 (2017), 19-25 m1 | x − x* | 3. Phương pháp Newton suy rộng | F ( x) − F ( x* ) − F ( x).( x − x* ) | . 4 Như đã trình bày ở phần đặt vấn đề, phương pháp * Newton suy rộng cho phương trình (2) như sau: Bổ đề 2.5. Cho x là một nghiệm của phương trình (2). Ta có m 1. Chọn x0  ¡ và  n sao cho 0   0  | x0 − x* | . 4c F ( x* ) − F ( x* )  c. ,   0. 2. Thực hiện bước lặp: Chứng minh. Ta có F ( x*) = 0 nên 1 2.1 Tính xn +1 = xn − .F ( xn ) F ( x ) − F ( x ) = F ( x ) * * * Fn ( xn ) n  2 2.2 Chọn  n +1 sao cho ( )  max 0; − X 2 x*   s  ( ) − = x* − X x* .e  m1 0   n +1  | xn +1 − x* |, (8) 4c  1  + Nếu x* = 0 thì H 2  − f (0)  = 0 . Suy ra trong đó m1 là hằng số được xác định trong Bổ đề 2.3. s  s  Sự hội tụ của dãy { xn } được đưa ra ở định lí sau: 1 2 − f (0)  Định lí 3.1. Cho x * là một nghiệm của phương s s trình (2), x0  ¡ là một số thực tùy ý, và dãy ( xn ) 1 2 và X s (0) = − f (0)  . định nghĩa bởi vòng lặp xn+1 = xn − 1 .F ( xn ), n = 0,1,. s s Fn ( xn ) n Do đó Nếu x0 đủ gần x * và dãy { n } thỏa mãn 2 X s2 ( 0)− s m1 F (0) − F (0) = − X s ( 0 ) .e  0  n  | xn − x* |, n = 0,1,. 4c thì dãy { xn } hội tụ đến x * với tốc độ tuyến tính.   X s ( 0) = c . Chứng minh. Giả sử x0 đủ gần x * để Bổ đề 2.3 2 − X s2 (0) đúng. Khi đó, ta có: s 2 xn +1 − x* = xn − 1 .F ( xn ) − x* + Nếu | x* | thì s Fn ( xn ) n  1  H 2  x* − f ( x* )  = x*  0 . 1  s  = . Fn ( xn )( xn − x* ) − F n ( xn ) s Fn ( xn )  1  1 Do đó x* = H 2  x* − f ( x* )  = x* − f ( x* ). 1 = . Fn ( xn )( xn − x* ) − F n ( xn ) + F n ( x* ) s   s s  F n ( xn ) Đẳng thức này chỉ xảy ra khi f ( x* ) = 0 . Điều này − F n ( x* ) + F ( x* ) suy ra rằng F ( x* ) − F ( x* ) = 0 − 0 = 0,   0. 1  . F n ( xn ) − F n ( x* ) − Fn ( xn )( xn − x* ) Fn ( xn ) Vậy | F ( x* ) − F ( x* ) | c. ,   0. 23
Phạm Quý Mười, Đỗ Viết Lân, Dương Xuân Hiệp, Phan Đức Tuấn và Phan Quang Như Anh 1 Ví dụ 4.2. Cho f ( x) = x4 − 8x2 + 4 ;  = 0, 01 ; + . F ( x* ) − F n ( x* ) Fn ( xn ) 1 s = 10 ; òn = . 100n 1 m1 xn − x * c  . + n. Fòn ( xn ) m1 4 m1 Thực hiện bước lặp xn +1 = xn − . Fòn ( xn ) m1 Vì 0   n  xn − x* với mọi n¥ , ta suy ra Sự hội tụ của dãy { xn } được thể hiện ở Bảng 2. Dễ 4c 1 thấy nghiệm đúng ở đây là x* = 2 và x* = −2 , khi ta lấy xn +1 − x  xn − x* với mọi n  ¥ . Bằng phương pháp * x0 gần với nghiệm nào thì xn sẽ hội tụ về nghiệm đó. 2 1 quy nạp, ta có xn − x*  n x0 − x* . Điều này suy ra Nếu lấy x0 = 3 thì xn → 2 2 Nếu lấy x0 = −4 thì xn → −2 rằng dãy { xn } hội tụ đến x * với tốc độ tuyến tính. Chú ý 3.1. Điều kiện (8) chỉ mang tính lí thuyết. Trong thực tế, nghiệm chính xác là giá trị mà chúng ta muốn tìm nên không được biết. Trong thực hành, chúng ta có thể chọn một dãy không âm tùy ý { n } sao cho tốc độ tiến tới không của dãy này nhanh hơn tốc độ tuyến tính (chẳng hạn hội tụ bậc đa thức hoặc bậc mũ) và giá trị ban đầu  0 đủ bé. 4. Một vài ví dụ số về phương pháp Newton suy rộng Ví dụ 4.1. Cho 1 f ( x) = x 2 ; = 0,5; s = 100; òn = . 100n Fòn ( xn ) Thực hiện bước lặp xn +1 = xn − . Fòn ( xn ) Sự hội tụ của dãy { xn } được thể hiện ở Bảng 1. Dễ thấy nghiệm đúng ở đây là x* = 0 , và dù ta lấy x0 = 20 khá xa x * thì cũng chỉ sau 3 bước lặp xn đã hội tụ về x * . 5. Kết luận Trong bài báo này, chúng tôi nghiên cứu bài toán tìm nghiệm của phương trình không liên tục một biến, Phương trình (1), xuất hiện trong các bài toán chỉnh hóa cho bài toán ngược. Chúng tôi đã đề xuất một họ các hàm khả vi Newton, xấp xỉ cho hàm không trơn trong Phương trình (1) và nghiên cứu một số tính chất cơ bản của họ hàm này. Trên cơ sở đó, chúng tôi đề xuất phương pháp Newton suy rộng cho Phương trình (1) và 24
ISSN 1859 - 4603 - Tạp chí Khoa học Xã hội, Nhân văn & Giáo dục, Tập 7, số 3 (2017), 19-25 chứng minh sự hội tụ địa phương của phương pháp này. quasinewton methods in weighted r1 -regularization. Các ví dụ số đã chỉ ra, phương pháp Newton suy rộng Journal of Inverse and Ill-Posed Problems. 21(5), rất hiệu quả, có tốc độ hội tụ nhanh như phương pháp pp.665-693. Newton cổ điển cho phương trình trơn. [4] Xiaojun Chen, Zuhair Nashed, and Liqun Qi (2000). Smoothing methods and Semismooth Tài liệu tham khảo methods for nondifferentiable operator equations. SIAM Journal Numerical Analysis. 38(5), 1200- [1] Thomas Blumensath and Mike E Davies (2008). 1216. Iterative thresholding for sparse approximations. [5] M. HinterMuller, K. Ito, and K. Kunish (2003). Journal of Fourier Analysis and Applications, 14(5- The primal-dual active set strategy as a semismooth 6), 629-654. Newton method. SIAM Journal on Optimization. [2] Thomas Blumensath, Mehrdad Yaghoobi, and 13(3), 865-888. Mike E Davies (2007). Iterative hard thresholding [6] M. HinterMuller (2010). Semismooth Newton and l0 regularisation. IEEE International Conference Method and Applications. Oberwolfach-Seminar on on Acoustics. Speech and Signal Processing- Mathematics of PDE-Constrained Optimization, ICASSP'07, 3: III-877. IEEE. November. [3] Pham Quy Muoi, Dinh Nho Hao, Peter Maass, and Michael Pidcock (2013). Semismooth newton and GENERALIZED NEWTON METHOD FOR NON-CONTINUOUS ONE-VARIABLE EQUATIONS Abstract: In this article, we put forward a generalized Newton method to find out the root of a non-continuous equation. Here we only present this method for discontinuous equations in a one-way space. First of all, we propose approximate semi-smooth functions for corresponding non-smooth functions. Then, we prove some basic properties that are necessary for the testification of the convergence of the generalized Newton method. After that, we prove the convergence of this method in non-continuous equations under study. Finally, we present the root findings for a number of specific examples. The numerical examples show that the convergence speed of the generalized Newton method is as fast as that of the traditional Newton method. Key words: generalized Newton method; non-continuous equation; Newton derivative; semi-smooth approximation; root of a non-continuous equation. 25