#!/usr/bin/env python
# coding: utf-8

# # Problème: projection sur les vecteurs croissants
# 
# <br/>
# <font color='red'><b> Le fichier doit être copié sur l'ordinateur et renommé M315-NUMERODECOPIE</b> </font>
# 
# $\newcommand{\Rsp}{\mathbb{R}}
# \newcommand{\nr}[1]{\Vert#1\Vert}$
# 
# Dans toute la suite, on supposera que $n=30$. On prendra pour vecteur $y$ celui donné ci-dessous. La solution du problème de minimisation (P) a été calculée et est stockée dans le vecteur xsol (ce qui permettra d'étudier la vitesse de convergence des deux algorithmes considérés):

# ** NUMERO DE COPIE: ** (à compléter)

# In[2]:


import numpy as np
import matplotlib.pyplot as plt
get_ipython().run_line_magic('matplotlib', 'inline')

n = 30
t = np.linspace(0,1,n)
y = np.sin(np.pi*t) + 0.05*((-1)*np.ones(n))**np.arange(0,n)
xsol = [0.05, 0.05811901842394177, 0.2649704402110241, 0.26930153013598, 0.4677214793686432, 0.4677214793686432,
        0.6464368370235942, 0.6464368370235942, 0.7078730506579234, 0.7078730506579234, 0.7078730506579218,
        0.7078730506579214, 0.7078730506579185, 0.7078730506579184, 0.7078730506579138, 0.7078730506579139,
        0.7078730506579083, 0.7078730506579083, 0.7078730506579022, 0.7078730506579018, 0.7078730506578964,
        0.7078730506578963, 0.7078730506578907, 0.707873050657891, 0.7078730506578864, 0.7078730506578865,
        0.7078730506578831, 0.7078730506578829, 0.7078730506578809, 0.707873050657881]

plt.plot(t,y)
plt.plot(t,xsol)


# ## Première approche: paramétrisation et gradient projeté
# 
# **QN1.** Calculer la matrice $A$ décrite dans le sujet. Écrire une fonction calculant la projection d'un vecteur $z\in \Rsp^n$ sur le convexe $L = \Rsp\times \Rsp_+^{n-1}$.

# In[ ]:





# **QN2** Implémenter l'algorithme de gradient projeté décrit dans la première partie du sujet:
# - Le pas de temps $\tau$ sera choisi égal à $1/\Lambda_A$ (on rappelle *np.linalg.eigh(B)[0]* permet de calculer les valeurs propres d'une matrice symétrique B).
# - On effectuera $N = 30000$ itérations, et on tracera la courbe d'erreur $k \mapsto \nr{x^{(k)} - xsol}$ en échelle logarithmique.

# In[ ]:





# **QN3** Montrer que si $\tau>\Lambda_A$, alors l'algorithme devient instable.

# In[ ]:





# ## Deuxième approche: dualité algorithme d'Uzawa
# 
# **QN4.** Calculer la matrice $D$ décrite dans le sujet. Écrire une fonction projP calculant la projection d'un vecteur $\lambda \in \Rsp^n$ sur $\Rsp_+^{n-1}$.

# In[ ]:





# **QN5** Implémenter l'algorithme d'Uzawa décrit dans la deuxième partie du sujet:
# - Le pas de temps $\tau$ sera choisi égal à $1$ 
# - On effectuera $N = 3000$ itérations, et on tracera la courbe d'erreur $k \mapsto \nr{x^{(k)} - xsol}$ en échelle logarithmique.
# 
# Dans une deuxième figure, illustrer l'instabilité de l'algorithme d'Uzawa pour $\tau > 1$.

# In[ ]: