---

ЧИСЛЕННЫЕ МЕТОДЫ - ТЕОРИЯ ДЛЯ ЭКЗАМЕНА ПО ЛЕКЦИЯМ

Как пользоваться этим файлом

1. Открой файл и ищи тему через Ctrl+F.
2. Для ответа на теоретический вопрос бери: определение, идею метода, формулу, условия применимости, плюсы и минусы, критерий остановки или оценку ошибки.
3. Не надо учить весь текст слово в слово. Лучше понимать схему ответа и уметь переписать своими словами.
4. Если теория идет рядом с практикой, сначала найди метод из практики. Обычно теория спрашивает соседние вещи из того же раздела.

Общая структура курса по лекциям

1. Теория приближенных вычислений.
2. Численное решение нелинейных уравнений и систем нелинейных уравнений.
3. Методы интерполирования и экстраполяции функций.
4. Численные методы линейной алгебры для матриц.
5. Методы численного дифференцирования.
6. Ряды Фурье и спектральный анализ.

===============================================================================
1. ЧТО ТАКОЕ ЧИСЛЕННЫЕ МЕТОДЫ
===============================================================================

Определение

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

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

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

Этапы решения прикладной задачи

1. Постановка задачи.
Нужно понять, что дано и что требуется найти.

2. Построение математической модели.
Реальная задача заменяется уравнением, системой, функцией, матрицей или другим математическим объектом.

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

4. Вычисление.
Метод реализуется вручную или на компьютере.

5. Анализ результата.
Нужно понять, насколько ответ точный и адекватен ли он исходной задаче.

Аналитические, графические и численные методы

Аналитические методы:
- дают формулу или точное выражение;
- позволяют делать теоретические выводы;
- но часто неприменимы для сложных задач.

Графические методы:
- дают наглядное представление;
- позволяют грубо оценить значение;
- но имеют низкую точность.

Численные методы:
- дают число или набор чисел;
- позволяют решать задачи без точной формулы;
- но всегда содержат погрешность.

Главная мысль для экзамена

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

===============================================================================
2. ПОГРЕШНОСТИ
===============================================================================

Определение погрешности

Погрешность - это разница между точным значением величины и ее приближенным значением.

Если точное значение равно a, а приближенное значение равно a_p, то:

absolute_error = abs(a - a_p)

Абсолютная погрешность

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

Формула:

Delta = abs(a - a_p)

Например, если точное значение 10, а приближенное 9.8, то абсолютная погрешность равна 0.2.

Относительная погрешность

Относительная погрешность показывает ошибку относительно размера самой величины.

Формула:

delta = Delta / abs(a)

Иногда ее выражают в процентах:

delta_percent = delta * 100%

Например, ошибка 0.1 при числе 100 почти незаметна, а ошибка 0.1 при числе 0.2 очень большая. Поэтому относительная погрешность часто важнее абсолютной.

Предельная абсолютная погрешность

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

Предельная абсолютная погрешность - это число, которое точно не меньше реальной абсолютной погрешности.

То есть если реальная ошибка неизвестна, но известно, что она не больше некоторого Delta_a, то Delta_a называют предельной абсолютной погрешностью.

Предельная относительная погрешность

Предельная относительная погрешность примерно считается так:

delta_x = Delta_x / abs(x)

где x - приближенное значение, если точное значение неизвестно.

Полная погрешность

Полная погрешность состоит из трех частей:

1. Неустранимая погрешность.
Она связана с неточностью исходных данных или с тем, что математическая модель не полностью описывает реальность.

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

3. Вычислительная погрешность.
Она возникает из-за округления чисел при вводе, вычислениях и выводе.

Формула по смыслу:

total_error = data_error + method_error + rounding_error

Неустранимая погрешность

Неустранимая погрешность делится на:
- погрешность исходных данных;
- погрешность математической модели.

Пример: если температура измерена с ошибкой, то никакой численный метод не сделает исходные данные точными.

Погрешность метода

Погрешность метода появляется из-за замены точной задачи приближенной схемой.

Примеры:
- интеграл заменили суммой прямоугольников;
- производную заменили разностью;
- корень ищем не точно, а до eps;
- дифференциальное уравнение решаем с шагом h.

Вычислительная погрешность

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

Поэтому при большом количестве операций ошибки округления накапливаются.

===============================================================================
3. ВЕРНЫЕ ЦИФРЫ И ОКРУГЛЕНИЕ
===============================================================================

Значащие цифры

Значащие цифры - это все цифры числа, начиная с первой ненулевой.

Примеры:
0.00314 имеет три значащие цифры: 3, 1, 4.
120.5 имеет четыре значащие цифры: 1, 2, 0, 5.

Верные цифры в строгом смысле

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

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

Верные цифры в широком смысле

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

Связь с относительной погрешностью

Если относительная погрешность примерно равна 10^(-k), то можно ожидать около k верных значащих цифр.

Правило для положительного приближенного числа

Если положительное приближенное число имеет n верных значащих цифр, то его относительная погрешность ограничивается величиной вида:

delta <= 10^(1-n) / first_digit

где first_digit - первая значащая цифра числа.

Как округлять погрешность

Обычно погрешность округляют до 1 или 2 значащих цифр. Само приближенное значение округляют до того же разряда, что и погрешность.

Что писать на экзамене

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

===============================================================================
4. КОМПЬЮТЕРНАЯ АРИФМЕТИКА
===============================================================================

Почему компьютерные вычисления отличаются от ручных

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

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

Числа с плавающей точкой

Число с плавающей точкой хранится примерно в виде:

number = sign * mantissa * base^exponent

В двоичной машине base обычно равен 2.

Смысл:
- sign хранит знак;
- mantissa хранит значащие цифры;
- exponent хранит порядок числа.

Преимущество плавающей точки

Можно хранить очень большие и очень маленькие числа.

Недостаток

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

Overflow

Overflow - переполнение.

Оно возникает, когда результат по модулю больше максимально представимого числа. Тогда компьютер может получить infinity или аварийное значение.

Underflow

Underflow - исчезновение порядка.

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

Потеря значимости

Потеря значимости возникает при вычитании близких чисел.

Пример:

u = x - y

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

Это важно для:
- метода секущих;
- численного дифференцирования;
- вычисления разностей;
- работы с почти одинаковыми числами.

Накопление ошибок

Если алгоритм выполняет миллионы операций, маленькие ошибки округления могут накопиться.

Особенно опасны:
- длинные суммы;
- вычитание близких чисел;
- плохо обусловленные системы;
- слишком маленький шаг h в разностных формулах.

Суммирование Кэхэна

Суммирование Кэхэна уменьшает ошибку при сложении многих чисел.

Идея: кроме суммы хранится компенсация c, куда попадает потерянная из-за округления часть.

Формулы:

y = x_i - c
t = sum + y
c = (t - sum) - y
sum = t

Что писать на экзамене

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

===============================================================================
5. ПОГРЕШНОСТИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
===============================================================================

Сложение

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

Главная идея: сложение чисел одного знака относительно безопасно.

Вычитание

При вычитании абсолютные погрешности складываются.

Если:

u = x - y

то абсолютная погрешность результата зависит от погрешностей x и y.

Опасность: если x и y близки, то знаменатель в относительной погрешности мал, и относительная ошибка результата может стать большой.

Умножение и деление

При умножении и делении обычно складываются относительные погрешности.

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

Практический вывод

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

===============================================================================
6. СЛОЖНОСТЬ АЛГОРИТМОВ
===============================================================================

Определение

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

Обычно сложность записывают через O(...).

Примеры классов сложности

O(1) - постоянная сложность. Время почти не зависит от размера входа.

O(log n) - логарифмическая сложность. Пример: деление отрезка пополам, поиск в отсортированном массиве.

O(n) - линейная сложность. Нужно один раз пройти по данным.

O(n^2) - квадратичная сложность. Часто возникает при двух вложенных циклах.

O(n^3) - кубическая сложность. Пример: наивное умножение матриц.

O(2^n) - экспоненциальная сложность. Очень быстро становится непрактичной.

Примеры из численных методов

Бисекция:
число итераций примерно log2((b-a)/eps)

Наивное умножение матриц:
O(n^3)

Метод Штрассена:
примерно O(n^2.807)

ДПФ:
O(N^2)

БПФ:
O(N log N)

Почему это важно

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

Что писать на экзамене

При выборе численного метода нужно учитывать не только точность, но и вычислительную сложность, объем памяти и устойчивость алгоритма.

===============================================================================
7. ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ
===============================================================================

Определение

Численное интегрирование - это приближенное вычисление определенного интеграла.

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

Интеграл от f(x) на отрезке [a,b] можно понимать как площадь под графиком функции, ограниченную осью Ox, графиком f(x) и прямыми x=a и x=b.

Идея всех простых методов интегрирования

Отрезок [a,b] делится на N частей.

Шаг:

h = (b - a) / N

Площадь под графиком заменяется суммой площадей простых фигур:
- прямоугольников;
- трапеций;
- криволинейных трапеций через параболы.

Формула прямоугольников

Левые прямоугольники:

S = h * sum f(a + i*h), i = 0..N-1

Правые прямоугольники:

S = h * sum f(a + i*h), i = 1..N

Средние прямоугольники:

S = h * sum f(a + (i+0.5)*h), i = 0..N-1

Смысл: на каждом маленьком отрезке график заменяется горизонтальным отрезком.

Плюсы прямоугольников:
- очень простой метод;
- легко реализовать.

Минусы:
- точность невысокая;
- результат сильно зависит от выбора точки внутри отрезка.

Формула трапеций

Идея: на каждом маленьком отрезке график заменяется прямой линией. Площадь считается как площадь трапеции.

Формула:

S = h * ( (f(a)+f(b))/2 + sum f(a+i*h), i=1..N-1 )

Плюсы:
- обычно точнее прямоугольников;
- простая формула.

Минусы:
- все равно приближает функцию линейно;
- на сильно изогнутой функции ошибка может быть заметной.

Формула Симпсона

Идея: на каждом двойном отрезке функция заменяется параболой.

Формула:

S = h/3 * [ f(a) + f(b) + 4 * sum f(a+i*h) по нечетным i + 2 * sum f(a+i*h) по четным i ]

Важно: N должно быть четным.

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

Минусы:
- нужно четное число интервалов;
- формула сложнее.

Что писать на экзамене

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

===============================================================================
8. НЕЛИНЕЙНЫЕ УРАВНЕНИЯ
===============================================================================

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

Нужно найти корень уравнения:

f(x) = 0

Корень - это такое x, при котором функция равна нулю.

Отделение корней

Перед уточнением корня часто нужно найти отрезок [a,b], где расположен корень.

Если f(a)*f(b) < 0 и f непрерывна, то на отрезке есть хотя бы один корень.

Это основано на теореме о промежуточном значении.

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

Другое название: метод бисекции.

Условия:
- функция непрерывна на [a,b];
- f(a)*f(b) < 0.

Идея: отрезок делится пополам.

Берется середина:

c = (a+b)/2

Потом выбирается та половина, где сохраняется смена знака.

Критерии остановки:

abs(f(c)) < eps

или

abs(b-a) < eps.

Число итераций:

n >= log2((b-a)/eps)

Плюсы:
- надежный;
- не нужна производная;
- корень не теряется.

Минусы:
- сходится медленно;
- нужен отрезок со сменой знака.

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

Метод простой итерации

Постановка: уравнение f(x)=0 приводят к виду:

x = phi(x)

Итерационный процесс:

x_next = phi(x)

Идея: начиная с x0, строится последовательность приближений. Если она сходится, ее предел является решением.

Условие сходимости:
если abs(phi_prime(x)) <= q < 1 на нужном отрезке, то метод сходится.

Смысл: phi должна быть сжимающим отображением.

Критерий остановки:

abs(x_next - x) < eps

Плюсы:
- простая формула;
- не нужна производная f(x);
- удобно, если уравнение уже приведено к x=phi(x).

Минусы:
- нужно правильно выбрать phi;
- может не сходиться;
- часто сходится медленно.

Что писать:
Метод простой итерации ищет неподвижную точку функции phi. Сходимость гарантируется, если phi сжимает расстояния, то есть abs(phi_prime) меньше 1.

Метод хорд, или секущих

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

Формула одного из вариантов:

x_next = x_curr - f(x_curr)*(x_curr-x_prev)/(f(x_curr)-f(x_prev))

Идея: через две точки графика проводится прямая. Точка пересечения этой прямой с осью Ox берется как новое приближение.

Плюсы:
- не нужна производная;
- часто быстрее бисекции.

Минусы:
- сходимость не гарантирована;
- чувствителен к начальным точкам;
- может страдать от потери значимости, если f(x_curr) и f(x_prev) близки.

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

Метод Ньютона, или метод касательных

Постановка: решаем f(x)=0.

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

Формула:

x_next = x - f(x)/f_prime(x)

Что нужно:
- функция f(x);
- производная f_prime(x);
- начальное приближение x0.

Критерий остановки:

abs(x_next - x) < eps

или

abs(f(x_next)) < eps

Сходимость: при хорошем начальном приближении метод сходится быстро, обычно квадратично.

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

Плюсы:
- быстрый;
- часто требует мало итераций.

Минусы:
- нужна производная;
- плохой x0 может привести к расходимости;
- если f_prime(x) близка к нулю, шаг становится слишком большим.

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

Модифицированный метод Ньютона

Идея: в обычном методе Ньютона производная пересчитывается на каждом шаге. В модифицированном методе производную фиксируют, например в точке x0.

Формула:

x_next = x - f(x)/f_prime(x0)

Плюсы:
- дешевле итерация;
- удобно, если производную считать сложно.

Минусы:
- сходимость обычно медленнее;
- если f_prime(x0) плохая, метод может не сойтись.

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

Метод дихотомии для минимума

Этот метод похож на деление пополам, но используется для поиска минимума функции на отрезке.

Идея: берутся две близкие точки около середины отрезка:

x1 = mid - delta
x2 = mid + delta

Сравниваются f(x1) и f(x2). Часть отрезка, где минимума быть не может, отбрасывается.

Критерий остановки:

abs(b-a) < eps

Условие: метод хорошо работает для функции с одним минимумом на отрезке.

===============================================================================
9. СИСТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
===============================================================================

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

Нужно решить систему:

F(x) = 0

где F(x) - вектор функций, а x - вектор неизвестных.

Пример для двух переменных:

F1(x,y) = 0
F2(x,y) = 0

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

Систему приводят к виду:

x = g(x)

Итерационный процесс:

x_next = g(x)

Критерий остановки:

norm(x_next - x) < eps

или

norm(F(x_next)) < eps

Условие сходимости: отображение g должно быть сжимающим.

Плюсы:
- простая схема;
- не нужен Якобиан.

Минусы:
- нужно правильно построить g;
- сходимость может быть медленной;
- может не сойтись.

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

Идея: нелинейная система в текущей точке заменяется линейной системой.

Матрица Якоби

Якобиан - это матрица частных производных.

Для системы F1, F2 по переменным x, y:

J = [ dF1/dx  dF1/dy
      dF2/dx  dF2/dy ]

Формула метода Ньютона

На каждом шаге решается линейная система:

J(x_k) * delta = -F(x_k)

Потом:

x_next = x_k + delta

Критерий остановки:

norm(delta) < eps

или

norm(F(x_next)) < eps

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

Плюсы:
- быстро сходится около решения;
- мощный метод для систем.

Минусы:
- нужно считать Якобиан;
- нужно решать линейную систему на каждом шаге;
- плохой старт может привести к расходимости.

Что писать:
Метод Ньютона для систем использует линеаризацию векторной функции. Якобиан играет роль производной. Поправка находится из линейной системы.

Гаусс-Зейдель как итерационный подход

В контексте систем можно встретить итерационные схемы типа Гаусса-Зейделя.

Идея: переменные обновляются по очереди. Новое значение сразу используется при вычислении следующих переменных.

Плюсы:
- простая итерационная схема;
- не всегда нужно решать полную систему сразу.

Минусы:
- сходимость не всегда гарантирована;
- обычно сходимость линейная;
- зависит от свойств системы.

===============================================================================
10. ИНТЕРПОЛЯЦИЯ, ЭКСТРАПОЛЯЦИЯ, АППРОКСИМАЦИЯ
===============================================================================

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

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

Если известны точки:

(x0,y0), (x1,y1), ..., (xn,yn)

то интерполяционная функция должна давать:

F(x_i) = y_i

Экстраполяция

Экстраполяция - это нахождение значения вне диапазона известных узлов.

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

Аппроксимация

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

Она полезна для зашумленных данных.

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

Один полином строится сразу по всем узлам. Пример: полином Лагранжа.

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

Локальная интерполяция

Для каждого участка используются ближайшие точки.

Примеры:
- ступенчатая;
- линейная;
- квадратичная;
- сплайны.

Ступенчатая интерполяция

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

Плюсы:
- максимально простая.

Минусы:
- разрывная;
- низкая точность.

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

Функция между двумя соседними точками заменяется прямой.

Формула:

F(x) = y_i*(x_{i+1}-x)/(x_{i+1}-x_i) + y_{i+1}*(x-x_i)/(x_{i+1}-x_i)

для x_i < x < x_{i+1}.

Плюсы:
- простая;
- непрерывная;
- хорошо работает на малых промежутках.

Минусы:
- в узлах есть изломы;
- производная разрывна;
- невысокая точность для кривых функций.

Квадратичная интерполяция

Используется парабола по трем соседним точкам.

Алгоритм:
1. Найти отрезок или группу точек, содержащую x_star.
2. Построить полином второй степени.
3. Подставить x_star в полином.

Плюсы:
- точнее линейной;
- учитывает кривизну.

Минусы:
- сложнее;
- может давать лишние колебания.

Полином Лагранжа

Определение

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

Формула:

P(x) = sum y_i * L_i(x)

где базисный полином:

L_i(x) = product over j != i of (x - x_j)/(x_i - x_j)

Свойство:

L_i(x_j) = 1, если i=j
L_i(x_j) = 0, если i != j

Почему работает

В каждом узле x_j все базисные полиномы, кроме одного, становятся равны нулю. Остается только y_j. Поэтому P(x_j)=y_j.

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

Минусы:
- при большом числе точек может быть неустойчивым;
- добавление новой точки требует перестроить полином;
- плохо подходит для шумных данных.

Погрешность интерполирования

Ошибка зависит от:
- гладкости функции;
- расположения узлов;
- степени полинома;
- расстояния между узлами.

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

Сплайны

Определение

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

Кубический сплайн

На каждом отрезке используется полином третьей степени:

S_i(x) = a_i + b_i*(x-x_i) + c_i*(x-x_i)^2 + d_i*(x-x_i)^3

Условия:
- сплайн проходит через узлы;
- значения соседних полиномов совпадают в узлах;
- первые производные совпадают;
- вторые производные совпадают;
- задаются граничные условия.

Натуральный кубический сплайн

У натурального сплайна вторые производные на концах равны нулю.

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

Минусы:
- нужно решать систему для коэффициентов;
- реализация сложнее.

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

Билинейная интерполяция - это расширение линейной интерполяции на функцию двух переменных.

Идея: сначала выполняется линейная интерполяция в одном направлении, потом в другом.

Используются четыре значения функции в вершинах прямоугольника.

Что писать:
Билинейная интерполяция интерполирует значение внутри прямоугольника по четырем значениям в его вершинах.

===============================================================================
11. ЛИНЕЙНАЯ АЛГЕБРА И МАТРИЦЫ
===============================================================================

Плотные матрицы

Плотная матрица - это матрица, в которой большинство элементов ненулевые. Для нее обычно хранят все n^2 элементов.

Разреженные матрицы

Разреженная матрица содержит много нулей. Хранить все элементы невыгодно, поэтому хранят только ненулевые элементы и их индексы.

Плюсы разреженного хранения:
- меньше памяти;
- быстрее умножение на вектор, если ненулевых элементов мало.

Основные операции и сложность

Скалярное произведение векторов:
O(n)

Умножение матрицы на вектор:
O(n^2)

Умножение матриц наивным методом:
O(n^3)

Решение системы методом Гаусса:
O(n^3)

QR-разложение:
O(n^3)

===============================================================================
12. СОБСТВЕННЫЕ ЗНАЧЕНИЯ И СОБСТВЕННЫЕ ВЕКТОРЫ
===============================================================================

Определение

Число lambda называется собственным значением матрицы A, если существует ненулевой вектор x такой, что:

A*x = lambda*x

Вектор x называется собственным вектором.

Смысл

При умножении на матрицу A собственный вектор не меняет направление, а только растягивается или сжимается в lambda раз.

Характеристическое уравнение

Собственные значения можно найти из уравнения:

det(A - lambda*I) = 0

Это характеристическое уравнение.

Для маленьких матриц его можно решать напрямую. Для больших матриц используют численные методы.

Спектр матрицы

Спектр матрицы - это набор всех ее собственных значений.

Спектральный радиус

Спектральный радиус - это максимальный модуль собственного значения:

rho(A) = max abs(lambda_i)

===============================================================================
13. СТЕПЕННОЙ МЕТОД
===============================================================================

Назначение

Степенной метод ищет доминирующее собственное значение, то есть собственное значение с наибольшим модулем.

Идея

Берем начальный вектор x0. На каждом шаге умножаем его на матрицу:

y = A*x

Потом нормируем:

x_next = y / norm(y)

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

Оценка lambda

Можно использовать отношение Релея:

lambda = (A*x, x) / (x, x)

Сходимость

Скорость сходимости зависит от отношения:

abs(lambda_2 / lambda_1)

Если lambda_1 сильно больше lambda_2 по модулю, метод сходится быстро. Если они близки, метод сходится медленно.

Зачем нужна нормировка

Без нормировки вектор может стать слишком большим или слишком маленьким. Нормировка защищает от overflow и underflow.

Плюсы:
- простой;
- подходит для больших матриц;
- не ищет весь спектр.

Минусы:
- ищет только доминирующее собственное значение;
- может медленно сходиться;
- не работает хорошо при малом спектральном зазоре.

===============================================================================
14. ОБРАТНЫЙ СТЕПЕННОЙ МЕТОД СО СДВИГОМ
===============================================================================

Назначение

Метод ищет собственное значение, близкое к заданному числу sigma.

Идея

Вместо A используется матрица:

A - sigma*I

На каждом шаге решается система:

(A - sigma*I)*y = x

Потом y нормируется.

Почему работает

Если sigma близко к нужному собственному значению, то после обращения матрицы это значение становится доминирующим для итерационного процесса.

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

Минусы:
- на каждом шаге нужно решать линейную систему;
- если A - sigma*I плохо обусловлена, могут быть большие ошибки;
- нужно выбрать sigma.

===============================================================================
15. КРУГИ ГЕРШГОРИНА
===============================================================================

Назначение

Круги Гершгорина позволяют оценить, где находятся собственные значения матрицы.

Для каждой строки строится круг.

Центр:

center_i = a_ii

Радиус:

radius_i = sum abs(a_ij), j != i

Теорема

Все собственные значения матрицы лежат в объединении кругов Гершгорина.

Плюсы:
- быстро;
- не нужно решать характеристическое уравнение;
- дает область локализации спектра.

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

===============================================================================
16. QR-РАЗЛОЖЕНИЕ
===============================================================================

Определение

QR-разложение представляет матрицу A как произведение:

A = Q*R

где:
Q - ортогональная матрица;
R - верхнетреугольная матрица.

Ортогональная матрица

Матрица Q ортогональна, если:

Q^T * Q = I

Это значит, что ее столбцы имеют длину 1 и взаимно перпендикулярны.

Верхнетреугольная матрица

Матрица R верхнетреугольная, если все элементы ниже главной диагонали равны 0.

Грамм-Шмидт

Один способ построения QR - ортогонализация Грамма-Шмидта.

Идея: из столбцов A строятся ортонормированные столбцы Q. Каждый новый столбец очищается от проекций на предыдущие.

Проверка:

A примерно равно Q*R
Q^T*Q примерно равно I

Плюсы:
- понятный метод;
- строит ортонормированный базис.

Минусы:
- классический Грамм-Шмидт может быть численно неустойчивым;
- при почти зависимых столбцах возникают ошибки.

Отражения Хаусхолдера

Более устойчивый способ строить QR - отражения Хаусхолдера.

Отражение Хаусхолдера имеет вид:

H = I - 2*v*v^T/(v^T*v)

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

Плюсы:
- устойчивее Грамма-Шмидта;
- используется в реальных алгоритмах линейной алгебры.

===============================================================================
17. РАЗЛОЖЕНИЕ ШУРА И QR-АЛГОРИТМ
===============================================================================

Теорема Шура

Для матрицы A можно получить представление:

A = U*T*U^T

где:
U - ортогональная или унитарная матрица;
T - верхнетреугольная матрица.

Диагональные элементы T являются собственными значениями матрицы.

Смысл

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

QR-алгоритм

QR-алгоритм ищет собственные значения матрицы.

На каждом шаге:

A_k = Q_k*R_k

Затем:

A_{k+1} = R_k*Q_k

Почему собственные значения сохраняются

Матрицы A_k и A_{k+1} подобны, поэтому имеют одинаковые собственные значения.

Результат

Для симметричной матрицы A_k стремится к диагональной матрице. Для несимметричной - к верхнетреугольной форме Шура.

Сходимость

Скорость зависит от зазоров между собственными значениями. Сдвиги ускоряют сходимость.

QR со сдвигами

Вместо обычного QR применяют QR к матрице:

A_k - sigma*I

После шага возвращают сдвиг.

Идея: сдвиг помогает быстрее выделять собственные значения.

Гессенбергова форма

Верхне-гессенбергова матрица имеет нули ниже первой поддиагонали.

То есть элементы a_ij = 0 при i >= j+2.

Зачем нужна: перед QR-алгоритмом матрицу приводят к гессенберговой форме, чтобы QR-итерации были дешевле.

Что писать:
QR-алгоритм многократно применяет QR-разложение и сохраняет спектр матрицы, постепенно приводя ее к форме, где собственные значения читаются с диагонали.

===============================================================================
18. SVD И PCA
===============================================================================

SVD

Сингулярное разложение матрицы:

A = U*S*V^T

где:
U и V - ортогональные матрицы;
S - диагональная матрица с неотрицательными сингулярными числами.

Сингулярные числа

Сингулярные числа связаны с собственными значениями матрицы A^T*A.

Если lambda_i - собственные значения A^T*A, то сингулярные числа:

sigma_i = sqrt(lambda_i)

Смысл SVD

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

Применение:
- сжатие изображений;
- понижение размерности;
- анализ данных;
- фильтрация шума.

PCA

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

Если данные центрированы, ковариационная матрица имеет собственные векторы, которые являются главными компонентами.

Связь с SVD: PCA часто считают через SVD матрицы данных.

Что писать:
SVD раскладывает матрицу на ортогональные направления и сингулярные числа. PCA использует эти идеи для поиска главных направлений разброса данных.

===============================================================================
19. УМНОЖЕНИЕ МАТРИЦ И ШТРАССЕН
===============================================================================

Наивное умножение

Для матриц A и B элемент C[i,j] считается так:

C[i,j] = sum A[i,k]*B[k,j]

Сложность для n на n:

O(n^3)

Метод Штрассена

Идея: обычное блочное умножение матриц 2 на 2 требует 8 блочных умножений. Штрассен заменяет их на 7 блочных умножений, добавляя больше сложений и вычитаний.

Сложность:

O(n^log2(7)) примерно O(n^2.807)

Плюсы:
- асимптотически быстрее наивного метода.

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

Архитектура памяти

Реальная скорость зависит не только от числа операций. Важно, как алгоритм работает с кэшем и памятью.

Блочное умножение может быть быстрее за счет лучшего доступа к памяти. Штрассен может проигрывать на малых размерах из-за временных массивов.

===============================================================================
20. ЧИСЛЕННОЕ ДИФФЕРЕНЦИРОВАНИЕ
===============================================================================

Определение

Численное дифференцирование - это приближенное вычисление производной по значениям функции.

Идея

Производная заменяется разностным отношением.

Сетка

Пусть есть узлы:

x_i = x_0 + i*h

где h - шаг сетки.

Прямая разность

Использует текущую и правую точку:

f_prime(x) примерно (f(x+h)-f(x))/h

Порядок ошибки:
O(h)

Обратная разность

Использует текущую и левую точку:

f_prime(x) примерно (f(x)-f(x-h))/h

Порядок ошибки:
O(h)

Центральная разность

Использует точки с двух сторон:

f_prime(x) примерно (f(x+h)-f(x-h))/(2*h)

Порядок ошибки:
O(h^2)

Почему центральная лучше

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

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

Центральная формула:

f_second(x) примерно (f(x+h)-2*f(x)+f(x-h))/(h^2)

Порядок ошибки:
O(h^2)

Ошибка усечения

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

Ошибка округления

Если h слишком маленький, то f(x+h) и f(x) почти равны. При их вычитании возникает потеря значимости. Потом деление на маленький h усиливает ошибку.

Итог

Нельзя бесконечно уменьшать h. Существует оптимальный шаг, где сумма ошибки усечения и ошибки округления минимальна.

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

===============================================================================
21. РАЗНОСТНЫЕ СХЕМЫ: НЕВЯЗКА, АППРОКСИМАЦИЯ, УСТОЙЧИВОСТЬ, СХОДИМОСТЬ
===============================================================================

Невязка

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

Для уравнения f(x)=0:

residual = abs(f(x))

Для системы A*x=b:

residual = norm(A*x-b)

Аппроксимация

Разностная схема аппроксимирует исходную задачу, если при h -> 0 она переходит в исходное дифференциальное уравнение.

Смысл: формула должна становиться точной при уменьшении шага.

Устойчивость

Схема устойчива, если малые ошибки в данных или вычислениях не растут неограниченно.

Смысл: если немного испортить начальные данные, решение не должно взорваться.

Сходимость

Схема сходится, если численное решение стремится к точному при h -> 0.

Связь

Для корректных линейных задач важна идея: аппроксимация + устойчивость дают сходимость.

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

===============================================================================
22. ОБЫКНОВЕННЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ УРАВНЕНИЯ
===============================================================================

Задача Коши

Задача Коши задается уравнением:

y' = f(x,y)

и начальным условием:

y(x0) = y0

Нужно найти приближенное значение y на отрезке.

Метод Эйлера

Идея: на каждом шаге решение продолжается по касательной.

Формула:

y_{n+1} = y_n + h*f(x_n, y_n)

x_{n+1} = x_n + h

Порядок точности: первый порядок.

Плюсы:
- самый простой метод;
- легко реализуется.

Минусы:
- низкая точность;
- может быть неустойчивым при большом h.

Метод Эйлера с пересчетом, или предиктор-корректор

Идея: сначала делается прогноз обычным Эйлером:

y_pred = y_n + h*f(x_n,y_n)

Потом коррекция:

y_corr = y_n + h/2 * ( f(x_n,y_n) + f(x_{n+1}, y_pred) )

Смысл: используется средний наклон на шаге.

Плюсы:
- точнее простого Эйлера.

Минусы:
- требует больше вычислений функции.

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

Один из вариантов:

k1 = h*f(x_n,y_n)
k2 = h*f(x_n+h, y_n+k1)

y_{n+1} = y_n + (k1+k2)/2

Идея: берется среднее из двух наклонов.

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

Формулы:

k1 = h*f(x_n, y_n)
k2 = h*f(x_n+h/2, y_n+k1/2)
k3 = h*f(x_n+h/2, y_n+k2/2)
k4 = h*f(x_n+h, y_n+k3)

y_{n+1} = y_n + (k1+2*k2+2*k3+k4)/6

Порядок точности: четвертый порядок.

Плюсы:
- высокая точность;
- самостартующий метод;
- хорошо работает для гладких задач.

Минусы:
- четыре вычисления функции на шаг;
- для жестких задач может требовать очень маленький шаг.

Системы ОДУ

Если неизвестных функций несколько, их собирают в вектор.

Пример:

x' = v
v' = -x

Тогда:

u = [x, v]
u' = F(t,u)

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

Фазовый портрет

Фазовый портрет - это график зависимости переменных системы друг от друга, например x от v.

Он показывает качественное поведение системы:
- колебания;
- устойчивость;
- циклы;
- уход решения.

Локальная и глобальная ошибка

Локальная ошибка - ошибка за один шаг, если предыдущая точка была точной.

Глобальная ошибка - накопленная ошибка на всем интервале.

Для RK4:
локальная ошибка порядка O(h^5), глобальная ошибка порядка O(h^4).

Устойчивость для ОДУ

Метод устойчив, если ошибки не растут неограниченно при переходе от шага к шагу.

Если h слишком большой, даже правильный метод может дать плохой результат.

Жесткие системы

Жесткая система имеет процессы с разными масштабами времени. Явные методы, например Эйлер и RK4, могут требовать очень маленький шаг. Для жестких систем часто лучше неявные методы.

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

Методы Адамса - многошаговые. Они используют не только текущую точку, но и предыдущие значения.

Адамс-Башфорт

Явный многошаговый метод. Часто используется как предиктор.

Адамс-Мултон

Неявный или полунеявный многошаговый метод. Часто используется как корректор.

Пример предиктор-корректор:

AB2:
y_pred = y_n + h/2*(3*f_n - f_{n-1})

AM2:
y_corr = y_n + h/2*(f(x_{n+1}, y_pred) + f_n)

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

Адаптивный шаг

Адаптивный шаг меняет h в процессе решения.

Если решение быстро меняется, h уменьшают. Если решение гладкое, h увеличивают.

Смысл: поддержать нужную точность без лишних вычислений.

===============================================================================
23. ДЕТЕРМИНИРОВАННЫЙ ХАОС
===============================================================================

Определение

Детерминированный хаос - это поведение системы, где уравнения не случайные, но решение очень чувствительно к начальным условиям.

Малое изменение начального условия может через некоторое время привести к сильно другому решению.

Признаки хаоса:
- чувствительность к начальным условиям;
- сложное поведение;
- невозможность долгосрочного точного прогноза.

Почему важно для численных методов

При моделировании хаотических систем ошибки округления и ошибки метода могут быстро усиливаться.

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

===============================================================================
24. РЯДЫ ФУРЬЕ
===============================================================================

Идея

Сложный периодический сигнал можно представить как сумму простых гармоник: синусов и косинусов.

Тригонометрический ряд Фурье

Функция представляется в виде:

f(t) = a0/2 + sum [ a_k*cos(k*w*t) + b_k*sin(k*w*t) ]

где:
w - основная угловая частота;
a_k и b_k - коэффициенты Фурье.

Смысл коэффициентов

Коэффициенты показывают, насколько сильно в сигнале присутствует гармоника с номером k.

Амплитудный спектр

Амплитудный спектр показывает силу каждой частоты.

Фазовый спектр

Фазовый спектр показывает сдвиг фазы каждой гармоники.

Почему это важно

Фурье-анализ позволяет:
- находить скрытые периодичности;
- анализировать сигналы;
- фильтровать шум;
- понимать частотный состав.

===============================================================================
25. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ
===============================================================================

ДПФ

Дискретное преобразование Фурье переводит дискретный сигнал из временной области в частотную.

Пусть есть N отсчетов сигнала:

x[0], x[1], ..., x[N-1]

ДПФ:

X[k] = sum x[n] * exp(-2*pi*i*k*n/N), n=0..N-1

Обратное ДПФ:

x[n] = 1/N * sum X[k] * exp(2*pi*i*k*n/N), k=0..N-1

Смысл

X[k] показывает вклад частоты k в сигнал.

abs(X[k]) - амплитуда.
arg(X[k]) - фаза.

Свойства ДПФ

1. ДПФ переводит сигнал в спектр.
2. Большие пики амплитудного спектра соответствуют главным частотам.
3. Обратное ДПФ восстанавливает сигнал по спектру.
4. Шум обычно распределяется по многим частотам.

Сложность

Прямое ДПФ требует O(N^2) операций.

БПФ

Быстрое преобразование Фурье снижает сложность до O(N log N).

Идея: сигнал делится на четные и нечетные отсчеты, потом результаты объединяются.

Частота дискретизации

Частота дискретизации fs - это число отсчетов в секунду.

Частотное разрешение

df = fs / N

Чем больше N, тем меньше df и тем лучше различаются близкие частоты.

Частота Найквиста

Максимальная частота, которую можно различить:

f_max = fs/2

Алиасинг

Если в сигнале есть частоты выше fs/2, они могут исказиться и выглядеть как ложные низкие частоты.

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

Фильтрация сигнала

Процедура:
1. Посчитать ДПФ.
2. Найти спектр.
3. Удалить или ослабить ненужные частоты.
4. Сделать обратное ДПФ.

Смысл: большинство фильтров работают не с самим сигналом, а со спектром.

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

===============================================================================
26. КОРОТКИЕ ШАБЛОНЫ ОТВЕТОВ НА ЭКЗАМЕНЕ
===============================================================================

Если спрашивают "что такое численный метод"

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

Если спрашивают "откуда берется погрешность"

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

Если спрашивают "почему бисекция сходится"

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

Если спрашивают "почему Ньютон быстрый"

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

Если спрашивают "чем секущие отличаются от Ньютона"

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

Если спрашивают "что такое Якобиан"

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

Если спрашивают "что такое интерполяция"

Интерполяция - это построение функции, проходящей через заданные узлы, для оценки значений внутри диапазона этих узлов.

Если спрашивают "почему сплайн лучше большого полинома"

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

Если спрашивают "что такое собственное значение"

Собственное значение lambda матрицы A - это число, при котором существует ненулевой вектор x такой, что A*x=lambda*x. Такой вектор при умножении на A не меняет направление.

Если спрашивают "что делает степенной метод"

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

Если спрашивают "что такое QR-алгоритм"

QR-алгоритм многократно раскладывает матрицу A_k на Q_k*R_k и строит A_{k+1}=R_k*Q_k. Собственные значения сохраняются, а матрица постепенно приходит к виду, где они читаются с диагонали.

Если спрашивают "что такое численное дифференцирование"

Численное дифференцирование заменяет производную разностным отношением. Оно основано на разложении Тейлора. Центральная разность обычно точнее прямой и обратной.

Если спрашивают "что такое метод Эйлера"

Метод Эйлера решает задачу Коши пошагово. На каждом шаге он использует производную в текущей точке и идет по касательной:

y_next = y + h*f(x,y)

Если спрашивают "почему RK4 точнее Эйлера"

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

Если спрашивают "что такое ДПФ"

ДПФ переводит дискретный сигнал из временной области в частотную. Оно показывает, какие частоты присутствуют в сигнале и с какими амплитудами.

Если спрашивают "что такое фильтрация через Фурье"

Сначала сигнал переводят в спектр через ДПФ, затем ослабляют или удаляют ненужные частоты, после чего выполняют обратное преобразование. Так можно подавлять шум.

===============================================================================
27. КАРТА ТЕМ ДЛЯ БЫСТРОГО ПОИСКА
===============================================================================

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

Компьютерная арифметика:
плавающая точка, мантисса, порядок, overflow, underflow, потеря значимости, Кэхэн.

Интегрирование:
прямоугольники, трапеции, Симпсон, площадь под графиком, шаг h.

Нелинейные уравнения:
отделение корней, бисекция, половинное деление, простая итерация, хорд, секущих, Ньютон, модифицированный Ньютон.

Системы:
нелинейная система, Якобиан, Ньютон для системы, простые итерации, Гаусс-Зейдель.

Интерполяция:
интерполяция, экстраполяция, аппроксимация, ступенчатая, линейная, квадратичная, Лагранж, сплайн, билинейная.

Матрицы:
собственное значение, собственный вектор, спектр, спектральный радиус, степенной метод, обратный степенной метод, Гершгорин, QR, Шур, SVD, PCA, Штрассен, Хаусхолдер, гессенбергова форма.

Дифференцирование:
прямая разность, обратная разность, центральная разность, вторая производная, ошибка усечения, ошибка округления.

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

Фурье:
ряд Фурье, гармоники, амплитуда, фаза, ДПФ, БПФ, спектр, фильтрация, частота дискретизации, Найквист, алиасинг.