Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 1 de 11
RespostasdaListadeExercı́ciospara
a1ªProvadeCá lculoNumé rico
1. Fale sobre e descreva a representação dos números reais e inteiros em um
computador.
O computador é uma máquina finita, ou seja, seus elementos são
finitos (memória, processador, etc.) e assim as coisas que ele
consegue representar ou simbolizar são também finitas. Isso cria
um problema, pois os números com os quais trabalhamos são
infinitos. Podemos continuar contando para sempre e não
acabaríamos. Essa limitação deve ser sempre levada em conta no
trabalho com computadores.
Especificamente, quando estamos representando números reais,
temos o chamado “ponto flutuante”:
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
1
0
1
1
1
2
1
3
1
4
mantissa
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
3
1
3
2
expoente
Figura 1 - Uma word de memória mapeada para um número real
São dois inteiros combinados para fazer o número real. O
primeiro inteiro é a precisão e o segundo a escala (tamanho) do
número. No exemplo da Figura 1, a precisão tem 24 bits e a
escala 8 bits, com os números representados na forma:
mantissa × 2
.
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 2 de 11
Por exemplo: 0,9837234 × 10
(100101100001101010110010 x
20000100) é a representação de 9837,234. Note que para escrever
um número real infinito em sua precisão, estamos usando
números inteiros e finitos para fazer uma aproximação.
No caso dos números inteiros com sinal, temos:
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
1
0
1
1
s
i
n
a
l
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
3
1
3
2
Número
Figura 2 - Uma word de memória mapeada para um inteiro com sinal
O menor número inteiro com sinal que conseguimos representar
dessa forma é −2$%& e o maior 2$%& − 1, onde n é o número de bits.
Notar que um bit fica reservado para o sinal e é descontado.
Assim, para 32 bits, temos um range
(faixa de valores) de -
2.147.483.648 até 2.147.483.647 (note que o maior vai até “7”
e não “8”, porque um bit foi perdido para representar o sinal).
Se adicionarmos +1 ao valor maior, começamos tudo de novo, a
partir do menor valor do range (overflow). Por outro lado, se
subtrairmos -1 do menor valor, vamos chegar ao maior valor do
range (underflow).
2. Descreva o Método da Bisseção (finalidade, passo-a-passo e características).
O Método da Bisseção é um dos métodos mais simples, mais
robustos e demorados para encontrar raízes de funções. Na
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Página 3 de 11
Figura 3, veja que é fácil encontrar a raiz só de olhar, pois onde
isso acontece, a função muda de sinal. Esse método se baseia
justamente na mudança de sinal para perseguir a raiz da
função.
Figura 3 – Ilustração do Método da Bisseção
O método vai “cercando” a raiz a partir de um intervalo inicial
que vai diminuindo sempre pela metade (bisseção), até que a
solução seja tão próxima da raiz (dentro de uma tolerância), que
possamos aceitar o valor como uma resposta.
Passo a passo:
1. Definir um intervalo para procurar a raiz: xe e xd (à
esquerda e à direita da raiz);
2. Criar um terceiro ponto no meio do intervalo, xr, que é o
candidato à raiz, da seguinte forma:
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 4 de 11
'( =
'* + ',
2
3. Se f.x /f.x0 / < 0
', = '(
Caso contrário
'* = '(
Se |3.'( /| ≤ 567 então
o '( é a solução, então pare!
Caso contrário, volte para 2 e continue até achar ou exceder o
número máximo de iterações.
É fundamental escolher um intervalo inicial que se tenha
certeza de conter a raiz, caso contrário o algoritmo pode ficar
infinitamente procurando sem nunca achar (loop infinito).
Note que no Passo 4 perguntamos se o valor absoluto da função
avaliada no ponto '( (candidato à raiz da função) é menor que
uma certa tolerância. Isso é importante porque nunca devemos
basear nossos métodos numa comparação com pontos singulares,
como um “zero”, mas sempre com intervalos tão pequenos quanto
possível. Se perguntássemos à máquina se esse valor é “zero”, ou
seja, se acertamos na “mosca”, muito dificilmente a respostas
seria “sim”. Sendo assim, temos que perguntar “está próximo o
suficiente?” e esse é o papel da tolerância. Se a função nesse
ponto estiver dentro da tolerância (menor ou igual a ela), então
encontramos a resposta.
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Página 5 de 11
3. Descreva o Método de Newton-Raphson (finalidade, passo-a-passo e
características).
O Método de Newton-Raphson também é um método para
encontrar raízes de funções. Ao contrário do Método da Bisseção,
ele é normalmente rápido para achar a raiz.
Ele se baseia em substituições da função3.'/ por sua reta
tangente, combinando as ideias básicas de linearizações e
interações sucessivas.
Para estabelecer uma expressão analítica para o cálculo de
sucessivas aproximações à raiz da função (Figura 4), observamos
que a tangente do ângulo θ pode ser obtida pela derivada de
3.'/no ponto '8 (inclinação da reta tangente).
Figura 4 – Ilustração do Método de Newton-Raphson
Assim, a seguinte expressão pode ser obtida:
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Página 6 de 11
tan 9 =
3.'$ /
= 3 ; .'$ /
'$ − '$:&
Sendo 3 ; .'/ a derivada da função 3.'/. Da expressão acima
podemos encontrar uma expressão para cada nova aproximação
da raiz, '$:& :
'$:& = '$ −
3.'$ /
3 ; .'$ /
Tudo o que precisamos para começar é um ponto inicial, que
será nossa primeira estimativa para a raiz e, daí por diante, o
próprio algoritmo deve conduzir até a solução.
Passo-a-passo:
1. Definir um valor candidato à raiz inicial, '8 e uma
tolerância tol;
2. Obter um novo candidato à raiz através de:
'$:& = '$ −
3.'$ /
3 ; .'$ /
3. Testar se |3.'$:& /| ≤ 567, então '$:& é a raiz, caso contrário
voltar ao passo 2 e obter um novo candidato.
4. Descreva o Método da Eliminação de Gauss (finalidade, passo-a-passo e
características).
O Método da Eliminação de Gauss é o método direto mais
comum. Ele consiste na aplicação das operações básicas de troca
da ordem das equações no sistema, multiplicação de uma
equação do sistema por uma constante não nula, adições de
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 7 de 11
equações do sistema, etc., de uma forma ordenada para deixar o
sistema na forma de uma matriz triangular superior, que é um
formato
conveniente
para
depois
ser
resolvido
por
simples
substituições retroativas.
Considere o seguinte sistema genérico como exemplo:
=&& '& + =&> '> + =&? '? = @&
< =>& '& + =>> '> + =>? '? = @>
=?& '& + =?> '> + =?? '? = @?
A solução pelo Método da Eliminação de Gauss necessita de
algumas etapas sucessivas, descritas a seguir:
1ª Etapa: Escrever a matriz aumentada AB = CD|EF:
=&&
GB = H=>&
=?&
=&>
=>>
=?>
=&? @& K&
=>? I@> J K>
=?? @? K?
2ª Etapa: Utilizar como pivô =&& (primeiro elemento da diagonal)
para gerar um fator multiplicativo das linhas 2 e 3 da matriz
aumentada:
M
M
L>& = MNO e L?& = MPO
OO
OO
3ª Etapa: Multiplicar cada pivô pela primeira linha da matriz
e subtrair da respectiva linha, ou seja:
K> = K> − L>& × K& e K? = K? − L?& × K& , resultando em:
G&
=&&
=&>
=&?
@&
K&
= QC=>& − L>& × =&& F C=>> − L>& × =&> F C=>? − L>& × =&& F RC@> − L>& × @& FS K>
C=?& − L?& × =&& F C=?> − L?& × =&> F C=?? − L?& × =&? F C@? − L?& × @& F K?
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 8 de 11
=&&
GT = Q 0
0
=&>
=&>>
=&?>
=&? @& K
&
=&>? R@>& S K>
=&?? @?& K?
Onde o sobrescrito “1” indica que o elemento já passou pela
primeira transformação (matriz aumentada GT ).
4ª Etapa: Tomar o segundo pivô, =>> , que é o segundo elemento
da diagonal, e repetir as Etapas 2 e 3:
M
Com L?> = MPN
NN
Fazer K? = K? − L?> × K> :
=&&
G> = Q 0
0
=&>
=&?
@&
K&
=&>>
=&>?
@>&
S K>
R
C=&?> − L?> × =&>> F C=&?? − L?> × =&>? F C@?& − L?> × @>& F K?
Ou
=&&
G> = Q 0
0
=&>
=&>>
0
=&? @& K&
=&>? R@>& S K>
>
=??
@?> K?
Onde o sobrescrito “2” indica que o elemento já passou pela
segunda transformação (matriz aumentada GU ). Esse sistema é
equivalente a:
=&& '&
V 0
0
=&> '>
=&>> '>
0
=&? '? @&
=&>? '? = @>&
>
=??
'? @?>
Do qual é fácil perceber que se começarmos pela última equação:
>
=??
'? = @?>
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Página 9 de 11
'? = @?>
>
=??
Se pegarmos esse valor de '? e substituirmos na penúltima
equação
e
assim
por
diante,
do
fim
para o
começo,
substituições retroativas, obteremos todos os valores de 'W .
em
Resumindo: primeiro fazemos uma eliminação das variáveis do
começo para fim de modo a obter um sistema triangular
superior. Depois, do fim para o começo, fazemos as substituições
no sistema transformado para obter os valores dos 'W .
5. Na busca pela raiz da equação 3.'/ = ' ? − 3' > + 4' + 12 pelo Método da
Bisseção, começando com '* = −10,0 e ', = 5,0, ache o primeiro '(
(candidato à raiz) e os valores de '* ,', e '( dos dois passos seguintes.
Primeiro passo
•
•
•
•
'( =
%&8:X
>
= −2,5;
3.'* / = −1328;
3.'( / = −32,375;
3.', / = 82,0;
Com esse resultado, sabemos que a raiz está onde o sinal da
função mudou: entre '( e ', . Assim, o '( vai virar o novo '* e ',
fica como está, então temos:
•
•
•
'* = −2,5;
'( = %>,X:X
>
', = 5
= 1,25;
2º Passo, avaliando novamente em 3.'/, temos:
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
•
•
•
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Página 10 de 11
3.'* / = −32,375;
3.'( / = 14,265625;
3.', / = 82,0;
Com esse resultado, sabemos que a raiz está onde o sinal da
função mudou: entre '* e '( . Assim, o '( vai virar o novo ', , e
ficamos com:
•
•
•
'* = −2,5;
'( = %>,X:&,>X
>
', = 1,25;
= −0,625;
6. Na busca pela raiz da mesma equação acima, pelo Método de NewtonRaphson (lembre-se que vai precisar da derivada!), encontre o próximo valor
do candidato à raiz, '$*Z , quando '[\, = −3,0.
'$*Z = '[\, −
'$*Z = −3,0 −
3.'[\, /
3 ; .'[\, /
.−3,0/? − 3 × .−3,0/> + 4 × .−3,0/ + 12
=
3 × .−3,0/> − 6.−3,0/ + 4
−54
'$*Z = −3,0 − ]
^ = −1,8979
48
7. Dado o Sistema de Equações Lineares Algébricas (SELA):
2'&
−'&
'&
+
+
−
3'>
'>
8'>
−
+
−
'?
4'?
'?
=
=
=
0
3
1
Encontre o primeiro pivô e realize o primeiro conjunto de transformações sobre
a matriz aumentada, para deixá-la na forma triangular superior, que é a
primeira etapa no Método da Eliminação de Gauss.
Respostas da Lista de Exercícios para a 1ª
Prova de Cálculo Numérico
Lista para Prova de Cálculo Numérico,
Lista 01, Rev. 01
Data: 18/9/2012
Página 11 de 11
O primeiro pivô é o elemento =&& , ou seja: 2. Com ele, o temos os
fatores L>& =
MNO
MOO
=−
&
>
e L?& =
transformar as linhas K& e K> :
MPO
MOO
&
>
= . Com esses fatores, vamos
K> = K> − L>& × K&
1
1
1
1
K> = _−1 − ]− × 2^` _1 − ]− × 3^` _4 − ]− × −1^` _3 − ]− × 0^`
2
2
2
2
5 7
K> = C0F _ ` _ ` C3F
2 2
Já K?
K? = K? − L?& × K&
1
1
1
1
K? = _1 − ] × 2^` _−8 − ] × 3^` _−1 − ] × −1^` _1 − ] × 0^`
2
2
2
2
K? = C0F _−
19
1
` _− ` C1F
2
2
Assim nosso primeiro sistema equivalente fica da forma
2'&
0
0
+
3'>
5
+
'
2 >
19
−
'
2 >
−
'?
7
+
'
2 ?
1
−
'
2 ?
= 0
= 3
= 1
Que é o primeiro conjunto de transformações sobre o sistema
original.