БДЗ задание 16(9)

GradSolve.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перенесем все в системе из правой части в левую, получаем систему\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "f_1(x, y) = 0 \\\\\n",
    "f_2(x, y) = 0\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Дальше решаем методом градиентного спуска."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "EPS = 0.001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f1(X):\n",
    "    return (X[0][0] ** 2) + 2 * X[0][0] * X[1][0] + 2 * (X[1][0] ** 2) - 4\n",
    "\n",
    "def f2(X):\n",
    "    return X[0][0] + X[1][0] - np.exp(X[1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def df1dx(X):\n",
    "    return 2 * X[0][0] + 2 * X[1][0]\n",
    "\n",
    "def df1dy(X):\n",
    "    return 2 * X[0][0] + 4 * X[1][0]\n",
    "\n",
    "def df2dx(X):\n",
    "    return 1\n",
    "\n",
    "def df2dy(X):\n",
    "    return 1 - np.exp(X[1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(X):\n",
    "    return np.array([[f1(X)], [f2(X)]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def J(X):\n",
    "    return np.array([\n",
    "        [df1dx(X), df1dy(X)],\n",
    "        [df2dx(X), df2dy(X)],\n",
    "    ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mu(J, F):\n",
    "    tmp = J @ J.T @ F\n",
    "    return ((F.T @ tmp) / (tmp.T @ tmp))[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def norm(X):\n",
    "    return np.sqrt((X.T @ X)[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def descent(X):\n",
    "    Xp = np.copy(X)\n",
    "    Fp = f(Xp)\n",
    "    Jp = J(Xp)\n",
    "    mu_p = mu(Jp, Fp)\n",
    "    it = 0\n",
    "    while True:\n",
    "        if it % 10 == 0:\n",
    "            print(f'Iteration {it}, X={Xp.tolist()} ||f||={norm(Fp)}')\n",
    "        Xp = Xp - mu_p * Jp.T @ Fp\n",
    "        Fp = f(Xp)\n",
    "        \n",
    "        if norm(Fp) < EPS:\n",
    "            print(f'Iteration {it}, X={Xp.tolist()} ||f||={norm(Fp)}')\n",
    "            print('Converges!')\n",
    "            break\n",
    "        \n",
    "        Jp = J(Xp)\n",
    "        mu_p = mu(Jp, Fp)\n",
    "        it += 1\n",
    "        if it > 1000:\n",
    "            print('Does not converge!')\n",
    "            break\n",
    "    return Xp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "Xs = [\n",
    "    np.array([[0], [0]]),\n",
    "    np.array([[1], [1]]),\n",
    "    np.array([[-1], [-1]]),\n",
    "    np.array([[-10], [10]]),\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running descent with X=[[0], [0]]\n",
      "Iteration 0, X=[[0], [0]] ||f||=4.123105625617661\n",
      "Iteration 9, X=[[1.2558431606990426], [0.6392465213457059]] ||f||=3.723631052873236e-05\n",
      "Converges!\n",
      "\n",
      "Finished, Xr=[[1.2558431606990426], [0.6392465213457059]], f=[[1.0180450518149087e-06], [3.722239119219317e-05]], ||f||=3.723631052873236e-05\n",
      "--------------------------------------\n",
      "Running descent with X=[[1], [1]]\n",
      "Iteration 0, X=[[1], [1]] ||f||=1.231230597855036\n",
      "Iteration 10, X=[[1.2305074904330284], [0.6536234369735383]] ||f||=0.04464100790833041\n",
      "Iteration 20, X=[[1.2515162472617607], [0.6417603527635993]] ||f||=0.007493289999423335\n",
      "Iteration 30, X=[[1.2550494328187465], [0.6397121454707032]] ||f||=0.0013399816858530368\n",
      "Iteration 31, X=[[1.2552730748864984], [0.6395820097567084]] ||f||=0.0009513370803318047\n",
      "Converges!\n",
      "\n",
      "Finished, Xr=[[1.2552730748864984], [0.6395820097567084]], f=[[-0.0004590609973553761], [-0.0008332498071534911]], ||f||=0.0009513370803318047\n",
      "--------------------------------------\n",
      "Running descent with X=[[-1], [-1]]\n",
      "Iteration 0, X=[[-1], [-1]] ||f||=2.5703799423280564\n",
      "Iteration 10, X=[[-0.4079096531987968], [-1.122259387022702]] ||f||=1.8981472098889889\n",
      "Iteration 20, X=[[0.8285494497143042], [-1.7438475853404052]] ||f||=1.0968639484616909\n",
      "Iteration 30, X=[[1.4152436468552034], [-1.9587526902902745]] ||f||=0.6971754749863556\n",
      "Iteration 40, X=[[2.1194204482096817], [-1.9931622764242367]] ||f||=0.015140392031010615\n",
      "Iteration 49, X=[[2.130613393427277], [-1.995245690557906]] ||f||=0.000907963057114277\n",
      "Converges!\n",
      "\n",
      "Finished, Xr=[[2.130613393427277], [-1.995245690557906]], f=[[-0.0006702193299750192], [-0.0006125381317209078]], ||f||=0.000907963057114277\n",
      "--------------------------------------\n",
      "Running descent with X=[[-10], [10]]\n",
      "Iteration 0, X=[[-10], [10]] ||f||=22026.67499668959\n",
      "Iteration 10, X=[[-3.9709588643071836], [2.022579863569473]] ||f||=10.270162906173162\n",
      "Iteration 20, X=[[-0.8202238626505393], [-0.809726538031868]] ||f||=2.185894596407133\n",
      "Iteration 30, X=[[-0.36111572249189805], [-1.1498879399526836]] ||f||=1.8697937490830192\n",
      "Iteration 40, X=[[0.8799698423834298], [-1.7623019668008808]] ||f||=1.0603217536789062\n",
      "Iteration 50, X=[[1.4657674320157894], [-1.969429452437899]] ||f||=0.6566695616357558\n",
      "Iteration 60, X=[[2.125036176702674], [-1.994017139173961]] ||f||=0.008460996174373648\n",
      "Iteration 66, X=[[2.1305718344770974], [-1.9954000624706159]] ||f||=0.0007947398630572753\n",
      "Converges!\n",
      "\n",
      "Finished, Xr=[[2.1305718344770974], [-1.9954000624706159]], f=[[-0.00010718274489107671], [-0.0007874790848841073]], ||f||=0.0007947398630572753\n",
      "--------------------------------------\n"
     ]
    }
   ],
   "source": [
    "for X in Xs:\n",
    "    print(f'Running descent with X={X.tolist()}')\n",
    "    Xr = descent(X)\n",
    "    Fr = f(Xr)\n",
    "    print(f'\\nFinished, Xr={Xr.tolist()}, f={Fr.tolist()}, ||f||={norm(Fr)}')\n",
    "    print('--------------------------------------')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dirty 3.7",
   "language": "python",
   "name": "dirty3.7"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}