What's wrong with my GMRES implementation?

Question

I'm trying to implement GMRES in Jupyter Notebook, which is (in case you don't know):

This is my code:

import numpy as np

def GMRes(A, b, x0, e, nmax_iter, restart=None):
    r = b - np.asarray(np.dot(A, x0)).reshape(-1)

    x = []
    q = [0] * (nmax_iter)

    x.append(r)

    q[0] = r / np.linalg.norm(r)

    h = np.zeros((nmax_iter + 1, nmax_iter))

    for k in range(nmax_iter):
        y = np.asarray(np.dot(A, q[k])).reshape(-1)

        for j in range(k):
            h[j, k] = np.dot(q[j], y)
            y = y - h[j, k] * q[j]
        h[k + 1, k] = np.linalg.norm(y)
        if (h[k + 1, k] != 0 and k != nmax_iter - 1):
            q[k + 1] = y / h[k + 1, k]

        b = np.zeros(nmax_iter + 1)
        b[0] = np.linalg.norm(r)

        result = np.linalg.lstsq(h, b)[0]

        x.append(np.dot(np.asarray(q).transpose(), result) + x0)

    return x

According to me it should be correct, but when I execute:

A = np.matrix('1 1; 3 -4')
b = np.array([3, 2])
x0 = np.array([1, 2])

e = 0
nmax_iter = 5

x = GMRes(A, b, x0, e, nmax_iter)

print(x)

Note: For now e is doing nothing.

I get this:

[array([0, 7]), array([ 1.,  2.]), array([ 1.35945946,  0.56216216]), array([ 1.73194463,  0.80759216]), array([ 2.01712479,  0.96133459]), array([ 2.01621042,  0.95180204])]

x[k] should be approaching to (32/7, -11/7), as this is the result, but instead it is approaching to (2, 1), what am I doing wrong?

Answer 1

I think the algorithm is giving the correct result.

You are trying to solve Ax=b where:

If you try to find a solution by hand, the matrix operation you are trying to solve is equivalent to a system that can be solved using substitution.

If you try to solve it you'll see that the solution is:

Which is the same solution your algorithm is giving.

You can double check this using the GMRES implementation already in scipy:

import scipy.sparse.linalg as spla
import numpy as np

A = np.matrix('1 1; 3 -4')
b = np.array([3, 2])
x0 = np.array([1, 2])
spla.gmres(A,b,x0)

Which outputs

array([ 2.,  1.])