#!/usr/bin/python3

from copy import deepcopy
from math import sqrt

def Gauss(A, f):
    n = len(A)

    for i in range(n):
        for j in range(i, n):
            if (A[j][i] != 0):
                A[i], A[j] = A[j][:], A[i][:]
                f[i], f[j] = f[j], f[i]
                break

        for k in range(i + 1, n):
            A[i][k] /= A[i][i]
        f[i] /= A[i][i]
        A[i][i] = 1

        for j in range(i + 1, n):
            for k in range(i + 1, n):
                A[j][k] -= A[i][k] * A[j][i]
            f[j] -= f[i] * A[j][i]
            A[j][i] = 0

    for i in range(n - 1, -1, -1):
        for j in range(i - 1, -1, -1):
            f[j] -= f[i] * A[j][i]
            A[j][i] = 0

def GaussMax(A, f):
    n = len(A)
    permutations = []

    for i in range(n):
        max_ind = i
        for j in range(i, n):
            if (abs(A[i][j]) > abs(A[i][max_ind])):
                max_ind = i

        for k in range(n):
            A[k][i], A[k][max_ind] = A[k][max_ind], A[k][i]
        permutations.append([i, max_ind])

        for k in range(i + 1, n):
            A[i][k] /= A[i][i]
            f[i] /= A[i][i]
        A[i][i] = 1

        for j in range(i + 1, n):
            for k in range(i + 1, n):
                A[j][k] -= A[i][k] * A[j][i]
            f[j] -= f[i] * A[j][i]
            A[j][i] = 0

    for i in range(n - 1, -1, -1):
        for j in range(i - 1, -1, -1):
            f[j] -= f[i] * A[j][i]
            A[j][i] = 0

    for perm in permutations:
        f[perm[0]], f[perm[1]] = f[perm[1]], f[perm[0]]

def Det(A_orig):
    n = len(A_orig)
    A = deepcopy(A_orig)

    for i in range(n):
        for j in range(i, n):
            if (A[j][i] != 0):
                A[i], A[j] = A[j][:], A[i][:]
                break

        for j in range(i + 1, n):
            for k in range(i + 1, n):
                A[j][k] = A[j][k] * A[i][i] - A[i][k] * A[j][i]
            A[j][i] = 0

    res = 1
    for i in range(n):
        res *= A[i][i]

    return res

def MakeI(n):
    I = [0] * n
    for i in range(n):
        I[i] = [0] * n
        I[i][i] = 1

    return I

def Inv(A_orig):
    n = len(A_orig)
    A, I = deepcopy(A_orig), MakeI(n)

    for i in range(n):
        for j in range(i, n):
            if (A[j][i] != 0):
                A[i], A[j] = A[j][:], A[i][:]
                I[i], I[j] = I[j][:], I[i][:]
                break

        for k in range(i + 1, n):
            A[i][k] /= A[i][i]
        for k in range(n):
            I[i][k] /= A[i][i]
        A[i][i] = 1

        for j in range(i + 1, n):
            for k in range(i + 1, n):
                A[j][k] -= A[i][k] * A[j][i]
            for k in range(n):
                I[j][k] -= I[i][k] * A[j][i]
            A[j][i] = 0

    for i in range(n - 1, -1, -1):
        for j in range(i - 1, -1, -1):
            for k in range(n):
                I[j][k] -= I[i][k] * A[j][i]
            A[j][i] = 0

    return I

def MatrixNorm(A):
    n = 0

    for i in range(len(A)):
        for j in range(len(A[i])):
            n += a[i][j]**2

    return sqrt(n)

def ConditionNumber(A):
    return MatrixNorm(A) * MatrixNorm(Inv(A))

def IterMethod(A, f, w, EPS):
    n = len(A)
    x = [0] * n

    invANorm = MatrixNorm(Inv(A))
    iterCnt = 0

    while (True):
        for i in range(n):
            sum = 0
            for j in range(n):
                sum += A[i][j] * x[j]

            sum = w * (sum - f[i]) / A[i][i]
            x[i] -= sum

        nev = [0] * n
        for i in range(n):
            for j in range(n):
                nev[i] += A[i][j] * x[j]
            nev[i] -= f[i]

        nevNorm = 0
        for i in range(n):
            nevNorm += nev[i]**2
        nevNorm = sqrt(nevNorm)

        iterCnt += 1
        err = invANorm * nevNorm
        if (err < EPS):
            return x, iterCnt

a = [[1, -1], [1, 1]]
f = [-1, 1]

print(IterMethod(a, f, 0.5, 0.0001))