Lebih lanjut tentang metode untuk memecahkan sistem persamaan aljabar linier

Tentu saja sangat sulit untuk mengatakan secara terperinci tentang semua metode, tetapi bagi saya topik ini tampaknya menarik dan sangat penting, karena setiap orang dihadapkan dengan tugas mencari solusi cukup sering. Dalam artikel pertama Mengapa Gauss? metode Gauss dijelaskan (termasuk dengan modifikasi) dan beberapa metode berulang. Namun, mengingat kritik Sinn3r , saya memutuskan untuk menjelaskan metode lain juga.

Mulai lagi dari awal

Jadi, mari kita lagi perlu memecahkan sistem persamaan aljabar linier dari pesanan $$$n$ . Salah satu metode numerik yang paling mencolok adalah metode yang digunakan $$$Lu$ -Komposisi dari matriks.

Metode intuitif ini adalah sebagai berikut. Misalkan kita memiliki sistem persamaan aljabar linier (ditulis dalam bentuk vektor):

$$

$$Ax = b,$$

dimana $$$A = (a_ {ij})$ - Matriks non-degenerasi yang mengerikan dan membingungkan. Kami menyatakannya sebagai produk dari dua matriks lain: $$$L = (l_ {ij})$ Apakah matriks segitiga lebih rendah, dan $$$U = (u_ {ij})$ Apakah matriks segitiga atas. Maka jelas sistem mengambil bentuk:

$$

$$LUx = b.$$

Jika ditunjuk $$$Ux = y$ , maka solusi untuk sistem asli ditemukan dari solusi dua sistem lainnya:

$$

$$Ly = b,$$

$$

$$Ux = y.$$

Keuntungan dari metode ini adalah bahwa solusi dari dua sistem bantu sangat sederhana (karena fakta bahwa matriks $$$L$ dan $$$U$ - segitiga). Tetapi apakah mudah untuk menemukan matriks ini? Jadi, tugas memecahkan sistem direduksi menjadi tugas membangun $$$Lu$ -Komposisi untuk matriks.

Deskripsi penerapan algoritma $$$Lu$ -komposisi dijelaskan secara cukup rinci di sini . Sementara itu, kita akan melihat metode lain.

Metode akar kuadrat

Kami memberlakukan ketentuan tambahan pada matriks $$$A$ . Kami mengharuskan itu simetris, mis. $$$a_ {ij} = a_ {ji}$ atau $$$A ^ t = A$ . Matriks seperti itu dapat direpresentasikan sebagai

$$

$$A = S ^ tDS,$$

dimana $$$S$ - matriks segitiga atas, $$$D$ Adalah matriks nyata diagonal, dan elemen-elemen diagonalnya sama dengan kesatuan dalam nilai absolut. Demikian pula, sistem asli dikurangi menjadi dua lainnya:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

yang juga diselesaikan secara mendasar karena sifat-sifat matriks $$$S$ dan $$$D$ .

Derivasi formula algoritmik agak rumit dan tetap berada di luar lingkup publikasi. Jika diinginkan, mereka dapat ditemukan di sini .

Contoh kode Java yang mengimplementasikan metode sapuan:

import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class SquareRootMethod { public static void main(String[] args) throws FileNotFoundException { Scanner scanner = new Scanner(new FileReader("input.txt")); scanner.useLocale(Locale.US); int n = scanner.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] = scanner.nextDouble(); } b[i] = scanner.nextDouble(); } double[] x = new double[n + 1]; double[] d = new double[n + 1]; double[][] s = new double[n + 1][n + 1]; // for i = 1 d[1] = Math.signum(a[1][1]); s[1][1] = Math.sqrt(Math.abs(a[1][1])); for (int j = 2; j <= n; j++) { s[1][j] = a[1][j] / (s[1][1] * d[1]); } // for i > 1 //searching S and D matrix for (int i = 2; i <= n; i++) { double sum = 0; for (int k = 1; k <= i - 1; k++) { sum += s[k][i] * s[k][i] * d[k]; } d[i] = Math.signum(a[i][i] - sum); s[i][i] = Math.sqrt(Math.abs(a[i][i] - sum)); double l = 1 / (s[i][i] * d[i]); for (int j = i + 1; j <= n; j++) { double SDSsum = 0; for (int k = 1; k <= i - 1; k++) { SDSsum += s[k][i] * d[k] * s[k][j]; } s[i][j] = l * (a[i][j] - SDSsum); } } //solve of the system (s^t * d)y = b double[] y = new double[n + 1]; y[1] = b[1] / (s[1][1] * d[1]); for (int i = 2; i <= n; i++) { double sum = 0; for (int j = 1; j <= i - 1; j++) { sum += s[j][i] * d[j] * y[j]; } y[i] = (b[i] - sum) / (s[i][i] * d[i]); } //solve of the system sx = y x[n] = y[n] / s[n][n]; for (int i = n - 1; i >= 1; i--) { double sum = 0; for (int k = i + 1; k <= n; k++) { sum += s[i][k] * x[k]; } x[i] = (y[i] - sum) / s[i][i]; } //output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i++) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } } 

Metode sapuan

Dengan menggunakan metode ini, hanya sistem spesifik dengan tidak lebih dari tiga yang tidak diketahui di setiap baris yang dapat dipecahkan. Yaitu, dengan sistem

$$

$$Ax = b$$

matriks $$$A$ adalah tridiagonal:

$$

$$A = \ begin {pmatrix} C_1 & -B_1 & 0 & \ dots & 0 & 0 \\ -A_2 & C_2 & -B_2 & \ dots & 0 & 0 \\ \ vdots & \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ vdots \\ 0 & 0 & \ dots & -A_ {n-1} & C_ {n-1} & -B_ {n-1} \\ 0 & 0 & \ dots & 0 & -A_n & C_n \\ \ end {pmatrix}.$$

Perhatikan bahwa ada koneksi solusi tetangga:

$$

$$x_ {i-1} = \ alpha_ {i-1} x_i + \ beta_ {i-1},$$

$$$\ alpha_k, \ beta_k$ - beberapa nomor tidak dikenal. Jika kita menemukan mereka dan satu variabel tunggal, kita dapat menemukan yang lainnya.

Penurunan formula

$$

$$\ alpha_1 = \ dfrac {B_1} {C_1}, \ \ alpha_i = \ dfrac {B_i} {C_i - A_i \ alpha_ {i-1}}, \ i = \ overline {2, n},$$

$$

$$\ beta_1 = \ dfrac {b_1} {C_1}, \ \ beta_i = \ dfrac {b_i + A_i \ beta_ {i-1}} {C_i - A_i \ alpha_ {i-1}}, \ i = \ overline { 2, n}$$

hadir di sini . Yah, pada akhirnya

$$

$$x_n = \ dfrac {b_n + A_n \ beta_ {n-1}} {C_n - A_n \ alpha_ {n-1}}, \ x_i = \ alpha_i x_ {i + 1} + \ beta_i, \ i = n- 1, n-2, \ dots, 1$$

Perhatikan bahwa dalam rumus pencarian $$$\ alpha_i, \ beta_i$ ada pembagian berdasarkan nomor $$$C_i - A_i \ alpha_ {i-1},$ yang mungkin berubah menjadi nol yang perlu dilacak. Namun pada kenyataannya, pernyataan berikut ini berlaku, buktinya ada di sini : algoritma sweep benar dan stabil jika kondisinya terpenuhi:

$$

$$C_1, C_n \ neq 0, A_i, B_i \ neq 0 \ (i = \ overline {2, n}),$$

$$

$$| C_i | \ geq | A_i | + | B_i |.$$

Pertimbangkan kode program Java yang memecahkan sistem.

$$

$$\ left \ {\ begin {aligned} & x_1 = 0, \\ & x_ {i-1} + \ xi x_ {i + 1} = \ dfrac {i} {n}, \ (i = \ overline {2, n-1}), \\ & x_n = 1, \\ \ end {aligned} \ kanan.$$

di $$$\ xi = 2, n = 21$ .

 package SystemOfLinearAlgebraicEquations; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.PrintWriter; import java.util.Locale; import java.util.Scanner; public class TridiagonalMatrixAlgorithm { public static void main(String[] args) throws FileNotFoundException { final int n = 21; double[] A = new double[n + 1]; double[] B = new double[n + 1]; double[] C = new double[n + 1]; double[] F = new double[n + 1]; double xi = 2; C[1] = 1; F[1] = 0; for(int i = 2; i <= n-1; i++) { A[i] = 1; C[i] = xi; B[i] = 1; F[i] = - (double) i / n; } A[n] = 0; C[n] = 1; F[n] = 1; double[] alpha = new double[n + 1]; double[] beta = new double[n + 1]; // right stroke alpha[1] = B[1] / C[1]; beta[1] = F[1] / C[1]; for (int i = 2; i <= n - 1; i++) { double denominator = C[i] - A[i] * alpha[i-1]; alpha[i] = B[i] / denominator; beta[i] = (F[i] + A[i] * beta[i - 1]) / denominator; } double[] x = new double[n + 1]; // back stroke x[n] = (F[n] + A[n] * beta[n - 1]) / (C[n] - A[n] * alpha[n - 1]); for (int i = n - 1; i >= 1; i--) { x[i] = alpha[i] * x[i + 1] + beta[i]; } // output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 1; i <= n; i = i + 5) { pw.printf(Locale.US, "x%d = %f\n", i, x[i]); } pw.flush(); pw.close(); } }