A.7 · Faktorisasi LU dan nulitas pemetaan majemuk

Persiapan GRE tingkat sarjana. Tujuan lokal dalam cakupan ETS yang ditinjau; ini adalah pengajaran orisinal, bukan uji coba resmi atau prediktor skor.

Prasyarat: Operasi baris, sistem segitiga, dan rank-nullity.

• Menyelesaikan sistem linear terfaktor dengan substitusi maju dan mundur
• Menerapkan permutasi baris secara konsisten ketika pivot diperlukan
• Membatasi dimensi kernel komposisi menggunakan irisan gambar-kernel

substitusi maju: Menyelesaikan sistem segitiga bawah dari persamaan pertamanya ke bawah.

nullitas: Dimensi kernel pemetaan linear.

Faktorisasi A=LU mengekspresikan matriks persegi sebagai segitiga bawah L dan segitiga atas U. Dengan diagonal unit L, substitusi maju sangat sederhana. Matriks yang dapat dibalik mungkin tidak menerima bentuk ini tanpa pertukaran baris: pivot utama nol dapat memerlukan permutasi. Untuk PA=LU, selesaikan Ly=Pb, kemudian Ux=y. Permutasi bertindak pada sisi kanan serta matriks koefisien. Pivot utama principal yang tidak nol membenarkan eliminasi tanpa pertukaran biasa, bukan sekadar keterbalikan saja.

Dalam Ly=b, hitung y dari atas ke bawah, mengurangkan suku-suku yang sudah diketahui; bagi dengan diagonal saat ini kecuali jika satu. Dalam Ux=y, hitung x dari bawah ke atas. Untuk setiap persamaan substitusikan kembali ke baris asli sebagai pemeriksaan. Menggunakan LU ulang untuk banyak sisi kanan menghindari pengulangan eliminasi: faktorisasi padat membutuhkan kerja orde kubik dalam dimensi, sedangkan setiap penyelesaian segitiga membutuhkan kerja orde kuadratik. Aritetika eksak dapat memeriksa contoh kecil; penumpukan numerik mengurangi beberapa masalah pembulatan tetapi tidak dapat menghilangkan ketidakberadaan kondisi yang melekat.

Untuk B:V→W dan A:W→Z, ker B terkandung dalam ker(A∘B), namun yang terakhir bisa lebih besar. Vektor tambahan adalah mereka yang dipetakan oleh B ke dalam ker A. Batasi B pada ker(A∘B): gambarannya adalah im B∩ker A dan kernelnya adalah ker B. Rank-nullity pada peta terbatas ini memberikan dim ker(A∘B)=dim ker B+dim(im B∩ker A). Irisan, bukan seluruh kernel A, menentukan nullitas tambahan.

Untuk endomorfisme R⁶ dengan nullitas A=2 dan nullitas B=3, rank B=3, dan dimensi irisan dapat berkisar dari 0 hingga 2. Dengan demikian, nullitas A∘B berkisar dari 3 hingga 5. Batas-batas bergantung pada ruang perantara bersama: untuk subruang berdimensi r dan s dalam ruang m-dimensi, irisan mereka memiliki dimensi antara max(0,r+s−m) dan min(r,s). Membalik komposisi dapat mengubah nullitasnya, meskipun AB dan BA keduanya terdefinisi. Pilihlah ruang yang kompatibel sebelum menerapkan rumus-rumus ini.

Misalkan L=[[1,0,0],[2,1,0],[−1,3,1]], U=[[2,1,−1],[0,3,2],[0,0,4]], dan b=(−1,−1,12). Substitusi maju memberi y=(−1,1,8). Substitusi mundur memberi x₃=2, x₂=(1−4)/3=−1, dan x₁=(−1−(−1)+2)/2=1. Oleh karena itu x=(1,−1,2). Mengalikan Ux memberi y dan mengalikan Ly memberi b, memeriksa urutan faktorisasi secara independen.

Selesaikan dengan L terlebih dahulu dan U kedua, serta permute b jika PA=LU. Nullitas komposisi tidak otomatis merupakan jumlah dari dua nullitas; hanya irisan image-kernel yang menambah nullitas B.

Misalkan $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$, $U=\begin{pmatrix}3&1\\0&2\end{pmatrix}$, dan $b=(5,12)^T$. Selesaikan LUx=b dan verifikasi pada matriks hasil kali. Untuk PA=LU, di mana P bekerja saat menyelesaikan Ax=b?

Penyelesaian terarah

Pertama selesaikan Ly=b: $y_1=5$, $2y_1+y_2=12$, sehingga $y_2=2$. Kemudian Ux=y menghasilkan $x_2=1$ dan $3x_1+1=5$, sehingga $x_1=4/3$. Matriks hasil kalinya adalah $A=\begin{pmatrix}3&1\\6&4\end{pmatrix}$; menerapkannya ke $(4/3,1)^T$ menghasilkan $(5,12)^T$. Jika PA=LU, kalikan persamaan asli dengan P dan selesaikan Ly=Pb, diikuti oleh Ux=y. Mengabaikan P pada b akan menyelesaikan sistem yang berbeda.

Misalkan A dan B adalah endomorfisme dari $\mathbb R^5$ dengan nullitas dua dan tiga, masing-masing. Temukan semua kemungkinan nullitas AB, dan justifikasikan batas serta ketercapaiannya.

Periksa setelah mencoba

Rank B adalah dua. Restriksi B ke $\ker(AB)$ untuk mendapatkan

Kedua subruang dalam irisan tersebut masing-masing memiliki dimensi dua dalam lima dimensi, sehingga dimensi irisan mungkin nol, satu, atau dua. Dengan demikian, nullitasnya adalah 3, 4, atau 5. Untuk merealisasikan setiap kasus, ambil $\ker A=\operatorname{span}(e_1,e_2)$ dan citra B sebagai $\operatorname{span}(e_3,e_4)$, $\operatorname{span}(e_1,e_3)$, atau $\operatorname{span}(e_1,e_2)$. Pilih sembarang B berank dua yang memetakan ke citra tersebut. Konstruksi-konstruksi ini membuktikan ketercapaian, bukan hanya batas interval yang longgar.