Phương pháp newton python trong khi vòng lặp

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ó

• Ví dụ, một cách tính căn bậc hai là phương pháp Newton
• Giả sử bạn muốn biết căn bậc hai của n
• Nếu bạn bắt đầu với hầu hết mọi giá trị gần đúng, bạn có thể tính giá trị gần đúng tốt hơn bằng công thức sau

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ố

• Đầu tiên là giá trị mà căn bậc hai của nó sẽ được xấp xỉ
• Thứ hai là số lần lặp phép tính mang lại kết quả tốt hơn

Chạy Save Load Show trong Codelens

(chp07_newtonsdef)

• Các cuộc gọi thứ hai và thứ ba đến ____3_______ trong ví dụ trước đều trả về cùng một giá trị cho căn bậc hai của 10
• Sử dụng 10 lần lặp thay vì 5 không cải thiện giá trị
• Nói chung, thuật toán của Newton cuối cùng sẽ đạt đến điểm mà phép tính gần đúng mới không tốt hơn thuật toán trước đó
• Tại thời điểm đó, chúng ta chỉ có thể dừng lại

Việc triển khai này, được hiển thị trong codelens, sử dụng điều kiện while để thực hiện cho đến khi giá trị gần đúng không còn thay đổi. Mỗi lần qua vòng lặp, chúng tôi tính toán giá trị gần đúng “tốt hơn” bằng cách sử dụng công thức được mô tả trước đó. Miễn là "tốt hơn" là khác nhau, chúng tôi sẽ thử lại. Bước qua chương trình và xem các xấp xỉ ngày càng gần hơn

Ghi chú

Câu lệnh while hiển thị ở trên sử dụng so sánh hai số dấu phẩy động trong điều kiện. Vì bản thân các số dấu phẩy động gần đúng với các số thực trong toán học, nên tốt hơn hết là bạn nên so sánh để có kết quả nằm trong một ngưỡng nhỏ nào đó của giá trị mà bạn đang tìm kiếm

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 trong

Giả 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 Newton

Vì 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ại

Phươ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

• viết lại phương trình sao cho có dạng \(f(x)=0\)
• thuyết phục bản thân rằng hàm \(f(x)\) thực sự có số 0 (hoặc nhiều hơn)
• tìm ra, đại khái một trong các số 0 nằm ở đâu (phương pháp của Newton tìm từng số 0 một)
• chọn một điểm trên hàm đủ gần với số 0 đó (bạn sẽ thấy chính xác “đủ gần” nghĩa là gì)
• lưu ý giá trị của \(x\) tại thời điểm này và gọi nó là \(x_0\)
• dựng tiếp tuyến của \(f\) tại điểm này
• tính số 0 của tiếp tuyến (đơn giản vì tiếp tuyến là một hàm tuyến tính)
• sử dụng số không đó của tiếp tuyến làm \(x_0\) mới của chúng tôi, nhưng để tránh nhầm lẫn, chúng tôi gọi nó là \(x_1\)
• lặp lại với \(x_1\) thay vì \(x_0\), bắt đầu với việc dựng tiếp tuyến
• lặp lại lần nữa với \(x_2\), \(x_3\), \(x_4\), v.v. cho đến khi hài lòng với độ chính xác của giải pháp hoặc thất bại là điều hiển nhiên
• nếu thành công, \(x_i\) cuối cùng là một phép tính gần đúng bằng số của nghiệm thực tế của phương trình

Đ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ấy

Giả 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

Ghi chú. Tôi sử dụng python và matplotlib để tạo những hình này. Tôi đã dán các ví dụ mã bên dưới, cùng với các ví dụ cho chính phương pháp Newton-Raphson

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-Raphson

Trong 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 Newton

Giao đ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 Newton

Vì 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-Raphson

Phé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. 000000000000

Rõ 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 nhau

Thậ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ự

• Đường cong màu xanh lam vẫn là chức năng của chúng tôi từ phía trên, để so sánh và để xem đạo hàm của nó đang làm gì
• 10 000 điểm màu đỏ đại diện cho \(g(x)\) và được phân bố đều dọc theo trục \(x\)
• Các giá trị hàm của \(g(x)\) là rời rạc, vì chúng chỉ có thể giả sử là số nguyên. Chúng tôi đang đếm số bước cần thiết để thuật toán Newton đạt được độ chính xác tương đối mong muốn là \(10^{-10}\)

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-Raphson

Trong 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 Newton

Thuậ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

1. Đưa ra một hàm \(f(x)\) của một biến \(x\) và cách tính cả \(f(x_i)\) và đạo hàm của nó \(f'(x_i)\) tại một điểm cho trước \
2. Đặt các giá trị cho độ chính xác tương đối bằng số mong muốn \(\Delta_{d}\) của kết quả cũng như cho số lần lặp tối đa \(N\) mà thuật toán được phép thực hiện
3. Chọn một dự đoán ban đầu \(x_0\), lý tưởng nhất là gần với vị trí của gốc được tính gần đúng
4. Tính xấp xỉ tiếp theo \(x_1\) cho gốc là
   \(x_{1}= x_0 – \frac{f(x_0)}{f'(x_0)} \)
5. Lặp lại như sau \(x_{i+1}= x_i – \frac{f(x_i)}{f'(x_i)} \) và tính toán sự khác biệt tương đối giữa các giá trị gần đúng như
   \(\Delta= \frac{. x_{i+1} -x_i. }{. x_i. }=\frac{. f(x_i). }{. f'(x_i)x_i. } \),
   cho đến khi một trong hai điều xảy ra
   • đạt đến số lần lặp tối đa cho phép, i. e. , \(i>N\)
   • đạt được độ chính xác tương đối bằng số mong muốn, i. e. , \(\Delta