The approximation of a multiple isolated root is a difficult problem. In fact the root can even be a repulsive root for a fixed point method like the Newton method. However there exists a huge literature on this topic but the answers given are not satisfactory. Numerical methods allowing a local convergence analysis work often under specific hypotheses. This viewpoint favouring numerical analysis forgets the geometry and the structure of the local algebra. Thus appeared so-called symbolic-numeric methods, yet full of lessons, but their precise numerical analysis is still missing. We propose in this paper a method of symbolic-numeric kind, whose numerical treatment is certified. The general idea is to construct a finite sequence of systems, admitting the same root, and called the deflation sequence, so that the multiplicity of the root drops strictly between two successive systems. So the root becomes regular. Then we can extract a regular square we call deflated system. We described already the construction of this deflated sequence when the singular root is known. The originality of this paper consists on one hand to construct a deflation sequence from a point close to the root and on the other hand to give a numerical analysis of this method. Analytic square integrable functions build the functional frame. Using the Bergman kernel, reproducing kernel of this functional frame, we are able to give a -theory à la Smale. Furthermore we present new results on the determinacy of the numerical rank of a matrix and the closeness to zero of the evaluation map. As an important consequence we give an algorithm computing a deflation sequence free of , threshold quantity measuring the numerical approximation, meaning that the entry of this algorithm does not involve the variable .
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 .
Revised:
Accepted:
Published online:
Mot clés : systèmes d’équations, racines singulières, déflation, rang numérique, évaluation
Keywords: systems of equations, singular roots, deflation, numerical rank, evaluation
@article{AHL_2020__3__901_0, author = {Giusti, Marc and Yakoubsohn, Jean-Claude}, title = {Approximation num\'erique de racines isol\'ees multiples de syst\`emes analytiques}, journal = {Annales Henri Lebesgue}, pages = {901--957}, publisher = {\'ENS Rennes}, volume = {3}, year = {2020}, doi = {10.5802/ahl.49}, language = {fr}, url = {http://archive.numdam.org/articles/10.5802/ahl.49/} }
TY - JOUR AU - Giusti, Marc AU - Yakoubsohn, Jean-Claude TI - Approximation numérique de racines isolées multiples de systèmes analytiques JO - Annales Henri Lebesgue PY - 2020 SP - 901 EP - 957 VL - 3 PB - ÉNS Rennes UR - http://archive.numdam.org/articles/10.5802/ahl.49/ DO - 10.5802/ahl.49 LA - fr ID - AHL_2020__3__901_0 ER -
%0 Journal Article %A Giusti, Marc %A Yakoubsohn, Jean-Claude %T Approximation numérique de racines isolées multiples de systèmes analytiques %J Annales Henri Lebesgue %D 2020 %P 901-957 %V 3 %I ÉNS Rennes %U http://archive.numdam.org/articles/10.5802/ahl.49/ %R 10.5802/ahl.49 %G fr %F AHL_2020__3__901_0
Giusti, Marc; Yakoubsohn, Jean-Claude. Approximation numérique de racines isolées multiples de systèmes analytiques. Annales Henri Lebesgue, Volume 3 (2020), pp. 901-957. doi : 10.5802/ahl.49. http://archive.numdam.org/articles/10.5802/ahl.49/
[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, 185, Springer, 2005 | MR | Zbl
[Ded06] Points fixes, zéros et la méthode de Newton, Mathématiques & Applications, 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 (Manuel, Kauers, ed.), ACM Press (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, 132, Springer, 1995 | Zbl
[Kra13] Geometric analysis of the Bergman kernel and metric, Graduate Texts in Mathematics, 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, ACM Press (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
Cited by Sources: