Luận văn bao gồm phần mở đầu, ba chương: Chương 1 - Các khái niệm cơ bản về giải tích hàm; chương 2 - Lịch sử phương pháp Newton và chương 3 - Phương pháp Newton Kantorovich. Mời các bạn tham khảo!
Không gian Euclide
Cho E là không gian vectơ trên trường số thực R, một tích vô hướng trên E là một ánh xạ :E ×E →R
(x, y) →< x, y > thỏa mãn các điều kiện sau
Không gian vectơ E trên trường số thực R được gọi là không gian vectơ Euclide khi có một tích vô hướng xác định Độ dài của một vectơ x trong không gian vectơ Euclide E với tích vô hướng được tính bằng công thức kxk = √.
< x, x > Định nghĩa 1.4 Đối với hai vectơ x và y của không gian vectơ Euclide thì ta gọi góc ϕ giữa x và y được xác định bởi công thức: cosϕ = < x, y > kxkkyk
Không gian Banach và toán tử liên tục
Không gian Banach
Định nghĩa 1.5 (Không gian định chuẩn)
Một không gian định chuẩn (hay không gian tuyến tính định chuẩn) là không gian tuyến tính X trên trường P (P = R hoặc P = C) với một ánh xạ từ X vào tập số thực R, được gọi là chuẩn và ký hiệu là k.k, thỏa mãn các tiên đề nhất định.
1 (∀x∈ X)kxk ≥0, kxk = 0 ⇔ x= θ (ký hiệu phần tử không là θ);
Số kxk được gọi là chuẩn của vectơ x, và không gian định chuẩn được ký hiệu là X Các tiên đề (1), (2), (3) được xem là hệ tiên đề chuẩn Định nghĩa 1.6 đề cập đến sự hội tụ trong không gian định chuẩn.
Dãy điểm {xn} của không gian định chuẩn X được gọi là hội tụ tới điểm x ∈ X nếu lim n→∞kx n −xk = 0 Kí hiệu lim n→∞x n = x hay x n → x khi n → ∞ Định nghĩa 1.7 (Dãy cơ bản)
Dãy {x n } trong không gian định chuẩn X được gọi là dãy cơ bản nếu n,m→∞lim kxn −xmk = 0. Định nghĩa 1.8 (Không gian Banach)
Không gian định chuẩn X được gọi là không gian Banach nếu mọi dãy cơ bản trong X đều hội tụ.
Xét không gian véc tơk- chiềuRk, với mỗix∈ Rk, x = (x1, x2, , xk)trong đó x i ∈ R, i = 1,2, , k Đặt kxk q
Pk i=1|x i | 2 Khi đó Rk là không gian Banach.
Cho không gian véc tơ C [a,b] Đối với hàm số bất kì xt ∈ C [a,b] , ta đặt kxk = max [a,b] |x t | Khi đó C [a,b] là không gian Banach.
Toán tử tuyến tính liên tục
Cho X, Y là hai không gian định chuẩn. Định nghĩa 1.9 (Toán tử tuyến tính)
Một toán tử A : X → Y gọi là một toán tử tuyến tính nếu thỏa mãn các điều kiện sau
Ta viết Ax thay cho A(x) Nếu X ≡ Y ta nói A là toán tử trong X.
ImA = {y ∈ Y|y = Ax,∀x ∈ X} là miền giá trị của toán tử A
KerA = {x ∈X|Ax = 0} là hạch (hạt nhân) của toán tử A.
Trong toán học, ta có định nghĩa X ≡ Y ≡ C [a,b] và phương trình Ax(t) = Rb a K(t, s)x(s)ds, với K(t, s) là hàm liên tục theo hai biến t và s trong khoảng a ≤ t, s ≤ b Ở đây, A được gọi là toán tử tuyến tính và là một toán tử tích phân Định nghĩa 1.10 đề cập đến khái niệm toán tử liên tục.
Giả sử X, Y là hai không gian định chuẩn Toán tử A : X → Y gọi là liên tục tại x 0 ∈ X nếu
Toán tử A được gọi là liên tục trên X nếu nó liên tục tại mọi điểm thuộcX.
Đạo hàm theo nghĩa Fréchet
Phương pháp Viète
Vào cuối năm 1664, Isaac Newton bắt đầu quan tâm đến toán học và đã tiếp cận công trình của nhà đại số học Pháp, Francois Viète (1540-1603) Viète nổi tiếng với tác phẩm "De numerosa potestatum", nghiên cứu về nghiệm số của phương trình đại số phi tuyến, được xuất bản năm 1600 và tái bản trong tuyển tập "Opera Mathematica" vào năm 1646 William Oughtred cũng đã tóm tắt và bổ sung tài liệu của Viète trong cuốn "Clavis Mathematicae" từ năm 1647 Newton đã tham khảo cả bộ sưu tập của Schooten và ấn bản Latin của Oughtred, ghi chép cẩn thận các kết quả, cho thấy sự quan tâm của ông đối với nghiệm số của phương trình phi tuyến, đặc biệt là các phương trình đa thức monic mà Viète tập trung nghiên cứu.
Kỹ thuật Viète cho phép chúng ta xác định các chữ số thập phân của nghiệm x ∗ trong phương trình, với các chữ số có nghĩa liên tiếp được ký hiệu là a0, a1, a2, Do đó, x∗ có thể được biểu diễn dưới dạng x∗ = a0 10^k + a1 10^(k−1) + a2 10^(k−2) + Đối với ước lượng thứ i của x ∗, ta có x i = a0 10^k + a1 10^(k−1) + + a i 10^(k−i) Giả sử đã biết xi, thì ước lượng tiếp theo xi+1 có thể được tính bằng công thức xi+1 = xi + ai+1 10^(k−(i+1)), từ đó cho phép tính toán a i+1 như phần nguyên của biểu thức này.
Trong đón là bậc của đa thức, và đôi khi đại lượng 5(p(xi + 10k−i−1) + p(xi)) trong tử số của (2.5) có thể được thay thế bằng giá trị của p(xi) Số nguyên ai+l có thể âm hoặc có một vài chữ số sau dấu phẩy, cho phép hiệu chỉnh hoặc ước lượng sớm hơn giá trị xi của x* Viết lại (2.4) dưới dạng f(x) = 0, trong đó f(x) = p(x) - N, biểu thức (2.5) trở thành.
Do đó, phương pháp Viète gần như tương đương với x i+1 = x i −10 k−i−1 f(x i ) f(xi + 10 k−i−1 )−f(xi)
Phương pháp của Viète có thể được coi là một phiên bản sơ khai của phương pháp sai phân hữu hạn, tương tự như việc thay thế (2.2) vào (2.1) với hi = 10 k−i−1 Việc trừ biểu thức 10 (k−i−1)n trong mẫu số của (2.5) có thể được giải thích khi p(x) = x n thông qua khai triển nhị thức (x i + 10 k−i−1 ) n Đối với phương trình bậc hai monic, phương pháp này cho kết quả chính xác tương tự như phương pháp Newton-Raphson (2.1), mặc dù trong thực tế, thành phần này thường không đáng kể và bị bỏ qua Sẽ có một so sánh thú vị giữa kỹ thuật này và phương pháp Newton-Raphson trong trường hợp p(x) = x n, và kỹ thuật này đã được sử dụng rộng rãi cho đến khi bị thay thế bởi phương pháp Newton-Raphson.
Phương pháp dây cung
Trong bộ sưu tập "Newton’s Waste Book", có một kỹ thuật lặp được gọi là "phương pháp dây cung" nhằm giải phương trình phi tuyến Phương pháp này được áp dụng để giải phương trình f(x) = 0, với công thức hiện đại là x k+1 = x k − f(x k ) / (f(x k ) − f(x k−1 )) (x k − x k−1).
Cuộc thảo luận lịch sử về phương pháp Regula Falsi của Maas cho thấy mối quan hệ chặt chẽ với các phương pháp hiện đại Sự khác biệt giữa các số đối được phân tích từ góc độ tuyến tính hóa hàm f(x), mang lại những hiểu biết mới cho kỹ thuật này Hình ảnh dưới đây minh họa rõ nét cho cách tiếp cận tính toán hiệu quả của phương pháp.
Trong nghiên cứu của Newton, chúng ta nhận thấy rằng, thông qua sự tương tự của các tam giác, tỷ lệ a/b = c/d được thiết lập, từ đó dẫn đến công thức (2.6) cho x i+1 ≈ x ∗ Cụ thể, công thức này được biểu diễn qua (f(x i )−f(x i−1 ))/(x i − x i−1 ) = ∓f(x i )/d, với d được xấp xỉ là ∓(x ∗ −x i ) Việc lựa chọn dấu hiệu phù hợp trong từng trường hợp là rất quan trọng để đạt được kết quả chính xác.
Hình 2.1: Phương pháp dây cung
Ví dụ 2.1 Tìm nghiệm dương của phương trình f(x) := x 3 −0,2x 2 −0,2x−1,2 = 0 với độ chính xác ε = 0,02 Vìf(1) = −0,6; f(1,5) = 1,425 nên ξ ∈ (1; 1,5).
Dễ thấy f 0 (x) = 3x 2 −0,4x−0,2 > 0 và f 00 (x) = 6x−0,4 > 0 với mọi x∈ (1; 1,5) Xấp xỉ ban đầu x0 = 1. Điểm Fourier b= 1,5. Đặt fn = x 3 n −0,2x 2 n −0,2xn−1,2, ta có xn+1 = xn − f n
Do x 3 = 1,198,f(x 3 )' −0,0072 và f 00 (x)≥ 3×1,198 2 −0,4×1,5−0,2 ' 3,49 ta có ước lượng 0 < ξ−x 3 < 0,0072 3,49 ' 0,002.
Phương pháp Newton- Công thức đầu tiên
Trong tác phẩm "De analysi per aequationes numero terminorum infinitas" của Newton, xuất bản vào giữa năm 1669, ông đã đề cập đến những ý tưởng về vi phân và các đại lượng vô cùng nhỏ Đoạn trích từ cuốn sách, khi được dịch sang tiếng Anh, là cuộc thảo luận đầu tiên về phương pháp Newton, mặc dù công thức được trình bày khác biệt so với hiện nay và các tính toán dài dòng hơn nhiều Phương pháp này chỉ được áp dụng trong phạm vi giải phương trình đa thức, không sử dụng Toán giải tích hay tham chiếu đến đạo hàm, cho thấy rằng nó hoàn toàn mang tính đại số.
Trong một số trường hợp, Newton đã áp dụng các phương pháp và ký hiệu truyền thống để làm cho ý tưởng của mình dễ hiểu hơn cho nhiều đối tượng Tuy nhiên, không có bằng chứng rõ ràng về thời điểm này, ông nhận thấy kỹ thuật đặc biệt này là ứng dụng của phép tính hoặc có nguồn gốc từ nó, sử dụng các kỹ thuật tính toán.
Kỹ thuật Newton có thể được biểu diễn bằng ký hiệu hàm số hiện đại, với x₀ là ước lượng ban đầu cho nghiệm x∗ của phương trình f(x) = 0 Đặt g₀(x) = f(x) và giả sử g₀(x) = Σaᵢxⁱ (i = 0 đến n) Khi định nghĩa e₀ = x∗ - x₀, ta có thể mở rộng nhị thức x₀ để xây dựng một phương trình đa thức mới trong biến e₀.
Bỏ qua các thuật ngữ liên quan đến bậc cao hơn của e 0 (tuyến tính hóa hiệu quả tính toán rõ ràng đa thức g1) tạo ra
Từ đó, chúng ta suy luận rằng e 0 ≈ c 0 = − n X i=0 a i x i 0 n X i=0 a i ix i−1 0
Và đặt x 1 = x 0 +c 0 Chính thức, chỉnh sửa này có thể viết c 0 = −g 0 (x 0 )/g 0 0 (x 0 ) =−f(x 0 )/f 0 (x 0 ).
Lặp lại quá trình, thay vì mở rộng đa thức g0 về x1, ta mở rộng đa thức g1 tại điểm c0, coi c0 là ước lượng đầu tiên của nghiệm e0 cho phương trình g1(x) = 0 Từ đó, ta có 0 = g1(e0) g1(c0 + e1) = g2(e1), với g2 được tính toán rõ ràng Việc tuyến tính hóa tạo ra một hiệu chỉnh chính thức, tương đương với e1 ≈ c1 = -g1(c0)/g1'(c0), và c1 = -g0(x0 + c0)/g0'(x0 + c0) - f(x1)/f'(x1), dẫn đến x2 = x1 + c1 Quá trình này tiếp tục bằng cách mở rộng g2 về c1 và tiếp tục như vậy.
Quá trình mà Newton mô tả yêu cầu tính toán tường minh các đa thức kế tiếp g1, g2, , điều này khá tốn công sức Trong bài thuyết trình của ông, việc tính toán không được sử dụng mà hoàn toàn dựa vào việc duy trì giới hạn bậc thấp nhất trong một nhị thức mở rộng Đáng lưu ý, ước lượng cuối cùng của x∗ chỉ được tính vào cuối quá trình, với công thức x∗ = x0 + c0 + c1 + thay vì cập nhật và sử dụng liên tiếp ước lượng x i.
Quá trình mà Newton đề xuất khác biệt rõ rệt so với kỹ thuật lặp hiện tại, với sự nhận thức về sự hội tụ bậc hai Ông đã quan sát rằng số chữ số có nghĩa chính xác được giữ lại trong các bước nhân đôi liên tiếp tăng lên, cho thấy sự cải thiện đáng kể trong độ chính xác của phương pháp.
Các phương pháp khác cho phương trình phi tuyến 15 2.1.5 Công thức Raphson
Newton đã gửi hai bức thư đến địa chỉ John Smith, ngày 24 tháng
Vào ngày 7 tháng 8 năm 1675, Smith đã chuẩn bị một bảng chứa các hình vuông, hình lập phương và căn bậc bốn của các số nguyên từ 1 đến 10,000 Trong bức thư gửi ngày 8 tháng 5 năm 1675, Newton đề xuất rằng Smith chỉ cần tính căn của mỗi số nguyên thứ một trăm, sau đó sử dụng phép nội suy để tạo ra toàn bộ số lượng cần thiết với độ chính xác 8 chữ số Newton đã cung cấp cho Smith một số sơ đồ, trong đó ông giải phương trình x^n - A = 0 với n = 2, 3, 4, bắt đầu từ ước lượng ban đầu x0 = B Ông nhấn mạnh rằng nên giữ lại tất cả các chữ số đã tính để sử dụng làm thuật ngữ chỉnh sửa thay vì cắt ngắn sau vài chữ số có nghĩa đầu tiên Newton cho thấy rằng không cần phải lặp lại công thức nhiều lần, mà chỉ cần chọn ước lượng ban đầu với năm chữ số có nghĩa chính xác để đạt được mười một chữ số đúng sau một lần áp dụng công thức, nhận thức được khả năng nhân đôi số lượng chữ số có nghĩa chính xác trong một bước của quy trình, thể hiện sự hội tụ bậc hai của phương pháp.
Năm 1690, Joseph Raphson (1648−1712) đã xuất bản cuốn sách "Analysis aequationum universalis", giới thiệu một phương pháp mới để giải các phương trình đa thức Ấn bản thứ hai của cuốn sách được phát hành vào năm 1697, bao gồm tài liệu tham khảo đến Newton nhưng không có lời nói đầu như trong bản gốc Trong tác phẩm, Raphson nghiên cứu các phương trình có dạng a³ - ba - c = 0, với a là ẩn số, và chỉ ra rằng nếu g là ước lượng của nghiệm x*, thì một ước lượng chính xác hơn có thể được tính bằng g + x, trong đó x = c + bg - g³.
Phương pháp Raphson được áp dụng cho phương trình a³ - 2a - 5 = 0 với công thức g + x = g - f(g)/f'(g), trong đó f(a) = a³ - ba - c Bắt đầu từ ước lượng ban đầu g = 2, Raphson thực hiện các bước lặp để tính toán các hiệu chỉnh liên tiếp là x = 0,1, -0,0054, và -0,000048517.
−.0000000014572895859 và các ước lượng tương ứng g = 2, 2.1, 2.0946, 2.094551483 và 2.0945514815427104141 của x ∗
Raphson đã trình bày hơn 30 ví dụ và công thức trong cuốn sách của mình, chủ yếu liên quan đến đa thức cấp 10 Ông sử dụng các mở rộng nhị thức để sửa các thuật ngữ x, từ đó suy ra một phương trình cụ thể được áp dụng lặp đi lặp lại Mặc dù Raphson đã sử dụng phương pháp đại số hoàn toàn, ông đã viết các biểu thức tương ứng với f(x) và f'(x) dưới dạng đa thức Cuốn sách kết thúc với một tập hợp các công thức hiệu chỉnh cho nhiều loại phương trình đa thức Dù Công thức Raphson có liên quan đến vi phân, ông không bao giờ kết nối phép tính với kỹ thuật lặp của mình cho các phương trình đa thức, và phương pháp này không được mở rộng sang các lớp phương trình khác.
Công thức Raphson và phương pháp Newton là những công cụ quan trọng trong phát triển tính toán, đặc biệt là với công thức lặp giúp cải thiện đáng kể hiệu quả tính toán.
Phương pháp Newton trong không gian hữu hạn chiều
Trường hợp một biến
Cho hàm một biến f(x), mục tiêu là tìm giá trị củax thỏa mãn phương trình f(x) = 0.
Phương pháp Newton xuất phát từ việc xấp xỉ giá trị của đạo hàm tại một điểm : f 0 (x 1 ) = df(x 1 ) dx ≈ f(x 1 )−f(x 2 ) x1 −x2
Do ta đang muốn tìm x sao cho f(x) = 0 nên với f(x2) = 0 thì phương trình trở thành :x2 = x1− f f 0 (x (x 1 1 ) )
Tổng quát, phương pháp Newton lặp liên tục để tìm nghiệm ngày càng gần giá trị thực, với công thức nghiệm là: x n+1 =x n − f(x n ) f 0 (xn)
Ví dụ 2.2 Tìm nghiệm trong khoảng (1,1; 1,4) của phương trình: f(x) =x 3 −0,2x 2 −0,2x−1,2 = 0
Trường hợp nhiều biến
Giả sử ta giải hệ n phương trình n biến sau:
Một trong những phương pháp giải hệ phương trình là phương pháp Newton nhiều biến, được mở rộng từ phương pháp Newton cho hàm một biến Phương pháp này bắt đầu bằng việc đạo hàm từng phần của mỗi phương trình fj, cụ thể là dfj = ∂fj.
Giống như trước, ta xấp xỉ như sau: fj(x (2) )−fj(x (1) ) n
(x (2) i −x (1) i ) vớix (k) là giá trị của nghiệm ở lần lặp thứ k Ta mong muốnfj x (2)
= 0, do đó hệ n phương trình 2.2.2 có thể viết dưới dạng ma trận:
J (k) δx (k) = −R (k) trong đó J (k) là ma trận Jacobi kích thước n×n tại bước lặp thứ k
R (k) là vector thặng dư kích thước n×1 tại bước lặp thứ k
Do đó nghiệm của hệ tại bước thứ k+ 1 là x (k+1) = δx (k) +x (k)
Kantorovich đã mở rộng phương pháp Newton cho phương trình toán tử trong không gian vô hạn chiều.
Phương pháp Newton hay Newton- Raphson có dạng: x k+1 = x k −[F 0 (x k )] −1 F(x k ), k = 0,1, (3.1) với nghiệm của phương trình phi tuyến
Phương trình F(x) = 0 (F : X → Y), với X và Y là các không gian Banach, và F 0 là đạo hàm Fréchet của F, thể hiện phương pháp Newton trong giải tích Ý nghĩa hình học của phương pháp này trở nên rõ ràng khi F là một hàm số thực Cụ thể, điểm x k+1 được xác định là nơi mà tiếp tuyến của hàm số F tại điểm (xk, F(xk)) giao với trục Ox, với phương trình tiếp tuyến là y - F(xk) = F 0(xk)(x - xk).
Giải tích hình học của phương pháp Newton phức (F : C → C) được Yau và Ben- Israel đề xuất.
Trong trường hợp tổng quát F(x) xấp xỉ tại điểm x k như sau:
Phần tử không của L k (x) = 0 được định nghĩa là xấp xỉ mới x k+1
Biến thể của phương pháp Newton là phương pháp Newton tắt dần xk+1 = xk −tk[F 0 (xk)] −1 F(xk) (tk > 0, k = 0,1,2, ) (3.4) và phương pháp Newton đã sửa đổi: x k+1 = x k −[F 0 (x αk )] −1 F(x k ) (k = 0,1,2, ), (3.5) trong đó α0 = 0, αk−1 ≤ αk ≤ k (k ≥ 1)
Công thức Shamanskii-Newton sử dụng phương pháp đánh giá Jacobian sau m lần lặp liên tiếp Các phương pháp tương tự như phương pháp Newton được định nghĩa qua phép đệ quy: xk+1 = xk−[M(xk)] −1 F(xk) (k = 0,1,2, ) Trong đó, M(x) thường được xấp xỉ với F 0 (x ∗), với x ∗ là nghiệm của phương trình 3.2.
Kết quả hội tụ cho phương trình trơn
Cho X và Y là hai không gian Banach.
Cho S(x, r) = {z ∈ X | kz−xk < r} - hình cầu mở trong X với tâm x và bán kính r và cho S(x, r) là hình cầu đóng.
Cho F : S(x0, R) ⊂ X → Y là một ánh xạ phi tuyến Giả sử tồn tại một hình cầu S(x0, r) sao cho S(x, r) ⊂ S(x0, r) F' (x) và F'' (x) lần lượt là đạo hàm bậc nhất và bậc hai của F theo nghĩa Fréchet Kantorovich đã chứng minh một kết quả cổ điển, được gọi là Định lý 3.1 (Kantorovich).
Cho F : S(x 0 , R) ⊂ X → Y có đạo hàm Fréchet bậc hai liên tục tại S(x0, r) Hơn nữa, giả sử (i) ánh xạ tuyến tính Γ0 = [F 0 (x0)] −1 tồn tại, (ii) kΓ 0 F(x0)k ≤η, (iii) kΓ 0 F 00 (x)k ≤K (x∈ S(x0, r)).
1−2h h η, thì phương trình (3.2) sẽ có nghiệm x ∗ mà tại đó phương pháp Newton hội tụ. kx ∗ −x 0 k ≤r0. Hơn nữa, nếu h < 1 2 r < r1 = 1 +√
1−2h h η, hoặc h= 1 2 thì r ≤ r1, nghiệm x ∗ sẽ là duy nhất trong hình cầu S(x 0 , r).
Tốc độ hội tụ được đặc trưng bởi bất đẳng thức: kx ∗ −xkk ≤ 1
Chú ý 3.1 Các điều kiện (ii) và (iii) của định lí có thể được thay thế bởi: (i’)kΓ0k ≤ B 0 , (ii’)kF(x0)k ≤η 0 , (iii’)kF 00 (x)k ≤K 0 (x∈ S(x0, r))
Trong trường hợp này h, r 0 , r 1 tương ứng là: h= K 0 (B 0 ) 2 η 0 , r0 = 1−√
Chú ý 3.2 Các điều kiện h ≤ 1 2 và r 0 ≤ r là cần thiết cho sự tồn tại nghiệm Nghiệm không phải là duy nhất trong trường hợp: r < r1 hoặc r ≤ r 1
Lưu ý rằng tập S(x₀, r) chứa nghiệm của phương trình 3.2 Nếu ràng buộc k[F₀(x)]⁻¹k trong S(x₀, r) được biết, điều kiện áp đặt cho h có thể được nới lỏng bằng cách yêu cầu h ≤ 2 thay vì h ≤ 1/2, theo Định lý 3.2 của Mysovskikh.
Cho các điều kiện sau thỏa mãn:(i)kF(x0)k ≤ η; (ii) toán tử tuyến tính Γ(x) = [F 0 (x)] −1 tồn tại với x ∈ S(x0, r) tại kΓ(x)k ≤ B (x ∈ S(x0, r)); (iii) kF 00 (x)k ≤K (x ∈S(x 0 , r)) Khi đó, nếu h =B 2 Kη r 0 = Bη
Phương trình (3.2) có một nghiệm x ∗ ∈ S(x 0 , r) mà phương pháp Newton với điểm ban đầu x0 hội tụ.
Tốc độ hội tụ được cho bởi: kx ∗ −x k k ≤Bη (h/2) 2 k −1
Phép lặp Newton xk giữ nguyên tính chất dưới mọi phép biến đổi F → G AF, với A là ánh xạ tuyến tính giới hạn từ không gian Y đến không gian Banach Z Tính chất này có thể dễ dàng kiểm tra.
Định lý Kantorovich phản ánh tính chất bất biến affin một cách rõ ràng và được xem là một kiệt tác nhờ tầm quan trọng và phương pháp chứng minh hiệu quả Kết quả của Kantorovich đã khởi xướng nghiên cứu chuyên sâu về các phương pháp Newton và dẫn đến nhiều biến thể cũng như phần mở rộng trong lĩnh vực này Tài liệu của Ortega-Rheinboldt cung cấp cái nhìn tổng quan về những phát triển liên quan cho đến năm 1970, đồng thời đề cập đến một định lý bất biến khác của Deuflhard và Heindl.
Trong lý thuyết Newton-Kantorovich, các điều kiện liên tục trên F 00 (x) có thể được thay thế bằng bất đẳng thức kF 0 (x)−F 0 (y)k ≤Kkx−yk với (x, y ∈ S(x 0 , r)) hoặc k[F 0 (x 0 )] −1 (F 0 (x)−F 0 (y))k ≤ Kkx−yk trong cùng miền Điều này đã được một số tác giả thực hiện, trong đó Fenyo là người đầu tiên Một số kết quả điển hình của loại này được nêu trong Định lý 3.3 (Tapia).
Cho X, Y là các không gian Banach và F : D ⊂ X → Y Giả sử rằng trên một tập mở lồi D0 ⊂ D, F khả vi Fréchet với điều kiện kF 0 (x)−F 0 (y)k ≤ Kkx−yk cho mọi x, y ∈ D0 Giả sử x0 ∈ D0 thỏa mãn rằng (i) [F 0 (x0)] −1 tồn tại với k[F 0 (x0) −1]k < B, và k[F 0 (x0)] −1 F(x0)k ≤ η, từ đó h = BKη ≤ 1.
1−2h)/h)η) Khi dó, phép lặp Newton xk được xác định, còn lại trong S(x0, t ∗ ) và hội tụ đến x ∗ ∈ S(x0, t ∗ ), sao cho F(x ∗ ) = 0 Ngoài ra: kx ∗ −x k k ≤ η h
Kết quả này thường được gọi là định lí Kantorovich, là một cải tiến của Ortega và đưa ra ước lượng tối ưu cho tốc độ hội tụ.
Nếu các giả thuyết (i) và (ii) của định lý Kantorovich được thỏa mãn, thì không chỉ dãy Newton xk tồn tại và hội tụ đến nghiệm x∗, mà còn tồn tại [F 0 (x∗)]−1 Kết quả của Rall cho thấy rằng sự tồn tại của [F 0 (x∗)]−1 đảm bảo các giả thuyết của định lý.
Kantorovich với h < 1 2 và thỏa mãn tại mỗi điểm của hình cầu mở với tâm x ∗ Trong trường hợp như vậy x ∗ được gọi là nghiệm đơn giản của
Nếu x ∗ là nghiệm đơn giản của F, k[F 0 (x ∗ )] −1 k ≤B ∗ và
Khi đó, giả thuyết (i) với h < 1 2 và (ii) của định lí Kantorovich được thỏa mãn với x0 ∈ S ∗ , tại:
Giá trị được cho là bán kính của S ∗ là tốt nhất có thể Suy yếu điều kiện
C2 của F(x) thỏa mãn điều kiện Holder, với kF 0 (x)−F 0 (y)k ≤ Kkx−yk α cho mọi x, y thuộc D 0, trong đó 0 < α ≤ 1 là hằng số Kết quả này đã được cải thiện hoặc tái khám phá bởi nhiều tác giả khác nhau Một số kết quả tiêu biểu cho dạng này được thể hiện trong Định lý 3.5 (Janko’-Coroian).
Cho F : S(x 0 , R) ⊂ X → Y là một ánh xạ phi tuyến đã cho, giả sử rằng: kF 0 (x)−F 0 (y)k ≤ Kkx−yk α (x, y ∈ S(x 0 , r),0 < α ≤ 1), tại r = (1 +α) 1/α [(1 +α) 1/α h] 1−(1/α)
1 +α. Khi đó, có ít nhất một nghiệm x ∗ tại S(x0, r) và {x k } hội tụ đến x ∗ với tốc độ: kx ∗ −x k k ≤ [(1 +α) 1/α h] (1+h) k −(1/α)
Các kết quả tương tự cũng đúng với định lí Newton- Mysovskikh, một trong số đó như sau: Định lí 3.6 (Janko’)
Cho F : X → Y là một ánh xạ phi tuyến cho trước và cho các điều kiện sau thỏa mãn:
(i) Toán tử tuyến tính Γ(x) = [F 0 (x)] −1 tồn tại với mọi x ∈ S(x0, T η), tại đó:
(iv) h = Kη α < 1 +α. thì phương trình 3.2 có một nghiệm x ∗ ∈ S(x 0 , T η) mà phương pháp Newton với điểm ban đầu x0 là hội tụ Tốc độ hội tụ cho bởi: kx ∗ −xkk ≤T η h
Toán tử F được xem là một giải tích, và các nhà nghiên cứu Smale, Rheinboldt, Wang, và Han đã chứng minh được kết quả hội tụ chỉ dựa trên thông tin tại điểm ban đầu.
F (j) (x) là đạo hàm Fréchet thứ j của F tại điểm x Một kết quả điển hình của dạng này như sau: Định lí 3.7 (Rheinboldt)
Cho F : X → Y là giải tích trên một số tập mở S của X và cho: β(x) = k[F 0 (x)] −1 F(x)k, γ(x) = sup j>1
Xét 1 điểm x0 của S tại đó F 0 (x0) khả nghịch.
Cho ρ(≈ 0,16842669) là gốc dương của khối (√
Nếu 2(≈ 0,11909565) và khối cầu S(x0, r0) với bán kính r0 = ρ/γ(x0) được chứa trong S, thì phép lặp Newton xk sẽ hội tụ đến một nghiệm x ∗ của phương trình 3.2 Hơn nữa, sự hội tụ này ít nhất là đảm bảo.
R là bậc hai R 2 với hệ số 1 2
Sai số ước lượng cho phương pháp Newton
Phương pháp Newton có một số sai số ước lượng, trong đó định lý Kantorovich đóng vai trò quan trọng Các định lý tiếp theo dựa trên các điều kiện của định lý Tapia, với Gragg và Tapia đã bổ sung các giới hạn sai số tối ưu Định lý 3.8 (Gragg-Tapia) xác định rằng kx∗ − xk ≤.
Miel đã chứng minh định lý này bằng kỹ thuật của Ortega, đồng thời giới thiệu một phiên bản bất biến affin của định lý do Deuflhard và Heindl đề xuất Ngoài ra, Miel cũng phát triển riêng sai số giới hạn cho phương pháp Newton.
Cho các hằng số Ak, Bk và Ck đệ quy bởi:
C 1 = B 1 , C k+1 = 2C C k 2 k +∆/η. thì sai số giới hạn: kx ∗ −x k k ≤A k kx k −x k−1 k 2 ≤ B k kx k −x k−1 k ≤C k kx 1 −x 0 k, là phù hợp và tốt nhất có thể. Định lí 3.10 (Miel)
1 + (2 k /η)kx k+1 −xkk ≤ kx ∗ −xkk ≤ 2 k −1 η kxk −x k−1 k 2 nếu 2h = 1. Định lí 3.11 (Potra- Pta’k)
Khi đó γ(kx k+1 −x k k) ≤ kx k −x ∗ k ≤ (a 2 +kx k −x k−1 k 2 ) 1/2 −a.
Yamamoto đã chỉ ra rằng các ước lượng Gragg-Tapia phát sinh từ quan hệ lặp Kantorovich và Potra-Pta’k, đồng thời ước lượng Miel hoàn thiện lý thuyết Gragg-Tapia Ông cũng nhấn mạnh rằng hai kết quả tiếp theo cũng tuân theo định lý này.
Kantorovich ban đầu, kết quả của Miel cải tiến so với của Potra và Pta’k.
Yamamoto đưa ra phương pháp tìm sai số giới hạn cho phương pháp
Định lý Kantorovich và phương pháp Newton có mối liên hệ quan trọng trong lý thuyết tối ưu Bài báo của Yamamoto cung cấp một so sánh chi tiết giữa các giới hạn nổi tiếng, là nguồn tài liệu hữu ích cho việc ước lượng tối ưu trong phương pháp Newton Ngoài ra, Neumaier đã đề xuất một dạng ước lượng tối ưu khác cho hai vectơ bất kỳ x, y ∈ R N, với điều kiện x ≤ y khi và chỉ khi x i ≤ y i cho mọi i.
|A| = [|aij|] m,n i,j=1 cho bất kì A ∈ R m×n Định lí 3.12 (Neumaier)
Cho F : D ⊂ R n → R n liên tục, x0 ∈ D, A ∈ R m×n không suy biến và δ0 = A −1 F(x0) Giả sử rằng có một hằng số κ > 1 sao cho:
S(x0, κkδ0k) ⊂ D và một vectơ không âm c ∈ R n sao cho, với hàm đơn điệu định chuẩn k.k
Nếu vectơ b =|A −1 |c thỏa mãn điều kiện kbk < κ−1 thì F(x) có ít nhất một nghiệm trong S(x 0 , κkδ 0 k) và bất kì nghiệm xˆ thỏa mãn
Miền bao gồm S(x0, r) của định lí Kantorovich dễ dàng làm theo để lựa chọn tỉ lệ l∞ định chuẩn và A = F 0 (x0).
Sự hội tụ đơn điệu
Phương pháp Newton cho thấy sự hội tụ đơn điệu theo thứ tự từng phần, sử dụng phần riêng tự nhiên để sắp xếp vectơ và ma trận Đối với hai ma trận A và B thuộc R m×n, A ≤ B nếu và chỉ nếu aij ≤ bij cho mọi chỉ số i, j từ 1 đến n Hàm số F : R n → R n được định nghĩa là lồi trên một tập lồi D ⊆ R n.
Giả sử rằng F : R n → R n khả vi trên tập lồi D thì F là sai số trên D khi và chỉ khi
Giả sử rằng F : R n → R n là một hàm khả vi liên tục và lồi, với điều kiện F 0 (x) không suy biến và [F 0 (x)] −1 ≥ 0 cho mọi x ∈ R n Nếu F(x) = 0 có một nghiệm duy nhất x ∗, thì phương pháp lặp Newton x k sẽ hội tụ đến x ∗ từ bất kỳ x 0 nào Hơn nữa, ta có x ∗ ≤ xk+1 ≤ xk cho mọi k = 1, 2,
Phương pháp Newton cho các phương trình không xác định 30 3.5 Phương pháp Newton tại các điểm suy biến
Cho phương trình không xác định có dạng:
F(x) = 0 (F : R n → R m , n ≥ m) (3.12) một phần mở rộng của phép lặp Newton yêu cầu nghiệm của
Nếu n > m, thì xấp xỉ x+ không xác định duy nhất Có nhiều phương pháp để xác định x+ Kết quả đầu tiên trong dạng này là của Ben-Israel, sử dụng nghịch đảo Moore-Penrose để xác định x+: x+ = x−F 0 (x) + F(x) Định lý 3.14 (Ben-Israel).
Cho F : R n → R m là 1 hàm số, x 0 ∈ R n và r > 0 sao cho F ∈
C 1 (S(x 0 , r)) Cho M, N là các hằng số dương sao cho ∀x, y ∈ S(x 0 , r) với y ∈ R(F 0 (y) T ): kF(x)−F(y)−F 0 (y)(x−y)k ≤ Mkx−yk, kF 0 (x) + −F 0 (y) + F(y)k ≤Nkx−yk. và
Dãy x k+1 = x k −F 0 (x k ) + F(x k ) (k = 0,1,2, ) hội tụ tại một nghiệm F 0 (x) T F(x) = 0 nằm trên S(x0, r) nếu thỏa mãn điều kiện MkF 0 (x) + k+N = γ 0, tồn tại một ε > 0 phụ thuộc vào K, α, B, và η Nếu x0 ∈ Dη và kF(x0)k < ε, thì chuỗi lặp {xk} từ k=0 đến vô hạn được xác định bởi thuật toán dòng chuẩn tắc sẽ hội tụ về một điểm x* ∈ D.
F(x ∗ ) = 0 Hơn nữa, có 1 hàm số mà: kx k+1 −x ∗ k ≤βkx k −x ∗ k 1+α , k = 0,1,2, Định lí 3.16 (Walker)
Cho F thỏa mãn giả thuyết Jacobian tăng cường với Dη đã cho cho một số η > 0 Tồn tại một số ε > 0 chỉ phụ thuộc vào K, α, B và η, sao cho nếu x0 ∈ Dη và kF(x0)k < ε, thì phép lặp {xk} ∞ k=0 do thuật toán Jacobian tăng cường xác định sẽ hội tụ về một điểm x ∗ ∈ D với F(x ∗ ) = 0.
Hằng số β được xác định bởi bất đẳng thức kxk+1−x ∗ k ≤ βkxk −x ∗ k 1+α, với k = 0,1,2, Định lý sau đây là hệ quả của định lý trước, cho thấy rằng thuật toán Jacobian tăng cường cho F tương đương với dạng thuật toán dòng chuẩn tắc.
Nghịch đảo Moore-Penrose không phải là phương pháp duy nhất để thực hiện bước Newton trong các tình huống không xác định Nashed và Chen đã đề xuất việc áp dụng các nghịch đảo bên ngoài trong một bối cảnh nhất định.
Trong lý thuyết không gian Banach, L(X, Y) đại diện cho tập hợp tất cả các toán tử tuyến tính giới hạn từ không gian X vào không gian Y Nếu A thuộc L(X, Y), thì một toán tử tuyến tính B từ Y về X được gọi là nghịch đảo ngoài nếu thỏa mãn điều kiện BAB = B.
Nghịch đảo ngoài của A được kí hiệu là: A #
Vì vậy, phương pháp Newton được đưa ra dưới dạng: x k+1 = x k −F 0 (x k ) # F(x k ), k = 0,1,2, (3.15) Kết quả sau đây là đúng: Định lí 3.17 (Nashed-Chen)
Cho F :D ⊂ X → Y là khả vi Fréchet Giả sử tồn tại một tập con lồi mở D₀ của D, với x₀ ∈ D₀ và một giới hạn nghịch đảo bên ngoài F₀(x₀) # của F₀(x₀) Có hằng số η, K > 0 sao cho với mọi x, y ∈ D₀, các điều kiện sau được thỏa mãn: kF₀(x₀) # F(x₀)k ≤ η, kF₀(x₀) # (F₀(x)−F₀(y))k ≤ Kkx−yk, và h := Kη ≤ 1/2 Đồng thời, S(x₀, t*) ⊂ D₀ tại t* = (1−√).
1−2h)/K thì (i) dãy {x k } xác định bởi 3.15 với
F 0 (x k ) # = [I +F 0 (x 0 ) # (F 0 (x k )−F 0 (x 0 ))] −1 F 0 (x 0 ) # (3.16) nằm trênS(x0, t ∗ ) và hội tụ tại một nghiệmx ∗ ∈S(x0, t ∗ )củaF 0 (x0) # F(x) 0; (ii) phương trình F 0 (x 0 ) # F(x) = 0 có một nghiệm duy nhất trong:
(iii) Tốc độ hội tụ là phương trình bậc hai: kx ∗ −xk+1k ≤ 1
Tapia đã chứng minh sự hội tụ của phương pháp Newton khi sử dụng nghịch đảo trái F 0 (x) Ông mở rộng các kết quả của Gragg-Tapia và Paardekooper cho một dạng Kantorovich, áp dụng cho miền bao quanh nghiệm của phương trình F(x) = 0, trong đó F là ánh xạ từ không gian Hilbert X đến không gian Hilbert Y, và nghịch đảo của F 0 được sử dụng.
3.5 Phương pháp Newton tại các điểm suy biến
Cho X là một không gian Banach và F :X →Y.
Giả sử F(x ∗ ) = 0 và Jacobian F 0 (x ∗ ) là suy biến, nghiệm x ∗ được gọi là bội, kì dị hoặc không cô lập Những tình huống này có thể xảy ra trong phương pháp Bairstow Nghiên cứu về nhiều nghiệm được thực hiện đầu tiên bởi Rall, sau đó Reddien đã tìm ra một kết quả cơ bản từ việc nghiên cứu chuyên sâu về điểm kì dị Ở đây, chúng tôi chỉ nhắc lại kết quả của Reddien.
Giả sử F là C 3 và F 0 (x ∗ ) có không gian n chiều không giới hạn N và phạm vi đóng R, với X = N ⊕ R Hình chiếu P N lên N song song với R được định nghĩa, trong khi PR = I − PN Tập suy biến của F 0 (x) gần x ∗ có thể dao động từ một điểm đến một điểm mã hóa một đa tạp trơn thông qua x ∗ Tính không suy biến của F 0 chỉ có thể chọn trong lân cận của x ∗ Hơn nữa, việc thực hiện phép lặp Newton cần phải duy trì trong miền khả nghịch của F 0 đã chọn.
Tập sau thỏa mãn tất cả yêu cầu:
Wρ,θ = {x ∈ X|0 < kx−x ∗ k ≤ρ,kPR(x−x ∗ )k ≤θkPN(x−x ∗ )k} (3.18) Định lí 3.18 (Reddien)
(iii) Có c >0 sao cho ∀φ ∈ N, x ∈ X,kF 00 (x ∗ )(φ, x)k ≥ckφkkxk
Khi ρ và θ đủ nhỏ, tồn tại ánh xạ F 0 (x) −1 cho x∈ W ρ,θ, với ánh xạ G(x) từ Wρ,θ về chính nó và có c1 > 0 sao cho kF 0 (x) −1 k ≤ c1kx−x ∗ k −1 với mọi x∈ Wρ,θ Nếu x0 ∈ Wρ,θ và xk = G(xk−1) với k ≥ 1, dãy x k sẽ hội tụ về x ∗, thỏa mãn kPR(xk −x ∗ )k ≤ c2kxk−1 −x ∗ k 2 và giới hạn k→∞lim kP N (x k −x ∗ )k/kP N (x k−1 −x ∗ )k = 1 2.
Ngoài ra, x ∗ là nghiệm duy nhất của phương trình F(x) = 0 trên hình cầu S(x ∗ , ρ).
Kết quả nghiên cứu của Reddien cho thấy khu vực xung quanh điểm x ∗ có cấu trúc đặc biệt Griewank đã phát triển một miền giống sao mở từ điểm khởi đầu, từ đó phương pháp Newton đạt được sự hội tụ tuyến tính đến x ∗ Ngoài ra, Griewank cũng cung cấp một khảo sát chi tiết về các kết quả liên quan đến điểm kỳ dị.
Phương pháp Newton liên tục
Gavurin là người đầu tiên xem xét sự tương tự liên tục tương tự của phương pháp Newton. x 0 (t) = −[F 0 (x)] −1 F(x), x(0) =x0 (3.19)
Gọi x(t, x 0 ) biểu thị nghiệm của 3.19 sao cho x(0, x 0 ) = x 0
Chúng ta giả sửx(t, x0)được xác định trên khoảng cực đại[0, M) Nghiệm thỏa mãn tích phân đầu tiên.
Hình ảnh của quỹ đạo di chuyển theo hướng F(x 0 ) tiến về gốc khi thời gian trôi qua, với cường độ của F(x) giảm theo cấp số nhân dọc theo đường này Nếu nghiệm tồn tại trong khoảng [0,∞), thì giới hạn khi t tiến đến vô cực của F(x(t, x 0 )) sẽ bằng 0.
Chúng ta có thể kỳ vọng rằng nghiệm sẽ dẫn đến tập hợp V = {x | F(x) = 0} Đồng thời, chúng ta cũng mong muốn hành động từ nghiệm số của phương trình (3.19) Nếu áp dụng phương pháp Newton tường minh trên lưới, kết quả sẽ được cải thiện.
{t k+1 |t k+1 = tk +hk, hk >0, k = 0,1,2, , t0 = 0}, chúng ta có đệ quy: xk+1 =xk−hk[F 0 (xk)] −1 F(xk) (k = 0,1,2, ),
Phương pháp Newton "rời rạc" với h k = 1 (k ≥ 0) được gọi là phương pháp Newton liên tục hoặc tổng quát Để xác định điều kiện mà x(t, x0) tiến đến nghiệm x ∗ của phương trình (3.2) khi t → ∞, ta cần xem xét các yếu tố ảnh hưởng đến hội tụ Đồng thời, cũng cần phân tích các phương pháp rời rạc có khả năng dẫn dắt nghiệm x(t, x0) tới vô cùng.
Liên quan đến câu hỏi a), chúng ta trình bày các kết quả của Tanabe Cho F: R^n → R^m là hàm vi phân hai lần liên tục với n ≥ m, chúng ta xem xét sự liên tục theo phương pháp Newton-Ben-Israel với x_0(t) = -[F'(x)]^+ F(x), x(0) = x_0 Đặt V_F = {x ∈ R^n | F(x) = 0} và SF = {x ∈ R^n | rank(F'(x)) = m} Định lý 3.19 (Tanabe) được áp dụng trong bối cảnh này.
Nếu rank(F 0 (x ∗ )) = m với một nghiệm x ∗ ∈ V F thì tồn tại một vùng lân cận U ∗ của x ∗ sao cho với mỗi x0 ∈ U ∗ tồn tại một nghiệm x(t, x0),
0 ≤ t < ∞ của 3.20 với x(0, x 0 ) = x 0 , và khi t đến vô cùng nó luôn hội tụ đến một điểm trong V F có thể là khác với x ∗ trong trường hợp m < n. Định lí 3.20 (Tanabe)
Đối với x 0 ∈ S r đã cho, tồn tại một nghiệm x(t, x 0 ) trong khoảng thời gian 0 ≤ t < M, với điều kiện x(0, x0) = x0 Khi t tiến tới M, quỹ đạo sẽ hội tụ đến một nghiệm x ∗ thuộc V F ∩S F Trong một số trường hợp, với M = ∞, ta có kx(t, x 0 )−x ∗ k ≤ kkF(x 0 )kexp(−t) cho 0 ≤ t < ∞ với một số dương k, hoặc (ii) tiếp cận tập.
S ={x∈ R n |rank(F 0 (x)) < m} của các điểm kì dị của 3.20, hoặc (iii) phân kì.
Trong nghiên cứu của Tanabe, trường hợp m > n được xem xét Đồng thời, Smale đã đưa ra các điều kiện biên trên ∂Ω cho hàm F : R n → R n, với Ω là một miền cố định bị chặn mở trong R n, nhằm đảm bảo rằng nghiệm của phương trình dẫn đến một nghiệm x ∗ của F trong Ω.
Phương pháp Newton cho phương trình không trơn
Các phương trình không trơn xuất hiện từ nhiều bài toán khác nhau, bao gồm bài toán bổ sung phi tuyến, bài toán biến phân và hệ Karush-Kuhn-Tucker Phương pháp Newton không trơn được định nghĩa cho hàm F.
Hàm F từ R^n đến R^m là Lipschitz địa phương liên tục, và theo lý thuyết Rademacher, F gần như ở mọi nơi đều khả vi Điều này cho phép áp dụng các loại đạo hàm suy rộng khác nhau cho hàm F.
Giả sử F :R n →R m là hàm Lipschitz cục bộ và cho D F biểu thị tập hợp các điểm mà tại đó F là khả vi Cho:
Cho ∂F là Jacobian suy rộng của F trong ý nghĩa của Clarke Khi đó,
∂ b F(x) = ∂ B F 1 (x)×∂ B F 2 (x)× .×∂ B F m (x). Đạo hàm theo hướng cổ điển của F được định nghĩa bởi
Hàm F được gọi là nửa trơn tại x nếu F là Lipschitz địa phương tại x và lim
V ∈∂F (x+th 0 ),h 0 →h,t↓0{V h 0 } tồn tại với bất kì h∈ R n
Giả sử rằng F : R n → R n, phương pháp Newton không trơn được định nghĩa bởi x k+1 = x k − V k −1 F(x k ) với V k ∈ ∂F(x k ), k = 0,1,2, Định lý 3.21 (Qi-Sun) là một phần mở rộng của định lý Newton-Kantorovich cổ điển.
Giả sử F là Lipschitz địa phương và nửa trơn trên S(x0, r) Với bất kỳ V ∈ ∂F(x) và x, y ∈ S(x0, r), giả định rằng V không suy biến với kV −1 k ≤ β, kV(y−x)−F 0 (x;y−x)k ≤ Kky−xk, và kF(y)−F(x)−F 0 (x;y−x)k ≤ δky−xk, tại q = β(γ+δ) < 1 và βkF(x0)k ≤ r(1−q) Trong trường hợp này, các lần lặp (3.21) trong S(x0, r) sẽ hội tụ đến nghiệm duy nhất x ∗ của F(x) trong S(x0, r), với sai số ước lượng kx k −x ∗ k ≤ q.
Cải biến phương pháp Newton không trơn được xác định bởi xk+1 = xk−V k −1 F(xk) (Vk ∈∂BF(xk), k = 0,1,2, ) (3.22)
Phương pháp này đã chứng minh sự hội tụ siêu tuyến tính địa phương cho trường hợp F: R^n → R^m Thuật toán không trơn được mô tả như sau: xk+1 = xk - Vk # F(xk), trong đó Vk ∈ ∂BF(xk) và k = 0, 1, 2, ; với Vk # biểu thị nghịch đảo ngoài của Vk.
Sự hội tụ và phân kì của phương pháp Newton
Theo các giả định tiêu chuẩn, phương pháp Newton hội tụ địa phương trong một hình cầu tập trung tại nghiệm Chúng ta có thể xác định tập hợp tất cả các điểm x0 mà từ đó phương pháp Newton hội tụ tới một nghiệm Phương pháp Newton liên tục cho phép mô tả tập hợp các điểm hội tụ Trong không gian R^n, Braess nghiên cứu trường hợp đa phức tạp Một khả năng khác là áp dụng các kết quả và kỹ thuật từ lý thuyết lặp, với những kết quả tốt nhất được đưa ra cho các đa thức thực và phức Các quan sát này chỉ ra bài toán hội tụ, theo định lý 3.22 của Rényi.
Cho hàm f : R → R xác định trên khoảng (−∞,+∞) với giả thiết rằng f''(x) là đơn điệu tăng cho mọi x ∈ R và f(x) = 0 có đúng 3 nghiệm Ai (i = 1,2,3) Dãy x_{k+1} = x_k - f(x_k)/f'(x_k) hội tụ đến một trong các nghiệm này với mọi lựa chọn của x_0, ngoại trừ khi x_0 thuộc một tập hợp E của các điểm kỳ dị Đối với bất kỳ ε > 0, tồn tại một khoảng (t, t+ε) trong đó có 3 điểm a_i (t < a_i < t+ε, i = 1,2,3) sao cho nếu x_0 = a_i, thì dãy {x_k} sẽ hội tụ đến A_i (i = 1,2,3).
Một sự thay đổi nhỏ trong giá trị x0 có thể dẫn đến sự thay đổi lớn trong quá trình hội tụ, điều này làm nổi bật bản chất của bài toán hội tụ Tập hợp các điểm phân kỳ của phương pháp Newton là cách mô tả tốt nhất cho các đa thức thực.
Phân tích sai số
Lancaster, Rokne và Miel đã nghiên cứu mô hình lan truyền sai số của phương pháp Newton, mô tả bằng công thức ξ k+1 = ξ k −[F 0 (ξ k ) +E k ] −1 (F(ξ k ) +e k ) +g k Trong đó, Ek, ek và gk đại diện cho các sự nhiễu loạn, còn ξk là kết quả của phép lặp Newton Dưới một số giả định nhất định, nghiên cứu chỉ ra rằng chuỗi sai số {kxk − ξkk} là bị chặn Nếu xét một số k = p và l ≥ 1, với điều kiện ξ p = ξ p+1 và x k tiến tới x ∗, thì ta có {kξ k −x ∗ k} ≤ ξ 0 với k ≥ p.
Wozniakowski nghiên cứu phương pháp Newton trên một hệ thống phi tuyến được tham số hóa
F(x) = F(x;d) = 0 (F, x∈ C n , d∈ C m ) là phương trình mà tại đó d là tham số Giả sử rằng nghiệm đơn giản x ∗ tồn tại và F là đủ trơn trong x và d Chuỗi {xk} là các xấp xỉ liên tiếp của x ∗ thông qua một lần lặp φ Độ chính xác tương đối của máy tính trong f l số học được ký hiệu là ζ Lần lặp φ được coi là ổn định số nếu limk kx k −x ∗ k ≤ζ(k1kx ∗ k +k2kF x 0 (x ∗ ;d) −1 F d 0 (x ∗ ;d)kkdk) +O(ζ 2 ) Nếu tồn tại các giá trị {δx k } và {δd k } sao cho limk kF(xk +δxk;d+δdk)k = O(ζ 2 ) và kδx k k ≤k 3 ζkx k k, kδd k k ≤ k 4 ζkdk với k lớn, thì lặp φ được gọi là chạy tốt Nếu φ chạy tốt, nó cũng sẽ ổn định số Một thuật toán Newton trong f l số học được đưa ra như sau.
(ii) Giải hệ tuyến tính F 0 (x k )z k =F(x k ),
(iii) Đặt xk+1 = xk −zk.
Giả sử rằng F được tính toán bằng một thuật toán hiệu quả, ta có thể biểu diễn f l(F(xk;d)) = (I + ∆Fk)F(xk + ∆xk;d + ∆dk) = F(xk) + δFk, với các điều kiện k∆Fkk ≤ ζKF,k∆xkk ≤ Kxkxkk, k∆dkk ≤ Kdkdk và δFk = ∆FkF(xk) + F x 0 (xk)∆xk + F d 0 (xk)∆dk + O(ζ 2) Thêm vào đó, giả sử rằng f l(F 0 (xk;d)) = F 0 (xk) + δF k 0, trong đó δF k 0 = O(ζ 2) Điều này cho thấy rằng không cần một thuật toán hiệu quả để đánh giá F 0 (x k ) Cuối cùng, giả sử rằng một nghiệm tính toán của hệ tuyến tính F 0 (xk)zk = F(xk) thỏa mãn các điều kiện đã nêu.
Trong bài viết này, chúng ta xem xét phương trình (3.28) với điều kiện Ek = O(ζ), dẫn đến việc tính toán gần đúng xk+1 từ xk+1 = xk − zk Kết quả là xk+1 có thể được biểu diễn dưới dạng xk+1 = (I + δIk)(xk − zk), trong đó δIk là ma trận đường chéo và thỏa mãn điều kiện kδIk ≤ C1ζ, với C1 phụ thuộc vào định chuẩn Định lý 3.23 của Wozniakowski cung cấp nền tảng cho các kết quả này.
Nếu các điều kiện (3.25), (3.27) và (3.28) được thỏa mãn, phép lặp Newton sẽ hoạt động hiệu quả, tạo ra chuỗi {x k } với giới hạn limk kF(xk+1+ ∆xk−δIkxk;d+ ∆dk)k = O(ζ 2 ) Trong đó, các giá trị ∆x k , δI k và ∆d k được xác định bởi các công thức (3.25) và (3.29).
Phương pháp Newton là một trong những phương pháp phổ biến và hiệu quả để giải các phương trình toán học, bao gồm phương trình phi tuyến và hệ phương trình Bài viết này khám phá lịch sử của phương pháp Newton cùng với các kết quả liên quan đến tính chất định tính của nó Mặc dù các chứng minh liên quan rất phức tạp và không phải là mục tiêu chính của luận văn, chúng tôi vẫn đề cập đến những đóng góp của Newton, Raphson và Viéte trong việc phát triển phương pháp giải phương trình đại số, cũng như sự mở rộng của Kantorovich trong việc áp dụng phương pháp này cho các phương trình toán tử phi tuyến trong không gian Banach.