А где?

Вторые вопросы билета: развернутые ответы с подготовкой

Численные методы: теория, формулы, алгоритмы и простые фразы для ответа

Как пользоваться файлом: Сначала прочитай блок “коротко”, чтобы быстро вспомнить суть. Потом смотри формулы и алгоритм. На экзамене можно говорить простыми словами: что ищем, каким методом, почему метод работает и как оценивается ошибка.

1. Источники и виды погрешностей. Теория погрешностей

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

Коротко для устного ответа

Погрешности появляются из-за неточных исходных данных, округления чисел, приближенных формул и особенностей вычислительной машины. Основные характеристики — абсолютная и относительная погрешности. Прямая задача теории погрешностей отвечает на вопрос: какая ошибка будет у результата, если известны ошибки исходных данных. Обратная задача отвечает: насколько точно надо задать исходные данные, чтобы результат был нужной точности.

Источники погрешностей

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

Основные количественные характеристики

абсолютная погрешность: Δx = |x - x̃|

относительная погрешность: δx = Δx / |x̃|

Абсолютная погрешность показывает ошибку в тех же единицах, что и сама величина. Относительная погрешность показывает, насколько ошибка велика по сравнению с самим числом. Часто ее выражают в процентах: δ·100%.

Погрешности арифметических операций

• при сложении и вычитании складываются абсолютные погрешности;
• при умножении и делении примерно складываются относительные погрешности;
• самая опасная операция — вычитание близких чисел, потому что значащие цифры могут потеряться.

Погрешность функции от нескольких переменных

Δf ≈ |∂f/∂x1|Δx1 + |∂f/∂x2|Δx2 + ... + |∂f/∂xn|Δxn

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

Правила округления и записи результата

• погрешность обычно округляют до одной или двух значащих цифр;
• сам результат округляют до того же разряда, что и погрешность;
• нельзя писать слишком много цифр, если они не являются достоверными;
• правильная запись имеет вид: x = x̃ ± Δx.

Главная фраза: Теория погрешностей нужна, чтобы понимать, насколько можно доверять численному ответу и как ошибки исходных данных переходят в ошибку результата.

2. Аппроксимация функций. Непрерывная аппроксимация. Ряд Тейлора

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

Постановка задачи

Дана функция f(x) на некотором отрезке. Нужно построить более простую функцию φ(x), которая приближает f(x). В непрерывной аппроксимации близость рассматривают не только в отдельных точках, а на всем отрезке.

f(x) ≈ φ(x), x ∈ [a, b]

Ряд Тейлора

Ряд Тейлора позволяет заменить функцию многочленом около некоторой точки x0. Идея такая: если знать значение функции и ее производные в точке, можно построить многочлен, который рядом с этой точкой ведет себя почти так же, как исходная функция.

f(x) ≈ f(x0) + f'(x0)(x-x0) + f''(x0)(x-x0)^2/2! + ...

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

Пример алгоритма

1. Задать x, точность eps и начальное значение суммы.
2. Вычислять очередной член ряда.
3. Добавлять его к сумме.
4. Остановиться, когда очередной член стал меньше eps.
5. Полученную сумму считать приближенным значением функции.

s = 0
term = 1
k = 0
while abs(term) > eps:
s = s + term
k = k + 1
term = next_term(k)

Главная фраза: Аппроксимация нужна, чтобы заменить сложную функцию простой, а ряд Тейлора делает это через значения производных в одной точке.

3. Точечная аппроксимация. Интерполяция полиномами, глобальная, многоинтервальная, кусочная и сплайн-интерполяция

Точечная аппроксимация строится по набору точек (xi, yi). Самый важный частный случай — интерполяция. При интерполяции приближающая функция обязана проходить через все заданные точки.

Интерполяция

P(xi) = yi

Это означает: если у нас есть таблица значений функции, мы строим новую функцию P(x), которая в табличных точках дает точно те же значения. А между точками она позволяет оценивать значения функции.

Глобальная интерполяция

Глобальная интерполяция строит один многочлен сразу по всем точкам. Например, это может быть полином Лагранжа или Ньютона. Преимущество: получается одна формула на весь отрезок. Недостаток: при большом числе узлов полином может сильно колебаться.

Многоинтервальная и кусочная интерполяция

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

Сплайн-интерполяция

Сплайн — это кусочная интерполяция полиномами, но куски соединяются гладко. Обычно используют кубический сплайн: на каждом маленьком отрезке стоит кубический многочлен, а в узлах значения, первые и вторые производные согласованы. Поэтому график получается гладким.

• линейная интерполяция — простая ломаная;
• полиномиальная глобальная интерполяция — один многочлен на весь отрезок;
• сплайн-интерполяция — несколько полиномов, соединенных гладко.

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

4. Среднеквадратичное приближение. Метод наименьших квадратов

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

Постановка задачи

Есть экспериментальные точки (xi, yi). Выбирается модель, например y = ax + b или y = a exp(bx). Нужно подобрать параметры модели так, чтобы отклонения расчетных значений от экспериментальных были минимальными.

S = Σ(yi - φ(xi))^2 → min

Здесь S — сумма квадратов ошибок. Ошибки возводят в квадрат, чтобы положительные и отрицательные отклонения не компенсировали друг друга. Чем меньше S, тем лучше модель описывает точки.

Почему именно квадраты

• квадрат делает все отклонения положительными;
• большие ошибки получают больший вес;
• математически такую функцию удобно минимизировать.

Линеаризация

Линеаризация — это преобразование нелинейной зависимости к линейной. Например, если y = a exp(bx), то можно взять логарифм: ln y = ln a + bx. После этого строится прямая для ln y от x.

Главная фраза: МНК не обязан проходить через все точки; он строит такую зависимость, у которой сумма квадратов отклонений минимальна.

5. Этапы численного решения нелинейных уравнений

Нелинейное уравнение обычно записывают как f(x)=0. Численное решение означает, что корень ищется не в виде точной формулы, а приближенно, с заданной точностью.

Этапы решения

1. Записать уравнение в виде f(x)=0.
2. Построить график или таблицу значений функции.
3. Локализовать корень, то есть найти отрезок [a,b], где он находится.
4. Уточнить корень выбранным методом: половинного деления, Ньютона, секущих или простых итераций.
5. Проверить точность и вывести результат.

Локализация корней

Локализация — это поиск небольшого промежутка, где находится корень. Часто используют признак смены знака: если f(a) и f(b) имеют разные знаки, то на отрезке [a,b] есть хотя бы один корень, если функция непрерывна.

f(a) · f(b) < 0

Итерационная последовательность

Итерационная последовательность — это набор приближений x0, x1, x2, ..., которые постепенно должны приближаться к корню. Если приближения становятся все ближе к истинному корню, последовательность называется сходящейся. Если значения уходят или начинают прыгать, метод расходится.

Главная фраза: Сначала корень нужно найти грубо, то есть локализовать, а потом уточнять итерационным методом до нужной точности.

6. Метод половинного деления

Метод половинного деления, или метод бисекции, применяется для уравнения f(x)=0 на отрезке [a,b], если функция непрерывна и на концах отрезка имеет разные знаки.

Идея метода

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

c = (a + b) / 2

Алгоритм

1. Проверить, что f(a)·f(b)<0.
2. Найти середину c=(a+b)/2.
3. Если f(a)·f(c)<0, корень лежит на [a,c], значит b=c.
4. Иначе корень лежит на [c,b], значит a=c.
5. Повторять, пока длина отрезка не станет меньше eps.

while abs(b - a) > eps:
c = (a + b) / 2
if f(a) * f(c) < 0:
b = c
else:
a = c
root = (a + b) / 2

Плюсы и минусы

• плюс: метод очень надежный, если есть смена знака;
• плюс: не нужны производные;
• минус: сходится медленнее метода Ньютона.

Главная фраза: Метод половинного деления каждый раз оставляет ту половину отрезка, где сохраняется смена знака, поэтому корень постепенно зажимается.

7. Метод Ньютона

Метод Ньютона, или метод касательных, используется для уточнения корня уравнения f(x)=0. Он обычно сходится быстро, но требует производную функции.

Формула метода

x_{k+1} = x_k - f(x_k) / f'(x_k)

Смысл формулы такой: в текущей точке xk строится касательная к графику функции. Точка пересечения этой касательной с осью Ox берется как новое приближение к корню.

Геометрический смысл

Если мы стоим на графике функции в точке xk, то вместо кривой временно используем касательную. Касательная проще, потому что это прямая. Где эта прямая пересечет ось Ox, туда мы переходим.

Алгоритм

1. Выбрать начальное приближение x0.
2. Вычислить f(x0) и f'(x0).
3. Найти новое приближение по формуле Ньютона.
4. Повторять, пока |x_{k+1}-x_k| < eps или |f(x)| < eps.

x = x0
while True:
x_new = x - f(x) / df(x)
if abs(x_new - x) < eps:
break
x = x_new

Условия применимости

• функция должна быть достаточно гладкой;
• производная не должна быть равна нулю около корня;
• начальное приближение должно быть выбрано достаточно близко к корню;
• часто используют условие выбора x0: f(x0)·f''(x0)>0.

Главная фраза: Метод Ньютона заменяет кривую касательной и берет пересечение касательной с осью как новое приближение.

8. Метод простых итераций

Метод простых итераций применяют после преобразования уравнения f(x)=0 к виду x = φ(x). Тогда корень ищется повторением формулы x_{k+1}=φ(x_k).

Идея метода

Мы выбираем начальное приближение x0, подставляем его в φ(x), получаем x1. Потом x1 снова подставляем в φ(x), получаем x2, и так далее. Если все хорошо, значения приближаются к корню.

x_{k+1} = φ(x_k)

Условие сходимости

|φ'(x)| < 1

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

Геометрический смысл

Решение x=φ(x) можно понимать как точку пересечения графиков y=x и y=φ(x). Итерации двигаются между этими графиками. Если процесс приближается к точке пересечения, метод сходится.

x = x0
while True:
x_new = phi(x)
if abs(x_new - x) < eps:
break
x = x_new

Главная фраза: Метод простых итераций многократно подставляет старое приближение в φ(x), а сходимость обычно требует |φ'(x)|<1.

9. Системы нелинейных уравнений. Ньютон, простые итерации, оптимизация и Монте-Карло

Система нелинейных уравнений имеет вид F(x)=0, где x — вектор неизвестных. Например, нужно найти не одно число x, а сразу несколько величин x1, x2, ..., xn.

Метод Ньютона для систем

J(x_k) Δx = -F(x_k), x_{k+1}=x_k+Δx

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

Метод простых итераций для систем

x_{k+1} = Φ(x_k)

Идея такая же, как для одного уравнения, только вместо одного числа теперь вектор. Условие сходимости связано с тем, чтобы отображение Φ было сжимающим: новые приближения должны становиться ближе друг к другу.

Сведение к оптимизации

Систему F(x)=0 можно заменить задачей минимизации функции невязки. Если все уравнения выполнены точно, невязка равна нулю.

S(x) = f1(x)^2 + f2(x)^2 + ... + fn(x)^2 → min

Метод Монте-Карло

Метод Монте-Карло использует случайные точки. Для оптимизации можно случайно выбирать много точек в области и искать, где значение функции S(x) меньше. Метод простой, но не всегда быстрый и точный.

Главная фраза: Нелинейную систему можно решать итерациями, методом Ньютона через матрицу Якоби или как задачу минимизации суммы квадратов невязок.

10. Численное дифференцирование

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

Формулы для первой производной

правая разность: f'(x) ≈ [f(x+h)-f(x)]/h

левая разность: f'(x) ≈ [f(x)-f(x-h)]/h

центральная разность: f'(x) ≈ [f(x+h)-f(x-h)]/(2h)

Центральная разность обычно точнее, потому что использует значения функции с двух сторон от точки.

Вторая производная

f''(x) ≈ [f(x+h)-2f(x)+f(x-h)]/h^2

Третья производная

f'''(x) ≈ [f(x+2h)-2f(x+h)+2f(x-h)-f(x-2h)]/(2h^3)

Погрешность

У численного дифференцирования есть две проблемы. Если шаг h слишком большой, формула грубо приближает производную. Если h слишком маленький, начинают сильно влиять ошибки округления, потому что вычитаются близкие числа. Поэтому шаг нужно выбирать разумно.

• ошибка метода уменьшается при уменьшении h;
• ошибка округления может увеличиваться при слишком малом h;
• центральные формулы обычно точнее односторонних.

Главная фраза: Численная производная — это замена производной разностным отношением; слишком большой шаг дает грубость, слишком маленький усиливает округление.

11. Численное интегрирование. Методы прямоугольников

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

Методы прямоугольников

• левых прямоугольников: высота берется по левому концу отрезка;
• правых прямоугольников: высота берется по правому концу;
• средних прямоугольников: высота берется в середине отрезка.

I ≈ h Σ f(xi)

Здесь h — шаг разбиения. Чем меньше h, тем больше прямоугольников и тем точнее результат. Метод средних прямоугольников обычно точнее левых и правых.

Вычисление с заданной точностью

Чтобы получить интеграл с заданной точностью, можно считать интеграл с шагом h, потом с шагом h/2 и сравнивать результаты. Если разница стала меньше eps, расчет останавливают. Это называется практической оценкой погрешности, часто через правило Рунге.

R ≈ |I(h/2)-I(h)| / (2^p - 1)

p — порядок метода. Для метода средних прямоугольников p=2, для левых и правых обычно p=1.

Главная фраза: Метод прямоугольников заменяет площадь под графиком суммой прямоугольников, а точность повышают уменьшением шага.

12. Метод трапеций

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

Формула метода

I ≈ h [ f(x0)/2 + f(x1) + f(x2) + ... + f(xn)/2 ]

Первое и последнее значения берутся с коэффициентом 1/2, потому что они входят только в одну крайную трапецию. Внутренние точки входят в две соседние трапеции, поэтому учитываются полностью.

Алгоритм

1. Разбить отрезок [a,b] на n частей.
2. Вычислить шаг h=(b-a)/n.
3. Посчитать значения функции во всех узлах.
4. Подставить значения в формулу трапеций.
5. При необходимости уменьшать шаг и оценивать ошибку по правилу Рунге.

Погрешность

Метод трапеций имеет второй порядок точности для гладких функций. Это значит, что при уменьшении шага примерно в 2 раза ошибка уменьшается примерно в 4 раза.

ошибка ~ h^2

Главная фраза: Метод трапеций заменяет кривую на каждом маленьком участке прямой линией и складывает площади трапеций.

13. Численные методы нахождения кратных интегралов

Кратный интеграл — это интеграл по области на плоскости или в пространстве. Например, двойной интеграл можно понимать как объем под поверхностью z=f(x,y) над областью D.

Последовательное интегрирование

Если область удобно описывается границами, двойной интеграл можно вычислять как два обычных интеграла: сначала по y, потом по x, или наоборот.

∫∫_D f(x,y) dA = ∫_a^b [∫_{φ1(x)}^{φ2(x)} f(x,y) dy] dx

Во внутреннем интеграле x считается фиксированным. Сначала для каждого x считается площадь по y, потом эти значения интегрируются по x.

Метод ячеек

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

I ≈ Σ f(xi, yj) Δx Δy

Вероятностный метод Монте-Карло

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

I ≈ S_D · среднее значение f(x,y)

Интерполяционные методы

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

Главная фраза: Двойной интеграл можно считать последовательным интегрированием, суммированием по ячейкам или методом Монте-Карло через случайные точки.

14. Численные методы решения ОДУ: Эйлер, Рунге-Кутта, Адамс, выбор шага

Задача Коши для ОДУ первого порядка имеет вид y'=f(x,y), y(a)=y0. Нужно найти значения функции y(x) на отрезке. Численные методы строят решение по шагам: зная значение в одной точке, вычисляют значение в следующей.

Явный метод Эйлера

y_{i+1} = y_i + h f(x_i, y_i)

Это самый простой метод. Он идет по касательной из текущей точки. Геометрически решение заменяется ломаной линией. Метод простой, но не очень точный.

Неявный метод Эйлера

y_{i+1} = y_i + h f(x_{i+1}, y_{i+1})

В правой части стоит неизвестное y_{i+1}, поэтому на каждом шаге нужно решать уравнение. Зато неявные методы часто устойчивее.

Модифицированный метод Эйлера

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

Метод Рунге-Кутта 4-го порядка

Метод Рунге-Кутта 4-го порядка на каждом шаге несколько раз оценивает правую часть f(x,y): в начале шага, в середине и в конце. Потом эти наклоны усредняются со специальными весами. Метод намного точнее Эйлера.

y_{i+1}=y_i+h(k1+2k2+2k3+k4)/6

• k1 = f(xi, yi);
• k2 = f(xi+h/2, yi+h k1/2);
• k3 = f(xi+h/2, yi+h k2/2);
• k4 = f(xi+h, yi+h k3).

Методы Адамса

Методы Адамса относятся к многошаговым методам. Они используют не только последнее значение, но и несколько предыдущих значений. Поэтому они могут быть эффективными, но для старта им нужны первые точки, которые часто получают методом Рунге-Кутта.

Выбор шага

Шаг h влияет на точность и время вычислений. Малый шаг дает более точный результат, но требует больше вычислений. Большой шаг быстрее, но может дать большую ошибку. Практически шаг выбирают, сравнивая решения с шагом h и h/2 по правилу Рунге.

R ≈ |y(h/2)-y(h)|/(2^p-1)

Главная фраза: Численное решение ОДУ строится по шагам: Эйлер использует один наклон, Рунге-Кутта — несколько наклонов за шаг, а Адамс использует несколько предыдущих точек.

Мини-шпаргалка: что сказать, если совсем растерялась

• Погрешность — это отличие приближенного результата от точного.
• Аппроксимация — замена сложной функции более простой.
• Интерполяция — частный случай аппроксимации, когда кривая проходит через заданные точки.
• МНК — подбор параметров модели так, чтобы сумма квадратов ошибок была минимальна.
• Нелинейные уравнения сначала локализуют, потом уточняют итерационным методом.
• Метод Ньютона использует касательную и производную.
• Метод простых итераций требует записи x=φ(x) и условия |φ'|<1.
• Численное дифференцирование заменяет производную разностями.
• Численное интегрирование заменяет площадь суммой простых фигур.
• ОДУ решают по шагам: из текущей точки получают следующую.