<jupyter_start><jupyter_text>Т.к. $||Ax - b||^2 =  = x^TA^TAx - 2b^TAx + b^Tb$, будем минимизировать функцию $f(x) = \frac{1}{2}x^TA^TAx - b^TAx$.<jupyter_code>def conjugate_gradient(A, b, x_0):
    x = x_0
    A = SparseMatrix(A)
    A_T = A.transpose()
    v = A_T * (A * x) - b * A
    d = v
    v_norm = np.dot(v, v)
    
    result = [x.copy()]
    for i in range(len(b)):
        Ad = A_T * (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
        result.append(x.copy())
    return result
def show_cgd():
    A = np.random.rand(5, 5)
    A = A @ A.T
    sD = sp.linalg.sqrtm(np.linalg.inv(np.diag(np.diag(A))))
    A = sD.T @ A @ sD
    
    b = np.random.rand(5)
    fig, axs = plt.subplots(1, 1, figsize=(10, 7))
    x = np.zeros_like(b)
    
    estimates_conjugate_gradient = conjugate_gradient(A, b, x)
    
    axs.plot([i for i in range(len(estimates_conjugate_gradient))], [np.linalg.norm(A @ x - b) for x in estimates_conjugate_gradient], label='CGD')
    axs.legend()
    axs.set_ylabel(r'$\|Ax_k-b\|$', fontsize=20)
    axs.set_xlabel(r'$k$', fontsize=20)
    axs.set_yscale('log')
    plt.close(fig)
    return fig
show_cgd()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17293233082706766, 'fraction_numerical': 0.013533834586466165, 'mean_word_length': 2.38676844783715, 'pattern_counts': {'":': 0, '<': 5, '<?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': '152995', 'license': 'MIT', 'n_tokens_mistral': 624, 'n_tokens_neox': 601, 'n_words': 118, 'path': 'shmidt-svetlana/HW02.ipynb', 'repo_name': 'Malkovsky/co-mkn-hw-2021', 'size': '1330'}