Phương pháp cải biên của Newton.

Chúng tôi liệt kê những nhược điểm của phương pháp Newton, nhằm mục đích loại bỏ các sửa đổi khác nhau của nó:

khó khăn trong việc thiết lập xấp xỉ ban đầu mà từ đó phương pháp hội tụ;

nhu cầu tính toán ma trận Jacobian ở mỗi lần lặp, có thể yêu cầu chi phí tính toán đáng kể;

sự cần thiết phải giải một hệ phương trình đại số tuyến tính ở mỗi lần lặp;

yêu cầu ma trận Jacobi không suy biến.

Chúng ta hãy xem xét các sửa đổi của phương pháp Newton, ở một mức độ nào đó loại bỏ những thiếu sót được liệt kê.

Phương pháp Newton với ma trận hằng số từng phần.

Để giảm chi phí tính toán của các lần lặp, ma trận Jacobi trong sửa đổi này không đổi trong một số bước. Số bước tôi, ở đâu J là hằng số, được chỉ định làm tham số trong sửa đổi này hoặc thời điểm tính toán lại ma trận Jacobian được xác định bởi điều kiện

trong đó, ví dụ (ma trận Jacobi chỉ được tính toán lại nếu điều kiện này bị vi phạm).

Hiệu quả của phương pháp đạt được trong trường hợp này không chỉ bằng cách giảm số lượng phép tính của ma trận Jacobi, mà chủ yếu là do trên tôi lặp lại phương pháp, người ta phải giải các hệ thống tuyến tính với cùng một ma trận.

Phương pháp Newton-Raphson.

Để đảm bảo sự hội tụ của phương pháp từ xấp xỉ ban đầu đã chọn, một sửa đổi được gọi là phương pháp Newton-Raphson được áp dụng. phép tính (k+ 1) phép tính gần đúng trong sửa đổi này được thực hiện theo quy tắc

tham số có giá trị ở đâu k lần lặp thứ được chọn từ điều kiện

Chiến lược chọn tham số trong một lần lặp có thể như sau. Ban đầu, một giá trị dùng thử được lấy hoặc hơn nữa, giá trị này được sửa đổi cho đến khi đáp ứng điều kiện đã lập. Điều kiện này có thể yêu cầu nhiều lần đánh giá vectơ ở lần lặp hiện tại. Rõ ràng, tại , phương pháp Newton-Raphson trùng với phương pháp Newton.

Phương pháp tiếp tục theo tham số.

Các phương pháp này giúp đảm bảo sự hội tụ của phương pháp Newton từ xấp xỉ ban đầu đã chọn.Bản chất của các phương pháp tiếp tục đối với một tham số là thay thế nhiệm vụ ban đầu chuỗi nhiệm vụ, mỗi nhiệm vụ tiếp theo hơi khác so với nhiệm vụ trước đó. Trình tự được xây dựng theo cách mà hệ thống đầu tiên có một giải pháp và hệ thống mới nhất phù hợp với vấn đề ban đầu. Vì các hệ thống hơi khác nhau nên nghiệm của bài toán trước sẽ là một xấp xỉ ban đầu tốt cho bài toán tiếp theo. Giải một dãy bài toán như vậy bằng phương pháp Newton, cuối cùng ta sẽ thu được nghiệm của hệ ban đầu. Hãy xem xét một phương pháp để xây dựng chuỗi nhiệm vụ được chỉ định.

Để khi giải hệ

dự đoán ban đầu được sử dụng. Ta thay phương trình ban đầu bằng một phương trình với tham số

mà for có nghiệm và for trùng với nghiệm của bài toán ban đầu, tức là

Bạn có thể chọn các chức năng như

Hãy chia đoạn theo điểm thành các khoảng. Chúng tôi nhận được chuỗi hệ thống mong muốn:

Phương pháp Newton cho các bài toán điều kiện kém.

Nếu ma trận Jacobi không có điều kiện, lỗi khi giải hệ phương trình tuyến tính

có thể là đáng kể do lỗi làm tròn. Vì vậy, trong

trong trường hợp ma trận không điều kiện, khi tính toán vectơ hiệu chỉnh, hệ thống

với một tham số số, trong đó E-ma trận đơn vị. Đối với , hệ thống sửa đổi trùng với hệ thống tuyến tính Phương pháp tiêu chuẩn của Newton, khi có xu hướng thống nhất, số điều kiện của hệ thống biến đổi cũng có xu hướng thống nhất. Tuy nhiên, tốc độ hội tụ của phương pháp tương ứng giảm đi đáng kể, vì đối với , phương pháp này suy biến thành phương pháp lặp đơn giản.

Kinh nghiệm cho thấy rằng trong việc nghiên cứu các hàm không bậc hai, phương pháp của Newton không đáng tin cậy cho lắm. Thật vậy, nếu điểm X(0) ở một khoảng cách đáng kể so với điểm X*, bước Newton thường trở nên quá lớn, điều này có thể dẫn đến sự thiếu hội tụ. Phương pháp này có thể được sửa đổi khá dễ dàng để giảm hàm mục tiêu từ phép lặp này đến phép lặp khác và tìm kiếm dọc theo một đường thẳng, như trong phương pháp Cauchy. Trình tự lặp được xây dựng theo công thức

x = x -α f(x)f(x).(3.56)

Sự lựa chọn α được thực hiện theo cách mà

f(x) → min;

điều này đảm bảo sự thỏa mãn của bất đẳng thức

f(x) ≤ f(x).

Một phương pháp như vậy được gọi là phương pháp Newton sửa đổi và trong trường hợp việc tính toán các giá trị chính xác của đạo hàm thứ nhất và thứ hai không gặp khó khăn đáng kể, thì nó trở nên đáng tin cậy và hiệu quả. Tuy nhiên, khi sử dụng phương pháp Newton đã sửa đổi, tại mỗi lần lặp lại, cần phải xây dựng và giải_một phương trình tuyến tính chứa các phần tử của ma trận Hesse f().

phương pháp Marquardt

Phương pháp đang được xem xét là sự kết hợp của phương pháp Cauchy và Newton, kết hợp thành công các đặc tính tích cực của cả hai phương pháp. Tuy nhiên, khi sử dụng phương pháp Marquardt yêu cầu thông tin về các giá trị của đạo hàm cấp hai của hàm mục tiêu. Ở trên đã lưu ý rằng độ dốc biểu thị hướng tăng cục bộ lớn nhất trong hàm và chuyển động theo hướng ngược lại với độ dốc từ điểm X(0) nằm ở một khoảng cách đáng kể so với điểm cực tiểu X*, thường dẫn đến sự suy giảm đáng kể trong hàm mục tiêu. Mặt khác, các hướng tìm kiếm hiệu quả trong vùng lân cận của điểm cực tiểu được xác định bằng phương pháp của Newton. ý tưởng đơn giản kết hợp các phương pháp Cauchy và Newton là cơ sở của thuật toán do Marquardt phát triển năm 1963. Theo phương pháp này, hướng tìm kiếm được xác định bởi đẳng thức

S(x(k)) = – [h(k) + λ (k) Tôi] -1 f (x(k)). (3.57)

Trong trường hợp này, trong công thức (3.42), ta nên đặt α(k) = +1, vì tham số λ không chỉ cho phép thay đổi hướng tìm kiếm mà còn điều chỉnh độ dài bước. Biểu tượng Tôiở đây ma trận đồng nhất được biểu thị, tức là ma trận, tất cả các phần tử đều bằng 0, ngoại trừ các phần tử đường chéo bằng +1. trên giai đoạn ban đầu tham số tìm kiếm λ (0) được chỉ định tầm quan trọng lớn(ví dụ: 10 4), vì vậy

[h(0) +λ(0) Tôi] -1 = [λ(0) Tôi] -1 = TÔI. (3.58)

Bằng cách này, giá trị lớnλ(0) tương ứng với hướng tìm kiếm s( x (0)) → f (x(0)).Từ công thức (3.57) ta có thể kết luận rằng khi giảm λ xuống không s(x) thay đổi từ hướng ngược lại với gradient sang hướng được xác định bởi phương pháp của Newton. Nếu sau bước đầu tiên, một điểm có giá trị nhỏ hơn của hàm mục tiêu thu được (tức là f(X (1)) < f(x(0))) nên chọn λ (1)< λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β >1 và thực hiện lại bước trước đó. Dưới đây là các bước của thuật toán.

Thuật toán Marquardt

Bước 1. Đặt X(0) - xấp xỉ ban đầu với X*; m- số lần lặp tối đa (cho phép); ε là tham số hội tụ.

Bước 2. Đặt k= 0, λ (0) = 10 4 .

Bước 3. Tính toán các thành phần f (x(k)).

Bước 4. Bất đẳng thức có đúng không?

|| f (x(k))||< ε?

Có: chuyển sang bước 11.

Bước 5. Bất đẳng thức có đúng không? k ≥ M?

Có: chuyển sang bước 11.

Không: chuyển sang bước tiếp theo.

Bước 6. Tính toán S(x(k)) = – [h(k) + λ (k) Tôi] -1 f (x(k)).

Bước 7. Đặt x = xs(x).

Bước 8. Bất đẳng thức có đúng không? f(x) < f(x)?

Có: chuyển sang bước 9.

Không: Chuyển sang bước 10.

Bước 9. Đặt λ (k +1) = ½ λ (k) và k = k+ 1. Chuyển sang bước 3.

Bước 10. Đặt λ (k) = 2λ (k) . Chuyển sang bước 6.

Bước 11 In kết quả và dừng lại.

Phương pháp Marquardt được đặc trưng bởi tính đơn giản tương đối, thuộc tính giảm hàm mục tiêu trong quá trình chuyển đổi từ phép lặp này sang phép lặp khác, tốc độ hội tụ cao trong vùng lân cận của điểm cực tiểu x* và cũng bởi sự vắng mặt của thủ tục tìm kiếm dọc theo một đường thẳng. Nhược điểm chính của phương pháp là cần phải tính toán h(k) và giải pháp tiếp theo của hệ thống Các phương trình tuyến tính tương ứng với (3.57). Phương pháp này được sử dụng rộng rãi để giải các bài toán trong đó f(x)được viết dưới dạng tổng bình phương 1) , tức là

f(x) = f(x) + f(x) +…+ f(x). (3.59)

Marquardt đã xem xét vấn đề này. Powell và Bard, dựa trên các thí nghiệm tính toán, đã chỉ ra rằng phương pháp Marquardt khác hiệu quả cao khi giải các bài toán dạng này.

Phương pháp Newton và phương pháp secant

phương pháp Newton trong trường hợp một nghiệm thực đơn giản có dạng

x k+1 = x k - ――― , k = 1,2,…. (8.6)

f′(xk)

trong trường hợp căn bội số r

x k +1 - x k

f ′(x k)―――― + f(x k) = 0 .

Ước tính sai số như sau:

|x k - x *| £ q |x 0 - x *|, k = 1,2,….

M p+1 |x 0 - x * |

q = ―――――< 1.

m p p(p + 1)

Bạn có thể sử dụng ước tính lỗi như trong phương pháp lặp đơn giản, với điều kiện là phương pháp của Newton

sx) = x – p ――

x k+1 = x k - ――― , k = 0, 1, ….

f′(x0)

được sử dụng khi bạn muốn tránh tính toán lặp lại đạo hàm ¦¢(xk).

Trong phương pháp của Newton, yêu cầu tính đạo hàm của một hàm, điều này không phải lúc nào cũng thuận tiện. Bạn có thể thay thế đạo hàm bằng hiệu chia đầu tiên được tìm thấy trong hai lần lặp cuối cùng. Sau đó, thay vì phương pháp của Newton (8.6), chúng tôi nhận được phương pháp secant

(x k – x k -1)f(x k)

x k+1 = x k - ――――――

f(x k) – f(x k-1)

Để bắt đầu quá trình, bạn cần biết các giá trị x 0 và x1 .

NHIỆM VỤ CÔNG TÁC CỦA PHÒNG THÍ NGHIỆM.

1. Tách các gốc thực bằng phương pháp phân tích hoặc đồ thị.

2. Tinh chỉnh rễ bằng cách chia đôi đoạn (nếu có thể) với độ chính xác 0,1.

3. Tinh chỉnh các gốc bằng phương pháp cho trước với độ chính xác cho trước.

Đối với phương pháp Newton và phương pháp lặp đơn giản, số lần lặp cần thiết để đạt được độ chính xác nhất định được chọn trước bằng cách ước tính sai số theo cách thủ công. Đối với các phương pháp khác, các lần lặp lại dừng sau sự khác biệt của hai xấp xỉ liên tiếp trở nên nhỏ hơn độ chính xác quy định.

4. Kiểm tra kết quả bằng cách thế các giá trị tìm được vào phương trình.

TÙY CHỌN

1. Tìm tất cả các nghiệm của phương trình

1000000 x 4 - 3000 x 3 + 1000002 x 2 - 3000 x + 2 = 0

với độ chính xác 0,0001 bằng phương pháp a) Newton b) secant.

2. Tìm tất cả các nghiệm của phương trình

x 4 - 10001,01 x 3 -9800,01 x 2 - 999901 x + 10000 = 0

với độ chính xác 0,001 a) Phương pháp Newton b) Phương pháp Newton cải biên.

3. Tìm tất cả các nghiệm của phương trình

trên một đoạn với độ chính xác 0,001 theo phương pháp Newton.

4. Tìm tất cả các nghiệm của phương trình

5. Tìm nghiệm của phương trình

x 4 - 20 x 3 + 101 x 2 - 20 x + 1 = 0

trên khoảng [-1,1] với độ chính xác 0,0001 theo phương pháp Newton với tham số

độ chính xác đã cho.

6. Tìm nghiệm của phương trình

7. Tìm tất cả các nghiệm của phương trình

x5 - 3x2 + 1 = 0

bằng phương pháp parabol với độ chính xác 0,0005.

8. Tìm nghiệm thực của phương trình

9. Tìm nghiệm nào trong các nghiệm 0, 1, -1 của phương trình

Phương pháp của Newton hội tụ nếu chúng ta bắt đầu từ một xấp xỉ ban đầu tùy ý. Những xấp xỉ ban đầu nào đưa ra sự phân kỳ của phương pháp?

10. Tìm tất cả các nghiệm của phương trình

x 3 + 3 x 2 - 1 = 0

phương pháp lặp đơn giản với độ chính xác 0,0005.

11. Tìm tất cả các nghiệm của phương trình

x 4 - 10000,01 x 3 +101 x 2 - 10000,01 x + 100 = 0

chính xác đến 0,001 a) Phương pháp Newton b) Phương pháp Newton cải tiến.

12. Tìm nghiệm của phương trình

arccos (x/2) = x 2

trên khoảng a) theo phương pháp Newton b) theo phương pháp Newton cải biên.

13. Tìm tất cả các nghiệm của phương trình

x 4 - 0,015x 3 + 0,3x 2 + x - 1 = 0

14. Tìm nghiệm của phương trình

x 3 - sin (2x) \u003d 1

bằng phương pháp parabol với độ chính xác 0,001.

15. Tìm tất cả các nghiệm của phương trình

x 3 - 1777x 2 + 777 = 0

trên khoảng [-1,1] theo phương pháp parabol với độ chính xác 0,0001

16. Tìm tất cả các nghiệm của một phương trình

5555x 4 - 555x 3 - 55x 2 - 5x = 0

với độ chính xác 0,00001 bằng phương pháp a) Newton b) secant.

17. Tìm nghiệm của phương trình

arctan(7x) = 0,2

trên khoảng [-1,1] a) Phương trình Newton b) Phương pháp Newton biến đổi.

mười tám . Tìm nghiệm của phương trình

tội lỗi (x 4) = 1 - 2x

bằng phương pháp parabol với độ chính xác 0,0001.

19 . Tìm nghiệm của phương trình

với độ chính xác 0,001 theo phương pháp Newton. Thực hiện các lần lặp lại cho đến khi sự khác biệt giữa các lần lặp liền kề trở nên nhỏ hơn độ chính xác đã chỉ định. So sánh số lượng cần thiết lặp đi lặp lại.

20. Tìm tất cả các nghiệm của một phương trình

x 3 - 45x 2 + 43 = 0

trên đoạn [-2,1] a) phương pháp Newton biến đổi b) phương pháp secant.

21 . Tìm nghiệm của phương trình

arcsin(x) + e x = 2

bằng phương pháp lặp đơn giản với độ chính xác 0,001 bằng cách ước lượng sơ bộ sai số.

22. Tìm tất cả các nghiệm của một phương trình

54x4 + x2 - 0,0000001 =0

với độ chính xác 0,00001 bằng phương pháp a) Newton b) secant.

23. Tìm tất cả các nghiệm của một phương trình

tg (x / 3) - x 3 \u003d 0

bằng phương pháp parabol với độ chính xác 0,001.

24. Tìm tất cả các nghiệm của một phương trình

12x4 + 11x3 -10x2 -999 = 0

trên đoạn [-3,5,3] với độ chính xác 0,0001 theo phương pháp Newton với tham số

p=1 và p=2. So sánh số lần lặp cần thiết để đạt được

độ chính xác đã cho.

25 . Tìm nghiệm của phương trình

với độ chính xác 0,0001 theo phương pháp Newton và phương pháp Newton cải tiến. Thực hiện các lần lặp lại cho đến khi sự khác biệt giữa các lần lặp liền kề trở nên nhỏ hơn độ chính xác đã chỉ định. So sánh số lần lặp yêu cầu.

ĐÁP ÁN:1) 0,0100; 0,0200 2) 0,688; 10000 3) 0,107; 0,155; 0,361 4) –1,32; 0; 1,32 5) 0,0917; 0,1125 6) 0 7) –0,5611; 0,5992; 1,348 8) –0,637; 1,41 9) –1; 0; 1 10) -2,879; -0,6527; 0,5321 11) 0,231; 10000 12) 1,01817183 13) –1,1468; 0,66935; 1 14) 1,191 15) -0,6611; 0,6614 16) –0,09811;0,19695 17) 0,028959 18) 0,4746 19) 0,987 20) –0,9672; 0,9884; 44,98 21) 0,4369 22) +/- 0,0003 23) +/- 0,581; 0 24) -3,36; 2,875 25) 1,2784.

Phương pháp Newton cải biên dựa trên phương pháp Newton. Nếu đạo hàm thay đổi một chút trên đoạn, thì chúng ta có thể giả định.

Từ đây, đối với nghiệm của phương trình, ta thu được các xấp xỉ liên tiếp

N=0,1,2... (1.16)

Về mặt hình học, phương pháp này có nghĩa là chúng ta thay thế các tiếp tuyến tại các điểm bằng các đường thẳng song song với tiếp tuyến của đường cong tại một điểm cố định.

Phương pháp này cho phép bạn từ chối tính toán đạo hàm lặp đi lặp lại tại các điểm. Phương pháp Newton cải tiến được sử dụng để giải các phương trình trong đó việc tính đạo hàm tốn nhiều công sức và tương đối lâu dài. Trong các trường hợp khác, tốt hơn là sử dụng phương pháp Newton tiêu chuẩn.

Các hạn chế về chức năng và xấp xỉ ban đầu cho các phương pháp Newton tiêu chuẩn và sửa đổi là như nhau. Thuật toán của cả hai phương pháp gần như giống nhau.

Phương pháp Newton biến đổi có hội tụ tuyến tính

Phương pháp đảm bảo không chia cho 0 nếu .

Thí dụ. phương trình.

Áp dụng phương pháp của Newton với một tham số, bởi vì gốc có bội số p=2. Chúng tôi lấy xấp xỉ ban đầu và nhận được. Đã tìm thấy gốc.

Thí dụ. phương trình.

Rễ được phân lập trên một vết cắt. Lỗi Eps là 0,000001

Phương pháp Newton hội tụ trong 5 lần lặp, phương pháp Newton biến đổi trong 19 lần lặp, phương pháp chia nửa cho 22 lần lặp. Sự hội tụ của phương pháp lặp phụ thuộc vào việc lựa chọn tham số. Với sự hội tụ đạt được trong 24 lần lặp, hội tụ trong 11 lần lặp, hội tụ trong 6 lần lặp, hội tụ trong 25 lần lặp.

phương pháp secant

Phương pháp secant nhận được từ phương pháp Newton bằng cách thay hiệu số bị chia

được tính bằng các xấp xỉ đã biết và .

Theo đó, công thức sau đây của phương pháp secant thu được

. (1.18)

Phương pháp này là hai bước (vì bạn cần biết hai bước trước đó để thực hiện một bước mới). Ở điểm này, nó khác với tất cả các phương pháp đã cho trước đó - một bước.

Đối với phương pháp secant, giá trị gần đúng ban đầu được chọn trước. Hơn nữa, sử dụng công thức của phương pháp khác hoặc theo cách khác, phép tính gần đúng ban đầu thứ hai. Và chỉ sau đó, để tính toán các phép tính gần đúng tiếp theo, công thức của phương pháp secant mới được sử dụng.

Tích hợp chức năng Tuyên bố vấn đề

Cho hàm số liên tục trên một khoảng. Hãy xây dựng một phân vùng của phân khúc với một điểm và các phân đoạn một phần:

Độ dài các đoạn là .

Hãy gọi tổng tích phân

Tích phân xác định của hàm số trên một đoạn được gọi là

Các lớp hàm khả tích và tính chất của chúng được xem xét trong lý thuyết giải tích toán học và không được thảo luận ở đây. Chúng ta sẽ giả sử rằng hàm của chúng ta có thể tích phân trên khoảng .

Làm thế nào tích phân có thể được tính toán trong thực tế? Đối với điều này, công thức Newton-Leibniz thường được sử dụng:

ở đâu P(x) - nguyên hàm của chức năng F(x) , I E..

Công thức Newton-Leibniz đóng một vai trò quan trọng trong phân tích toán học. Nhưng nó có thể được sử dụng khi giải một bài toán trên máy tính không? Có thể, nhưng không phải lúc nào cũng vậy (vì không phải lúc nào cũng tồn tại nguyên hàm).

Có thuận tiện để sử dụng nó trong lập trình không? Không, bạn cần phải biết nguyên thủy. Ngoài ra, nếu hàm được cho bởi biểu đồ hoặc bảng, thì tích phân từ nó không thể được tính theo công thức này.

Điều này cho phép chúng tôi kết luận rằng công thức Newton-Leibniz không cung cấp một phương pháp chung, phổ quát để tìm tích phân xác định của một hàm tùy ý và không nên sử dụng nó trong các chương trình máy tính chuyên nghiệp. Công thức Newton-Leibniz chỉ được sử dụng để kiểm tra các chương trình mới được phát triển trong đó các phương pháp tích phân hàm gần đúng khác đã được triển khai.

Dưới đây sẽ trình bày các thuật toán tính toán phổ thông để giải bài toán tích phân số. Các phương pháp như vậy giúp tính tích phân trực tiếp từ các giá trị của tích phân và không phụ thuộc vào cách nó được chỉ định.

Các công thức tương ứng được gọi là công thức tích phân số hay công thức cầu phương 5 .

Bước phân vùng trong trường hợp này được tính theo công thức.