For AI agents: use /llms.txt for the Nakafa content index.
Kita ingin mengubah matriks menjadi bentuk segitiga atas, tetapi bukan melalui operasi baris elementer, melainkan melalui transformasi ortogonal yang lebih baik kondisinya. Bayangkan seperti memutar dan memantulkan ruang geometris untuk menyederhanakan matriks, tanpa mengubah sifat fundamentalnya.
Misalkan adalah matriks persegi panjang dengan dan . Maka terdapat matriks ortogonal dengan dan matriks segitiga atas dengan elemen diagonal untuk , sehingga:
Representasi ini disebut QR dekomposisi dari .
Kolom-kolom untuk dari matriks dapat diorthonormalisasi menggunakan proses Gram-Schmidt:
Kita memperoleh vektor ortonormal untuk sebagai kolom dari matriks ortogonal . Sebaliknya:
Jadi dengan matriks segitiga atas yang elemen diagonalnya .
Jika dilengkapi dengan kolom tambahan menjadi matriks ortogonal dan menjadi , maka .
Ketika kita memiliki matriks dengan , ada dua cara untuk merepresentasikan QR dekomposisi. Perbedaannya terletak pada ukuran matriks yang digunakan.
QR dekomposisi penuh menggunakan matriks berukuran penuh:
dengan adalah matriks ortogonal berukuran penuh dan adalah matriks segitiga atas.
Karena bagian bawah matriks hanya berisi nol, kita bisa menghemat penyimpanan dan komputasi. QR dekomposisi ekonomis hanya menggunakan bagian yang benar-benar diperlukan:
Di sini hanya mengambil kolom pertama sampai ke- dari , dan adalah matriks segitiga atas persegi.
Mengapa disebut ekonomis? Karena kita menghemat ruang penyimpanan dan waktu komputasi. Alih-alih menyimpan matriks berukuran yang bisa sangat besar, kita hanya perlu berukuran .
Kolom-kolom matriks yang tidak kita pakai membentuk basis ortonormal dari kernel (ruang nol) :
Di sini kernel dari adalah himpunan semua vektor yang memenuhi .
QR dekomposisi ekonomis dengan kondisi untuk semua adalah unik untuk matriks yang memiliki peringkat penuh.
Meskipun proses Gram-Schmidt memberikan cara teoretis yang elegan untuk memperoleh QR dekomposisi, metode ini tidak cocok untuk perhitungan praktis. Masalah utamanya adalah ketidakstabilan numerik akibat pembatalan, ortogonalitas kolom-kolom cepat hilang selama komputasi.
Untuk mengatasi masalah ini, kita memerlukan metode yang lebih stabil secara numerik. Salah satu pendekatan yang paling berhasil adalah prosedur Householder, yang menggunakan transformasi refleksi ortogonal. Alternatif lain adalah prosedur Givens dengan transformasi rotasi.
Untuk vektor dengan , kita dapat mendefinisikan matriks transformasi Householder:
Perhatikan bahwa adalah produk diadik (outer product), yaitu perkalian vektor kolom dengan vektor baris . Hasil perkalian ini adalah matriks dengan peringkat 1 untuk . Jangan sampai tertukar dengan perkalian skalar yang menghasilkan bilangan tunggal.
Misalkan adalah matriks transformasi Householder untuk vektor dengan . Maka berlaku:
adalah simetri:
adalah matriks ortogonal:
Perkalian dari dari kiri dengan vektor menyebabkan refleksi pada subruang , yaitu pada hiperplane (bidang datar berdimensi tinggi) dengan vektor normal
Diberikan matriks dengan dan . Untuk perhitungan QR dekomposisi, matriks ditransformasi kolom demi kolom melalui refleksi Householder menjadi bentuk segitiga atas.
Mulai dengan dan refleksikan kolom pertama dari terhadap vektor menggunakan bidang refleksi dengan:
Matriks transformasi Householder . Diperoleh:
dengan dan .
Lanjutkan dengan refleksi kolom pertama dari submatriks dengan bidang refleksi:
Dengan matriks transformasi:
Diperoleh:
dengan dan , dan seterusnya hingga:
Pada akhirnya diperoleh matriks segitiga atas:
Jadi diperoleh faktorisasi:
dengan adalah matriks ortogonal.
Implementasi prosedur Householder:
Mulai dengan:
Untuk :
Hitung:
dan:
Kemudian:
Sehingga diperoleh:
Akhirnya diperoleh:
Kompleksitas numerik untuk perhitungan QR dekomposisi matriks dengan prosedur Householder pada dasarnya adalah:
Karena transformasi ortogonal, berlaku
Elemen diagonal adalah bilangan dari langkah ke-. Memilih transformasi sehingga semuanya positif memberikan QR dekomposisi. Jika , tidak memiliki peringkat penuh dan algoritma berhenti.
Untuk alasan numerik memilih tanda sehingga pembatalan dihindari:
Sebagai pengganti membangun , dalam penyimpanan kompak juga dapat menyimpan hanya informasi yang diperlukan untuk transformasi:
Jika hanya ingin menghitung QR dekomposisi ekonomis, hapus kolom dan baris yang sesuai.
di tempat bebas dari di bawah diagonal dan elemen diagonal dalam vektor tambahan.
