Estudio del error en la interpolación polinómica

FACULTAD DE MATEM´ ATICAS DEPARTAMENTO DE ECUACIONES DIFERENCIALES Y AN´ ALISIS NUM´ ERICO TRABAJO FIN DE GRADO EN MATEM´ ATICAS ESTUDIO DEL ERROR EN LA INTERPOLACI´ ON POLIN´ OMICA MARTA LOBATO L´ OPEZ 19 de Junio de 2018 Dirigido por: D. Manuel Delgado Delgado Abstract This dissertation provides a study of the error of Lagrange’s Polynomial Interpolation. It consists of seven chapters that include some topics of the Numerical Analysis. Firstly, we will have introduced a series of basic tools that are also very useful in other fields of Numerical Analysis and that we will use throughout the project. Secondly, we will recall the main results related to the approximation of a function of a real variable by an algebraic polynomial. After that, we will study the error of polynomial interpolation when the nodes are equidistant. In addition, we will analyse the problem of minimizing the oscillations produced in the extremes in the Runge phenomenon and we will study the existence of the polynomial of best approximation. From here, the Weierstrass Theorem is deduced and the approximation of a class C1function is studied by polynomials that interpolate it to the zeros of the Chebyshev polynomials. Finally, we will conclude the dissertation by considering which choice of nodes uniformly approximate regular functions. 1 2 Resumen En este trabajo se lleva a cabo un estudio del error de la interpolaci´on polin´omica de Lagrange. Consta de siete cap´ıtulos que recoge algunos temas del C´alculo Num´erico. En los cap´ıtulos 1 y 2, hemos introducido una serie de herramientas b´asicas que tambi´en son muy ´utiles en otros campos del an´alisis num´erico y que utilizaremos a lo largo del trabajo. En el cap´ıtulo 3, recordamos los principales resultados relativos a la aproximaci´on de una funci´on de una variable real por un polinomio algebraico. Comenzamos el cap´ıtulo introduciendo el concepto de la interpolaci´on polin´omica de Lagrange, citando un resultado de existencia y unicidad del polinomio de interpolaci´on y una expresi´on del error de interpolaci´on, ya estudiada en el grado. En el cap´ıtulo 4, estudiaremos el error de la interpolaci´on polin´omica cuando los nodos son equidistantes y veremos lo que puede ocurrir en los extremos del intervalo cuando estudiamos el fen´omeno de Runge. En el cap´ıtulo 5, analizaremos el problema de minimizar las oscilaciones producidas en los extremos en el fen´omeno de Runge mediante otra elecci´on de los nodos, en este caso, los ceros de los polinomios de Chebyshev, dando una mejor estimaci´on del error. En el cap´ıtulo 6, estudiaremos la existencia del polinomio de mejor aproximaci´on, introduciendo el concepto de Constante de Lebesgue y probando la acotaci´on del grado de aproximaci´on (m´ınima distancia entre la funci´on y el polinomio de mejor 3 aproximaci´on de grado n) por el m´odulo de continuidad de la funci´on en el intervalo b−a n. De aqu´ı se deduce el Teorema de Weierstrass y se estudia la aproximaci´on de una funci´on de clase C1por polinomios que la interpolan a los ceros del los polinomios de Chebyshev. Finalmente concluiremos el trabajo viendo qu´e elecci´on de los nodos aproximan uniformemente a funciones regulares. 4 ´ Indice general 1 Introducci´on 7 1.1 Generalidades............................... 8 2 Resultados previos 11 2.1 Teor´ıadeseries .............................. 11 2.2 Resultados de variable compleja . . . . . . . . . . . . . . . . . . . . . 13 2.3 Otrosresultados.............................. 13 3 Interpolaci´on polin´omica 15 3.1 F´ormula de interpolaci´on de Lagrange . . . . . . . . . . . . . . . . . . 16 3.2 Estimaci´ondelerror ........................... 17 4 Interpolaci´on polin´omica para puntos de abscisas equidistantes 19 4.1 Estudio de Qn i=0 |(x−xi)|en el caso de abscisas equidistantes . . . . 19 4.2 Fen´omenodeRunge ........................... 26 4.2.1 Ejemplo .............................. 26 4.2.2 Explicaci´on del Fen´omeno de Runge . . . . . . . . . . . . . . . 29 5 Polinomios de Chebyshev 31 5.1 Mejores estimaciones de errores reales: Polinomios de Chebyshev . . . 31 6 Aproximaci´on de funciones continuas 39 6.1 Existencia del polinomio de mejor aproximaci´on . . . . . . . . . . . . 39 6.2 Constante de Lebesgue . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.3 M´odulo de continuidad . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.4 Casosparticulares............................. 50 5 ´ Indice general 6.5 Ejemplo considerando los ceros del polinomio de Chebyshev . . . . . 51 7 Anexos 55 7.1 C´odigoMatlab .............................. 55 7.1.1 Fen´omeno de Runge . . . . . . . . . . . . . . . . . . . . . . . 55 7.1.2 Interpolaciones de Polinomios de Chebyshev . . . . . . . . . . 56 Bibliograf´ıa 57 6 Cap´ıtulo 1 Introducci´on Una cuesti´on que encontramos con frecuencia en las ciencias experimentales y en ingenier´ıa es tratar de construir una funci´on denominada “funci´on interpolante” de la cual se conoce una serie de valores en ciertos puntos denominados “datos de interpolaci´on”. En ocasiones, este problema comprende tambi´en otros datos, especialmente los valores de las derivadas de la funci´on en ciertos puntos. Estos datos pueden ser obtenidos, por ejemplo, a partir de observaciones realizadas en un determinado experimento. El objetivo ser´a determinar una funci´on cuyos valores en los puntos considerados coincidan con los datos y que adem´as sea f´acil de construir y manipular. Los polinomios se usan con frecuencia como funciones interpolantes porque son f´aciles de evaluar y por el hecho fundamental de que dados n+1 puntos de abscisa distinta, (x0, y0),(x1, y1),...,(xn, yn), existe exactamente un polinomio Pn(x) de grado no superior a n, que pasa por dichos puntos, es decir, tal que Pn(xi) = yi, i = 0,1,2. . . , n. En la interpolaci´on lineal, la funci´on se sustituye por la recta que pasa por dos puntos. Tres datos se interpolan con un polinomio de segundo grado, gr´aficamente una par´abola que pasa por esos tres puntos. Una vez que se ha determinado la funci´on interpolante, en nuestro caso se tratar´ıa del polinomio interpolante, uno puede estimar el valor que el experimento de partida habr´ıa tomado en puntos pr´oximos a los datos de interpolaci´on evaluando la funci´on 7 14 Cap´ıtulo 3 Interpolaci´on polin´omica Comenzamos este cap´ıtulo introduciendo el concepto de la interpolaci´on polin´omica de Lagrange y obteniendo un resultado de existencia y unicidad del polinomio de interpolaci´on. Presentaremos un algoritmo de construcci´on del polinomio de interpolaci´on y una expresi´on del error de interpolaci´on. A la vista de la expresi´on del error obtenida, analizamos el problema de minimizar dicho error, usando para ellos la sucesi´on de polinomios de Chebyshev que veremos en el cap´ıtulo 5. Definici´on 3.1 Sea f(x) una funci´on continua definida f: [a, b]→Ry consideremos unos valores conocidos de esta en n+ 1 puntos distintos xi, i = 0,1, . . . , n con xi∈ [a, b]. La interpolaci´on polin´omica de Lagrange consiste en obtener un polinomio Pn(x)de grado no superior a ntal que se cumpla que en los nodos, las im´agenes de f(x) y Pn(x)coincidan, es decir, Pn(xi) = f(xi), i = 0, . . . , n. Al polinomio Pn(x)se le conoce como polinomio interpolador de Lagrange y forma parte del conjunto de los polinomio de grado menor o igual que ny, por tanto, Pn(x) ser´a de la forma: Pn(x) = anxn+an+1xn+1 +. . . +a1x+a0. 15 Cap´ıtulo 3. Interpolaci´on polin´omica y, para determinarla, habr´a que hallar los n+ 1 coeficientes reales a0, a1, . . . , an. Nota 3.2 Diremos que Pn(x) tiene grado nen el caso que ansea no nulo. Supongamos que aproximamos f(x) por Pn(x) en dichos nodos. Con Pn(x) estimamos el valor de f(x), cometiendo un error cuya cota es interesante determinar. En el siguiente resultado recordaremos la existencia y unicidad del polinomio de interpolaci´on Pn(x). 3.1 F´ormula de interpolaci´on de Lagrange Teorema 3.3 (F´ormula de interpolaci´on de Lagrange) Sean f :[a,b] →R, {x0, x1, . . . , xn}n+ 1 puntos distintos del intervalo [a,b]. Entonces, existe un ´unico polinomio Pn(x)de grado menor o igual que n, que verifica: Pn(xi) = f(xi), i = 0, . . . , n. (3.1) A este polinomio se le denomina polinomio de interpolaci´on de fen los nodos x0, x1, . . . , xny viene dado por: Pn(x) = n X i=0 f(xi)Li(x),(3.2) donde Li(x) = n Y j=0,j6=i x−xj xi−xj ,para cada i ∈ {0,1, . . . , n}. Nota 3.4 : Ver [4] •La expresi´on (3.2) se conoce como f´ormula de Lagrange del polinomio de interpolaci´on. El Teorema anterior proporciona un m´etodo constructivo para obtener el polinomio de interpolaci´on Pn(x) mediante la f´ormula (3.2). •Podr´ıamos omitir el c´alculo de Lj(x) si alg´un dato es f(xj) = 0. 16 Cap´ıtulo 3. Interpolaci´on polin´omica •Los polinomios Lk(x) s´olo dependen de los nodos de interpolaci´on {x0, x1, . . . , xn}. De modo que, una vez calculado cada Lk(x) se construyen los polinomios de interpolaci´on poniendo los f(xk) como coeficientes de una combinaci´on lineal, lo cual es una ventaja si queremos resolver varios problemas de interpolaci´on como los mismos nodos xk. En este sentido, {L0(x), L1(x), . . . , Ln(x)}es la base del espacio vectorial de los polinomios de interpolaci´on asociados a los nodos {x0, x1, . . . , xn}. •La f´ormula de Lagrange (3.2) tiene el inconveniente de que hay que realizar numerosos c´alculos y al a˜nadir un dato m´as de interpolaci´on, hay que volver a calcular todos los polinomios Lk(x). 3.2 Estimaci´on del error En este apartado analizaremos el error en la interpolaci´on polin´omica de una funci´on f(x). El teorema que introduciremos a continuaci´on permite estudiar el error de la interpolaci´on por polinomios cuando la funci´on dada posee derivadas de hasta orden (n+ 1). Mediante este resultado se puede obtener una estimaci´on del error que estamos cometiendo al aproximar f(x) por Pn(x). Teorema 3.5 (Error de la interpolaci´on polin´omica de Lagrange) . Sea f : [a,b] →R, con f(x) continua en [a,b] yn+1 veces derivable en dicho intervalo. Consideremos x0, x1, x2, . . . , xn∈[a,b] nodos distintos dos a dos. Sea Pn(x)el polinomio de interpolaci´on de grado ≤n tal que Pn(xi) = f(xi), x ∈[a, b],∀i= 0, . . . , n. Entonces, existe ξ∈[a,b] tal que: |Rn(f;x)|=|f(x)−Pn(x)| ≤ |fn+1(ξ)| (n+ 1)! |(x−x0)(x−x1)···(x−xn)|.(3.3) Observamos que aparecen dos factores en la cota, fn+1(ξ) y Qn i=0 |(x−xi)|. 17 Cap´ıtulo 3. Interpolaci´on polin´omica Nota 3.6 El teorema anterior resulta ser una extensi´on del Teorema del Valor Medio para m´as de un punto. En efecto, para n= 0 y S=x0, la expresi´on se reduce a lo siguiente: |f(x)−f(x0)|≤|f0(ξx)|·(x−x0). A continuaci´on, introduciremos un corolario en el cual acotaremos el t´ermino f(n+1)(ξ). Corolario 3.7 Sea f(x) ∈A(R)donde Res una regi´on que contiene [a,b]. Sea C una curva cerrada que contiene a [a,b] en su interior y sea L(C) la longitud de la curva C, MC=m´axz∈C|f(z)|es el valor m´aximo que puede tomar dicha curva y δ es la m´ınima distancia de C a [a,b]. Luego: |Rn(f;x)|=|f(x)−Pn(x)| ≤ n!L(C)MC 2πδn+2 |x−x0||x−x1|···|x−xn|.(3.4) Demostraci´on: Tomando valor absoluto en la proposici´on (2.3) obtenemos la siguiente expresi´on: |f(n)(z0)| ≤ n! 2πZC |f(z)| |z−z0|n+1 |dz| ≤ n! 2π m´axz∈C|f(z)| m´ın |z−z0|n+1 L(C), donde L(C) es la longitud de la curva C, m´axz∈C|f(z)|es el valor m´aximo que puede tomar dicha curva y m´ın |z−z0|n+1 el valor m´ınimo de la distancia entre los puntos de la curva y z0.  En los siguientes cap´ıtulos, estudiaremos diversas cotas de Qn i=0 |(x−xi)|en funci´on de la elecci´on de los puntos. 18 Cap´ıtulo 4 Interpolaci´on polin´omica para puntos de abscisas equidistantes 4.1 Estudio de Qn i=0 |(x−xi)|en el caso de abscisas equidistantes En este cap´ıtulo estudiaremos el error de la interpolaci´on polin´omica cuando los nodos son puntos equidistantes. Veremos c´omo el c´alculo del polinomio de interpolaci´on se simplifica cuando los nodos est´an igualmente espaciados. Proposici´on 4.1 Dados {x0, x1, . . . , xn}(n+ 1) puntos igualmente espaciados en el intervalo [a,b] con x0=a, xn=b, existe C >0tal que: m´ax x∈[a,b]| n Y i=0 (x−xi)| ≤ C e−n √n Ln(n)(b−a)n+1,∀n > 1.(4.1) Donde Qn i=0(x−xi)es el t´ermino de la f´ormula del error de interpolaci´on en el punto x. Demostraci´on: Dividiremos la demostraci´on en varias etapas: Primera etapa: Esta etapa va a consistir en reducir el problema al intervalo [0,n]. 19 Cap´ıtulo 4. Interpolaci´on polin´omica para puntos de abscisas equidistantes Sea: x=a+sb−a n, s ∈[a, b]. xi=a+ib−a n, i = 0,1, . . . , n.              Luego (x−xi) = b−a n(s−i). Por tanto, n Y i=0 (x−xi) = (s−0) b−a n·(s−1) b−a n·. . . ·(s−n)b−a n= =b−a nn+1 |s·(s−1) ·. . . ·(s−n)|,con s ∈[0, n]. Consideremos la funci´on f(s) = |s(s−1) ·. . . ·(s−n)|definida para s∈[0, n] y que alcanza su m´aximo en un punto sn. Vamos a estudiar la posici´on de sny el valor del m´aximo de f, dando paso a la siguiente etapa. Segunda etapa: Aqu´ı vemos la simetr´ıa de la funci´on f(s) = |s(s−1) ·. . . ·(s−n)|.Tomamos s0= s−n 2y sustituyendo obtenemos: s0+n 2·s0+n 2−1·. . . ·s0+n 2−n+ 1·s0+n 2−n que simplificando quedar´ıa: s0+n 2·s0+n 2−1·. . . ·s0−n 2+ 1·s0−n 2. De aqu´ı concluimos que s0tiene exponente par, ya que el producto entre el primer t´ermino y el ´ultimo queda un t´ermino de segundo grado, de igual forma pasar´ıa con el segundo t´ermino y el pen´ultimo, y as´ı sucesivamente, dando lugar al producto de 20 Cap´ıtulo 4. Interpolaci´on polin´omica para puntos de abscisas equidistantes polinomios de exponente par, lo que implica que la funci´on es sim´etrica respecto de s = n 2. Por tanto, el m´aximo se da en la primera mitad del intervalo [0, n], es decir, en h0,n 2i. Tercera etapa: En esta etapa, veremos c´omo la funci´on fpuede describirse a partir de sus valores en [0,1], alcanzando su m´aximo en alg´un valor snque pertenece al intervalo 0,1 2. Veamos ahora que f(s+`) es una funci´on decreciente de `con `= 0,...,hn 2i−1. f(s+`) = |(s+`)(s+`−1)(s+`−2) ·. . . ·(s+`−n+ 1)(s+`−n)|. f(s+`−1) = |(s+`−1)(s+`−2) ·. . . ·(s+`−n+ 1)(s+`−n)(s+`−n−1)|. Por tanto, f(s+`) = f(s+`−1)·s+` n+ 1 −s−`,definida para s ∈[0,1) y `∈ {1,2,··· ,hn 2i−1}. La f´ormula da, en forma recursiva, los valores de fa partir de los valores en [0,1]. Luego, f(s+`) f(s+`−1) =s+` 1 + n−s−`<1 y por tanto f(s+`)< f(s+`−1). Ahora la analizaremos en el intervalo [0,1] y cogeremos la primera mitad para facilitar, es decir, cogeremos s∈0,1 2. 21 Cap´ıtulo 4. Interpolaci´on polin´omica para puntos de abscisas equidistantes f1 2+s=1 2+ss−1 2s−3 2·. . . ·s+1 2−n+ 1·s+1 2−n= =1 2+s·1 2−s·3 2−s·. . . ·n−s−1 2 f1 2−s=1 2−ss−1 2s−3 2s−5 2·. . . ·1 2−s−n= =1 2−s·1 2+s·3 2+s·. . . ·n+s−1 2                                              =⇒ =⇒f1 2+s< f 1 2−spara s ∈0,1 2. Por lo tanto, falcanza su m´aximo en un punto sn∈0,1 2. Cuarta etapa: Tomamos logaritmos para obtener la derivada m´as f´acilmente: Ln(f(s)) = Ln(s) + Ln(1 −s) + . . . +Ln(n−s). Por tanto, para s∈0,1 2 f0(s) f(s)=1 s−1 1−s+. . . +1 n−s. En el m´aximo, f0(sn) = 0 : 1 sn−1 1−sn +. . . +1 n−sn= 0. De donde obtenemos 1 sn =1 1−sn +. . . +1 n−sn = n X k=1 1 k−sn .(4.2) 22 Cap´ıtulo 4. Interpolaci´on polin´omica para puntos de abscisas equidistantes Entonces, 1 sn≥ n X k=1 1 k que por (2.1) se comporta como Ln(n) cuando n→ ∞. Por tanto, 1 sn≥ n X k=1 1 k∼Ln(n) → ∞, si n → ∞. Luego debe ser, l´ım n→∞ sn= 0. Ahora veamos que 1 sn− n X k=1 1 k=sn n X k=1 1 k(k−sn).(4.3) En efecto, n X k=1 1 k(k−sn)= n X k=1    1 sn k−sn− 1 sn k  =1 sn n X k=1 1 k−sn−1 k=⇒ =⇒sn n X k=1 1 k(k−sn)= n X k=1 1 k−sn− n X k=1 1 k=1 sn− n X k=1 1 k,por (4.3). Por lo que obtenemos la igualdad (4.3). Como sn∈0,1 2entonces, sn<1 2−→ k−sn> k −1 2−→ 1 k−sn <1 k−1 2 . Y al ser una serie geom´etrica de exponente dos, converge y est´a acotada por una constante que llamaremos C. n X k=1 1 k(k−sn)≤ n X k=1 1 k(k−1 2)≤C, sigue que 0<1 sn− n X k=1 1 k≤C·sn. 23 Cap´ıtulo 4. Interpolaci´on polin´omica para puntos de abscisas equidistantes Aplicando (3.3) en la primera desigualdad y (4.1) en la segunda:  1 1 + 25x2Pn(x)≤|fn+1(ξ)| (n+ 1)! ·m´ax  n Y i=0 (x−xi)≤|fn+1(ξ)| (n+ 1)! C e−n √n Ln(n)(2)n+1 ≤ ≤n!·5n (n+ 1)! ·2n+1 √n Ln(n)en≤C10n (n+ 1)√n Ln(n)en−→ ∞. Lo que permite que en los extremos la cota del error tienda a infinito, como anteriormente pudimos observar en las gr´aficas. Definici´on 4.5 (Spline). Un spline es una curva diferenciable definida en porciones mediante polinomios. En los problemas de interpolaci´on, se utiliza a menudo la interpolaci´on mediante splines porque da lugar a resultados similares requiriendo solamente el uso de polinomios de bajo grado, evitando as´ı las oscilaciones, indeseables en la mayor´ıa de las aplicaciones, encontradas al interpolar mediante polinomios de grado elevado. 30 Cap´ıtulo 5 Polinomios de Chebyshev En esta secci´on veremos c´omo podemos solucionar el problema presentado por el fen´omeno de Runge. Para minimizar las oscilaciones producidas en los extremos usaremos los polinomios de Chebyshev en lugar de nodos de abscisa equidistante, como vimos en el cap´ıtulo anterior. En este caso se garantiza que el error m´aximo disminuye al crecer el orden polin´omico. Estos polinomios reciben este nombre en honor al matem´atico ruso Pafnuti Chebyshev. Se trata de una familia de polinomios ortogonales que est´an relacionados con la f´ormula de De Moivre y son definidos de forma recursiva con facilidad. Normalmente se hace una distinci´on entre polinomios de Chebyshev de primer tipo que son denotados Tny polinomios de Chebyshev de segundo tipo, denotados Un. Los polinomios de Chebyshev son importantes en la teor´ıa de la aproximaci´on puesto que las ra´ıces de los polinomios de Chebyshev de primer tipo Tn, tambi´en llamadas nodos de Chebyshev, son usadas como nodos en interpolaci´on polin´omica. 5.1 Mejores estimaciones de errores reales: Polinomios de Chebyshev La estimaci´on del error m´ax a≤x≤b|fn+1(x)|· |x−x0|·|x−x1|···|x−xn| (n+ 1)! (5.1) 31 Cap´ıtulo 5. Polinomios de Chebyshev para el polinomio de interpolaci´on esta dividida en dos partes. La primera parte, m´axa≤x≤b|fn+1(x)|que depende de la funci´on interpolada pero no depende de la forma en la cual la interpolaci´on se realiza. La segunda parte, |x−x0|·|x−x1|···|x−xn| (n+ 1)! es independiente de la funci´on pero depende de los puntos . La estimaci´on (5.1) se ha obtenido de sustituir |fn+1(ξ)|por m´axa≤x≤b|fn+1(x)|. En muchos casos, el error predicho por (5.1) ser´a mucho mejor que el error (3.4). Consideremos la cantidad m´axa≤x≤b|(x−x0)·(x−x1)···(x−xn)|que depende de los puntos x0, x1, . . . , xn. Esto nos lleva a plantear la siguiente pregunta: ¿C´omo podemos seleccionar los puntos x0, x1, . . . , xnen [a,b] de forma que el m´aximo sea lo m´as peque˜no posible?. La respuesta al problema viene dada por los ceros del polinomio de Chebyshev. Si tomamos x=cos θ en la f´ormula (2.4) con θ∈[0, π], entonces sen θ = √1−x2≥0. Luego, (cos nθ +isin nθ) = (x+i√1−x2)n. Si desarrollamos esta expresi´on por el teorema del Binomio, cogemos la parte real del resultado de la ecuaci´on y sustituimos el valor de x=cos θ, obtenemos: cos(n(arc cos x)) = cos(nθ) = n 0xn(x2−1)0+n 2xn−2(x2−1)+n 4xn−4(x2−1)2+. . . As´ı, cos(nθ) es un cierto polinomio de grado nen cos θ Definici´on 5.1 Se define el polinomio de Chebyshev de grado n como: Tn(x) = cos(narc cos x) = xn+n 2xn−2(x2−1) + . . . , para n= 0,1, . . . (5.2) Los polinomios definidos por (5.2) son los que se denominan Polinomios de Chebyshev por antonomasia. Es f´acil calcular los primeros los polinomios de Chebyshev expl´ıcitamente y para ellos usaremos (5.2). De esta forma obtenemos: 32 Cap´ıtulo 5. Polinomios de Chebyshev T0(x) = cos(0) = 1 T1(x) = cos(arc cos x) = x T2(x) = cos(2 arc cos x) = 2 2x2−2(x2−1) + x2= 2x2−1 T3(x) = 4x3−3x T4(x)=8x4−8x2+ 1 T5(x) = 16x5−20x3+ 5x T6(x) = 32x6−48x4+ 18x2−1 A continuaci´on, incluiremos algunas gr´aficas que pertenecen a los anteriores polinomios: Figura 5.1: Funci´on T0(x) Figura 5.2: Funci´on T1(x) 33 Cap´ıtulo 5. Polinomios de Chebyshev Figura 5.3: Funci´on T2(x) Figura 5.4: Funci´on T3(x) Teorema 5.2 Los polinomios de Chebyshev verifican la siguiente relaci´on de recurrencia. Tn+1(x)=2xTn(x)−Tn−1(x)n= 1,2, ... (5.3) Demostraci´on: Usando identidades trigonom´etricas adecuadas, obtenemos: cos(n+ 1)θ= cos nθ cos θ−sin nθ sin θ cos(n−1)θ= cos nθ cos θ+ sin nθ sin θ Sum´andolas obtenemos: cos(n+ 1)θ+ cos(n−1)θ= 2 cos nθ cos θ y despejando, cos(n+ 1)θ= 2 cos nθ cos θ−cos(n−1)θ 34 Cap´ıtulo 5. Polinomios de Chebyshev A continuaci´on, tomamos:    x= cos θ cos nθ =Tn(x) Finalmente, sustituimos y se obtiene lo deseado: Tn+1(x) = cos((n+ 1) ·arc cos x) = 2 ·(narc cos x)·cos(arc cos x)− cos((n−1) ·arc cos x) = 2xTn(x)−Tn−1(x).  Corolario 5.3 Se verifica: Tn(x) = 2n−1xn+ t´erminos de menor grado. (5.4) Teorema 5.4 Tn(x)tiene ceros simples, es decir, puntos que anulan a la funci´on pero no a su derivada,en los npuntos. xk= cos 2k−1 2nπpara k= 1,2, . . . , n. (5.5) En el intervalo cerrado x ∈[−1,1],Tn(x)tiene valores extremos en los n+1 puntos, x0 k= cos 2k 2nπpara k= 0,1, . . . , n donde toma los valores alternativos (−1)k. Demostraci´on: Por definici´on de los polinomios de Chebyshev y aplicando (5.4) obtenemos: Tn(xk) = cos(narc cos xk) = cos narc cos cos 2k−1 2nπ= = cos 2k−1 2π= 0, k = 1,2, . . . , n. 35 Cap´ıtulo 5. Polinomios de Chebyshev Estas son las nra´ıces que puede tener el polinomio Tn(x) de grado n. Sea su derivada, T0 n(xk) = n p1−x2 k sin(narc cos xk) y aplicando (5.5) tenemos, T0 n(xk) = n p1−x2 k sin narc cos cos 2k−1 2nπ= =n p1−x2 k sin 2k−1 2π6= 0 y los ceros deben ser simples. Adem´as, T0 n(x0 k) = n s1−cos2kπ nsin(kπ)=0,para k= 1,2, . . . , n −1. Tomamos ahora: Tn(x0 k) = cos narc cos cos 2kπ 2n= cos(kπ) = (−1)k. Esto es v´alido para k= 0,1, . . . , n. Pero para x∈[−1,1], Tn(x) = cos(narc cos x) y por lo tanto, |Tn(x)| ≤ 1. Esto nos muestra que los puntos x0 kson puntos extremos en −1≤x≤1.  Definici´on 5.5 Denotamos: f Tn(x) = 1 2n−1Tn(x). 36 Cap´ıtulo 5. Polinomios de Chebyshev Notaremos que f Tn(x) = xn+t´erminos de menor grado. Teorema 5.6 (Chebyshev). Dado Pnque designa la clase de todos los polinomios de grado ncon coeficiente principal 1. Entonces, para cualquier p∈Pntenemos, m´ax −1≤x≤1|f Tn(x)| ≤ m´ax −1≤x≤1|p(x)|. Demostraci´on: En −1≤x≤1,|f Tn|toma su valor m´aximo, 1 2n−1, n + 1 veces en los puntos x0 k= cos kπ n, k = 0,1, . . . , n. Supongamos que hay un p∈Pn,con m´ax−1≤x≤1|p(x)|<1 2n−1. En forma de diferencia tenemos Q(x) = f Tn(x)−p(x).Claramente, Q(x)∈Pn−1 como m´aximo. Sea ahora, Q(x0 k) = f Tn(x0 k)−p(x0 k) = (−1)k 2n−1−p(x0 k), k = 0,1, . . . , n. Estas cantidades son alternativas tanto positivas como negativas ya que |p(x0 k)|< 1 2n−1. Por lo tanto, hay n+ 1 puntos donde Q(x) toma valores con signos alternados. De modo que, Q(x) tiene n ceros. Ya que Q∈Pn−1, debe anularse de forma id´entica. As´ı, p(x)≡f Tn(x) lo que indica que: 1 2n−1= m´ax −1≤x≤1|f Tn(x)|= m´ax −1≤x≤1|p(x)|<1 2n−1 llegando a contradicci´on. Por tanto, m´ax −1≤x≤1|f Tn(x)| ≤ m´ax −1≤x≤1|p(x)|.  Para finalizar este cap´ıtulo nos preguntamos si cu´ando n −→ ∞, los polinomios que interpolan la funci´on en los ceros de los polinomios de Chebyshev como nodos verifica pn−→ f. 37 38 Cap´ıtulo 6 Aproximaci´on de funciones continuas 6.1 Existencia del polinomio de mejor aproximaci´on En este cap´ıtulo estudiaremos la existencia del polinomio de mejor aproximaci´on. Sea un espacio vectorial Ede funciones definidas en un subconjunto de R, previsto de una norma k kEy tal que Pn⊂E. Teorema 6.1 Para toda funci´on f∈E, existe al menos un polinomio pn∈Pn, tal que: kf−pnkE= ´ınf q∈Pnkf−qkE. Demostraci´on: Sea f∈EyPn([a, b]) ⊂Eel espacio vectorial de polinomios de grado nque tiene dimensi´on finita. El teorema de Bolzano Weierstrass nos dice que en un espacio vectorial normado de dimensi´on finita, todo conjunto compacto tiene un punto de acumulaci´on. Sea {kf−qk ≥ 0, q ∈Pn} un conjunto de n´umeros reales acotado inferiormente y que tiene un ´ınfimo, al que denotaremos α. Existe {qn} ⊂ Pnde forma que kf−qnk → α. 39 Cap´ıtulo 6. Aproximaci´on de funciones continuas (cuando n → ∞). Adem´as, se ha logrado caracterizar los puntos de interpolaci´on dados para la constante Lebesgue ¯ Λn. Desafortunadamente, el c´alculo de estos puntos es demasiado complicado como para presentar un inter´es pr´actico. Si uno elige para interpolar puntos los ceros del polinomio de Chebyshev de grado (n+ 1), es decir, xn i=a+b 2+b−a 2·cos(2i+ 1)π 2n+ 2 ,para i= 0,1, . . . , n. Se tiene que Λn>¯ Λn, si n6= 1, pero se tiene todav´ıa que: Λn∼2 πLog(n),cuando n→ ∞, por lo que los puntos de Chebyshev son casi ´optimos. En muchas aplicaciones, es necesario elegir puntos de interpolaci´on equidistantes, xn i=a+i·b−a n, , donde i= 0,1, . . . , n. Se sabe que en este caso que: Λn∼2n+1 e·n·Log(n),cuando n→ ∞ que es mucho peor que para los puntos anteriores de Chebyshev. No es sorprendente, por lo tanto, ver fuertes inestabilidades cuando nse vuelve grande y de ah´ı el ejemplo de Runge. 6.3 M´odulo de continuidad Estudiemos ahora la cantidad En(f) y su comportamiento cuando ntienda hacia el infinito. Veremos que este estar´a relacionado con la regularidad de la funci´on fy m´as particularmente con su m´odulo de continuidad denotado por ω(f;h). 46 Cap´ıtulo 6. Aproximaci´on de funciones continuas Definici´on 6.12 Se define m´odulo de continuidad de una funci´on f de la siguiente manera: ω(f;h) = m´ax t,t0∈[a,b]; |t−t0|≤h|f(t)−f(t0)|. A continuaci´on, veamos que se verifican las siguientes propiedades del m´odulo de continuidad. Proposici´on 6.13 Las propiedades el m´odulo de continuidad son las siguientes: 1) La funci´on h→ω(f;h)definida para R+es positiva y creciente. 2) Es subaditiva: ω(f;h1+h2)≤ω(f;h1) + ω(f;h2). 3) Si n∈N, ω(f;n·h)≤n·ω(f;h) 4) Si λ∈R, ω(f;λ·h)≤(1 + λ)ω(f;h) 5) Si f∈C0([a, b]) entonces limh→0ω(f;h) = 0 y la funci´on h→ω(f;h)es continua para R+. 6) Si f∈C1[a, b], ω(f;h)≤hkf0k∞. Demostraci´on: 1) Al aumentar h, aumenta el tama˜no del intervalo sobre el que se ten´ıa el m´aximo y por tanto el valor de este m´aximo o, al menos, se queda igual.  2) Sea ω(f;hi) = m´axt,t0∈[a,b]; |t−t0|≤hi|f(t)−f(t0)|con i= 1,2 de forma que |f(t)−f(t0)| ≤ |f(t)−ft·h2+t0·h1 h1+h2|+|ft·h2+t0·h1 h1+h2−f(t0)| ≤ω(f;h1) + ω(f;h2). Y tomando m´aximo tenemos que ω(f;h1+h2)≤ω(f;h1) + ω(f, h2).  47 Cap´ıtulo 6. Aproximaci´on de funciones continuas 3) Sale directa de la anterior, aplicando inducci´on. 4) Sea λun n´umero real positivo. Todo n´umero real est´a comprendido entre dos n´umeros naturales a los que denotaremos [λ]y[λ] + 1. Por ser creciente, tenemos: ω(f;λ·h)≤ω(f; ([λ] + 1)h)≤(1 + [λ]) ·ω(f;h)≤ ≤ω(f;h)+[λ]·ω(f;h)≤ω(f;h) + λ·ω(f;h) = (1 + λ)·ω(f;h)  6) Sea f∈C1([a, b]). Por el Teorema del Valor Medio tenemos: f(t)−f(t0) = f0(ξ)(t−t0), adem´as: |f(t)−f(t)|−|f0(ξ)||t−t0| ≤ kf0k∞|t−t0|. Por otro lado, sabemos que kf0k∞= m´ax ξ∈[a,b]|f0(ξ)| Entonces, ω(f;h) = m´ax t,t0∈[a,b]; |t−t0|≤h|f(t)−f(t0)| ≤ m´ax t,t0∈[a,b]; |t−t0|≤hkf0k∞|t−t0|≤kf0k∞·h  A continuaci´on, enunciaremos el teorema de Jackson que demuestra que l´ım n−→∞ En(f)=0 Teorema 6.14 Existe un real M, (independiente de n, a ,b) tal que para todo n≥1 y todo f∈C0[a, b], 0≤En(f)≤M·ωf;b−a n. 48 Cap´ıtulo 6. Aproximaci´on de funciones continuas Corolario 6.15 (Teorema de Weierstrass). Si [a, b]es un intervalo cerrado y acotado de R, el conjunto de funciones polin´omicas es denso en C0[a, b]para la topolog´ıa de la convergencia uniforme. Demostraci´on: En efecto, por la propiedad 5 del m´odulo de continuidad, se tiene limn→∞ f;b−a n= 0 y como resultado limn→∞En(f) = 0,para toda funci´on f∈C0[a, b].  Nota 6.16 Si la funci´on es de clase p, la estimaci´on del Teorema de Jackson puede mejorarse. Corolario 6.17 Suponemos que f∈Cp[a, b], p ≥0. Tenemos que para todo n > p : En(f)≤Mp+1 (b−a)p n(n−1) . . . (n−p+ 1) ·ωf(p);b−a n−p.(6.3) Demostraci´on: Lo demostraremos por inducci´on. De acuerdo con el teorema de Jackson, el corolario se cumple para p= 0. Supongamos, ahora, que se cumple para cualquier funci´on f∈Cp[a, b] para un entero p. Hay que probar que se cumple para un f∈Cp+1[a, b] y en este caso, tenemos que f0es de clase Cp, es decir, f0∈Cp[a, b] donde ∀n>p+ 1. En−1(f)≤Mp+1 (b−a) (n−1)(n−2) . . . (n−p)·ωf(p+1);b−a n−1−p. Existe un polinomio qde mejor aproximaci´on de f0, donde q∈Pn−1tal que: kf0−qk∞=En−1(f0). Llamamos p(x) = Rx aq(t)dt yϕ(x) = f(x)−p(x). Para p∈Pn,se tiene En(f) = En(ϕ) y adem´as que kϕ0k∞=kf0−qk∞=En−1(f0) 49 Cap´ıtulo 6. Aproximaci´on de funciones continuas y aplicando el teorema de Jackson a la funci´on ϕy la propiedad (6) del m´odulo de continuidad se obtiene: En(f) = En(ϕ)≤Mω ϕ;b−a n≤Mb−a n·kϕ0k∞ Por lo tanto, En(f)≤Mp+2 (b−a)p+1 n(n−1) . . . (n−p)·ωf(p+1);b−a n−p−1.  6.4 Casos particulares Usando los resultados anteriores, las estimaciones que hemos dado para las constantes de Lebesgue y el teorema (6.2), obtenemos las siguientes cotas en el error de interpolaci´on de Lagrange si f∈Cp[a, b]. a) En el caso de los nodos xiequidistantes tenemos: kf−pnk∞≤(1 + Λn)·En(f)≤1 + C·2n+1 e·nLog(n)·En(f) Y aplicando (6.3) obtenemos que kf−pnk∞≤1 + C·2n+1 e·nLog(n)·En(f)≤ ≤1 + C·2n+1 e·nLog(n)·Mp+1 (b−a)p n(n−1) . . . (n−p+ 1) ·ωf(p);b−a n−p≤ ≤Cp (b−a)p·2n np+1 Log(n)·f(p);b−a n−p. 50 Cap´ıtulo 6. Aproximaci´on de funciones continuas b) En el caso de los puntos de interpolaci´on de Chebyshev tenemos: kf−pnk∞≤1 + C·2Log(n) πEn(f)≤C·Log(n)·ωf;b−a n≤ Cp(b−a)pLog(n) npωf(p);b−a n−p. Nota 6.18 Usando este resultado con p= 0, encontramos el resultado de Bernstein que dice que la interpolaci´on de Lagrange en los puntos de Chebyshev converge a f tan pronto como l´ımh→∞ ω(f;h)·Log(h) = 0 si f∈Cp[a, b], es decir, para p= 0 tenemos: kf−pnk ≤ C·Log(n)·ωf;b−a n Y aplicando la propiedad (6) del m´odulo de continuidad: kf−pnk∞≤C·Log(n)·kf0k∞·b−a n donde C·Log(n) ntiende a cero cuando n−→ ∞. De aqu´ı deducimos que Chebyshev consigue que la funci´on de clase C1se aproxime uniformemente. 6.5 Ejemplo considerando los ceros del polinomio de Chebyshev Ejemplo 6.19 Consideremos de nuevo la funci´on f=1 1 + 25x2del ejemplo de Runge que utilizamos en el cap´ıtulo 4 y calculamos su polinomio de interpolaci´on, pero esta vez, en los nodos del polinomio de Chebyshev. A continuaci´on, veremos c´omo a partir de las gr´aficas podemos deducir que a medida que aumentamos el grado del polinomio, la funci´on converge uniformemente. Es decir, que el m´etodo de Chebyshev resulta ´optimo para la minimizaci´on de 51 Cap´ıtulo 6. Aproximaci´on de funciones continuas la distancia existente entre la funci´on que se desea aproximar y el polinomio de interpolaci´on. Figura 6.1: Relaci´on entre la funci´on f(x) y el polinomio Pn(x) de grado 5. Figura 6.2: Relaci´on entre la funci´on f(x) y el polinomio Pn(x) de grado 10. 52 Cap´ıtulo 6. Aproximaci´on de funciones continuas Figura 6.3: Relaci´on entre la funci´on f(x) y el polinomio Pn(x) de grado 15. Figura 6.4: Relaci´on entre la funci´on f(x) y el polinomio Pn(x) de grado 20. 53 54 Cap´ıtulo 7 Anexos A continuaci´on, presentaremos los respectivos programas que se han usado en MATLAB para observar el fen´omeno de Runge y para los polinomios de Chebyshev respectivamente. 7.1 C´odigo Matlab 7.1.1 Fen´omeno de Runge f= @(x)1./(1 + 25 ∗x.2); Para n=5 figure(1) *N´umero de nodos es n+1: n=5; *Elecci´on de n+ 1 puntos igualmente espaciados en [−1,1] nodos=linspace(-1,1,n+1); *Valores de la funci´on en los nodos: valores=f(nodos); *Polinomio de interpolaci´on: p=polyfit(nodos,valores,n); *500 puntos del intervalo [−1,1] igualmente espaciados: 55