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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

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

Մեթոդի նկարագրությունը[խմբագրել | խմբագրել կոդը]

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

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

որտեղ

,

Կգտնվի կապը այնպես, որ

Ընտրվում է սկզբնական մոտարկումը։ Յուրաքանչյուր քայլում անհրաժեշտ է առավելագույն կապը տանել զրոյի [2] ։

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

։

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

։

Օրինակ[խմբագրել | խմբագրել կոդը]

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

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

Iteration
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-ի պատճեի օրինակով «Գծային հավասարումների համակարգերի լուծման կաղապարներ», Բարեթ և այլն։

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Յուսիֆ Սաադ, Iterative Methods for Sparse Linear Systems, 1-ին հրատ․, PWS, 1996.։
  2. Ա․ Հաջիդիմոս, Successive overrelaxation (SOR) and related methods, Հաշվողական և կիրառական մաթեմատիկայի հանդես 123 (2000), 177-199:

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]