Գաուս-Զեյդելի մեթոդ

Գաուս-Զեյդելի մեթոդը (Զեյդելի մեթոդ, Լիբմանի պրոցես, հաջորդական փոխարինումների մեթոդ) հանդիսանում է դասական իտերացիոն մեթոդով հավասարումների համակարգի լուծում։ Այն անվանվում է ի պատիվ Զեյդելի և Գաուսի։

Խնդրի դրվածքը

Դիտարկենք հավասարումների համակարգը՝

$A\overrightarrow{x}=\overrightarrow{b}$, где $A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \dots & a_{nn}\end{array}\right),\overrightarrow{b}=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_n\end{array}\right)$

կամ

$\{\begin{array}{ccc}{a}_{11}{x}_1+\dots +a_{1n}{x}_n& =& b_1\\ & & \\ a_{n1}{x}_1+\dots +a_{nn}{x}_n& =& b_n\end{array}$

և ցույց տանք, թե ինչպես կարելի է լուծել այն Գաուս-Զեյդելի մեթոդով։

Մեթոդը

Մեթոդի էությունը պարզաբանելու համար առաջադրանքը գրենք հետևյալ տեսքով՝

$\{\begin{array}{ccc}{a}_{11}{x}_1& =& -a_{12}{x}_2-a_{13}{x}_3-\dots -a_{1n}{x}_n+b_1\\ a_{21}{x}_1+a_{22}{x}_2& =& -a_{23}{x}_3-\dots -a_{2n}{x}_n+b_2\\ \dots & & \\ a_{(n-1)1}{x}_1+a_{(n-1)2}{x}_2+\dots +a_{(n-1)(n-1)}{x}_{n-1}& =& -a_{(n-1)n}{x}_n+b_{n-1}\\ a_{n1}{x}_1+a_{n2}{x}_2+\dots +a_{n(n-1)}{x}_{n-1}+a_{nn}{x}_n& =& b_n\end{array}$

Այստեղ $j$-րդ հավասարումում մենք աջ մաս տեղափոխեցինք բոլոր այն $x_i$ անդամները, որտեղ բավարարում էր $i>j$ պայմանը։ Այս գրառումը կարող է ներկայացվել հետևյալ ձևով՝

$(\mathrm{L}+\mathrm{D})\overrightarrow{x}=-\mathrm{U}\overrightarrow{x}+\overrightarrow{b},$

որտեղ ընդունված նշանակումներով $\mathrm{D}$-ն մատրից է, որում գլխավոր անկյունագծի վրա գրված են $A$ մատրիցի համապատասխան անդամները, իսկ մնացած անդամները զրոներ են, այնինչ $\mathrm{U}$ և $\mathrm{L}$ մատրիցները պարունակում են $A$ մատրիցի վերևի և ներքևի եռանկյունային մասերը, որոնց գլխավոր անկյունագծի վրա զրոներ են։ Գաուս-Զեյդելի մեթոդում իտերացիոն պրոցեսը ստեղծվում է հետևյալ բանաձևով՝

$(\mathrm{L}+\mathrm{D}){\overrightarrow{x}}^{(k+1)}=-\mathrm{U}{\overrightarrow{x}}^{(k)}+\overrightarrow{b},k=0,1,2,\dots$

համապատասխան ${\overrightarrow{x}}^{(0)}$ սկզբնական մոտարկման ընտրությամբ։

Գաուս-Զեյդելի մեթոդը կարելի է դիտարկել որպես Յակոբիի մեթոդի մոդիֆիկացիա։ Մոդիֆիկացիայի հիմնական գաղափարը կայանում է նրանում, որ այստեղ ${\overrightarrow{x}}^{(i)}$ նոր արժեքները օգտագործվում են անմիջապես ստանալուց հետո, այնինչ Յակոբիի մեթոդում այն չի օգտագործվում մինչև հաջորդ իտերացիան՝

$\{\begin{array}{ccccccccccc}{x_1}^{(k+1)}& =& c_{12}{x}_2^{(k)}& +& c_{13}{x}_3^{(k)}& +& \dots & +& c_{1n}{x_n}^{(k)}& +& d_1\\ {x_2}^{(k+1)}& =& c_{21}{x}_1^{(k+1)}& +& c_{23}{x}_3^{(k)}& +& \dots & +& c_{2n}{x_n}^{(k)}& +& d_2\\ \dots & & & & & & & & & & \\ {x_n}^{(k+1)}& =& c_{n1}{x}_1^{(k+1)}& +& c_{n2}{x}_2^{(k+1)}& +& \dots & +& c_{n(n-1)}{x_{n-1}}^{(k+1)}& +& d_n\end{array},$

որտեղ

$c_{ij}=\{\begin{array}{cc}-\frac{a_{ij}}{a_{ii}},& j\ne i,\\ 0,& j=i.\end{array}{d}_i=\frac{b_i}{a_{ii}},i=1,\dots ,n.$

Այսպիսով, $i$-րդ կոմպոնենտի $(k+1)$-րդ մոտարկման հաշվարկը կատարվում է

$x_i^{(k+1)}=\sum _{j=1}^{i-1}{c}_{ij}{x}_j^{(k+1)}+\sum _{j=i}^n{c}_{ij}{x}_j^{(k)}+d_i,i=1,\dots ,n$

բանաձևով։

Օրինակ, $n=3$-ի դեպքում`

$x_1^{(k+1)}=\sum _{j=1}^{1-1}{c}_{1j}{x}_j^{(k+1)}+\sum _{j=1}^3{c}_{1j}{x}_j^{(k)}+d_1$, այսինքն $x_1^{(k+1)}=c_{11}{x}_1^{(k)}+c_{12}{x}_2^{(k)}+c_{13}{x}_3^{(k)}+d_1,$

$x_2^{(k+1)}=\sum _{j=1}^{2-1}{c}_{2j}{x}_j^{(k+1)}+\sum _{j=2}^3{c}_{2j}{x}_j^{(k)}+d_2$, այսինքն $x_2^{(k+1)}=c_{21}{x}_1^{(k+1)}+c_{22}{x}_2^{(k)}+c_{23}{x}_3^{(k)}+d_2,$

$x_3^{(k+1)}=\sum _{j=1}^{3-1}{c}_{3j}{x}_j^{(k+1)}+\sum _{j=3}^3{c}_{3j}{x}_j^{(k)}+d_3$, այսինքն $x_3^{(k+1)}=c_{31}{x}_1^{(k+1)}+c_{32}{x}_2^{(k+1)}+c_{33}{x}_3^{(k)}+d_3:$

Զուգամիտության պայման

Բերենք զուգամիտության մեթոդի բավարար պայման։ Կաղապար:Message box

Դադարեցման պայմանը

Զեյդելի պրոցեսի իտերացիայի ավարտի պայմանը անհրաժեշտ $\epsilon$ ճշգրտության դեպքում կրճատ ձևով ունի այսպիսի տեսք՝

$\parallel x^{(k+1)}-x^{(k)}\parallel \le \epsilon$

Իտերացիոն պրոցեսի առավել ճշգրիտ պայմանը ունի այսպիսի տեսք՝

$\parallel A{x}^{(k)}-b\parallel \le \epsilon$

և պահանջում է ավելի շատ հաշվարկներ։ Այն բավականին հարմար է կտրտված մատրիցների համար։

Իրականացման օրինակ C++ - ում

#include <iostream>
#include <cmath>

using namespace std;

// Ավարտի պայման
bool converge(double xk[10], double xkp[10], int n, double eps)
{
	double norm = 0;
	for (int i = 0; i < n; i++)
		norm += (xk[i] - xkp[i]) * (xk[i] - xkp[i]);
	return (sqrt(norm) < eps);
}

double okr(double x, double eps)
{
	int i = 0;
	while (eps != 1)
	{
		i++;
		eps *= 10;
	}
	int okr = pow(double(10), i);
	x = int(x * okr + 0.5) / double(okr);

	return x;
}

bool diagonal(double a[10][10], int n)
{
	int i, j, k = 1;
	double sum;
	for (i = 0; i < n; i++) {
		sum = 0;
		for (j = 0; j < n; j++) sum += a[i][j];
		sum -= a[i][i];
		if (sum > a[i][i]) 
		{
			k = 0; 
			cout << a[i][i] << " < " << sum << endl;
		}
		else
		{
			cout << a[i][i] << " > " << sum << endl;
		}
		

	}

	return (k == 1);

}

int main()
{
	setlocale(LC_ALL, "");

	double eps, a[10][10], b[10], x[10], p[10];
	int n, i, j, m = 0;
	int method;
	cout << "Մուտքագրել քառակուսի մատրիցի չափը՝ ";
	cin >> n;
	cout << "Մուտքագրել հաշվարկի ճշտությունը՝ ";
	cin >> eps;
	cout << "Մուտքագրել А մատրիցն՝ " << endl << endl;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
		{
			cout << "A[" << i << "][" << j << "] = ";
			cin >> a[i][j];
		}
	cout << endl << endl;
	cout << " Ձեր А մատրիցն՝ " << endl << endl;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}

	cout << endl;

	cout << "Լրացրեք ազատ անդամների սյունը՝ " << endl << endl;
	for (i = 0; i < n; i++)
	{
		cout << "В[" << i + 1 << "] = ";
		cin >> b[i];
	}

	cout << endl << endl;

	/*
	Քայլ մեթոդ, որտեղ։
	a[n][n] - մատրիցի գործակիցներն են
	x[n], p[n] - Ընթացիկ և նախորդ լուծումները
	b[n] - Աջ մասերի սյունը
	Բոլոր թվարկված զանգվածները իրական են և
	պետք է որոշված լինեն հիմնական ծրագրում,
	ինչպես նաև x[n] մասիվում անհրաժեշտ է լրացնել սկզբնական
	սյան լուծումի մոտարկումը (օրիակ, բոլորը զրոներ)
	*/

	for (int i = 0; i < n; i++)
		x[i] = 1;

	cout << "Անկյունագծային գերակշռություն՝ " << endl;
	if (diagonal(a, n)) {
		do
		{
			for (int i = 0; i < n; i++)
				p[i] = x[i];
			for (int i = 0; i < n; i++)
			{
				double var = 0;
				for (int j = 0; j < i; j++)
					var += (a[i][j] * x[j]);
				for (int j = i + 1; j < n; j++)
					var += (a[i][j] * p[j]);
				x[i] = (b[i] - var) / a[i][i];
			}
			m++;
		} while (!converge(x, p, n, eps));

		cout << "Համակարգի լուծում՝" << endl << endl;
		for (i = 0; i < n; i++) cout << "x" << i << " = " << okr(x[i], eps) << "" << endl;
		cout << "Իտերացիա՝ " << m << endl;
	}
	else {
		cout << "Չի կատարվում անկյունագծերի գերակշռություն։" << endl;
	}

	system("pause");
	return 0;
}

Իրականացման օրինակ Python - ում

from math import sqrt
import numpy as np

def seidel(A, b, eps):
    n = len(A)
    x = [.0 for i in range(n)]

    converge = False
    while not converge:
        x_new = np.copy(x)
        for i in range(n):
            s1 = sum(A[i][j] * x_new[j] for j in range(i))
            s2 = sum(A[i][j] * x[j] for j in range(i + 1, n))
            x_new[i] = (b[i] - s1 - s2) / A[i][i]

        converge = sqrt(sum((x_new[i] - x[i]) ** 2 for i in range(n))) <= eps
        x = x_new

    return x

Տես նաև

• Երկրաչափական պրոգրեսիա
• Պարզ իտերացիայի մեթոդ
• Յակոբիի մեթոդ
• Բանախի թեորեմ
• Իտերացիայի մեթոդ

Արտաքին հղումներ

• https://www.maa.org/press/periodicals/loci/joma/iterative-methods-for-solving-iaxi-ibi-gauss-seidel-method Կաղապար:Webarchive
• https://www3.nd.edu/~zxu2/acms40390F12/Lec-7.3.pdf
• http://mathworld.wolfram.com/Gauss-SeidelMethod.html