{
"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<ipython-input-4-584a7602291b>\u001b[0m in \u001b[0;36m<module>\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<ipython-input-1-294d71ef7606>\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
}