Các vòng lặp thường được sử dụng trong các chương trình tính toán kết quả số bằng cách bắt đầu với một câu trả lời gần đúng và lặp đi lặp lại việc cải thiện nó Show
better = 1/2 * (approx + n/approx) Việc triển khai phương pháp Newton sau đây yêu cầu hai tham số
Chạy Save Load Show trong Codelens (chp07_newtonsdef)
Việc triển khai này, được hiển thị trong codelens, sử dụng điều kiện Ghi chú Câu lệnh Phương pháp Newton để tìm nghiệm số của một phương trình còn được gọi là phương pháp Newton-Raphson. Gần đây, tôi đã tự hỏi làm thế nào để giải thích tốt nhất thuật toán số thú vị này Ở đây tôi đã thu thập một vài bước minh họa cho thấy rõ phương pháp của Newton hoạt động như thế nào, nó có thể làm tốt những gì, và nó thất bại ở đâu và như thế nào. Bạn cũng sẽ tìm thấy một số đoạn mã trong ngôn ngữ lập trình python để giúp bạn tự thử nội dung này Trước khi tôi chuyển sang mã python, tôi sẽ chỉ cho bạn chi tiết những gì nó đã tạo ra để giúp tôi chứng minh rõ hơn, phương pháp của Newton hoạt động như thế nào. Tôi sử dụng một hàm ví dụ cụ thể bên dưới để minh họa và điều tra, nhưng nếu bạn quan tâm đến các ví dụ hơn là những điều cơ bản, hãy xem ngay bài viết của tôi Các ví dụ mang tính hướng dẫn cao cho Phương pháp Newton Raphson Sẵn sàng? Ở đây bạn sẽ tìm hiểu thêm về Một tình huống điển hình để sử dụng phương pháp của Newton trongGiả sử bạn có một phương trình trước mặt. Ai đó đã đưa nó cho bạn để giải quyết hoặc bạn tự tìm thấy nó trong một mô hình tuyệt vời cho một số hiện tượng mà bạn đang điều tra (như trong nghiên cứu trí tuệ nhân tạo của bạn, hoặc một cái gì đó tương tự). Hãy chọn một ví dụ, như \[\sin (x^2)-x^3=1\]Không quan trọng nó đến từ đâu và thậm chí không quan trọng phương trình trông phức tạp như thế nào. Phương trình này có cấu trúc khá đơn giản, nhưng nó đủ phức tạp. Hãy đồng ý không thử và giải quyết nó một cách chính xác Chà, trên thực tế, điều đó không quan trọng, phương trình phức tạp đến mức nào. Điều quan trọng duy nhất là bạn biết dạng của nó và về cơ bản bạn có các giá trị số cho tất cả các tham số trong phương trình Ý nghĩa của các giá trị số cho các tham số trong phương trình là gì? . Tuy nhiên, hãy tưởng tượng rằng phương trình trên ban đầu sẽ trông như thế này \[\sin (a x^2)-b x^3=1\]Sau đó, chúng ta sẽ cần biết các giá trị số cụ thể cho các tham số \(a\) và \(b\) để có thể áp dụng phương pháp của Newton. Nếu chúng ta không thể đặt các tham số này thành các giá trị số, chúng ta phải chọn một số để sử dụng phương pháp. Vì vậy, trong trường hợp của chúng ta, chúng ta có thể chọn \(a =1\) và \(b =1\) và đi đến dạng trên của phương trình. Điều này dẫn chúng ta đến Điều kiện tiên quyết để sử dụng phương pháp NewtonVì vậy, chúng ta có một phương trình để giải quyết. Chúng ta cần đảm bảo rằng biến duy nhất trong phương trình là biến mà chúng ta muốn biết một giải pháp cho. Tất cả các biến khác (hoặc tham số, trong trường hợp này), phải nhận các giá trị số. Nếu cần, chúng tôi đặt chúng thành các giá trị ví dụ. Khi kết thúc quy trình như vậy, chúng tôi sẽ nhận được một biểu mẫu tương tự như ví dụ của chúng tôi, đó là \[\sin (x^2)-x^3=1\]Có một điều kiện tiên quyết khác, cụ thể là chúng ta đang xử lý các số thực trong phương trình. Điều này áp dụng cho các tham số và hệ số, cũng như cho chính biến \(x\). Phương pháp của Newton không thể tìm ra các nghiệm có giá trị phức cho một phương trình như vậy. Các ví dụ sẽ hiển thị một cách hoàn hảo và trực quan, tại sao lại như vậy Có hai điều nữa chúng ta cần có thể làm khi sử dụng phương thức. một là tính đạo hàm và hai là tìm các điểm hợp lý để hàm bắt đầu tìm nghiệm trong lân cận của các điểm này. Hai yêu cầu này trở nên rõ ràng ngay khi chúng ta bắt đầu sử dụng phương pháp của Newton và chúng ta sẽ sớm làm được điều đó. Nhưng trước khi thực hiện, chúng ta cần hiểu sơ lược về chức năng của phương thức này Phương pháp Newton-Raphson như một thủ tục lặp đi lặp lạiPhương pháp của Newton là một quy trình từng bước một. Cụ thể, một tập hợp các bước được lặp đi lặp lại nhiều lần, cho đến khi chúng tôi hài lòng với kết quả hoặc quyết định rằng phương pháp đó đã thất bại. Sự lặp lại như vậy trong một thủ tục toán học hoặc một thuật toán được gọi là phép lặp. Vì vậy, chúng tôi lặp lại (i. e. lặp lại cho đến khi chúng tôi hoàn thành) ý tưởng sau Đưa ra bất kỳ phương trình trong một biến thực để giải quyết, chúng tôi làm như sau
Điều đó hơi nhanh, vì vậy hãy để tôi thực hiện lại các bước này một lần nữa, nhưng chậm hơn Biến đổi phương trình cần giải thành một hàm, có các số 0 mà phương pháp của Newton sẽ tìm thấyGiả sử chúng ta có một phương trình để giải. Vâng, giống như ở trên, vì vậy đây là một lần nữa \[\sin (x^2)-x^3=1\]Nguyên tắc của phương pháp là tìm các số 0 trong một hàm. Vì vậy, để sử dụng nguyên tắc đó, chúng ta phải viết lại phương trình dưới dạng một hàm mà chúng ta muốn bằng 0. Điều đó khá đơn giản trong bất kỳ phương trình nào. tất cả những gì cần làm là đưa mọi thứ trong phương trình sang một bên. Trong trường hợp của chúng ta, hãy sử dụng vế trái của phương trình và biểu thị hàm bằng chữ \(f\). Sau đó chúng tôi có \[f(x)=\sin (x^2)-x^3-1\]và phương trình bây giờ được thể hiện dưới dạng \(f(x)\) như \[f(x)=0\]Càng xa càng tốt. Bây giờ, làm thế nào chúng ta có thể tìm thấy giải pháp cho phương trình này? . Bằng cách tìm nghiệm (số 0) của \(f(x)\). Ok, làm thế nào để chúng ta làm điều đó? Trước khi bắt đầu phương pháp Newton. có được một ý tưởng về chức năng trông như thế nàoĐiều đầu tiên cần làm là cố gắng vẽ đồ thị của hàm và nhìn vào nó. Ví dụ của chúng tôi trông như thế này \(f(x)\) được thể hiện bằng đường cong màu xanh. Đường màu đen là số không
Vậy điều này giúp ích như thế nào? . Chúng ta cũng có thể thấy rằng nó dường như có một gốc. Đánh giá từ hành vi tiệm cận của cả sin và phần khối, chúng ta có thể nói ngay rằng đây có thể là nghiệm duy nhất của hàm của chúng ta Hơn nữa, chúng ta thấy rằng gốc này nằm đâu đó giữa \(-1\) và \(-0. 5\), nhưng giá trị bằng số chính xác của gốc này rất khó đọc trên biểu đồ. Tuy nhiên, điều đó đã đủ tốt để bắt đầu phương pháp của Newton để tìm ra giá trị chính xác hơn cho giải pháp. Chúng tôi đã nhìn thấy một con số không và chúng tôi ít nhiều biết nó ở đâu Trước khi chúng tôi tiếp tục, một lời cảnh báo. khi chức năng rõ ràng không hoạt động tốt như trong ví dụ của chúng tôi, kiểm tra trực quan thực sự có thể gây hiểu nhầm. Thật không may, tôi đã thấy thậm chí một số nhà khoa học đồng nghiệp của tôi tranh luận điều gì đó dựa trên biểu đồ, điều này sẽ cần một số loại sao lưu hoặc bằng chứng. Trong trường hợp của chúng tôi, chúng tôi biết rằng mọi thứ đều ổn vì chúng tôi biết dạng chức năng của \(f(x)\) và cách các phần của nó hoạt động. Vì vậy, nếu đó không phải là trường hợp, tiến hành thận trọng Tìm điểm bắt đầu \(x_0\) cho phương pháp Newton-RaphsonTrong ví dụ của chúng ta, chúng ta có thể vẽ đồ thị hàm của mình một cách thuận tiện, nhìn vào biểu đồ và chọn một giá trị cho \(x_0\). Tuy nhiên, điều đó có thể khó khăn hơn nhiều trong thực tế. Vì vậy, điều quan trọng để nhận được giá trị tốt đầu tiên cho \(x_0\) là gì? Trước hết, nó phải gần với gốc thực tế. Gần gốc sẽ hữu ích, bởi vì nói chung điều đó là đủ để đảm bảo rằng phương pháp hội tụ một kết quả tốt. Như chúng ta sẽ thấy bên dưới, những điều kỳ lạ có thể xảy ra nếu \(x_0\) được chọn sai Nhưng nếu không dễ để có được một đồ thị đủ tốt của \(f\), chẳng hạn vì mỗi giá trị của hàm này được tính toán bằng số và mất hai ngày để tạo ra, thì người ta chỉ có thể sử dụng bất kỳ giá trị nào làm điểm bắt đầu. Chỉ cần chuẩn bị sẵn một số đối số về lý do tại sao bạn mong đợi chức năng của mình hoạt động tốt. Hoặc, có một ý tưởng/ước tính cho chức năng của bạn về những gì nó nên làm và ở đâu Trong ví dụ của chúng ta, để biết điều gì xảy ra trong quá trình lặp lại phương pháp Newton, tôi khuyên chúng ta nên sử dụng \(x_0=-1. 5\) để thành công nhanh chóng và dễ dàng. Mặt khác, \(x_0=+1\) sẽ không phải là một ý kiến hay. Đây là hai điểm được đánh dấu trên biểu đồ hàm của chúng tôi dưới dạng các ngôi sao màu đỏ Tại sao một trong số chúng hoạt động tốt hơn cái kia và tại sao vấn đề gần với số 0 thực tế sẽ rõ ràng hơn trong bước sau. Nếu bạn cần thêm trợ giúp về cách tìm các giá trị ban đầu tốt cho phương pháp của Newton, vui lòng đọc bài viết của tôi Cách tìm giá trị ban đầu trong phương pháp của Newton Xây dựng tiếp tuyến của hàm cho bước phương pháp Newton tiếp theoĐây là bước phức tạp nhất trong toàn bộ quy trình. Nhưng thật ra nó cũng không phức tạp lắm. Nếu bạn có thước kẻ và bút chì, bạn có thể làm điều đó cho cả hai điểm trên hình trên trong vòng vài giây. Vì vậy, chúng ta phải làm gì về mặt số? Cấu trúc mà chúng ta đang tìm kiếm là một hàm tuyến tính \(y(x)\) tiếp xúc với hàm \(f(x)\) của chúng ta tại điểm \(x_0\) và có cùng hệ số góc với \(f(x) . Biểu thị đạo hàm của \(f(x)\) đối với biến \(x\) theo một số nguyên tố, chúng ta có thể viết độ dốc này là \[f'(x_0)\]Bây giờ, bất kỳ hàm tuyến tính nào cũng có thể được viết ở dạng thông thường \[y(x)=k x+d\] trong đó \(k\) và \(d\) là hằng số/tham số. Vì ta muốn \(y(x)\) sao cho hệ số góc của nó bằng \(f'(x_0)\), ta biết ngay rằng \[k = f'(x_0)\] Và bởi vì chúng ta cũng muốn các hàm bằng nhau tại \(x_0\), nên chúng ta biết rằng \(y(x_0)=f(x_0)\) và như vậy \[k x_0+d =f(x_0)\quad\rightarrow\quad d=f(x_0)-k x_0=f(x_0)-f'(x_0) x_0 \] Vì vậy, với thông tin này, chúng ta có thể tiếp tục và vẽ tiếp tuyến của hàm tại điểm \(x_0\), nếu chúng ta biết các giá trị \(f(x_0)\) và \(f'(x_0)\). Nhưng làm cách nào để tính đạo hàm của hàm? Thành thật mà nói, điều đó phụ thuộc vào cách bạn biết chức năng của mình. Trong trường hợp của chúng ta, nó đơn giản theo nghĩa là chúng ta biết dạng hàm của \(f(x)\) theo cách mà chúng ta có thể tính đạo hàm một cách chính thức. Nhưng nói chung là không có gì sai sót cả e ạ. g. , sử dụng đạo hàm số thay thế. Hãy giữ cho nó đơn giản, mặc dù. Lấy đạo hàm theo quy tắc giải tích ta được \[f'(x)=2x \cos (x^2)-3x^2\]Sử dụng công thức này, chúng ta có thể tính toán và vẽ bất kỳ tiếp tuyến nào với đường cong của chúng ta (i. e. , tiếp tuyến tại bất kỳ điểm nào trên đường cong của chúng ta). Đây là chức năng của chúng tôi một lần nữa với hai điểm và các tiếp tuyến tương ứng Các tiếp tuyến hiện cho chúng ta thấy bước tiếp theo. tìm giao điểm của chúng với số không. Trong trường hợp của chúng tôi, người ta có thể thấy rằng một trong số chúng (đối với điểm bên trái tại \(-1. 5\) tiến gần đến số 0 thực hơn so với số còn lại). Tuy nhiên, đây không phải là lý do duy nhất khiến điểm bên trái là giá trị khởi đầu tốt hơn. Lần lặp lại tiếp theo sẽ cho chúng ta thấy lý do tại sao lại như vậy, nhưng trước khi đến đó, chúng ta cần tính toán phần kế tiếp của \(x_0\), \(x_1\) Cắt tiếp tuyến với 0 để tìm bước tiếp theo trong phương pháp NewtonGiao điểm của một hàm tuyến tính với số 0 rất dễ tính toán. Cho rằng \[y(x)=k x+d\] tất cả những gì chúng ta cần làm là đặt \(y=0\) và nhận \[0=k x+d\] có nghĩa là chúng tôi tìm thấy phần kế tiếp của \(x_0\), bằng cách thay thế từ trên cho \(k\) và \(d\), làm nghiệm của phương trình \[0= f'(x_0) x+f(x_0)-f'(x_0) x_0\] đó là \[x_1= x_0 – \frac{f(x_0)}{f'(x_0)} \] Lưu ý rằng chúng tôi cần \(f'(x_0)\ne 0\) để điều này hoạt động. Nếu \(f'(x_0) = 0\), chúng ta có một phép chia cho 0, đây là một ý tưởng tồi, cả về mặt số học và phân tích Hãy vẽ những điểm này trong hình cho đường cong ví dụ của chúng ta. Các điểm hiện có thể nhìn thấy trên trục 0, nhưng chưa có trên đường cong (đó là điểm bắt đầu của bước lặp tiếp theo). Vì vậy, ở đây chúng tôi đi Tại thời điểm này, chúng ta đã đi từ dự đoán đầu tiên, \(x_0\) đến dự đoán thứ hai, \(x_1\). Ý tưởng cơ bản của phương pháp Newton là lặp lại các bước này cho đến khi chúng ta đạt đủ số 0 thực tế của hàm và \(x_i\) không thay đổi nữa với một độ chính xác nhất định. Tại mỗi bước \(i\), ta có \[x_{i+1}= x_i – \frac{f(x_i)}{f'(x_i)} \] Lặp lại cách xây dựng tiếp tuyến cho phương pháp NewtonVì vậy, tại thời điểm này, chúng tôi lặp lại những gì chúng tôi vừa làm, nhưng bắt đầu từ \(x_1\) thay vì \(x_0\). Trước tiên, tôi đã thêm tất cả các bước (màu xanh lục) vào hình và ở đây, các tiếp tuyến mới tại mỗi \(x_1\) dành cho cả hai biến thể điểm bắt đầu thử nghiệm của chúng tôi cho \(x_0\) Bây giờ, điều này trông hơi lộn xộn, mặc dù tôi đã giảm các tiếp tuyến đầu tiên (màu đỏ) thành các đường đứt nét. Những gì chúng ta quan sát được là tiếp tuyến màu lục ở phía bên trái, tiếp tuyến xuất phát từ \(x_0=-1. 5\) của phiên bản lặp lại, chỉ thay đổi một chút so với phiên bản tiền nhiệm màu đỏ của nó. Tuy nhiên, tiếp tuyến màu lục khác xuất phát từ \(x_0=1\), bị nghiêng mạnh so với tiếp tuyến màu đỏ trước đó và hiện đang thực sự chỉ ra bên ngoài hình Đây là kết quả của hàm \(f\) chạy gần như song song với trục hoành tại \(x_1\) cho điểm xuất phát thay thế này. Theo đường tăng dần yếu này, chúng ta sẽ tìm thấy ứng cử viên tiếp theo cho nghiệm nguyên hàm của chúng ta nằm ngoài vùng quan tâm. Không rõ rằng điều này sẽ dẫn đến bất kỳ loại thành công nào. Hoàn toàn ngược lại, trên thực tế. Đây là một ví dụ điển hình cho sự thất bại của phương pháp Newton-Raphson, do lựa chọn dự đoán ban đầu không tốt. Thành thật mà nói, toàn bộ quan điểm của tôi khi đưa vào dự đoán ban đầu thứ hai này là để chỉ ra chính xác điều đó. Bây giờ điều này đã hoàn thành, tôi sẽ vẽ lại hình, nhưng chỉ với điểm bắt đầu bên trái và phóng to hơn nữa. Bằng cách này, quy trình được hiển thị rõ ràng hơn nhiều Giá trị bắt đầu trên đường cong (ngôi sao màu đỏ) dẫn đến tiếp tuyến màu đỏ, xuống 0 (X màu xanh lá cây), ngược trở lại đường cong (ngôi sao màu xanh lá cây). Ngôi sao màu xanh lá cây dẫn đến tiếp tuyến màu xanh lá cây, giảm xuống 0 tại X màu vàng, vốn đã khá gần với điểm 0 của đường cong màu xanh lam, đồ thị của hàm \(f\) Chờ đợi sự hội tụ trong phương pháp Newton-RaphsonPhép lặp này tạo ra hết giá trị này đến giá trị khác, cái gọi là chuỗi \(x_i\) với \(i=0,1,2,\ldots \). Nhìn vào những điều này, chúng ta có thể quyết định liệu phương pháp của Newton có thành công trong việc tạo ra một giá trị gần đúng với nghiệm của hàm đang được nghiên cứu hay không. Hãy xem những gì xảy ra cho ví dụ của chúng tôi. Bảng bên dưới chứa giá trị của \(i\), \(x_i\), khoảng cách từ giá trị trước đó, i. e. , \(. x_i-x_{i-1}. \), và sự thay đổi tương đối, i. e. , \(. x_i-x_{i-1}. /. x_{i-1}. \) \(i\)\(x_i\)\(. x_i-x_{i-1}. \)\(. x_i-x_{i-1}. /. x_{i-1}. \)1-0. 8519501139650. 6480498860350. 4320332573562-0. 7702241495590. 0817259644070. 0959281101873-0. 7649946223000. 0052295272580. 0067896173624-0. 7649722608200. 0000223614800. 0000292308995-0. 7649722604110. 0000000004090. 0000000005356-0. 7649722604110. 0000000000000. 000000000000Rõ ràng, giá trị của \(x_i\) không còn thay đổi nhiều nữa sau \(i=5\) và cả chênh lệch tuyệt đối và tương đối ngày càng nhỏ hơn. Cái sau là thước đo tốt hơn, bởi vì chúng ta có thể quan sát một số nhỏ thay đổi theo một số nhỏ, điều này không nhất thiết phải là một thay đổi nhỏ về mặt tương đối Ngây thơ, và trong trường hợp này thực sự, bảng này có nghĩa là chúng ta có một kết quả hội tụ và có thể dừng việc lặp lại. Trong thực tế, một giá trị nhỏ nhất định được đặt cho độ chính xác mong muốn và ngay khi sự khác biệt trong \(x_i\) từ bước này sang bước tiếp theo giảm xuống dưới ngưỡng này, chúng tôi tuyên bố tìm kiếm thành công và sử dụng \(x_i Và, bây giờ chúng ta có thể tự tin tuyên bố rằng nghiệm của phương trình \[\sin (x^2)-x^3=1\]là \(x=-0. 7649723\), nếu được làm tròn đến tám chữ số Sự hội tụ trong phương pháp Newton-Raphson cho các dự đoán ban đầu khác nhauThật thú vị khi đặt câu hỏi liệu chúng ta có thể luôn đạt được kết quả hội tụ với phương pháp của Newton hay không, bất kể chúng ta đưa ra dự đoán ban đầu nào, nếu chúng ta chỉ chờ đợi đủ lâu. Tôi đã quá vội vàng hay thiếu kiên nhẫn khi loại bỏ giá trị ban đầu khác đó, chỉ vì nó không có vẻ hứa hẹn ngay lập tức? Hãy cùng tìm hiểu. Tôi để phép lặp Newton-Raphson chạy lại với dự đoán ban đầu \(x_0=1\), và đây là kết quả. Phải mất một lúc, nhưng trên thực tế, các lần lặp lại cũng tìm ra giải pháp chính xác \(i\)\(x_i\)\(. x_i-x_{i-1}. \)\(. x_i-x_{i-1}. /. x_{i-1}. \)10. 3964093993990. 6035906006010. 60359060060123. 3030616217962. 9066522223977. 33245030718432. 1607042633891. 1423573584080. 34584803107241. 3092302263930. 8514740369960. 39407245657050. 9005441394330. 4086860869600. 31215754014960. 0573827210020. 8431614184310. 93627994621379. 5619068915709. 504524170567165. 63390519924986. 5677040712132. 9942028203570. 31313867142994. 2063134485852. 3613906226280. 359545831698102. 6701094147531. 5362040338320. 365213874955111. 5895176549151. 0805917598380. 404699430618121. 1532997385730. 4362179163420. 274434143586130. 6990484202220. 4542513183510. 39387099741614-3. 0676252237773. 7666736439985. 38828718446015-1. 8057976266011. 2618275971750. 41133694800616-1. 0361248415980. 7696727850040. 42622316790417-0. 8006278336360. 2354970079610. 22728632545718-0. 7659449788920. 0346828547440. 04331957157519-0. 7649730338130. 0009719450790. 00126894895320-0. 7649722604110. 0000007734020. 00000101101821-0. 7649722604110. 0000000000000. 00000000000122-0. 7649722604110. 0000000000000. 000000000000Điều này phải được thực hiện với một phần rất thận trọng, mặc dù. Trước hết, chỉ có một nghiệm của phương trình trong ví dụ của chúng tôi. Nếu có nhiều hơn một nghiệm, phương pháp Newton có thể dễ dàng chuyển sang nghiệm khác, nếu giá trị ban đầu không được chọn cẩn thận. Điều đó có nghĩa là, nó có thể không tìm thấy các giải pháp khác nhau. Nhưng quay lại câu hỏi chúng tôi đã hỏi ở đầu phần này. còn điểm khởi đầu khác thì sao? Phương pháp Newton có luôn hội tụ không?KHÔNG. Phương pháp của Newton có thể không hội tụ bằng cách đạt đến một điểm trên đường cong có đạo hàm bằng 0, bằng cách dao động giữa hai hoặc nhiều vùng trên đường cong, bằng cách chạy lệch về phía một vùng tiệm cận hoặc nếu hàm tăng chậm hơn căn bậc hai xung quanh gốc. Nếu hàm không có bất kỳ gốc nào, phương pháp của Newton phải thất bại Trong bài viết của tôi Các ví dụ mang tính hướng dẫn cao cho Phương pháp Newton Raphson, tôi sẽ chỉ cho bạn các ví dụ cụ thể cho tất cả những điều này, vì vậy hãy đến đó, nếu bạn muốn xem phương pháp này thất bại vì lý do này hay lý do khác. Nhưng đối với bài viết này, tôi muốn tóm tắt những gì có thể xảy ra, sẽ được trình bày tiếp theo Hãy minh họa điều này bằng ý tưởng sau. chúng tôi lấy hàm ví dụ của chúng tôi và điều tra số bước cần thiết để phương pháp của Newton hội tụ đến gốc duy nhất mà hàm này có. Chúng tôi sẽ làm điều này cho tất cả \(x\) làm điểm bắt đầu \(x_0\) và vẽ biểu đồ số lần lặp cần thiết cho một hàm mới \(g(x)\) Sẵn sàng? Một số nhận xét về con số này theo thứ tự
Vậy chúng ta có thể học được gì từ con số này? . Chính xác hơn, các giá trị bắt đầu âm hoạt động tốt hơn các giá trị dương. Tại sao vậy? Nếu vị trí bắt đầu của chúng ta ở bên trái của gốc, như ví dụ “tốt” của chúng ta \(x_0=-1. 5\), thì tiếp tuyến trong mỗi bước sẽ có \(x_i\) tiếp theo gần gốc hơn so với tiếp tuyến trước đó. Do đó, cần thực hiện một số bước nhỏ để phương pháp Newton-Raphson đạt được kết quả hội tụ Mặt khác, nếu vị trí bắt đầu của chúng ta ở bên phải của gốc, hành vi của hàm và đặc biệt là hành vi của đạo hàm đầu tiên của nó sao cho rất nhiều lần, \(x_i\) tiếp theo ở xa hơn so với . Đặc biệt, điều này đúng khi hệ số góc của \(f(x)\) trở nên rất bằng phẳng, i. e. , giá trị của \(f'(x_i)\) trở nên rất nhỏ, vì điều đó tạo ra sự khác biệt giữa \(x_i\) lớn. Điều này là hiển nhiên, khi nhớ thủ tục lặp \[x_{i+1}= x_i – \frac{f(x_i)}{f'(x_i)} \] Giá trị \(f'(x_i)\) xuất hiện ở mẫu số, do đó làm tăng số hạng thứ hai ở vế phải của phương trình, khi \(f'(x_i)\) nhỏ Các khu vực không ổn định cho phương pháp Newton-RaphsonTrong hình trên, có một số “tháp” điểm đỏ. Điều đó có nghĩa là phương pháp của Newton cần nhiều bước để phương pháp này hội tụ, khi nó được bắt đầu từ một điểm xung quanh đó. Tương tự, điều này cũng xảy ra, nếu tại một thời điểm nào đó trong quá trình lặp lại, \(x_i\) tình cờ rơi vào vùng này, bởi vì đó là tình huống tương tự như khi quá trình lặp đã bắt đầu ở đó Các “tháp” này đại diện cho các vùng không ổn định đối với phương pháp Newton-Raphson trên trục \(x\). Làm thế nào chúng ta có thể hiểu những điều đó? . Hãy xem đạo hàm bậc nhất của hàm ví dụ của chúng ta. Vì \[f(x)=\sin (x^2)-x^3-1\]chúng ta có \[f'(x)=2x\cos (x^2)-3x^2\]Hàm số \(f(x)\) có các điểm có hệ số góc bằng 0, trong đó \(f'(x)=0\). Chúng ta có thể thấy ngay rằng \(x=0\) thỏa mãn phương trình này, vì vậy có một điểm cần tránh. cái kia ở đâu \[2\cos (x^2)=3x\]Vì vậy, xung quanh mỗi điểm đó, phương pháp của Newton có thể không hoạt động bình thường, bị ném ra xa khỏi gốc hoặc thậm chí trúng một trong những điểm này. Nếu thuật toán đáp xuống một trong những điểm này đủ chính xác để tạo ra giá trị số bằng 0 cho đạo hàm của \(f\), thì thuật toán không thể tiếp tục Tuy nhiên, nói chung, không có khả năng đạt được giá trị số chính xác của một điểm kỳ dị như vậy với một điểm lưới, trừ khi giá trị số đó rơi vào một số loại mẫu mà lưới có, chẳng hạn như là một số nguyên và các điểm lưới đều là số nguyên. Trong ví dụ của chúng tôi, điều này có thể xảy ra với \(x=0\), nhưng không có khả năng xảy ra với giá trị khác Bây giờ, hãy thảo luận thêm về cốt truyện từ trên cao một chút – tôi trình bày lại ở đây để bạn tiện theo dõi Theo đường cong màu đỏ từ trái sang phải, hai tháp điểm màu đỏ đầu tiên tương ứng với hai vùng không ổn định mà chúng ta vừa thảo luận, xung quanh \(x=0\) và \(x=2/3\cos (x^2 . Các tháp sau bên phải được tạo bởi các điểm bắt đầu, có điểm đầu tiên, thứ hai, thứ ba, v.v. bước chân rơi ngay vào một trong hai vùng bất ổn này Ở giữa các tháp điểm đỏ này, chúng ta có vùng ngược lại, cụ thể là các vùng nhỏ hơn, từ đó điểm thứ nhất, thứ hai, thứ ba, v.v. các bước trong quá trình lặp đưa thuật toán về rất gần gốc, nơi nó hội tụ nhanh chóng Như tôi đã đề cập ở trên, hàm ví dụ ở đây chỉ có một gốc, giúp phương pháp Newton-Raphson thành công. Trong ví dụ cụ thể này, điều duy nhất có thể sai là đạo hàm chạm 0. Không thể có dao động liên tục giữa các vùng hoặc chạy về phía một vùng tiệm cận. Vì vậy, ví dụ của chúng tôi ở đây được thực hiện để cho thấy phương pháp của Newton hoạt động tốt. Để điều tra các lỗi có thể xảy ra khác, tôi giới thiệu bạn đến bài viết của tôi Các ví dụ mang tính hướng dẫn cao cho Phương pháp Newton Raphson Trước khi chúng ta đến với các ví dụ mã python, hãy để tôi tóm tắt thuật toán cho phương pháp Newton-Raphson một lần nữa ở dạng thu gọn Bản tóm tắt. thuật toán cho phương pháp NewtonThuật toán cho phương pháp Newton để xấp xỉ bằng số một nghiệm của hàm có thể được tóm tắt như sau
Nếu thuật toán đạt đến số lần lặp tối đa mà bạn đã đặt, thì điều này có thể nhưng không nhất thiết phải chỉ ra rằng không thể hội tụ. Có thể cần thử nghiệm với các giá trị phù hợp cho cả \(\Delta_{d}\) và \(N\) để đạt được kết quả khả quan Trực giác đơn giản về Newton Fract Vui lòng bật JavaScript Trực giác đơn giản về Newton Fractals trong 7 ví dụ haySử dụng phương pháp của Newton mà không cần máy tínhĐiều này thật thú vị khi đề cập đến, bởi vì nó không tự động xuất hiện trong đầu tôi khi nghĩ về các thuật toán tính toán. bạn có thể làm tất cả những gì tôi vừa mô tả bằng tay, tôi. e. , bằng bút chì và giấy. Có lẽ tôi sẽ bỏ qua việc vẽ đồ thị chi tiết của hàm số và chỉ phác thảo đồ thị của nó. Tôi cũng sẽ đảm bảo rằng mình chọn một điểm xuất phát lý tưởng và không đánh lừa quá nhiều. Nhưng khác với điều đó, các bước là như nhau Để điều này hoạt động bằng tay, dạng hàm của \(f\) phải được biết và bạn cần có khả năng đánh giá hàm và đạo hàm của nó một cách chính xác hợp lý. Nếu không, độ chính xác mà bạn có thể đạt được trong nỗ lực tìm kiếm gốc sẽ bị ảnh hưởng. Và đừng phạm sai lầm khi tính toán. Và … bạn có được hình ảnh Nếu bạn muốn xem một ứng dụng của phương pháp Newton có thể và thực sự được sử dụng để thu được kết quả hay không, tôi giới thiệu cho bạn bài viết của tôi Các ví dụ mang tính hướng dẫn cao cho Phương pháp Newton Raphson. Ví dụ đầu tiên ở đó cho bạn thấy cách tính căn bậc hai của một số thực dương bằng phương pháp Newton. Chúc vui vẻ Mã Python để tạo các số liệuNhư đã hứa, tôi đăng mã python của mình cho mô tả này và ví dụ tại đây. Đầu tiên, tôi đăng toàn bộ mã mà tôi đã sử dụng để tạo tất cả các số liệu khác nhau trong bài viết này. Xin lưu ý rằng mã này không hoàn hảo, nó chỉ là một ví dụ. Hơn nữa, mã có sẵn và không có bảo hành hoặc bất cứ thứ gì tương tự. Cũng. sử dụng mã có nguy cơ của riêng bạn Vì tôi có một số bước và số liệu khác nhau trong bài viết này, tôi có thể đăng một số đoạn mã ở đây. Tuy nhiên, tôi đã quyết định chỉ đăng một đoạn mã ở đây cho các số liệu và chỉ tách riêng phần dành cho thuật toán Newton-Raphson bên dưới Nhiều dòng khác nhau trong mã này được nhận xét, nhưng điều đó chỉ có nghĩa là bạn có thể chuyển đổi giữa các cài đặt khác nhau để tạo ra hình này hay hình khác. Đừng lo lắng, nó không phức tạp lắm #!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 24 05:52:47 2019
@author: Andreas Krassnigg, ComputingSkillSet.com/about/
This work is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
More information: https://creativecommons.org/licenses/by-sa/4.0/
"""
import matplotlib.pyplot as plt
import numpy as np
# define the function to investigate
def f(x):
return np.sin(x**2) - x**3 - 1
# and its derivative
def fp(x):
return 2*x*np.cos(x**2) - 3*x**2
# define left and right boundaries for plotting
# for demo reasons:
interval_left = -2
interval_right = 2
# for better search:
#interval_left = -1.6
#interval_right = -0.5
# define x grid of points for computation and plotting the function
# increase num at your convenience, but with caution. Article figure has 10 000
xvals = np.linspace(interval_left, interval_right, num=100)
# define y values for example function
yvals = f(xvals)
# create a list of startin points for Newton's method to loop over later in the code
# demo list of starting points
#pointlist = [-1.5,1]
# good starting point
#pointlist = [-1.5]
# not so good starting point
#pointlist = [1]
# try all x values as starting points
pointlist = xvals
# begin figure for plotting
plt.figure()
# plot the function f
plt.plot(xvals,yvals)
# plot the zero line for easy reference
plt.hlines(0, interval_left, interval_right)
#label the axes
plt.xlabel("$x$", fontsize=16)
plt.ylabel("$f(x)$", fontsize=16)
# set limits for the x and y axes in the figure
# set x limits
plt.xlim((interval_left, interval_right))
# set y limits
# for demo reasons:
#plt.ylim((-10,6))
# for better search:
#plt.ylim((-1,4))
# for convergence plot:
plt.ylim((-10,50))
# loop over all starting points defined in pointlist
for x0 in pointlist:
# set desired precision and max number of iterations
prec_goal = 1.e-10
nmax = 1000
# initialize values for iteration loop
reldiff = 1
xi = x0
counter = 0
# start iteration loop
while reldiff > prec_goal and counter < nmax:
# # plot the tangents, points and intersections for finding the next xi
# # plot star on the curve where x=xi
# plt.plot(xi,f(xi),'r*', markersize=16)
# # compute y values for tangent plotting
# tangy = fp(xi)*xvals + f(xi) - fp(xi)*xi
# # plot the tangent
# plt.plot(xvals, tangy, 'r--')
# # perfom iteration step and compute next xi
# x1 = xi - f(xi)/fp(xi)
# # print numbers for use in convergence tables (csv format)
# print('%i, %15.12f, %15.12f, %15.12f' % (counter+1, x1, np.abs(f(xi)/fp(xi)), np.abs(f(xi)/fp(xi)/xi)))
# # plot next xi on the axis
# plt.plot(x1,0,'gx', markersize=16)
# # trade value to next iteration step
# xi = x1
# get the number of necessary iterations at that particular x0
# compute relative difference
reldiff = np.abs(f(xi)/fp(xi)/xi)
# compute next xi
x1 = xi - f(xi)/fp(xi)
# trade output to input for next iteration step
xi = x1
# increase counter
counter += 1
# plot the number of necessary iterations at that particular x0
plt.plot(x0,counter,'r.', markersize=5)
# print test output
print(x0,counter,reldiff)
# save the figure to an output file
plt.savefig('newton-method-demo-figure.jpg', bbox_inches='tight')
# close plot for suppressing the figure output at runtime. Figure is still saved to file
#plt.close()Mã ví dụ Python cho phương pháp Newton-RaphsonCuối cùng, trong phần này, tôi đăng một đoạn mã ngắn trong python 3 để tính giá trị gần đúng cho nghiệm của một hàm bằng phương pháp Newton-Raphson. Thay thế hàm và đạo hàm của nó bằng hàm bạn muốn khảo sát. Đặt giá trị bắt đầu, độ chính xác mong muốn và số lần lặp lại tối đa Nhược điểm chính của phương pháp Newton là gì?Hai nhược điểm chính của phương pháp Newton là (i) sự cần thiết phải bắt đầu phép lặp khá gần với điểm 0 được tìm kiếm để đạt được sự hội tụ and (ii) to calculate the inverse of the derivative at each iterative step.
Khi nào chúng ta không nên sử dụng NewtonPhương pháp của Newton có thể không hoạt động nếu có các điểm uốn, cực đại hoặc cực tiểu cục bộ xung quanh x 0 x_0 x0 hoặc nghiệm . Ví dụ: giả sử bạn cần tìm nghiệm của 27 x 3 − 3 x + 1 = 0 27x^3 - 3x + 1 = 0 27x3−3x+1=0 gần x = 0 x = 0 x=0.
Phương pháp của Newton có nhanh không?Phương pháp Newton để xác định nghiệm của phương trình phi tuyến f ( x ) = 0 từ lâu đã được ưa chuộng vì tính đơn giản và tốc độ hội tụ nhanh.
Phương pháp x0 Newton là gì?Phương pháp của Newton là kỹ thuật giải các phương trình dạng f(x)=0 bằng phép xấp xỉ liên tiếp . Ý tưởng là chọn một dự đoán ban đầu x0 sao cho f(x0) gần bằng 0. Sau đó, chúng ta tìm phương trình của đường tiếp tuyến với y=f(x) tại x=x0 và theo nó trở lại trục x tại một điểm mới (và đã được cải tiến. ) đoán x1. |
