# Analisando o erro numérico

Seja $z$ a raiz de $f$ para a qual o método de Newton converge.
Temos $x_n$ e $x_{n+1}$, e queremos ver como o erro (ou seja, a distância até $z$) evolui com 1 passo.

## Relações que possuímos:

- $x_{n+1} = x_n - f(x_n)/f'(x_n)$
- Taylor: $f(x_n) = f(z) + f'(z)(x_n - z) + \frac{f''(\xi)}{2}(x_n - z)^2$

Poderíamos usar esta expansão de Taylor, mas então teríamos que analisar $f'(z)$ e $f'(x_n)$.
O que pode ser feito usando Taylor (de novo) para a primeira derivada, mas começam a aparecer muitos "pontos intermediários".

Vamos usar uma outra expansão de Taylor:
- $f(z) = f(x_n) + f'(x_n)(z - x_n) + \frac{f''(\xi)}{2}(z - x_n)^2$ (o $\xi$ desta fórmula é diferente do da anterior!)

### Comentário

Aqui vemos a grande utilidade da técnica "dar nome aos burros" ao resolver um problema.
Por mais que $z$ seja desconhecido, podemos incluí-lo em nossas fórmulas.
Além disso, por mais que seja desconhecido, podemos também usar alguma propriedade -
no nosso caso, $f(z) = 0$ - nas contas.

## Continuando as contas

Da fórmula de Taylor, temos:
$$\begin{align}
0 & = f(x_n) + f'(x_n)(z - x_n) + \frac{f''(\xi)}{2}(z - x_n)^2 \\
- f(x_n) & = f'(x_n)(z - x_n) +  \frac{f''(\xi)}{2}(z - x_n)^2 \\
- \frac{f(x_n)}{f'(x_n)} & = (z - x_n) + \frac{f''(\xi)}{2 f'(x_n)}(z - x_n)^2.
\end{align}$$
Portanto, $x_{n+1} = x_n + (z - x_n) + \frac{f''(\xi)}{2 f'(x_n)}(z - x_n)^2 = \frac{f''(\xi)}{2 f'(x_n)}(z - x_n)^2$.

Isso mostra que o erro $\varepsilon_{n+1} = x_{n+1} - z$ será, em função do erro anterior $\varepsilon_n$:
$$\varepsilon_{n+1} = \frac{f''(\xi)}{2 f'(x_n)} \varepsilon_n^2,$$
que é a famosa propriedade de "elevar o erro anterior ao quadrado" (a menos de um fator).

### Exercício

Suponha que o quociente das derivadas seja sempre menor do que 2,
e suponha que o erro inicial é 1/3.
Em quantas etapas ele será menor do que `1e-16`?


```python
def tempo_para_convergir(erro, max_quot, alvo):
    """Retorna o número de passos necessários para que o `erro` fique menor do que `alvo`,
    se o quociente das derivadas do método de Newton for sempre menor do que `max_quot`. """
    i = 0
    ### Resposta aqui

    return i
```


```python
tempo_para_convergir(1/3, 2, 1e-16)
```




    6



Como evolui o erro?


```python
def tempo_para_convergir_lista(erro, max_quot, alvo):
    """Retorna a lista com os erros intermediários produzidos pelo método de Newton, cf `tempo_para_convergir`. """
    ### Resposta aqui

```


```python
tempo_para_convergir_lista(1/3, 2, 1e-16)
```




    [0.3333333333333333,
     0.1111111111111111,
     0.012345679012345678,
     0.00015241579027587256,
     2.3230573125418767e-08,
     5.396595277354286e-16,
     2.9123240587562585e-31]



O que acontece se apenas garantimos que o fator é menor do que 4?
E se for 10?


```python
tempo_para_convergir_lista(1/3, 4, 1e-16)
```




    [0.3333333333333333,
     0.2222222222222222,
     0.09876543209876543,
     0.019509221155311687,
     0.0007612194201737221,
     1.1589100112992354e-06,
     2.686144828579188e-12,
     1.443074808020543e-23]




```python
tempo_para_convergir_lista(1/3, 10, 1e-16)
```




    []



O que fazer para ainda ter convergência caso só seja possível limitar o quociente das derivadas por 10??



## Mas e o $\xi$?

A nossa fórmula já explica uma boa parte da rapidez de convergência do método de Newton,
mas ela ainda contém vários elementos desconhecidos, como o $\xi$, $f'(x_n)$,
que dependem da função, do ponto onde estamos, etc.
Para transformar esta conta exata, mas com termos variáveis,
numa estimativa mais independente, o que vamos fazer é **supor** algo sobre a função $f$.

Por exemplo, podemos supor que a segunda derivada é _limitada_ perto de $z$.
Assim, quando estivermos "perto" da raiz, podemos supor (como fizemos acima) que uma parte do fator não é muito grande.
Novamente, podemos supor que a primeira derivada não é **pequena demais** perto de $z$.
Assim, o quociente estará certamente limitado, e, se estivermos "perto o suficiente" da raiz,
vamos convergir bem rápido.

### Exercício

Resolva a recorrência $x_{n+1} = Cx_n^2$, com $x_0 = \delta$.
Dica: escreva uns 5 termos, e veja o padrão em $\delta$, $C$ e $n$!

6653e029b97552d97dfcab3e4f9fb8ac3deef98c
ipynb
Jupyter Notebook
comp-cientifica-I-2018-2/semana-5/raw_files/Semana3-Parte4-AnaliseNewton.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
2019-12-23T16:39:01.000Z
2019-12-23T16:39:01.000Z
comp-cientifica-I-2018-2/semana-5/raw_files/Semana3-Parte4-AnaliseNewton.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
comp-cientifica-I-2018-2/semana-5/raw_files/Semana3-Parte4-AnaliseNewton.ipynb
mirandagil/university-courses
e70ce5262555e84cffb13e53e139e7eec21e8907
MIT
Qwen/Qwen-72B
1. YES
2. YES