Математика: темы

Численные методы

Формулы и правила по теме «Численные методы».

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\|}$ Численное решение линейных систем Относительная ошибка приближённого решения линейной системы ограничена произведением относительной невязки на число обусловленности матрицы. Оценка объясняет, почему малая невязка сама по себе не гарантирует точного решения.