रैखिक बीजीय समीकरणों के सिस्टम को हल करने के तरीकों के बारे में अधिक

सभी तरीकों के बारे में विस्तार से बताना निश्चित रूप से बहुत मुश्किल है, लेकिन यह विषय मेरे लिए दिलचस्प और बेहद महत्वपूर्ण लगता है, क्योंकि हर किसी को अक्सर समाधान खोजने की समस्या का सामना करना पड़ता है। पहले लेख में गॉस क्यों? गॉस विधि का वर्णन किया गया था (संशोधनों के साथ) और कुछ पुनरावृत्त तरीके। हालाँकि, Sinn3r की आलोचना को देखते हुए , मैंने अन्य तरीकों का भी वर्णन करने का निर्णय लिया।

शुरू करो

तो, हमें फिर से आदेश के रैखिक बीजीय समीकरणों की एक प्रणाली को हल करने की आवश्यकता है $$$एन$। सबसे हड़ताली संख्यात्मक विधियों में से एक एक विधि है जो उपयोग करती है $$$लू$-मैट्रिक्स का अपघटन।

यह सहज विधि इस प्रकार है। मान लें कि हमारे पास रैखिक बीजीय समीकरणों की एक प्रणाली है (वेक्टर रूप में लिखित):

$$

$$अक्ष = बी,$$

जहाँ $$$A = (a_ {ij})$- एक भयानक और भ्रामक गैर-पतित मैट्रिक्स। हम इसे दो अन्य मैट्रिक्स के उत्पाद के रूप में दर्शाते हैं: $$$L = (l_ {ij})$एक कम त्रिकोणीय मैट्रिक्स है, और $$$U = (u_ {ij})$ऊपरी त्रिकोणीय मैट्रिक्स है। फिर स्पष्ट रूप से सिस्टम फॉर्म लेता है:

$$

$$एलयूएक्स = बी$$

यदि नामित हो $$$Ux = y$, तब मूल प्रणाली का समाधान दो अन्य प्रणालियों के समाधान से पाया जाता है:

$$

$$लय = बी,$$

$$

$$यूएक्स = वाई$$

इस पद्धति का लाभ यह है कि दो सहायक प्रणालियों के समाधान बहुत सरल हैं (इस तथ्य के कारण कि मैट्रिसेस $$$एल$और $$$यू$- त्रिकोणीय)। लेकिन क्या इन मैट्रिस को ढूंढना आसान है? इसलिए, सिस्टम को हल करने का कार्य भवन के कार्य को कम कर दिया गया है $$$लू$मैट्रिक्स के लिए -ecompositions।

एल्गोरिथ्म के आवेदन का विवरण $$$लू$-decomposition यहाँ पर्याप्त विवरण में वर्णित है । इस बीच, हम एक और तरीका देखेंगे।

वर्गमूल विधि

हम मैट्रिक्स पर अतिरिक्त शर्तें लगाते हैं $$$ए$। हमें आवश्यकता है कि यह सममित हो, अर्थात $$$a_ {ij} = a_ {ji}$या $$$ए ^ टी = ए$। इस तरह के मैट्रिक्स का प्रतिनिधित्व किया जा सकता है

$$

$$A = S ^ tDS,$$

जहाँ $$$एस$- ऊपरी त्रिकोणीय मैट्रिक्स, $$$डी$एक विकर्ण वास्तविक मैट्रिक्स है, और इसके विकर्ण तत्व पूर्ण मूल्य में एकता के बराबर हैं। इसी तरह, मूल प्रणाली दो अन्य के लिए कम हो गई है:

$$

$$S ^ tDy = b,$$

$$

$$Sx = y,$$

जो कि मेट्रिसेस के गुणों के कारण भी हल हो जाते हैं $$$एस$और $$$डी$।

एल्गोरिथम फ़ार्मुलों की व्युत्पत्ति बोझिल है और प्रकाशन के दायरे से परे है। यदि वांछित है, तो उन्हें यहां पाया जा सकता है ।

नमूना जावा कोड जो स्वीप विधि को लागू करता है:

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(); } } 

स्वीप विधि

इस पद्धति का उपयोग करते हुए, प्रत्येक पंक्ति में तीन से अधिक अज्ञात वाले केवल विशिष्ट सिस्टम हल किए जा सकते हैं। वह है, सिस्टम के साथ

$$

$$अक्ष = बी$$

मैट्रिक्स $$$ए$त्रिदलीय है:

$$

$$A = \ start {pmatrix} C_1 & -B_1 & 0 & \ dots & 0 & 0 \\ -A_2 & C_2 & -B_2 और \ dots & 0 & 0 \\ \ 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}।$$

बस ध्यान दें कि पड़ोसी समाधान का एक कनेक्शन है:

$$

$$x_ {i-1} = \ Alpha_ {i-1} x_i + \ Beta_ {i-1},$$

$$$\ Alpha_k, \ Beta_k$- कुछ अज्ञात नंबर। यदि हम उन्हें और एक एकल चर पाते हैं, तो हम अन्य सभी को पा सकते हैं।

सूत्रों की व्युत्पत्ति

$$

$$\ Alpha_1 = \ dfrac {B_1} {C_1}, \ \ Alpha_i = \ dfrac {B_i} {C_i - A_i \ Alpha_ {i-1}}, \ i = \ over \ {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 = \ _ झुकना {। 2, एन}$$

यहाँ मौजूद है । खैर, अंत में

$$

$$x_n = \ dfrac {b_n + A_n \ beta_ {n-1}} {C_n - A_n \ Alpha_ {n-1}}, \ x_i = \ Alpha_i x_ {+ 1} + \ Beta_i, \ i = n- n- 1, एन -2, \ डॉट्स, 1$$

ध्यान दें कि खोज सूत्रों में $$$\ Alpha_i, \ Beta_i$संख्या के आधार पर विभाजन होता है $$$C_i - A_i \ Alpha_ {i-1},$जो शून्य हो सकता है जिसे ट्रैक करने की आवश्यकता है। लेकिन वास्तव में, निम्नलिखित कथन रखता है, जिसका प्रमाण यहां है : स्वीप एल्गोरिथ्म सही और स्थिर है यदि शर्तें संतुष्ट हैं:

$$

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

$$

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

सिस्टम को हल करने वाले जावा प्रोग्राम कोड पर विचार करें।

$$

$$\ बाईं \ {\ _ शुरू करना {संरेखित} & x_1 = 0, \\ & x_ {i-1} + \ xi x_ {i + 1} = \ dfrac {i} {n}, \ (i = \ overline # 2), n-1}), \\ & x_n = 1, \\ \ end {align} \ right$$

पर $$$\ 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(); } }