Tài liệu (Luận văn thạc sĩ) Về phương pháp Newton

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- ĐINH THỊ HIỀN VỀ PHƯƠNG PHÁP NEWTON LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- ĐINH THỊ HIỀN VỀ PHƯƠNG PHÁP NEWTON Chuyên ngành: Toán ứng dụng Mã số : 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Đinh Nho Hào THÁI NGUYÊN - 2019 i Mục lục Lời cảm ơn iii Mở đầu 1 1 Các khái niệm cơ bản về giải tích hàm 3 1.1. Không gian Euclide . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Không gian Banach và toán tử liên tục . . . . . . . . . . . 4 1.2.1. Không gian Banach . . . . . . . . . . . . . . . . . . 4 1.2.2. Toán tử tuyến tính liên tục . . . . . . . . . . . . . 5 1.3. Đạo hàm theo nghĩa Fréchet . . . . . . . . . . . . . . . . . 6 2 Lịch sử phương pháp Newton 8 2.1. Phương pháp Newton . . . . . . . . . . . . . . . . . . . . . 8 2.1.1. Phương pháp Viète . . . . . . . . . . . . . . . . . . 9 2.1.2. Phương pháp dây cung . . . . . . . . . . . . . . . . 11 2.1.3. Phương pháp Newton- Công thức đầu tiên . . . . . 13 2.1.4. 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 . . . . . . . . . . . . . . . . . . 16 2.2. Phương pháp Newton trong không gian hữu hạn chiều . . 17 2.2.1. Trường hợp một biến . . . . . . . . . . . . . . . . . 17 2.2.2. Trường hợp nhiều biến . . . . . . . . . . . . . . . . 18 3 Phương pháp Newton- Kantorovich 20 ii 3.1. Kết quả hội tụ cho phương trình trơn . . . . . . . . . . . . 21 3.2. Sai số ước lượng cho phương pháp Newton . . . . . . . . . 27 3.3. Sự hội tụ đơn điệu . . . . . . . . . . . . . . . . . . . . . . 29 3.4. 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 . . . . . . . . 34 3.6. Phương pháp Newton liên tục . . . . . . . . . . . . . . . . 36 3.7. Phương pháp Newton cho phương trình không trơn . . . . 38 3.8. Sự hội tụ và phân kì của phương pháp Newton . . . . . . . 39 3.9. Phân tích sai số 40 . . . . . . . . . . . . . . . . . . . . . . . Kết luận 43 Tài liệu tham khảo 44 iii Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS.TSKH. Đinh Nho Hào. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Đồng thời tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học Toán K11C (khóa 2017-2019), cảm ơn gia đình bạn bè đã động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập. 1 Mở đầu Isaac Newton (1642 − 1727) là một nhà vật lý, nhà thiên văn học, nhà triết học tự nhiên và nhà toán học vĩ đại người Anh. Ông đã xây dựng một công thức giải phương trình phi tuyến f (x) = 0 viết năm 1671 và được công bố lần đầu tiên vào năm 1685. Newton tính toán một chuỗi các đa thức sau đó ông đưa đến một nghiệm xấp xỉ của phương trình. Joseph Raphson (1648−1715) đã coi phương pháp của Newton hoàn toàn như là một phương pháp đại số và giới hạn việc sử dụng nó cho các đa thức một biến. Tuy nhiên Raphson đã mô tả phương pháp thông qua dãy các xấp xỉ kế tiếp thay vì các chuỗi đa thức phức tạp như Newton. Cách giải thích của Raphson được xem như là đơn giản hơn của Newton và đã được ông công bố vào năm 1690. Ngày nay chúng ta gọi là phương pháp Newton (hay phương pháp Newton – Raphson) tìm nghiệm xấp xỉ của phương trình phi tuyến f (x) = 0 bằng việc xây dựng một dãy lặp hội tụ tới nghiệm của phương trình. Phương pháp Newton – Raphson đóng vai trò quan trọng trong khoa học và kĩ thuật, đặc biệt đối với ngành Toán học nói chung và phương pháp số nói riêng. Trong thực tế nó có khả năng ứng dụng rất lớn. Sau khi phương pháp Newton – Raphson ra đời, việc giải phương trình phi tuyến phát triển rất mạnh mẽ và có ứng dụng trong nhiều lĩnh vực. Giải các bài toán có ý nghĩa thực tế quan trọng, đặc biệt trong giai đoạn hiện nay với sự hỗ trợ của máy tính điện tử việc này càng trở nên có hiệu lực. Điều đó đã thu hút nhiều nhà khoa học tìm hiểu sâu hơn về phương 2 pháp này. Dựa trên cơ sở của phương pháp Newton – Raphson đã có, rất nhiều bài báo được đăng trên các tạp chí nổi tiếng thế giới nói về cách xây dựng những phương pháp cải tiến giải xấp xỉ phương trình phi tuyến với tốc độ hội tụ cao, có thể thực hiện trên máy tính điện tử. Luận văn bao gồm phần mở đầu, ba chương, kết luận và danh mục các tài liệu tham khảo. 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" Chương 3 " Phương pháp Newton Kantorovich". 3 Chương 1 Các khái niệm cơ bản về giải tích hàm 1.1. Không gian Euclide Định nghĩa 1.1 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 1. < x, y >=< y, x >, 2. < x + y, z >=< x, z > + < y, z >, 3. < λx, y >= λ < x, y >, 4. < x, x >≥ 0 ∀x ∈ E và < x, x >= 0 ⇔ x = 0. Định nghĩa 1.2 Không gian vectơ E trên trường số thực R được gọi là không gian vectơ Euclide nếu trên E có một tích vô hướng. 4 Định nghĩa 1.3 Độ dài của một vectơ x của không gian vectơ Euclide E với tích vô hướng <, > được xác định bởi: 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: < x, y > cos ϕ = kxkkyk 1.2. Không gian Banach và toán tử liên tục 1.2.1. 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) cùng 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 đề sau: 1. (∀x ∈ X) kxk ≥ 0, kxk = 0 ⇔ x = θ (ký hiệu phần tử không là θ); 2. (∀x ∈ X) , (∀α ∈ P ), kαxk = |α|.kxk; 3. (∀x, y ∈ X) kx + yk ≤ kxk + kyk. Số kxk gọi là chuẩn của vectơ x . Ta cũng kí hiệu không gian định chuẩn là X. Các tiên đề (1), (2), (3) được gọi là hệ tiên đề chuẩn. Định nghĩa 1.6 (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 kxn − xk = 0 Kí hiệu lim xn = x hay xn → x khi n→∞ n→∞ n→∞ 5 Định nghĩa 1.7 (Dãy cơ bản) Dãy {xn } trong không gian định chuẩn X được gọi là dãy cơ bản nếu lim kxn − xm k = 0. n,m→∞ Đị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ụ. Ví dụ 1.1 Xét không gian véc tơ k - chiều Rk , vớiqmỗi x ∈ Rk , x = (x1 , x2 , . . . , xk )trong Pk 2 đó xi ∈ R, i = 1, 2, . . . , k. Đặt kxk = i=1 |xi | . Khi đó Rk là không gian Banach. Ví dụ 1.2 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] |xt |. Khi đó C[a,b] là không gian Banach. 1.2.2. 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 1. (∀x, y ∈ X)A(x + y) = A(x) + A(y); 2. (∀x ∈ X)(∀α ∈ P )A(αx) = αA(x). Ta viết Ax thay cho A(x). Nếu X ≡ Y ta nói A là toán tử trong X. Ta kí hiệu 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. 6 Ví dụ 1.3 X ≡ Y ≡ C[a,b] , Ax(t) = Rb a K(t, s)x(s)ds, trong đó K(t, s) là hàm liên tục theo hai biến t, s trong hình vuông a ≤ t, s ≤ b. A là toán tử tuyến tính và được gọi là toán tử tích phân. Định nghĩa 1.10 (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 x0 ∈ X nếu ∀{xn } ⊂ X, xn → x0 (n → ∞)thì Axn → Ax0 (n → ∞) 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ộc X. 1.3. Đạo hàm theo nghĩa Fréchet Cho X, Y là hai không gian Banach. Toán tử f : X → Y (không nhất thiết tuyến tính) Định nghĩa 1.11 Cho x là một điểm cố định trong không gian Banach X. Toán tử f : X → Y gọi là khả vi (theo nghĩa Fréchet) tại x nếu tồn tại một toán tử tuyến tính liên tục A : X → Y sao cho f (x + h) − f (x) = A(h) + φ(x, h), (∀h ∈ X) kφ(x,h)k khk→0 khk và lim kf (x+h)−f (x)−A(h)k khk khk→0 = 0 (hay tương đương lim = 0). A(h) gọi là vi phân cấp một của toán tử f tại x. Ký kiệu là df (x, h).Toán tử A gọi là đạo hàm cấp một (theo nghĩa Fréchet) của f tại x. Kiệu là: f 0 (x). Vậy df (x, h) = f 0 (x).h Định lí 1.1 Nếu đạo hàm F tồn tại, nó là duy nhất. 7 Định lí 1.2 Nếu một toán tử được xác định trên một tập con mở của một không gian Banach là khả vi Fréchet tại một điểm, thì nó liên tục tại điểm đó. Định lí 1.3 Một toán tử tuyến tính A từ một không gian Banach vào một không gian Banach là khả vi Fréchet nếu và chỉ nếu A là bị chặn. Trong trường hợp đó, A0 ≡ A. Định nghĩa 1.12 (Đạo hàm Fréchet cấp hai ) Nếu A : B1 → B2 là khả vi Fréchet trên một tập mở Ω ⊂ B1 và A0 là khả vi Fréchet tại x ∈ Ω, thì A được gọi là khả vi Fréchet cấp hai tại x. Đạo hàm Fréchet của A0 tại x được gọi là đạo hàm Fréchet cấp hai của A và được kí hiệu là A00 (x). 8 Chương 2 Lịch sử phương pháp Newton 2.1. Phương pháp Newton Mục này trình bày lịch sử phát triển của phương pháp Newton- Raphson để giải các phương trình đại số phi tuyến thông qua các ấn phẩm, thư từ và bản thảo còn sót lại của Isaac Newton, Joseph Raphson và Thomas Simpson. Sự khác nhau giữa công thức Newton với quy trình lặp của Raphson được nêu ra, khẳng định Simpson là người đầu tiên đưa ra một công thức chung, về tính toán vi phân, áp dụng cho các phương trình phi đa thức. Việc mở rộng phương pháp của Simpson cho các hệ phương trình được trưng bày. Thuật toán lặp xk+1 = xk − f (xk ) f 0 (xk ) (2.1) để giải phương trình đại số phi tuyến f (x) = 0 thường được gọi là phương pháp Newton. Đôi khi nó được gọi là phương pháp Newton-Raphson. Phương pháp (2.1) được áp dụng để giải hệ phương trình phi tuyến, tạo thành cơ sở cho hầu hết các kỹ thuật thường được sử dụng để giải các phương trình đại số phi tuyến. Phần sau chúng tôi chỉ ra rằng các phương pháp có thể được xem như 9 thay thế biểu thức f 0 (xk ) trong (2.1) bởi một xấp xỉ sai phân dạng f 0 (xk ) ≈ h−1 k [f (xk + hk ) − f (xk )] (2.2) và cũng là phương pháp cát tuyến, trong đó f 0 (xi ) ≈ f (xk ) − f (xk−1 ) , xk − xk−1 (2.3) là tiền thân của phương pháp (2.1) . Từ quan điểm hiện đại, các phương pháp được mô tả bởi (2.1)–(2.3) phát sinh tự nhiên từ sự tuyến tính hóa của phương trình f (x) = 0. Chúng ta xem xét bản trình bày gốc của Newton về phương pháp của ông, tương phản với phương pháp hiện tại (2.1) và với công thức lặp của Raphson cho các phương trình đa thức. Không có bằng chứng rõ ràng rằng Newton đã sử dụng bất kỳ phép tính vi phân nào trong việc tìm ra phương pháp của mình, mặc dù trong Principia Mathematica, Newton áp dụng kỹ thuật của mình trong cách lặp cho phương trình phi đa thức. Công thức tổng quát của Simpson cho phương trình phi tuyến về mặt tính toán vi phân được trình bày trong phần sau, và chúng ta thảo luận về phần mở rộng của Simpson của quá trình cho các hệ phương trình phi tuyến. 2.1.1. Phương pháp Viète Vào cuối năm 1664, ngay sau khi chuyển sang quan tâm đến toán học, Isaac Newton đã được làm quen với công trình của nhà đại số học người Pháp Francois Viète (1540 − 1603) (thường được gọi là "Vieta"). Công trình của Viète liên quan đến nghiệm số của phương trình đại số phi tuyến, De numerosa potestatum, xuất bản ở Paris năm 1600, sau đó được tái bản trong tuyển tập các tác phẩm của Viète Francisci Vietae Opera Mathematica do Frans van Schooten ở Leiden sắp xếp và xuất bản 10 vào năm 1646. William Oughtred đã tóm tắt, đơn giản hóa và bổ sung một số tài liệu và xuất bản trong các phiên bản khác nhau của Clavis Mathematicae của từ năm 1647 trở đi. Mới đây bản dịch của tác phẩm liên quan, bao gồm tiểu sử của Viète. Newton đã truy cập vào cả bộ sưu tập của Schooten và ấn bản Latin thứ ba của cuốn sách của Oughtred xuất bản ở Oxford năm 1652 và đã ghi chép rất cẩn thận các kết quả này. Những ghi chép này là dấu hiệu đầu tiên của Newton quan tâm đến nghiệm số của phương trình phi tuyến. Viète hạn chế sự chú ý của mình vào các phương trình đa thức monic. Trong ký hiệu hàm số hiện đại, chúng ta có thể viết các phương trình của Viète dưới dạng p(x) = N (2.4) Trong đó, hằng số N xuất hiện bên phải của phương trình. Kỹ thuật Viète có thể được đánh giá là mang lại các chữ số sau dấu phẩy của nghiệm x∗ của (2.4) như sau. Cho các chữ số thập phân có nghĩa liên tiếp của x∗ là a0 , a1 , a2 , . . ., nghĩa là x∗ = a0 10k + a1 10k−1 + a2 10k−2 + · · · , và cho ước lượng thứ i của x∗ được cho bởi xi = a0 10k + a1 10k−1 + · · · + ai 10k−i . Giả sử xi cho trước, ta có xi+1 = xi + ai+1 10k−(i+1) , kỹ thuật lượng Viète để tính toán ai+1 như phần nguyên của N − 5(p(xi + 10k−i−1 ) + p(xi )) , p(xi + 10k−i−1 ) − p(xi ) − 10(k−i−1)n (2.5) Trong đó n là bậc của đa thức. Đôi khi đại lượng 5(p(xi +10k−i−1 )+p(xi )) trong tử số của (2.5) được thay thế bằng giá trị của p(xi ) Số nguyên ai+l trên thực tế có thể âm hoặc có một vài chữ số sau dấu phẩy, do đó cho phép hiệu chỉnh hoặc sớm hơn ước lượng 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 −5(f (xi + 10k−i−1 ) + f (xi )) , f (xi + 10k−i−1 ) − f (xi ) − 10(k−i−1)n 11 Do đó, phương pháp Viète gần như tương đương với   f (x ) i xi+1 = xi − 10k−i−1 . f (xi + 10k−i−1 ) − f (xi ) Điều này gần giống với biểu thức được tạo ra bằng cách thay thế (2.2) vào (2.1) với hi = 10k−i−1 . Theo nghĩa này, phương pháp của Viète là tiền thân hoặc sơ đồ sai phân hữu hạn của (2.1)–(2.2), thường được trình bày dưới dạng sửa đổi hoặc (2.1). Phép trừ của biểu thức 10(k−i−1)n trong mẫu số của (2.5) có thể giải thích trong trường hợp p(x) = xn bằng cách xem xét khai triển nhị thức của (xi + 10k−i−1 )n ; cho phương trình bậc hai monic kết quả phương pháp chính xác với phương pháp Newton-Raphson (2.1), nhưng trong thực tế thành phần này không đáng kể và thường được bỏ qua. Một so sánh thú vị giữa kỹ thuật này và phương pháp NewtonRaphson cho trường hợp p(x) = xn được đưa ra trong phần sau. Kỹ thuật này là được sử dụng rộng rãi cho đến khi được thay thế bằng phương pháp Newton-Raphson. 2.1.2. Phương pháp dây cung Trong bộ sưu tập các bản thảo chưa được công bố có tên là "Newton’s Waste Book" ([21, I, tr 489−−491 khoảng từ đầu năm 1665) kỹ thuật lặp mà chúng ta có thể xác định là "phương pháp dây cung" để giải phương trình phi tuyến. Trong ký hiệu hiện đại, phương pháp này để giải phương trình f (x) = 0 là phương trình (2.1) với f 0 (xk ) thay thế bởi (2.3) đó là:  f (xk ) − f (xk−1 )  . xk+1 = xk − f (xk )/ xk − xk−1 (2.6) Một cuộc thảo luận lịch sử thú vị về phương pháp này và mối quan hệ của nó có liên quan chặt chẽ tới phương pháp được gọi là Regula Falsi của Maas. Một số khác nhau các số đối, tất cả từ phối cảnh hiện đại về bản chất dựa trên tuyến tính hóa cơ bản hàm f (x), mang lại kỹ thuật này. Cách tiếp cận dựa trên hình dưới đây phù hợp với tính toán của 12 Newton. Trong cả hai trường hợp được hiển thị trong hình vẽ, chúng tôi lưu ý rằng, bằng sự tương tự của các tam giác được kí hiệu , a/b = c/d, đó là (f (xi ) − f (xi−1 ))/(xi − xi−1 ) = ∓f (xi )/d; vậy với d ≈ ∓(x∗ − xi ), chúng ta có được (với sự lựa chọn dấu hiệu thích hợp trong từng trường hợp) công thức (2.6) cho xi+1 ≈ x∗ 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 13 f (x) := x3 − 0, 2x2 − 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) = 3x2 − 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 = x3n − 0, 2x2n − 0, 2xn − 1, 2, ta có fn (1, 5 − xn ). xn+1 = xn − 1, 425 − fn Do x3 = 1, 198,f (x3 ) ' −0, 0072 và f 00 (x) ≥ 3 × 1, 1982 − 0, 4 × 1, 5 − 0, 2 ' 3, 49 ta có ước lượng 0 < ξ − x3 < 0,0072 3,49 ' 0, 002. Nghiệm đúng ξ = 1, 2. 2.1.3. Phương pháp Newton- Công thức đầu tiên Trong tác phẩm De analysi per aequationes nurnero terminorurn infinitas của Newton, có lẽ xuất bản vào giữa năm 1669, một số ý tưởng về vô cùng nhỏ, hay phép tính vi phân đã được đề cập. Đoạn trích từ cuốn sách, trong bản dịch sang tiếng Anh của cuốn sách này là cuộc thảo luận đầu tiên của Newton về những gì chúng ta có thể nhận ra như là một ví dụ của phương pháp Newton, mặc dù công thức khác biệt đáng kể so với dạng thông thường bây giờ, các tính toán cũng dài dòng hơn nhiều so với công thức hiện đại và phương pháp chỉ được đưa ra trong phạm vi giải phương trình đa thức. Không có Toán giải tích nào được sử dụng trong bài thuyết trình cũng như tham chiếu đến đạo hàm cho thấy rằng phương pháp Newton này hoàn toàn là một phương pháp đại số. Trong một số các trường hợp khác, Newton được biết là đã sử dụng các phương pháp và ký hiệu truyền thống hơn trong nỗ lực để làm cho ý 14 tưởng của ông ấy dễ tiếp cận hơn cho nhiều đối tượng, nhưng không có bằng chứng rõ ràng nào về thời gian đó, ông nhận thấy kỹ thuật đặc biệt này là một ứng dụng của phép tính hoặc bắt nguồn từ nó sử dụng các kĩ thuật tính toán. Kĩ thuật Newton có thể được mô tả trong kí hiệu hàm số hiện đại như sau. Đặt x0 là ước lượng ban đầu của nghiệm x∗ của f (x) = 0. Viết P g0 (x) = f (x), và giả sử g0 (x) = ni=0 ai xi . Viết e0 = x∗ − x0 chúng ta thu được bằng cách mở rộng nhị thức về x0 cho trước một phương trình đa thức mới trong biến e0 : 0 = g0 (x∗ ) = g0 (x0 +e0 ) = n X i=0 X  i   n X i j i−j x0 e0 = g1 (e0 ). ai (x0 +e0 ) = ai j j=0 i=0 i (2.7) Bỏ qua các thuật ngữ liên quan đến bậc cao hơn của e0 (tuyến tính hóa hiệu quả tính toán rõ ràng đa thức g1 ) tạo ra X  X  n n n X i i−1 i i−1 0 = g1 (e0 ) ≈ ai [x0 + ix0 e0 ] = ai x0 + e0 ai ix0 i=0 i=0 i=0 Từ đó, chúng ta suy luận rằng  X  X n n i−1 i ai ix0 e0 ≈ c0 = − ai x0 i=0 i=0 Và đặt x1 = x0 + c0 . Chính thức, chỉnh sửa này có thể viết c0 = −g0 (x0 )/g00 (x0 ) = −f (x0 )/f 0 (x0 ). Bây giờ lặp lại quá trình, nhưng thay vì mở rộng đa thức ban đầu g0 về x1 bằng cách mở rộng đa thức g1 thu được một cách rõ ràng trong (2.7) về điểm c0 , tức là c0 được coi là ước lượng đầu tiên của nghiệm e0 của phương trình mới g1 (x) = 0. Do đó, tương tự ta thu được 0 = g1 (e0 ) = g1 (c0 + e1 ) = g2 (e1 ), trong đó đa thức g2 là tính toán rõ ràng. Tuyến tính hóa lại tạo ra như trên một hiệu chỉnh chính thức tương đương với e1 ≈ c1 = −g1 (c0 )/g10 (c0 ), tương ứng với c1 = −g0 (x0 + c0 )/g00 (x0 + c0 ) = 15 −f (x1 )/f 0 (x1 ) và x2 = x1 + c1 . Quá trình tiếp tục bằng cách mở rộng g2 về c1 và v. . .v. . .. Qua trình mô tả bởi Newton đòi hỏi sự tính toán tường minh của các đa thức kế tiếp g1 , g2 , . . ., điều này khá là tốn công sức. Rõ ràng tính toán không được sử dụng trong bài thuyết trình của ông, mà nó hoàn toàn dựa trên việc duy trì giới hạn bậc thấp nhất trong một nhị thức mở rộng. Cũng lưu ý rằng ước lượng cuối cùng của x∗ chỉ được tính ở cuối quá trình là x∗ = x0 + c0 + c1 + · · · thay vì ước lượng liên tiếp xi được cập nhật và sử dụng liên tiếp . Rõ ràng quá trình này khác biệt đáng kể so với kỹ thuật lặp hiện đang sử dụng. Cuốn sách này gợi ý rằng Newton đã nhận thức được sự hội tụ bậc hai của kỹ thuật như đặc trưng bởi sự nhân đôi gần đúng của số các chữ số có nghĩa chính xác trong các bước kế tiếp: quan sát thấy rằng số các chữ số được Newton giữ lại trong các bước nhân đôi liên tiếp. 2.1.4. Các phương pháp khác cho phương trình phi tuyến Newton đã gửi hai bức thư đến địa chỉ John Smith, ngày 24 tháng 7 và ngày 7 tháng 8 năm 1675. Smith đã chuẩn bị một bảng gồm các hình vuông, hình lập phương, và căn bốn của toàn bộ số nguyên từ 1 đến 10000; trong bức thư ngày 8 tháng 5 năm 1675 Newton đề nghị rằng ông ấy làm điều này bằng cách chỉ tính duy nhất căn của mỗi số nguyên thứ một trăm đến số đủ của chữ số (10), sau đó là phép nội suy để tạo ra toàn bộ số lượng muốn có đòi hỏi khác đến độ chính xác đòi hỏi ( 8 chữ số ). Newton đã trình bày trong các bức thư của ông ấy gởi cho Smith vài sơ đồ, chúng tôi có thể tổng hợp như x1 = (1/n)[(n − 1)x0 + a/xn−1 0 ], n = 2, 3, 4, Ở đây Newton đang giải phương trình xn − A = 0, cho n = 2, 3, 4 bắt đầu từ ước lượng ban đầu x0 = B và viết C = A − B n = a − xn0 . Trong