Metadata
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] 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 | Zbl
[BCSS97] Complexity and Real Computation, Springer, 1997 (foreword by Richard M. Karp) | Zbl
[CLO05] Using algebraic geometry, Graduate Texts in Mathematics, Volume 185, Springer, 2005 | MR | Zbl
[Ded06] Points fixes, zéros et la méthode de Newton, Mathématiques & Applications, Volume 54, Springer, 2006 | Zbl
[DK80a] Newton’s method at singular points. I., SIAM J. Numer. Anal., Volume 17 (1980) no. 1, pp. 66-70 | DOI | MR | Zbl
[DK80b] Newton’s method at singular points. II, SIAM J. Numer. Anal., Volume 17 (1980) no. 3, pp. 465-471 | DOI | MR | Zbl
[DKK83] Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal., Volume 20 (1983) no. 2, pp. 296-314 | DOI | MR | Zbl
[DLZ11] Multiple zeros of nonlinear systems, Math. Comput., Volume 80 (2011) no. 276, pp. 2143-2168 | DOI | MR | Zbl
[DS01] On simple double zeros and badly conditioned zeros of analytic functions of n variables, Math. Comput., Volume 70 (2001) no. 233, pp. 319-327 | DOI | MR | Zbl
[DZ05] Computing the multiplicity structure in solving polynomial systems, Proceedings of the 2005 international symposium on Symbolic and algebraic computation (2005), pp. 116-123 | Zbl
[EI95] Relative perturbation techniques for singular value problems, SIAM J. Numer. Anal., Volume 32 (1995) no. 6, pp. 1972-1988 | DOI | MR | Zbl
[Ems78] Géométrie des points épais, Bull. Soc. Math. Fr., Volume 106 (1978), pp. 399-416 | DOI | Numdam | MR | Zbl
[EY36] The approximation of one matrix by another of lower rank, Psychometrika, Volume 1 (1936), pp. 211-218 | DOI | Zbl
[FH05] UTV expansion pack : Special-purpose rank-revealing algorithms, Numer. Algorithms, Volume 40 (2005) no. 1, pp. 47-66 | DOI | MR | Zbl
[GLSY05] On location and approximation of clusters of zeros of analytic functions, Found. Comput. Math., Volume 5 (2005) no. 3, pp. 257-311 | DOI | MR
[GLSY07] On location and approximation of clusters of zeros : Case of embedding dimension one, Found. Comput. Math., Volume 7 (2007) no. 1, pp. 1-58 | DOI | MR | Zbl
[GO81] Newton’s method for singular problems when the dimension of the null space is , SIAM J. Numer. Anal., Volume 18 (1981) no. 1, pp. 145-149 | DOI | MR | Zbl
[GO83] Analysis of Newton’s method at irregular singularities, SIAM J. Numer. Anal., Volume 20 (1983) no. 4, pp. 747-773 | DOI | MR | Zbl
[Gri85] n solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev., Volume 27 (1985) no. 4, pp. 537-563 | DOI | MR | Zbl
[GY14] 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 | DOI
[HMS17] On deflation and multiplicity structure, J. Symb. Comput., Volume 83 (2017), pp. 228-253 | DOI | MR | Zbl
[Kat95] Perturbation theory for linear operators, Classics in Mathematics, Volume 132, Springer, 1995 | Zbl
[Kra13] Geometric analysis of the Bergman kernel and metric, Graduate Texts in Mathematics, Volume 268, Springer, 2013 | MR | Zbl
[KS83] A new acceleration method for Newton’s method at singular points, SIAM J. Numer. Anal., Volume 20 (1983) no. 5, pp. 1001-1009 | DOI | MR | Zbl
[Lec02] Quadratic Newton iteration for systems with multiplicity, Found. Comput. Math., Volume 2 (2002) no. 3, pp. 247-293 | DOI | MR | Zbl
[LVZ06] Newton’s method with deflation for isolated singularities of polynomial systems, Theor. Comput. Sci., Volume 359 (2006) no. 1-3, pp. 111-122 | DOI | MR | Zbl
[LZ12a] Computing isolated singular solutions of polynomial systems : case of breadth one, SIAM J. Numer. Anal., Volume 50 (2012) no. 1, pp. 354-372 | MR | Zbl
[LZ12b] 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 | Zbl
[LZ14] Verified error bounds for isolated singular solutions of polynomial systems, SIAM J. Numer. Anal., Volume 52 (2014) no. 4, pp. 1623-1640 | MR | Zbl
[Mar11] Low rank approximation : algorithms, implementation, applications, Communications and Control Engineering Series, Springer, 2011
[MG03] Strong rank revealing LU factorizations, Linear Algebra Appl., Volume 367 (2003) no. 1, pp. 1-16 | DOI | MR | Zbl
[Mir60] Symmetric gauge functions and unitarily invariant norms, Q. J. Math., Oxf. II. Ser., Volume 11 (1960), pp. 50-59 | DOI | MR | Zbl
[MM11] 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
[Mou97] Isolated points, duality and residues, J. Pure Appl. Algebra, Volume 117/118 (1997), pp. 469-493 | DOI | MR | Zbl
[Oji87] 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 | DOI | MR | Zbl
[OWM83] Deflation algorithm for the multiple roots of a system of nonlinear equations, J. Math. Anal. Appl., Volume 96 (1983) no. 2, pp. 463-479 | DOI | MR | Zbl
[Pan00] 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 | Zbl
[Ral66] Convergence of the Newton process to multiple solutions, Numer. Math., Volume 9 (1966) no. 1, pp. 23-37 | DOI | MR | Zbl
[Red78] On Newton’s method for singular problems, SIAM J. Numer. Anal., Volume 15 (1978) no. 5, pp. 993-996 | DOI | MR | Zbl
[Red79] Newton’s method and high order singularities, Comput. Math. Appl., Volume 5 (1979) no. 2, pp. 79-86 | DOI | MR | Zbl
[Rud08] Function theory in the unit ball of , Classics in Mathematics, Springer, 2008 (Reprint of the 1980 original) | Zbl
[Sch70] Ueber unendliche viele Algorithmen zur Auflösung der Gleichungen, Math. Ann., Volume 2 (1870), pp. 317-365 | DOI
[Sha67] 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 | DOI | MR
[SS90] Matrix Perturbation Theory, Computer Science and Scientific Computing, Academic press, 1990 | Zbl
[SY05] 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 | DOI | MR | Zbl
[Wey12] 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 | DOI | MR | Zbl
[XL08] 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 | Zbl
[Yak90] On Newton’s rule and Sylvester’s theorems, J. Pure Appl. Algebra, Volume 65 (1990) no. 3, pp. 293-309 | DOI | MR | Zbl
[Yam83] Newton’s method for singular problems and its application to boundary value problems, J. Math., Tokushima Univ, Volume 17 (1983), pp. 27-88 | MR | Zbl