Bel pidió por mail, asi que aca está el final del 23 de febrero de Numerico con soluciones y todo. Cualquier duda posteen!
a) Sea \(A \in \mathbb{R}^{n\times n}\), pruebe que Jacobi converge si \(A\) es estrictamente diagonal dominante.
b) Pruebe que si \(B \in \mathbb{R}^{n\times n}\) y \(||B^k||<1\) para cierto \(k \geq 1\) entonces las iteraciones \(x^{m+1} = Bx^m+b\) convergen a un punto fijo \(x\) tal que \(x = Bx+b\)
c) De un ejemplo de una matriz \(B\in \mathbb{R}^{n\times n}\) tal que \(||B||\geq 1\) y sin embargo las iteraciones \(x^{m+1} = Bx^m+b\) convergen a un punto fijo \(x\) tal que \(x = Bx+b\).
(Sug. mire matrices de la forma
Sea \(f\in C^2[a,b],\ a=x_0<x_1<\cdots < x_n=b\). Llamando \(h_i=x_{i+1}-x_i\) y \(l(x)\) a la función lineal a trozos que verifica \(l(x_i)=f(x_i)\) se tiene que:
a) \(||f-l||_{\infty,[a,b]}\leq \tfrac{h_M^2}{2} ||f''||_{\infty,[a,b]}\)
b) \(||f'-l'||_{\infty,[a,b]}\leq h_M ||f''||_{\infty,[a,b]}\)
donde \(\displaystyle h_M= \max_{0\leq i\leq n-1} \{h_i\}.\)
Sean \(T_n\) y \(T_m\) polinomios de Tchebychev con \(m\not = n\). Verifique que son ortogonales en el producto interno dado por
Dos cosas que surgieron preguntandole a Acosta:
i) En 1)b) se puede asumir la existencia de un punto fijo tal que \(x=Bx+b\), según Acosta este hecho se debería desprender de la solucion, peeeero a mi no me quedo tan claro asi que fui y pregunte.
ii) La norma de la que habla 1)c) es una norma particular. Tiene que ser asi porque si para toda norma \(||B||\geq 1\), entonces \(\rho(B)\geq 1\) y \(x_{m+1}=Bx_m+b\) no converge para algun dato inicial.
Las soluciones
1)a)
Solucion tal cual el apunte:
Alcanza con ver que \(||B_J||<1\)
Mirando en norma infinito, queda \(||B_J||_\infty = \displaystyle \max_i \sum_j |b_{ij}| = \sum_{j=1}^N \left|\tfrac{a_{ij}}{a_{ii}}\right|\) para algún \(i\)
Ahora, \(||B_J||<1 \Leftrightarrow \displaystyle \sum_{j=1}^N \left|\tfrac{a_{ij}}{a_{ii}}\right| <1 \Leftrightarrow \sum_{j=1}^N \tfrac{|a_{ij}|}{|a_{ii}|} < 1 \Leftrightarrow \sum_{j=1}^N |a_{ij}|< |a_{ii}|\)
que vale por ser \(A\) estrictamente diagonal dominante.
b)
Nosotros sabemos que si \(||B|| < 1\) las iteraciones convergen y somos felices. Hay que ver como podemos hacer para acomodar esa idea a la condicion \(||B^k|| < 1\)
Para esto consideramos las \(k\) subsucesiones de \(\{x_n\}\) que van saltando de a \(k\) elementos, a saber: \(\left\{x_{nk+i}\right\}, 0\leq i < k\)
Para cada una de esas subsucesiones (que por conveniencia vamos a notar \(\{y_n\}\)), vale: \(y_{n+1}=B^ky_n\), entonces como \(||B^k||<1\) esas \(k\) subsucesiones convergen.
Observemos que el punto fijo es único: si \(x_1\) y \(x_2\) son puntos fijos, restando las ecuaciones \(x_i = Bx_i+b\) queda \((x_1-x_2)=B(x_1-x_2)\) hacemos ese reemplazo k veces y queda \((x_1-x_2)=B^k(x_1-x_2)\) tomando norma \(||x_1-x_2|| = ||B^k(x_1-x_2)|| \leq ||B_k||\cdot ||x_1-x_2||< ||x_1-x_2||\), que vale solo si \(x_1-x_2=0\).
Recapitulando: las k subsucesiones que saltan de a k convergen a un mismo punto \(x\). Aca ya casi está, falta un argumento para ver que todas juntas también convergen, y que va a necesitar una cuentita con epsilons y enes_i:
Dado \(\varepsilon >0\) existe \(n_i\) tal que \(n\geq n_i \Rightarrow ||x_{nk+i}-x||<\varepsilon\). Entonces tomamos \(N=\max\{n_i\}\). Si consideramos \(n\geq k(N+1)=kN+k\), y \(n=kp+i\), con \(0\leq i < k\), se puede ver que \(p\geq N\), si no fuera asi, \(n=kp+i< kN+k = k(N+1) \leq n\), ABS!
Entonces \(p\geq N \geq n_i\), por lo que \(||x-x_n||<\varepsilon\)
((Notar que esto es solo una forma recontra rebuscada y formal de decir "Para todo epsilon positivo existe \(n_0\ (=k(N+1))\), tal que si \(n\geq n_0\) entonces \(||x-x_n|| < \varepsilon\)"))
c)
Inductivamente se puede ver que
La idea ahora, es recordar que \(e_n = B^n e_0\), entonces si \(\lambda<1\), \(B^n \to 0\) y por lo tanto el metodo va a converger para cualquier dato inicial.
Viendo esto tomamos:
Si hacemos el cambio de variables \(y =cos^{-1}x \Leftrightarrow x=\cos y\)
$$\langle T_n,T_m\rangle = \displaystyle \int_0^\pi \cos(ny)\cos(my) \dfrac{1}{\sqrt{1-\cos^2(y)}} |sen(y)|\ dy = \int_0^\pi \cos(ny)\cos(my) \dfrac{|sen(y)|}{|sen(y)|} \ dy = \int_0^\pi \cos(ny)\cos(my)\ dy$$
Como la funcion \(\cos(ny)\cos(my)\) es par,
\(\langle T_n,T_m\rangle = \displaystyle \int_0^\pi \cos(ny)\cos(my)\ dy = \dfrac{1}{2} \int_{-\pi}^\pi \cos(ny)\cos(my)\ dy = \dfrac{1}{2} 0 = 0 \Rightarrow T_n \perp T_m\)
b)
Para que la cuadratura tenga presición máxima, debe interpolar en los ceros del polinomio ortogonal. En nuestro caso, como queremos dos nodos, queremos los ceros de \(T_2\):
\(x_0 = \cos\left(\dfrac{\pi}{4}\right) = \dfrac{\sqrt{2}}{2}\) y \(x_1 = \cos\left(\dfrac{3\pi}{4}\right) = \dfrac{\sqrt{-2}}{2}\)
Las cuadraturas gaussianas de n+1 nodos tienen presición 2n+1, entonces la nuestra tiene presición 3
Recordemos que si nuestro metodo multipaso es \(\alpha_0y_n+\alpha_1y_{n+1}+\cdots+\alpha_Ny_{n+N} = h(\beta_0f_n+\beta_1f_{n+1}+\cdots+\beta_Nf_{n+N})\) y ademas \(y\) es lo suficientemente regular podemos expresar a \(h\tau\) como:
Para que el metodo sea convergente es suficiente que \(C_0=C_1=0\) (consistencia (NOTA: si uno define los polinomios \(p(x)=\sum\alpha_j x^j\) y \(q(x)=\sum\beta_j x^j\) estas condiciones son totalmente equivalentes a \(p(1)=0\) y \(p'(1)=q(1)\))) y la condición de la raiz.
En nuestro metodo: \(\alpha_0 = -a\), \(\alpha_1 = 0\), \(\alpha_2 = 1\), \(\beta_0 = \tfrac{1}{3}\), \(\beta_1 = \tfrac{b}{3}\) y \(\beta_2 = \tfrac{1}{3}\)
Ambas raices son simples y tienen modulo 1 por lo que cumplen la Condicion de la Raiz. (Recordar la condicion era raices simples modulo menor o igual a 1, raices multiples modulo menor a 1)
Luego el metodo es convergente.
Falta ver el orden
El metodo tiene orden q si \(C_0=C_1=\cdots=C_q = 0\) y \(C_{q+1}\not= 0\)
Ya vimos \(C_0 = C_1 = 0\)
yo también me desesperé un poco cuando lo leí, pero me parece que es acotar el error en los intervalos y nada más... igual todavía no lo intenté, capaz que nada que ver. todavía no terminé con la teoría, me estoy volviendo loca con multipaso, no lo puedo entender 🙁
no, en verdad creo que puedo resolver un ejercicio típico (como este), lo que siento es que es el tema que más flojo tengo "conceptualmente", o sea, no lo entiendo en profundidad, solo puedo aplicarlo :p
recién terminé con toda la teoría, (de entenderla, no de saber todas las demos :p)
ahora me voy a poner a hacer ejercicios modelo de cada tema, y después a aprennder los teoremas, y después a hacer finales viejos.
y ahora me voy a dejar de desvirtuar 😛
se comprende todo lo que hace "nachito" en el punto 1 b) pero tengo una dificultad apenas iniciado el ejercicio.
¿y si k no es natural? no se, digo por ej k=pi... no podés ir "saltando" de a pi elementos. Salvo que en la hipotesis se agregue eso, pues la hipótesis asegura la existencia d un k pero no dice qe sea entero
¿alguien me ayuda con esto?
Además... tampoco veo la relación \(y_{n+1}=B^ky_n\) yo más bien llego a algo así:
\(y_{n+1}=B^ky_n+(\sum_{j=0}^nB^j).b\) o podría pensarse:
\(y_{n+1}=B^ky_n+b'\) total el término indep no importa demasiado... aunque para la convergencia capaz q si. ¿qe onda? ¿me equivoqué? ayuda con estooo1!!
yo la verdad no lo hice como lo hizo nacho, porque.. nada, ni ahí se me ocurre algo así, que involucre tantas sucesiones xd
supongo que algún error tendrá hacerlo así, pero yo lo que hice fue decir que , para algún n muy grande (más grande que k),
\(||{e}_{n}||<||{B}^{n}{e}_{0}||=||{({B}^{k})}^{\frac{n}{k}}{e}_{0}||<||{B}^{k}||^{n/k}||{e}_{0}|| \longrightarrow 0\)cuando \(n \rightarrow \infty\) porque k está fijo y \(||{B}^{k}||<1\) por hipótesis
bueno, yo lo había pensado así, es mucho menos sofisticado pero también me resultó más natural con el tipo de demos que se hacen en la materia (seguro la de nacho es mucho más elegante, pero yo ni la entiendo 🙁 jaja), así que por favor si alguien quiere contarme qué les parece...
en lugar de calcular B^n yo lo que hice fue usar que el radio espectral es menor qe uno, para una matriz muuuuy parecida (nomás que puse 5 en lugar de 10)
La diferencia es que la condición del radio espectral es necesaria y suficiente para que el método converja, en cambio la condición de que la norma sea <1 es sólo suficiente.
Así me ahorré un par de cuentas.. pues se ve clarito que el radio espectral es 1/2 y qe la norma infinito, o la uno, para el caso es lo mismo, es mayor que uno.
Buenísimo que te haya parecido bien lo del 1-b)!
lo que decís del 1-c) me parece lógico, la verdad no se me ocurrió (tampoco se me ocurrió lo que hizo nacho igual u.u). Lo que hizo nacho así tal cual está hecho en el apunte (especulación: habría que mirar todos los ejemplos del apunte porque puede tomar alguno,jaja)
por lo que sé nacho se sacó 10, así que no debe estar mal :p
igual.. fijate que en el 3) a) probás que los polinomios de Tchebychev son, justamente, ortogonales para ese PI. Y como no necesitás hacer Gram-Schmidt porque ya tenés una Base Ortogonal, justamente los \({T}_{k}\), no hace falta normalizarlos porque... bueno, lo que necesitás son las raíces, así que sirven sin normalizar. (uno en general normaliza sólo para haer GS)
Pero son ortogonales entre si, y Además esas dos funciones no generan P_2 como se querría
o sea T_m y T_n forman un conjunto ortogonal, que es base de un subespacio que no es P_2,
Cómo aseguras la precisi[on de la cuadratura con funciones que no son polinomios, si la definición de precisión (al menos la que yo tengo) es a partir de polinomios??
como T_n y T_m son ortogonales para valores distintoosde m y n sería que T_2 es orto a T_1 y a T_0 y esos tres son generadores de P_2 pues tienen grados 2 1 y 0.. ahora siii!!!!