Mengapa metode Newton tidak konvergen?

22

Saya menggunakan paket PETSc non -linier SNES untuk menyelesaikan sistem persamaan nonlinier yang diperoleh dengan mendiskritisasi persamaan diferensial parsial. Bagaimana saya bisa menentukan mengapa pemecah tidak konvergen dan apa yang bisa saya lakukan untuk berhasil menyelesaikan persamaan saya?

Jed Brown
sumber
8
Seperti halnya metode iteratif, sangat penting bagi seseorang untuk menghasilkan benih yang baik untuk memulai metode Newton-Raphson. Titik awal yang buruk sering kali menghasilkan kekacauan.
JM
6
Saya berpikir bahwa "sering mengakibatkan kekacauan" tidak benar. Mengacu pada Blum, Cucker, Shub, dan Smale, Newton memiliki cekungan menarik yang dipisahkan oleh batas-batas yang dapat mengakibatkan iterasi kacau. Dengan demikian perilaku semacam ini sangat tidak mungkin dibandingkan dengan konvergensi. Jika algoritma ini hanya mencari solusi nyata, ia akan gagal untuk sering bertemu, tetapi tidak akan menjadi kacau.
Matt Knepley
5
Maksudku "kekacauan" dalam arti nonteknis, @Matt; misalnya, divergensi hingga tak terbatas, atau perilaku siklik. Mungkin "bencana" akan menjadi pilihan kata yang lebih baik?
JM

Jawaban:

42

Metode Newton mungkin tidak konvergen karena banyak alasan, berikut adalah beberapa yang paling umum.

  • Jacobian salah (atau benar secara berurutan tetapi tidak paralel).
  • Sistem linear tidak terpecahkan atau tidak dipecahkan dengan cukup akurat.
  • Sistem Jacobian memiliki singularitas yang tidak ditangani oleh pemecah linear.
  • Ada bug dalam rutinitas evaluasi fungsi.
  • Fungsi ini tidak kontinu atau tidak memiliki turunan pertama yang berkelanjutan (misalnya perubahan fase atau pembatas TVD).
  • Persamaan mungkin tidak memiliki solusi (mis. Siklus batas alih-alih keadaan mantap) atau mungkin ada "bukit" antara dugaan awal dan keadaan mapan (mis. Reaktan harus terbakar dan terbakar sebelum mencapai kondisi mapan, tetapi persamaan status residu akan lebih besar selama pembakaran).

Berikut adalah beberapa cara untuk membantu men-debug kurangnya konvergensi Newton.

  • Jalankan dengan opsi -snes_monitor -ksp_monitor_true_residual -snes_converged_reason -ksp_converged_reason. Jika penyelesaian linier tidak bertemu, periksa apakah Jacobian benar, lalu lihat pertanyaan ini . Jika residu prekondisi menyatu, tetapi residu sebenarnya tidak, prekondisi mungkin tunggal. Jika penyelesaian linear konvergen dengan baik, tetapi pencarian baris gagal, Jacobian mungkin salah.
  • Jalankan dengan -pc_type lu or -pc_type svduntuk melihat apakah masalahnya adalah pemecah linier yang buruk
  • Jalankan dengan -mat_viewatau -mat_view_drawuntuk melihat apakah Jacobian terlihat masuk akal
  • Jalankan dengan -snes_type test -snes_test_displayuntuk melihat apakah Jacobian yang Anda gunakan salah. Bandingkan output ketika Anda menambahkan -mat_fd_type dsuntuk melihat apakah hasilnya sensitif terhadap pilihan parameter pembeda.
  • Jalankan dengan -snes_mf_operator -pc_type luuntuk melihat apakah Jacobian yang Anda gunakan salah. Jika masalah terlalu besar untuk diselesaikan langsung, coba -snes_mf_operator -pc_type ksp -ksp_ksp_rtol 1e-12. Bandingkan output ketika Anda menambahkan -mat_mffd_type dsuntuk melihat apakah hasilnya sensitif terhadap pilihan parameter pembeda.
  • Jalankan pada satu prosesor untuk melihat apakah masalahnya hanya paralel.
  • Jalankan dengan -snes_ls_monitoruntuk melihat apakah pencarian baris gagal (ini biasanya pertanda Jacobian buruk).
  • Jalankan dengan -infountuk mendapatkan informasi lebih rinci tentang proses solusi.

Berikut adalah beberapa cara untuk membantu proses Newton jika semuanya di atas diperiksa

  • Jalankan dengan sekuensing grid ( -snes_grid_sequenceadalah yang Anda butuhkan jika bekerja dengan a DM) untuk menghasilkan tebakan awal yang lebih baik pada mesh yang lebih halus
  • Jalankan dengan presisi quad ( ./configure --with-precision=__float128 --download-f2cblaslapackdengan PETSc 3.2 dan yang lebih baru, membutuhkan versi 4.6 atau yang lebih baru dari kompiler GNU)
  • Ubah unit (nondimensionalization), penskalaan kondisi batas, atau formulasi sehingga Jacobian lebih terkondisi.
  • Mollify fitur dalam fungsi yang tidak memiliki turunan pertama berkelanjutan (sering terjadi ketika ada ifpernyataan dalam evaluasi residu, misalnya perubahan fase atau pembatas TVD). Gunakan pemecah ketimpangan variasional ( SNESVINEWTONRSLS ) jika diskontinuitas itu sangat penting.
  • Coba metode wilayah kepercayaan ( -ts_type tr, mungkin harus menyesuaikan parameter).
  • Jalankan dengan beberapa parameter lanjutan dari titik di mana Anda tahu solusinya, lihat TSPSEUDO untuk memecahkan masalah kondisi mapan. Ada paket solver homotopy seperti PHCpack yang dapat memberi Anda semua solusi yang mungkin (dan memberi tahu Anda bahwa ia telah menemukan semuanya) tetapi itu tidak dapat diskalakan dan tidak dapat menyelesaikan masalah selain masalah kecil.
Jed Brown
sumber