week_5_intep_approx.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-78f75b2228a73d9d",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# I. Аппроксимация методом наименьших квадратов (линейный случай)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-a5dbb9bfecbe8783",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Рассмотрим функцию $y = f(x)$ определенной набором значений $y_0, y_1, \\cdots, y_n$ в точках $x_0, x_1, \\cdots, x_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-f5815a6aff49a678",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "x = [-1, -0.7, -0.43, -0.14, -0.14, 0.43, 0.71, 1, 1.29, 1.57, 1.86, 2.14, 2.43, 2.71, 3]\n",
    "y = [-2.25, -0.77, 0.21, 0.44, 0.64, 0.03, -0.22, -0.84, -1.2, -1.03, -0.37, 0.61, 2.67, 5.04, 8.90]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-98a91662e46cdd3a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### I.I. Найдите многочлен наилучшего приближения.\n",
    "\n",
    "$$\n",
    "P_m(x) = a_0 + a_1 x + \\cdots + a_m x^m\n",
    "$$\n",
    "\n",
    "используйте линейный метод наименьших квадратов. С его помощью\n",
    "\n",
    "1. реализуйте алгоритм, создающий  \"design matrix\", используя $1, x, \\cdots, x^m$ в качестве базисных функций.\n",
    "\n",
    "2. постройте явно нормальную систему уравнений задачи наименьших квадратов при фиксированных значениях $m$.\n",
    "\n",
    "3. решите систему уравнений, чтобы найти коэффициенты $P_m(x)$ для $m = 0, 1, 2, \\dots$. Для решения задач линейной алгебры можете использовать либо библиотечные функции (`numpy.linalg.solve`), либо Вашу реализацию LU - разложение из 1 недели.\n",
    "\n",
    "(20% итоговой оценки)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-5b4328bd5bb8a1fc",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-f6f0f84795c73024",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### I.II \n",
    "\n",
    "Чтобы найти оптимальное значение $m$, используйти следующий критерий: возьмем $m=0, 1, 2, \\dots$, для каждого значения $m$ вычислим\n",
    "\n",
    "$$\n",
    "\\sigma_m^2 = \\frac{1}{n - m} \\sum_{k=0}^n \\left( P_m(x_k) - y_k \\right)^2\n",
    "$$\n",
    "\n",
    "и возьмем такое значение $m$, при котором $\\sigma_m$ стабилизируется или начинает расти.\n",
    "\n",
    "(20% итоговой оценки)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-6cda17a3a0e12e9b",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-57e0268e519fef92",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "Постройте ваши полиномы $P_m(x)$ вместе с данными. Визуально сравните полиномы различных степеней. Согласуется ли визуальное сравнение с ожидаемым оптимальным значением $m$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-e0c699a43acea547",
     "locked": false,
     "points": 1,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-ca71c0d238bdffd2",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### I.III. МНК с использовнием QR - разложениея.\n",
    "\n",
    "Для оптимального значения $m$ из предыдущей части решите задачу МНК, используя безматричную реализацию QR - разложения. Для решения задач линейной алгебры можете использовать библиотечные функции (обратите внимание на `numpy.linalg.solve`, `numpy.linalg.qr` и т.д.) или код предыдущих недель.\n",
    "Сравните результат с ответом, полученным при решении системы уравнений.\n",
    "\n",
    "(20% итоговой оценки)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-6a13331259d49d1f",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-af0193379161e7dd",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# II. Интерполяция при помощи полиномов Лагранжа."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-7017c4fddb92f038",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### II.1 \n",
    "\n",
    "Рассмотрим функцию $f(x) = x^2 \\cos{x}$. На интервале $x\\in [\\pi/2, \\pi]$, интерполируйте функцию, используя полиномы Лагранжа степени $m$, где $m=1, 2, 3, 4, 5$. Используйте равномерную сетку. Постройте результат интерполяции вместе с $f(x)$.\n",
    "\n",
    "(20% итоговой оценки)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-b037b38543ee78b1",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-70dc7921d6ab0007",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### II.2. \n",
    "\n",
    "Повторите предыдущее задание, используя узлы Чебышева. Сравните качество интерполяции на равномерной сетке и на узлах Чебышева для $m=3$.\n",
    "\n",
    "(20% итоговой оценки)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-7a747da828035bb3",
     "locked": false,
     "points": 2,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# ... ENTER YOUR CODE HERE ..."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}