<jupyter_start><jupyter_text>Минимизировать $\lVert Ax - b \rVert$ это тоже самое, что минимизировать $\lVert Ax - b \rVert^2$, т.к. норма всегда не отрицательна.Второе выражение есть ни что иное, как $x^TA^TAx - 2b^TAx + const$. Минимизировать неконстантную часть - это тоже самое, что было на лекции, если сделать замену $A = A^TA, b = A^Tb$<jupyter_code>def conjugate_gradient(A, b, x_0 = None):
    if x_0 is None:
        x_0 = np.zeros(len(b))
    x = x_0
    
    b = A.T() @ b
    A = Matrix(A.T().to_np() @ A.to_np())
    
    v = (A @ x - b)
    d = v
    v_norm = np.dot(v, v)
    for i in range(len(b)):
        Ad = A @ d
        alpha = v_norm / np.dot(d, Ad)
        x = x - alpha * d
        v = v - alpha * Ad
        v_norm_new = np.dot(v, v)
        d = v + (v_norm_new / v_norm) * d
        v_norm = v_norm_new
    return x
import cvxpy as cp
from tqdm import tqdm

for i in tqdm(range(10)):
    A = np.random.rand(5, 5)
    b = np.random.rand(5)

    x = cp.Variable(5)
    cs = []
    d = cp.Minimize(cp.sum_squares(A @ x - b))
    cp.Problem(d, cs).solve()
    cp_result = np.array(x.value)
    
    result = conjugate_gradient(Matrix(A), b)
    try:
        assert(np.all(result - cp_result < 1e-2))
        assert(np.all(-result + cp_result > -1e-2))
    except:
        print(A)
        print(b)
        print(cp_result)
        print(result)<jupyter_output>100%|██████████████████████████████████████████| 10/10 [00:00<00:00, 139.55it/s]
{'fraction_non_alphanumeric': 0.17008196721311475, 'fraction_numerical': 0.02459016393442623, 'mean_word_length': 2.2555555555555555, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, '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': '411608', 'license': 'MIT', 'n_tokens_mistral': 677, 'n_tokens_neox': 639, 'n_words': 149, 'path': 'korotchenko-denis/hw2/hw2-korotchenko.ipynb', 'repo_name': 'Malkovsky/co-mkn-hw-2021', 'size': '1464'}