Pengkondisian dan Stabilitas Numerik

Pengkondisian mengukur seberapa sensitif solusi suatu masalah terhadap perturbasi dalam datanya, sementara stabilitas mengukur seberapa banyak galat yang ditambahkan oleh algoritma tertentu dalam aritmetika presisi-terbatas; bersama-sama keduanya menentukan akurasi hasil yang dihitung.

Definition

Pengkondisian adalah properti intrinsik dari suatu masalah yang menjelaskan bagaimana solusi eksaknya merespons perturbasi input, sedangkan stabilitas numerik adalah properti dari suatu algoritma yang menjelaskan seberapa setia algoritma tersebut menyelesaikan masalah meskipun ada galat pembulatan.

Scope

Topik ini mencakup aritmetika titik-mengambang (floating-point) dan pembulatan unit (unit roundoff), bilangan kondisi (condition number) dari masalah seperti penyelesaian sistem linear dan evaluasi fungsi, galat maju (forward error) dan galat mundur (backward error), aturan praktis bahwa galat maju dibatasi oleh bilangan kondisi dikalikan galat mundur, serta definisi stabilitas mundur dan stabilitas maju.

Core questions

• Bagaimana aritmetika titik-mengambang dimodelkan, dan apa peran pembulatan unit?
• Apa yang diukur oleh bilangan kondisi suatu masalah, dan bagaimana definisinya untuk sistem linear dan untuk evaluasi fungsi?
• Bagaimana hubungan antara galat maju, galat mundur, dan pengkondisian?
• Apa yang membedakan algoritma stabil-mundur dari algoritma stabil-maju, dan mengapa stabilitas mundur menjadi target yang umum?

Key theories

Bilangan kondisi

Bilangan kondisi adalah faktor di mana perturbasi relatif dalam data dapat diperkuat dalam solusi; untuk sistem linear, ini sama dengan norma matriks dikalikan norma inversnya, dan ini menetapkan batas pada akurasi yang dapat dicapai terlepas dari algoritmanya.

Analisis galat mundur

Alih-alih membatasi galat dalam jawaban secara langsung, ditunjukkan bahwa hasil yang dihitung adalah jawaban eksak untuk masalah yang berdekatan; algoritma stabil-mundur ketika masalah yang berdekatan ini berbeda dari aslinya sebesar orde pembulatan unit.

Galat maju sama dengan bilangan kondisi dikalikan galat mundur

Aturan praktis utama analisis numerik menyatakan bahwa galat maju (solusi) dibatasi kira-kira oleh bilangan kondisi masalah dikalikan galat mundur, secara jelas memisahkan kontribusi masalah dan algoritma.

Mechanisms

Bilangan titik-mengambang merepresentasikan bilangan riil dengan presisi terbatas, sehingga setiap operasi elementer menimbulkan galat relatif yang dibatasi oleh pembulatan unit. Analisis galat mundur melacak galat-galat ini dengan mengaitkannya pada perturbasi data daripada hasil, menghasilkan batasan dalam bentuk: jawaban terhitung sama dengan jawaban eksak dari input yang terganggu. Menggabungkan batasan galat mundur dengan bilangan kondisi masalah menghasilkan estimasi galat maju, yang menjelaskan mengapa algoritma yang stabil masih dapat kehilangan akurasi pada masalah yang berkondisi buruk (ill-conditioned).

Clinical relevance

Memahami pengkondisian dan stabilitas sangat penting setiap kali hasil komputasi harus dipercaya: hal ini menjelaskan mengapa beberapa formulasi kuadrat terkecil (least-squares) kehilangan akurasi, memandu pemilihan algoritma yang stabil dan formulasi yang terdefinisi dengan baik (well-posed) di seluruh simulasi dan analisis data, serta memperingatkan ketika model yang berkondisi buruk tidak dapat menghasilkan jawaban yang andal terlepas dari metode yang digunakan.

History

Kerangka konseptual ini ditetapkan oleh Wilkinson, yang analisis galat mundurnya pada tahun 1960-an menjelaskan keandalan praktis eliminasi Gaussian, dan kemudian disistematisasi serta diperluas di seluruh bidang oleh Higham; standar titik-mengambang IEEE 754 selanjutnya menempatkan perilaku pembulatan pada pijakan yang kokoh dan portabel.

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

Jika suatu algoritma stabil, apakah akan selalu memberikan jawaban yang akurat?

Tidak. Algoritma stabil-mundur hanya menjamin bahwa jawabannya eksak untuk masalah yang berdekatan; jika masalah itu sendiri berkondisi buruk, masalah yang berdekatan itu dapat memiliki solusi yang sangat berbeda, sehingga galat maju mungkin masih besar.

Apa itu pembulatan unit?

Pembulatan unit adalah galat relatif maksimum yang terjadi ketika bilangan riil dibulatkan ke bilangan titik-mengambang terdekat; ini menetapkan granularitas aritmetika titik-mengambang dan muncul pada dasarnya di setiap batasan stabilitas.