Conjugate gradient method
A comparison of the convergence ofgradient descent with optimal step size (in green) and conjugate gradient (in red) for minimizing a quadratic function associated with a given linear system. Conjugate gradient, assuming exact arithmetics, converges in at most n steps where n is the size of the matrix of the system (here n=2).
that takes account of information about the inclusion of — the spectrum of the operator — in a certain set , and uses the properties and parameters of those polynomials that deviate least from zero on and are equal to 1 at 0.
in which for a given one obtains a sequence as . In (2) and (3) and are the numerical parameters of the method. If , then the initial error and the error at the -th iteration are related by the formula
where are the elements of the permutation , while for method (3)they are calculated from the recurrence relations
where . Then
Then after iterations, inequality (8) holds for .
then once again one obtains a Chebyshev iteration method after iterations. To ensure stability, the set(14) is decomposed into two sets: in the -th set, , one puts the for which is a root of the -th bracket in (13); within each of the subsets the are permuted according to the permutation . For one substitutes elements of the first set in (5), (11), and for one uses the second subset; the permutation is defined in the same way. Continuing in an analogous way the process of forming parameters, one obtains an infinite sequence , uniformly distributed on , called a -sequence, for which the method (2) becomes optimal with and
and the application of the Chebyshev iteration method to this equation. The operator is defined by taking account of two facts: 1) the algorithm for computing a quantity of the form should not be laborious; and 2) should lie in a set that ensures the fast convergence of the Chebyshev iteration method.
|||G.I. Marchuk, V.I. Lebedev, “Numerical methods in the theory of neutron transport” , Harwood (1986) (Translated from Russian)|
|||N.S. Bakhvalov, “Numerical methods: analysis, algebra, ordinary differential equations” , MIR (1977) (Translated from Russian)|
|||G.I. Marchuk, “Methods of numerical mathematics” , Springer (1982) (Translated from Russian)|
|||A.A. Samarskii, “Theorie der Differenzverfahren” , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)|
|[5a]||V.I. Lebedev, S.A. Finogenov, “The order of choices of the iteration parameters in the cyclic Chebyshev iteration method” Zh. Vychisl. Mat. i Mat. Fiz. , 11 : 2 (1971) pp. 425–438 (In Russian)|
|[5b]||V.I. Lebedev, S.A. Finogenov, “Solution of the problem of parameter ordering in Chebyshev iteration methods” Zh. Vychisl. Mat. i Mat. Fiz , 13 : 1 (1973) pp. 18–33 (In Russian)|
|[5c]||V.I. Lebedev, S.A. Finogenov, “The use of ordered Chebyshev parameters in iteration methods” Zh. Vychisl. Mat. i Mat. Fiz. , 16 : 4 (1976) pp. 895–907 (In Russian)|
|[6a]||V.I. Lebedev, “Iterative methods for solving operator equations with spectrum located on several segments” Zh. Vychisl. Mat. i Mat. Fiz. , 9 : 6 (1969) pp. 1247–1252 (In Russian)|
|[6b]||V.I. Lebedev, “Iteration methods for solving linear operator equations, and polynomials deviating least from zero” , Mathematical analysis and related problems in mathematics , Novosibirsk (1978) pp. 89–108 (In Russian)|
This formula has already been used in [a1] in the numerical determination of fundamental modes.
|[a1]||D.A. Flanders, G. Shortley, “Numerical determination of fundamental modes” J. Appl. Physics, 21 (1950) pp. 1326–1332|
|[a2]||G.E. Forsythe, W.R. Wasow, “Finite difference methods for partial differential equations” , Wiley (1960)|
|[a3]||G.H. Golub, C.F. van Loan, “Matrix computations” , North Oxford Acad. (1983)|
|[a4]||G.H. Golub, R.S. Varga, “Chebyshev semi-iterative methods, successive over-relaxation methods and second-order Richardson iterative methods I, II” Num. Math. , 3 (1961) pp. 147–156; 157–168|
|[a5]||T.A. Manteuffel, “The Tchebychev iteration for nonsymmetric linear systems” Num. Math. , 28 (1977) pp. 307–327|
|[a6a]||L.F. Richardson, “The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam” Philos. Trans. Roy. Soc. London Ser. A , 210 (1910) pp. 307–357|
|[a6b]||L.F. Richardson, “The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam” Proc. Roy. Soc. London Ser. A , 83 (1910) pp. 335–336|
|[a7]||G. Shortley, “Use of Tchebycheff-polynomial operators in the numerical solution of boundary-value problems” J. Appl. Physics , 24 (1953) pp. 392–396|
|[a8]||J.W. Sheldon, “On the numerical solution of elliptic difference equations” Math. Tables Aids Comp. , 9 (1955) pp. 101–112|
|[a9]||E.L. Stiefel, “Kernel polynomials in linear algebra and their numerical applications” , Appl. Math. Ser. , 49 , Nat. Bur. Standards (1958)|
|[a10]||R.S. Varga, “Matrix iterative analysis” , Prentice-Hall (1962)|
|[a11]||E.L. Wachspress, “Iterative solution of elliptic systems, and applications to the neutron diffusion equations of nuclear physics” , Prentice-Hall (1966)|
- e(k + 1) = e(k) − ωAe(k) = (I − ωA)e(k).
- Richardson, L.F. (1910). “The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam”.Philos. Trans. Roy. Soc. London Ser. A 210: 307–357.
- Vyacheslav Ivanovich Lebedev (2002). “Chebyshev iteration method”. Springer. Retrieved 2010-05-25. Appeared in Encyclopaedia of Mathematics (2002), Ed. by Michiel Hazewinkel, Kluwer – ISBN 1402006098
- Extremal polynomials with application to Richardson iteration for indefinite linear systems (Technical summary report / Mathematics Research Center, University of Wisconsin–Madison)