Ռելակսացիայի մեթոդ

Ռելակսացիայի մեթոդ, գծային հանրահաշվական հավասարումների լուծման իտերացիոն մեթոդ։

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

Գծային հավասարումների համակարգը

$\left\{{\begin{matrix}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+\ldots +a_{2n}x_{n}&=&b_{2}\\&\ldots &\\a_{n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\\\end{matrix}}\right.$

բերենք այսպիսի տեսքի՝

$\left\{{\begin{matrix}P_{11}x_{1}+P_{12}x_{2}+\ldots +P_{1n}x_{n}+c_{1}&=&0\\&\ldots &\\P_{n1}x_{1}+P_{n2}x_{2}+\ldots +P_{nn}x_{n}+c_{n}&=&0\\\end{matrix}}\right.$

որտեղ

$P_{ij}=-{\frac {a_{ij}}{a_{ii}}}$, $c_{i}={\frac {b_{i}}{a_{ii}}}$

Կգտնվի $R_{j}$ կապը այնպես, որ

$\left\{{\begin{matrix}R_{1}^{(0)}&=&c_{1}-x_{1}^{(0)}+\sum \limits _{j=2}^{n}P_{1j}x_{j}^{(0)}\\R_{2}^{(0)}&=&c_{2}-x_{2}^{(0)}+\sum \limits _{j=1,j\neq 2}^{n}P_{2j}x_{j}^{(0)}\\&\ldots &\\R_{n}^{(0)}&=&c_{n}-x_{n}^{(0)}+\sum \limits _{j=1}^{n-1}P_{nj}x_{j}^{(0)}\\\end{matrix}}\right.$

Ընտրվում է սկզբնական $X^{(0)}=0$ մոտարկումը։ Յուրաքանչյուր քայլում անհրաժեշտ է առավելագույն կապը տանել զրոյի $R_{s}^{(k)}=\delta x_{s}^{(k)}\Rightarrow R_{s}^{(k+1)}=0,R_{i}^{(k+1)}=R_{i}^{(k)}+P_{is}\delta x_{s}^{(k)}$։

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

$|R_{j}^{(k)}|<\varepsilon ,\forall j={\overline {1,n}}$։

Պատասխանը գտնվում է այս բանաձևով՝

$x_{i}\approx x_{i}^{(0)}+\sum _{j}\delta x_{i}^{(j)}$։

Օրինակ

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

${\begin{aligned}4x_{1}-x_{2}-6x_{3}+0x_{4}=2,\\-5x_{1}-4x_{2}+10x_{3}+8x_{4}=21,\\0x_{1}+9x_{2}+4x_{3}-2x_{4}=-12,\\1x_{1}+0x_{2}-7x_{3}+5x_{4}=-6.\end{aligned}}$

Հավասարումների համակարգը լուծելու համար որպես մոտարկման արժեք ընդոունենք՝ $\omega =0.5$ և նախնական մոտարկման վեկտոր՝ $\phi =(0,0,0)$։ Համաձայն ռելակսացիայի մեթոդի հաջորդական քայլերին անցման ստանում ենք հետևյալ աղյուսակը, որն իրենից ներկայացնում է մոտարկումների հաջորդականություն։ Այն իդեալականորեն, սակայն ոչ պարտադիր մոտենում է ճիշտ լուծմանը՝ (3, −2, 2, 1), 38 քայլերով։

Iteration	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$
1	0.25	-2.78125	1.6289062	0.5152344
2	1.2490234	-2.2448974	1.9687712	0.9108547
3	2.070478	-1.6696789	1.5904881	0.76172125
...	...	...	...	...
37	2.9999998	-2.0	2.0	1.0
38	3.0	-2.0	2.0	1.0

Վերևում բերված հավասարումների համակարգի լուծումը ներկայացնենք Python ծրագրավորման լեզվով՝

import numpy as np

def sor_solver(A, b, omega, initial_guess, convergence_criteria):
    """
    This is an implementation of the pseudo-code provided in the Wikipedia article.
    Arguments:
        A: nxn numpy matrix.
        b: n dimensional numpy vector.
        omega: relaxation factor.
        initial_guess: An initial solution guess for the solver to start with.
        convergence_criteria: The maximum discrepancy acceptable to regard the current solution as fitting.
    Returns:
        phi: solution vector of dimension n.
    """
    phi = initial_guess[:]
    residual = np.linalg.norm(np.matmul(A, phi) - b) #Initial residual
    while residual > convergence_criteria:
        for i in range(A.shape[0]):
            sigma = 0
            for j in range(A.shape[1]):
                if j != i:
                    sigma += A[i][j] * phi[j]
            phi[i] = (1 - omega) * phi[i] + (omega / A[i][i]) * (b[i] - sigma)
        residual = np.linalg.norm(np.matmul(A, phi) - b)
        print('Residual: {0:10.6g}'.format(residual))
    return phi

# An example case that mirrors the one in the Wikipedia article
residual_convergence = 1e-8
omega = 0.5 #Relaxation factor

A = np.matrix([4, -1, -6, 0],
              [-5, -4, 10, 8],
              [0, 9, 4, -2],
              [1, 0, -7, 5])

b = np.matrix([2, 21, -12, -6])

initial_guess = np.zeros(4)

phi = sor_solver(A, b, omega, initial_guess, residual_convergence)
print(phi)

Գրականություն

• Աբրահամ Բերման, Ռոբերտ Պլեմմոնս, «Ոչբացասական մատրիցները մաթեմատիկական գիտություններում»', 1994, SIAM. 0-89871-321-8.
• Black, Noel and Moore, Shirley, "Successive Overrelaxation Method", MathWorld.
• Netlib-ի պատճեի օրինակով «Գծային հավասարումների համակարգերի լուծման կաղապարներ», Բարեթ և այլն։

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

• Module for the SOR Method