Математика: темы
Численные методы
Формулы и правила по теме «Численные методы».
28 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Сингулярное разложение матрицы | $A=U\Sigma V^T,\quad U^TU=I,\quad V^TV=I$ | Линейная алгебра | Сингулярное разложение представляет матрицу как произведение двух ортогональных матриц и диагональной матрицы сингулярных чисел. Это универсальная форма разложения, которая работает для прямоугольных матриц и показывает главные направления действия линейного отображения. |
| Ранг матрицы через сингулярные числа | $\operatorname{rank}(A)=\#\{i:\sigma_i>0\}$ | Линейная алгебра | Ранг матрицы равен количеству ненулевых сингулярных чисел. Эта формула связывает алгебраическое понятие размерности образа с численной диагностикой зависимости строк и столбцов. |
| Формула Шермана-Моррисона | $(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}$ | Линейная алгебра | Формула Шермана-Моррисона дает обратную матрицу после рангового обновления A+uv^T. Она позволяет обновить уже известную обратную матрицу без полного повторного обращения. |
| Формула Вудбери | $(A+UCV)^{-1}=A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}$ | Линейная алгебра | Формула Вудбери обобщает обновление обратной матрицы на добавку малого ранга UCV. Она позволяет заменить обращение большой матрицы обращением меньшей матрицы. |
| Правая разность: производная по двум соседним значениям | $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)$ | Численное дифференцирование | Пятиточечная центральная формула оценивает первую производную с четвёртым порядком по шагу. Для неё нужны четыре значения вокруг центра: вес самого центрального значения равен нулю. |
| Экстраполяция Ричардсона для численной производной | $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)$ | Численное дифференцирование | Экстраполяция Ричардсона объединяет две центральные оценки производной на шагах h и h/2. При гладкой функции она сокращает ведущую ошибку второго порядка и даёт оценку четвёртого порядка. |
| Метод Якоби для системы линейных уравнений | $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}}$ | Численное решение линейных систем | Метод Гаусса—Зейделя решает Ax=b последовательными проходами: новая компонента сразу участвует в вычислении следующих. Это обычно ускоряет простую итерацию, но делает результат одного прохода зависимым от порядка переменных. |
| Метод SOR: последовательная сверхрелаксация | $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)$ | Численное решение линейных систем | Метод SOR добавляет к проходу Гаусса—Зейделя параметр релаксации ω. При 0<ω<2 он дозирует поправку; ω=1 возвращает обычный метод, а удачный выбор ω>1 способен ускорить сходимость. |
| Метод прогонки для трёхдиагональной системы | $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)}$ | Численное решение линейных систем | Метод Ричардсона прибавляет к текущему приближению невязку, умноженную на параметр τ. Для симметричной положительно определённой матрицы разумный τ превращает эту простую формулу в сходящуюся стационарную итерацию. |
| Метод золотого сечения: сужение интервала минимума | $\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$ | Численная оптимизация | Золотое сечение находит минимум унимодальной функции без производных. Два внутренних значения позволяют отбросить часть интервала, а удачное отношение длин сохраняет одно вычисление для следующего шага. |
| Тернарный поиск минимума непрерывной унимодальной функции | $u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$ | Численная оптимизация | Тернарный поиск сравнивает функцию в двух точках, делящих интервал на трети. При унимодальности одно сравнение позволяет удалить крайнюю треть и сохранить интервал, содержащий минимум. |
| Параболическая интерполяция для поиска минимума функции | $A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$ | Численная оптимизация | Через три значения функции строят квадратичный интерполянт и используют его вершину как новую пробную точку минимума. В отличие от деления интервала схема учитывает высоты всех трёх точек. |
| Градиентный спуск с постоянным шагом: условие убывания | $x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$ | Численная оптимизация | Постоянный шаг градиентного спуска смещает точку против градиента. При липшицевом градиенте известная граница шага обеспечивает уменьшение функции и объясняет, почему слишком крупный шаг вызывает расходимость. |
| Правило Армихо: обратный поиск длины шага спуска | $f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$ | Численная оптимизация | Обратный поиск по правилу Армихо уменьшает пробный шаг, пока функция не снизится на заданную долю линейного прогноза. Он выбирает длину движения вдоль уже найденного направления спуска. |
| Составная формула средних прямоугольников | $M_n=h\sum_{i=0}^{n-1}f\!\left(a+\left(i+\tfrac12\right)h\right),\quad h=\frac{b-a}{n}$ | Численное интегрирование | Составная формула средних прямоугольников заменяет интеграл суммой площадей с высотами в серединах равных отрезков. Для гладкой функции погрешность имеет второй порядок по шагу, хотя значения на концах не используются. |
| Квадратура Гаусса—Лежандра с двумя узлами | $G_2=\frac{b-a}{2}\left[f\!\left(m-\frac{b-a}{2\sqrt3}\right)+f\!\left(m+\frac{b-a}{2\sqrt3}\right)\right],\quad m=\frac{a+b}{2}$ | Численное интегрирование | Двухузловая квадратура Гаусса—Лежандра вычисляет функцию в двух специально выбранных внутренних точках. На конечном отрезке с единичным весом она точно интегрирует любой многочлен степени не выше трёх. |
| Метод Ромберга: таблица уточнений интеграла | $R_{k,0}=T_{2^k},\quad R_{k,j}=R_{k,j-1}+\frac{R_{k,j-1}-R_{k-1,j-1}}{4^j-1},\quad 1\le j\le k$ | Численное интегрирование | Метод Ромберга строит таблицу из составных трапеций с последовательным удвоением числа отрезков. Экстраполяция устраняет ведущие чётные степени шага и повышает точность без смены уже вычисленных узлов. |
| Адаптивный Симпсон: локальная оценка ошибки | $S_1=S(a,b),\ S_2=S(a,m)+S(m,b),\quad \varepsilon_{\mathrm{est}}=\frac{|S_2-S_1|}{15},\quad I\approx S_2+\frac{S_2-S_1}{15}$ | Численное интегрирование | Адаптивный метод Симпсона сравнивает одну параболическую оценку с двумя оценками на половинах. Разность даёт локальный индикатор ошибки, по которому алгоритм уточняет только те участки, где не достигнут допуск. |
| Интеграл методом Монте-Карло: среднее и ошибка | $\hat I_N=\frac{b-a}{N}\sum_{i=1}^N f(X_i),\quad X_i\overset{\mathrm{iid}}\sim U(a,b),\quad\widehat{\mathrm{SE}}=(b-a)\frac{s_f}{\sqrt N}$ | Численное интегрирование | Метод Монте-Карло оценивает интеграл как длину отрезка, умноженную на среднее значений функции в случайных равномерных точках. Разброс оценки измеряют стандартной ошибкой, которая при независимой выборке убывает как N⁻¹ᐟ². |
| Неявная трапециевидная схема Кранка — Николсон для ОДУ | $y_{n+1}=y_n+\frac h2[f(t_n,y_n)+f(t_{n+1},y_{n+1})]$ | Численные методы ОДУ | Неявная трапециевидная схема усредняет производные на концах шага, включая неизвестный новый уровень. Она имеет второй порядок и A-устойчивость, но при крупном шаге затухание может сопровождаться сменой знака. |
| Метод Адамса — Башфорта второго порядка для ОДУ | $y_{n+1}=y_n+h\left(\frac32 f_n-\frac12 f_{n-1}\right)$ | Численные методы ОДУ | Двухшаговый метод Адамса — Башфорта использует два уже вычисленных наклона и получает явное приближение второго порядка с одним новым вызовом правой части. |
| Метод Стёрмера — Верле для гармонического осциллятора | $q_{n+1}=2q_n-q_{n-1}-h^2\omega^2q_n$ | Механика | Схема Стёрмера — Верле обновляет координату осциллятора по двум соседним моментам и хорошо сохраняет структуру обратимого движения при малом шаге. |
| Оценка ошибки решения системы через невязку и обусловленность | $\frac{\|\widetilde{x}-x\|}{\|x\|}\le\kappa(A)\frac{\|r\|}{\|b\|}$ | Численное решение линейных систем | Относительная ошибка приближённого решения линейной системы ограничена произведением относительной невязки на число обусловленности матрицы. Оценка объясняет, почему малая невязка сама по себе не гарантирует точного решения. |