Kaedah Newton yang diubah suai.

Kami menyenaraikan kelemahan kaedah Newton, yang pelbagai pengubahsuaian bertujuan untuk menghapuskan:

kesukaran untuk menentukan anggaran awal dari mana kaedah menumpu;

keperluan untuk mengira matriks Jacobian pada setiap lelaran, yang mungkin memerlukan kos pengiraan yang ketara;

keperluan untuk menyelesaikan sistem persamaan algebra linear pada setiap lelaran;

keperluan bukan degenerasi matriks Jacobi.

Mari kita pertimbangkan pengubahsuaian kaedah Newton, yang pada satu tahap atau yang lain menghapuskan kelemahan yang disenaraikan.

Kaedah Newton dengan matriks pemalar sekeping.

Untuk mengurangkan kos pengiraan lelaran, matriks Jacobian dalam pengubahsuaian ini kekal malar sepanjang beberapa langkah. Bilangan langkah m, di mana J adalah malar, dinyatakan dalam pengubahsuaian ini sebagai parameter, atau momen pengiraan semula matriks Jacobian ditentukan oleh keadaan

di mana, sebagai contoh, (matriks Jacobian hanya dikira semula jika syarat ini dilanggar).

Keberkesanan kaedah dicapai dalam kes ini bukan sahaja dengan mengurangkan bilangan pengiraan matriks Jacobian, tetapi terutamanya disebabkan oleh fakta bahawa m Dalam lelaran kaedah, sistem linear dengan matriks yang sama perlu diselesaikan.

Kaedah Newton-Raphson.

Untuk memastikan penumpuan kaedah daripada anggaran awal yang dipilih, pengubahsuaian yang dipanggil kaedah Newton-Raphson digunakan. Pengiraan (k+ 1) Anggaran ke- dalam pengubahsuaian ini dijalankan mengikut peraturan

di manakah parameter yang nilainya k lelaran ke-th dipilih daripada syarat

Strategi untuk memilih parameter pada lelaran boleh menjadi seperti ini. Pertama, nilai percubaan diterima atau nilai ini kemudiannya diubah suai sehingga syarat yang dinyatakan dipenuhi. Keadaan ini mungkin memerlukan vektor untuk dinilai beberapa kali dalam lelaran semasa. Jelas sekali apabila kaedah Newton-Raphson bertepatan dengan kaedah Newton.

Kaedah penerusan mengikut parameter.

Kaedah ini memungkinkan untuk memastikan penumpuan kaedah Newton daripada anggaran awal yang dipilih.Intipati kaedah penerusan berkenaan dengan parameter adalah untuk menggantikan masalah asal urutan tugasan, setiap tugasan berikutnya berbeza sedikit daripada tugasan sebelumnya. Urutan itu dibina sedemikian rupa sehingga sistem pertama mempunyai penyelesaian, dan sistem terkini bertepatan dengan tugas asal. Oleh kerana sistem hanya berbeza sedikit, penyelesaian kepada masalah sebelumnya akan menjadi anggaran awal yang baik untuk yang seterusnya. Menyelesaikan urutan masalah ini menggunakan kaedah Newton, kami akhirnya memperoleh penyelesaian kepada sistem asal. Mari kita pertimbangkan kaedah untuk membina urutan tugas yang ditentukan.

Biarkan apabila menyelesaikan sistem

anggaran awal digunakan. Mari kita gantikan persamaan asal dengan persamaan dengan parameter

yang at mempunyai penyelesaian, dan pada bertepatan dengan penyelesaian kepada masalah asal, i.e.

Anda boleh memilih fungsi sebagai

Mari bahagikan segmen kepada selang dengan mata. Kami memperoleh urutan sistem yang diperlukan:

Kaedah Newton untuk masalah yang tidak bersyarat.

Jika matriks Jacobian tidak terkondisi, ralat dalam menyelesaikan sistem linear

mungkin penting kerana ralat pembundaran. Oleh itu dalam

Dalam kes matriks yang tidak bersyarat, apabila mengira vektor pembetulan, seseorang menggunakan sistem

dengan parameter berangka, di mana E-matriks identiti. Apabila sistem yang diubah suai bertepatan dengan sistem linear Kaedah piawai Newton, kerana nombor keadaan sistem yang diubah suai cenderung kepada satu, ia juga cenderung kepada satu. Walau bagaimanapun, kadar penumpuan kaedah yang sepadan merosot dengan ketara, kerana kaedah itu merosot kepada kaedah lelaran mudah.

Pengalaman menunjukkan bahawa apabila mengkaji fungsi bukan kuadratik, kaedah Newton tidak boleh dipercayai. Malah, jika maksudnya X(0) terletak pada jarak yang agak jauh dari titik X*, Langkah Newton selalunya terlalu besar, yang boleh menyebabkan kekurangan penumpuan. Kaedah ini boleh diubah suai dengan mudah untuk memberikan pengurangan Fungsi objektif daripada lelaran kepada lelaran dan cari sepanjang garis lurus, seperti dalam kaedah Cauchy. Urutan lelaran dibina mengikut formula

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

Pilihan α dijalankan sedemikian rupa sehingga

f(x) → min;

ini menjamin ketidaksamaan

f(x) ≤ f(x).

Kaedah ini dipanggil kaedah Newton yang diubah suai dan dalam kes di mana pengiraan nilai tepat derivatif pertama dan kedua tidak melibatkan kesukaran yang ketara, ia ternyata boleh dipercayai dan berkesan. Walau bagaimanapun, apabila menggunakan kaedah Newton yang diubah suai, pada setiap lelaran terdapat keperluan untuk membina dan menyelesaikan persamaan linear yang mengandungi unsur-unsur matriks Hessian. f().

Kaedah Marquardt

Kaedah yang dipertimbangkan adalah gabungan kaedah Cauchy dan Newton, yang berjaya menggabungkan sifat positif kedua-dua kaedah. Walau bagaimanapun, apabila menggunakan kaedah Marquardt diperlukan maklumat tentang nilai derivatif kedua bagi fungsi sasaran. Telah dinyatakan di atas bahawa kecerunan menunjukkan arah peningkatan tempatan terbesar dalam fungsi, dan pergerakan ke arah yang bertentangan dengan kecerunan dari titik X(0) terletak pada jarak yang agak jauh dari titik minimum X*, biasanya membawa kepada pengurangan ketara dalam fungsi objektif. Sebaliknya, arah carian berkesan di sekitar titik minimum ditentukan oleh kaedah Newton. Idea mudah menggabungkan kaedah Cauchy dan Newton adalah asas untuk algoritma yang dibangunkan oleh Marquardt pada tahun 1963. Selaras dengan kaedah ini, arah carian ditentukan oleh kesamaan

s(x(k)) = – [N(k) + λ (k) saya] -1 f (x(k)). (3.57)

Dalam kes ini, dalam formula (3.42) kita harus meletakkan α (k) = +1, kerana parameter λ membenarkan bukan sahaja menukar arah carian, tetapi juga melaraskan panjang langkah. Simbol saya di sini kita menandakan matriks identiti, iaitu, matriks yang semua unsurnya adalah sifar, kecuali unsur pepenjuru bersamaan dengan +1. hidup peringkat awal parameter carian λ (0) diberikan sangat penting(contohnya 10 4) jadi

[N(0) + λ (0) saya] -1 = [λ (0) saya] -1 = saya. (3.58)

Oleh itu, nilai yang besarλ (0) sepadan dengan arah carian s( x (0)) → f (x(0)).Daripada formula (3.57) kita boleh membuat kesimpulan bahawa dengan menurun λ kepada sifar s(x) berubah dari arah yang bertentangan dengan kecerunan kepada arah yang ditentukan oleh kaedah Newton. Jika selepas langkah pertama satu titik dengan nilai fungsi objektif yang lebih kecil diperolehi (iaitu. f(X (1)) < f(x(0))), kita harus memilih λ (1)< λ (0) и реализовать еще один шаг; в противном случае следует положить λ (0) = βλ (0) , где β >1, dan laksanakan langkah sebelumnya sekali lagi. Di bawah adalah langkah-langkah algoritma.

Algoritma Marquardt

Langkah 1. Tetapkan X(0) - pendekatan awal untuk X*; M- bilangan lelaran maksimum (dibenarkan); ε ialah parameter penumpuan.

Langkah 2. Letakkan k= 0, λ (0) = 10 4 .

Langkah 3. Kira komponen f (x(k)).

Langkah 4. Adakah ketidaksamaan berlaku?

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

Ya: pergi ke langkah 11.

Langkah 5. Adakah ketidaksamaan berlaku? k ≥ M?

Ya: pergi ke langkah 11.

Tidak: pergi ke langkah seterusnya.

Langkah 6. Kira s(x(k)) = – [N(k) + λ (k) saya] -1 f (x(k)).

Langkah 7. Letakkan x = xs(x).

Langkah 8. Adakah ketidaksamaan berlaku? f(x) < f(x)?

Ya: pergi ke langkah 9.

Tidak: pergi ke langkah 10.

Langkah 9. Tetapkan λ (k +1) = ½ λ (k) dan k = k+ 1. Pergi ke langkah 3.

Langkah 10. Tetapkan λ (k) = 2λ (k) . Pergi ke langkah 6.

Langkah 11.Cetak keputusan dan berhenti.

Kaedah Marquardt dicirikan oleh kesederhanaan relatif, sifat fungsi objektif berkurangan apabila bergerak dari lelaran ke lelaran, dan kadar penumpuan yang tinggi di sekitar titik minimum. x*, a juga dengan ketiadaan prosedur carian sepanjang garis lurus. Kelemahan utama kaedah adalah keperluan untuk mengira N(k) dan penyelesaian sistem yang seterusnya persamaan linear, sepadan dengan (3.57). Kaedah ini digunakan secara meluas dalam menyelesaikan masalah di mana f(x) ditulis sebagai hasil tambah kuasa dua 1), i.e.

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

Inilah masalah yang dipertimbangkan oleh Marquardt. Powell dan Bard, berdasarkan eksperimen pengiraan, menunjukkan bahawa kaedah Marquardt adalah berbeza kecekapan tinggi apabila menyelesaikan masalah jenis ini.

Kaedah Newton dan kaedah sekan

Kaedah Newton dalam kes punca sebenar yang mudah mempunyai bentuk

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

f ′(x k)

dalam kes kepelbagaian akar r

x k +1 - x k

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

Anggaran ralat adalah seperti berikut:

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

M p+1 |x 0 - x * |

q = ―――――< 1.

m p p(p + 1)

Anda boleh menggunakan anggaran ralat seperti dalam kaedah lelaran mudah, dengan mengambil kira kaedah Newton

sx) = x – p ――

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

f′(x 0)

digunakan apabila mereka ingin mengelakkan pengiraan terbitan berbilang ¦¢(x k).

Kaedah Newton memerlukan pengiraan derivatif fungsi, yang tidak selalunya mudah. Anda boleh menggantikan derivatif dengan perbezaan terbahagi pertama yang ditemui daripada dua lelaran terakhir. Kemudian, bukannya kaedah Newton (8.6), kami memperoleh kaedah secant

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

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

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

Untuk memulakan proses anda perlu mengetahui nilainya x 0 Dan x 1.

TUGASAN UNTUK KERJA MAKMAL.

1. Asingkan punca sebenar secara analitik atau grafik.

2. Jelaskan akar dengan membahagikan ruas kepada separuh (jika boleh) dengan ketepatan 0.1.

3. Perhalusi akar menggunakan kaedah yang diberikan dengan ketepatan yang diberikan.

Untuk kaedah Newton dan kaedah lelaran mudah, bilangan lelaran yang diperlukan untuk mencapai ketepatan tertentu mesti dipilih terlebih dahulu dengan menganggar ralat secara manual. Untuk kaedah lain, lelaran berhenti selepas perbezaan kedua-duanya anggaran berturut-turut menjadi kurang daripada ketepatan yang ditetapkan.

4. Semak keputusan dengan menggantikan nilai yang ditemui ke dalam persamaan.

PILIHAN

1. Cari semua punca persamaan

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

dengan ketepatan 0.0001 dengan kaedah a) Newton b) secan.

2. Cari semua punca persamaan

x 4 - 10001.01 x 3 -9800.01 x 2 - 999901 x + 10000 = 0

dengan ketepatan 0.001 a) Kaedah Newton b) Kaedah Newton yang diubah suai.

3. Cari semua punca persamaan

pada segmen dengan ketepatan 0.001 dengan kaedah Newton.

4. Cari semua punca persamaan

5. Cari punca persamaan

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

pada segmen [-1,1] dengan ketepatan 0.0001 dengan kaedah Newton dengan parameter

ketepatan yang ditentukan.

6. Cari punca persamaan

7. Cari semua punca persamaan

x 5 - 3 x 2 + 1 = 0

menggunakan kaedah parabola dengan ketepatan 0.0005.

8. Cari punca sebenar persamaan

9. Cari punca 0, 1, -1 yang manakah bagi persamaan itu

Kaedah Newton menumpu jika anda bermula dengan anggaran awal yang sewenang-wenangnya. Apakah anggaran awal yang memberikan perbezaan kaedah?

10. Cari semua punca persamaan

x 3 + 3 x 2 - 1 = 0

dengan kaedah lelaran mudah dengan ketepatan 0.0005.

11. Cari semua punca persamaan

x 4 - 10000.01 x 3 +101 x 2 - 10000.01 x + 100 = 0

dengan ketepatan 0.001 a) Kaedah Newton b) mengubahsuai kaedah Newton.

12. Cari punca persamaan

arccos(x/2) = x2

pada segmen a) Kaedah Newton b) mengubahsuai kaedah Newton.

13. Cari semua punca persamaan

x 4 – 0.015x 3 + 0.3x 2 + x – 1 = 0

14. Cari punca persamaan

x 3 – dosa (2x) = 1

menggunakan kaedah parabola dengan ketepatan 0.001.

15. Cari semua punca persamaan

x 3 – 1777x 2 + 777 = 0

pada segmen [-1,1] menggunakan kaedah parabola dengan ketepatan 0.0001

16. Cari semua punca persamaan

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

dengan ketepatan 0.00001 dengan kaedah a) Newton b) secan.

17. Cari punca persamaan

arctan(7x) = 0.2

pada segmen [-1,1] a) Kaedah Newton b) mengubahsuai kaedah Newton.

18 . Cari punca persamaan

sin (x 4) = 1 – 2x

menggunakan kaedah parabola dengan ketepatan 0.0001.

19 . Cari punca persamaan

dengan ketepatan 0.001 dengan kaedah Newton. Lelaran sehingga perbezaan antara lelaran bersebelahan menjadi kurang daripada ketepatan yang ditentukan. Bandingkan kuantiti yang diperlukan lelaran.

20. Cari semua punca persamaan

x 3 – 45x 2 + 43 = 0

pada segmen [-2,1] a) kaedah Newton yang diubah suai b) kaedah sekan.

21. Cari punca persamaan

arcsin(x) + e x = 2

menggunakan kaedah lelaran mudah dengan ketepatan 0.001, membuat anggaran awal ralat.

22. Cari semua punca persamaan

54x 4 + x 2 – 0.0000001 =0

dengan ketepatan 0.00001 dengan kaedah a) Newton b) secan.

23. Cari semua punca persamaan

tg (x/3) – x 3 = 0

menggunakan kaedah parabola dengan ketepatan 0.001.

24. Cari semua punca persamaan

12x 4 + 11x 3 –10x 2 –999 = 0

pada segmen [-3.5,3] dengan ketepatan 0.0001 dengan kaedah Newton dengan parameter

p=1 dan p=2. Bandingkan bilangan lelaran yang diperlukan untuk dicapai

ketepatan yang ditentukan.

25. Cari punca persamaan

dengan ketepatan 0.0001 dengan kaedah Newton dan kaedah Newton yang diubah suai. Lelaran sehingga perbezaan antara lelaran bersebelahan menjadi kurang daripada ketepatan yang ditentukan. Bandingkan bilangan lelaran yang diperlukan.

JAWAPAN: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.

Kaedah Newton yang diubah suai adalah berdasarkan kaedah Newton. Jika derivatif berubah sedikit ke atas segmen, maka kita boleh menganggap.

Dari sini kita memperoleh penghampiran berturut-turut untuk punca persamaan

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

Secara geometri, kaedah ini bermakna kita menggantikan tangen pada titik dengan garis lurus selari dengan tangen kepada lengkung pada titik tetap.

Kaedah ini membolehkan anda mengelakkan pengiraan berulang bagi derivatif pada titik. Kaedah Newton yang diubah suai digunakan untuk menyelesaikan persamaan di mana pengiraan derivatif adalah intensif buruh dan agak memakan masa. Dalam kes lain, lebih baik menggunakan kaedah Newton standard.

Sekatan ke atas fungsi dan anggaran awal kaedah Newton yang diubah suai dan piawai bertepatan. Algoritma untuk kedua-dua kaedah adalah hampir sama.

Kaedah Newton yang diubah suai mempunyai penumpuan linear

Kaedah ini menjamin bahawa tiada pembahagian dengan sifar jika .

Contoh. Persamaan.

Kaedah Newton dengan parameter digunakan, kerana punca mempunyai multiplicity p=2. Mari kita ambil anggaran awal dan dapatkan. Akar telah dijumpai.

Contoh. Persamaan.

Akar diasingkan pada segmen. Ralat Eps ialah 0.000001

Kaedah Newton menumpu dalam 5 lelaran, mengubah suai kaedah Newton dalam 19 lelaran, kaedah separuh bahagian dalam 22 lelaran. Penumpuan kaedah lelaran bergantung pada pilihan parameter. Apabila penumpuan dicapai dalam 24 lelaran, penumpuan dalam 11 lelaran, penumpuan dalam 6 lelaran, penumpuan dalam 25 lelaran.

Kaedah secant

Kaedah sekan diperoleh daripada kaedah Newton dengan menggantikan beza terbahagi

dikira daripada anggaran yang diketahui dan.

Sehubungan itu, kami memperoleh formula berikut untuk kaedah sekan

. (1.18)

Kaedah ini adalah dua langkah (kerana anda perlu mengetahui dua langkah sebelumnya untuk melakukan langkah baharu). Ini berbeza daripada semua kaedah yang disebutkan sebelumnya - satu langkah.

Untuk kaedah pemisahan, anggaran awal mula-mula dipilih. Seterusnya, menggunakan formula kaedah lain atau dengan cara lain, anggaran awal kedua dikira. Dan hanya kemudian, untuk mengira anggaran berikutnya, formula kaedah sekan digunakan.

Integrasi fungsi Pernyataan masalah

Biarkan fungsi berterusan diberikan pada segmen. Mari kita bina partition segmen titik dan segmen separa:

Panjang segmen ialah .

Mari kita panggil jumlah integral

Kamiran pasti bagi fungsi pada segmen dipanggil

Kelas fungsi boleh integrasi dan sifatnya dipertimbangkan dalam teori analisis matematik dan tidak dibincangkan di sini. Kami akan menganggap bahawa fungsi kami boleh diintegrasikan pada selang waktu.

Bagaimanakah anda boleh mengira kamiran dalam amalan? Untuk melakukan ini, formula Newton-Leibniz biasanya digunakan:

di mana P(x) - antiderivatif fungsi F(x) , iaitu..

Formula Newton-Leibniz memainkan peranan penting dalam analisis matematik. Tetapi bolehkah ia digunakan untuk menyelesaikan masalah pada komputer? Ia mungkin, tetapi tidak selalu (kerana antiderivatif tidak selalu wujud).

Adakah mudah untuk menggunakannya semasa membuat program? Tidak, anda perlu tahu antiderivatif. Di samping itu, jika fungsi diberikan oleh graf atau jadual, maka kamirannya tidak boleh dikira menggunakan formula ini.

Ini membolehkan kita membuat kesimpulan bahawa formula Newton-Leibniz tidak menyediakan kaedah umum yang universal untuk mencari kamiran pasti bagi fungsi arbitrari dan tidak disyorkan untuk digunakan dalam program komputer profesional. Formula Newton-Leibniz digunakan hanya untuk menguji program yang baru dibangunkan di mana kaedah penyepaduan anggaran fungsi lain telah dilaksanakan.

Di bawah ini kami akan membentangkan algoritma pengiraan sejagat untuk menyelesaikan masalah penyepaduan berangka. Kaedah sedemikian membolehkan seseorang mengira kamiran terus daripada nilai fungsi kamiran dan tidak bergantung pada kaedah definisinya.

Rumus yang sepadan dipanggil formula kamiran berangka atau formula kuadratur 5 .

Langkah pembahagian dalam kes ini dikira mengikut formula.