Lompat ke konten

Tinjauan ilmiah

Persamaan Normal, QR, dan Dekomposisi Nilai Singular untuk Kuadrat Terkecil Linear

Redaksi ARSTEMA · · 9 menit baca

Abstrak

Masalah kuadrat terkecil linear muncul ketika parameter model ditentukan dari sistem persamaan yang umumnya tidak dapat dipenuhi secara serentak. Persamaan normal, faktorisasi QR, dan dekomposisi nilai singular menawarkan jalur penyelesaian dengan konsekuensi komputasi yang berbeda. Tinjauan ini membandingkan ketiganya berdasarkan materi kuliah aljabar numerik dan makalah tentang dekomposisi tensor, analisis aliran fluida, serta penyelesaian persamaan diferensial parsial. Persamaan normal dapat memanfaatkan struktur masalah dan memiliki keuntungan biaya pada keadaan tertentu, tetapi pembentukan matriksnya menguadratkan bilangan kondisi matriks asal. QR menghindari pembentukan persamaan normal sebagai langkah utama dan merupakan pendekatan baku untuk regresi kuadrat terkecil biasa. Dekomposisi nilai singular menyediakan cara untuk menangani informasi peringkat dan masalah yang mengalami kekurangan peringkat. Pada dekomposisi tensor berperingkat kecil, varian berbasis QR dan dekomposisi nilai singular memiliki kompleksitas yang sama dengan algoritma baku, dengan waktu yang sama dalam implementasi MATLAB yang dilaporkan dan kemungkinan galat aproksimasi yang lebih rendah. Pada masalah besar, faktorisasi juga dapat dipakai untuk membentuk pengondisi awal bagi metode iteratif. Pemilihan metode perlu mempertimbangkan kondisi dan struktur matriks, ketelitian yang dibutuhkan, serta biaya keseluruhan perhitungan.

Kata kunci: kuadrat terkecil linear; persamaan normal; faktorisasi QR; dekomposisi nilai singular; bilangan kondisi; kestabilan numerik

Pendahuluan

Model teknik kerap menghasilkan lebih banyak persamaan daripada parameter yang hendak ditentukan. Persamaan tersebut tidak harus memiliki penyelesaian yang memenuhi semuanya secara tepat. Pendekatan kuadrat terkecil mencari parameter yang meminimalkan ukuran gabungan selisih antara nilai yang dihasilkan model dan ruas kanan persamaan. Selisih itu disebut residual. Dalam bentuk linear, hubungan antara parameter dan hasil model dinyatakan oleh matriks koefisien (Paciorek, 2024).

Persoalannya tidak selesai dengan memilih kriteria residual. Cara menghitung parameter juga memengaruhi hasil ketika aritmetika komputer bekerja dengan ketelitian terbatas. Persamaan normal membentuk sistem baru dari matriks koefisien, sedangkan faktorisasi QR memisahkan matriks menjadi faktor ortogonal dan segitiga. Dekomposisi nilai singular, yang selanjutnya disebut SVD, menguraikan matriks melalui nilai singular dan arah yang terkait dengannya. Ketiganya berhubungan dengan masalah matematis yang sama dan memiliki karakter numerik serta biaya yang berbeda (Johnson, 2019; Paciorek, 2024).

Perbedaan tersebut terlihat dalam aplikasi yang struktur matriksnya berlainan. Masalah dekomposisi tensor dapat menghasilkan serangkaian submasalah kuadrat terkecil. Analisis aliran fluida juga dapat menghasilkan masalah kuadrat terkecil berstruktur, sedangkan pendekatan tertentu untuk persamaan diferensial parsial menghasilkan sistem jarang berukuran besar. Struktur tersebut dapat dimanfaatkan dalam perancangan algoritma (Minster dkk., 2021; Drmač dkk., 2018; Chen dan Tan, 2024).

Pembahasan ini membandingkan sifat masalah, pilihan algoritma, dan implikasinya pada aplikasi tersebut. Fokusnya ialah penyelesaian numerik kuadrat terkecil linear, dengan batasan bahwa sumber yang ditelaah membahas masalah dan kondisi pengujian yang berbeda.

Kondisi matriks dan arti residual

Residual menunjukkan seberapa dekat hasil model dengan ruas kanan yang digunakan dalam perhitungan. Jika matriks koefisien berkondisi buruk, perubahan kecil pada data atau akibat pembulatan dapat menghasilkan perubahan parameter yang besar (Paciorek, 2024).

Bilangan kondisi merangkum salah satu aspek sensitivitas tersebut. Materi MIT menunjukkan bahwa penggunaan persamaan normal secara langsung menguadratkan bilangan kondisi. Paciorek menyatakan hubungan yang sama dari arah sebaliknya: bilangan kondisi matriks rancangan X adalah akar kuadrat bilangan kondisi XᵀX. Dengan demikian, matriks hasil perkalian dalam persamaan normal dapat memiliki kondisi yang lebih sulit daripada matriks asalnya (Johnson, 2019; Paciorek, 2024).

Peringkat matriks merupakan pertimbangan lain. Peringkat kolom penuh berkaitan dengan keunikan penyelesaian kuadrat terkecil pada masalah yang dibahas Paciorek. Ketika peringkat kurang, terdapat beberapa kemungkinan penyelesaian dan pilihan penyelesaian yang dicari perlu diperjelas (Paciorek, 2024).

Dari sudut pandang yang lebih luas, Paciorek menyatakan bahwa keadaan yang menimbulkan kekhawatiran tentang akurasi numerik umumnya juga merupakan keadaan ketika penaksir kuadrat terkecil biasa tidak banyak membantu, misalnya jika prediktor sangat kolinear. Kolinearitas berarti informasi dalam prediktor saling berkaitan kuat, sehingga pembedaan kontribusi koefisien menjadi sulit (Paciorek, 2024).

Persamaan normal dan manfaat struktur

Persamaan normal diperoleh dari syarat bahwa residual optimum tegak lurus terhadap ruang kolom matriks koefisien. Dalam notasi regresi Paciorek, X adalah matriks rancangan, Y adalah vektor pengamatan, dan β adalah vektor koefisien. Persamaan yang diselesaikan berbentuk XᵀXβ = XᵀY. Dengan faktorisasi X = QR dan asumsi peringkat penuh pada bentuk yang dibahas, persamaan tersebut dapat ditulis sebagai Rβ = QᵀY. Karena R berbentuk segitiga atas, koefisien diperoleh melalui substitusi balik (Paciorek, 2024).

Paciorek membandingkan biaya beberapa pendekatan untuk n pengamatan dan p peubah. Hitungan operasinya adalah np² + ⅓p³ untuk Cholesky, np² + p³ untuk penyapuan atau sweeping, 2np² − ⅔p³ untuk QR Householder, dan 2np² untuk QR Gram-Schmidt termodifikasi. Ketika n jauh lebih besar daripada p, Cholesky dan penyapuan lebih cepat menurut perbandingan tersebut. Paciorek juga menilai regresi umumnya cepat kecuali jika p besar, sehingga perbedaan biaya itu jarang perlu terlalu dirisaukan (Paciorek, 2024).

QR memfaktorkan X secara langsung, sedangkan Cholesky dalam pembahasan ini bekerja pada XᵀX yang bilangan kondisinya lebih besar. Menurut penilaian Monahan yang dikutip Paciorek, Gram-Schmidt termodifikasi merupakan yang paling stabil secara numerik di antara pendekatan yang dibandingkan, sedangkan penyapuan paling kurang stabil. Paciorek menyajikan QR sebagai pendekatan baku untuk kuadrat terkecil biasa dan menyatakan bahwa kedua pendekatan umumnya memadai ketika kolinearitas tidak ekstrem (Paciorek, 2024).

Pada dekomposisi tensor CP, kuadrat terkecil bergantian atau alternating least squares, disingkat ALS, memecah perhitungan menjadi sejumlah submasalah linear. Persamaan normal yang lazim digunakan memanfaatkan struktur khusus tensor dan dengan demikian menguntungkan dari sisi efisiensi. Minster dan rekan mengembangkan varian berbasis QR serta SVD untuk meningkatkan kestabilan ketika kondisi numerik buruk (Minster dkk., 2021).

Varian tensor tersebut menunjukkan bahwa peningkatan kestabilan dapat dicapai dengan biaya yang bersaing. Pada peringkat kecil, kompleksitas varian QR dan SVD sama dengan kompleksitas CP-ALS baku. Implementasi MATLAB yang dilaporkan juga mencapai waktu jalan yang sama dengan algoritma baku untuk peringkat kecil. Dalam contoh yang dibahas, metode baru dapat menghasilkan galat aproksimasi yang lebih rendah dan lebih andal memulihkan sinyal berperingkat rendah dari data yang nilai acuannya diketahui (Minster dkk., 2021).

Contoh lain berasal dari identifikasi struktur koheren dalam aliran fluida. Drmač dan rekan membahas sistem kuadrat terkecil yang matriksnya melibatkan struktur Vandermonde dan Khatri-Rao dalam kerangka dekomposisi modus dinamis. Struktur tersebut memungkinkan penyelesaian efisien dengan persamaan normal. Para penulis juga mengusulkan algoritma berbasis QR yang memanfaatkan struktur yang sama untuk kasus berkondisi buruk, ketika persamaan normal dapat gagal menghasilkan solusi yang cukup akurat (Drmač dkk., 2018).

Kedua aplikasi memperlihatkan bahwa struktur matriks berperan dalam pemilihan metode. Pada tensor, struktur digunakan dalam submasalah yang berulang dan juga dimanfaatkan oleh varian QR serta SVD. Pada analisis aliran, struktur matriks menjadi dasar algoritma khusus untuk persamaan normal maupun QR. Pertimbangan biaya dan kestabilan dengan demikian dapat diarahkan pada struktur perhitungan yang tersedia (Minster dkk., 2021; Drmač dkk., 2018).

Faktorisasi QR dan dekomposisi nilai singular

Faktorisasi QR memisahkan matriks koefisien menjadi faktor yang memuat basis ortonormal dan faktor segitiga. Ortonormal berarti arah basis saling tegak lurus dan masing-masing memiliki panjang satu. Dalam masalah berperingkat penuh pada materi Berkeley, transformasi ruas kanan dengan Q dan bentuk segitiga R menghasilkan sistem yang dapat diselesaikan melalui substitusi balik. Faktorisasi ini bekerja pada matriks rancangan (Johnson, 2019; Paciorek, 2024).

Materi MIT membahas Gram-Schmidt termodifikasi dan transformasi Householder sebagai cara membangun faktorisasi QR. Gram-Schmidt klasik dapat kehilangan sifat ortogonal, terutama ketika kolom matriks hampir saling bergantung. Versi termodifikasi memperbaiki perilaku tersebut. Householder menggunakan serangkaian transformasi ortogonal untuk membentuk faktor segitiga. Materi itu juga menjelaskan kestabilan mundur Gram-Schmidt termodifikasi dalam arti bahwa hasil perkalian faktor QR dekat dengan matriks asal (Johnson, 2019).

Paciorek membahas QR dengan pemilihan poros kolom untuk matriks yang tidak berperingkat penuh. Pemilihan poros mengubah urutan kolom selama faktorisasi dan membantu menangani struktur peringkat. Untuk matriks berperingkat penuh, bentuk QR yang hanya mempertahankan kolom Q dan bagian R yang diperlukan dapat mengurangi ukuran faktor yang digunakan dalam regresi (Paciorek, 2024).

SVD memberi pandangan lain dengan memisahkan matriks menurut arah dan nilai singularnya. Nilai singular membantu mengungkap peringkat, sedangkan faktor SVD dapat digunakan untuk membangun invers semu. Pada masalah yang memiliki lebih dari satu penyelesaian, invers semu menyediakan cara untuk memilih penyelesaian dengan panjang terkecil sebagaimana dijelaskan dalam materi Berkeley (Paciorek, 2024).

Dalam metode Chen dan Tan, SVD digunakan untuk membangun pengondisi awal dari matriks yang telah diringkas. Pada submasalah tensor, Minster dan rekan menggunakan QR dan SVD sebagai dasar varian yang lebih stabil daripada persamaan normal (Chen dan Tan, 2024; Minster dkk., 2021).

Kedua penggunaan tersebut menempatkan faktorisasi pada tahap yang berbeda. Dalam CP-ALS, QR dan SVD dipakai untuk menyelesaikan submasalah kuadrat terkecil. Dalam metode Chen dan Tan, faktorisasi matriks yang lebih kecil membentuk pengondisi awal bagi penyelesai iteratif (Minster dkk., 2021; Chen dan Tan, 2024).

Masalah besar dan penyelesaian iteratif

Pada sistem jarang berskala besar, penyelesaian langsung dapat menjadi bagian yang mahal dari keseluruhan perhitungan. Chen dan Tan menelaah masalah kuadrat terkecil dengan banyak persamaan dan kondisi buruk yang muncul terutama dari metode fitur acak untuk persamaan diferensial parsial. Mereka menggabungkan peringkasan acak matriks, faktorisasi pada matriks yang lebih kecil, dan penyelesai kuadrat terkecil iteratif (Chen dan Tan, 2024).

Peringkasan yang digunakan disebut count sketch, yaitu transformasi acak untuk membentuk representasi matriks yang lebih kecil. Dari representasi tersebut, QR atau SVD menghasilkan pengondisi awal. Pengondisi awal adalah transformasi yang dirancang agar masalah yang diselesaikan oleh algoritma iteratif memiliki sifat numerik yang lebih menguntungkan. Penyelesai iteratif kemudian bekerja pada sistem yang telah diberi pengondisi awal (Chen dan Tan, 2024).

Dalam eksperimen yang dilaporkan, penulis menyatakan bahwa metode yang diusulkan memiliki akurasi sebanding dengan atau lebih baik daripada metode langsung dan lebih efisien untuk masalah besar yang diuji. Dengan asumsi ringan, mereka membuktikan bahwa batas atas bilangan kondisi masalah berpengondisi awal tidak bergantung pada bilangan kondisi matriks asal, serta memberikan taksiran galat untuk kedua metode (Chen dan Tan, 2024).

Perbandingan dengan masalah tensor dan aliran memperlihatkan beberapa cara pemanfaatan struktur. Pada tensor, submasalah berulang memanfaatkan struktur dekomposisi. Pada aliran, struktur matriks menjadi dasar algoritma kuadrat terkecil khusus. Pada metode fitur acak, matriks diringkas sebelum pengondisi awal dibentuk dan iterasi dijalankan. Masing-masing menempatkan operasi faktorisasi dalam alur penyelesaian yang lebih luas (Minster dkk., 2021; Drmač dkk., 2018; Chen dan Tan, 2024).

Implikasi untuk pemilihan metode

Pemilihan metode dapat dimulai dengan memperjelas tujuan perhitungan: apakah yang diperlukan terutama kecocokan model, koefisien yang dapat ditafsirkan, atau keduanya. Karakter matriks, termasuk indikasi kolinearitas dan kekurangan peringkat, kemudian membantu menilai sensitivitas hasil. Dalam regresi kuadrat terkecil biasa, Paciorek menempatkan QR sebagai pendekatan baku. Tanpa kolinearitas ekstrem, QR dan pendekatan persamaan normal umumnya memadai menurut pembahasan tersebut (Paciorek, 2024).

Hitungan operasi memberi gambaran tentang biaya relatif, sementara penilaian kestabilan membantu memilih algoritma di antara pilihan yang tersedia. Dalam perbandingan yang dikutip Paciorek dari Monahan, Gram-Schmidt termodifikasi paling stabil dan penyapuan paling kurang stabil. Karena regresi umumnya cepat kecuali p besar, Paciorek menilai selisih biaya yang dibahas jarang perlu terlalu dirisaukan (Paciorek, 2024).

Struktur masalah dapat membuka pilihan yang sekaligus efisien dan stabil. Hasil Minster dan rekan untuk peringkat kecil menunjukkan kompleksitas yang sama antara varian QR atau SVD dan CP-ALS baku, serta waktu jalan yang sama dalam implementasi MATLAB yang dilaporkan, disertai kemungkinan galat aproksimasi lebih rendah. Pada masalah aliran yang dibahas Drmač dan rekan, struktur yang mendukung persamaan normal juga dimanfaatkan dalam algoritma QR. Contoh tersebut memperluas pilihan selain memperlakukan biaya dan kestabilan sebagai pertukaran yang harus terjadi pada setiap masalah (Minster dkk., 2021; Drmač dkk., 2018).

Ketika informasi peringkat menjadi perhatian, QR dengan pemilihan poros atau SVD menyediakan sarana untuk menanganinya. Untuk masalah besar dan jarang, metode iteratif dengan pengondisi awal menawarkan jalur lain (Paciorek, 2024; Chen dan Tan, 2024).

Keterbatasan tinjauan

Sumber yang dibahas mencakup materi kuliah aljabar numerik dan makalah metode komputasi pada tensor, aliran fluida, serta persamaan diferensial parsial. Sumber-sumber tersebut tidak menyajikan pengujian terpadu atas semua metode pada matriks dan perangkat yang sama. Pernyataan tentang biaya dan akurasi karena itu berlaku dalam kondisi masing-masing pembahasan. Tinjauan ini tidak menetapkan ambang bilangan kondisi atau pemenang kinerja yang berlaku umum.

Kesimpulan

Persamaan normal, QR, dan SVD menawarkan cara yang berbeda untuk menangani kuadrat terkecil linear. Persamaan normal dapat efisien ketika struktur masalah dimanfaatkan, sedangkan penguadratan bilangan kondisi menjadikan ketelitian pertimbangan utama. QR menghindari pembentukan persamaan normal sebagai langkah utama dan menjadi pendekatan baku dalam regresi yang dibahas. SVD memberi sarana tambahan untuk masalah yang informasi peringkatnya penting.

Pada dekomposisi tensor berperingkat kecil yang ditelaah, varian QR dan SVD mencapai kompleksitas yang sama dengan algoritma baku serta waktu jalan yang sama dalam implementasi MATLAB yang dilaporkan, dan dapat memberikan galat aproksimasi lebih rendah. Pada sistem besar, QR dan SVD juga dapat berperan dalam pembentukan pengondisi awal untuk penyelesai iteratif. Pemilihan metode memerlukan penilaian atas kondisi dan peringkat matriks, struktur masalah, kebutuhan ketelitian, serta biaya alur komputasi.

Daftar pustaka

  1. Johnson (2019). Week 4 | Introduction to Numerical Methods | Mathematics | MIT OpenCourseWare. MIT OpenCourseWare. https://ocw.mit.edu/courses/18-335j-introduction-to-numerical-methods-spring-2019/pages/week-4/
  2. Paciorek (2024). Numerical linear algebra. University of California, Berkeley. https://stat243.berkeley.edu/fall-2024/units/unit10-linalg.html
  3. Minster dkk. (2021). CP Decomposition for Tensors via Alternating Least Squares with QR Decomposition. arXiv. https://arxiv.org/abs/2112.10855
  4. Drmač dkk. (2018). On least squares problems with certain Vandermonde--Khatri--Rao structure with applications to DMD. arXiv. https://arxiv.org/abs/1811.12562
  5. Chen dan Tan (2024). High-precision randomized iterative methods for the random feature method. arXiv. https://arxiv.org/abs/2409.15818

Pelajari lebih dalam di ARSTEMA Academy