لماذا غاوس؟ (100 طريقة لحل نظام المعادلات)

ماذا ستفعل إذا طُلب منك حل نظام بسيط مع ثلاثة مجهولين؟ كل منها شكل منهجه الخاص والأكثر ملاءمة له شخصياً. هناك طرق عديدة لحل نظام المعادلات الجبرية الخطية. ولكن لماذا يتم إعطاء التفضيل بشكل خاص لطريقة غاوس؟

الأشياء الأولى أولاً

لنبدأ بواحد بسيط. يجب إعطاء نظام المعادلات الخطية من الرتبة الثالثة:

$$$$ display $$ \ left \ {\ start {align} 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 {align} \ right. $$ display $$

تتكون طريقة غاوس من "تدمير" متسلسل للمصطلحات تحت القطر الرئيسي. في الخطوة الأولى ، يتم ضرب المعادلة الأولى في$$ $ inline $ \ dfrac {a_ {21}} {a_ {11}} $ مضمنة $ وطرح من الثانية (وضرب بالمثل$$ $ inline $ \ dfrac {a_ {31}} {a_ {11}} $ inline $ وطرح من الثالث). أي بعد هذا التحويل نحصل على ما يلي:

$$$$ display $$ \ left \ {\ start {align} 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 {align} \ right. $$ display $$

الآن يتم ضرب المعادلة الثانية في$$ $ inline $ \ dfrac {a_ {32} '} {a_ {22}'} $ مضمنة $ وطرح من الثالث:

$$$$ display $$ \ left \ {\ start {align} 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 {align} \ right. $$ display $$

لقد حصلنا على نظام بسيط إلى حد ما ، يسهل العثور عليه$$ $ inline $ x_3 $ مضمنة $ ثم$$ $ مضمنة $ x_2 $ مضمنة $ و$$ $ مضمنة $ x_1 $ مضمنة $ .

سيلاحظ القارئ اليقظ بالتأكيد: ماذا لو كانت العناصر القطرية تساوي الصفر؟ ماذا تفعل إذا ، على سبيل المثال ،$$ $ مضمنة $ a_ {11} = 0 $ مضمنة $ ؟؟؟ هل تنتهي طريقة Gauss الشهيرة عند هذا الحد؟

لا داعي للقلق! دعنا نجد$$ $ inline $ \ max | a_ {1j} | $ مضمنة $ وتبادل$$ $ inline $ j $ مضمنة $ الصف الأول والصف الأول (بدون فقدان العمومية ، افترض ذلك$$ $ inline $ \ max | a_ {1j} | = a_ {13} $ مضمنة $ ) لاحظ أن الحالة عندما يكون كل شيء$$ $ مضمنة $ a_ {1j} = 0 $ مضمنة $ لا يمكن أن يكون ذلك ، لأنه في هذه الحالة يختفي محدد مصفوفة المعاملات ولا يمكن حل النظام. لذا ، بعد إعادة ترتيب المعادلة الثالثة على الخط الأول ، نقوم بالخطوات الموضحة سابقًا.

يمكن التعامل مع البحث عن عنصر modulo الأقصى عند كل تكرار ، أي في$$ $ مضمنة $ k $ مضمنة $ - التكرار الذي تبحث عنه$$ $ inline $ \ max | a_ {kj} | $ مضمنة $ ثم تغير$$ $ inline $ j $ مضمنة $ و$$ $ مضمنة $ k $ مضمنة $ خط ال. تسمى الخوارزمية التي يتم فيها البحث عن العنصر الأقصى في العمود طريقة Gauss مع اختيار العنصر الرئيسي في العمود.

هناك طريقة أخرى. يمكن على$$ $ مضمنة $ k $ مضمنة $ - التكرار الذي تبحث عنه$$ $ inline $ \ max | a_ {ik} | $ مضمنة $ ، ثم قم بتغيير الصفوف ، ولكن الأعمدة. ولكن من المهم تذكر مؤشرات الأعمدة المتغيرة في بعض المصفوفة$$ $ مضمنة $ \ alpha $ مضمنة $ (ثم ​​استعادة الترتيب الدقيق للمتغيرات).

مثال على كود بسيط يقوم بتنفيذ هذه الخوارزمية:

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. وهو يتألف من الحساب الأولي لعدد محدد من المحددات ، والتي يتم من خلالها حساب قيم المتغيرات على الفور. في ظل النظام الأصلي ، ستبدو هذه الطريقة كما يلي:

$$$$ display $$ \ Delta = \ start {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} ، $$ display $$

$$$$ display $$ \ Delta_2 = \ start {vmatrix} a_ {11} & b_1 & a_ {13} \\ a_ {21} & b_2 & a_ {23} \\ a_ {31} & b_3 & a_ {33} \\ \ end {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} ، $$ display $$

$$$$ display $$ x_i = \ dfrac {\ Delta_i} {\ Delta}. $$ display $$

لكن تذكر - ما هو المؤهل؟

بحكم التعريف ، محدد المصفوفة$$ $ inline $ A = (a_ {ij}) $ مضمنة $ هناك مبلغ

$$$$ display $$ \ sum \ limits_ {1 \ leq i_1 <\ dots <i_n \ leq n} (-1) ^ {N (i_1، \ dots، i_n)} a_ {1i_1} \ dots a_ {ni_n} ، $$ display $$

أين$$ $ inline $ N (i_1، \ dots، i_n) $ inline $ - حرف بدل$$ $ inline $ i_1 ، \ dots ، i_n. $ inline $

المحدد يحتوي على$$ $ مضمنة $ n! $ مضمنة $ الشروط. لحل النظام ، تحتاج إلى العد$$ $ مضمنة $ n + 1 $ مضمنة $ المحددات. على نطاق واسع بما فيه الكفاية$$ $ مضمنة $ n $ مضمنة $ إنه مكلف للغاية. على سبيل المثال ، متى$$ $ inline $ n = $ 12 مضمنة $ يصبح عدد العمليات$$ $ inline $ 12! (12 + 1) = 6227020800، $ inline $ بينما طريقة غاوس مع الخطوط المقاربة$$ $ مضمنة $ n ^ 3 $ مضمنة $ سوف يتطلب فقط$$ $ مضمنة $ 12 ^ 3 = 1728 $ مضمنة $ العمليات.

طرق تكرارية

ما يسمى بالطرق التكرارية مناسبة أيضًا كخوارزميات لحل SLAEs. وهي تتكون في حساب التقديرات التقريبية بالتسلسل حتى يصبح أحدها أقرب ما يمكن من الإجابة الدقيقة.

أولاً ، يتم تحديد بعض المتجه التعسفي$$ $ مضمنة $ x ^ 0 $ مضمنة $ هو تقريب صفري. متجه مبني عليه.$$ $ مضمنة $ x ^ 1 $ مضمنة $ - هذا هو التقريب الأول. وهكذا دواليك. تنتهي الحسابات عندما$$ $ inline $ || x ^ k - x ^ {k + 1} || <\ varepsilon $ مضمنة $ أين$$ $ inline $ \ varepsilon $ مضمنة $ - بعض القيمة المحددة مسبقًا. يعني عدم المساواة الأخير أن "تحسيننا" للحل مع كل تكرار يكاد يكون غير ذي أهمية.

ضع في اعتبارك طريقة Jacobi الشائعة ، والتي تعد واحدة من أبسط الطرق التكرارية لحل SLAEs.

بادئ ذي بدء ، نكتب النظام في الشكل التالي:

$$$$ display $$ \ sum \ limits_ {j \ leq n} a_ {ij} x_j = b_i، \ i = \ overline {1، n}. $$ display $$

منفصل$$ $ مضمنة $ i $ مضمنة $ - المصطلح العاشر والتعبير عنه من خلال أي شيء آخر:

$$$$ display $$ x_i = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j} {a_ {ii}} ، \ i = \ overline {1، n}. $$ display $ $

الآن فقط قم بتعليق "العدادات" على المتغيرات واحصل على طريقة تكرار جاكوبي:

$$$$ display $$ x_i ^ k = \ dfrac {b_i - \ sum \ limits_ {j \ neq i} a_ {ij} x_j ^ k} {a_ {ii}} ، \ i = \ overline {1، n} ، \ k = 0،1، \ dots. $$ display $$

لاحظ أن الشرط الأساسي لاستخدام هذه الطريقة هو عدم وجود أصفار على طول القطر الرئيسي.

تطبيق طريقة جاكوبي في جافا:
ك$$ $ inline $ \ 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 $ مضمنة $ ، ولكن دعنا نعد العدادات بشكل مختلف قليلاً ونضيف المعلمة$$ $ inline $ \ omega $ مضمنة $ :

$$$$ display $$ x_i ^ k = \ dfrac {\ omega \ left (b_i - \ sum \ limits_ {j = 1} ^ {i-1} a_ {ij} x_j ^ {k + 1} - \ sum \ limits_ {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. $$ display $$

في$$ $ inline $ \ omega = 1 $ inline $ كل ذلك يتحول إلى طريقة جاكوبي.

لذا ، سنبحث عن بعض "الخير"$$ $ inline $ \ omega $ مضمنة $ . حدد بعض الأرقام$$ $ مضمنة $ s $ مضمنة $ وسنأخذ القيم$$ $ inline $ \ omega \ in (0،2) $ مضمنة $ ، لكل منها سننظر في المعايير$$ $ inline $ || x ^ {k + 1} -x ^ k ||، \ k = \ overline {1، s} $ inline $ . بالنسبة لأصغر هذه المعايير ، تذكر هذه القيمة$$ $ inline $ \ omega $ مضمنة $ ومعها سنحل نظامنا.

توضيح طريقة جافا:
هنا$$ $ inline $ 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. على سبيل المثال ، طريقة الجذر التربيعي ، حيث يتم استبدال النظام المطلوب بنظامين "بسيطين" ، يتم حساب حلولهما بواسطة صيغ أولية ؛ طريقة الكنس ، والتي تستخدم لمصفوفات ثلاثية الأبعاد محددة للغاية. يختار الجميع الطريقة التي يستخدمها لمشكلته.