08_Problemas_de_Valor_Inicial.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Pacotes usados nesse caderno\n",
    "using Printf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Equações diferenciais - problemas de valor inicial\n",
    "\n",
    "Equações diferenciais são expressões que nos dão informações sobre o comportamento da derivada de uma função. O nosso objetivo é então encontrar uma função cujas derivadas obedeçam à equação. Vejamos alguns exemplos:\n",
    "\n",
    "* $y'(t) = 2t$. Nesse caso é fácil ver que $y(t) = t^2 + c$ é uma possível solução para qualquer constante $c$ real escolhida. Nesse curso as funções vão tipicamente ter um único argumento que será denotado por $t$ já que, tipicamente, ele representa a passagem do tempo e a equação busca representar a dinâmica de um fenômeno (com respeito ao tempo).\n",
    "\n",
    "* $u' = u$. Note que aqui deixamos de colocar explicitamente a variável da função, $t$. Isso deixa a notação mais próxima da notação de equações numéricas usuais e pode ser feito sempre que essa omissão não causar dúvidas. Nesse caso também é possível obter soluções lembrando de uma das derivadas fundamentais: $u(t) = ce^t$. Note que mais uma vez é possível escolher qualquer constante $c \\in\\mathbb{R}$.\n",
    "\n",
    "* $v'' + v = 0$. Nesse caso a obtenção de uma solução não é tão simples. Observe também que a equação diferencial envolve a derivada segunda. Possíveis soluções têm a forma $v(t) = \\alpha \\cos(t) + \\beta \\sin(t)$ para quaisquer constantes $\\alpha \\beta \\in \\mathbb{R}$.\n",
    "\n",
    "* $y''y + (y')^2 = 1 + 2t$. De novo uma equação difícil, agora envolvendo $y, y'$ e $y''$. Possíveis soluções têm a forma $y(t) = \\ln | c_1 + c_2 t + t^2/2 + t^3/3 |$, com constantes reais $c_1, c_2 \\in \\mathbb{R}$. \n",
    "\n",
    "Uma primeira observação sobre as equações acima é que elas não definem completamente a resposta. Veja que em todos os casos há um parâmetro, ou mais, que pode ser escolhido. Isso está ligado ao teorema fundamental do cálculo. Ele diz que a primitiva de uma função não está completamente determinada, já que sempre podemos somar uma constante na resposta. Para conseguir definir completamente a resposta é necessário dar mais informação além da equação. Muitas vezes essa informação extra nos informa qual o valor da função em um ponto de partida, que chamamos valor inicial.\n",
    "\n",
    "## Problema de valor inicial\n",
    "\n",
    "Um problema de valor inicial é composto por uma equação diferencial e do estabelecimento do valor das funções desejadas em um instante inicial que denotamos abaixo por $t_0$. Formalmente um problema de valor inicial (PVI) é definido pelas equações\n",
    "$$\\begin{split}\n",
    "y'(t) &= f(t, y(t)),\\quad t > t_0 \\\\\n",
    "y(t_0) &= y_0,\n",
    "\\end{split}$$\n",
    "em que $y: \\mathbb{R} \\rightarrow \\mathbb{R}$, $f: \\mathbb{R} \\times \\mathbb{R} \\rightarrow \\mathbb{R}$ e $t_0, y_0$ são constantes reais.\n",
    "\n",
    "Nesse caso, além da equação diferencial, definimos o valor da função desejada em um tempo (argumento) inicial. Daí o seu nome. Vejamos o que ocorre se definirmos valores iniciais nos dois primeiros exemplos acima.\n",
    "\n",
    "* $y'(t) = 2t,\\ y(0) = 5$. Nesse caso, se partimos da forma que já conhecemos para a solução, teremos $y(t) = t^2 + c$ para algum $c \\in\\mathbb{R}$. Já a condição inicial diz que $5 = y(0) = 0^2 + c = c$. Assim, a solução fica completamente determinada. $y(t) = t^2 + 5$.\n",
    "\n",
    "* $u' = u,\\ u(1) = 2$. De novo temos da forma geral da solução $u(t) = ce^t$, em que que $2 = u(1) = ce^2$. Portanto $c = 2/e^2$ e a solução será $u(t) = 2e^{t - 2}$.\n",
    "\n",
    "É possível provar que problemas de valor inicial possuem solução única sob hipóteses bastantes gerais.\n",
    "\n",
    "#### Teorema (existência e unicidade de soluções para PVI). \n",
    "Considere o PVI e um \"retângulo\" no $\\mathbb{R}^2$, $R = [a, b] \\times [c, d]$ tais que\n",
    "* $f$ é contínua em $R$.\n",
    "* $f$ é Lipschitz contínua com respeito à sua segunda variável em $R$, isto é\n",
    "\n",
    "$$\\exists L, |(f(t, y_1) - f(t, y_2)| \\leq L |y_1 - y_2|,\\quad \\forall y_1, y_2 \\in [c, d].$$\n",
    "\n",
    "* $(t_0, y_0) \\in (a, b) \\times (c, d)$.\n",
    "\n",
    "Então, existe $\\delta > 0$ tal que o PVI tem solução única para $t \\in [t_0 - \\delta, t_0 + \\delta]$.\n",
    "\n",
    "Esse teorema garante, por exemplo, que as soluções encontradas acima para os exemplos de problemas de valor inicial são únicas.\n",
    "\n",
    "Já um PVI baseado na equação diferencial\n",
    "\n",
    "$$y' = 2t + \\ln(y),$$\n",
    "\n",
    "não satisfaz as hipóteses do teorema para qualquer retângulo que contenha o zero na segunda coordenada. Isso porque nesse caso a função $f(t, y) = 2t + \\ln(y)$ não é Lipschitz contínua.\n",
    "\n",
    "## Estendendo para além de $\\mathbb{R}$\n",
    "\n",
    "Nossa definição do PVI considerou que a função que desejamos \n",
    "$y: \\mathbb{R} \\rightarrow \\mathbb{R}$. Mas isso não é realmente necessário. Ela também pode ser uma função a valores vetoriais. Isto é, podemos pensar em um problema de valor inicial que procura uma função $y: \\mathbb{R} \\rightarrow \\mathbb{R}^n$, por exemplo, descrevendo uma trajetória de um corpo se movendo no espaço tridimensional ($n = 3$). De uma forma geral vamos considerar o problema de valor inicial PVI\n",
    "$$\\begin{split}\n",
    "y'(t) &= f(t, y(t)),\\quad t > t_0 \\\\\n",
    "y(t_0) &= y_0,\n",
    "\\end{split}$$\n",
    "em que $y: \\mathbb{R} \\rightarrow \\mathbb{R}^n$, $f: \\mathbb{R} \\times \\mathbb{R}^n \\rightarrow \\mathbb{R}^n$ e $t_0$, $y_0 \\in \\mathbb{R}^n$ são valores pré-definidos.\n",
    "\n",
    "#### Exemplo\n",
    "\n",
    "$$y'(t) \\equiv\n",
    "\\left( \\begin{array}{c}\n",
    "y_1'(t) \\\\\n",
    "y_2'(t) \\\\\n",
    "\\end{array} \\right)\n",
    "\\left( \\begin{array}{c}\n",
    "3y_1 - t^2y_2 \\\\\n",
    "(1 - t)^2y_2 \\\\\n",
    "\\end{array} \\right)\n",
    "\\equiv\n",
    "f(t, y),\n",
    "$$\n",
    "em que\n",
    "$$\n",
    "y(1) = \n",
    "\\left( \\begin{array}{c}\n",
    "-1 \\\\\n",
    "2 \\\\\n",
    "\\end{array} \\right).$$\n",
    "\n",
    "Uma grande vantagem dessa generalização é que podemos transformar equações diferenciais que envolvem derivadas além da primeira em equações diferenciais vetoriais envolvendo apenas a derivada primeira (chamadas _de primeira ordem_). Para isso basta criar variáveis auxiliares cujas derivadas são usadas para representar as derivadas de ordem maior do que 1. Vejamos um exemplo com uma equação geral de segunda ordem.\n",
    "\n",
    "$$\\begin{cases}\n",
    "x'' + p(t)x' + q(t)x = g(t) \\\\\n",
    "x(0) = \\alpha \\\\\n",
    "x'(0) = \\beta.\n",
    "\\end{cases}$$\n",
    "\n",
    "Se definirmos\n",
    "\n",
    "$$y_1 = x,\\quad\\quad\\quad y_2 = y_1' = x',$$\n",
    "\n",
    "a equação fica\n",
    "\n",
    "$$\\begin{cases}\n",
    "y_1' = y_2 \\\\\n",
    "y_2' = g(t) - p(t)y_2 + q(t)y_1 \\\\\n",
    "y_1(0) = \\alpha \\\\\n",
    "y_2(0) = \\beta.\n",
    "\\end{cases}$$\n",
    "\n",
    "Veja, ela envolve apenas as derivadas primeiras das funções desconhecidas que formam $y(t) = (y_1(t), y_2(t))$.\n",
    "\n",
    "#### Exercício\n",
    "\n",
    "Reformule o PVI abaixo como um sistema de primeira ordem\n",
    "\n",
    "$$\\begin{cases}\n",
    "u'' + u = 6 \\cos(t) \\\\\n",
    "u(0) = 2 \\\\\n",
    "u'(0) = 3.\n",
    "\\end{cases}$$\n",
    "\n",
    "## Solução numérica\n",
    "\n",
    "Agora vamos pensar um pouco o que representa resolver um PVI. Idealmente desejamos encontrar a expressão da função $y$, mas isso nem sempre é possível. De fato, é bastante comum que isso não seja possível.\n",
    "\n",
    "Vamos então nos contentar a calcular uma aproximação numérica de $y$. Se desejamos conhecer $y$ em um intervalo $[t_0, t + \\delta]$ o que fazemos é subdividir esse intervalo em $N$ partes usando $t_0 < t_1 < t_2 < \\ldots < t_N = t_0 + \\delta$, tipicamente as larguras de todos os subintervalos $h_i = t_{i} - t_{i - 1}$ são iguais, denotadas por $h$, e são conhecidas como *tamanho de passo (no tempo)*. Nosso objetivo será achar aproximações $y_i$ que aproximam o valor da solução do PVI em $t_i$. Ou seja, vamos tentar calcular\n",
    "\n",
    "$$y_i \\approx y(t_i),\\quad i = 1, \\ldots, N.$$\n",
    "\n",
    "Mas como fazer isso? Lembremos que a condição inicial nos dá o $y_0 = y(t_0)$. Devemos usar essa informação, e o resto do PVI, para tentar obter os outros valoes. De uma forma geral, vamos usar que conhecemos a sequência de aproximações $y_0, y_1, \\ldots, y_{i - 1}$ e tentar encontrar o próximo valor $y_i$. Uma ferramenta fundamental é a expansão de Taylor\n",
    "\n",
    "$$y(t_i) = y(t_{i - 1}) + h_i y'(t{i - 1}) + \\frac{h_i^2}{2}y''(\\tau),\\quad \\tau \\in (t_{i-1}, t_i).$$\n",
    "\n",
    "Agora lembramos que estamos considerando que já obtivemos $y_{i -1} \\approx y(t_i)$, temos também que\n",
    "$y'(t_{i - 1})  = f(t_{i - 1}, y(t_{i -1})) \\approx f(t_{i - 1}, y_{i - 1})$ que é conhecido. Assim, se $h_i$ for pequeno (em relação a $y''$), podemos escrever:\n",
    "\n",
    "$$y(t_i) \\approx  y_{i -1} + h_i f(t_{i - 1}, y_{i - 1}),\\quad\\quad i = 1, \\ldots, N.$$\n",
    "\n",
    "Podemos então definir a nova aproximação $y_i \\approx y(t_i)$ como \n",
    "\n",
    "$$y_i = y_{i -1} + h_i f(t_{i - 1}, y_{i - 1}),\\quad\\quad i = 1, \\ldots, N,$$\n",
    "\n",
    "definindo um método iterativo. Esse método é conhecido como método de Euler. Vejamos uma implementação \"inocente\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Método de Euler para PVI y' = f(t, y), y(a) = y0, usando n pontos. \n",
    "function Euler(a, b, f, y0, N::Int64)\n",
    "    h = (b - a) / N\n",
    "    y = zeros(N + 1)\n",
    "    y[1] = y0\n",
    "    t = a\n",
    "    for i = 2:N + 1\n",
    "        y[i] = y[i - 1] + h*f(t, y[i - 1])\n",
    "        t += h\n",
    "    end\n",
    "    return y\n",
    "end \n",
    "\n",
    "# Teste com equação simples y'= y, y(0) = 1 em [0, 2].\n",
    "f(t, y) = y\n",
    "N = 1000\n",
    "\n",
    "# Resolve primeiro com o método de Euler\n",
    "y = Euler(0, 2, f, 1, N)\n",
    "@printf(\"Valor correto    = %f\\n\", exp(2))\n",
    "@printf(\"Valor aproximado = %f\\n\", y[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(y[end] - exp(2))/exp(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Métodos de ordem mais alta\n",
    "\n",
    "Retomando o raciocínio que nos levou ao método de Euler. Lembramos que a ideia fundamenta foi a observação da expansão de Taylor da solução.\n",
    "\n",
    "$$y(t_{i + 1}) = y(t_i) + h y'(t_i) + \\frac{h^2}{2} y''(t_i) + \\ldots + \\frac{h^k}{k!} y^{(k)}(t_i) + O(h^{k + 1}).$$\n",
    "\n",
    "Apesar da expansão de Taylor ir até um grau qualquer de derivação, olhamos apenas a primeira derivada e obtivemos\n",
    "\n",
    "$$y(t_{i + 1}) = y(t_i) + h y'(t_i) + O(h^2).$$\n",
    "\n",
    "O proximo passo é ignorar o erro e escrever\n",
    "\n",
    "$$y(t_{i + 1}) \\approx y(t_i) + h y'(t_i).$$\n",
    "\n",
    "Por fim relembramos que a equação diferencial fornece o valor de $y'(t_i)$, ele é simplesmente $f(t_i, y(t_i))$ que é conhecido aproximadamente pois conhecemos $f$ e supomos que já conhecemos uma boa aproximação de $y(t_i)$, resultando em\n",
    "\n",
    "$$y(t_{i + 1}) \\approx y(t_i) + h f(t_i, y_i).$$\n",
    "\n",
    "Substituindo pelos valores calculados pelo anteriormente, que combina todas as aproximações, temos a expressão final da iteração método de Euler\n",
    "\n",
    "$$y_{i+1} = y_{i} + h f(t_i, y_i).$$\n",
    "\n",
    "Agora porque parar no primeiro termo da expansão de Taylor? Por que não continuar? Vamos ver o que podemos fazer se usarmos até o segundo termo. Ou seja, se partirmos da expressão\n",
    "\n",
    "$$y(t_{i + 1}) = y(t_i) + h y'(t_i) + \\frac{h^2}{2} y''(t_i) + O(h^3).$$\n",
    "\n",
    "Nesse caso, precisamos não apenas conhecer uma boa aproximação de $y'(t_i)$ que já sabemos ser $f(t_i, y_i)$, precisamos também aproximar a segunda derivada.\n",
    "\n",
    "Isso pode ser feito partindo da equação diferencial que diz que\n",
    "\n",
    "$$y'(t) = f(t, y(t)).$$\n",
    "\n",
    "Derivando os dois lados da igualdade\n",
    "\n",
    "$$\\begin{split}\n",
    "y''(t) &= \\frac{d}{dt} f(t, y(t)) \\\\\n",
    "&= \\frac{d}{dt} f(t, y(t)) + \\frac{d}{dy} f(t, y(t)) y'(t) \\\\\n",
    "&= \\frac{d}{dt} f(t, y(t)) + \\frac{d}{dy} f(t, y(t)) f(t, y(t)).\n",
    "\\end{split}$$\n",
    "\n",
    "Podemos simplificar um pouco a expressão acima adotando a notação\n",
    "\n",
    "$$\\frac{d}{dt} f = f_t,\\quad \\frac{d}{dy} f = f_y.$$\n",
    "\n",
    "Temos então \n",
    "\n",
    "$$y''(t) = f_t(t, y(t)) + f_y(t, y(t)) f(t, y(t)).$$\n",
    "\n",
    "Portanto,\n",
    "\n",
    "$$y''(t_i) \\approx f_t(t_i, y_i) + f_y(t_i, y_i) f(t_i, y_i).$$\n",
    "\n",
    "Veja que o valor obtido é apenas uma aproximação, já que $y_i$ é apenas uma aproximação de $y(t_i)$. \n",
    "\n",
    "Substituindo a fórmula acima na expasão de Taylor até a segunda ordem e, mais uma vez, ignorando o erro obtemos:\n",
    "\n",
    "$$y(t_{i + 1}) \\approx y_{i + 1} = y_i + h f(t_i, y_i) + \\frac{h^2}{2} (f_t(t_i, y_i) + f_y(t_i, y_i) f(t_i, y_i)).$$\n",
    "\n",
    "Esse método é interessante porque consegue usar a informação da segunda derivada de $y$, obtendo assim mais precisão. Uma das formas de entender isso é definir a ideia de **erro de truncamento local**.\n",
    "\n",
    "**Definição**. *Erro de truncamento local* é o erro com o qual a solução *real* deixa de obedecer à equação que define o método quando o lado esquerdo é re-escrito de maneira a aproximar a derivada $y'$:\n",
    "\n",
    "$$\\frac{y_{i + 1} - y_i}{h}.$$\n",
    "\n",
    "Vamos usar essa definição para calcular o erro de truncamento local dos métodos de Euler e do método de segunda ordem apresentado acima.\n",
    "\n",
    "Para o método de Euler temos a equação\n",
    "\n",
    "$$\\frac{y_{i + 1} - y_i}{h} = f(t_i, y_i).$$\n",
    "\n",
    "Se no lugar da aproximação $y_k$ usarmos a solução real $y(t_k)$, não valerá mais a igualdade. Na verdade podemos usar diretamente Taylor e ver que\n",
    "\n",
    "$$\\frac{y(t_{i + 1}) - y(t_i)}{h} = f(t_i, y(t_i)) + \\frac{h}{2} y''(\\xi_i).$$\n",
    "\n",
    "Ou seja, a solução real obedece à equação que define o método de Euler a menos de erro que é da ordem de $h$. Por isso dizemos que o método de Euler é de primeira ordem.\n",
    "\n",
    "Já no caso do método de segunda ordem, mais uma vez usando Taylor, teremos\n",
    "\n",
    "$$\\frac{y(t_{i + 1}) - y(t_i)}{h} = f(t_i, y(t_i)) + \\frac{h}{2} y''(t_i) + \\frac{h^2}{3!} y'''(\\xi_i).$$\n",
    "\n",
    "Retomando a expressão de $y''$ obtida anteriormente obtemos\n",
    "\n",
    "$$\\frac{y(t_{i + 1}) - y(t_i)}{h} = f(t_i, y(t_i)) + \\frac{h}{2}[f_t(t_i, y(t_i)) + f_y(t_i, y(t_i)) f(t_i, y(t_i))] + \\frac{h^2}{3!} y'''(\\xi_i).$$\n",
    "\n",
    "E vemos que solução real obedece ao método de segunda ordem com erro da ordem de $h^2$, o que é potencialmente bem menor do que $h$, quando $h$ é pequeno.\n",
    "\n",
    "Nesse sentido o método de segunda ordem é melhor que o método de Euler. Além disso, deve ficar claro que podemos obter métodos de ordem mais alta aproveitando mais termos da expansão de Taylor. Para isso, precisamos saiber como calcular as derivadas de ordem mais alta de $y$. Isso é sempre possível partindo da equação diferencial e fazendo aplicações repetidas da regra da cadeia. Por exemplo\n",
    "\n",
    "$$y''' = f_{tt} + 2f_{ty}f + f_{y}f^2 + f^2_y f.$$\n",
    "\n",
    "A única dificuldade encontrada nesse caso é que teremos que calcular as derivadas de $f$ o que pode ser trabalhoso ou impossível se não conhecermos uma expressão explícita para a função. Surge então uma pergunta natural: é possível obter métodos de ordem maior que $1$ usando apenas os valores de $f$ evitando suas derivadas explícitas?\n",
    "\n",
    "Por fim, há resultados bem gerais sobre a convergência de métodos numéricos para a resolução de PVI que garantem que as aproximações $y_i$ de $y(t_i)$ que são calculadas convergem para os valores reais se o erro de truncamento local vai para zero quando $h \\rightarrow 0$, e essa convergência ocorre mais rapidamente quanto menor for o erro de truncamento local como função de $h$. Não vamos apresentar esses resultados formalmente aqui, mas você pode encontrá-los em bons livros de cálculo numérico ou livros mais especializados na solução numérica de equações diferenciais. \n",
    "\n",
    "## Método do ponto médio\n",
    "\n",
    "Um dos problemas do método de Euler é que ele considera constante a derivada de $y$ ao ir do ponto $y_{i}$ para $y_{i + 1}$. Isso, por exemplo, implica que o método irá sempre errar por baixo se a derivada for crescente ou por cima se a derivada for decrescente. O ideal seria conhecer qual é a derivada média entre $[t_i, t_{i + 1}]$ e usar esse valor. Mas isso não é possível. Não conhecemos $y$ nesse intervalo, já que isso é justamente o que queremos calcular. Uma tentativa de aproximar essa ideia é tentar aproximar a derivada no ponto médio do intervalo e usá-la como aproximação da derivada média. Se as derivadas forem contínuas, o que é uma hipótese razoável no contexto de PVI, essa derivada no ponto médio deve tanto receber influência das derivadas em $t_i$ quanto em $t_{i + 1}$. Mas, de novo, recaímos no mesmo problema: não conhecemos $y(t_i + h / 2)$. \n",
    "\n",
    "A ideia do método do ponto médio é usar o Euler para aproximar $y(t_i + h / 2)$ e depois calcular a derivada nesse ponto usando a definição da equação diferencial. Por fim usamos essa derivada \"média aproximada\" para dar um passo parecido com Euler de $t_i$ para $t_{i + 1}$. Obtemos o *método do ponto médio*:\n",
    "\n",
    "$$\\begin{split}\n",
    "y_{i + 1/2} &= y_i + h/2f(t_i, y_i), \\\\\n",
    "y_{i + 1} &= y_i + h f(t_{i + 1/2}, y_{i + 1/2}).\n",
    "\\end{split}$$\n",
    "\n",
    "Observe que esse método necessita de duas avaliações de $f$, mas de nenhuma avaliação da _derivada_ de $f$. Ele será vantajoso somente se conseguir a mesma precisão que $Euler$ com um passo duas vezes maior e melhor se puder usar um passo ainda mais longo. Para justificar que esse método é interessante vamos analisar o seu erro de truncamento local.\n",
    "\n",
    "Começamos expandindo $y(t_i)$ e $y(t_{i + 1})$ em torno de $t_{i + 1/2}$.\n",
    "\n",
    "$$\\begin{split}\n",
    "y(t_{i + 1}) &= y(t_{i + 1/2}) + y'(t_{i + 1/2}) (h/2) + \\frac{y''(t_{i + 1/2})}{2} (h/2)^2 + O(h^3), \\\\\n",
    "y(t_{i}) &= y(t_{i + 1/2}) - y'(t_{i + 1/2}) (h/2) + \\frac{y''(t_{i + 1/2})}{2} (h/2)^2 + O(h^3),\n",
    "\\end{split}$$\n",
    "\n",
    "Subtraindo essas duas expressões obtemos\n",
    "$$y(t_{i + 1}) - y(t_i) = f(t_{i + 1/2}, y(t_{i + 1/2})) h + O(h^3).$$\n",
    "\n",
    "Para chegar à equação que define o método precisamos trocar $y(t_{i + 1/2})$ por $y_{i + 1/2}$. Para isso vamos expandir $y(t_{i + 1/2})$ por Taylor.\n",
    "\n",
    "$$y(t_{i + 1/2}) = y(t_i) + h/2 f(t_i, y_i) + O(h^2).$$\n",
    "\n",
    "Agora se olharmos para a primeira equação que define o método do ponto médio obtemos:\n",
    "\n",
    "$$y(t_{i + 1/2}) = y_{i + 1/2} + O(h^2).$$\n",
    "\n",
    "Substituindo na equação anterior, temos\n",
    "\n",
    "$$y(t_{i + 1}) - y(t_i) = f(t_{i + 1/2}, y_{i + 1/2} + O(h^2)) h + O(h^3).$$\n",
    "\n",
    "Relembrando que $f$ é Lipschitz na segunda variável,\n",
    "\n",
    "$$y(t_{i + 1}) - y(t_i) = f(t_{i + 1/2}, y_{i + 1/2}) h + O(h^3).$$\n",
    "\n",
    "Agora dividindo por $h$ dos dois lados para achar a aproximação de $y'$, resulta em\n",
    "\n",
    "$$\\frac{y(t_{i + 1}) - y(t_i)}{h} = f(t_{i + 1/2}, y_{i + 1/2}) + O(h^2).$$\n",
    "\n",
    "Vemos que o erro de truncamento de $f$ no método do ponto médio é computado naturalmente no ponto médio e é da ordem de $h^2$, melhor que Euler e sem envolver derivadas de $f$. Essa diferença de ordem pode fazer com que o método do ponto médio possa atingir às vezes uma precisão boa com passos muito maiores. Vamos ver isso acontecendo na prática. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Teste com equação boba y'= y, y(0) = 1 em [0, 2].\n",
    "f(t, y) = y\n",
    "n = 1000\n",
    "\n",
    "# Resolve primeiro com o método de Euler\n",
    "y = Euler(0, 2, f, 1, n)\n",
    "@printf(\"Euler:\\n\")\n",
    "@printf(\"Valor correto    = %f\\n\", exp(2))\n",
    "@printf(\"Valor aproximado = %f\\n\", y[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(y[end] - exp(2))/exp(2))\n",
    "\n",
    "# Método de Ponto médio para PVI y' = f(t, y), y(a) = y0, usando n pontos. \n",
    "function PontoMedio(a, b, f, y0, n::Int64)\n",
    "    h = (b - a) / n\n",
    "    y = zeros(n + 1)\n",
    "    y[1] = y0\n",
    "    t = a\n",
    "    for i = 2:n + 1\n",
    "        y05 = y[i - 1] + (h/2)*f(t, y[i - 1])\n",
    "        t += h/2\n",
    "        y[i] = y[i - 1] + h*f(t, y05)\n",
    "        t += h/2\n",
    "    end\n",
    "    return y\n",
    "end \n",
    "y = PontoMedio(0, 2, f, 1, round(Int64, n / 10))\n",
    "@printf(\"\\nPonto médio com 10%% dos pontos:\\n\")\n",
    "@printf(\"Valor aproximado = %f\\n\", y[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(y[end] - exp(2))/exp(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Métodos baseados em fórmulas de integração\n",
    "\n",
    "Uma ideia bastante natural é derivar métodos de solução de problemas de valor inicial usando fórmulas de integração. Para isso basta partir da definição de um PVI\n",
    "$$\\begin{split}\n",
    "y'(t) &= f(t, y(t)) \\\\\n",
    "y(a) &= y_0.\n",
    "\\end{split}$$\n",
    "Integrando essa fórmula obtemos\n",
    "$$\n",
    "y(t) - y_0 = \\int_a^t y'(t) dt = \\int_a^t f(t, y(t)) dt.\n",
    "$$\n",
    "\n",
    "Assim, se queremos estimar $y(t_{i + 1})$, ou seja calcular $y_{i + 1}$, e temos uma boa estimativa de $y(t_i)$, que chamamos de $y_i$, podemos calcular\n",
    "$$\n",
    "y(t_{i+1}) = y(t_{i}) + \\int_{t_i}^{t_{i+1}} f(t, y(t)) dt \\approx y_i + \\int_{t_i}^{t_{i+1}} f(t, y(t)) dt.\n",
    "$$\n",
    "\n",
    "Assim, para achar uma boa estimativa de $y(t_{i + 1})$ basta achar uma boa estimativa de $\\int_{t_i}^{t_{i+1}} f(t, y(t)) dt$. Para isso podemos usar qualquer uma das fórmulas de integração que vimos anteriormente. Por, exemplo usando a fórmula do trapézio temos\n",
    "$$\n",
    "\\int_{t_i}^{t_{i+1}} f(t, y(t)) dt \\approx \\frac{h}{2} \\big(f(t_{i}, y(t_{i})) + f(t_{i + 1}, y(t_{i + 1}) \\big) \\approx \\frac{h}{2} \\big(f(t_{i}, y_{i}) + f(t_{i + 1}, y_{i + 1}) \\big).\n",
    "$$\n",
    "Substituindo na fórmula acima temos o método do trapézio\n",
    "$$\n",
    "y_{i + 1} = y_i + \\frac{h}{2} \\big(f(t_{i}, y_{i}) + f(t_{i + 1}, y_{i + 1}) \\big).\n",
    "$$\n",
    "\n",
    "Esse método pode ser implementado e tem um bom comportamento. Infelizmente a sua implementação é um pouco mais complicada do que parece inicialmente. Isso porque o valor desconhecido $y_{i + 1}$ aparece dos dois lados da equação e do segundo lado de forma não linear. Ele não pode ser isolado facilmente e cada iteração do método envolverá a resolução de uma equação não-linear em $y_{i + 1}$, por exemplo usando o método de Newton. Esse tipo de método é conhecido como **implícito**. Note que como o método do trapézio tem erro da ordem $O(h^3)$ então o erro de truncamento local do método do trapézio para PVI é $1/h O(h^3) = O(h^2)$.\n",
    "\n",
    "Podemos contonar a dificuldade de um método implícito e ainda conseguir um método mais interessante do que Euler. Por exemplo podemos primeiro estimar $y_{i + 1}$ por Euler e depois substituir essa aproximação no lado direito da equação que define o método dos trapézios. Com isso obtemos o método de Heun:\n",
    "$$\\begin{split}\n",
    "\\hat{y}_{i + 1} &= y_i + h f(t_i, y_i) \\\\\n",
    "y_{i + 1} &= y_i + \\frac{h}{2} \\big(f(t_{i}, y_{i}) + f(t_{i + 1}, \\hat{y}_{i + 1}) \\big).\n",
    "\\end{split}$$\n",
    "Uma forma geométrica de entender esse método é que ele segue uma linha que tem como inclinação a média de inclinação em $(t_i, y_i)$ e em $(t_{i + 1}, \\hat{y}_{i + 1})$.\n",
    "\n",
    "## Métodos do tipo Runge-Kutta\n",
    "\n",
    "Uma forma alternativa de se deduzir o Método de Heun é tentar analisar as expansões de Taylor de modo a obter um método que obtenha um erro de truncamento o menor possível. Para atingir isso podemos imaginar que vamos calcular um ponto intermediário\n",
    "$$\n",
    "\\tilde{y}_{i + \\alpha} = y_i + \\alpha h f(t_i, y_i).\n",
    "$$\n",
    "Para em seguida obter o próximo ponto através de\n",
    "$$\n",
    "y_{i + 1} = y_i + \\beta h f(t_i, y_i) + \\gamma h f(t_i + \\alpha h, \\tilde{y}_{i + \\alpha}).\n",
    "$$\n",
    "O objetivo é escolher os parâmetros $\\alpha,\\ \\beta$ e $\\gamma$ de modo a garantir um erro de truncamento local o menor possível.\n",
    "\n",
    "Vamos começar analisando o que podemos obter pela escolha do ponto intermediário $\\tilde{y}_{i + \\alpha}$. Vamos então expandir $f(t_i + \\alpha h, \\tilde{y}_{i + \\alpha})$ em torno do ponto original $(t_i, y_i)$. \n",
    "\\begin{multline}\n",
    "f(t_i + \\alpha h, \\tilde{y}_{i + \\alpha}) = f(t_i + \\alpha h, y_i + \\alpha h f(t_i, y_i).) = \\\\\n",
    "f + \\alpha h (f_t + f f_y) + \\frac{\\alpha^2 h^2}{2} (f_{tt} + 2 f f_{ty} + f^2 f_{yy}) + O(h^3).\n",
    "\\end{multline}\n",
    "Todas as aparições de $f$ e suas derivadas estão sendo avaliadas em $(t_i, y_i)$. \n",
    "\n",
    "Substituindo de volta na fórmula de $y_{i + 1}$\n",
    "$$\\begin{split}\n",
    "y_{i + 1} &= y_i + \\beta h f + \\gamma h (f + \\alpha h (f_t + f f_y) + \\frac{\\alpha^2 h^2}{2} (f_{tt} + 2 f f_{ty} + f^2 f_{yy}) + O(h^3)) \\\\\n",
    "&= y_i + (\\beta + \\gamma)h f + \\alpha \\gamma h^2 (f_t + f f_y) + \\frac{\\alpha^2 \\gamma h^3}{2} (f_{tt} + 2 f f_{ty} + f^2 f_{yy}) + O(h^4). \n",
    "\\end{split}$$\n",
    "\n",
    "Já a expansão de Taylor da solução real $y(t_{i + 1})$ em torno de $t_i$ é\n",
    "$$\\begin{split}\n",
    "y(t_{i + 1}) &= y(t_i) + h y'(t_i) h + \\frac{h^2}{2} y''(t_i) + \\frac{h^3}{6} y'''(t_i) + O(h^4) \\\\\n",
    "&= y(t_i) + h f + \\frac{h^2}{2} (f_t + f f_y) + \\frac{h^3}{6} ( f_{tt} + 2 f f_{t y} + f_t f_y + f^2 f_{yy} + f f_y^2 ) + O(h^4).\n",
    "\\end{split}$$\n",
    "\n",
    "Analisando as duas últimas expressões vemos que conseguimos forçar $y(t_{i + 1})$ a obedecer a equação do método até o termo que multiplica $h^2$, já o termo $O(h^3)$ não pode ser exatamente iguais por que o conjunto de derivadas que o multiplica ser diferente. Para isso precisamos que\n",
    "$$\n",
    "\\beta + \\gamma = 1, \\quad \\alpha \\gamma = \\frac{1}{2}.\n",
    "$$\n",
    "Essas esquações têm múltiplas soluções. Por exemplo podemos tomar $\\beta = \\gamma = 1/2$, $\\alpha = 1$ e recuperamos o método de Heun. Ou ainda tomarmos $\\alpha = 1/2$, $\\gamma = 1$ e $\\beta = 0$ e então temos o método do ponto médio.\n",
    "\n",
    "Métodos que oebedecem a esse tipo de equações, usando pontos intermediários para anular termos de ordem mais alta nas séries de Taylor são conhecidos como métodos de Runge-Kutta. Os dois métodos acima tem erro de truncamento local da ordem de $O(h^2)$. Porém, introduzindo mais pontos intermediários e parâmetros é possível obter métodos de quarta ordem, ou seja com erro de truncamento $O(h^4)$. A dedução é porém muito complicada e vamos apenas apresentar as fórmulas envolvidas\n",
    "$$\\begin{split}\n",
    "q_1 &= f(t_i, y_i), \\\\\n",
    "q_2 &= f(t_i + h/2, y_i + (h/2) q_1) \\\\\n",
    "q_3 &= f(t_i + h/2, y_i + (h/2) q_2) \\\\\n",
    "q_4 &= f(t_i + h, y_i + h q_3) \\\\\n",
    "y_{i + 1} &= y_i + \\frac{h}{6} (q_1 + 2 q_2 + 2 q_3 + q_4).\n",
    "\\end{split}$$\n",
    "Esse método é conhecido como méto de Runge-Kurra de quarta ordem clássico. Uma forma interessante de derivá-lo é ver que se $f$ não depende de $y$ então esse método corresponde a a fórmula de integração de Simpson que é dada por\n",
    "$$\n",
    "y(t + h) - y(t) = \\int_t^{t + h} f(s) ds \\approx \\frac{h}{6} \\left( f(t) + 4 f(t + h/2) + f(t + h) \\right).\n",
    "$$\n",
    "\n",
    "Está na hora de testar esses métodos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Teste com y'= f, [2, 3], y(2) = 2.\n",
    "f(t, y) = 1 - y / t\n",
    "ys(t) = t/2 + 2/t\n",
    "n = 2\n",
    "\n",
    "# Imprime solução\n",
    "@printf(\"Valor correto    = %f\\n\", ys(3))\n",
    "\n",
    "# Resolve primeiro com o método de Euler\n",
    "println(\"Euler:\")\n",
    "ye = Euler(2, 3, f, 2, n)\n",
    "@printf(\"Valor aproximado = %f\\n\", ye[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(ye[end] - ys(3))/ys(3))\n",
    "\n",
    "@printf(\"\\nPonto médio de segunda ordem:\\n\")\n",
    "ypm = PontoMedio(2, 3, f, 2, n)\n",
    "@printf(\"Valor aproximado = %f\\n\", ypm[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(ypm[end] - ys(3))/ys(3))\n",
    "\n",
    "# Método de Runge-Kutta de quarta ordem para PVI y' = f(t, y), y(a) = y0, usando n pontos. \n",
    "function RK4(a, b, f, y0, n::Int64)\n",
    "    h = (b - a) / n\n",
    "    y = zeros(n + 1)\n",
    "    y[1] = y0\n",
    "    t = a\n",
    "    for i = 2:n+1\n",
    "        q1 = f(t, y[i - 1])\n",
    "        q2 = f(t + h/2, y[i - 1] + (h/2)*q1)\n",
    "        q3 = f(t + h/2, y[i - 1] + (h/2)*q2)\n",
    "        q4 = f(t + h, y[i - 1] + h*q3)\n",
    "        y[i] = y[i - 1] + (h / 6)*(q1 + 2*q2 + 2*q3 + q4)\n",
    "        t += h\n",
    "    end\n",
    "    return y\n",
    "end\n",
    "@printf(\"\\nRunge-Kutta de quarta ordem:\\n\")\n",
    "yrk4 = RK4(2, 3, f, 2, n)\n",
    "@printf(\"Valor aproximado = %f\\n\", yrk4[end])\n",
    "@printf(\"Erro relativo    = %.2e\\n\", abs(yrk4[end] - ys(3))/ys(3))\n",
    "\n",
    "# Método de Runge-Kutta de segunda ordem para PVI y' = f(t, y), y(a) = y0, usando n pontos. \n",
    "function RK2(a, b, f, y0, n::Int64)\n",
    "    h = (b - a) / n\n",
    "    y = zeros(n + 1)\n",
    "    y[1] = y0\n",
    "    t = a\n",
    "    for i = 2:n+1\n",
    "        ty = y[i - 1] + h*f(t, y[i - 1])\n",
    "        y[i] = y[i - 1] + (h / 2)*(f(t, y[i - 1]) + f(t + h, ty))\n",
    "        t += h\n",
    "    end\n",
    "    return y\n",
    "end;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.3",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.6.3"
  },
  "latex_metadata": {
   "title": "Problema de valor inicial"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}