Basin tarik untuk metode Newton

9

Metode Newton untuk menyelesaikan persamaan nonlinier diketahui konvergen secara kuadrat ketika tebakan awal "cukup dekat" dengan solusinya.

Apa itu "cukup dekat"?

Apakah ada literatur tentang struktur cekungan tarik ini?

iterative-method convergence nonlinear-equations David Ketcheson
sumber

Root harus diisolasi (bukan multipel). Jika Hessian jelas seragam (cekung ke atas atau ke bawah) di wilayah tersebut, Anda harus bersikap baik. Tentu saja menjamin atau menguji kondisi ini secara empiris biasanya tidak praktis.

hardmath

Saya melihat pertanyaan di NA-Digest tempo hari dan berpikir itu menarik. Tampaknya saya bukan satu-satunya :-)

Wolfgang Bangerth

8

Untuk persamaan rasional tunggal dalam domain kompleks, cekungan tarik adalah fraktal, kompelemen dari apa yang disebut set Julia. http://en.wikipedia.org/wiki/Julia_set . Untuk teori dengan beberapa angka online yang bagus, lihat, misalnya,
http://mathlab.mathlab.sunysb.edu/~scott/Papers/Newton/Published.pdf
http://hera.ugr.es/doi/15019160.pdf

$x^3-1=0$

Dengan demikian ada sedikit gunanya dalam menentukan secara rinci apa yang "cukup dekat" dengan solusi. Jika seseorang tahu batas pada turunan kedua, ada teorema Newton - Kantorovich yang memberikan batas lebih rendah pada jari-jari bola di mana metode Newton bertemu, tetapi kecuali dalam 1D, ini cenderung sangat pesimis.

Batas yang bermanfaat secara komputasi dapat diperoleh dengan menggunakan aritmatika interval; lihat, misalnya, makalah saya
Shen Zuhe dan A. Neumaier, operator Krawczyk dan teorema Kantorovich, J. Math. Anal Appl. 149 (1990), 437-443.
http://www.mat.univie.ac.at/~neum/scan/61.pdf

Arnold Neumaier
sumber

x^{3} - 1 = 0

$x^3 - 1 = 0$

x > 0

$x > 0$

x > 1

$x > 1$

1

@hardmath: ya, tetapi persamaan kompleks menjadi dua persamaan nyata dalam 2 variabel, yang mana berlaku sama.

Arnold Neumaier

4

"Cukup dekat" sulit untuk dikarakterisasi mengingat hal itu menimbulkan kelas fraktal . Metode Newton dengan strategi globalisasi seperti pencarian garis dan wilayah kepercayaan memperluas daya tarik. Jika struktur masalah tambahan tersedia, seperti dalam optimasi, asumsi yang diperlukan untuk konvergensi dapat semakin melemah.

Jed Brown
sumber

Hanya untuk rasa ingin tahu, apakah Anda memiliki contoh untuk "Jika struktur masalah tambahan tersedia, seperti dalam pengoptimalan, asumsi yang diperlukan untuk konvergensi dapat semakin melemah."?

vanCompute

@vanCompute Lihat contoh ini untuk contoh terkait dengan optimasi, di mana objek fungsional memberikan informasi yang hilang dalam kondisi optimal urutan pertama. Bentuk lain adalah pengetahuan bahwa kelanjutan tertentu (pseudotransient, parameter, kisi, dll) selalu menyatu, tetapi residu mungkin harus meningkat sebelum mencapai solusi jika seseorang mencoba menyelesaikan masalah secara langsung.

Jed Brown

3

Ada beberapa hasil yang bermanfaat untuk metode Newton yang diterapkan pada polinomial kompleks.

$f$

r = \frac{η}{2 d}

$r=\frac{\eta}{2d}$

η

$\eta$

f

$f$

d

$d$

f

$f$

Batas eksplisit lainnya diberikan oleh Anthony Manning di Bagaimana memastikan menemukan akar polinomial kompleks menggunakan metode Newton (Teorema 1.2).

Lihat juga Cara menemukan semua akar polinomial kompleks dengan metode Newton oleh Hubbard et al.
Menciptakan. Matematika 146 (2001), no. 1, 1–33. pdf

lhf
sumber

Diadaptasi dari math.stackexchange.com/a/1038487/589 .

lhf

Basin tarik untuk metode Newton

Jawaban: