Ukur tujuh kali - potong sekali, atau gunakan pepatah dalam praktik

Saya duduk di kursus Coursera. Kursus ini ditujukan untuk pemula di Jawa, dan di salah satu tutorial video topik 7 Langkah untuk Mengatasi Masalah diangkat .

Saya, dengan hati nurani yang jernih, mendengarkan tutorial video, berpikir dalam hati, hal ini telah berlangsung lama.

Sisa kursus itu mudah, santai. Tetapi, pada salah satu mata pelajaran di universitas, yaitu dalam apa yang disebut “Pemrograman Ilmiah”, tugas berikut muncul:

Memecahkan sistem persamaan linear $$$Ax=b$menggunakan ekspansi matriks berikut $$$A$:

$$

$$A = LU,$$

Dimana $$$L$Apakah matriks segitiga bawah, dan $$$U$Apakah matriks segitiga atas.

Topik aljabar linier, yang kami ambil pada kursus pertama. Terus terang, saya ingat prinsip-prinsip umum operasi dengan matriks, vektor, dan yang suci - metode Gauss. Jika Anda memikirkannya dengan otak, maka kami tidak mempelajari dekomposisi LU apa pun, tetapi metode Google selalu membantu. Terselamatkan, sampai saat ini.

Saya menemukan algoritma umum untuk menemukan matriks $$$L$dan $$$U$, tapi pada jam setengah tiga pagi tidak ada kopi memberi saya kesempatan untuk menerapkannya dengan benar (mengingat bahwa kami memberi kode pada Octave). Pada akhirnya, saya ketakutan, dan memutuskan untuk tetap mendengarkan pepatah bernama cerdik.

1. Jelaskan masalah dengan tangan

Yang tidak Anda miliki dalam hidup adalah memahami apa masalahnya sebenarnya. Mari kita ambil contoh masalah di atas dan menulisnya di selembar kertas. Dalam cara yang baik, kondisi berikut untuk keberadaan matriks harus dipenuhi$$$L$ dan $$$U$:

- matriks invers harus ada$$$A$, Maksudku $$$\exists{A^{-1}}$;
- semua anak di bawah umur utama tidak boleh merosot, yaitu$$$\Delta_{(1,...,n)}\neq{0}$

Nah, itu sebabnya kita setidaknya membutuhkan "tes bodoh", karena pasti ada orang pintar yang ingin menggunakan matriks yang tidak cocok untuk kita. Tapi untuk sekarang, mari kita hilangkan.

Masalahnya jelas bagi kami: temukan matriks$$$L$ dan $$$U$yang akan jatuh dalam kondisi di atas. Setelah mencoba google metode solusi, kecil kemungkinan Anda akan dapat mengimplementasikan algoritma dengan benar pertama kali (jika Anda tidak pandai aljabar linier). Setelah melalui banyak upaya, kemungkinan besar kita akan mengembangkan beberapa urutan tindakan untuk menyelesaikan masalah kita, dan kemudian kita melanjutkan ke langkah 2.

2. Jelaskan apa yang Anda lakukan

Ambil matriks sebagai contoh

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 1&-1&0 \end{pmatrix}.$$

Sekarang kita menerapkan metode Gauss kita untuk itu dan menyingkirkan elemen tambahan di baris 3, dengan mengurangi baris pertama dari itu, dikalikan dengan rasio elemen pertama dari 3 baris ke elemen pertama dari 1 baris:

$$

$$a_3=a_3-a_1 \cdot\frac { {a_3}_1 }{ {a_1}_1 }.$$

Sekarang, singkirkan elemen kedua dari 3 baris dengan tindakan serupa:

$$

$$a_3=a_3-a_2 \cdot\frac { {a_3}_2 }{ {a_2}_2 }.$$

Sebagai hasilnya, kami mendapatkan matriks

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 0&0&0 \end{pmatrix}=U.$$

Dan sekarang, koefisien yang kami temukan (hasil dari rasio elemen $$$\frac{{a_i}_j}{{a_j}_j}$) ambil nilai dari matriks $$$L$, dan dapatkan

$$

$$L = \begin{pmatrix} 1&0&0 \newline 0&1&0 \newline 1&\frac{1}{2}&1 \end{pmatrix}.$$

Melihat melalui templat, bukan?

3. Menemukan pola

Pada tahap ini, kemungkinan besar, Anda akan kembali ke langkah 1 dan 2, karena templat yang tidak selalu Anda temukan akan berlaku untuk semua kasus. Tapi tidak ada, karena tidak berhasil, itu akan terjadi selanjutnya.

Jadi, berdasarkan contoh, kita dapat merumuskan algoritma / solusi template berikut:

1. Tentukan matriks kuadrat$$$A, n$pesanan th;
2. Atur matriks$$$L = I$dimana $$$I$- matriks identitas $$$n$pesanan th;
3. Atur matriks$$$U = A$;
4. Kami menerapkan transformasi berturut-turut berikut untuk matriks, asalkan$$$\begin{cases} i=2,\ldots, n \newline j=1,\ldots,i \end{cases}$

$$

$$\begin{array}{c} {l_i}_j=\frac{{u_i}_j}{{u_j}_j} \newline u_i = u_i-u_j\cdot{{{l_i}_j}} \end{array},$$

Di $$$n = 3$kita mendapatkan:

$$

$$L = \begin{pmatrix} 1&0&0 \newline {l_2}_1&1&0 \newline {l_3}_1&{l_3}_2&1 \end{pmatrix},\quad U = \begin{pmatrix} {u_1}_1&{u_1}_2&{u_1}_3 \newline 0&{u_2}_2&{u_2}_3 \newline 0&0&{u_3}_3 \end{pmatrix}$$

4. Memeriksa template / algoritma

Ada algoritma - ada jutaan matriks untuk mengujinya! Anda tidak dapat khawatir tentang template ini, itu jelas benar (secara pribadi diuji pada yang paling tidak merosot dari matriks yang mungkin). Tapi ingat: cepatlah - Anda membuat orang tertawa . Jadi selalu periksa templat yang Anda buat sehingga Anda tidak terus melompat seperti keparat sampai awal.

5. Penerjemahan algoritma ke dalam kode

Langkah yang jelas, semua yang Anda butuhkan sering sudah dalam sintaks bahasa, dan jika tidak, tidak ada yang mengganggu Anda untuk membuat kelas dan fungsi untuk menyelesaikan masalah ini, maka Anda memiliki algoritma. Karena saya menerapkan algoritme ini sebagai bagian dari program universitas pendidikan, saya hanya bisa menggunakan Oktaf untuk implementasi, jadi semua kode yang saya berikan kepada Anda ada dalam sintaksnya (sangat mirip dengan Python, jadi saya akan menggunakan highlightnya untuk memformat):

A = input("Enter the matrix A: ")
numOfRows = size(A, 1)
numOfCols = size(A, 2)

if numOfRows ~= numOfCols
    disp("Wrong matrix.")
else
    n = numOfCols
    disp("----------------")
    L = eye(3)
    disp("Making U = A")
    U = A
    disp("----------------")

    for i=2:n
        disp("Step "), disp(i-1)
        for j=1:i-1
            L(i,j) = U(i,j)/U(j,j)
            U(i,:) = U(i,:) - U(j,:)*L(i,j)
        end
        disp("----------------")
    end

    disp("Check the answer of L*U: "), disp(L*U)
end

6. Cari tes yang gagal

Anda harus selalu mencoba untuk "memecahkan" kode Anda. Di sini (jelas) tidak ada "perlindungan dari si bodoh" yang lengkap, tetapi saya mengambil sebagai dasar asumsi bahwa matriks yang semula benar akan diperkenalkan.

Pada langkah ini, Anda harus menemukan semua kemungkinan kesalahan, ketidakakuratan dalam kode Anda, sebagai akibatnya bias dari algoritma yang dibangun juga dapat terungkap. Karena itu, di sini Anda harus mencoba sebanyak mungkin kelalaian yang bisa dibuat.

7. Debug gagal tes

Langkah-langkah yang paling logis, dan mungkin diharapkan. Kode harus bias dan algoritma diperbaiki. Tidak ada lagi yang bisa ditambahkan di sini.

Kesimpulan

Saya dapat mengatakan bahwa tidak mungkin saya akan serius mengambil pendekatan ini untuk menyelesaikan masalah, jika bukan karena keadaan mengantuk saya. Tetapi perlu memperhatikan metode ini - metode ini pendek, dan semua kesusahannya hanya karena fakta bahwa itu harus digunakan.

Catatan

Berkat buku teks aljabar linier untuk bahan untuk memecahkan masalah.