Linearizing the Method of Conjugate Gradients

Serge Gratton, David Titley-Peloquin, Philippe Toint, Jean Tshimanga Ilunga

Résultats de recherche: Contribution à un journal/une revueArticle

42 Downloads (Pure)

Résumé

The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.
langue originaleAnglais
Pages (de - à)110-126
journalSIAM Journal on Matrix Analysis and Applications
Volume35
Numéro de publication1
Date de mise en ligne précoce14 févr. 2014
Les DOIs
étatPublié - 2014

Empreinte digitale

Jacobian matrices
Conjugate Gradient
Spectral Norm
Algorithm Design
Jacobian matrix
Iterative Solution
Condition number
Iterate
Positive definite
System of equations
Experiments
Numerical Experiment
Denote
Estimate

mots-clés

    Citer ceci

    @article{c047f6d1df644c8fa72502cd464fb1a9,
    title = "Linearizing the Method of Conjugate Gradients",
    abstract = "The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.",
    keywords = "linear algebra, conjugate gradients, sesnistivity analysis",
    author = "Serge Gratton and David Titley-Peloquin and Philippe Toint and {Tshimanga Ilunga}, Jean",
    year = "2014",
    doi = "10.1137/120889848",
    language = "English",
    volume = "35",
    pages = "110--126",
    journal = "SIAM Journal on Matrix Analysis and Applications",
    issn = "0895-4798",
    publisher = "Society for Industrial and Applied Mathematics Publications",
    number = "1",

    }

    Linearizing the Method of Conjugate Gradients. / Gratton, Serge; Titley-Peloquin, David; Toint, Philippe; Tshimanga Ilunga, Jean.

    Dans: SIAM Journal on Matrix Analysis and Applications, Vol 35, Numéro 1, 2014, p. 110-126.

    Résultats de recherche: Contribution à un journal/une revueArticle

    TY - JOUR

    T1 - Linearizing the Method of Conjugate Gradients

    AU - Gratton, Serge

    AU - Titley-Peloquin, David

    AU - Toint, Philippe

    AU - Tshimanga Ilunga, Jean

    PY - 2014

    Y1 - 2014

    N2 - The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.

    AB - The method of conjugate gradients (CG) is widely used for the iterative solution of large sparse systems of equations Ax=b, where A is symmetric positive definite. Let xk denote the k-th iterate of CG. In this paper we obtain an expression for Jk, the Jacobian matrix of xk with respect to b. We use this expression to obtain computable bounds on the spectral norm condition number of xk, and to design algorithms to compute or estimate Jk.v and JkT.v for a given vector v. We also discuss several applications in which these ideas may be used. Numerical experiments are performed to illustrate the theory.

    KW - linear algebra

    KW - conjugate gradients

    KW - sesnistivity analysis

    U2 - 10.1137/120889848

    DO - 10.1137/120889848

    M3 - Article

    VL - 35

    SP - 110

    EP - 126

    JO - SIAM Journal on Matrix Analysis and Applications

    JF - SIAM Journal on Matrix Analysis and Applications

    SN - 0895-4798

    IS - 1

    ER -