Sistemas no Lineales

Teorema del Punto fijo

Una función $G:D\subset {\mathbb{R}}^n\to {\mathbb{R}}^n$ tiene un punto fijo en $\overline{p}\in D$ si $G(\overline{p})=\overline{p}$

1. Sea $G$ continua en $D$, entonces si $G(\overline{x})\in D,\forall x\in D$, entonces $G$ tiene punto fijo en $D$
2. Si $\exists 0<k<1$ talque $\Vert \frac{\partial g_i(\overline{x})}{\partial x_j}\Vert \le \frac{K}{n},\forall \overline{x}\in D$, entonces el punto fijo de $G$ es en $D$

Entonces la sucesión definida como:

$$x^{(k)}=G(x^{(k-1)})\forall k\ge 1$$

Converge al único punto fijo $p\in D$, además podemos encontrar el mínimo de iteraciones necesarias a partir de:

$$\Vert x^k-p{\Vert }_{\infty }\ge \frac{K^k}{1-K}\Vert x^{(1)}-x^{(0)}{\Vert }_{\infty }$$

Note

Este método converge para cualquier semilla perteneciente a $D$.

Newton-Raphson

En el caso $n$-dimensional, el método Newton Raphson se resuelve a partir de dividir por la matriz Jacobiana

$$G(x)=x-A^{-1}(x)F(x)$$

Donde $A(x)=J(x)$, por lo tanto, la sucesión del punto fijo puede ser definida como

$$x^{(k)}=x^{(k-1)}-J_F^{-1}(x^{(k-1)})F(x^{(k-1)})$$

Sin embargo, no se calcula la inversa de la Jacobiana en cada iteración, por lo que se resuelve el sistema de la siguiente forma

$$J_F(x^{(k-1)})y^{(k-1)}=-F(x^{(k-1)})$$ $$x^{(k)}={\overline{x}}^{(k-1)}+{\overline{y}}^{(k-1)}$$

Note

Este método tiene convergencia cuadrática, al igual que para una sola variable.

Métodos Cuasi Newton

Consisten en aproximar la matriz Jacobiana con cada iteración mediante fórmulas de recurrencia.

Podemos definir una sucesión de $A$ a partir de la Jacobiana inicial:

$$A_k=A_{k-1}+\frac{(y_{k-1}-A_{k-1}{s}_{k-1})s_{k-1}^T}{s_{k-1}^T{s}_{k-1}}$$

Definiendo:

• $y_k=f(x_k)-f(x_{k-1})$
• $s_{k-1}=x_k-x_{k-1}$

De esta forma, los métodos de Cuasi-Newton necesitan el cálculo de una sola Jacobiana

Método del Descenso más Rápido

Converge solo linealmente a la función, pero siempre converge. La idea consiste en partir de cualquier semilla, evaluar la función, y movernos en la dirección del máximo descenso, es decir, en la dirección inversa al gradiente.

Primero, definimos $G$ como $G(\vec{x})={\sum }_i^n{f}_i(\vec{x}{)}^2$

1. Evaluar $g$ en una aproximación inicial $x^{(0)}$
2. Determinar una dirección en $x^{(0)}$ que origine una disminución del valor de $G$
3. Desplazar una cantidad $\alpha$ apropiada en esa dirección y llamar al nuevo punto $x^{(1)}$
4. Repetir los pasos hasta encontrar una aproximación deseada.

De esta forma, encontramos una sucesión que converge para toda semilla inicial a la solución del sistema, para alguna constante $\alpha >0$.

$$x^{(k)}=x^{(k-1)}-\alpha {\nabla }_G(x^{(k-1)})$$

Para hallar nuestra constante, buscamos el valor $\alpha$ que minimice la función $F$ en nuestro nuevo punto

Como hallar este mínimo es muy costoso, definimos $h(\alpha )$ como un polinomio de grado 2.

Primero definimos los coeficientes

$${\alpha }_1=0$$ $${\alpha }_3/h({\alpha }_3)<h({\alpha }_1)$$ $${\alpha }_2=\frac{{\alpha }_3}{2}$$

Luego, buscamos un polinomio $h^{\ast }(\alpha )$ de grado $2$ que interpole los puntos

$$\{({\alpha }_1,h({\alpha }_1)),({\alpha }_2,h({\alpha }_2)),({\alpha }_3,h({\alpha }_3))\}$$

Una vez construido este polinomio, encontramos $\alpha$ que minimice $h(\alpha )$ en el intervalo $({\alpha }_1,{\alpha }_3)$

Para hallar el gradiente, nos conviene usar la forma matricial, vale que:

$${\nabla }_G(\vec{x})=2J_F^T(\vec{x})F(\vec{x})$$