Memahami "tingkat konvergensi" untuk metode berulang

13

Menurut Wikipedia , laju konvergensi dinyatakan sebagai rasio spesifik dari norma-norma vektor. Saya mencoba memahami perbedaan antara tingkat "linear" dan "kuadrat", pada titik waktu yang berbeda (pada dasarnya, "di awal" dari iterasi, dan "di akhir"). Mungkinkah dinyatakan bahwa:

  • ek+1xk+1ek

  • dengan konvergensi kuadrat, norma kesalahan dari iterate dibatasi olehek+1xk+1ek2

Interpretasi seperti itu akan berarti bahwa, dengan beberapa (sejumlah kecil) iterasi dari algoritma linear konvergen A1 (diasumsikan inisialisasi acak), kesalahan yang lebih kecil akan dicapai bahwa dengan beberapa iterasi algoritma kuadratatik konvergen A2. Namun, karena kesalahan berkurang, dan karena mengkuadratkan, kemudian beralih berarti kesalahan yang lebih kecil dengan A2.

Apakah interpretasi di atas valid? Perhatikan bahwa ini mengabaikan koefisien laju .λ

usero
sumber
1
Algoritma konvergen kuadratik Anda juga dapat dimulai dengan kesalahan yang lebih besar daripada algoritma konvergen linier Anda, yang dapat membuat algoritma A1 Anda lebih "akurat" untuk jumlah iterasi tertentu ...
FrenchKheldar

Jawaban:

9

Dalam latihan, ya. Meskipun masih besar, koefisien laju akan mendominasi kesalahan daripada laju-q. (Perhatikan bahwa ini adalah tingkat asimptotik , jadi pernyataan yang Anda tautkan hanya berlaku untuk batas sebagai .)ekλk

Misalnya, untuk metode urutan pertama dalam pengoptimalan, Anda sering mengamati penurunan kesalahan yang awalnya cepat, yang kemudian naik level. Untuk metode Newton, di sisi lain, perlu beberapa saat sebelum konvergensi superlinear (atau kuadratik) dimulai (konvergen hanya superlinear secara lokal). Untuk alasan itu, adalah umum untuk memulai dengan beberapa langkah gradien untuk mulai sebelum beralih ke metode Newton, atau menggunakan metode homotopy atau quasi-Newton yang berperilaku sebagai metode urutan pertama pada awalnya dan berubah menjadi metode Newton saat Anda mendekati target.

Christian Clason
sumber
11

Selain jawaban Christian, perlu juga dicatat bahwa untuk konvergensi linier Anda memiliki mana Anda memiliki jika metode ini menyatu. Di sisi lain, untuk konvergensi kuadratik Anda memilikiek+1λ1ekλ1<1ek+1λ2ek2λ2λ2e1<1- yaitu, bahwa tebakan awal Anda cukup dekat. Ini adalah perilaku umum yang diamati: bahwa algoritma konvergen kuadratik perlu dimulai "cukup dekat" dari solusi untuk menyatu sedangkan algoritma konvergen linear biasanya lebih kuat. Ini adalah alasan lain mengapa seseorang sering memulai dengan beberapa langkah dari algoritma konvergensi linier (misalnya, metode penurunan paling curam) sebelum beralih ke yang lebih efisien (misalnya, metode Newton).

Wolfgang Bangerth
sumber
6

Penafsirannya secara kualitatif benar.

Perhatikan bahwa konvergensi linier dan kuadratik berkaitan dengan kasus terburuk, situasi dalam algoritma tertentu bisa lebih baik daripada yang Anda dapatkan dari analisis kasus terburuk yang diberikan oleh Wolfgang Bangerth, meskipun situasi kualitatif biasanya sesuai dengan analisis ini.

Dalam algoritma konkret (misalnya, dalam optimasi) sering masuk akal untuk pertama-tama beralih dengan metode yang murah tetapi hanya konvergen linear sampai kemajuan menjadi lambat, dan kemudian selesai dengan metode konvergen kuadratik (atau setidaknya superlinearly). Dalam prakteknya, konvergensi superlinear cenderung sebagus konvergensi kuadrat hanya karena bagian awal, konvergen perlahan cenderung mendominasi keseluruhan pekerjaan.

Arnold Neumaier
sumber