---------------
#  Aufgabe 1  #
---------------

Die Loesungen von z^p = 1 sind gegeben durch 

w = w_k = exp(2*pi*i*k/p)    mit k=0,...,p-1

denn es ist w_k^p = exp(2*pi*i*k) = 1. 
Machen wir einen R-Plot fuer p=6:


p = 6
w0 = 1 + 0*1i
plot( w0 , xlim=c(-2,2), ylim=c(-2,2) )
for(k in 1:(p-1))
{
  w = exp(2*pi*1i*k/p)
  points( w )
}



---------------------------
#                         #
#    Aufgabe 2 a,b,c,d    #
#                         #
---------------------------


--------
#  2a  #
--------

dx = 0.01
dy = 0.01
x = seq( from=-2, to=2, by=dx)     
y = seq( from=-2, to=2, by=dy)    

nmax = 100                 # maximale Anzahl an Newton-Iterationen
eps = 0.00001              # wenn eine Nullstelle mit dieser Genauigkeit 
                           # erreicht wird, wird abgebrochen
p = 2

# fuer p=2 haben wir die zwei Nullstellen
w1 =  1 + 0*1i
w2 = -1 + 0*1i

z0 = 0+1i*0
plot(z0,xlim=c(-2,2),ylim=c(-2,2))    # alle farbigen z0's werden zu diesem 
                                      # plot mit points() hinzugefuegt
for( xx in x )
{
  for(yy in y )
  {
    z0 = xx + 1i*yy
    z = z0                 # Startwert fuer Newton-Iteration
    n = 0                  # Zaehler fuer Newton-Iteration
    if(abs(z)==0)
      n = nmax
    # wir iterieren solange, bis wir eine Nullstelle mit 
    # Genauigkeit epsilon erreicht haben, oder bis die 
    # maximale Zahl an Iterationen erreicht ist. Im letzteren 
    # haben wir keine Konvergenz, und das zugehoerige z0 wird 
    # weiss gefaerbt. Haben wir die Nullstelle w1 erreicht, 
    # wird der zugehoerige Startwert z0 blau gefaerbt. Haben 
    # wir die Nullstelle w2 erreicht, wird der zugehoerige 
    # Startwert gelb eingefaerbt:

    while( abs(z-w1)>eps & abs(z-w2)>eps & n < nmax )
    {
      z = z - (z^p-1)/(p*z^(p-1))        # die Newton-Iteration
      n = n + 1
      if(abs(z)==0)
        n = nmax
    }

    # wenn der while-loop verlassen wird, kann das aus 3 Gruenden 
    # passieren: 

    # 1) die Nullstelle w1 ist erreicht:        # wenn nach einem if nur eine
    if( abs(z-w1)<eps )                         # code-Zeile kommt, kann man  
      points( z0 , pch="." , col="blue" )       # die { ... } weglassen

    # 2) die Nullstelle w2 ist erreicht:
    if( abs(z-w2)<eps )
      points( z0 , pch="." , col="yellow" )

    # 3) die maximale Anzahl an Iterationen ist erreicht, es wuerde 
    # keine Nullstelle getroffen, keine Konvergenz:
    if( n==nmax )
      points( z0 , pch="." , col="white" )
  }
}



--------
#  2b  #
--------

dx = 0.01
dy = 0.01
x = seq( from=-2, to=2, by=dx)     
y = seq( from=-2, to=2, by=dy)    

nmax = 100                 # maximale Anzahl an Newton-Iterationen
eps = 0.00001              # wenn eine Nullstelle mit dieser Genauigkeit 
                           # erreicht wird, wird abgebrochen
p = 3

# fuer p=3 haben wir die drei Nullstellen
w0 =  1 + 0*1i
w1 = exp(2*pi*1i/3)
w2 = exp(2*pi*1i*2/3)

z0 = 0+1i*0
plot(z0,xlim=c(-2,2),ylim=c(-2,2))    # alle farbigen z0's werden zu diesem 
                                      # plot mit points() hinzugefuegt
for( xx in x )
{
  for(yy in y )
  {
    z0 = xx + 1i*yy
    z = z0                 # Startwert fuer Newton-Iteration
    n = 0                  # Zaehler fuer Newton-Iteration
    if(abs(z)==0)
      n = nmax

    while( abs(z-w0)>eps & abs(z-w1)>eps & abs(z-w2)>eps & n < nmax )
    {
      z = z - (z^p-1)/(p*z^(p-1))        # die Newton-Iteration
      n = n + 1
      if(abs(z)==0)
        n = nmax
    }

    # wenn der while-loop verlassen wird, kann das aus 4 Gruenden 
    # passieren: 

    # 0) die Nullstelle w0 ist erreicht:
    if( abs(z-w0)<eps )
      points( z0 , pch="." , col="green" )   # sieht mit gruen besser aus..

    # 1) die Nullstelle w1 ist erreicht:        
    if( abs(z-w1)<eps )                          
      points( z0 , pch="." , col="red" )       

    # 2) die Nullstelle w2 ist erreicht:
    if( abs(z-w2)<eps )
      points( z0 , pch="." , col="yellow" )

    # 3) die maximale Anzahl an Iterationen ist erreicht, es wuerde 
    # keine Nullstelle getroffen, keine Konvergenz:
    if( n==nmax )
      points( z0 , pch="." , col="white" )
  }
}



--------
#  2c  #
--------

dx = 0.01
dy = 0.01
x = seq( from=-2, to=2, by=dx)     
y = seq( from=-2, to=2, by=dy)    

nmax = 100                 # maximale Anzahl an Newton-Iterationen
eps = 0.00001              # wenn eine Nullstelle mit dieser Genauigkeit 
                           # erreicht wird, wird abgebrochen
p = 4

# fuer p=4 haben wir die vier Nullstellen
w0 =  1 + 0*1i
w1 = exp(2*pi*1i/4)
w2 = exp(2*pi*1i*2/4)
w3 = exp(2*pi*1i*3/4)

z0 = 0+1i*0
plot(z0,xlim=c(-2,2),ylim=c(-2,2))    # alle farbigen z0's werden zu diesem 
                                      # plot mit points() hinzugefuegt
for( xx in x )
{
  for(yy in y )
  {
    z0 = xx + 1i*yy
    z = z0                 # Startwert fuer Newton-Iteration
    n = 0                  # Zaehler fuer Newton-Iteration
    if(abs(z)==0)
      n = nmax

    while( abs(z-w0)>eps & abs(z-w1)>eps & abs(z-w2)>eps & abs(z-w3)>eps & n < nmax )
    {
      z = z - (z^p-1)/(p*z^(p-1))        # die Newton-Iteration
      n = n + 1
      if(abs(z)==0)
        n = nmax
    }

    # wenn der while-loop verlassen wird, kann das aus 5 Gruenden 
    # passieren: 

    # 0) die Nullstelle w0 ist erreicht:
    if( abs(z-w0)<eps )
      points( z0 , pch="." , col="green" )   

    # 1) die Nullstelle w1 ist erreicht:        
    if( abs(z-w1)<eps )                          
      points( z0 , pch="." , col="red" )       

    # 2) die Nullstelle w2 ist erreicht:
    if( abs(z-w2)<eps )
      points( z0 , pch="." , col="blue" )

    # 3) die Nullstelle w3 ist erreicht:
    if( abs(z-w3)<eps )
      points( z0 , pch="." , col="yellow" )

    # 4) die maximale Anzahl an Iterationen ist erreicht, es wuerde 
    # keine Nullstelle getroffen, keine Konvergenz:
    if( n==nmax )
      points( z0 , pch="." , col="white" )
  }
}



--------
#  2d  #
--------

dx = 0.01
dy = 0.01
x = seq( from=-2, to=2, by=dx)     
y = seq( from=-2, to=2, by=dy)    

nmax = 100                 # maximale Anzahl an Newton-Iterationen
eps = 0.00001              # wenn eine Nullstelle mit dieser Genauigkeit 
                           # erreicht wird, wird abgebrochen
p = 12

# wir haben p Nullstellen:
pp = 1:p
w = exp(2*pi*1i*pp/p)      # ist Vektor der Laenge p
w
plot(w)                    # looks ok

z0 = 0+1i*0
plot(z0,xlim=c(-2,2),ylim=c(-2,2))    # alle farbigen z0's werden zu diesem 
                                      # plot mit points() hinzugefuegt
# wir brauchen p verschiedene Farben: 
# da die erste und die letzte Farbe der rainbow-Farbpalette beides rot ist, 
# benutzen wir rainbow(p+1), dann ist die p-te Farbe rosa:

mycolors = rainbow(p+1)

for( xx in x )
{
  for(yy in y )
  {
    z0 = xx + 1i*yy
    z = z0                 # Startwert fuer Newton-Iteration
    n = 0                  # Zaehler fuer Newton-Iteration
    if(abs(z)==0)
      n = nmax
    
    mindiff = 999999       # Minimum der Abstaende zu den Nullstellen
    while( mindiff > eps & n < nmax )
    {
      z = z - (z^p-1)/(p*z^(p-1))        # die Newton-Iteration
      for(k in 1:p)
        mindiff = min( mindiff , abs(z-w[k]) )
      
      n = n + 1
      if(abs(z)==0)
        n = nmax
    }

    # wenn der while-loop verlassen wird, kann das aus 2 Gruenden 
    # passieren: 

    # 1) eine Nullstelle wurde erreicht:
    if( mindiff < eps )
    {
      k = which.min( abs(z-w) )         
      #                 (Zahl-Vektor) ist Vektor, der kleinste Eintrag ist an Position k 
      #                  -> die k-te Einheitswurzel wurde getroffen: 
      points( z0 , pch="." , col=mycolors[k] )  
    }            

    # 2) die maximale Anzahl an Iterationen ist erreicht, es wuerde 
    # keine Nullstelle getroffen, keine Konvergenz:
    if( n==nmax )
      points( z0 , pch="." , col="white" )
  }
}




# der obige code funktioniert fuer p=12, aber liefert etwa fuer p=16  
# eine Fehlermeldung. Der folgende code funktioniert auch fuer p=16: 


# mit etwas hoeherer Aufloesung, dauert ein bischen.. :

dx = 0.005
dy = 0.005
x = seq( from=-2, to=2, by=dx)     
y = seq( from=-2, to=2, by=dy)    

nmax = 200                 # maximale Anzahl an Newton-Iterationen
eps = 0.0000001            # wenn eine Nullstelle mit dieser Genauigkeit 
                           # erreicht wird, wird abgebrochen
p = 16

# wir haben p Nullstellen:
pp = 1:p
w = exp(2*pi*1i*pp/p)      # ist Vektor der Laenge p
w
plot(w)                    # looks ok

z0 = 0+1i*0
plot(z0,xlim=c(-2,2),ylim=c(-2,2))    # alle farbigen z0's werden zu diesem 
                                      # plot mit points() hinzugefuegt
# wir brauchen p verschiedene Farben: 
# da die erste und die letzte Farbe der rainbow-Farbpalette beides rot ist, 
# benutzen wir rainbow(p+1), dann ist die p-te Farbe rosa:

mycolors = rainbow(p+1)

for( xx in x )
{
  for(yy in y )
  {
    z0 = xx + 1i*yy
    z = z0                 # Startwert fuer Newton-Iteration
    n = 0                  # Zaehler fuer Newton-Iteration
    if(abs(z)==0 || abs(z)>999999999999)
      n = nmax
    
    mindiff = 999999       # Minimum der Abstaende zu den Nullstellen
    while( mindiff > eps & n < nmax )
    {
      z = z - (z^p-1)/(p*z^(p-1))        # die Newton-Iteration
      for(k in 1:p)
        mindiff = min( mindiff , abs(z-w[k]) )
      
      n = n + 1
      if(abs(z)==0 || abs(z)>999999999999)
        n = nmax
    }

    # wenn der while-loop verlassen wird, kann das aus 2 Gruenden 
    # passieren: 

    # 1) eine Nullstelle wurde erreicht:
    if( mindiff < eps )
    {
      k = which.min( abs(z-w) )         
      #                 (Zahl-Vektor) ist Vektor, der kleinste Eintrag ist an Position k 
      #                  -> die k-te Einheitswurzel wurde getroffen: 
      points( z0 , pch="." , col=mycolors[k] )  
    }            

    # 2) die maximale Anzahl an Iterationen ist erreicht, es wuerde 
    # keine Nullstelle getroffen, keine Konvergenz:
    if( n==nmax )
      points( z0 , pch="." , col="white" )
  }
}