{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Soluções de equações não lineares\n", "====\n", "Dada uma função $f:I\\to \\mathbb{R}$ contínua, queremos encontrar um elemento $x\\in I$ tal que $f(x)=0$.\n", "Se encontramos $a,b$ tais que $f(a)f(b)\\lt 0$, podemos garantir a existência de, pelo menos, uma raiz da equação (por causa da continuidade). Determinar um intervalo onde exista uma única raiz não é tão simples e requer mais regularidade da função $f$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O método da dicotomia\n", "----\n", "\n", "O algoritmo mais simples para se encontrar esta solução é ir repartindo o intervalo ao meio. Testando de que lado está a raiz, e repetir o processo até que o tamanho do intervalo. Podemos descrever este algoritmo assim:\n", "\n", "* Passo 1: Temos o intervalo $[a,b]$ com $f(a)f(b) \\lt 0$ fazemos $x_1= (a+b)/2$. Se $|f(x_1)|\\lt \\varepsilon$, encontramos uma boa aproximação. Senão repetimos este passo em $[a,x_1]$ se $f(a)f(x_1) \\lt 0$ ou em $[x_1,b]$ caso contrário.\n", "\n", "O algoritmo em python pode ser:\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def dicotomia(f,a,b,n):\n", " \"\"\" Calcula a raiz de f(x)=0 usando o método da dicotomia\n", " a: inicio do intervalo\n", " b: fim do intervalo\n", " n: numero de iterações \"\"\"\n", " # por uma mensagem de erro depois se f(a)*f(b)>=0\n", " if f(a)*f(b)>= 0:\n", " raise ValueError( \"f(a) e f(b) têm mesmo sinal\" ) \n", " raiz = (a+b)/2\n", " for i in range(n):\n", " if f(a)*f(raiz) < 0:\n", " a,b = a,raiz\n", " else : a,b = raiz,b\n", " raiz =(a+b)/2\n", " return raiz" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "-1 64\n" ] } ], "source": [ "f = lambda x : (x-1)**3\n", "print(f(0),f(5))" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0.99853515625" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dicotomia(f,0,5, 10)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "ename": "ValueError", "evalue": "f(a) e f(b) têm mesmo sinal", "output_type": "error", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[1;32m\u001b[0m in \u001b[0;36m\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mdicotomia\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m4\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[1;32m\u001b[0m in \u001b[0;36mdicotomia\u001b[1;34m(f, a, b, n)\u001b[0m\n\u001b[0;32m 6\u001b[0m \u001b[1;31m# por uma mensagem de erro depois se f(a)*f(b)>=0\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 7\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m>=\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 8\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m \u001b[1;34m\"f(a) e f(b) têm mesmo sinal\"\u001b[0m \u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m 9\u001b[0m \u001b[0mraiz\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m/\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m 10\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n", "\u001b[1;31mValueError\u001b[0m: f(a) e f(b) têm mesmo sinal" ] } ], "source": [ "dicotomia(f,2,4,10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O erro inicial no método da dicotomia é $|x_1-x_r|\\leq |b-a|/2$. A cada passo a estimativa desse erro é dividida por 2, assim $|x_n-x_r|\\leq |b-a|/2^n$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "O método de Newton\n", "----\n", "Agora $f: [a,b] \\to \\mathbb{R}$ é uma função diferenciável com um único zero neste intervalo. Podemos produzir uma sequência de estimativas $x_n$ deste zero, baseado na aproximação linear da função $f$, ou de seu polinômio de primeira ordem.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suponha que $x_e$ seja uma estimativa do zero que queremos melhorar. A série de Taylor em torno de $x_e$ é\n", "\n", "$$ f(x) = f(x_e) + f^\\prime(x_e)(x-x_e) + O(|x-x_e|^2)$$\n", "\n", "se fizermos $f(x)=0$, e desprezarmos o $o(|x-x_e|^2)$ temos \n", "\n", "$$ 0 = f(x_e) + f^\\prime(x_e)(x_n - x_e)$$\n", "\n", "sendo $x_n$ a nova estimativa. Resolvendo para $x_n$ temos:\n", "\n", "$$ x_n = x_e - \\frac{f(x_e)}{f^\\prime(x_e)} $$\n", "\n", "e esta relação é a base do método de Newton.\n", "\n", "da mesma forma que anteriormente, produzimos uma sequência de estimativas, escolhendo um $x_0$ arbritário e, a partir dele, calculando\n", "\n", "$$x_{k+1} = x_k - \\frac{f(x_k)}{f^\\prime(x_k)} $$\n", "\n", "E esperemos que esta sequência convirja!!" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from math import *\n", "def met_Newton(f,flinha,x0,epsilon):\n", " x1=x0 - f(x0)/flinha(x0)\n", " erro = max(abs(x1-x0),abs(f(x1)))\n", " while erro > epsilon:\n", " x0=x1\n", " x1=x0 - f(x0)/flinha(x0)\n", " erro = max(abs(x1-x0),f(x1))\n", " return x1 " ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [], "source": [ "g= lambda x: (x-1.)*(x-5.)**2\n", "glinha = lambda x: (x-5.)**2 + 2.*(x-1)*(x-5)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0.9999999999999999" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "met_Newton(g,glinha,1.5,0.00001)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.4.3" } }, "nbformat": 4, "nbformat_minor": 0 }