Յակոբիի մեթոդ

Յակոբիի մեթոդը գծային հանրահաշվում հավասարումների համակարգերի լուծման պարզ իտերացիայի տարատեսակներից է։ Այն անվանվել է ի պատիվ Կարլ Գուստավ Յակոբիի։

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

Վերցնենք գծային հավասարումների համակարգը.

$A{\vec {x}}={\vec {b}}$, где $A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}\end{array}}\right),\quad {\vec {b}}=\left({\begin{array}{c}b_{1}\\\vdots \\b_{n}\end{array}}\right)$

կամ

$\left\{{\begin{array}{rcl}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots ~~~~~~~~~~~~~~~~~~~~~\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.$

Մեթոդի նկարագրությունը

Որպեսզի կառուցենք Յակոբիի մեթոդի իտերատիվ ընթացակարգը, անհրաժեշտ է իրականացնել $A{\vec {x}}={\vec {b}}$ հավասարումների համակարգի նախնական ձևափոխում ${\vec {x}}=B{\vec {x}}+{\vec {g}}$ իտերացիոն տեսքին։ Այն կարող է կատարվել հետևյալ կանոններից որևէ մեկի համաձայն՝

• $B=E-D^{-1}A=D^{-1}(D-A),\quad {\vec {g}}=D^{-1}{\vec {b}};$

  $B=-D^{-1}(L+U)=-D^{-1}(A-D),\quad {\vec {g}}=D^{-1}{\vec {b}}$

  $D_{ii}^{-1}=1/D_{ii},D_{ii}\neq 0,\,i=1,2,...,n\quad ,$

որտեղ ըստ ընդունված նշանակումների $D$-ն մատրից է, որի գլխավոր անկյունագծի վրա գտնվում են $A$ մատրիցի համապատասխան էլեմենտները, իսկ մնացած բոլոր էլեմենտները զրոներ են, այնինչ $U$ և $L$ մատրիցները պարունակում են $A$ մատրիցի վերևի և ներքևի եռանկյունային մասերը, որոնց գլխավոր անկյունագծի վրա զրոներ են, իսկ $E$-ն միավոր մատրից է։

Այդ դեպքում լուծման գտնելու ընթացակարգը ունիայսպիսի տեսք՝

${\vec {x}}^{(k+1)}=B{\vec {x}}^{(k)}+{\vec {g}},$

կամ ըստ էլեմենտային բանաձևի տեսքով՝

$x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n,$

որտեղ $k$-ն իտերացիայի հաշվիչն է։

Ի տարբերություն Զեյդելի մեթոդի մենք չենք կարող փոխարինել $x_{i}^{(k)}$-ը $x_{i}^{(k+1)}$-ի իտերացիայի գործընթացի ընթացքում, քանի որ այդ արժեքները անհրաժեշտ են մյուս հաշվարկների համար։

Սա ամենաէական տարբերությունն է գծային հանրահաշվական հավասարումների համակարգի լուծման Յակոբիի և Գաուս-Զեյդել մեթոդների միջև։ Այսպիսով, յուրաքանչյուր իտերացիայի ժամանակ անհրաժեշտություն է առաջանում մոտարկումների երկու վեկտորները՝ հին և նոր, պահպանել։

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

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

Թեորեմ. Դիցուկ $\|B\|<1$։ Այդ դեպքում ցանկացած ${\vec {x}}^{(0)}$ սկզբնական մոտարկման ընտրության դեպքում՝ Գաուս-Զեյդելի մեթոդը զուգամիտում է, մեթոդի զուգամիտության արագությունը հավասար է երկրաչափական պրոգրեսիայի զուգամիտության արագությանը $q=\|\mathrm {A} _{2}\|$ հայտարարով, ճիշտ է $\|{\vec {x}}^{(k)}-{\vec {x}}\|=q^{k}\,\|{\vec {x}}^{(0)}-{\vec {x}}\|$ գնահատման սխալը։

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

Իտերացիոն գործընթացի ավարտի պայմանը անհրաժեշտ $\varepsilon$ ճշգրտության դեպքում ունի այսպիսի տեսք՝

$\parallel x^{(k+1)}-x^{(k)}\parallel \leq {\frac {1-q}{q}}\varepsilon$։

$B$ (երբ $\parallel B\parallel =q<1/2$) մատրիցի համար առավել լավ այն կատարվում է, երբ

$\parallel x^{(k+1)}-x^{(k)}\parallel \leq \varepsilon$։

Այս չափանիշը չի պահանջում մատրիցի նորմայի հաշվարկ և գործնականում հաճախ է օգտագործվում։ Այդ դեպքում կրկնվող գործընթացի ավարտի ճշգրիտ պայմանը ունի այսպիսի տեսք՝

$\parallel Ax^{(k)}-b\parallel \leq \varepsilon$

և պահանջում է լրացուցիչ բազմապատկում մատրիցն վեկտորին յուրաքանչյուր իտերացիայում, որը մոտավորապես երկու անգամ մեծացնում է ալգորիթմի հաշվարկային բարդությունը։

Ալգորիթմ

Ներքևում բերենք ալգորիթմի իրականացումը С++ -ում։

#include <math.h>
const double eps = 0.001; ///< ցանկալի ճշտությունը

..........................

/// N - մատրիցի չափը; A[N][N] - գործակիցների մատրիցն, F[N] - ազատ անդամների սյունը,
/// X[N] - սկզբնական մոտարկումը, պատասխանը նույնպես գրվում է X[N]-ում;
void Jacobi (int N, double** A, double* F, double* X)
{
	double* TempX = new double[N];
	double norm; // նորման, որոշված որպես ամենամեծ տարբերությունը հարևան իտերացիաների սյուների միջև

	do {
		for (int i = 0; i < N; i++) {
			TempX[i] = F[i];
			for (int g = 0; g < N; g++) {
				if (i != g)
					TempX[i] -= A[i][g] * X[g];
			}
			TempX[i] /= A[i][i];
		}
        norm = fabs(X[0] - TempX[0]);
		for (int h = 0; h < N; h++) {
			if (fabs(X[h] - TempX[h]) > norm)
				norm = fabs(X[h] - TempX[h]);
			X[h] = TempX[h];
		}
	} while (norm > eps);
	delete[] TempX;
}

Տես նաև

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