03_Equacoes_Nao-Lineares.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Equações não lineares\n",
    "\n",
    "A resolução de equações não lineares surge naturalmente em diversas aplicações. Vamos começar com um exemplo simples. Considere que temos um canhão que dispara seus projéteis a uma velocidade inicial $v_0$. O objetivo é definir o ângulo $\\theta$ de disparo para atingir um alvo que está a distância $d$.\n",
    "\n",
    "Precisamos então calibrar $\\theta$ de forma a garantir que o projétil caia exatamente à distância desejada. Dois fatores devem ser considerados. Logo após o disparo o projétil irá subir um pouco até a ação da gravidade inverter sua velocidade vertical e ele começar a cair. O tempo total de voo é o tempo de subida mais o tempo de queda. Vamos considerar que apenas a força da gravidade age sobre o projétil, desconsiderando o efeito do atrito com o ar. Nesse caso, a aceleração vertical é constante igual $-g$. Ou seja, temos:\n",
    "\\begin{align*}\n",
    "y(0) = 0,\\quad y'(t) = v_0 \\sin(\\theta), \\quad y''(t) &= -g \\Rightarrow \\\\\n",
    "y(t) = 0 + v_0 \\sin(\\theta)t - \\frac{g}{2} t^2.\n",
    "\\end{align*}\n",
    "O tempo total até o impacto será $T > 0$ é obtido resolvedo $y(t) = 0,\\ t > 0$, que é dado por\n",
    "$$\n",
    "T = \\frac{2v_0 \\sin(\\theta)}{g}.\n",
    "$$\n",
    "Já a distância horizontal pecorrida é dada por \n",
    "$$\n",
    "x(t) = v_0 \\cos(\\theta) T.\n",
    "$$\n",
    "Estamos novamente desprezando o atrito com o ar.\n",
    "\n",
    "O objetivo final é encontrar $\\theta$ tal que $x(T) = d$. Ou seja queremos resolver a equação\n",
    "$$\n",
    "\\frac{2 v_0^2 \\sin(\\theta) \\cos(\\theta)}{g} = d,\n",
    "$$\n",
    "em função de $\\theta$.\n",
    "\n",
    "Em outras palavras, se definirmos\n",
    "$$\n",
    "f(\\theta) = 2 v_0^2 \\sin(\\theta) \\cos(\\theta) - gd,\n",
    "$$\n",
    "desejamos encontrar $\\theta$ tal que a equação não-linear\n",
    "$$\n",
    "f(\\theta) = 0\n",
    "$$\n",
    "seja válida.\n",
    "\n",
    "Apesar dessa equação admitir solução por identidades trigonométricas, vamos encará-la como uma equação que não admite solução fechada. Nesse caso, precisamos de um método que consiga resolver equações gerais. Algo que funcione para além daquelas equações que conseguimos resolver manualmente usando manipulações algébricas. Esse é o objetivo das próximas aulas.\n",
    "\n",
    "# Estudo de equação não-lineares de uma variável\n",
    "\n",
    "Como vimos anteriormente, podemos ter interesse de resolver uma equação do tipo\n",
    "$$\n",
    "f(x) = 0,\n",
    "$$\n",
    "em que $f: \\mathbb{R} \\rightarrow \\mathbb{R}$. Um $x$ que obedece à equação acima será chamado de uma *zero*, ou *raiz*, de $f$.\n",
    "\n",
    "Veremos a seguir que isso pode ser feito por alguns métodos iterativos que irão encontrar soluções aproximadas da equação com precisão cada vez mais alta.\n",
    "\n",
    "Inicialmente, note que há algumas questões fundamentais que devem ser tratadas. Primeiro, é preciso se perguntar se a equação tem solução. Se tal solução existir, será que ela é única? Vamos apresentar abaixo algumas condições matemáticas que podem ser utilizadas nesse estudo. A situação mais confortável ocorre quando há solução e ela é única. Nesse caso, não há dúvidas de qual o papel do método numérico: encontrar a única raiz. Quando há mais de um zero, a situação já não é tão clara. Será que todas as raízes têm sentido Físico? O método teria que encontrar todas as possíveis soluções? Isso é possível? Se o método for capaz de encontrar apenas uma solução, será que é possível escolher, ou guiar o algoritmo, para uma das raízes em particular? Quanto tempo o método demora para encontrar uma boa aproximação da única, ou pelo menos de uma, solução?\n",
    "\n",
    "## Existência e unicidade de soluções\n",
    "\n",
    "Um resultado de cáculo fundamental para tratar da existência de soluções de uma equação não linear é o teorema de Bolzano.\n",
    "\n",
    "**Teorema de Bolzano** Seja $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ uma função contínua em um intervalo $[a, b] \\subset \\mathbb{R}$. Se $f(a)f(b) < 0$ então existe $x \\in (a, b)$, tal que $f(x) = 0$.\n",
    "\n",
    "Ou seja, se uma função contínua troca de sinal nos extremos em um intervalo, então ela possui pelo menos um zero (nesse intervalo). \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Plots\n",
    "pyplot()\n",
    "using LaTeXStrings\n",
    "\n",
    "# Define a função\n",
    "f(x) = x^5 - 3.0*x^3 - 2.0*x + 1.0\n",
    "\n",
    "# Define o intervalo\n",
    "x = LinRange(-2, 2, 100)\n",
    "\n",
    "# Desenha o gráfico e o eixo x.\n",
    "plot(x, f.(x), label=L\"f\", lw=2)\n",
    "plot!(x, 0.0*x, color=:black, label=\"\", lw=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note que essa condição é apenas necessária para a existência de zero. É claro que uma função pode ter o mesmo sinal nos extremos de um intervalo e mesmo assim ter zeros dentro dele. Considere, por exemplo, o caso acima no intervalo $[-2, 1.5]$.\n",
    "\n",
    "Já para garantir a unicidade é preciso exigir mais da função $f$. Uma hipótese razoável é que ela seja constantemente crescente ou decrescente dentro do intervalo. Para isso, basta exigir que a derivada da função não troque de sinal.\n",
    "\n",
    "**Teorema** Seja $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ diferenciável em um intervalo $[a, b] \\subset \\mathbb{R}$. Se $f(a)f(b) < 0$ e a derivada de $f$ tem sinal constante em $(a, b)$, então existe um único $x \\in (a, b)$, tal que $f(x) = 0$.\n",
    "\n",
    "Note que temos que considerar os valores da derivada em todo o intervalo, e não apenas nos extremos. \n",
    "\n",
    "*Exercício.* Estude os zeros da função acima, encontre intervalos que contém os três zeros apresentados de forma única usando os teoremas apresentados.\n",
    "\n",
    "## Método da Bissecção\n",
    "\n",
    "O teorema de Bolzano serve de ponto de partida para um primeiro método iterativo para resolução de equações não-lineares conhecido como bissecção. A ideia dele é simples. Imagine que $f$ é contínua e temos na mão um intervalo $[a, b]$ como no teorema. Isso quer dizer que temos certeza que existe uma raiz nesse intervalo. Uma aproximação razoável para essa raiz usando apenas essa informação é o ponto médio do intervalo. Aparentemente isso é tudo o que se pode fazer com essa informação.\n",
    "\n",
    "Porém, podemos também calcular a função nesse ponto médio $m = \\frac{a + b}{2}$ e há três possibilidades:\n",
    "\n",
    "1. $f(m) = 0$. Nesse caso demos sorte, de fato o ponto médio é uma raiz que foi encontrada.\n",
    "\n",
    "2. Sinal de $f(m)$ é o mesmo sinal de $f(a)$. Nesse caso podemos concluir, usando o teorema de Bolsano, que há uma raiz no intervalo $[m, b]$. Note que esse intervalo é bem menor que o original, tendo metade do seu comprimento.\n",
    "\n",
    "3. Sinal de $f(m)$ é o mesmo sinal de $f(b)$. Nesse caso podemos concluir, usando o teorema de Bolsano, que há uma raiz no intervalo $[a, m]$. Note que esse intervalo é bem menor que o original, tendo metade do seu comprimento."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = LinRange(1.5, 2.0, 100)\n",
    "plot(x, f.(x), lw=2, label=\"\", layout=2, subplot=1)\n",
    "plot!(x, 0*x, color=:black, lw=2, label=\"\", subplot=1)\n",
    "title!(\"Caso 2\", subplot=1)\n",
    "\n",
    "x = LinRange(0.25,0.75,100)\n",
    "plot!(x, f.(x), lw=2, label=\"\", subplot=2)\n",
    "plot!(x, 0*x, color=:black, lw=2, label=\"\", subplot=2)\n",
    "title!(\"Caso 3\", subplot=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ou seja, ao avaliarmos $f(x)$ conseguimos no mínimo melhorar a aproximação obtida, obtendo a cada passo um intervalo cada vez menor, dividindo o seu tamanho por 2. Note que o ponto médio do intervalo está à distância máxima de $\\frac{b - a}{2}$ de uma raiz real do problema, já que existe raiz no intervalo. Dessa forma é natural parar o método quando a largura do intervalo for pequena o suficiente para aceitar o ponto médio como uma boa aproximação da raiz.\n",
    "\n",
    "Isso sugere o seguinte método:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Método da bisseccao\n",
    "function bisseccao(f, a, b, epsilon=1.0e-5)\n",
    "    # Recebe a função f e os extremos de um intervalo [a, b] tal que f(a)f(b) < 0.\n",
    "    # Para quando b - a < 1.0e-5.\n",
    "    \n",
    "    iter = 0\n",
    "    while b - a >= epsilon\n",
    "        medio = (a + b)/2.0\n",
    "        println(\"$iter: $medio\")\n",
    "        if f(medio)*f(a) > 0.0\n",
    "            a = medio\n",
    "        else\n",
    "            b = medio\n",
    "        end\n",
    "        iter += 1\n",
    "    end\n",
    "    \n",
    "    medio = (a + b)/2.0\n",
    "    println(\"$iter: $medio\")\n",
    "    return medio\n",
    "end\n",
    "\n",
    "# Testa primeiro com a função do gráfico.\n",
    "println(\"Bissecção na função do gráfico:\")\n",
    "raiz = bisseccao(f, 1.5, 2.0)\n",
    "@show f(raiz)\n",
    "\n",
    "# Agora resolve o problema do início do texto.\n",
    "v0 = 12\n",
    "d = 10\n",
    "g = 9.80665\n",
    "\n",
    "println(\"\\nProblema balístico\\n\")\n",
    "impacto(θ) = 2.0*v0^2*sin(θ)*cos(θ) - g*d\n",
    "println(\"Intervalo onde a função troca de sinal\\n\")\n",
    "@show impacto(π/10)\n",
    "@show impacto(π/4)\n",
    "println(\"\\nBissecção para o problema balístico:\")\n",
    "raiz = bisseccao(impacto, π/10, π/4)\n",
    "@show impacto(raiz); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uma característica interessante do método da bissecção é que ele pede usa apenas os valores da função em alguns pontos para decidir o que fazer. Além disso o seu comportamento é bem previsível. O comprimento do intervalo é dividido por 2 a cada iteração. Assim podemos prever quantas iterações serão necessárias para terminar o método como função do comprimento inicial e da precisão, `epsilon`, desejada. Isso fica como exercício. \n",
    "\n",
    "Como foi possível ver acima essa convergência ainda é um pouco lenta. Vamos estudar as seguir um outro método com comportamento, em geral, bem mais rápido.\n",
    "\n",
    "## O método de Newton\n",
    "\n",
    "O método da bissecção tem algumas vantagens interessantes. Em primeiro lugar sua convergência é garantida, já que a cada passo a distância a uma raiz é divida por dois, indo, naturalmente, para zero. Uma segunda vantagem é a possibilidade de estimar a priori o número de iterações necessárias para se obter a precisão desejada. Por fim, ele pode ser implementado somente usando informação sobre o cômputo da função.\n",
    "\n",
    "Vamos agora estudar um outro método que usa mais informação, além dos simples valores funcionais. Se $f$ for diferenciável, podemos aproveitar informação sobre a sua derivada para obter um algoritmo extremamente rápido em vários casos. A ideia fundamental é lembrar que quando $f$ é diferenciável sabemos aproximar a função localmente por uma função linear, usando sua expansão de Taylor de primeira ordem.\n",
    "$$\n",
    "f(y) \\approx f(x) + f'(x)(y - x).\n",
    "$$\n",
    "Agora, imagine que o ponto já conhecido, $x_k$, está próximo de uma raiz, de modo que a aproximação de Taylor apresentada acima é muito boa para prever o comportamento de $f$ de $x_k$ até essa raiz. Podemos então pensar em substituir $f$ por sua aproximação linear, achar a raiz da aproximação e tomá-la como nova estimativa da raiz original. Ou seja queremos encontrar $x_{k + 1}$ tal que\n",
    "$$\n",
    "f(x_k) + f'(x_k)(x_{k+1} - x_k) = 0.\n",
    "$$\n",
    "É fácil ver que a nova estimativa é dada por\n",
    "$$\n",
    "x_{k + 1} = x_k - \\frac{f(x_k)}{f'(x_k)}.\n",
    "$$\n",
    "Veja o gráfico abaixo para ter uma ideia do que está ocorrendo. Nela o ponto $x_k = -1/2$ e a aproximação linear da curva azul é a reta verde. O ponto $x_{k + 1}$ é então ponto em que a aproximação linear cruza o eixo $x$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f(x) = sin(x + 1.0)*cos(x)\n",
    "df(x) = cos(x)*cos(x + 1.0) - sin(x)*sin(x + 1.0)\n",
    "x = LinRange(-2.0, 0.0, 100)\n",
    "plot(x, f.(x), lw=2, label=L\"f\")\n",
    "plot!(x, 0*x, color=:black, lw=2, label=\"\", legend=:topleft)\n",
    "\n",
    "# Apresenta o modelo linear em torno de xk\n",
    "xk = -0.5\n",
    "linearmodel(x) = f(xk) + df(xk)*(x - xk)\n",
    "plot!(x, linearmodel.(x), lw=2, label=\"modelo linear\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O método de Newton tem, tipicamente, convergência extremamente rápida sempre que o ponto inicial é uma boa aproximação da solução desejada. Um primeiro exemplo disso, que vamos explorar, é pensar nesse método sendo usado para calcular a raiz quadrada de um número. O problema de calular a raiz de um número $a > 0$ dado pode ser visto como o problema de resolver a equação\n",
    "$$\n",
    "f(x) = x^2 - a = 0.\n",
    "$$\n",
    "Nesse caso é muito fácil calcular a derivada. Assim, a iteração\n",
    "$$\n",
    "x_{k + 1} = x_k - \\frac{f(x_k)}{f'(x_k)}\n",
    "$$\n",
    "pode ser escrita como \n",
    "$$\n",
    "x_{k + 1} = x_k - \\frac{x_k^2 - a}{2 x_k} = \\frac{1}{2}\\left(x_k + \\frac{a}{x_k} \\right).\n",
    "$$\n",
    "Vamos implementar esse algoritmo e tentar calcular $\\sqrt{10}$ partindo de $x_0 = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 10\n",
    "xk = 1\n",
    "prec = 1.0e-14\n",
    "\n",
    "iters = 0\n",
    "println(iters, \": \", xk)\n",
    "while abs((xk*xk - a)/a) > prec\n",
    "    xk = 0.5*(xk + a/xk)\n",
    "    iters += 1\n",
    "    println(iters, \": \", xk)\n",
    "end\n",
    "println(\"\\nValor 'exato'= \", sqrt(a))\n",
    "println(\"xk*xk        = \", xk*xk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note que a convergência ocorre de forma extremamente rápida. Na iteração 2, o número já foi calculado com 1 casa correta, na próxima iteração o número de casa corretas já duplicou passando para 2, depois para 4, depois para 8 casas e por fim 15. Ou seja, o número de casas corretas dobrou aproximadamente por iteração. \n",
    "\n",
    "Para entender porque isso ocorre vamos lembrar o que nos diz o teorema de Taylor se $f$ for $n + 1$ vezes diferenciável.\n",
    "\n",
    "**Teorema de Taylor**. Seja $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ diferenciável $n + 1$ vezes em um intervalo que contenha os valores $x$ e $y$. Então existe $\\xi$ no intervalo aberto que une $x$ e $y$ tal que\n",
    "$$\n",
    "f(y) = f(x) + f'(x)(y - x) + \\frac{f''(x)}{2}(y - x)^2 + \\ldots + \\frac{f^{(n)}(x)}{n!}(y - x)^n + \\frac{f^{(n+1)}(\\xi)}{(n + 1)!}(y - x)^n.\n",
    "$$\n",
    "\n",
    "De posse desse resultado podemos provar que\n",
    "\n",
    "**Teorema (da Convergência Quadrática de Newton)**. Seja $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ uma função duas vezes continuamente diferenciável. Se $x_0$ inicia perto de uma raiz $x^*$ onde a derivada de $f$ é não nula, então o método de Newton está bem definido e gera uma sequência convergindo para $x^*$. Além disso, existe $M > 0$ tal que\n",
    "$$\n",
    "| x_{k+1} - x^* | \\leq M | x_k - x^* |^2.\n",
    "$$\n",
    "\n",
    "**Prova.** Usando o teorema de Taylor, com $x = x_k$ e $y = x^*$, temos\n",
    "\\begin{align*}\n",
    "| x_{k+1} - x^* | &= | x_k - f(x_k)/f'(x_k) - x^* | \\\\\n",
    "                  &= \\left| x_k + \\left(x^* - x_k + \\frac{f''(\\xi_k)}{2 f'(x_k)}(x^* - x_k)^2 \\right)- x^* \\right| \\\\\n",
    "                  &= \\left| \\frac{f''(\\xi_k)}{2 f'(x_k)} \\right| | x_k - x^* |^2,\n",
    "\\end{align*}\n",
    "em que $\\xi_k$ está no intervalo que une $x_k$ e $x_*$.\n",
    "\n",
    "Por outro lado podemos deduzir alguns limitantes interessantes, se fizermos hipóteses sobre a distância de $x_k$ até $x^*$.\n",
    "\n",
    "1. Sabemos que |f''(x)| atinge máximo no intervalo $[x^* - 1, x^* + 1]$. Chamemos o valor de máximo de $m$. Temos então que se $| x_k - x_* | \\leq 1$ teremos $|f''(\\xi_k)| \\leq m$ para todo $\\xi_k$ no intervalo que une $x_k$ e $x_*$.\n",
    "\n",
    "1. Como $f'(x^*) \\neq 0$, sabemos que para pontos suficientemente próximos de $x_*$, $|f'(x)| \\geq |f'(x^*)|/2 > 0$. Isto é, existe $\\delta_1 > 0$ tal que se $| x - x^* | \\leq \\delta_1$ então $|f'(x)| \\geq |f'(x^*)|/2$.\n",
    "\n",
    "Assim, se $| x_k - x_* | < \\min(1, \\delta_1)$, teremos \n",
    "$$\n",
    "|x_{k+1} - x^*| \\leq \\frac{2m}{f'(x^*)} |x_k - x^*| |x_k - x^*|.\n",
    "$$\n",
    "Portanto, se definirmos $\\delta = \\min(1, \\delta_1, f'(x^*)/(4m))$ e $| x_k - x_* | < \\delta$, teremos\n",
    "$$\n",
    "|x_{k+1} - x^*| \\leq \\frac{1}{2} |x_k - x^*|.\n",
    "$$\n",
    "Concluímos, então, que nesse caso a sequência converge a $x^*$ e todas as propriedades obtidas continuam valendo. Portando, se $| x _0 - x^* | \\leq \\delta$, podemos concluir que:\n",
    "\n",
    "1. Toda a sequência se mantem a essa distância máxima de $x^*$.\n",
    "\n",
    "1. Em toda a sequência, a derivada $f'(x_k)$ tem módulo maior ou igual a $|f'(x^*)|/2$, portando é sempre não nula e o método está bem definido.\n",
    "\n",
    "1. Por fim, chamando de $M = \\frac{2m}{f'(x^*)}$, teremos\n",
    "$$\n",
    "| x_{k+1} - x^* | \\leq M | x_k - x^* |^2.\n",
    "$$\n",
    "$\\blacksquare$\n",
    "\n",
    "O fato da distância à solução, uma vez que cai abaixo de $1$, diminuir elevando o valor anterior ao quadrado explica o comportamento observado no exemplo, com o número de casas decimais corretas duplicando a cada iteração.\n",
    "\n",
    "Um fato importante é que o teorema acima só garante a convergência quando o ponto inicial $x_0$ estiver perto de uma raiz com derivada não nula. Caso contrário, não há garantias para a convergência, em particular se o ponto inicial estiver longe das raízes. De fato, a convergência pode falhar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f(x) = atan(x)\n",
    "df(x) = 1 / (x^2 + 1)\n",
    "x0 = 1.5\n",
    "n = 2\n",
    "\n",
    "# Cria o gráfico inicial da função\n",
    "x_range = LinRange(-5.5, 3.5, 100)\n",
    "p = plot(f, x_range, lw=3, legend=:false, size=(400, 300))\n",
    "hline!([0.0], c=:black)\n",
    "\n",
    "xk = x0\n",
    "for i in 0:2\n",
    "    # Marca o ponto corrente\n",
    "    scatter!([xk], [0], c=:green, annotate=(xk, -0.15, L\"x_{%$i}\", 10))\n",
    "\n",
    "    # Calcula a função e a derivada\n",
    "    val, deriv = f(xk), df(xk)\n",
    "\n",
    "    # Desenha uma linha vertical de (x, 0) a (x, f(x))\n",
    "    plot!([xk, xk], [0, val], c=:gray)\n",
    "\n",
    "    # Marca o ponto (x, f(x))\n",
    "    scatter!([xk], [val], c=:red)\n",
    "\n",
    "    # Modelo da linha tangente\n",
    "    linearmodel(x) = val + deriv*(x - xk)\n",
    "\n",
    "    # Passo de Newton\n",
    "    xkp1 = xk - val / deriv\n",
    "    \n",
    "    # Desenho da linha tangente\n",
    "    plot!([xk, xkp1], linearmodel.([xk, xkp1]), c=:blue, ls=:dash, lw=2)\n",
    "    xk = xkp1\n",
    "end\n",
    "# Ponto corrente\n",
    "scatter!([xk], [0], c=:green, annotate=(xk, -0.15, L\"x_{%$n}\", 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Colocar um exemplo de divergência baseado em uma função sigmóide.**\n",
    "\n",
    "Existem algumas alternativas para se obter um método que convirja a partir de qualquer ponto inicial (globalização do método):\n",
    "\n",
    "* Começar com outro método com covergência garantida.\n",
    "\n",
    "* Fazer algum tipo de busca no passo de Newton para forçar $| f(x_{k+1}) |$ a diminuir, encurtando o passo quando necessário (busca linear)\n",
    "\n",
    "* Região de confiança.\n",
    "\n",
    "Outro problema que também pode ocorrer é encontrar um ponto de derivada nula (ou de derivada muito pequena). Esse tipo de situação pode também ser resolvido com estratégias parecidas com as  estratégias descritas acima.\n",
    "\n",
    "* Usar a derivada no ponto anterior.\n",
    "\n",
    "* Usar uma iteração de outro algoritmo.\n",
    "\n",
    "## Critério de parada\n",
    "\n",
    "Idealmente desejamos parar o método quando o erro $e_k = |x_k - x^*|$ for pequeno. Mas não conhecemos $x^*$, ele é exatamente que desejamos encontrar. \n",
    "\n",
    "Uma alternativa seria usar o próprio valor de $| f(x_k) |$. A expectativa é que quando esse valor for pequeno podemos esperar que $e_k$ seja pequeno. De fato usando a expansão de Taylor temos\n",
    "\\begin{gather*}\n",
    "f(x_k) \\approx f(x^*) - f'(x^*)(x_k - x^*) \\implies \\\\\n",
    "e_k \\approx | f(x_k) | / | f'(x^*) |.\n",
    "\\end{gather*}\n",
    "\n",
    "Assim, vemos que se $| f(x_k) |$ é pequeno esperamos que o erro $e_k$ seja pequeno. Note que essa relação depende também do valor de $|f'(x^*)|$. Se esse valor for pequeno, é necessário que $| f(x^k) |$ seja muito pequeno para $e_k$ também o seja e vice-versa. Faça alguns gráficos para se convencer disso.\n",
    "\n",
    "Outra possibilidade é parar o método quando o tamanho do último passo dado $s_{k + 1}  = x_{k + 1} - x_k$ se tornar muito pequeno, ou seja quando o método já está \"quase parando\".\n",
    "\n",
    "Estamos agora prontos para apresentar uma implementação do método de Newton. Nela, vamos supor que o ponto inicial está perto de uma raiz e que as derivadas encontradas são sempre não nulas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Método de Newton simples para resolução de equações não lineares\n",
    "function newton_eq(f, df, x, epsilon=1.0e-5, maxiters=100)\n",
    "\n",
    "    iter = 0\n",
    "    while iter < maxiters && abs(f(x)) > epsilon\n",
    "        println(iter, \": \", x)\n",
    "        x -= f(x)/df(x)\n",
    "        iter += 1\n",
    "    end\n",
    "\n",
    "    println(iter, \": \", x)\n",
    "    return x\n",
    "end\n",
    "\n",
    "dimpacto(θ) = 2*v0^2*cos(2.0.*θ)\n",
    "\n",
    "raiz = newton_eq(impacto, dimpacto, π, 1.0e-10)\n",
    "@show impacto(raiz);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare a velocidade de convergência do método da bissecção apresentado acima. Note também que a solução final obtida é bem mais precisa.\n",
    "\n",
    "### Taxas de convergência\n",
    "\n",
    "É interessante observar a velocidade de convergência estimada para o método de Newton e compará-la para o caso de bissecção.\n",
    "\n",
    "No caso da bissecção o método é construido para garantir que de uma interessão para outra o erro caia pelo menos pela metade. Ou seja temos que $e_k = | x_k - x_* | $.\n",
    "$$\n",
    "e_{k + 1} \\leq \\frac{1}{2} e_k.\n",
    "$$\n",
    "Isso garante que o erro de aproximação diminui à taxa constante a cada iteração. Quando o erro cai dessa forma dizemos que a convergência é *linear* (com constante $\\frac{1}{2}$). Isso garante que $e_k \\rightarrow 0$. Note que o mesmo ocorreria se a constante fosse qualquer número $\\alpha < 1$ no lugar de $\\frac{1}{2}$. Nesse caso dizemos que o método converge de forma linear com constante $\\alpha$. \n",
    "\n",
    "No caso do método de Newton a fórmula obtida foi\n",
    "$$\n",
    "e_{k + 1} \\leq M e_k^2 = (M e_k) e_k.\n",
    "$$\n",
    "Como também provamos que o método é convergente, ou seja que $e_k \\rightarrow 0$, vemos que a partir de uma certa iteração $M e_k < \\frac{1}{2}$. Portanto, a partir de um certo ponto, o método de Newton passa a ficar mais rápido do que a bissecção. Mais do que isso, já na próxima iteração a diferença de velocidade é maior, depois maior ainda e assim por diante. Ou seja, com as iterações o método de Newton vai ficando \"infinitamente\" mais rápido do que a bissecção. Isso é capturado pela equação\n",
    "$$\n",
    "\\lim_{k \\rightarrow \\infty} \\frac{e_{k+1}}{e_k} = 0.\n",
    "$$\n",
    "O que ela diz é que a medida que o tempo passa o método fica melhor do que a convergência linear com qualquer constante $\\alpha$ fixada. Dizemos que um método cujos erros obedecem à equação acima tem convergência é super linear. O caso do método de Newton é mais específico, pois sabemos que a constante vai para zero na mesma velocidade que $e_k$. Nesse caso chamamos a convergência de quadrática.\n",
    "\n",
    "## Método secante\n",
    "\n",
    "Vimos que o método de Newton para resolução de equações não-lineares é uma ótima alternativa. De fato, ele atinge alta precisão rapidamente, superando o método da bissecção na maioria dos casos. Porém, para utilizá-lo é necessário saber calcular não somente a função $f$ mas também sua derivada $f'$ e há situações em que o calculo da derivada pode ser difícil, mesmo quando a função é diferenciável. Um exemplo é quando a função é calculada por uma simulação numérica ou quando apenas temos acesso a ela através de um programa de computador sem acesso ao código (dizemos que ele é uma caixa preta). Além disso, o esforço computacional necessário pelo método de Newton, que exige um cômputo de $f$ e sua derivada a cada passo, é maior do que o esforço exigido pela bissecção que calcula apenas a função. \n",
    "\n",
    "Uma alternativa nessa situação é recordar a definição de derivada\n",
    "$$\n",
    "f'(x) = \\lim_{h \\rightarrow 0} \\frac{f(x + h) - f(x)}{h}.\n",
    "$$ \n",
    "\n",
    "Essa definição nos dá uma informação interessante: se temos dois pontos próximos $x$ e $y$, podemos aproximar a derivada de $f$ em $x$ por\n",
    "$$\n",
    "f'(x) \\approx \\frac{f(y) - f(x)}{y - x}.\n",
    "$$\n",
    "\n",
    "Será que podemos usar isso para gerar um algoritmo iterativo que aproxime o comportamento do método de Newton sem que haja a necessidade de calcular derivadas explicitamente? Vejamos. Um método iterativo que gera uma sequência $x_k$ que converge para uma raiz $x_*$ terá os iterados consecutivos, $x_{k - 1}$ e $x_{k},$  cada vez mais próximos. Isso ocorre porque eles estão se aproximando do mesmo ponto $x_*$ a medida que $k$ aumenta. Assim, a discussão acima sugere que\n",
    "$$\n",
    "f'(x_k) \\approx \\frac{f(x_{k - 1}) - f(x_k)}{x_{k -1} - x_k}.\n",
    "$$\n",
    "Lembrando a dedução do método de Newton temos\n",
    "$$\n",
    "f(x) \\approx f(x_k) + f'(x_k)(x - x_k) \\approx f(x_k) + \\frac{f(x_{k-1}) - f(x_k)}{x_{k -1} - x_k} (x - x_k).\n",
    "$$\n",
    "A expressão mais da direita é também uma aproximação afim de $f$ próximo a $x_k$. Assim, da mesma forma que vimos em Newton, podemos definir um método iterativo definindo como novo ponto $x_{k + 1}$ a raiz dessa equação afim. Isso nos leva a fórmula do *método Secante*.\n",
    "$$\n",
    "x_{k+1} = x_k - \\frac{f(x_k)(x_{k - 1} - x_k)}{f(x_{k - 1}) - f(x_k)}.\n",
    "$$\n",
    "A sua implementação é muito semelhante a do método de Newton, vamos fazê-la a seguir a executar um teste para ver o quão rápido é esse método para calcular o momento de impacto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Método Secante simples para resolução de equações não lineares. \n",
    "# Note que ele precisa de dois pontos iniciais x0 e x1.\n",
    "function secante(f, x0, x1, epsilon=1.0e-5, maxiters=100)\n",
    "\n",
    "    xant = x0\n",
    "    fant = f(xant)\n",
    "    println(0, \": \", x0)\n",
    "    x = x1\n",
    "    fx = f(x)\n",
    "    iter = 1\n",
    "    while iter < maxiters && abs(fx) > epsilon\n",
    "        println(iter, \": \", x)\n",
    "        df = (fant - fx) / (xant - x)\n",
    "        xant = x\n",
    "        x -= fx/df\n",
    "        fant = fx\n",
    "        fx = f(x)\n",
    "        iter += 1\n",
    "    end\n",
    "\n",
    "    println(iter, \": \", x)\n",
    "    return x\n",
    "end\n",
    "\n",
    "raiz = secante(impacto, π - 0.1, π, 1.0e-10);\n",
    "@show impacto(raiz)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vemos nesse exemplo que o método secante também pode convergir rapidamente, realizando apenas duas iterações a mais do que o método de Newton. De fato, pode-se provar os seguinte resultado de convergência.\n",
    "\n",
    "**Teorema (da Convergência Superlinear do método secante)**. Seja $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ uma função duas vezes continuamente diferenciável. Se $x_0$ inicia perto de uma raiz $x^*$ onde a derivada de $f$ é não nula, então o método secante está bem definido e gera uma sequência convergindo para $x^*$. Além disso, \n",
    "$$\n",
    "\\lim_{k \\rightarrow \\infty} \\frac{| x_{k+1} - x^* |}{| x_k - x^* |} = 0.\n",
    "$$\n",
    "\n",
    "Uma análise atenta do limite acima mostra que o método secante vai também ficando cada vez mais rápido, ganhando de qualquer método com convergência linear, daí chamarmos esse tipo de convergência de superlinear. \n",
    "\n",
    "## Método de Newton para Sistemas Não-Lineares\n",
    "\n",
    "O método de Newton admite uma generalização direta para resolver sistemas de equações não-lineares. Nesse caso, temos uma função $F: \\mathbb{R}^n \\rightarrow \\mathbb{R}^n$ e queremos resolver $F(x) = 0,\\ x \\in \\mathbb{R}^n$. Em outras palavras, queremos encontrar $x_1, x_2, \\ldots, x_n \\in \\mathbb{R}^n$ tais que\n",
    "\\begin{align*}\n",
    "f_1(x_1, x_2, \\ldots, x_n) &= 0 \\\\\n",
    "f_2(x_1, x_2, \\ldots, x_n) &= 0 \\\\\n",
    "\\quad\\quad\\quad\\vdots &\\\\\n",
    "f_n(x_1, x_2, \\ldots, x_n) &= 0,\n",
    "\\end{align*}\n",
    "em que $F(x) = (f_1(x), f_2(x), \\ldots, f_n(x))$.\n",
    "\n",
    "Para isso, podemos usar resultados de cálculo 2. Lembremos que cada função $f_i: \\mathbb{R}^n \\rightarrow R$ admite uma aproximação linear\n",
    "$$\n",
    "f_i(y) \\approx f_i(x) + \\nabla f_i(x)'(y - x),\\ i = 1, \\ldots, n,\n",
    "$$\n",
    "em que $\\nabla f(x)$ é o gradiente de $f_i$ em $x$. Podemos escrever todas essas equações de forma compacta usando a definição da matriz jacobiana de $F$. Ela é composta por linhas com os gradientes:\n",
    "$$\n",
    "JF(x) = \\left[ \\begin{array}{c}\n",
    "\\nabla f_1(x_1, x_2, \\ldots, x_n))' \\\\\n",
    "\\nabla f_s(x_1, x_2, \\ldots, x_n))' \\\\\n",
    "\\vdots \\\\\n",
    "\\nabla f_n(x_1, x_2, \\ldots, x_n))' \n",
    "\\end{array} \\right].\n",
    "$$\n",
    "Nesse caso, escrevemos\n",
    "$$\n",
    "F(y) \\approx F(x) + JF(x)(y - x).\n",
    "$$\n",
    "\n",
    "Podemos então aplicar as mesmas ideias que nos levaram a deduzir o método de Newton. Queremos resolver\n",
    "$$\n",
    "F(x) = 0.\n",
    "$$\n",
    "Já temos uma aproximação da solução $x^k$ e queremos melhorá-la. Uma ideia é então substituir a função não-linear $F$ por sua aproximação linear calculada nesse último ponto e usar o seu zero como nova aproximação. Isto é, queremos resolver\n",
    "$$\n",
    "F(x^{k + 1}) \\approx F(x^k) + JF(x^k)(x^{k + 1} - x^k) = 0.\n",
    "$$\n",
    "Isolando $x^{k + 1}$, que pode ser feito se o jacobiano for inversível, obtemos\n",
    "$$\n",
    "x^{k +1} = x^k - JF(x^k)^{-1}F(x^k).\n",
    "$$\n",
    "Uma clara generalização da equação que define o método de Newton no caso unidmensional. \n",
    "\n",
    "Uma observação importante é que, apesar da fórmula acima sugerir que devemos inicialmente inverter a matriz jacobiana, não há necessidade de inverter nenhuma matriz, o que exigiria a soluçào de $n$ sistemas lineares gerando uma complexidade total de $O(n ^4)$. Basta resolver inicialmente um único sistema\n",
    "$$\n",
    "JF(x^k)s^{k + 1} = -F(x^k)\n",
    "$$ \n",
    "e em seguida atualizar\n",
    "$$\n",
    "x^{k + 1} = x^{k} + s^{k + 1}.\n",
    "$$\n",
    "Se o jacobiano for inversível, claramente, esses dois passos são equivalentes à fórmula do método de Newton dada acima.\n",
    "\n",
    "Vejamos um exemplo. Se quisermos resolver\n",
    "$$\n",
    "F(x) = \\left[ \\begin{array}{c} \n",
    "    x_1^2 - e^{-x_1 x_2} \\\\\n",
    "    x_1x_2 + \\sin(x_1)\n",
    "    \\end{array} \\right] = 0.\n",
    "$$\n",
    "Temos\n",
    "$$\n",
    "JF(x) = \\left[ \\begin{array}{cc}\n",
    "    2x_1 + x_2e^{-x_1 x_2} & x_1 e^{-x_1 x_2} \\\\\n",
    "    x_2 + \\cos(x_1)        & x_1\n",
    "\\end{array} \\right].\n",
    "$$\n",
    "Vamos implementar o método de Newton e testá-lo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "using LinearAlgebra\n",
    "\n",
    "# Método de Newton simples para resolução de equações não lineares\n",
    "function newton(F, JF, x, epsilon=1.0e-5, maxiters=100)\n",
    "\n",
    "    iter = 0\n",
    "    while iter < maxiters && norm(F(x), Inf) > epsilon\n",
    "        println(iter, \": \", norm(F(x), Inf))\n",
    "        s =  -JF(x)\\F(x)     # Em Julia isso devolve em s a solução do sistema JF(x)s = -F(x)\n",
    "        x += s\n",
    "        iter += 1\n",
    "    end\n",
    "\n",
    "    println(iter, \": \", norm(F(x), Inf))\n",
    "    return x\n",
    "end\n",
    "\n",
    "F(x) = [x[1]^2 - exp(-x[1]*x[2]), x[1]*x[2] + sin(x[1])]\n",
    "JF(x) = [[2*x[1] + x[2]*exp(-x[1]*x[2]), x[2] + cos(x[1])] [x[1]*exp(-x[1]*x[2]), x[1]]] \n",
    "x0 = [2.0, 1.0]\n",
    "raiz = newton(F, JF, x0)\n",
    "@show F(raiz)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note que temos aqui o mesmo problema para determinar o momento ideal de parada. Assim como no método de Newton para equações, podemos usar a norma de $F(x)$ para definir quando o ponto está perto da solução. A justificativa para isso é continuidade. Uma justificativa mais formal pode ser obtida usando a expansão de Taylor em torno da solução $x^*$, assim como foi feito no método para uma variável. Outras opções de critério de parada que são muito usadas na prática são:\n",
    "\\begin{gather}\n",
    "\\| F(x) \\| \\leq \\epsilon \\| F(x^0) \\| \\\\\n",
    "\\| F(x) \\| \\leq \\epsilon_0 \\| F(x^0) \\| + \\epsilon_1 \\\\\n",
    "\\| s^k \\| \\leq \\epsilon.\n",
    "\\end{gather}\n",
    "\n",
    "Precisamos também destacar que a operação mais cara em cada iteração do método de Newton é a resolução do sistema linear para cômputo do passo. Isso pode ser feito com os métodos que estudamos antes, como a fatoração LU. Em alguns casos, principalmente quando as matrizes envolvidas são grandes e esparsas, pode ser interessante usar um método iterativo para achar o passo de Newton. Nesse caso o passo não é calculado exatamente, apenas uma aproximação é obtida. Se a aproximação obtida for boa, o método se comporta muitas vezes bem e é conhecido como Newton *inexato* ou *truncado*. \n",
    "\n",
    "Outro problema de do método de Newton para equações unidimensionais que também ocorre com o caso multidimensional é que a convergência não é garantida se o ponto inicial não estiver próximo de um zero onde a matriz Jacobiana é inversível. O resultado típico de convergência é muito parecido com o resultado para uma dimensão apenas.\n",
    "\n",
    "**Teorema (da Convergência Quadrática de Newton).** Seja $F:\\mathbb{R}^n \\rightarrow \\mathbb{R^n}$ uma função duas vezes continuamente diferenciável. Se $x^0$ inicia perto de uma raiz $x^*$ para a qual a matriz jacobiana de $F$ é inversível, então o método de Newton está bem definido e gera uma sequência convergindo para $x^*$. Além disso, existe $M > 0$  tal que\n",
    "$$\n",
    "\\|x^{k+1}−x^∗\\| \\leq M \\|x^k−x^∗\\|^2.\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.2",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.6.2"
  },
  "latex_metadata": {
   "title": "Equações e sistemas não lineares"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}