Sobre la existencia y el cálculo de ceros de funciones regulares

Sobre la existencia yei cálcuio de ceros de funciones regulares POR J. M. SORIANO ARBIZU Recibido: 18 de noviembre de 1988 Presentado por el académico correspondiente D. Antonio de Castro Brzezicki Abstract For a map / of class two a sufficient condition is obtained to secure the existence of a zero of / in the simplex 5 if a piecewise Hnear aproximation 9 of f has a cero in s. AppHcation: for a smooth map F: Z) Ê C" > C a noniterative algorithm is constructed of obtain the zeros of F using the usual homotopy H in Dx [0, 1] and a piecewise Hnear approximation 6 relative to a triangulation K of Dx [0, 1]. An implemention of the procedure is cited. Resumen Para una apHcación / de clase dos se obtiene una condición suficiente para asegurar la existencia de un cero de / en el simplex s si una aproximación Hneal a trozos 6 de f tiene un cero en s. ApHcación: para una apHcación regular F: D & C^ > C" se construye un algo 1 ritmo no iterativo para calcular sus ceros, utilizando la homotopía usual H en D x [O, 1] y una aproximación Hneal a trozos 6 relativa a una triangulación K ÚQ Dx [O, 1]. Se cita una aplicación del procedimiento. INTRODUCCiON El método seguido consiste en sustituir en un cierto dominio una función / por otra lineal y próxima a ella 9 y utilizar las propiedades del grado topológico [5] que nos permiten obtener una condición suficiente de existencia de ceros de la función problema en un cierto simplex si lo tiene la función aproximante 6, Esta última se caracteriza por tener igual valor numérico que / en los vértices de un simplex de diámetro suficientemente pequeño, y se extiende baricéntricamente a los restantes puntos de éste. En el apartado 2 se construye un algoritmo no iterativo para calcular los ceros de cierta clase de funciones. En primer lugar construimos una homotopía H con la función problema y otra auxiliar cuyos ceros se conocen. Los teoremas 2-1, 2-2, 2-3 tienen por finalidad conocer la naturaleza de H~^ (0). Vemos que son caminos que terminan en un cero de la función problema y empiezan en un cero de la función auxiliar. Las secciones 2-4 y 2-5 están dirigidas a aproximar H, En [3], [8] figuran varias construcciones de homotopías y se utilizan métodos iterativos para calcular cada cero, pero sin demostrar la efectiva existencia del mismo. Nosotros demostramos esta existencia y además la técmca uíiiizada permite un cálculo más rápido. 524 J. M. SORIANO ARBIZU /. Teorema- Sea /: Z) ç R" -• R" una función de clase dos y Q\ i) ^ R'^ -^ R" una aproximación lineal a trozos de / relativa a una triangulación de R'^. Entonces, si Q tiene un cero en el n-símplex 5, / también tiene un cero en s, si se verifica 2xMx(^^<<, (0,0(05)); siendo M una cota superior para la norma de la segunda derivada de / en 5, y ^ el diámetro de s. Demostración- Si O tiene un cero en 5 y cero no es un valor critico, se deduce de la definición de grado topológico que d (0,5,0) = 1. Aplicamos las dos siguientes propiedades de grado topológico: 1) si í/(/;5,O)^O=>/-^(O):?i0; 2) ¿/(.,5,0) es constante sobre {/} EC (I) si sup|/(Z)-0(X)L<r, con r = 4(O,0(55)) [5]. Calculemos una cota para máx | f{X) - 9 (X) \ ^, XSs máx|/(Z)-0(X)L = XSs =máx(\fr(X)-e^(X)\,...,\f„(x)-eAX)\) Para esto: a) Suponemos que máx\f{X)-e(X)\^=\fj(X*)-ej(X*)\; X^s J5r*Gj, 7GI, ...,n. b) Construimos la función /* fk* (X) =A* (X, Y*) =f, (X) + X ((dÁ(Y*)/ dX.) X/?, 1=1 k=l,...,n con XGs, F*Gs conocido; 5 = <y°,..., Y"}; SOBRE LA EXISTENCIA Y EL CALCULO DE CEROS 525 X=l^XiXY'; Y.^i=^' ^¿^0, i=0,...,n; /=0 1=0 h, = X,- Y,*= X ^-x Y¿- Y,*, k= 1, ...,n. i = 0 c) Maximizamos | f}* (X) - 6j (X) | para XG s; máx\J}*iX)-ejiX)\ = ZGJ max JTGJ n (r n {Y*)/dxdxYn-Y;} + que escrito en forma reducida es máx \J}''(X)-ej{X)\=méix MoX^+... + v4„x>l„ + 5| con XBs A,= xei X ((a/;(F*)/5X0X y, 1=1 ?]-Y,'; k = 0,...,«; B=fj(Y*)- j:mj(Y*)/dXdxY,* /=! Calcular este máximo equivale a calcular el máximo de \Ao x Xo + .,. + •j-A„xÀn + B\ con las condiciones Y Xi=\; ki ^ O, / = 0,...,«. í = 0 Así pues, calculamos máximo de I máximo de {AQ, ..., ^„} + B\ I mínimo de [AQ, ..., ^„} + B\\ por tanto, este máximo ocurre para un A, = 1, / = O,..., n. Esto implica que 526 J. M. SORIANO ARBIZU máx\f}*iX)-ej(X)\ = \J}*(Y)-{jiY)\, X€:S porque ej(Y)=fj(Y). Por ser \f* (X)-f(X)\^ ^ Mx ^^ tenemos max I/* (X) - e, iX)\ ^ MX ^\ XSs d) Calculamos por último una cota para max \f(X)-d (X) \ ^, XSs máx|/(Z)-0(Z)L = X& s ^fj(X*)-ej{X*)\ ^ max \fj(X)-f}*(X)\ + A Es + máx \fi*iX)-ei(X)\ < 2xMx^^ xei sup \fiX)-e{X)\^ < max \fiX)-e(X)\^. Así, cuando 2 x M x <^^ < ¿/^ (0, 0 {ds)), aplicando las propiedades 2) y 1) sucesivamente, si hay un cero de Q en 5, también hay un cero de / en s. Observaciones- A) Para comprobar las hipótesis del teorema necesitamos conocer el valor de d^ (O, Q {ds)) y un valor de M; el cálculo es sencillo; así, para calcular d^ (O, 6 {ds)) vemos: 1) Cada n puntos del conjunto {/(F^), ...,/(F'^} (F^ ..., F" pertenecen a un «-simplex de R") determinan un hiperplano de R" que contiene el cierre de un {n - l)-símplex perteneciente a 6 {ds); así obtenemos {n + l)-hiperplanos que contienen 6 {ds). La ecuación de uno de estos hiperplanos tiene la forma: O, 1 1 ... 1 X f{Y'^) ... /(F^) r O A'ixXi + ... + Al„xX^ + AÍ„+i = 0 = ni 2) í/^(0,7r,) = máx(M'.| x |4+il : M'Il,-, l4l x |4+il : M'li SOBRE LA EXISTENCIA Y EL CALCULO DE CEROS 527 œn A' = iA\,...,Al,). 3) Así it (O, e (ds)) = mín {ít (O, TT.),..., ít (0> 'i»+1)}- Para calcular el valor de M; \fiX)-f(Y)-f'(Y)x(X-Y)\^^ <(l/2)x\f"(Y' + tx(X-Y)\^x{X-Y'\i^Mx^\ con XGs, ÍG[0, 1], sup |/"(7'+íx(Jír-^ÓL = ^• sup|/"(7'•+í(A'-nL< < sup Ifc*X Hessiano [fi(Y' + tx (X~ Y)] xh,..., A:* X Hessiano [/„ (7'+í X (X-rÓ] X/!L, con 0^í< 1, |/i|^=|fcL=l. Con la triangulación Ki [8] y eligiendo Y' = F"; hj, kj G [O, 1], j— 1,..., n + 1; y diámetro de malla ^, obtenemos que cada componente de este vector es menor o igual que: '' Y.(SViiYo+p))ldXjdX,; max áx < (dY,(Y'>+p))/dXjdX,>0; AG[0,a Y,(dViiY'+p)/dX„dX„ m,n {dY,{Y^-\-p))ldX^dX,<Q, B) El teorema 1 completa algunos métodos para localizar los ceros de una función vectorial /. Por ejemplo, completa el método dado por Hsu y Zhu en [4] que encuentra ceros de una aproximación lineal a trozos 0 de / relativa a una triangulación K en un cierto dominio de interés. Esto es, encuentra ceros aproximados de / ó puntos que están próximos a sus imágenes por /, pero no necesariamente próximos a un cero. 2. ^/^wiVmo.-Para resolver F *(z) = 0, F *: D ç C—>C\ siendo F* GC°^ (D) con un número finito de ceros, identificamos C" con R^^" y empezamos con el sistema soluble G* (z) = 0, G*: D ^ C^ —• C"; G* es C"(/)). 528 J. M. SORIANO ARBIZU Construimos la homotopía H*:Dx[0,l]—>C"; H* = (H^*,...,H*% H*(z,t) = (l-t)xG*(z) + txF*(z), y resolvemos H* (z, O = 0; H* (z, 0) = G* (z), H* (z, 1) = F* (z). Sean H:D x[0,l]—>R^'", con H = (Re Hi*, Imag Hi*, ..., Imag H*); variable de H (w, t% u — = (Rezi, Imagzi, ..., Imagz„). con F=(ReFi*, Imag/'i*, ..., ImagF„*). G:Z)ÇR2-—>R'^", con G = (ReG?, ImagGf, ..., ImagG*). Así, resolver /f* (z, t) = Q, y /í (w, /) = O, son problemas equivalentes. Suponemos que cero es un valor regular para H. Esto no es substancialmente restrictivo en vista del corolario de Brown [6] del teorema de Sard. Estudiemos la naturaleza de H~^ (0) con la ayuda de los siguientes teorema [6]; con m = 2 X « + 1, /7 = 2 X «, M= D x [O, 1], y N::^ i?^'". 2.1. Teorema.- Si H es una aplicación regular H\ M —> N desde una m-variedad con borde M a una /?-variedad N, donde m > p, e F es un valor regular, para H y para la restricción H\dM, sigue que H~^ {Y) es una {m -/?)-variedad regular con borde. Además, el borde ô (H~* (F)) es la intersección de if"* (F) con 5M, y su dimensión es m-p-\. 2.2. Teorema.- Cualquier 1-variedad regular conexa es difeomorfa a un círculo 5 * ó a algún intervalo real; esto es, es un lazo o un camino. Para calcular los ceros de F* seguimos las componentes conexas de H~^ (0) desde t = 0 hasta t=l. Esto es posible porque H~^ (0) es una unión de caminos y lazos, según se deduce de los dos teoremas anteriores. Sea s el parámetro longitud de las componentes conexas de H~^ (0), {w, t}; H{u {s), t {s)) — 0. Diferenciando, X {SHIdu¡) X U¡ + {dHIdt) X í = O, (=1 SOBRE LA EXISTENCIA Y EL CALCULO DE CEROS 529 sigue [2] ùi = (-1)' X det (Hli (M, 0), i=l,...,n (2) í = (-l)2-+>xdet(/í^2,„_i(M,0). (1) 2.5. Teorema.- Si H* es holomorfa, entonces det (H-^-i ("s 0) ^ 0. De (1) y el teorema 2-3 sigue que los caminos de H~^ (0) son monónotonos en í y no hay lazos, si H es holomorfa. Si elegimos G tal que ninguno de los caminos de H~^ (0) diverja a infinito para 0 ^ / < 1; cada camino que empieza en {X*, 0) con G (Z*) = =0 termina en {X**, 1), F (X**) = 0. Así, resolviendo el problema de valores iniciales (1), (2) para cada una de las soluciones de G (ú) = O, obtenemos las soluciones de F{ü) = 0 y quizás algún camino que diverge a infini- to. [2] da una condición suficiente para que esto no ocurra. 2.4. Aproximación lineal a trozos.- Necesitamos unos dominios de R^^" X [O, 1] cuyos cierres contengan las componentes conexas de H~^ (0), siendo cero un valor regular para H; tal que la intersección del cierre de estos dominios con el hiperplano JGx«+1 = 1 sean entornos de las soluciones de nuestro problema. Para obtenerlos, construimos una triangulación regular K de ií^'"x[0, 1], talque Z* que verifica G(Z*) = 0, esté contenido en el interior de uno de sus 2 x «-símplices y que el diámetro de sus 2 x «-símpli- ces sea menor que el error admisible. Construimos una aproximación lineal a trozos a H relativa a la triangulación K que llamamos 6. 2x/i. 0:i)x[O, 1]—>R H (M, t) para (w, t) E {vértices de K} e(x)= { k Y^XiXHiY) para Z=(t/, Oe<F«,..., Y'\ siendo A/ las coordenadas baricéntricas de X respectode {F^ ..., Y^}. El estudio de 6~^ (0) es el usual en este tipo de algoritmos. 2.5. Construcción del algoritmo.- Seguimos una componente conexa de H~^ (0), recorriendo una componente conexa de 6'^ (0). La malla de la triangulación se construye suficientemente fina para garantizar la aproximación deseable entre los ceros de ambas fimciones; adoptando un diámetro de malla menor que el error deseable para las soluciones. En el primer paso conocemos la existencia de un cero de G en el interior de un 2 x n-símplex 530 J. M. SORIANO ARBIZU específico s, en el que también hay un cero de d si se verifica que el rango de la matriz í ' ' ) es máximo; y A, > O, / = O,..., 2xn para I * |x(Ao,...,A2.y = (l,0,...,0y; \H{Y^) ... H{Y^)I 5=<n..., 7^>. Suponemos ahora conocida la existencia de un cero de 9 en un 2 X «-simplex. Tenemos dos posibilidades para construir un algoritmo: 1) seguir una componente conexa de 6~^ (0) y comprobar si el 2 x «-simplex Sf, que contiene la intersección de esta componente conexa de 6~^ (0) con el hiperplano í= I, contiene un cero de F. 2) En cada 2«-símplex que es intersecado por una componente conexa de 6~^ (0), i*,, comprobamos la existencia de un cero de H, En el caso negativo, volvemos al anterior 2 x «-sim- plex 5j_ 1, y cambiamos la malla de la triangulación. Para realizar esta comprobación aplicamos el teorema 1. En nuestro algoritmo hacemos esta comprobación en un 2 x «-simplex s de R^^"'^\ Esto implica que s está contenido en un hiperplano; de donde sigue que H y 9 aplican i?^""" en i?^"^" como se requiere en el teorema. Hemos programado en Fortran 77 y resuelto en un VAX 11/785 con este algoritmo sistemas del tipo atX^ + a2XY+a3 = 0; bi Y' + b2X+ b^ = 0; üi^biGC, /=1,2,3; X, YGC con el sistema auxiliar: {Z^ - 1 = 0; F^ - 1 = 0}. Y del tipo: aiX' + a2U+a3 = 0; biY'+ b2Z + b3 = 0; CiZ2 + c2F+C3 = 0; diX+d2Z+d3U+d4 = 0; üi, bi. Ci, diGC, i= 1,..., 4; X, Y, Z, Í/EC con el sistema auxiliar: {Jr^-1=0, F^-1 =0, Z^-1 =0, U-l=0}. SOBRE LA EXISTENCIA Y EL CALCULO DE CEROS 531 DEFINICIONES y-símplex abierto s= {Y^, ..., Y^} de R" es el interior de la envoltura convexa de (7+ l)-puntos afínmente independientes, llamados vértices [8]. K triangula a M, con M subconjunto convexo de R", significa: a) K es una colección de «-símplices; b) los subsímplices de todos los n-sím- plices de K forman una partición de M [8]. Aproximación lineal a trozos 9 a f; f: D ^ W —> W relativa a la triangulación A^ de D es la función 6 definida por e(x): f{x) si X pertenece a los vértices de K j Y, hY' si X pertenece al interior de <F^..., F^>; ¿=o con A/, / = O, ..., 7 las coordenadas baricéntricas de X respecto de {Y\...,Y'), [8]. Sea s un abierto de R"; / una función de s en R" que tiene una extensión de clase uno a algún abierto que contenga a I. Sea cero un valor regular de / y que no pertenece a la imagen de la frontera de s por /. Llamamos grado de / respecto de cero en s, d (J, s,Q) a d (/, s, 0) = =^llJf{X), con X perteneciente a/"^ (0), [5]. BIBLIOGRAFÍA [1] BAZARAA, M. S. Y JARVIS, J. (1981): Programación lineal y flujo en redes. {Mé]\co\ Limusa). [2] GARCÍA, C. B. Y ZANGWILL, W. I (1981): Pathways to solutions, fixed points and equilibria. (Englewood Cliffs: Prentice-Hall). [3] GARCIA, C B. Y ZANGWILL, W. I. (I979): Finding all solutions to polynomial system and other equations. Math. Programming Vol. 16, pp. 159-176. [4] Hsu, C. S. Y ZHU, W. H. (1984): A slmplldal mapping method for locating the zeros of a function. Quart. Appl. Math. Vol. 42-1, pp. 41-60. [5] DEIMLING, K. (1984): Non linear Functional Analysis. (Berlin, Heidelberg, New York, Tokio: Springer Verlag). [6] MiLNOR, J. (1965): Topology from the differentiable viewpoint. (Charlottesville: University Press of Virginia). [7] SCARF, H. (1967): The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. Vol. 15, pp. 1328-1343. [8] TODD, J. (1976): The computations of fixed points and applications. hocimt^oXQ^ m Econom. and Math. Systems n° 124 (Berlin, Heidelberg, New York: SpringerVerlag). Dpto. de Análisis Matemático Facultad de Matemáticas 41012 Sevilla View publication statsView publication stats