Предмет

Математика, страница 11

Формулы по алгебре, геометрии, тригонометрии, началам анализа и вероятности.

Учебные маршруты

756 формул

Все формулы раздела

Показаны 601-660 из 756. Остальные формулы доступны на соседних страницах раздела.

Будущая стоимость одной суммы

Формула «Будущая стоимость одной суммы» связывает денежную сумму, ставку и время. Она показывает, как привести один поток к нужной дате или сравнить ставки с разной частотой начисления.

$FV=PV(1+r)^n$

Эффективная годовая ставка при сложном начислении

Формула «Эффективная годовая ставка при сложном начислении» связывает денежную сумму, ставку и время. Она показывает, как привести один поток к нужной дате или сравнить ставки с разной частотой начисления.

$EAR=(1+\frac jm)^m-1$

Номинальная ставка с начислением m раз в год

Формула «Номинальная ставка с начислением m раз в год» связывает денежную сумму, ставку и время. Она показывает, как привести один поток к нужной дате или сравнить ставки с разной частотой начисления.

$j=m((1+EAR)^{1/m}-1)$

Дюрация Маколея облигации

Формула «Дюрация Маколея облигации» связывает денежную сумму, ставку и время. Она показывает, как привести один поток к нужной дате или сравнить ставки с разной частотой начисления.

$D_M=\frac{\sum t\frac{CF_t}{(1+y)^t}}{\sum \frac{CF_t}{(1+y)^t}}$

Модифицированная дюрация облигации

Формула «Модифицированная дюрация облигации» связывает денежную сумму, ставку и время. Она показывает, как привести один поток к нужной дате или сравнить ставки с разной частотой начисления.

$D_{mod}=\frac{D_M}{1+y}$

Перестановки с повторениями: одинаковые элементы

Число различных упорядоченных записей из заданного набора элементов, среди которых есть одинаковые. Формула делит все перестановки на перестановки внутри каждой группы неразличимых элементов.

$P=\frac{n!}{n_1!n_2!\cdots n_r!},\qquad n_1+\cdots+n_r=n$

Сочетания с повторениями: метод звёзд и перегородок

Формула считает наборы из k элементов n видов, когда один вид разрешено выбирать несколько раз, а порядок выбора не важен. Эквивалентная задача — распределить k одинаковых предметов по n различимым ящикам.

$\overline C_n^k=\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}$

Беспорядки: перестановки без неподвижных точек

Беспорядок — перестановка, в которой ни один элемент не остаётся на своём первоначальном месте. Формула включений и исключений считает такие перестановки и помогает находить вероятность полного несовпадения.

$D_n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}$

Числа Каталана: правильные скобочные последовательности

Число Каталана Cₙ считает правильные последовательности из n пар скобок одного вида. В каждом начальном фрагменте открывающих скобок должно быть не меньше закрывающих, а в полной записи их количества равны.

$C_n=\frac{1}{n+1}\binom{2n}{n}$

Числа Стирлинга второго рода: разбиение на группы

Число Стирлинга второго рода S(n,k) показывает, сколькими способами можно разбить n различных элементов на k непустых неименованных групп. Рекурсия отделяет добавление элемента в старую группу от создания новой.

$S(n,k)=kS(n-1,k)+S(n-1,k-1)$

Числа Белла: все разбиения множества на группы

Число Белла считает все способы разделить различимые элементы на непустые непересекающиеся группы. Число групп заранее не задано, их порядок и порядок элементов внутри группы не учитываются.

$B_n=\sum_{k=0}^{n}S(n,k),\qquad B_0=1$

Числа Стирлинга первого рода: циклы перестановки

Беззнаковые числа Стирлинга первого рода считают перестановки n различных элементов, состоящие ровно из k циклов. Рекурсия отделяет новый одноэлементный цикл от вставки элемента в существующий цикл.

$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$

Круговые перестановки: рассадка за круглым столом

Число круговых перестановок n различных объектов равно (n−1)!, если повороты всей расстановки считаются одинаковыми. Зеркальное отражение при этом обычно даёт другой порядок соседей.

$P_{\mathrm{circle}}(n)=\frac{n!}{n}=(n-1)!,\qquad n\ge1$

Число сюръекций: распределение без пустых ящиков

Сюръективное отображение отправляет n различимых объектов в k различимых ящиков так, чтобы каждый ящик был занят. Формула считает такие распределения через числа Стирлинга или включения и исключения.

$N(n,k)=k!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n$

Формула Кэли: число деревьев с помеченными вершинами

Формула Кэли считает неориентированные деревья на заданных n различных вершинах: связные графы без циклов. Метки вершин сохраняются, а расположение рисунка на плоскости не создаёт новых деревьев.

$T_n=n^{n-2},\qquad n\ge2$

Функция Эйлера: произведение по простым делителям

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Число делителей по разложению на простые множители

Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.

$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$

Сумма делителей по простому разложению числа

Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают n.

$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \sigma(n)=\prod_{i=1}^{r}(1+p_i+\cdots+p_i^{a_i})$

Обратный элемент по модулю через расширенный алгоритм Евклида

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Китайская теорема об остатках для двух взаимно простых модулей

Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.

$x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$

Распределение Пуассона: вероятность числа событий

Распределение Пуассона даёт вероятность ровно k событий на фиксированном интервале, если известно их среднее число λ. Модель применяют к независимому потоку с постоянной интенсивностью.

$P(X=k)=e^{-\lambda}\frac{\lambda^k}{k!}$

Геометрическое распределение: номер первого успеха

Геометрическое распределение описывает число независимых попыток до первого успеха включительно. Вероятность успеха p остаётся одинаковой в каждой попытке, а предшествующие попытки заканчиваются неудачей.

$P(X=k)=(1-p)^{k-1}p$

Гипергеометрическое распределение: выбор без возвращения

Гипергеометрическая формула даёт вероятность выбрать ровно k объектов нужного типа среди n предметов, взятых без возвращения из N. В исходной совокупности ровно K объектов относятся к нужному типу.

$P(X=k)=\frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$

Равномерное распределение: вероятность попасть в интервал

Для непрерывного равномерного распределения на отрезке [a,b] вероятность попадания в его часть [c,d] равна отношению длин. Равные по длине части имеют одинаковые вероятности независимо от положения.

$P(c\le X\le d)=\frac{d-c}{b-a},\qquad a\le c\le d\le b$

Экспоненциальное распределение: вероятность времени ожидания

Экспоненциальная модель даёт вероятность ждать событие дольше t при постоянной интенсивности λ. В отличие от счёта событий по Пуассону, случайной величиной здесь служит непрерывное время до ближайшего события.

$P(T>t)=e^{-\lambda t}$

Составная формула трапеций для вычисления интеграла

Составная формула трапеций приближает определённый интеграл суммой площадей под линейными отрезками между соседними узлами. Концевые значения получают половинный вес.

$T_n=h\left[\frac{f(a)+f(b)}2+\sum_{i=1}^{n-1}f(a+ih)\right],\quad h=\frac{b-a}{n}$

Формула Симпсона: интеграл по параболическим дугам

Составная формула Симпсона объединяет соседние промежутки попарно и заменяет функцию параболой через три узла. Для равномерной сетки число промежутков должно быть чётным.

$S_n=\frac h3\left[f_0+f_n+4\!\sum_{\substack{i=1\\i\text{ нечётное}}}^{n-1}f_i+2\!\sum_{\substack{i=2\\i\text{ чётное}}}^{n-2}f_i\right]$

Явный метод Эйлера: решение задачи Коши по шагам

Явный метод Эйлера приближённо решает уравнение y′ = f(t,y), продолжая решение по наклону в начале каждого шага. При гладком решении глобальная ошибка имеет первый порядок по шагу.

$y_{n+1}=y_n+h f(t_n,y_n),\qquad t_{n+1}=t_n+h$

Неявный метод Эйлера: шаг и устойчивость затухания

Неявный метод Эйлера использует производную в конце шага. Новое значение входит в обе части равенства, поэтому каждый переход требует решения уравнения, зато схема хорошо подавляет быстро затухающие компоненты.

$y_{n+1}=y_n+h f(t_{n+1},y_{n+1})$

Явный метод средней точки для задачи Коши

Явный метод средней точки делает пробный полушаг по Эйлеру, оценивает производную в середине и использует её на полном шаге. Это двухстадийная схема Рунге — Кутты второго порядка.

$k_1=f(t_n,y_n),\quad k_2=f(t_n+h/2,y_n+hk_1/2),\quad y_{n+1}=y_n+hk_2$

Метод Хойна: явное усреднение двух наклонов

В этой двухстадийной схеме сначала делают прогноз Эйлера на полный шаг, затем усредняют начальный и прогнозный конечный наклоны. Метод имеет второй порядок, но названия его вариантов различаются в литературе.

$k_1=f(t_n,y_n),\quad k_2=f(t_n+h,y_n+hk_1),\quad y_{n+1}=y_n+\frac h2(k_1+k_2)$

Классический метод Рунге — Кутты четвёртого порядка

Классический RK4 вычисляет четыре наклона за шаг и объединяет их с весами 1:2:2:1. Для гладкой задачи Коши он даёт четвёртый порядок общей ошибки без явного вычисления высших производных.

$\begin{aligned}k_1&=f(t_n,y_n),&k_2&=f(t_n+h/2,y_n+hk_1/2),\\k_3&=f(t_n+h/2,y_n+hk_2/2),&k_4&=f(t_n+h,y_n+hk_3),\\y_{n+1}&=y_n+\frac h6(k_1+2k_2+2k_3+k_4).\end{aligned}$

Линейная интерполяция: значение между двумя узлами

Линейная интерполяция оценивает значение между двумя заданными точками по соединяющей их прямой. Доля положения внутри интервала задаёт веса концов; оценка учитывает наклон, но не кривизну исходного графика.

$P(x)=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)=(1-t)y_0+ty_1,\quad t=\frac{x-x_0}{x_1-x_0}$

Интерполяция Лагранжа: полином через заданные точки

Формула Лагранжа строит полином степени не выше n по n+1 различным узлам. Каждый базисный множитель выбирает значение своего узла и обращает вклады остальных узлов в ноль.

$P_n(x)=\sum_{k=0}^{n}y_kL_k(x),\qquad L_k(x)=\prod_{\substack{0\leq j\leq n\\j\ne k}}\frac{x-x_j}{x_k-x_j}$

Интерполяция Ньютона: таблица разделённых разностей

Форма Ньютона строит интерполяционный полином по треугольной таблице разделённых разностей. Новый узел добавляет коэффициент при очередном произведении, не требуя переписывать уже найденные нижние порядки.

$P_n(x)=f[x_0]+\sum_{k=1}^{n}f[x_0,\ldots,x_k]\prod_{j=0}^{k-1}(x-x_j),\quad f[x_i,\ldots,x_j]=\frac{f[x_{i+1},\ldots,x_j]-f[x_i,\ldots,x_{j-1}]}{x_j-x_i}$

Кубическая интерполяция Эрмита по значениям и наклонам

Кубический полином Эрмита согласует значения и первые производные на двух концах интервала. Четыре заданных условия определяют единственную кубическую или более простую кривую между узлами.

$H(x)=h_{00}(s)y_0+h_{10}(s)\ell m_0+h_{01}(s)y_1+h_{11}(s)\ell m_1,\quad s=\frac{x-x_0}{\ell},\quad \ell=x_1-x_0$

Барицентрическая интерполяция: веса и вычисление полинома

Барицентрическая форма вычисляет полином Лагранжа через заранее рассчитанные веса узлов. Она удобна для множества запросов по одной таблице; при точном совпадении аргумента с узлом нужно сразу вернуть узловое значение.

$P(x)=\frac{\sum_{k=0}^{n}\dfrac{w_ky_k}{x-x_k}}{\sum_{k=0}^{n}\dfrac{w_k}{x-x_k}},\qquad w_k=\frac{1}{\prod_{j\ne k}(x_k-x_j)},\quad x\ne x_k$

Правая разность: производная по двум соседним значениям

Правая разность оценивает производную по значениям функции в текущем и следующем узле. Это удобная односторонняя схема у левой границы таблицы, но её ошибка обычно линейна по шагу.

$f'(x)\approx D_h^+f(x)=\frac{f(x+h)-f(x)}{h},\qquad D_h^+f-f'=O(h)$

Центральная разность для первой производной

Центральная разность оценивает первую производную по двум узлам на одинаковом расстоянии слева и справа. Симметрия устраняет линейную по шагу ошибку и обычно даёт второй порядок точности.

$f'(x)\approx D_hf(x)=\frac{f(x+h)-f(x-h)}{2h},\qquad D_hf-f'=O(h^2)$

Вторая производная по трём равноотстоящим узлам

Трёхточечная центральная схема оценивает вторую производную по отклонению центрального значения от среднего соседей. Она измеряет изменение наклона, а не сам наклон, и имеет второй порядок по шагу.

$f''(x)\approx Q_hf(x)=\frac{f(x+h)-2f(x)+f(x-h)}{h^2},\qquad Q_hf-f''=O(h^2)$

Пятиточечная формула первой производной

Пятиточечная центральная формула оценивает первую производную с четвёртым порядком по шагу. Для неё нужны четыре значения вокруг центра: вес самого центрального значения равен нулю.

$f'(x)\approx P_hf=\frac{f(x-2h)-8f(x-h)+8f(x+h)-f(x+2h)}{12h},\qquad P_hf-f'=O(h^4)$

Экстраполяция Ричардсона для численной производной

Экстраполяция Ричардсона объединяет две центральные оценки производной на шагах h и h/2. При гладкой функции она сокращает ведущую ошибку второго порядка и даёт оценку четвёртого порядка.

$R_h=\frac{4D_{h/2}-D_h}{3},\qquad D_h=\frac{f(x+h)-f(x-h)}{2h},\qquad R_h-f'(x)=O(h^4)$

Быстрое возведение в степень по модулю двоичным методом

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Малая теорема Ферма: степени по простому модулю

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Теорема Эйлера: сокращение степени по составному модулю

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

$a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$

Линейное сравнение: решения через НОД коэффициента и модуля

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Мультипликативный порядок: минимальный период степеней

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Метод Якоби для системы линейных уравнений

Метод Якоби строит новое приближение к решению Ax=b, одновременно пересчитывая все неизвестные из значений предыдущего шага. Он удобен для разреженных систем и хорошо показывает, зачем проверять сходимость, а не только выполнять заданное число итераций.

$x_i^{(k+1)}=\frac{b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}}{a_{ii}},\quad i=1,\ldots,n$

Метод Гаусса—Зейделя для системы линейных уравнений

Метод Гаусса—Зейделя решает Ax=b последовательными проходами: новая компонента сразу участвует в вычислении следующих. Это обычно ускоряет простую итерацию, но делает результат одного прохода зависимым от порядка переменных.

$x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}}$

Метод SOR: последовательная сверхрелаксация

Метод SOR добавляет к проходу Гаусса—Зейделя параметр релаксации ω. При 0<ω<2 он дозирует поправку; ω=1 возвращает обычный метод, а удачный выбор ω>1 способен ускорить сходимость.

$x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\frac{\omega}{a_{ii}}\left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right)$

Метод прогонки для трёхдиагональной системы

Метод прогонки решает трёхдиагональную систему за линейное число операций, используя прямой расчёт коэффициентов связи и обратную подстановку. Он сохраняет ленточную структуру вместо работы с полной матрицей.

$c_i x_{i-1}+a_i x_i+b_i x_{i+1}=d_i;\quad \alpha_i=-\frac{b_i}{a_i+c_i\alpha_{i-1}},\;\beta_i=\frac{d_i-c_i\beta_{i-1}}{a_i+c_i\alpha_{i-1}}$

Метод Ричардсона: стационарная итерация для Ax=b

Метод Ричардсона прибавляет к текущему приближению невязку, умноженную на параметр τ. Для симметричной положительно определённой матрицы разумный τ превращает эту простую формулу в сходящуюся стационарную итерацию.

$x^{(k+1)}=x^{(k)}+\tau(b-Ax^{(k)}),\qquad r^{(k)}=b-Ax^{(k)}$

Неравенство Маркова для хвостовой вероятности

Неравенство Маркова даёт верхнюю границу вероятности большого значения неотрицательной случайной величины через её среднее. Оно работает без знания точного распределения, поэтому граница может быть грубой, но остаётся гарантированной при выполнении условий.

$P(X\ge a)\le\frac{E[X]}{a},\qquad X\ge0,\ a>0$

Неравенство Йенсена для ожидания функции

Неравенство Йенсена сравнивает значение выпуклой функции от среднего со средним её значений: φ(E[X])≤E[φ(X)]. Для вогнутой функции знак меняется. Это формальный способ учесть, что разброс влияет на нелинейное преобразование.

$\varphi(E[X])\le E[\varphi(X)]\quad\text{для выпуклой }\varphi$

Закон полного ожидания и условное среднее

Закон полного ожидания говорит: сначала можно найти среднее X внутри каждой группы, заданной Y или разбиением Hᵢ, а затем усреднить эти условные средние по вероятностям групп. Результат равен общему математическому ожиданию X.

$E[X]=E[E[X\mid Y]],\qquad E[X]=\sum_iE[X\mid H_i]P(H_i)$

Закон полной дисперсии: внутри и между группами

Закон полной дисперсии раскладывает общий разброс X на средний разброс внутри групп и разброс условных средних между группами. Группы задаёт Y. Формула помогает понять источник неопределённости, а не только получить одно число.

$\operatorname{Var}(X)=E[\operatorname{Var}(X\mid Y)]+\operatorname{Var}(E[X\mid Y])$

Производящая функция вероятностей дискретной величины

Производящая функция вероятностей кодирует распределение неотрицательной целочисленной величины X в степенном ряде. Коэффициент при zᵏ равен P(X=k), а независимая сумма превращает произведение функций. Она удобна для счётчиков событий и дискретных распределений.

$G_X(z)=E[z^X]=\sum_{k=0}^{\infty}P(X=k)z^k,\qquad X\in\{0,1,2,\ldots\}$