<jupyter_start><jupyter_text>Successive Overrelaxation Method From https://en.wikipedia.org/wiki/Successive_over-relaxation:In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence.Given a square system of $n$ linear equations with unknown $x$:$A\mathbf x = \mathbf b$where:$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad  \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad  \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.$Then $A$ can be decomposed into a diagonal matrix $D$, and strictly lower and upper triangular matrices $L$ and $U$:$A=D+L+U, $where:$D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_{nn} \end{bmatrix}, \quad L = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ a_{21} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & 0 \end{bmatrix}, \quad U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}. $$$ \mathbf{x}^{(k+1)} = (D+\omega L)^{-1} \big(\omega \mathbf{b} - [\omega U + (\omega-1) D ] \mathbf{x}^{(k)}\big)$$where $\mathbf{x}^{(k)}$ is the ''k''th approximation or iteration of $\mathbf{x}$ and $\mathbf{x}^{(k+1)}$ is the next or ''k'' + 1 iteration of $\mathbf{x}$.If $\omega=1$, the SOR method simplifies to the Gauss-Seidel method.  Stop Condition:$$ \lVert X^{(k+1)} - X^{(k)} \rVert_2 \le 10^{-4}$$<jupyter_code>import numpy as np
def SOR(A, b, initial_guess):
    #Decomposing the matrix A into a diagonal matrix, a strictly lower matrix, and a strictly
    # upper matrix:
    U = np.triu(A,1)
    L = np.tril(A,-1)
    Diagnal = np.diag(A)
    D = np.diagflat(Diagnal)
    x = initial_guess
    
    #omega parameter must be between 0 and 2, otherwise the series diverges:
    omega = 1.9
    
    a1 = np.linalg.inv(D + omega*L)
    a2 = omega*b
    a3 = omega*U + (omega - 1)*D
    while(1):
        #Symbol of matrix multiplication in numpy is @
        x = a1@(a2-a3@x)
        #Norm2:
        if np.linalg.norm(A@x-b, np.inf) < 5*10**(-4):
            break
    return x 
A = np.matrix([[4.0,1.0],
               [1.0,3.0]])

b = np.matrix([[1.0],[2.0]])

initialGuess = np.matrix([[2.0],[1.0]])

sol = SOR(A,b,initialGuess)

print ('A:')
print(A)

print ('\nb:')
print(b)

print('\nSolution:')
print(sol)<jupyter_output>A:
[[4. 1.]
 [1. 3.]]

b:
[[1.]
 [2.]]

Solution:
[[0.09103337]
 [0.63616071]]
{'fraction_non_alphanumeric': 0.20498915401301518, 'fraction_numerical': 0.04193781634128706, 'mean_word_length': 2.9585121602288984, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '417840', 'license': 'MIT', 'n_tokens_mistral': 1161, 'n_tokens_neox': 1065, 'n_words': 305, 'path': '.ipynb_checkpoints/Successive_Overrelaxation_Method-checkpoint.ipynb', 'repo_name': 'enazari/iterative-methods-for-solvling-linear-systems-of-equations', 'size': '2766'}