Zápočtový úkol 2

Metoda konjugovaných gradientů na funkci dvou proměnných (“banánová funkce”).

Postup metody (viz přednáška):

Pro zopakování této metody se můžete podívat na video zde (algoritmus v Matlabu je ke konci videa..).

Úkol - zápočet 2

Pomocí Metody konjugovaných nalezněte minimum “banánové funkce” (Rosenbrock function):

\[ f(x, y) = (1 - x)^2 + 100 (y - x^2)^2 \]

Srovnejte metodu konjugovaných gradientů a metodu největšího spádu (probrána na cvičení - stačí sem zkopírovat) na této úloze. Vykreslete závislost chyby na počtu iterací pro obě metody (zvolte logaritmickou škálu pro osu \(y\)). Okomentujte rychlost konvergence obou metod.

Vyzkoušejte obě metody s několika různými počátečnými odhady řešení (\(\vec{P}_0\)). Co za chování pozorujete u obou metod? Jak je potřeba změnit koeficient \(\alpha\) u metody největšího spádu, aby metoda konvergovala?

Zvolte dostatečně malý krok (\(h = 10^{-8}\)) při numerickém výpočtu gradientu a dostatečný počet kroků tak, aby jste dostali řešení s přesností \(10^{-8}\) u metody konjugovaných gradientů.

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import fsolve

Definice funkce a jejích derivací

## DOPLŇTE ##

Implementace metody největšího spádu

Zkopírujte ze cvičení..

## DOPLŇTE ##

Implementace metody konjugovaných gradientů

Tip

Krok 3 metody konjugovaných gradientů spočívá v nalezení minima funkce \(f\) v 1D podprostoru určeném směrem \(\vec{h}_{k}\). Pro 1D minimalizaci ve směru \(\vec{h}_k\) a nalezení bodu \(\vec{P}_{k+1}\) můžete použít knihovní funkci optimize.minimize_scalar() (zvolte dostatečně malou toleranci) nebo libovolnou z metod představených na cvičení. Pro použití knihovní funkce je vhodné zadefinovat novou funkci (\(g(t; \vec{x}, \vec{h}) = f(x + h_x t, y + h_y t)\)) s jistým parametrem (např. \(t\)), vůči kterému se provádí optimalizace.

## DOPLŇTE ##

Analýza konvergence

Vykreslete vývoj chyb pro obě metody a okomentujte jak se vývoj liší a proč. Chybu odhadněte pomocí velikosti vektoru \(\vec{g}_{k+1}\).

# ověření konvergence
## DOPLŇTE ##

Vizualizace řešení

Vykreslete jednotlivé iterace řešení do 2D grafu Rosenbrockovy funkce (pro vykreslení funkce využijte contourf()) a také výsledné řešení odlišnou barvou.

## DOPLŇTE ##