Ketik matriks persegi, buka tab Dekomposisi, lalu tekan LU(A). Karena jawabannya berupa sepasang matriks dan bukan satu, ia sepenuhnya berada di panel langkah demi langkah, yang terbuka sendiri dan menampilkan L dan U berdampingan di akhir. Cholesky(A) ada di tab yang sama, untuk kasus simetris yang dijelaskan di bawah.
Apa itu kedua faktornya
LU menuliskan A = L·U, dengan L segitiga bawah dan U segitiga atas. Tak satu pun dari keduanya misterius: U persis bentuk eselon baris yang dihasilkan eliminasi Gauss, dan L mencatat pengali yang Anda pakai di sepanjang jalan. Satu kali eliminasi memberi Anda keduanya.
Contoh terselesaikan
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
Angka 3/2 di L adalah pengali yang menolkan angka 6 di bawah pivot. Perhatikan bahwa determinannya kini gratis: kalikan diagonal U dan diperoleh 4 · (−3/2) = −6, dikali −1 untuk setiap penukaran baris yang dilakukan.
Mengapa ini sepadan
Karena faktorisasinya bisa dipakai ulang. Menyelesaikan Ax = b dari nol menghabiskan sekitar n³/3 operasi. Begitu L dan U sudah di tangan, tiap ruas kanan baru hanya menghabiskan n²: selesaikan Ly = b dengan substitusi maju, lalu Ux = y dengan substitusi mundur. Bila Anda menyelesaikan sistem yang sama untuk banyak vektor b berbeda — hal lazim dalam rekayasa dan simulasi — penghematannya luar biasa. Untuk matriks 100×100 dan lima puluh ruas kanan, itu berarti satu faktorisasi ditambah lima puluh lintasan murah, bukan lima puluh eliminasi penuh.
Substitusi maju dan mundur, dikerjakan sampai tuntas
Ambil matriks 3×3 yang dimuat di atas. Satu kali eliminasi memberi kedua faktornya:
| 2 | 1 | 1 |
| 4 | −6 | 0 |
| −2 | 7 | 2 |
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| −1 | −1 | 1 |
| 2 | 1 | 1 |
| 0 | −8 | −2 |
| 0 | 0 | 1 |
Entri L persis pengali yang dipakai selama eliminasi: 2 menolkan angka 4, −1 menolkan −2, dan −1 menolkan sisa di kolom kedua. Sekarang selesaikan Ax = b untuk b = (4, −2, 7). Pertama Ly = b, dari baris atas ke bawah, tiap baris langsung memberi satu nilai baru karena semua yang di kanannya nol:
y₁ = 4; lalu 2·4 + y₂ = −2, jadi y₂ = −10; lalu −4 + 10 + y₃ = 7, jadi y₃ = 1.
Kemudian Ux = y, dari baris bawah ke atas: x₃ = 1; lalu −8x₂ − 2 = −10, jadi x₂ = 1; lalu 2x₁ + 1 + 1 = 4, jadi x₁ = 1. Penyelesaiannya (1, 1, 1), dicapai tanpa satu pun pembagian oleh sesuatu selain entri diagonal. Determinannya jatuh gratis dari faktor yang sama: 2 · (−8) · 1 = −16.
Pivoting
Tidak setiap matriks menerima A = L·U polos: nol di posisi pivot mematahkannya. Perbaikannya adalah matriks permutasi, sehingga menjadi P·A = L·U. Dalam praktik pivoting dipakai bagaimanapun juga, karena memilih pivot terbesar yang tersedia menjaga galat pembulatan tetap terkendali. Faktorisasinya tunggal begitu sebuah kesepakatan ditetapkan; kalkulator ini memakai kesepakatan Doolittle, yang menaruh angka satu di diagonal L.
Cholesky: kasus simetris
Bila A simetris dan definit positif, ia terfaktorkan menjadi A = L·Lᵀ — akar kuadrat untuk matriks, yang cuma butuh satu faktor segitiga. Simetris berarti A = Aᵀ; definit positif berarti setiap nilai eigennya lebih besar dari nol. Kedengarannya membatasi, tetapi matriks semacam itu ada di mana-mana: matriks kovarians, matriks Gram, persamaan normal kuadrat terkecil, dan matriks kekakuan pada metode elemen hingga semuanya simetris definit positif secara alami.
| 4 | 2 |
| 2 | 5 |
| 2 | 0 |
| 1 | 2 |
| 2 | 1 |
| 0 | 2 |
Setiap entri diagonal L adalah akar kuadrat — di sini √4 = 2 dan √(5 − 1²) = 2 — dan karena itulah metode ini menuntut agar besaran di bawah setiap akar tetap positif. Tuntutan itu persis kedefinitan positif, dan ia mengubah algoritmanya menjadi sebuah uji: bila dekomposisinya tuntas, matriksnya definit positif; bila ia menabrak nilai tak positif di bawah akar, berarti bukan. Cholesky kira-kira dua kali lebih cepat daripada LU, memakai separuh memori, dan stabil tanpa pivoting — itulah sebabnya para pemecah menguji kesimetrian lebih dulu dan memakainya kapan pun bisa.
Kesalahan umum
- Mengira setiap matriks bisa difaktorkan. Nol di posisi pivot mematahkan LU polos. Perbaikannya matriks permutasi:
P·A = L·U. - Memakai Cholesky pada matriks tak simetris. A = L·Lᵀ simetris menurut konstruksinya, jadi masukan tak simetris tak punya faktorisasi seperti itu. Pakai LU.
- Mengira kesimetrian sudah cukup. Matriks simetris dengan nilai eigen negatif bersifat tak definit dan akan gagal di tengah algoritma.
- Mengharapkan faktor bilangan bulat. Diagonal Cholesky memuat akar kuadrat, jadi L biasanya irasional meski A tidak.
- Melupakan penukaran baris pada determinan. Tiap penukaran membalik tandanya.