Approximation numérique de racines isolées multiples de systèmes analytiques
Annales Henri Lebesgue, Volume 3 (2020) , pp. 901-957.

Metadata

Keywordssystèmes d’équations, racines singulières, déflation, rang numérique, évaluation Keywordssystems of equations, singular roots, deflation, numerical rank, evaluation

Abstract

L’approximation d’une racine isolée multiple est un problème difficile. En effet la racine peut même être répulsive pour une méthode de point fixe comme la méthode de Newton. La littérature sur le sujet est vaste mais les réponses proposées pour résoudre ce problème ne sont pas satisfaisantes. Des méthodes numériques qui permettent de faire une analyse locale de convergence sont souvent élaborées sous des hypothèses particulières. Ce point de vue privilégiant l’analyse numérique néglige la géométrie et la structure de l’algèbre locale. C’est ainsi qu’ont émergé des méthodes qualifiés de symboliques-numériques. Mais l’analyse numérique précise de ces méthodes pourtant riches d’enseignement n’a pas été faite. Nous proposons dans cet article une méthode de type symbolique-numérique dont le traitement numérique est certifié. L’idée générale est de construire une suite finie de systèmes admettant la même racine, appelée suite de déflation, telle que la multiplicité de la racine chute strictement entre deux systèmes successifs. La racine devient ainsi régulière lors du dernier système. Il suffit alors d’en extraire un système carré régulier pour obtenir ce que nous appelons système déflaté. Nous avions déjà décrit la construction de cette suite de déflation quand la racine est connue. L’originalité de cette étude consiste d’une part à définir une suite de déflation à partir d’un point proche de la racine et d’autre part à donner une analyse numérique de cette méthode. Le cadre fonctionnel de cette analyse est celui des systèmes analytiques constitués de fonctions de carré intégrable. En utilisant le noyau de Bergman, noyau reproduisant de cet espace fonctionnel, nous donnons une α-théorie à la Smale de cette suite de déflation. De plus nous présentons des résultats nouveaux relatifs à la détermination du rang numérique d’une matrice et à celle de la proximité à zéro de l’application évaluation. Comme conséquence importante nous donnons un algorithme de calcul d’une suite de déflation qui est libre de ε, quantité-seuil qui mesure l’approximation numérique, dans le sens que les entrées de cet algorithme ne comportent pas la variable ε.


References

[AH11] Argyros, Ionnis K.; Hilout, Said Semilocal convergence of Newton’s method for singular systems with constant rank derivatives, J. Korean Soc. Math. Educ., Ser. B, Pure Appl. Math., Volume 18 (2011) no. 2, pp. 97-111 | MR 2817137 | Zbl 1242.65101

[BCSS97] Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve Complexity and Real Computation, Springer, 1997 (foreword by Richard M. Karp) | Zbl 0948.68068

[CLO05] Cox, David A.; Little, John; O’shea, Donald B. Using algebraic geometry, Graduate Texts in Mathematics, Volume 185, Springer, 2005 | MR 2122859 | Zbl 1079.13017

[Ded06] Dedieu, Jean-Pierre Points fixes, zéros et la méthode de Newton, Mathématiques & Applications, Volume 54, Springer, 2006 | Zbl 1095.65047

[DK80a] Decker, Dwight W.; Kelley, Carl T. Newton’s method at singular points. I., SIAM J. Numer. Anal., Volume 17 (1980) no. 1, pp. 66-70 | Article | MR 559463 | Zbl 0428.65037

[DK80b] Decker, Dwight W.; Kelley, Carl T. Newton’s method at singular points. II, SIAM J. Numer. Anal., Volume 17 (1980) no. 3, pp. 465-471 | Article | MR 581492 | Zbl 0453.65037

[DKK83] Decker, Dwight W.; Keller, Herbert B.; Kelley, Carl T. Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal., Volume 20 (1983) no. 2, pp. 296-314 | Article | MR 694520 | Zbl 0571.65046

[DLZ11] Dayton, Barry H.; Li, Tien-Yien; Zeng, Zhonggang Multiple zeros of nonlinear systems, Math. Comput., Volume 80 (2011) no. 276, pp. 2143-2168 | Article | MR 2813352 | Zbl 1242.65102

[DS01] Dedieu, Jean-Pierre; Shub, Mike On simple double zeros and badly conditioned zeros of analytic functions of n variables, Math. Comput., Volume 70 (2001) no. 233, pp. 319-327 | Article | MR 1680867 | Zbl 0965.65071

[DZ05] Dayton, Barry H.; Zeng, Zhonggang Computing the multiplicity structure in solving polynomial systems, Proceedings of the 2005 international symposium on Symbolic and algebraic computation (2005), pp. 116-123 | Zbl 1360.65151

[EI95] Eisenstat, Stanley C.; Ipsen, Ilse C. F. Relative perturbation techniques for singular value problems, SIAM J. Numer. Anal., Volume 32 (1995) no. 6, pp. 1972-1988 | Article | MR 1360467 | Zbl 0837.65039

[Ems78] Emsalem, Jacques Géométrie des points épais, Bull. Soc. Math. Fr., Volume 106 (1978), pp. 399-416 | Article | Numdam | MR 518046 | Zbl 0396.13017

[EY36] Eckart, Carl; Young, Gale The approximation of one matrix by another of lower rank, Psychometrika, Volume 1 (1936), pp. 211-218 | Article | Zbl 62.1075.02

[FH05] Fierro, Ricardo D.; Hansen, Per Christian UTV expansion pack : Special-purpose rank-revealing algorithms, Numer. Algorithms, Volume 40 (2005) no. 1, pp. 47-66 | Article | MR 2161383 | Zbl 1079.65026

[GLSY05] Giusti, Marc; Lecerf, Grégoire; Salvy, Bruno; Yakoubsohn, Jean-Claude On location and approximation of clusters of zeros of analytic functions, Found. Comput. Math., Volume 5 (2005) no. 3, pp. 257-311 | Article | MR 2168678

[GLSY07] Giusti, Marc; Lecerf, Grégoire; Salvy, Bruno; Yakoubsohn, Jean-Claude On location and approximation of clusters of zeros : Case of embedding dimension one, Found. Comput. Math., Volume 7 (2007) no. 1, pp. 1-58 | Article | MR 2283341 | Zbl 1124.65047

[GO81] Griewank, Andreas; Osborne, Michael R. Newton’s method for singular problems when the dimension of the null space is >1, SIAM J. Numer. Anal., Volume 18 (1981) no. 1, pp. 145-149 | Article | MR 603436 | Zbl 0453.65032

[GO83] Griewank, Andreas; Osborne, Michael R. Analysis of Newton’s method at irregular singularities, SIAM J. Numer. Anal., Volume 20 (1983) no. 4, pp. 747-773 | Article | MR 708455 | Zbl 0525.65025

[Gri85] Griewank, Andreas n solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev., Volume 27 (1985) no. 4, pp. 537-563 | Article | MR 812453 | Zbl 0598.65026

[GY14] Giusti, Marc; Yakoubsohn, Jean-Claude Multiplicity hunting and approximating multiple roots of polynomial systems, Recent Advances in Real Complexity and Computation (Contemporary Mathematics) Volume 604, American Mathematical Society, 2014, pp. 105-128 | Article

[HMS17] Hauenstein, Jonathan D.; Mourrain, Bernard; Szanto, Agnes On deflation and multiplicity structure, J. Symb. Comput., Volume 83 (2017), pp. 228-253 | Article | MR 3645652 | Zbl 1387.13063

[Kat95] Kato, Tosio Perturbation theory for linear operators, Classics in Mathematics, Volume 132, Springer, 1995 | Zbl 0836.47009

[Kra13] Krantz, Steven G. Geometric analysis of the Bergman kernel and metric, Graduate Texts in Mathematics, Volume 268, Springer, 2013 | MR 3114665 | Zbl 1281.32004

[KS83] Kelley, Carl T.; Suresh, Ram A new acceleration method for Newton’s method at singular points, SIAM J. Numer. Anal., Volume 20 (1983) no. 5, pp. 1001-1009 | Article | MR 714695 | Zbl 0542.65032

[Lec02] Lecerf, Grégoire Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math., Volume 2 (2002) no. 3, pp. 247-293 | Article | MR 1907381 | Zbl 1030.65050

[LVZ06] Leykin, Anton; Verschelde, Jan; Zhao, Ailing Newton’s method with deflation for isolated singularities of polynomial systems, Theor. Comput. Sci., Volume 359 (2006) no. 1-3, pp. 111-122 | Article | MR 2251604 | Zbl 1106.65046

[LZ12a] Li, Nan; Zhi, Lihong Computing isolated singular solutions of polynomial systems : case of breadth one, SIAM J. Numer. Anal., Volume 50 (2012) no. 1, pp. 354-372 | MR 2888317 | Zbl 1247.65065

[LZ12b] Li, Nan; Zhi, Lihong Computing the multiplicity structure of an isolated singular solution : Case of breadth one, J. Symbolic Comput., Volume 47 (2012) no. 6, pp. 700-710 | MR 2908589 | Zbl 1239.13038

[LZ14] Li, Nan; Zhi, Lihong Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal., Volume 52 (2014) no. 4, pp. 1623-1640 | MR 3229659 | Zbl 1310.65056

[Mar11] Markovsky, Ivan Low rank approximation : algorithms, implementation, applications, Communications and Control Engineering Series, Springer, 2011

[MG03] Miranian, L.; Gu, Ming Strong rank revealing LU factorizations, Linear Algebra Appl., Volume 367 (2003) no. 1, pp. 1-16 | Article | MR 1976906 | Zbl 1020.65016

[Mir60] Mirsky, Leon Symmetric gauge functions and unitarily invariant norms, Q. J. Math., Oxf. II. Ser., Volume 11 (1960), pp. 50-59 | Article | MR 114821 | Zbl 0105.01101

[MM11] Mantzaflaris, Angelos; Mourrain, Bernard Deflation and certified isolation of singular zeros of polynomial systems, ISSAC 2011—Proceedings of the 36th international symposium on Symbolic and Algebraic Computation (2011), pp. 249-256 | Zbl 1323.65054

[Mou97] Mourrain, Bernard Isolated points, duality and residues, J. Pure Appl. Algebra, Volume 117/118 (1997), pp. 469-493 | Article | MR 1457851 | Zbl 0896.13020

[Oji87] Ojika, Takeo Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations, J. Math. Anal. Appl., Volume 123 (1987) no. 1, pp. 199-221 | Article | MR 881541 | Zbl 0625.65043

[OWM83] Ojika, Takeo; Watanabe, Satoshi; Mitsui, Taketommo Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl., Volume 96 (1983) no. 2, pp. 463-479 | Article | MR 719330 | Zbl 0525.65027

[Pan00] Pan, Chin-Tsuan On the existence and computation of rank-revealing LU factorizations, Conference Celebrating the 60th Birthday of Robert J. Plemmons (Winston–Salem, NC, 1999) (Linear Algebra and its Applications) Volume 316 (2000) no. 1-3, pp. 199-222 | MR 1782425 | Zbl 0962.65023

[Ral66] Rall, Louis B. Convergence of the Newton process to multiple solutions, Numer. Math., Volume 9 (1966) no. 1, pp. 23-37 | Article | MR 210316 | Zbl 0163.38702

[Red78] Reddien, Georges W. On Newton’s method for singular problems, SIAM J. Numer. Anal., Volume 15 (1978) no. 5, pp. 993-996 | Article | MR 507559 | Zbl 0397.65042

[Red79] Reddien, Georges W. Newton’s method and high order singularities, Comput. Math. Appl., Volume 5 (1979) no. 2, pp. 79-86 | Article | MR 539566 | Zbl 0436.65032

[Rud08] Rudin, Walter Function theory in the unit ball of C n , Classics in Mathematics, Springer, 2008 (Reprint of the 1980 original) | Zbl 1139.32001

[Sch70] Schröder, Ernst Ueber unendliche viele Algorithmen zur Auflösung der Gleichungen, Math. Ann., Volume 2 (1870), pp. 317-365 | Article

[Sha67] Shamanskiĭ, V. On the application of Newton’s method in a singular case, USSR Computational Mathematics and Mathematical Physics, Volume 7 (1967) no. 4, pp. 72-85 | Article | MR 219235

[SS90] Stewart, Gilbert W.; Sun, Ji-Guang Matrix Perturbation Theory, Computer Science and Scientific Computing, Academic press, 1990 | Zbl 0706.65013

[SY05] Shen, Yun-Qiu; Ypma, Tjalling J. Newton’s method for singular nonlinear equations using approximate left and right nullspaces of the jacobian, Appl. Numer. Math., Volume 54 (2005) no. 2, pp. 256-265 | Article | MR 2148044 | Zbl 1081.65046

[Wey12] Weyl, Hermann Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann., Volume 71 (1912) no. 4, pp. 441-479 | Article | MR 1511670 | Zbl 43.0436.01

[XL08] Xu, Xiubin; Li, Chong Convergence criterion of Newton’s method for singular systems with constant rank derivatives, J. Math. Anal. Appl., Volume 345 (2008) no. 2, pp. 689-701 | MR 2429168 | Zbl 1154.65332

[Yak90] Yakoubsohn, Jean-Claude On Newton’s rule and Sylvester’s theorems, J. Pure Appl. Algebra, Volume 65 (1990) no. 3, pp. 293-309 | Article | MR 1072286 | Zbl 0711.26007

[Yam83] Yamamoto, Norio Newton’s method for singular problems and its application to boundary value problems, J. Math., Tokushima Univ, Volume 17 (1983), pp. 27-88 | MR 719456 | Zbl 0564.65035