Map0151

| Comunidade no Stoa | Disciplina no Moodle|

Números no Computador

Muitos dos algoritmos de cálculo numérico, por uma questão prática, deverão ser executados numa máquina real. Nestas máquinas, no entanto, a capacidade de memória para representação dos números é finita. Vários números reais (infinitos, de fato) terão a mesma representação no computador (ou calculadora), daí originando-se os erros de arredondamentos. Vamos ver qual é a técnica usada atualmente para diminuir os erros de arredondamentos.

Representação de números inteiros numa base

Seja $\beta > 1$ um número natural. Então podemos representar qualquer número inteiro $k$ como a soma $$k= \text{sgn}(k)*a_0\beta^0 + \cdots + a_s \beta^s$$ onde cada algarismo $a_j$ representa um número natural entre $0$ e $\beta -1$. Só $a_s$ é diferente de zero. Esta representação é única. A representação de $k$ na base $\beta$ é $$k=\pm [a_s\dots a_0]_{\beta}$$ Deixando o sinal de $k$ de fora, para simplificar. Podemos calcular os algarismos do número daddo na base $\beta$ aplicando repetidas vezes o algoritmo da divisão. Escrevendo $$k = a_0 + \beta(a_1 +\beta( a_2 + \cdots +\beta a_s)\cdots ))$$ vemos que $a_0$ é o resto da divisão $k//\beta$, $a_1$ é o resto da divisão $(k-a_0)//\beta$ e assim por diante.

Exemplo: $39 = [100111]_2$

Representação de números fracionários e decimais numa base

Seja novamente $\beta > 1$ um número natural.

Se $x \in (0,1)$ então $$x= \frac{b_1}{\beta} + \cdots + \frac{b_k}{\beta^k} + \cdots$$ Diremos que $x=[0.b_1 b_2\dots]_{\beta}$ é a representação fracionária na base $\beta$ de $x$. Quando não houver dúvidas de que base se trata, omite-se a base da notação!

Exemplo: $0.9= [0.1110011001100...]_2$

Uma função para colocar um número decimal na forma binária

In[1]:

# -*- coding: utf-8 -*- """ Spyder Editor """ def binario(a):     # da a representacao binaria do numero a     ParteInteira = int(a)     ParteDecimal = a-int(a)     # representacao binaria da parte inteira     # a lista seguinte guarda os dígitos da parte inteira     ListaDigitos=[]     while (ParteInteira > 0):         ListaDigitos.append(ParteInteira%2)         ParteInteira=ParteInteira//2     # lista dos digitos depois da virgula     ListaResto=[]     k=1     while ((ParteDecimal!=0)&(k<50)):         ListaResto.append(int(2*ParteDecimal))         ParteDecimal=2*ParteDecimal - int(2*ParteDecimal)         k=k+1     # produz a string de representacao:             i=len(ListaDigitos)-1     p1=""     while (i>=0):         p1=p1+str(ListaDigitos[i])         i=i-1     # Depois disso p1 tem a parte inteira     l=0     p2=""     while (l<len(ListaResto)):         p2=p2+str(ListaResto[l])         l=l+1         return p1+"."+p2     print (binario(21.75))

Representação em ponto flutuante

Consideramos uma base fixa $\beta > 1$. Um número real $\alpha \in \mathbb{R}$ positivo pode ser escrito nesta base como: $$\alpha = [a_k\cdots a_0.b_1b_2\cdots]_{\beta}$$ Isto significa que: $$\alpha = a_k\beta^k + \cdots + a_0 + \frac{b_1}{\beta} +\frac{b_2}{\beta^2} + \cdots$$ Na equação acima, colocando $\beta^{k+1}$ em evidência temos: $$\alpha = \left( \frac{a_k}{\beta} + \cdots + \frac{a_0}{\beta^{k+1}} + \frac{b_1}{\beta^{k+2}} +\frac{b_2}{\beta^{k+3}} + \cdots\right)\times \beta^{k+1}$$ ou ainda, lembrando da notação de um número numa base dada: $$\alpha = [0.a_k \cdots a_0 b_1 b_2\cdots]_{\beta} \times \beta^{k+1}$$ Esta última fórmula é importante. O número real $\alpha$ fica caracterizado por três dados:

• O número $m = [0.a_k \cdots a_0 b_1 b_2\cdots]_{\beta} \in (0,1)$ chamado de mantissa.
• O número $e = k+1$ chamado de expoente
• O sinal do número $\sigma$

Esta representação do número $\alpha$ como $\sigma m \times \beta^e$ chamaremos de representação normal em ponto flutuante na base $\beta$. Em geral a base fica clara pelo contexto!

Números de máquina

Continuamos com a base fixa ($\beta$), mas na representação normal em ponto flutuante vamos admitir apenas números com a mantissa limitada a $D$ dígitos e o expoente limitado, em módulo, por um número inteiro $M$. O conjunto $$\mathbf{M} = \left\{ [0.d_1\cdots d_D]_{\beta}\times \beta^e: |e| \leq M \right\}$$ é um conjunto de números de máquina definido pelos números $(\beta, D, M)$. Este é um conjunto finito com $(\beta-1)(\beta^{(D-1)})(2M+1)$ elementos. Vamos agora definir a função arredondamento, que é uma função sobrejetora $\operatorname{rd}: \mathbb{R} \to \mathbf{M}$. Seja $\alpha$ um número real; se o expoente de $\alpha$ for maior que $M$ não representamos o número. Senão tomamos sua mantissa e se o dígito $b_{d+1}\geq \beta/2$ escolhemos o menor número de máquina maior que $\alpha$ para representá-lo. No caso de $b_{d+1} <\beta/2$ o representante será o maior número de máquina menor que $\alpha$.

Se denotarmos por $\underline{\alpha}$ o truncamento do número $\alpha$, isto é, o maior número de máquina menor que $\alpha$. E por $\overline{\alpha}$ o menor número de máquina maior que $\alpha$. Temos que: $$\overline{\alpha} - \underline{\alpha} = \beta^{e-D}$$ Com isto temos uma avaliação do erro absoluto e erro relativo do arredondamento: $$|\alpha -\operatorname{rd}(\alpha)| \leq \frac{\beta^{e-D}}{2}$$ $$\frac{|\alpha -\operatorname{rd}(\alpha)|}{|\alpha|}\leq \frac{\beta^{1-D}}{2}$$

Aritmética de números em pontos flutuantes

A extensão das operações aritméticas de soma e multiplicação de números reais faz-se pelo arredondamento: $$\alpha \oplus \beta = \operatorname{rd}( \operatorname{rd}(\alpha) + \operatorname{rd}(\beta))$$ $$\alpha \otimes \beta = \operatorname{rd}( \operatorname{rd}(\alpha) \times \operatorname{rd}(\beta))$$ Estas operações deixam de ser associativas.

Aproximações usando polinômios de Taylor

Para fazer as avaliações de funções de variável real, utilizaremos apenas as operações aritméticas. Basicamente, isto significa que só usaremos polinômios. Em primeiro lugar veremos o método de avaliação de Horner.

Método de Horner

É a forma de se avaliar o polinômio num ponto dado executando o menor número de operações aritméticas. O polinômio da forma $$p(x) =a_nx^n+ a_{n-1}x^{n-1}+\cdots + a_0$$ no ponto $x_0$ é avaliado na ordem $$p(x)= [[[[a_nx_0 + a_{n-1}]x_0+a_{n-2}]x_0+\cdots]x_0 +a_0]$$ Isto é, calculamos a sequência

• $A_0 = a_n$
• $A_{k+1} = A_kx_0+ a_{n-k}$ até o $A_n$ que é a avaliação.

Teorema de Taylor

Teorema: Seja $f:(a,b) \to \mathbb{R}$ uma função de classe $\mathcal{C}^r$, talque exista a derivada $f^{(r+1)}(c), \forall c \in (a,b)$. Então para todo $x$ do intervalo, e $c$ fixado existe $\xi \in |c,x|$ tal que: $$f(x) = f(c) + f^\prime(c)(x-c)+ \cdots + \frac{f^{(r)}(c)}{r!}(x-c)^{r} + \frac{f^{(r+1)}(\xi)}{(r+1)!}(x-c)^{r+1}$$

Zeros de funções

Dada uma função $f:(a,b)\to \mathbb{R}$, queremos encontrar um $r\in (a,b)$ tal que $f(r)=0$. Um tal número será chamado de zero da função $f$. Para assegurar a existência de zeros no intervalo, precisamos de alguma regularidade da função. Se $f$ é uma função contínua, uma condição suficiente para a existência do zero é que $f(a)*f(b) < 0$, e uma técnica para chegar ao zero é ir contraindo este intervalo, mantento a relação $f(a)*f(b) < 0$, até chegarmos suficientemente próximo. No método da bissecção vamos dividindo o intervalo ao meio. Se $(a_n,b_n)$ é o intervalo com $f(a_n)*f(b_n) < 0$, definimos $x_{n+1} = (a_n+b_n)/2$ e o novo intervalo como:

• $(a_{n+1},b_{n+1})=(x_{n+1},b_n)$ se $f(a_n)*f(x_{n+1}) < 0$
• $(a_{n+1},b_{n+1})=(a_n,x_{n+1})$ caso contrário

O tamanho do intervalo no n-ésimo passo é $|b-a|/2^n$. A seguir uma função em python que implementa a bissecção.