गॉस क्यों? (समीकरणों को हल करने के 100 तरीके)

यदि आपको तीन अज्ञात के साथ एक सरल प्रणाली को हल करने के लिए कहा जाए तो आप क्या करेंगे? प्रत्येक ने व्यक्तिगत रूप से उसके लिए अपना और सबसे सुविधाजनक दृष्टिकोण बनाया है। रैखिक बीजीय समीकरणों की एक प्रणाली को हल करने के कई तरीके हैं। लेकिन विशेष रूप से गॉस पद्धति को वरीयता क्यों दी जाती है?

पहले चीजें पहले

चलो एक साधारण से शुरू करते हैं। तीसरे क्रम के रैखिक समीकरणों की एक प्रणाली दी जाए:

$$$ $ $ $ $ \ बायाँ {\ _ \ _ शुरू {गठबंधन} 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। \\ \ अंत {संरेखित} \ सही। $ $ $ $ प्रदर्शित

गॉस विधि मुख्य विकर्ण के नीचे शब्दों को क्रमिक रूप से "नष्ट" कर रही है। पहले चरण में, पहला समीकरण गुणा किया जाता है$$ $ इनलाइन $ \ dfrac {a_ {21}} {a_ {11}} $ इनलाइन $ और दूसरे से घटाया (और इसी तरह से गुणा किया गया$$ $ इनलाइन $ \ dfrac {a_ {31}} {a_ {11}} $ इनलाइन $ और तीसरे से घटाया गया)। अर्थात्, इस रूपांतरण के बाद, हम निम्नलिखित प्राप्त करते हैं:

$$$ $ $ $ $ \ बायाँ {\ _ \ _ शुरू करना {संरेखित करना} 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'। \\ \ अंत {संरेखित} \ सही। $ $ $ $ प्रदर्शित

अब दूसरे समीकरण से गुणा किया जाता है$$ $ इनलाइन $ \ dfrac {a_ {32} '} {a_ {22}'} $ इनलाइन $ और तीसरे से घटाया गया:

$$$ $ $ $ $ \ बायाँ {\ _ \ _ शुरू करना {संरेखित करना} 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' '। \\ \ अंत {संरेखित} \ सही। $ $ $ $ प्रदर्शित

हमें एक काफी सरल प्रणाली मिली, जिससे इसे खोजना आसान है$$ $ इनलाइन $ x_3 $ इनलाइन $ तो$$ $ इनलाइन $ x_2 $ इनलाइन $ और$$ $ इनलाइन $ x_1 $ इनलाइन $ ।

एक चौकस पाठक निश्चित रूप से नोटिस करेगा: क्या होगा यदि विकर्ण तत्व शून्य के बराबर हैं? उदाहरण के लिए, क्या करें$$ $ इनलाइन $ a_ {11} = 0 $ इनलाइन $ ? क्या प्रसिद्ध गॉस विधि वहाँ समाप्त होती है?

चिंता की कोई बात नहीं! आइए ढूंढते हैं$$ $ इनलाइन $ \ max | a_ {1j} | $ इनलाइन $ और स्वैप करें$$ $ इनलाइन $ j $ इनलाइन $ वें और पहली पंक्ति (सामान्यता की हानि के बिना, मान लीजिए कि$$ $ इनलाइन $ \ max | a_ {1j} | = a_ {13} $ इनलाइन $ )। ध्यान दें कि जब सब कुछ हो$$ $ इनलाइन $ a_ {1j} = 0 $ इनलाइन $ यह नहीं हो सकता है, क्योंकि इस मामले में गुणांक के मैट्रिक्स का निर्धारक गायब हो जाता है और सिस्टम को हल करना संभव नहीं है। इसलिए, पहली पंक्ति पर तीसरे समीकरण को फिर से व्यवस्थित करने के बाद, हम पहले वर्णित चरणों का पालन करते हैं।

अधिकतम मोडुलो तत्व की खोज से प्रत्येक पुनरावृत्ति, यानी, पर निपटा जा सकता है$$ $ इनलाइन $ k $ इनलाइन $ -इसके लिए पुनरावृति देखना$$ $ इनलाइन $ \ max | a_ {kj} | $ इनलाइन $ फिर बदलो$$ $ इनलाइन $ j $ इनलाइन $ -s और$$ $ इनलाइन $ k $ इनलाइन $ वें पंक्ति। वह एल्गोरिथ्म जिसमें कॉलम में अधिकतम तत्व खोजा जाता है, कॉलम में मुख्य तत्व की पसंद के साथ गॉस विधि कहा जाता है।

एक और तरीका है। पर कर सकते हैं$$ $ इनलाइन $ k $ इनलाइन $ -इसके लिए पुनरावृति देखना$$ $ इनलाइन $ \ max | a_ {ik} | $ इनलाइन $ , फिर पंक्तियों को नहीं, बल्कि स्तंभों को बदलें। लेकिन कुछ कॉलम में बदलते कॉलम के सूचकांकों को याद रखना महत्वपूर्ण है$$ $ इनलाइन $ \ अल्फा $ इनलाइन $ (तब चर के सटीक क्रम को बहाल करने के लिए)।

एक सरल कोड का एक उदाहरण जो इस एल्गोरिथ्म को लागू करता है:

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]; // input for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { a[i][j] = sc.nextDouble(); } b[i] = sc.nextDouble(); } int[] alpha = new int[n + 1]; // array of indices for (int i = 1; i <= n; i++) { alpha[i] = i; } for (int m = 1; m <= n; m++) { double max = Math.abs(a[m][m]); int count = m; for (int i = m + 1; i <= n; i++) { if (Math.abs(a[m][i]) > max) { // search max elements at the string max = Math.abs(a[m][i]); count = i; } } int tmp = alpha[m]; // swap strings alpha[m] = alpha[count]; alpha[count] = tmp; for (int i = m; i <= n; i++) { double tmp2 = a[i][m]; a[i][m] = a[i][count]; a[i][count] = tmp2; } for (int i = m + 1; i <= n; i++) { // guassian right stroke b[i] = b[i] - a[i][m] * b[m] / a[m][m]; for (int j = m + 1; j < n; j++) { a[i][j] = a[i][j] - a[i][m] * a[m][j] / a[m][m]; } } } // for m double[] x = new double[n+1]; for (int i = n; i >= 1; i--) { // guassian back stroke double sum = 0; for (int j = i + 1; j <= n; j++) { sum += a[i][j] * x[alpha[j]]; } x[alpha[i] - 1] = (b[i] - sum) / a[i][i]; } // output PrintWriter pw = new PrintWriter("output.txt"); for (int i = 0; i < n; i++) { pw.printf(Locale.US, "x%d = %.5f \n", i + 1, x[i]); } pw.flush(); pw.close(); } } 

गॉस क्यों?

SLAE को हल करने का एक और तरीका है। उनमें से एक Cramer विधि है। इसमें निश्चित संख्या में निर्धारकों की प्रारंभिक गणना होती है, जिसकी सहायता से चर के मानों की तुरंत गणना की जाती है। मूल प्रणाली के तहत, यह विधि इस तरह दिखाई देगी:

$$$$ प्रदर्शन $ $ \ Delta = \ _ {शुरू {vmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \\ a_ 31 # & a_ {32} & a_ {33} \\ \ end {vmatrix}, \ Delta_1 = \ start {vmatrix} b_1 & a_ {12} & a_ {13} \\ b_2 & a_ {22} & a_ {23} \ _ \ b_3 & a_ {32} & a_ {33} \\ \ end {vmatrix}, $ $ $ $ प्रदर्शित

$$$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ प्रदर्शन प्रदर्शन करने के लिए। \\ \ अंत {vmatrix}, \ Delta_3 = \ start {vmatrix} a_ {11} & a_ {12} & b_1 \\ a_ {21} & a_ {22} & b_2 \\ a_ 31} & a_ {32 } & b_3 \\ \ end {vmatrix}, $ $ प्रदर्शन $ $

$$$ $ प्रदर्शन $ $ x_i = \ dfrac {\ Delta_i} {\ Delta}। $ $ प्रदर्शन $ $

लेकिन याद रखें - एक क्वालिफायर क्या है?

परिभाषा के अनुसार, एक मैट्रिक्स का निर्धारक$$ $ इनलाइन $ A = (a_ {ij}) $ इनलाइन $ एक राशि है

$$$$ $ $ $ \ _ \ _ सीमाएं {{1 \ leq i_1 <\ dots <i_n \ leq n} (-1) ^ {N (i_1, \ dots, i_n)} a_ {1i_1}} / डॉट्स a_ {ni_n}, प्रदर्शित करें $ $ प्रदर्शन $ $

जहाँ$$ $ इनलाइन $ N (i_1, \ dots, i_n) $ इनलाइन $ - वाइल्डकार्ड$$ $ इनलाइन $ i_1, \ dots, i_n। $ इनलाइन $

निर्धारक में होता है$$ $ इनलाइन $ n! $ इनलाइन $ शर्तों। सिस्टम को हल करने के लिए, आपको गणना करने की आवश्यकता है$$ $ इनलाइन $ n + 1 $ इनलाइन $ निर्धारकों। पर्याप्त रूप से बड़े स्तर पर$$ $ इनलाइन $ n $ इनलाइन $ यह बहुत महंगा है। उदाहरण के लिए, जब$$ $ इनलाइन $ n = 12 $ इनलाइन $ संचालन की संख्या बन जाती है$$ $ इनलाइन $ 12! (12 + 1) = 6227020800, $ इनलाइन $ जबकि गोमेट्स एसिम्पोटिक्स के साथ विधि है$$ $ इनलाइन $ n ^ 3 $ इनलाइन $ की आवश्यकता होगी$$ $ इनलाइन $ 12 ^ 3 = 1728 $ इनलाइन $ संचालन।

Iterative तरीके

तथाकथित पुनरावृत्ति विधियाँ SLAE को हल करने के लिए एल्गोरिदम के रूप में भी उपयुक्त हैं। वे क्रमिक रूप से अनुमानों की गणना करते हैं जब तक कि उनमें से एक सटीक उत्तर के करीब न हो।

सबसे पहले, कुछ मनमाना वेक्टर चुना जाता है$$ $ इनलाइन $ x ^ 0 $ इनलाइन $ एक शून्य सन्निकटन है। इस पर एक वेक्टर बनाया गया है।$$ $ इनलाइन $ x ^ 1 $ इनलाइन $ - यह पहला अनुमान है। और इसी तरह। गणनाएँ कब समाप्त होती हैं$$ $ इनलाइन $ || x ^ k - x ^ {k + 1} || <\ _ varepsilon $ इनलाइन $ जहाँ$$ $ इनलाइन $ \ varepsilon $ इनलाइन $ - कुछ सेट वैल्यू पहले से। अंतिम असमानता का अर्थ है कि प्रत्येक पुनरावृत्ति के साथ समाधान का हमारा "सुधार" लगभग नगण्य है।

लोकप्रिय जैकोबी विधि पर विचार करें, जो SLAE को हल करने के लिए सबसे सरल पुनरावृत्तियों में से एक है।

शुरू करने के लिए, हम सिस्टम को निम्नलिखित रूप में लिखते हैं:

$$$ $ $ $ $ \ _ \ _ सीमाएं {{j \ leq n} a_ {ij} x_j = b_i, \ i = \ overline {1, n} प्रदर्शित करें। $ $ प्रदर्शन $ $

वियोज्य$$ $ इनलाइन $ मैं $ इनलाइन $ -तब्द और बाकी सब के माध्यम से इसे व्यक्त करें:

$$$ $ प्रदर्शन $ $ x_i = \ dfrac {b_i - \ sum \ limit_ {j \ neq i} a_ {ij} x_j} {a_ {ii}}, \ i = \ overline {1, n}। $ $ $ $ प्रदर्शन। $

अब बस चर पर "काउंटर" लटकाएं और जैकोबी पुनरावृत्ति विधि प्राप्त करें:

$$$ $ $ $ $ x_i ^ k = \ dfrac {b_i - \ sum \ limit_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}}, \ i = \ _ toline {1, n} \ k = 0,1, \ dots। $$ प्रदर्शन $ $

ध्यान दें कि इस पद्धति का उपयोग करने के लिए एक शर्त मुख्य विकर्ण के साथ शून्य की अनुपस्थिति है।

जावा में जैकोबी पद्धति का कार्यान्वयन:
एक के रूप में$$ $ इनलाइन $ \ varepsilon $ इनलाइन $ एक पूर्व-गणना तथाकथित मशीन एप्सिलॉन को लिया जाता है।

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

जैकोबी विधि का एक संशोधन विश्राम विधि है। इसका मुख्य अंतर यह है कि पूर्व-चयनित पैरामीटर की मदद से पुनरावृत्तियों की संख्या काफी कम हो जाती है। आइए हम संक्षेप में विधि के मुख्य विचार का वर्णन करते हैं।

मूल प्रणाली से, हम फिर से व्यक्त करते हैं$$ $ इनलाइन $ x $ इनलाइन $ , लेकिन चलो काउंटरों को थोड़ा अलग तरीके से सेट करें और पैरामीटर जोड़ें$$ $ इनलाइन $ \ omega $ इनलाइन $ :

$$$ $ $ $ $ x_i ^ k = \ dfrac {\ omega \ left (b_i - \ sum \ limit_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k +}} - \ sum \ limit_ {j = i + 1} ^ n a_ {ij} x_j ^ k \ right)} {a_ {ii}} + (1- \ _ omega) x_i ^ k, \ i = \ overline {1, n}, \ k = 0,1, \ dots। $ $ $ $ प्रदर्शन

पर$$ $ इनलाइन $ \ omega = 1 $ इनलाइन $ यह सब एक जैकोबी पद्धति में बदल जाता है।

तो, हम कुछ “अच्छे” की तलाश करेंगे$$ $ इनलाइन $ \ omega $ इनलाइन $ । कुछ संख्या निर्धारित करें$$ $ इनलाइन $ एस $ इनलाइन $ और हम मान लेंगे$$ $ इनलाइन $ \ omega \ (0,2) $ इनलाइन $ , जिनमें से प्रत्येक के लिए हम मानदंडों पर विचार करेंगे$$ $ इनलाइन $ || x ^ {k + 1} -x ^ k ||, \ k = \ overline {1, s}} इनलाइन $ । इन मानदंडों में से सबसे छोटे के लिए, इस मूल्य को याद रखें$$ $ इनलाइन $ \ omega $ इनलाइन $ , और इसके साथ हम अपनी प्रणाली को हल करेंगे।

जावा विधि चित्रण:
यहां$$ $ इनलाइन $ s = 5 $ इनलाइन $

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

एक निष्कर्ष के बजाय

SLAE को हल करने के लिए कई और एल्गोरिदम हैं। उदाहरण के लिए, वर्गमूल विधि, जिसमें वांछित प्रणाली को दो "सरल" प्रणालियों द्वारा प्रतिस्थापित किया जाता है, जिनके समाधानों की गणना प्रारंभिक सूत्रों द्वारा की जाती है; स्वीप विधि, जिसका उपयोग इतने विशिष्ट ट्रिडिओगनल मैट्रीस के लिए किया जाता है। हर कोई अपनी समस्या के लिए किस विधि का उपयोग करता है।