##Exercice 1

##1)
#a)

# On a la relation : y_k+1 = y_k + h*F(y_k,t), avec h le pas (h = (b-a)/n)

#b)

def euler(F,a,b,y0,n):          #F une fonction, a,b,y0 des réels, n entier
    y,t,h = y0,a,(b-a)/n       #On initialise les ordonnées et les abcisses, et on calcule le pas
    liste_y = [y0]             #On initialise la liste des ordonnées
    liste_t = [a]              #On initialise la liste des abcisses
    while t<b:                 #On complète la liste des t et y jusqu'à t =b
        y = y+h*F(y,t)          #On crée le yk+1 d'après la définition
        liste_y.append(y)       #On l'ajoute à la liste des y
        t += h                  #On fait de même pour les t
        liste_t.append(t)
    return(liste_t,liste_y)

#c)

# On étudie l'équation y' = y avec y(0) = 1 : on veut donc trouver y(x) = exp(x)

#d)

# La fonction effectue n tours de boucle, dans lesquelles on effectue un produit et deux sommes
# On a donc une complexité d'environ 3n linéaire en n, ou en O(n)

#e)

# On dit que la méthode est d'ordre 1 car une multiplication du nombre de tours de boucles par 10
# entraîne une division par 10 de l'erreur associée à la méthode

##2)

#a)

def dicho(f,a,b,eps):       #f une fonction, a,b,eps des réels
    p,g,r = a,b,(a+b)/2     #On initialise les valeurs hautes, basses et au milieu
    while abs(f(r)) > eps:  #La fonction s'arrête quand on atteint 0 à eps près
        if f(r)*f(p) < 0:   #Si la racine est entre la valeur basse et le milieu:
            g = r           #On modifie la valeur haute
        else: p = r         #Sinon, on modifie la valeur basse
        r = (p+g)/2         #On met à jour la valeur du milieu
    return r

#b)

#On a la relation u_k+1 = u_k - f(u_k)/f'(u_k)

#c)

def derive(f,a):    #f une fonction, a réel
    eps = 1e-9      #On impose une précision de 10^-9
    return (f(a+eps)-f(a))/eps  #On renvoie la valeur approximative de f'(a)

#d)

def newton(f,a):        #f une fonction, a réel
    u = a               #On pose u_0 = a
    for i in range(10): #On itère 10 fois
        u = u - f(u)/derive(f,u)    #On applique la relation de récurrence
    return u            #On renvoie la dernière valeur de u

#e)

# h(y_n+1) vérifie l'équation (E)

#f)

def euler_implicite(F,a,b,y0,n): #F une fonction, a,b,y0,n des réels
    y,t,h = y0,a,(b-a)/n         #On initialise les y,t et on calcule le pas
    liste_t,liste_y = [a],[y0]   #On initialise les listes des t et y
    while t<b:
        t += h
        liste_t.append(t)
        y = newton(lambda x:x-y-h*F(x,t),y) #On résoud l'équation (E) avec newton
        liste_y.append(y)           #On ajoute le y ainsi calculé
    return liste_t,liste_y

##3

#a) Au lieu d'utiliser une fonction F à valeurs réelles, on utilise une fonction
# à valeurs vectorielles : les valeurs y_k sont donc des vecteurs

#b)

from math import sin
import numpy as np

def F(y,t):     #y un vecteur, t un réel
    return np.array((y[1],t*y[0]+sin(y[1])))

euler(F,1,3,np.array((1,0)),100)