Apa yang akan Anda lakukan jika Anda diminta menyelesaikan sistem sederhana dengan tiga hal yang tidak diketahui? Masing-masing telah membentuk pendekatannya sendiri dan yang paling nyaman baginya secara pribadi. Ada banyak cara untuk menyelesaikan sistem persamaan aljabar linier. Tetapi mengapa preferensi diberikan secara khusus untuk metode Gauss?
Hal pertama yang pertama
Mari kita mulai dengan yang sederhana. Biarkan sistem persamaan linear dari urutan ketiga diberikan:
$$ menampilkan $$ \ kiri \ {\ mulai {sejajar} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {21} x_1 + a_ {22} x_2 + a_ { 23} x_3 = b_2, \\ a_ {31} x_1 + a_ {32} x_2 + a_ {33} x_3 = b_3. \\ \ end {aligned} \ right. $$ menampilkan $$
Metode Gauss terdiri dari “penghancuran” secara berurutan istilah-istilah di bawah diagonal utama. Pada langkah pertama, persamaan pertama dikalikan dengan
$ inline $ \ dfrac {a_ {21}} {a_ {11}} $ inline $ dan dikurangkan dari yang kedua (dan dikalikan dengan
$ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ dan dikurangi dari yang ketiga). Yaitu, setelah konversi ini, kami mendapatkan yang berikut:
$$ menampilkan $$ \ kiri \ {\ mulai {sejajar} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {22} 'x_2 + a_ {23}' x_3 = b_2 ', \\ a_ {32}' x_2 + a_ {33} 'x_3 = b_3'. \\ \ end {aligned} \ right. $$ menampilkan $$
Sekarang persamaan kedua dikalikan dengan
$ inline $ \ dfrac {a_ {32} '} {a_ {22}'} $ inline $ dan dikurangkan dari yang ketiga:
$$ menampilkan $$ \ kiri \ {\ mulai {sejajar} a_ {11} x_1 + a_ {12} x_2 + a_ {13} x_3 = b_1, \\ a_ {22} 'x_2 + a_ {23}' x_3 = b_2 ', \\ a_ {33}' 'x_3 = b_3' '. \\ \ end {aligned} \ right. $$ menampilkan $$
Kami punya sistem yang cukup sederhana, yang mudah ditemukan
$ inline $ x_3 $ inline $ lalu
$ inline $ x_2 $ inline $ dan
$ inline $ x_1 $ inline $ .
Pembaca yang penuh perhatian pasti akan memperhatikan: bagaimana jika elemen diagonal sama dengan nol? Apa yang harus dilakukan jika, misalnya,
$ inline $ a_ {11} = 0 $ inline $ ? Apakah metode Gauss yang terkenal berakhir di sana?
Tidak ada yang perlu dikhawatirkan! Ayo temukan
$ inline $ \ max | a_ {1j} | $ inline $ dan bertukar
$ inline $ j $ inline $ baris ke-1 dan ke-1 (tanpa kehilangan sifat umum, anggaplah itu
$ inline $ \ max | a_ {1j} | = a_ {13} $ inline $ ) Perhatikan bahwa saat semuanya
$ inline $ a_ {1j} = 0 $ inline $ tidak mungkin, karena dalam hal ini penentu matriks koefisien menghilang dan tidak mungkin untuk menyelesaikan sistem. Jadi, setelah mengatur ulang persamaan ke-3 pada baris pertama, kami melakukan langkah-langkah yang dijelaskan sebelumnya.
Pencarian untuk elemen modulo maksimum dapat ditangani pada setiap iterasi, yaitu di
$ inline $ k $ inline $ -Iterasi yang harus dicari
$ inline $ \ max | a_ {kj} | $ inline $ lalu ubah
$ inline $ j $ inline $ dan
$ inline $ k $ inline $ garis th. Algoritma di mana elemen maksimum dalam kolom dicari disebut metode Gauss dengan pilihan elemen utama di kolom.
Ada cara lain. Bisa di
$ inline $ k $ inline $ -Iterasi yang harus dicari
$ inline $ \ max | a_ {ik} | $ inline $ , lalu ubah bukan baris, tetapi kolom. Tetapi penting untuk mengingat indeks kolom yang berubah dalam beberapa array
$ inline $ \ alpha $ inline $ (lalu untuk mengembalikan urutan variabel yang tepat).
Contoh kode sederhana yang mengimplementasikan algoritma ini:
import java.io.FileReader; import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.Locale; import java.util.Scanner; public class GuassianEliminationSearchMainElementsAtString { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1];
Mengapa Gauss?
Ada cara lain untuk menyelesaikan SLAE. Salah satunya adalah metode Cramer. Ini terdiri dalam perhitungan awal sejumlah faktor penentu, dengan bantuan yang nilai variabelnya langsung dihitung. Di bawah sistem asli, metode ini akan terlihat seperti ini:
$$ menampilkan $$ \ Delta = \ begin {vmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \\ a_ {31} & a_ {32} & a_ {33} \\ \ end {vmatrix}, \ Delta_1 = \ begin {vmatrix} b_1 & a_ {12} & a_ {13} \\ b_2 & a_ {22} & a_ {23} \ \ b_3 & a_ {32} & a_ {33} \\ \ end {vmatrix}, $$ menampilkan $$
$$ menampilkan $$ \ Delta_2 = \ begin {vmatrix} a_ {11} & b_1 & a_ {13} \\ a_ {21} & b_2 & a_ {23} \\ a_ {31} & b_3 & a_ {33} \\ \ end {vmatrix}, \ Delta_3 = \ begin {vmatrix} a_ {11} & a_ {12} & b_1 \\ a_ {21} & a_ {22} & b_2 \\ a_ {31} & a_ {32 } & b_3 \\ \ end {vmatrix}, $$ menampilkan $$
$$ menampilkan $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ menampilkan $$
Tapi ingat - apa itu kualifikasi?
Menurut definisi, penentu matriks
$ inline $ A = (a_ {ij}) $ inline $ ada jumlahnya
$$ menampilkan $$ \ jumlah \ limit_ {1 \ leq i_1 <\ dots <i_n \ leq n} (-1) ^ {N (i_1, \ dots, i_n)} a_ {1i_1} \ dots a_ {ni_n}, $$ tampilan $$
dimana
$ inline $ N (i_1, \ dots, i_n) $ inline $ - wildcard
$ inline $ i_1, \ dots, i_n. $ inline $
Penentu mengandung
$ inline $ n! $ inline $ ketentuan Untuk menyelesaikan sistem, Anda perlu menghitung
$ inline $ n + 1 $ inline $ penentu. Pada cukup besar
$ inline $ n $ inline $ ini sangat mahal. Misalnya kapan
$ inline $ n = 12 $ inline $ jumlah operasi menjadi
$ inline $ 12! (12 + 1) = 6227020800, $ inline $ sedangkan metode Gauss dengan asimptotik
$ inline $ n ^ 3 $ inline $ hanya akan membutuhkan
$ inline $ 12 ^ 3 = 1728 $ inline $ operasi.
Metode berulang
Apa yang disebut metode iteratif juga cocok sebagai algoritma untuk menyelesaikan SLAEs. Mereka terdiri dalam menghitung perkiraan secara berurutan sampai salah satu dari mereka sedekat mungkin dengan jawaban yang tepat.
Pertama, beberapa vektor acak dipilih
$ inline $ x ^ 0 $ inline $ Merupakan pendekatan nol. Vektor dibangun di atasnya.
$ inline $ x ^ 1 $ inline $ - ini adalah perkiraan pertama. Dan sebagainya. Perhitungan berakhir ketika
$ sebaris $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ inline $ dimana
$ inline $ \ varepsilon $ inline $ - beberapa nilai yang ditetapkan sebelumnya. Ketidaksetaraan terakhir berarti bahwa "peningkatan" solusi kami dengan setiap iterasi hampir tidak signifikan.
Pertimbangkan metode Jacobi yang populer, yang merupakan salah satu metode iteratif paling sederhana untuk menyelesaikan SLAEs.
Untuk memulai, kami menulis sistem dalam bentuk berikut:
$$ menampilkan $$ \ jumlah \ limit_ {j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n}. $$ tampilan $$
Terpisah
$ inline $ i $ inline $ - Istilah dan ungkapkan melalui yang lain:
$$ menampilkan $$ x_i = \ dfrac {b_i - \ jumlah \ limit_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}. $$ display $ $
Sekarang gantung "counter" pada variabel dan dapatkan metode iterasi Jacobi:
$$ menampilkan $$ x_i ^ k = \ dfrac {b_i - \ jumlah \ limit_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}}, \ i = \ overline {1, n}, \ k = 0,1, \ titik-titik $$ menampilkan $$
Perhatikan bahwa prasyarat untuk menggunakan metode ini adalah tidak adanya nol di sepanjang diagonal utama.
Implementasi metode Jacobi di Jawa:
Sebagai a $ inline $ \ varepsilon $ inline $ diambil epsilon mesin pra-perhitungan diambil. import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class JacobiMethod { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; double[] x0 = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); x0[i] = b[i] / a[i][i]; } double EPS = EPSCalc(); double[] x = new double[n+1]; double norm = Double.MAX_VALUE; int counter = 0; do{ for(int i = 1; i <= n; i++) { double sum = 0; for(int j = 1; j <= n; j++) { if(j == i) continue; sum += a[i][j] * x0[j]; } x[i] = (b[i] - sum) / a[i][i]; } norm = normCalc(x0, x, n); for(int i = 1; i <= n; i++) { x0[i] = x[i]; } counter++; } while(norm > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x0[i]); } pw.flush(); pw.close(); } static double normCalc(double []x1, double[] x2, int n) { double sum = 0; for(int i = 1; i <= n; i++) { sum += Math.abs(x1[i] - x2[i]); } return sum; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } }
Modifikasi metode Jacobi adalah metode relaksasi. Perbedaan utamanya adalah bahwa dengan bantuan parameter yang dipilih sebelumnya, jumlah iterasi berkurang secara signifikan. Mari kita jelaskan secara singkat ide utama metode ini.
Dari sistem asli, kami sekali lagi mengekspresikan
$ inline $ x $ inline $ , tapi mari kita mengatur penghitung sedikit berbeda dan menambahkan parameter
$ inline $ \ omega $ inline $ :
$$ menampilkan $$ x_i ^ k = \ dfrac {\ omega \ kiri (b_i - \ jumlah \ limit_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k + 1} - \ jumlah \ limit_ {j = i + 1} ^ n a_ {ij} x_j ^ k \ kanan)} {a_ {ii}} + (1- \ omega) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ titik. $$ menampilkan $$
Di
$ inline $ \ omega = 1 $ inline $ semuanya berubah menjadi metode Jacobi.
Jadi, kami akan mencari beberapa "baik"
$ inline $ \ omega $ inline $ . Tetapkan beberapa nomor
$ inline $ s $ inline $ dan kami akan mengambil nilai
$ inline $ \ omega \ in (0,2) $ inline $ , untuk masing-masing kita akan mempertimbangkan norma-norma
$ inline $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s} $ inline $ . Untuk yang terkecil dari norma-norma ini, ingat nilai ini
$ inline $ \ omega $ inline $ , dan dengan itu kita akan menyelesaikan sistem kita.
Ilustrasi metode Jawa:
disini $ inline $ s = 5 $ inline $ import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SuccessiveOverRelaxation { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner(new FileReader("input.txt")); sc.useLocale(Locale.US); int n = sc.nextInt(); double[][] a = new double[n + 1][n + 1]; double[] b = new double[n + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); } double EPS = EPSCalc(); double w = bestRelaxationParameterCalc(a, b, n); double[] x = new double[n + 1]; int counter = 0; double maxChange = Double.MAX_VALUE; do { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm ; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } counter++; } while(maxChange > EPS); PrintWriter pw = new PrintWriter("output.txt"); pw.println(w + " is the best relaxation parameter"); pw.println(counter + " iterations"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } static double bestRelaxationParameterCalc(double[][]a, double[]b, int n) { double bestW = 1, bestMaxChange = Double.MAX_VALUE; for (double w = 0.05; w <= 2; w += 0.05) { double[] x = new double[n + 1]; double maxChange = 0; for (int s = 0; s < 5; s++) { maxChange = 0; for (int i = 1; i <= n; i++) { double firstSum = 0; for (int j = 1; j <= i - 1; j++) { firstSum += a[i][j] * x[j]; } double secondSum = 0; for (int j = i + 1; j <= n; j++) { secondSum += a[i][j] * x[j]; } double lastTerm = (1 - w) * x[i]; double z = (b[i] - firstSum - secondSum); double temp = (w * z) / a[i][i] + lastTerm; maxChange = Math.max(maxChange, Math.abs(x[i] - temp)); x[i] = temp; } } if (maxChange < bestMaxChange) { bestMaxChange = maxChange; bestW = w; } } return bestW; } static double EPSCalc () { double eps = 1; while (1 + eps > 1) { eps /= 2; } return eps; } }
Alih-alih sebuah kesimpulan
Ada banyak lagi algoritma untuk menyelesaikan SLAE. Misalnya, metode akar kuadrat, di mana sistem yang diinginkan digantikan oleh dua sistem "sederhana", solusinya dihitung dengan rumus dasar; metode sapuan, yang digunakan untuk matriks tridiagonal khusus. Semua orang memilih metode mana yang akan digunakan untuk masalahnya.