Departamento de Ciência da Computação – IME-USP

MAC 115 – Introdução à Ciência da Computação

Instituto de Física - Primeiro Semestre de 2004

Segundo Exercício-Programa (EP2) Entregue até 31/5/2004, no pelo Panda.

O Método de Newton em ℂ

O objetivo desse EP é implementar o método de Newton para encontrar raízes complexas de equações.

Já conhecemos o método de Newton para equações reais f(x) = 0. Começamos com um valor arbitrário x_{0} e iteramos

x_{n} = x_{n−1} − \frac{f(x_{n−1})}{f′(x_{n−1})}  (1)

para todo n ≥ 1. Este processo define uma seqüência de reais x_{0}, x_{1}, x_{2}, … que converge (em geral) para uma raiz de f(x) = 0.

O fato crucial para este EP é que o processo acima também funciona quando fazemos as contas em ℂ.

Exemplo

Suponha que queremos encontrar todas as raízes da equação

z^{4} − 1 = 0.  (2)

(Naturalmente, sabemos que as raízes são ±1 e ±i, mas (2) é apenas um exemplo.) Suponha que definimos a seqüência z_{0}, z_{1}, z_{2}, …, colocando

z_{n} = z_{n−1} − \frac{f(z_{n−1})}{f′(z_{n−1})}  (3)

para todo n ≥ 1, e colocando z_{0} = a, b, c, e d, onde

a = 2 + i  b = 1 + 3i  c = −1 − i/2  (4)

e

d = −2 + i  e = −1 − 3i.  (5)

Note que obtemos assim 5 seqüências. Estas seqüências convergem para as raízes ±1 e ±i. (Qual seqüência converge para qual raiz?)

O que seu programa deve fazer

O seu programa deve receber como entrada um inteiro n e números complexos a_{0}, a_{1}, …, a_{n} representando o polinômio

p(z) = a_{0} + a_{1}z + ⋯ + a_{n}z^{n}  (6)

de grau n (a_{n} ≠ 0). A saída do seu programa deve ser composta pelas n raízes de p(z).

No caso do exemplo acima, teremos a entrada e a saída abaixo.

Entrada

A entrada para representar (2) deve ser

4
-1.0  0.0
0.0  0.0
0.0  0.0
0.0  0.0
1.0  0.0

Saída

A saída poderia então ser

1.000  0.000
0.000  1.000
-1.000  0.000
0.000 -1.000

Computação com complexos

Você deve estudar estes programas para implementar aritmética de números complexos: prog2.9.c, prog2.9.Complex.c.

Observações Importantes sobre os Exercícios-Programas

Todos os exercícios-programas devem ter o seguinte cabeçalho:

          /********************************************************/
          /* Fulano de Tal                                        */
          /* Exercicio-Programa xx                                */
          /* Curso yy  - Turma zz  -- Professor:  Ciclano de Tal  */
          /* Computador: .....                                    */
          /* Compilador: .....                                    */
          /********************************************************/

1. O exercício-programa é estritamente individual. Exercícios copiados (com ou sem eventuais disfarces) receberão nota ZERO.

2. Exercícios atrasados não serão aceitos.

3. Exercícios com erros de sintaxe (ou seja, erros de compilação) receberão nota ZERO.

4. É muito importante que seu programa tenha comentários e esteja bem indentado, ou seja, digitado de maneira a ressaltar a estrutura de subordinação dos comandos do programa (conforme visto em aula). A avaliação dos exercícios-programas levará isto em conta.

5. Cada programa deve ser executado tantas vezes quantas forem necessárias para testar todos os casos possíveis para as entradas. Você pode dizer no seu programa (em comentários), quais dados você usou para testar seu programa. A escolha desses dados também influirá na sua nota.

6. Guarde com você até o final do semestre, em seus disquetes, os arquivos de seus programas, pois eles podem ser solicitados pelo professor caso surja alguma dúvida.

7. Entregue o seu programa pelo sistema Panda.