Talk:Conjugate gradient method

This is the talk page for discussing improvements to the Conjugate gradient method article. This is not a forum for general discussion of the subject of the article.

Add new text under old text. New to Wikipedia? Welcome! Learn to edit; get help. Start a new topic Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: 1Auto-archiving period: 2 months

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

Archives

Archive 1

This page has archives. Topics inactive for 60 days are automatically archived by Lowercase sigmabot III.

The explanation skips a large important part of the correctness proof, which shows that the mentioned "Gram-Schmidt orthonormalization" only needs to consider the latest direction p_k and need not be performed relative to all previous directions p_j where j < k. This can be deduced from the fact that the r_k and p_k span the same Krylov subspace, but it should be highlighted how this implies that p_j r_k = 0 for j <= k and p_j A r_k = 0 for j < k. — Preceding unsigned comment added by 46.128.186.9 (talk) 16:04, 13 December 2023 (UTC)Reply

In your algorithm, the formula to calculate pk differs from Jonathan Richard Shewchuk paper. The index of r should be k instead of k-1. Mmmh, sorry, it seams to be correct! ;-) —The preceding unsigned comment was added by 171.66.40.105 (talk • contribs) 01:45, 21 February 2007 (UTC)

additional comment:

basis vector set $P = \{ p_0, ... p_{n-1} \}$.

In the subsection, I can see that r_i^T r_j = 0. The following is quoted from the same. However, in the algorithm, in the calculation for the value of {\beta}, the r_k^T r_k comes up in the denominator, which does not look right. In my openion, the denominator should be r_k^T r_k+1. However, I could be incorrect, and hence, I would like to bring this to the notice of the experts. — Preceding unsigned comment added by Zenineasa (talk • contribs) 13:25, 26 November 2021 (UTC)Reply

I can't wrap my head around the fact that it's optimizing

${\displaystyle f(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{\mathsf {T}}\mathbf {A} \mathbf {x} -\mathbf {x} ^{\mathsf {T}}\mathbf {b} ,\qquad \mathbf {x} \in \mathbf {R} ^{n}\,}$.

Abstractly, I think (?) the idea is that we choose ${\displaystyle f(x)}$ such that

${\displaystyle \nabla f(\mathbf {x} )=\mathbf {A} \mathbf {x} -\mathbf {b} \,}$

and so the residual vector is the gradient of the surface. But coming at it from the perspective of "let's minimize the residual", my line of thinking is let

${\displaystyle g(\mathbf {x} ):=\|\mathbf {A} \mathbf {x} -\mathbf {b} \|_{2}^{2}=(\mathbf {Ax-b} )^{\top }(\mathbf {Ax-b} )=\mathbf {x^{\top }A^{\top }Ax} -2\mathbf {b^{\top }Ax+b^{\top }b} }$

which we could drop the constant ${\displaystyle \mathbf {b^{\top }b} }$ from. That's similar but decidedly different from ${\displaystyle f(\mathbf {x} )}$. What gives? Is ${\displaystyle f(\mathbf {x} )}$ minimizing the residual? Can the norm of the residual be massaged to look like ${\displaystyle f(\mathbf {x} )}$? —Ben FrantzDale (talk) 21:30, 18 January 2023 (UTC)Reply

The method is supposed to be used for PSD matrices, but the example given in "A pathological example" is not PSD. Thomasda (talk) 17:47, 23 January 2024 (UTC)Reply

A method is not supposed to be used only for specific entries. It is supposed to be used on any input for which it converges to a solution. In § Conjugate gradient on the normal equations, it is shown that it may be applied to any linear system. When used for unconstrained optimization, it can be used for finding a local minimum of a non-convex function, in which case, if it converges, one cannot predict which local minimum is obtained. Personally, around 1970, I used this method for finding a solution of an overconstrained system of 81 quadratic equations in 54 unknowns, by minimizing the sum of the squares of the equations (see System of polynomial equations § General solving algorithms). More than 50 years later, I do not know any other method that works on this problem. D.Lazard (talk) 20:49, 23 January 2024 (UTC)Reply

That's fair, but in the beginning of the article it is assumed A is PSD: "is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite." and "the known ${\displaystyle n\times n}$ matrix ${\displaystyle \mathbf {A} }$ is symmetric (i.e., A^T = A), positive-definite (i.e. x^TAx > 0 for all non-zero vectors ${\displaystyle \mathbf {x} }$ in Rⁿ), and real".

So either it should be more clarified that the method is " supposed to be used on any input" (including in the analysis section, which also assumes PSD, as far as I can tell), or the Pathological example should note that it is not PSD, and hence doesn't conflict with the rest of the analysis.Thomasda (talk) 01:52, 24 January 2024 (UTC)Reply

The matrix is positive definite:

${\displaystyle x^{T}Wx=tx_{1}^{2}+\sum _{i=2}^{n-1}(1+t)x_{i}^{2}+2\sum _{i=1}^{n-1}{\sqrt {t}}x_{i}x_{i+1}}$

${\displaystyle =\sum _{i=1}^{n-1}(tx_{i}^{2}+2{\sqrt {t}}x_{i}x_{i+1}+x_{i+1}^{2})+tx_{n}^{2}}$

${\displaystyle =\sum _{i=1}^{n-1}({\sqrt {t}}x_{i}+x_{i+1})^{2}+tx_{n}^{2}\geq 0.}$

I don't know the derivation of those convergence results, and the cited source doesn't provide it either, but I did verify it numerically. Nothing contradicts the convergence theorem, since that is given in the energy norm.

Nileliketheriver (talk) 20:02, 3 August 2025 (UTC)Reply