Всё, что нужно знать, чтобы понимать лекции по численным методам
ОП.10 Численные методы · Специальность 09.02.07 «Информационные системы и программирование»
Этот словарь — ваш «справочник на полях». В лекциях вы будете встречать выделенные термины. Если что-то непонятно — возвращайтесь сюда. Каждое определение сопровождается примером и (где полезно) рисунком.
Все термины сгруппированы по темам. Щёлкните по названию, чтобы сразу перейти к нужному слайду.
Функция — это правило, которое каждому числу x из некоторого множества ставит в соответствие ровно одно число y. Обозначается y = f(x).
Здесь x называется аргументом, y — значением функции.
Функция f(x) = x². Если x = 3, то f(3) = 9. Если x = −2, то f(−2) = 4. Каждому x соответствует ровно одно y.
График функции — это множество всех точек на плоскости с координатами (x, f(x)).
График функции f(x) = x². Точка (3, 9) показывает, что при x = 3 значение функции равно 9
В численных методах мы всегда работаем с функциями. Корень уравнения f(x) = 0 — это точка, где график пересекает ось Ox. Понимание формы графика помогает выбрать метод решения.
Корень уравнения f(x) = 0 — это такое число x*, при котором функция обращается в ноль: f(x*) = 0.
Геометрически корень — это точка, где график функции пересекает горизонтальную ось Ox.
Уравнение x² − 4 = 0 имеет два корня: x* = 2 и x* = −2. Проверим: 2² − 4 = 0 ✓, (−2)² − 4 = 0 ✓.
Уравнение x³ − x − 1 = 0 имеет один вещественный корень x* ≈ 1.3247. Красивой формулы для него нет — именно такие уравнения мы и решаем численно.
Корни уравнения x² − 4 = 0 — точки, где график пересекает ось Ox
Поиск корней — одна из главных задач численных методов. Многие инженерные, физические и финансовые задачи сводятся к уравнению f(x) = 0.
Непрерывная функция — это функция, график которой можно нарисовать, не отрывая карандаша от бумаги. Формально: при малом изменении x значение f(x) тоже меняется мало, без «скачков».
Непрерывные: y = x², y = sin(x), y = eˣ — их графики плавные.
Разрывные: y = 1/x (разрыв в точке 0), функция, которая «прыгает» из одного значения в другое.
Слева: непрерывная функция (рисуется без отрыва). Справа: разрывная (есть скачок)
Все численные методы поиска корня (бисекция, хорды, Ньютон) требуют, чтобы функция была непрерывной. Иначе метод может «промахнуться» или найти ложный корень.
Производная функции f(x) в точке x — это скорость изменения функции в этой точке. Обозначается f'(x) или df/dx.
Геометрически производная равна наклону касательной к графику в этой точке.
| Функция | Производная | Пример |
|---|---|---|
xⁿ | n·xⁿ⁻¹ | (x³)' = 3x² |
const | 0 | (5)' = 0 |
x | 1 | (x)' = 1 |
sin(x) | cos(x) | — |
cos(x) | −sin(x) | — |
eˣ | eˣ | — |
ln(x) | 1/x | — |
Функция f(x) = x³ − x − 1. Считаем производную по правилам:
x³ равна 3x².−x равна −1.−1 равна 0.f'(x) = 3x² − 1.Метод Ньютона использует производную для «прицеливания» в корень. Чем точнее производная — тем быстрее сходится метод. Это ключевой инструмент для самого быстрого метода поиска корней.
Значение производной f'(x₀) в точке x₀ равно угловому коэффициенту касательной к графику функции в этой точке.
Если f'(x₀) > 0 — функция в этой точке возрастает (график идёт вверх).
Если f'(x₀) < 0 — функция убывает (график идёт вниз).
Если f'(x₀) = 0 — касательная горизонтальна (вершина горба или впадины).
Производная = наклон касательной. Слева f′ > 0 (функция растёт), в вершине f′ = 0, справа f′ < 0 (функция убывает)
Метод Ньютона строит касательную в текущей точке и смотрит, куда она приведёт. Знак и величина производной определяют, насколько далеко «прыгнуть» к корню.
Вторая производная — это производная от производной. Обозначается f''(x).
Если f'(x) показывает, как быстро растёт функция, то f''(x) показывает, как быстро меняется сама скорость.
Геометрически: f''(x) > 0 — график «выгнут вверх» (как чаша), f''(x) < 0 — «выгнут вниз» (как купол).
Функция f(x) = x³ − x − 1.
f'(x) = 3x² − 1.f''(x) = (3x² − 1)' = 6x.В точке x = 1: f''(1) = 6 > 0 — график выгнут вверх.
В точке x = −1: f''(−1) = −6 < 0 — график выгнут вниз.
Вторая производная показывает «выпуклость» графика: чаша (f″ > 0) или купол (f″ < 0)
Вторая производная используется при выборе начального приближения для метода Ньютона (правило Фурье) и для анализа квадратичной сходимости.
Функция монотонно возрастает на отрезке, если при увеличении x значение f(x) тоже увеличивается (или остаётся тем же). График «идёт вверх».
Функция монотонно убывает на отрезке, если при увеличении x значение f(x) уменьшается. График «идёт вниз».
Немонотонная функция — это функция, которая на отрезке то растёт, то убывает (у неё есть «горбы» и «впадины»).
f(x) = x — монотонно возрастает на всей оси.
f(x) = −x — монотонно убывает на всей оси.
f(x) = x² — немонотонна: убывает при x < 0, возрастает при x > 0.
Слева: возрастает. В центре: убывает. Справа: немонотонна (сначала убывает, потом возрастает)
Методы хорд и Ньютона требуют, чтобы функция была монотонной на отрезке локализации. Если функция немонотонна, метод может «застрять» или найти не тот корень.
Точка перегиба — это точка на графике, где функция меняет характер выпуклости: была «чашей», стала «куполом» (или наоборот).
В точке перегиба вторая производная равна нулю: f''(x) = 0, и при переходе через неё знак f''(x) меняется.
Функция f(x) = x³. Вторая производная f''(x) = 6x.
x < 0: f''(x) < 0 — купол.x = 0: f''(0) = 0 — точка перегиба.x > 0: f''(x) > 0 — чаша.Точка перегиба функции y = x³ — здесь выпуклость меняется с «купола» на «чашу»
Если внутри отрезка локализации есть точка перегиба, метод хорд и метод Ньютона могут работать нестабильно. Условие «f''(x) не меняет знак» как раз гарантирует, что перегибов нет.
Точка минимума — точка, в которой значение функции меньше, чем в соседних точках (вершина «впадины»).
Точка максимума — точка, в которой значение функции больше, чем в соседних (вершина «горба»).
Обе точки называются точками экстремума.
Функция f(x) = x² − 4x + 5 = (x − 2)² + 1. Минимум в точке x = 2, значение f(2) = 1. В этой точке производная равна нулю: f'(2) = 2·2 − 4 = 0.
Точки экстремума: максимум (горб) и минимум (впадина). В обеих производная равна нулю
Обучение нейросетей — это поиск минимума функции потерь. Метод Ньютона — один из способов найти его быстро. Понимание экстремумов — ключ к ML.
Касательная к графику функции в точке x₀ — это прямая, которая «прижимается» к графику в этой точке и имеет тот же наклон, что и график.
Наклон касательной равен производной: k = f'(x₀).
Касательная в точке x₀ имеет наклон, равный производной f′(x₀)
Метод Ньютона строит касательную в текущей точке и смотрит, где она пересечёт ось Ox. Это даёт новое, более точное приближение корня.
Хорда — это отрезок прямой, соединяющий две точки на графике функции.
В методе хорд мы проводим прямую через точки A(a, f(a)) и B(b, f(b)) и ищем, где эта прямая пересекает ось Ox.
Хорда — отрезок, соединяющий две точки графика. Метод хорд использует её для приближения корня
Метод хорд — это «младший брат» метода Ньютона. Он проще (не нужна производная), но чуть медленнее. Хорда — его основной инструмент.
Угловой коэффициент (наклон) прямой — это число, показывающее, насколько «круто» идёт прямая. Обозначается k.
Для прямой, проходящей через две точки (x₁, y₁) и (x₂, y₂):
k = y₂ − y₁ x₂ − x₁
Прямая через точки (1, 2) и (3, 8):
k = (8 − 2) / (3 − 1) = 6 / 2 = 3
Значит, при сдвиге на 1 вправо прямая поднимается на 3.
Угловой коэффициент = отношение Δy к Δx. Это «крутизна» прямой
И формула хорд, и формула Ньютона основаны на угловом коэффициенте. Понимание k — ключ к пониманию обеих формул.
Локализация корня — это поиск отрезка [a, b], внутри которого гарантированно находится хотя бы один корень уравнения f(x) = 0.
Гарантия обеспечивается теоремой Больцано — Коши: если функция непрерывна на [a, b] и на концах принимает значения разных знаков (f(a) · f(b) < 0), то внутри отрезка есть корень.
На отрезке [a, b] функция меняет знак — внутри есть хотя бы один корень
Все методы (бисекция, хорды, Ньютон) работают только после локализации. Без неё метод может найти не тот корень или вовсе не сойтись.
Погрешность — это разница между точным (истинным) значением и приближённым, которое мы получили.
Абсолютная погрешность: Δ = |X − x|, где X — истинное значение, x — приближённое. Измеряется в тех же единицах, что и сама величина.
Относительная погрешность: δ = Δ / |x|, обычно в процентах. Показывает, насколько велика ошибка относительно самой величины.
Истинное значение X = 3.14159, приближённое x = 3.14.
Δ = |3.14159 − 3.14| = 0.00159.δ = 0.00159 / 3.14 ≈ 0.000506 ≈ 0.051%.В численных методах мы всегда получаем приближённое решение. Важно понимать, насколько оно близко к точному — иначе можно принять неверный ответ за правильный.
Точность (обозначается греческой буквой ε, «эпсилон») — это число, задающее допустимую погрешность. Мы хотим, чтобы результат отличался от истинного не больше чем на ε.
Обычно задаётся как малое число: ε = 10⁻⁶ (одна миллионная) или ε = 10⁻⁹.
Если ε = 0.001, то приближение x = 1.3247 при истинном корне x* = 1.3247179 нас устраивает: |1.3247 − 1.3247179| = 0.0000179 < 0.001 ✓.
А приближение x = 1.32 — нет: |1.32 − 1.3247179| = 0.0047 > 0.001 ✗.
В коде: epsilon = 1e-6 — это 10⁻⁶. Все методы останавливаются, когда ошибка становится меньше ε.
Без критерия остановки итерационный метод может работать бесконечно (или до переполнения памяти). ε — это «планка», при достижении которой мы говорим: «достаточно точно».
Итерация — это один шаг повторяющегося процесса. В численных методах итерация — это одно уточнение приближения.
Итерационный метод — метод, который начинает с приближения и последовательно улучшает его на каждой итерации, пока не достигнет нужной точности.
Метод Ньютона: x₀ → x₁ → x₂ → x₃ → .... Каждая стрелка — одна итерация.
Если метод сходится за 5 итераций — значит, потребовалось 5 уточнений.
Понимание того, что методы итерационные, помогает правильно оценивать время работы. Быстрый метод — тот, которому нужно меньше итераций.
Сходимость — это свойство итерационного метода приближаться к истинному ответу при увеличении числа итераций.
Если метод сходится — значения xₙ с ростом n всё ближе к корню.
Если метод расходится — значения «улетают» в бесконечность или колеблются.
Слева: метод сходится (точки приближаются к ответу). Справа: расходится (точки улетают)
Не все методы сходятся на всех задачах. Например, метод Ньютона сходится только при хорошем начальном приближении. Понимание условий сходимости — обязательно.
Линейная сходимость — это сходимость, при которой ошибка на каждой итерации уменьшается в постоянное число раз.
Формально: |xₙ₊₁ − x*| ≈ C · |xₙ − x*|, где C < 1 — константа.
Проще: если ошибка была 0.1, потом 0.01, потом 0.001 — это линейная сходимость (каждый раз делим на 10).
Примеры: метод бисекции (делит отрезок пополам — ошибка уменьшается в 2 раза за шаг), метод хорд (уменьшает примерно в 1.5–2 раза).
При линейной сходимости число верных знаков растёт медленно и равномерно. Для достижения точности 10⁻⁶ может понадобиться 20–50 итераций.
Зная тип сходимости, вы можете предсказать, сколько шагов потребуется. Для линейной сходимости — «много». Именно поэтому методы с линейной сходимостью (бисекция, хорды) считаются «медленными».
Квадратичная сходимость — это сходимость, при которой ошибка на каждой итерации уменьшается пропорционально квадрату предыдущей ошибки.
Формально: |xₙ₊₁ − x*| ≈ C · |xₙ − x*|².
Проще: число верных знаков удваивается на каждом шаге.
Пусть текущая ошибка 0.1. Тогда:
| Итерация | Ошибка при линейной | Ошибка при квадратичной |
|---|---|---|
| 0 | 0.1 | 0.1 |
| 1 | 0.01 | 0.01 |
| 2 | 0.001 | 0.0001 |
| 3 | 0.0001 | 0.00000001 |
| 4 | 0.00001 | 10⁻¹⁶ (предел точности) |
Впечатляющий факт: квадратичная сходимость позволяет достичь максимальной точности компьютера (15–16 знаков) всего за 5–6 итераций. Именно так работает метод Ньютона.
Квадратичная сходимость — «королевская» скорость. Именно из-за неё метод Ньютона используется в промышленных пакетах (MATLAB, numpy, TensorFlow). Понимание этого термина — ключ к пониманию, почему Ньютон так популярен.
Матрица — это прямоугольная таблица чисел. Обозначается заглавной буквой: A, B.
СЛАУ (Система Линейных Алгебраических Уравнений) — это несколько линейных уравнений, в которых неизвестные связаны друг с другом.
Любую СЛАУ можно записать в матричной форме: A · x = b, где A — матрица коэффициентов, x — вектор неизвестных, b — вектор правых частей.
Система:
2x₁ + x₂ = 5
x₁ − x₂ = 1
В матричной форме:
A =
[2 1]
[1 −1]
, x =
[x₁]
[x₂]
, b =
[5]
[1]
СЛАУ — «рабочая лошадка» вычислительной математики. Нейросети, 3D-графика, инженерные расчёты — всё это сводится к решению систем уравнений. Раздел 3 курса полностью посвящён этому.
Диагональное преобладание — это свойство квадратной матрицы, при котором для каждой строки модуль диагонального элемента больше суммы модулей всех остальных элементов этой строки:
|aᵢᵢ| > Σⱼ≠ᵢ |aᵢⱼ|
Матрица:
[10 1 −1]
[ 1 11 1]
[−1 1 12]
|10| > |1| + |−1| = 2 ✓|11| > |1| + |1| = 2 ✓|12| > |−1| + |1| = 2 ✓Все три условия выполнены → матрица имеет диагональное преобладание.
Когда это нужно: диагональное преобладание — достаточное условие сходимости итерационных методов (простая итерация, метод Зейделя). Если оно есть — метод гарантированно сойдётся.
Перед запуском итерационных методов решения СЛАУ нужно проверить это условие. Если его нет — метод может «разбежаться», и программа зависнет. В практической работе №4 это отдельное задание.
💡 Подсказка: используйте клавиши ← → на клавиатуре для переключения слайдов