algorithms/linear_equations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Методы решения систем линейных уравнений"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Метод Крамера"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_det(m):\n",
    "    '''\n",
    "    Принимает матрицу - квадратный двумерный numpy array типа float\n",
    "    Возвращает определитель заданной матрицы\n",
    "    '''    \n",
    "    \n",
    "    if len(m) == 2:\n",
    "        return m[0][0] * m[1][1] - m[0][1] * m[1][0]\n",
    "    else:\n",
    "        D = 0\n",
    "        for i in range(len(m)): # i - индекс вычёркиваемого столбца\n",
    "            M = m[0, i]\n",
    "            new_m = []\n",
    "            \n",
    "            for j in range(len(m)):\n",
    "                for k in range(len(m)):\n",
    "                    if (j != 0 and k != i):\n",
    "                        new_m.append(m[j, k])\n",
    "            \n",
    "            new_m = np.array(new_m).reshape((len(m) - 1, len(m) - 1))\n",
    "            \n",
    "            if (i + 1) % 2 == 0:\n",
    "                D += M * get_det(new_m)\n",
    "            else:\n",
    "                D -= M * get_det(new_m)\n",
    "                \n",
    "        return D"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def сramer(A, b):\n",
    "    '''\n",
    "    Приминает на вход две переменные:\n",
    "    A - матрица коэффициентов - квадратный двумерный numpy array типа float\n",
    "    b - вектор свободных членов - numpy array типа float\n",
    "    Вовращает вектор решений\n",
    "    '''\n",
    "    \n",
    "    # считаем главный определитель\n",
    "    D = get_det(A)\n",
    "    \n",
    "    if (D == 0): \n",
    "        print('Решить методом Крамера невозможно (главный определитель = 0)')\n",
    "    else:\n",
    "        # список побочных определителей\n",
    "        dets = []\n",
    "\n",
    "        for i in range(len(A)):\n",
    "            copied_A = np.array(A)\n",
    "            copied_A[:, i] = b\n",
    "            dets.append(get_det(copied_A))\n",
    "\n",
    "        # вектор решений\n",
    "        x = []\n",
    "        for curr_det in dets:\n",
    "            x.append(float(curr_det) / D)\n",
    "\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Метод Гаусса"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gaussian(A, b):\n",
    "    '''\n",
    "    Приминает на вход две переменные:\n",
    "    A - матрица коэффициентов - квадратный двумерный numpy array типа float\n",
    "    b - вектор свободных членов - numpy array типа float\n",
    "    Вовращает вектор решений\n",
    "    '''\n",
    "\n",
    "    # составляем расширенную матрицу системы\n",
    "    reshaped_b = b.reshape((len(b), 1))\n",
    "    A = np.hstack((A, reshaped_b))\n",
    "    \n",
    "    # приводим матрицу к треугольному виду\n",
    "    # i - опорная строка\n",
    "    # j - текущая строка (всегда меньше i)\n",
    "    for i in range(len(A)):\n",
    "        for j in range(i + 1, len(A)):\n",
    "            A[j] -= A[i] * A[j][i] / A[i][i]\n",
    "            \n",
    "    # обратный ход\n",
    "    x = np.array([0] * len(b), dtype=float) # вектор решений\n",
    "\n",
    "    i = len(A) - 1\n",
    "    while i >= 0:\n",
    "        x[i] = (A[i][-1] - sum(x * A[i][0:-1])) / A[i][i] \n",
    "        i -= 1\n",
    "        \n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Тестирование"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A_list = [ [[4, 2, -1],\n",
    "            [5, 3, -2],\n",
    "            [3, 2, -3]],\n",
    "          \n",
    "           [[3, 2, -5],\n",
    "            [2, -1, 3],\n",
    "            [1, 2, -1]] ]             \n",
    "          \n",
    "b_list = [ [1, 2, 0],\n",
    "           [-1, 13, 9] ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# преобразуем python массивы в numpy массивы с нужным типом\n",
    "for A in A_list:\n",
    "    A = np.array(A, dtype=float)\n",
    "    \n",
    "for b in b_list:\n",
    "    b = np.array(b, dtype=float)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Матрица:\n",
      "[4, 2, -1]\n",
      "[5, 3, -2]\n",
      "[3, 2, -3]\n",
      "Вектор свободных членов:\n",
      "[1, 2, 0]\n",
      "Решение методом Крамера:\n",
      "[3.0, 5.0, 4.0]\n",
      "Решение методом Гаусса:\n",
      "[ 3.  5.  4.] \n",
      "\n",
      "Матрица:\n",
      "[3, 2, -5]\n",
      "[2, -1, 3]\n",
      "[1, 2, -1]\n",
      "Вектор свободных членов:\n",
      "[-1, 13, 9]\n",
      "Решение методом Крамера:\n",
      "[3.0, 5.0, 4.0]\n",
      "Решение методом Гаусса:\n",
      "[ 3.  5.  4.] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(A_list)):\n",
    "    print('Матрица:')\n",
    "    for row in A_list[i]:\n",
    "        print(row)\n",
    "    \n",
    "    print('Вектор свободных членов:')\n",
    "    print(b_list[i])\n",
    "    \n",
    "    print('Решение методом Крамера:')\n",
    "    print(сramer(A, b))\n",
    "    \n",
    "    print('Решение методом Гаусса:')\n",
    "    print(gaussian(A, b), '\\n')"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}