\documentclass[12pt]{article}
%\include{amsfonts}
\usepackage{amssymb,amsmath,latexsym,epsfig,euscript,multicol}
\usepackage{enumitem}
\usepackage[utf8x]{inputenc}

% Caracteres especiales
\def\A{\mathbb{A}}
\def\C{\mathbb{C}}
\def \N{\mathbb{N}}
\def \P{\mathbb{P}}
\def \Q{\mathbb{Q}}
\def \R{\mathbb{R}}
\def \Z{\mathbb{Z}}
\def \sen{\textrm{sen}}

\newtheorem{ejer}{Ejercicio}
\newcommand{\bej}{\begin{ejer}\rm}
\newcommand{\fej}{\end{ejer}}

\def\dt{\Delta t}
\def\dx{\Delta x}

\topmargin-2cm \vsize 29.5cm \hsize 21cm
\setlength{\textwidth}{16.75cm}\setlength{\textheight}{23.5cm}
\setlength{\oddsidemargin}{0.0cm}
\setlength{\evensidemargin}{0.0cm}


\begin{document}

%----------------------------------------------------------
%Encabezado:

\centerline{{\small Universidad de Buenos Aires - Facultad de Ciencias Exactas y Naturales - Depto. de Matemática}}
 
 \vskip 0.2cm
 \hrulefill
 \vskip 0.2cm

 \centerline{{\bf\Large{\sc Elementos de Cálculo Numérico / Cálculo Numérico}}}
 \vskip 0.2cm
 \centerline{\ttfamily Curso de Verano 2019}
 \hrulefill

 \bigskip
 \centerline{\bf Práctica N$^\circ$ 9: Ecuaciones no lineales.}
 \bigskip


%----------------------------------------------------------
% 1
\bej Implementar un programa que reciba como input una función $f$, dos números $a,b$, y una tolerancia $tol$ y aplique el método de bisección para aproximar una raíz de $f$ en el intervalo $[a,b]$, garantizando que el error cometido sea menor que $tol$. 
\fej

%----------------------------------------------------------
% 2
\bej Elegir un intervalo apropiado y utilizar el método de bisección para calcular una raíz de la ecuación:
$$
2x= \tan (x)
$$
>Cuántos pasos hay que hacer para garantizar que el error
sea menor que $10^{-5}$?
\fej

%----------------------------------------------------------
% 3
\bej Implementar un programa que reciba como input una función $f$, su derivada $f'$ y un punto inicial $x_0$ y aplique el método de Newton-Raphson para buscar una raíz de $f$ a partir de $x_0$. \fej

%----------------------------------------------------------
% 4
\bej Implementar un programa que reciba como input una función $f$ y dos puntos $x_0$ y $x_1$ y aplique el método de la secante para buscar una raíz de $f$ con datos iniciales $x_0$ y $x_1$. \fej

%----------------------------------------------------------
% 5
\bej Aproximar $\sqrt[3] 2$ utilizando el método de bisección con intervalo inicial $[1,2]$,  el m\'etodo 
N-R, comenzando con $x_0 = 2$ y el método de la secante con $x_0=3$, $x_1=2$. 

En todos los casos, calcular el error cometido en cada iteración comparando con el valor de $\sqrt[3] 2$ arrojado por Octave, y graficar el logaritmo del error para verificar el orden de convergencia de cada método.
\fej

%----------------------------------------------------------
% 6
\bej Considerar la función $\displaystyle
f(x)=\frac{x}{1+|x|}$. Determinar para qu\'e valores de $x_0$ la
iteración N-R es convergente, para cuáles es divergente, y
cu\'ando se obtienen ciclos periódicos.
\fej

%----------------------------------------------------------
% 7
\bej Sea $f$ una función $C^1$ y sea $(x_n)_{n\in \N}$ la
sucesión que se obtiene al aplicar el método N-R a $f$.
Supongamos que $x_n$ converge a $r$ y $f'(r)\ne 0$, mostrar que $r$ es raíz de $f$.
\fej

%----------------------------------------------------------
% 8
\bej
\label {concav} Sea $f$ una funci\'on suave, y $a$ tal que
$f(a)=0$, y
 $f'(a)\neq 0$. Suponiendo que en $(a,b]$, $f,\ f',\ f''$ son positivas,
 probar que la iteraci\'on de N-R generada a partir de $x_0 \in (a,b)$
converge decrecientemente hacia $a$.
\fej

%----------------------------------------------------------
% 9
\bej Sea $f:\R \to \R, \ f(x)= (x+1)e^x -4$.

\begin{enumerate}[label=\alph*)]
\item Probar que el método de Newton-Raphson es convergente para todo $x_0 >1$.

\item Analizar la convergencia del método si se toma como valor inicial $x_0 = -3$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 10
\bej Sea $f:\R\to\R$ tal que $f'(x)> \delta>0$ con una única raíz $r$. Se desea aplicar el método de Newton Raphson para hallar $r$.
\begin{enumerate}
\item Probar que si $f(x)>f'(x)(x-r)$ para todo $x>r$ entonces se tiene que $x_1<r$ para todo dato inicial $x_0 > r$. 
\item Probar que si $f''(x)<0$ para todo $x<r$, entonces el método genera una sucesión creciente que converge a $r$ para todo $x_0<r$. Concluir que si se cumplen ambas condiciones, el método converge.
\item Probar que Newton Raphson converge a la única raíz de  $f(x)=-e^{-x}+5x$ para todo dato inicial $x_0$. 
\end{enumerate}
\fej

%----------------------------------------------------------
% 11

\bej Sea $f(x)= x^3 - x -1$. La ecuación $f(x) = 0$ tiene una única raíz $r$ en el intervalo $(1,2)$. Se consideran las funciones:
$$ g(x) =  x^3-1,\hskip 2cm h(x)=\sqrt[3]{x+1}.$$
\begin{enumerate}[label=\alph*)]
\item Probar que $r$ es un punto fijo tanto de $g$ como de $h$.
\item Decidir si $g$ o $h$ pueden utilizarse para buscar $r$ a través de un método de punto fijo. 
\item Cuando sea posible, determinar un intervalo inicial $I$ en el cual el método converja, y dar un valor inicial $x_0\in I$ y la cantidad de iteraciones
necesarias para aproximar $r$ con error menor que
$10^{-5}$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 12

\bej Sea $f:\R_{>0}\to\R$ definida como $f(x)= \frac
{8x-1}x - e^x.$
\begin{enumerate}[label=\alph*)]
\item Determinar, mediante gráficos convenientes, el número de raíces de $f$, localizando cada una de ellas entre dos enteros consecutivos.
\item Proponer tres métodos de punto fijo para $f$ y determinar si convergen a alguna de sus raíces si se toma dato inicial $x_0=1$.
\end{enumerate}
\fej

%----------------------------------------------------------
% 13
\bej Sea $g$ una funci\'on tal que $g'$ es continua en $[s, b]$, donde $s$ es un punto fijo de $g$. Si adem\'as, se verifica que
$0\leq g'(x)\leq K<1$ para todo $x\in[s,b]$, mostrar que la iteraci\'on, comenzando con $x_0\in [s,b]$, converge decrecientemente a $s$.
\fej


%----------------------------------------------------------
% 14
\bej  Dada la funci\'on $f(x)=x+\frac{1}{x}-2$, $f:\R_{>0} \to \R$,
se construye el siguiente algoritmo para aproximar la ra\'{\i}z
$r=1$:
$$x_{n+1}=2-\frac{1}{x_n}$$
Verificar que si $x_0>1$ entonces la sucesi\'on $\{x_n\}$
es mon\'otona decreciente y acotada inferiormente por 1. Concluir
que $x_n\rightarrow 1$, aunque esta iteraci\'on no est\'a en las
hip\'otesis del teorema del punto fijo. ¿Qu\'e hip\'otesis no se
cumple?
\fej

%----------------------------------------------------------
% 15
\bej Sea $f$ una función $C^1$ en las condiciones del método
N-R. Sea $g(x)= x - \frac{f(x)}{f'(x)}$. Mostrar que el método
N-R es un m\'etodo de punto fijo.
\fej


%-------------------------------------------------------
%16
\bej  Para $f$ una funci\'on $C^2$ que tiene una raíz de orden $2$ en $r$:
\begin{enumerate}[label=\alph*)]
\item Demostrar que el método N-R converge sólo
linealmente a $r$ (Sugerencia: Notar que en este caso la $g$ del
ejercicio anterior no está definida para $x = r$, redefinirla
como $g(r) = r$, probar la diferenciabilidad de $g$ y demostrar
que $g'(r) \ne 0$).
\item >Cuál es el orden de convergencia de la siguiente modificación?
\begin{equation}\label{NRmod}
x_{n+1}=x_n - 2 \frac{f(x_n)}{f'(x_n)}
\end{equation}
\item Sea $f(x) = 4x^3 - 3x +1$. $f$ tiene una raíz doble.Aproximarla calculando las 10 primeras iteraciones de los métodos N-R y del método \eqref{NRmod}, con dato inicial $x_0=25$. Graficar simultáneamente las dos sucesiones obtenidas. 
\end{enumerate}
\fej

%----------------------------------------------------------
% 17
\bej Dada $F:\R^n\to\R^n$ el método N-R generalizado consiste en realizar la iteración vectorial $$x^{k+1}= x^k - (DF|_{x^k})^{-1}.F(x^k),$$ donde $(DF|_{x^k})^{-1}$ es la inversa de la matriz diferencial de $F$ evaluada en $x^k$.

Usar N-R generalizado para hallar un mínimo de la función $f(x,y) = ye^{-x^2}+x^2+y^4+x$, comenzando con $(x_0, y_0) = (2,1)$.
\fej

%----------------------------------------------------------
% 18
\bej
Considerar el problema de la propagación de una llama:
$$\left\{\begin{array}{ll}
\dot{y}=y^2-y^3 \mbox{ para } t\in[0,2/\delta]\\
y(0) = \delta. \\
\end{array}\right.$$
Al prender un fósforo, la bola de fuego crece rápidamente hasta que alcanza un tamaño crí­tico. Luego, permanece en ese tamaño porque la cantidad de oxígeno que se consume por la combustión en el interior de la bola se compensa con la cantidad disponible en la superficie. El radio de la bola de fuego se representa con $y(t)$ y los términos $y^2$ e $y^3$ provienen de la superficie y el volumen. El parámetro crítico es el radio inicial $\delta$.
\begin{enumerate}[label=\alph*)]
\item Resolver numéricamente el sistema para $\delta=0.01$ utilizando el método de Euler, con paso $h=2$. ¿Qué se observa?
\item Repetir el í­tem anterior pero utilizando el método de Euler implícito:
$$y_{n} = y_{n+1}-hf(t_{n+1},y_{n+1}).$$
Para despejar $y_{n+1}$ en cada paso, utilizar el método de Newton Raphson con dato inicial $y_n$. ¿Qué se observa?
\end{enumerate}


%----------------------------------------------------------
% 19

\fej
\bej {\bf Cuencas de atracción / Fractales de Newton: } Sea $P:\C\to\C$ un polinomio de grado $3$, con raíces $r_1,r_2,r_3$ contenidas en el rectángulo $R = [-1,1]\times[-1,1]$. Se desea saber, para cada punto $z_0$ en $R$, a qué raíz converge el método de Newton, cuando se toma dato inicial $z_0$. 
Hacer un programa que: 
\begin{enumerate}
\item Reciba como input un vector $P=(P_1,P_2,P_3,P_4)$, que representa al polinomio $P(x) = P_1 x^3+P_2 x^2+P_3 x+P_4$. 
\item Calcule las raíces de $P$ utilizando el comando \verb+roots+.
\item Haga una grilla de puntos de la forma $(x_j,y_k)\in R$.
\item Para cada punto $(x_j,y_k)$, corra 5 iteraciones del método de Newton, con dato inicial dado por el complejo $z = x_j+i y_k$. 
\item Determine la raíz $r$ más próxima al resultado obtenido.
\item Realice un gráfico que pinte cada punto $(x_j,y_k)$ de un color distinto de acuerdo a la raíz a la que el método se aproxime. Por ejemplo: si $r=r_1$, $(x_j,y_k)$ se pinta de azul, si $r=r_2$, de rojo y si $r=r_3$, de amarillo. 
\end{enumerate}
De este modo, la región pintada de azul es la \emph{cuenca de atracción} de la raíz $r_1$, etc. Comunmente, las cuencas de atracción resultan ser fractales. Puede repetirse el experimento para polinomios de mayor grado. 
\fej

%-------------------------------------------------------
%20
\bej
Se tiene la siguiente tabla de datos:
\begin{center}
\begin{tabular}{c|ccccccccccccc}
\hline
$x$ &0&0.5&1&1.5&2&2.5&3&3.5&4&4.5&5 \\
\hline
$y$ &0.756&0.561&0.407&0.372&0.305&0.24&0.219&0.209&0.21&0.194&0.140\\
\hline
\end{tabular}
\end{center}
Se propone un ajuste de los puntos a través de una función de la forma $f(x) = \frac{1}{x+b}$. Para determinar el valor de $b$ si desea resolver el problema de cuadrados mínimos:
$$\min_{b} F(b) = \sum_{i=0}^{10}\left(y_i-\frac{1}{x_i+b}\right)^2.$$
Para ello se propone una iteración de punto fijo de la forma $b_{n+1} = g(b_n)$, donde:
\begin{equation}\label{pf}
g(b) = \frac{1}{y_0+\sum_{i=1}^{10}\left(y_i-\frac{1}{x_i+b}\right)\left(\frac{x_0+b}{x_i+b}\right)^2}-x_0
\end{equation}
\begin{enumerate}[label=\alph*)]
\item Probar que \eqref{pf} define efectivamente un método de punto fijo del problema $F'(b) = 0$. 
\item Hallar $b$ utilizando el método de punto fijo, tomando $b_0=1$. 
\item Graficar los puntos, junto con la $f$ que los ajusta. Agregar, en un mismo gráfico, los polinomios de grado $2$ y $3$ que ajustan los datos por cuadrados mínimos.
\end{enumerate} 
\fej
\end{document}