Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du max. (French) Zbl 0531.65022

Pham Dinh Tao

Numer. Math. 45, 377-401 (1984).

Some direct and indirect methods are studied for computing \(Max\{x^ tAx,\phi_{\infty}(x)\leq 1\}\). Direct methods are constructed using particular properties of \(\phi_ 1,\phi_ 2,\phi_{\infty}\) norms. These methods are very simple, but uniquely suitable to certain families of matrices. The indirect method is the selfdual method, introduced by the author [Iterative methods for computing the bound norm of matrices. (Linear Alg. and Its Appl.; to appear) and Contribution à la théorie de normes et ses applications à l’analyse numérique. Doctoral thesis (1981). Université Scientifique et Médicale de Grenoble.] with \(\phi =\phi_ 1\). In this case the problem of choosing an initial vector so that convergence of the iterative sequence occurs to an optimal solution is largely discussed.

MSC:

65F35	Numerical computation of matrix norms, conditioning, scaling
15A63	Quadratic and bilinear forms, inner products
15A60	Norms of matrices, numerical range, applications of functional analysis to matrix theory

Keywords:

quadratic forms; direct and indirect methods; selfdual method; convergence; iterative sequence; optimal solution

References:

[1]	Angles d’Auriac, J.C.: Méthodes numériques pour l’étude de la dynamique des phénomènes critiques. Application aux verres de spins. Thèse, Grenoble, 1981
[2]	Bauer, F.L., Stoer, J., Witzgall, C.: Absolute and monotonic norms. Numer. Math.3, 257-264 (1961) · Zbl 0111.01602
[3]	Bieche, I.: La combinatoire: Un outil pour l’étude d’une transition de phase magnétique en physique du solide. Thèse, Grenoble, 1979
[4]	Bourbaki, N.: Espaces vectoriels topologiques, Chapitres 1 et 2, Hermann, Paris 1966 · Zbl 0145.37702
[5]	Day, M.: Normed linear spaces. Berlin, Heidelberg, New York: Springer 1962 · Zbl 0100.10802
[6]	Eggleston, H.G.: Convexity, Cambridge: University Press 1958
[7]	Gantmacher, F.R.: The theory of matrices, Vol. 2. New York: Chelsea Publishing Company 1959 · Zbl 0085.01001
[8]	Gastinel, N.: Matrices du second degré et normes générales en analyse numerique. Thèse d’Etat, Publications du Ministère de l’air, S.D.I.T., 1960
[9]	Gastinel, N.: Analyse numérique linéaire. Hermann, Paris, 1966 · Zbl 0151.21202
[10]	Glazman, I., Liubitch, Y.: Analyse linéaire dans les espaces de dimensions finies. Editions Mir Moscou 1972 · Zbl 0243.15002
[11]	Goles, E., Olivos, J.: Comportement itératif des fonctions à seuil. Séminaire d’Analyse Numérique, U.S.M.G. (1979)
[12]	Goles, E., Olivos, J.: Comportement itératif des fonctions à multiseuils. Rapport de recherche no 189, U.S.M.G. (1980) · Zbl 0445.94047
[13]	Gregory, R.T., Karney, D.L.: A collection of matrices for testing computational algorithms. New York: Wiley Interscience 1969 · Zbl 0195.44803
[14]	Householder, A.S.: The theory of matrices in numerical analysis. New York: Blaisdell 1964 · Zbl 0161.12101
[15]	Klee, V.L.: Extremal structure of convex sets II. Math. Z.69, 90-104 (1958) · Zbl 0079.12502
[16]	Kothe, G.: Topological vector spaces I. Berlin, Heidelberg, New York: Springer 1969
[17]	Lacolle, B.: Aspects théoriques et pratiques du problème du partionnement. Séminaire d’Analyse Numerique, Grenoble, 1971
[18]	Lacolle, B.: Bi-partionnement d’une matrice du type somme de deux anti-scalaires symétriques. Séminaire d’Analyse Numérique, Grenoble, 1975
[19]	Lacolle, B.: Quelques problèmes de restructuration dans un environnement paginé. Thèse de troisième cycle, Grenoble, 1976
[20]	Pham Dinh Tao: Normes d’opérateurS ? de matrices et leur rayon spectral. Exposant critique des espaces de BanachE = (? n ,?). Séminaire d’Analyse Numérique, Grenoble, 1973
[21]	Pham Dinh Tao: Etude de la structure convexe de normes d’opérateurs de matrices et ses applications. Rapport de recherche no 92, U.S.M.G. (1977)
[22]	Pham Dinh Tao: Eléments homoduaux d’une matriceA relatifs à un couple de normes (?, ?). Applications au calcul deS ? ? (A). Séminaire d’Analyse Numérique, Grenoble, 1975
[23]	Pham Dinh Tao: Calcul du maximum d’une forme quadratique définie positive sur la boule unité de la norme du maximum. Séminaire d’Analyse Numérique, Grenoble, 1976
[24]	Pham Dinh Tao: Méthodes directes et indirectes pour le calcul du maximum d’une forme quadratique définie positive sur la boule unité de la norme du maximum, Colloque d’Analyse Numérique (Port Bail) (1976)
[25]	Pham Dinh Tao: Iterative methods for computing the bound-norm of matrices. Linear Algebra and Its Appl. (To appear)
[26]	Pham Dinh Tao: Contribution à la théorie de normes et ses applications à l’analyse numérique. Thèse d’Etat (1981). Université Scientifique Médicale de Grenoble
[27]	Pham Dinh Tao: Etude des propriétés géométriques et différentielles des normes d’opérateurs de matricesS ? ? et ses applications. Rapport de recherche no92, U.S.M.G. (1978) (Publication à paraître dans Acta Mathematica)
[28]	Pham Dinh Tao: Etude par dualité du problème de calcul de normes d’opérateurs de matrices. Séminaire d’Analyse Numérique, Grenoble, (1981) (Publication à paraître dans Linear and Multilinear Algebra)
[29]	Pham Dinh Tao: Convergence of a subgradient method for computing the bound-norm of matrices. Linear Algebra and Its Appl. (To appear) · Zbl 0563.65029
[30]	Robert, F.: Une approche booléenne du problème de la frustration. Séminaire d’Analyse Numérique, Grenoble, 1978
[31]	Roberts, A.W., Varberg, D.E.: Convex functions. New York: Academic Press 1973 · Zbl 0271.26009
[32]	Rockafellar, R.T.: Convex analysis. New Jersey: Princeton 1970 · Zbl 0193.18401
[33]	Sakarovitch, M.: Programmation linéaire, U.S.M.G., 1973
[34]	Varga, R.S.: Matrix iterative analysis. Englewood Cliffs, New Jersey: Prentice Hall 1962 · Zbl 0133.08602