---

ЧИСЛЕННЫЕ МЕТОДЫ - РАСШИРЕННАЯ ТЕОРИЯ V8

Как пользоваться:
1. Сначала найди тему по названию метода.
2. Для короткого ответа бери: определение, идею, формулу, условия, плюс и минус.
3. Для длинного ответа добавь сравнение с соседним методом и устойчивость/погрешность.
4. В конце можно написать: результат приближенный, точность проверяется по ошибке или невязке.

Карта теории к нашим блокам:

1.1 Кэхэн - смотри IEEE 754, потеря значимости, накопление ошибок округления.
2.1 Бисекция - теорема о промежуточном значении, смена знака, линейная сходимость.
2.2 Ньютон - касательная, производная, квадратичная сходимость, зависимость от x0.
2.3 Модифицированный Ньютон - фиксированная производная, дешевле шаг, медленнее сходимость.
2.4 Секущие - замена производной разностным отношением, быстрее бисекции, менее надежно.
2.5 Простые итерации - неподвижная точка, сжимающее отображение, константа Липшица.
2.6 Дихотомия - одномерная минимизация, сужение отрезка, сравнение двух точек.
3.1 Ньютон для системы - вектор F, Якобиан, линейная система для поправки.
3.2 Итерации для системы - x=g(x), сжатие в многомерном случае, невязка.
4.1 Линейная интерполяция - локальная интерполяция прямой между узлами.
4.2 Лагранж - базисные полиномы, точное прохождение через узлы, феномен Рунге.
4.3 Сплайн - кусочные кубические полиномы, гладкая сшивка, натуральные условия.
5.1 Степенной метод - собственные значения, спектральный радиус, спектральный зазор.
5.2 Сдвиг - обратный степенной метод, sigma, отношение Релея, решение систем.
5.3 QR - ортогональность Q, верхнетреугольная R, Грамм-Шмидт.
5.4 QR-алгоритм - последовательные QR-шаги, спектр, сходимость к форме Шура.
5.5 Шур - A=U*T*U^T, верхнетреугольная форма, связь с собственными значениями.
5.6 Гершгорин - круги, центры, радиусы, локализация собственных значений.
5.7 Штрассен - O(n^3), O(n^2.807), память, кэш, 7 умножений вместо 8.
6.1 Дифференцирование - прямая, обратная, центральная разность, ошибка усечения и округления.
6.2 Эйлер - задача Коши, первый порядок, локальная и глобальная ошибка.
6.3 Предиктор-корректор - прогноз и исправление, метод Хойна, порядок 2.
6.4 метод Рунге-Кутты 4 порядка - четыре наклона, порядок 4, сравнение с Эйлером.
6.5 Система ОДУ - векторная форма, фазовый портрет, осциллятор/маятник.
6.6 Сравнение Эйлера и метод Рунге-Кутты 4 порядка - точность, стоимость шага, устойчивость.
6.7 Адамс - многошаговые методы, предиктор Башфорта, корректор Мултона.
7.1 ДПФ - временная и частотная области, амплитудный спектр, шум.
7.2 БПФ - разбиение на четные и нечетные отсчеты, O(N log N).

Нестандартные темы, которые добавлены запасом:
- численное интегрирование: прямоугольники, трапеции, Симпсон
- Гаусс-Зейдель
- метод вращений Якоби
- вторая производная
- адаптивный шаг
- фильтрация ДПФ
- Найквист и алиасинг
- аппроксимация МНК
- PageRank
- Хаусхолдер и гессенбергова форма
- SVD, PCA, разреженные матрицы, жесткие ОДУ


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

Как отвечать на теорию

Пиши по одной схеме:
1. Метод нужен для такой-то задачи.
2. Идея метода такая-то.
3. Основная формула такая-то.
4. Для метода нужны такие данные.
5. Остановка идет по ошибке, невязке или числу итераций.
6. Плюс метода.
7. Минус метода.
8. Итог является приближенным.

Общая теория

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

Причины погрешности:
1. Неточные исходные данные.
2. Неточная математическая модель.
3. Приближенный метод.
4. Округление чисел в компьютере.
5. Накопление ошибки при большом числе операций.

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

Абсолютная погрешность:
abs_error = abs(exact - approx)

Относительная погрешность:
rel_error = abs_error / abs(exact)

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

Невязка показывает, насколько хорошо найденный ответ удовлетворяет исходной задаче.
Для f(x)=0 невязка равна abs(f(x)).
Для A*x=b невязка равна norm(A*x-b).
Для собственного значения невязка равна norm(A*x-lambda*x).

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


1.1. АЛГОРИТМ КЭХЭНА ДЛЯ СУММИРОВАНИЯ
=====================================

Метод Кэхэна нужен для более точного суммирования чисел.

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

Формулы:
y = x_i - c
t = sum + y
c = (t - sum) - y
sum = t

Данные: список чисел.
Остановка: метод просто проходит по списку один раз.
Плюс: уменьшает накопление ошибки.
Минус: не убирает ошибку полностью.

Короткий ответ: алгоритм Кэхэна уменьшает ошибку округления при суммировании за счет хранения поправки.


2.1. МЕТОД БИСЕКЦИИ
===================

Метод бисекции решает уравнение f(x)=0 на отрезке [a,b].

Главное условие: f(a)*f(b) < 0. Тогда на отрезке есть смена знака.
Идея: делить отрезок пополам и оставлять половину, где есть смена знака.

Формула:
c = (a + b) / 2

Данные: f(x), a, b, eps.
Остановка: abs(f(c)) < eps или abs(b-a) < eps.
Плюс: надежный метод, не нужна производная.
Минус: сходится медленно.

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


2.2. МЕТОД НЬЮТОНА ДЛЯ ОДНОГО УРАВНЕНИЯ
=======================================

Метод Ньютона решает уравнение f(x)=0.

Идея: в текущей точке строится касательная, а ее пересечение с осью Ox дает новое приближение.

Формула:
x_next = x - f(x) / f_prime(x)

Данные: f(x), f_prime(x), x0, eps.
Остановка: abs(x_next-x) < eps или abs(f(x_next)) < eps.
Плюс: часто сходится очень быстро.
Минус: нужна производная, метод зависит от x0, нельзя делить на почти нулевую производную.

Короткий ответ: метод Ньютона заменяет функцию касательной и уточняет корень по формуле x_next.


2.3. МОДИФИЦИРОВАННЫЙ МЕТОД НЬЮТОНА
===================================

Модифицированный метод Ньютона похож на обычный Ньютон.

Отличие: производная считается один раз в начальной точке x0.

Формула:
x_next = x - f(x) / f_prime(x0)

Данные: f(x), f_prime(x), x0, eps.
Остановка: abs(x_next-x) < eps или abs(f(x_next)) < eps.
Плюс: меньше вычислений производной.
Минус: обычно медленнее обычного Ньютона.

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


2.4. МЕТОД СЕКУЩИХ
==================

Метод секущих решает уравнение f(x)=0 без явной производной.

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

Формула:
x_next = x_curr - f(x_curr)*(x_curr-x_prev)/(f(x_curr)-f(x_prev))

Данные: f(x), x0, x1, eps.
Остановка: abs(x_next-x_curr) < eps или abs(f(x_next)) < eps.
Плюс: не нужна производная.
Минус: нужны две стартовые точки, метод может не сойтись.

Короткий ответ: метод секущих использует две последние точки, чтобы приблизить производную.


2.5. МЕТОД ПРОСТЫХ ИТЕРАЦИЙ x = phi(x)
======================================

Метод простых итераций решает уравнение, записанное как x = phi(x).

Идея: много раз считать x_next = phi(x), пока значения не перестанут сильно меняться.

Формула:
x_next = phi(x)

Данные: phi(x), x0, eps.
Остановка: abs(x_next-x) < eps.
Условие хорошей сходимости: abs(phi_prime(x)) < 1 около решения.
Плюс: простая схема.
Минус: нужно правильно выбрать phi, иначе метод не сойдется.

Короткий ответ: метод ищет неподвижную точку функции phi.


2.6. МИНИМИЗАЦИЯ МЕТОДОМ ДИХОТОМИИ
==================================

Метод дихотомии ищет минимум функции на отрезке.

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

Данные: f(x), a, b, eps, delta.
Остановка: abs(b-a) < eps.
Плюс: не нужна производная.
Минус: нужен отрезок и метод может быть медленным.

Короткий ответ: метод постепенно сужает отрезок, в котором находится точка минимума.


3.1. МЕТОД НЬЮТОНА ДЛЯ СИСТЕМЫ
==============================

Метод Ньютона для системы решает F(x)=0, где x - вектор.

Идея: нелинейная система заменяется линейной системой с матрицей Якоби.

Формулы:
J(x_k)*delta = -F(x_k)
x_next = x_k + delta

Данные: F(x), J(x), x0, eps.
J(x) - матрица частных производных.
Остановка: norm(delta) < eps или norm(F(x_next)) < eps.
Плюс: быстро сходится около решения.
Минус: нужен Якобиан и решение линейной системы.

Короткий ответ: метод на каждом шаге решает линейную систему с матрицей Якоби.


3.2. ПРОСТЫЕ ИТЕРАЦИИ ДЛЯ СИСТЕМЫ x = g(x)
==========================================

Метод простых итераций для системы решает систему вида x = g(x).

Идея: строится последовательность векторов x_next = g(x).

Формула:
x_next = g(x)

Данные: g(x), x0, eps, исходная F(x) для проверки.
Остановка: norm(x_next-x) < eps.
Плюс: не нужен Якобиан.
Минус: метод может не сойтись, если g выбрана плохо.

Короткий ответ: метод повторяет векторную формулу g до стабилизации решения.


4.1. ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ
==========================

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

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

Формула:
y = y0 + (y1-y0)*(x-x0)/(x1-x0)

Данные: x_points, y_points, x_star.
Плюс: простой метод.
Минус: низкая точность на сильно изогнутых функциях.

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


4.2. ИНТЕРПОЛЯЦИЯ ЛАГРАНЖА
==========================

Полином Лагранжа проходит через все заданные точки.

Идея: полином строится как сумма y_i*L_i(x), где L_i - базисные полиномы.

Формула в словах:
P(x) = сумма y_i * L_i(x)

Данные: x_points, y_points, x_star.
Плюс: не нужно решать систему для коэффициентов.
Минус: при большом числе точек полином может сильно колебаться.

Короткий ответ: метод строит интерполяционный полином, который проходит через все узлы.


4.3. НАТУРАЛЬНЫЙ КУБИЧЕСКИЙ СПЛАЙН
==================================

Кубический сплайн строит гладкую кусочную интерполяцию.

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

Форма:
S_i(x) = a + b*(x-x_i) + c*(x-x_i)^2 + d*(x-x_i)^3

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

Короткий ответ: сплайн - это набор кубических полиномов на отдельных интервалах.


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

Степенной метод ищет доминирующее собственное значение матрицы.

Доминирующее значение - самое большое по модулю.
Идея: многократно умножать вектор на A и нормировать его.

Формулы:
y = A*x
x_next = y / norm(y)
lambda = (A*x_next, x_next) / (x_next, x_next)

Данные: A, x0, eps.
Остановка: изменение lambda меньше eps или малая невязка.
Плюс: простой метод.
Минус: находит только доминирующее значение и может сходиться медленно.

Короткий ответ: метод выделяет направление доминирующего собственного вектора.


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

Обратный степенной метод со сдвигом ищет собственное значение около sigma.

Идея: вместо умножения на A решается система с A - sigma*I.

Формула:
(A - sigma*I)*y = x

Данные: A, sigma, x0, eps.
Остановка: изменение lambda меньше eps или малая невязка.
Плюс: можно искать значение около заданного sigma.
Минус: на каждом шаге нужно решать систему.

Короткий ответ: сдвиг sigma направляет метод к ближайшему собственному значению.


5.3. QR-РАЗЛОЖЕНИЕ ЧЕРЕЗ ГРАММА-ШМИДТА
======================================

QR-разложение представляет матрицу как A = Q*R.

Q - матрица с ортонормированными столбцами.
R - верхнетреугольная матрица.

Идея Грамма-Шмидта: из каждого столбца убираются проекции на уже построенные ортонормированные столбцы, потом он нормируется.

Данные: A.
Проверка: A примерно равно Q*R, а Q^T*Q примерно равно I.
Плюс: используется в QR-алгоритме.
Минус: классический вариант может быть неустойчив для почти зависимых столбцов.

Короткий ответ: QR-разложение делит матрицу на ортогональную и верхнетреугольную части.


5.4. QR-АЛГОРИТМ ДЛЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ
=========================================

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

Идея: много раз выполнять QR-разложение и менять порядок множителей.

Формулы:
A_k = Q_k*R_k
A_next = R_k*Q_k

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

Короткий ответ: QR-алгоритм постепенно приводит матрицу к почти треугольной форме.


5.5. ПРИБЛИЖЕННОЕ РАЗЛОЖЕНИЕ ШУРА ЧЕРЕЗ QR-ИТЕРАЦИИ
===================================================

Разложение Шура записывает матрицу как A = U*T*U^T.

U - ортогональная матрица.
T - верхнетреугольная или почти верхнетреугольная матрица.
Диагональ T связана с собственными значениями.

Идея: QR-итерации накапливают ортогональные преобразования и приводят A к T.

Данные: A, число итераций.
Плюс: удобно для анализа собственных значений.
Минус: простая учебная реализация дает приближение.

Короткий ответ: разложение Шура приводит матрицу к верхнетреугольному виду ортогональным преобразованием.


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

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

Для каждой строки строится круг:
center = a_ii
radius = сумма abs(a_ij), где j != i

Главное утверждение: все собственные значения лежат в объединении этих кругов.

Данные: A.
Плюс: быстро дает оценку спектра.
Минус: оценка может быть грубой.

Короткий ответ: круги Гершгорина локализуют собственные значения по элементам матрицы.


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

Наивное умножение матриц считает каждый элемент как строка на столбец.

Формула:
C[i,j] = сумма A[i,k]*B[k,j]

Сложность наивного метода: O(n^3).

Метод Штрассена делит матрицы на блоки и уменьшает число умножений блоков с 8 до 7.

Данные: A, B.
Плюс Штрассена: лучше асимптотическая сложность для больших матриц.
Минус: сложнее и может быть невыгоден для маленьких матриц.

Короткий ответ: Штрассен ускоряет матричное умножение за счет уменьшения числа блочных умножений.


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

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

Формулы:
forward = (f(x+h)-f(x))/h
backward = (f(x)-f(x-h))/h
central = (f(x+h)-f(x-h))/(2*h)

Данные: f(x), x0, h.
Плюс: не нужна аналитическая производная.
Минус: точность зависит от h, есть ошибка округления.

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


6.2. МЕТОД ЭЙЛЕРА ДЛЯ ОДУ y' = f(t,y)
=====================================

Метод Эйлера решает задачу Коши y'=f(t,y), y(t0)=y0.

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

Формулы:
y_next = y + h*f(t,y)
t_next = t + h

Данные: f(t,y), t0, y0, t_end, h.
Порядок точности: первый.
Плюс: самый простой метод.
Минус: низкая точность и возможная неустойчивость при большом h.

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


6.3. ПРЕДИКТОР-КОРРЕКТОР ЭЙЛЕРА
===============================

Предиктор-корректор Эйлера улучшает метод Эйлера.

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

Формулы:
y_pred = y + h*f(t,y)
y_corr = y + h/2*(f(t,y) + f(t+h,y_pred))

Данные: f(t,y), t0, y0, t_end, h.
Плюс: точнее простого Эйлера.
Минус: нужно больше вычислений функции.

Короткий ответ: метод сначала прогнозирует значение, затем корректирует его.


6.4. МЕТОД РУНГЕ-КУТТЫ 4-ГО ПОРЯДКА
===================================

Метод Рунге-Кутты 4 порядка решает задачу Коши для ОДУ.

Идея: на каждом шаге считается четыре наклона, потом они усредняются.

Формулы:
k1 = h*f(t,y)
k2 = h*f(t+h/2, y+k1/2)
k3 = h*f(t+h/2, y+k2/2)
k4 = h*f(t+h, y+k3)
y_next = y + (k1+2*k2+2*k3+k4)/6

Данные: f(t,y), t0, y0, t_end, h.
Порядок точности: четвертый.
Плюс: высокая точность.
Минус: 4 вычисления функции на шаг.

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


6.5. СИСТЕМА ОДУ: ЭЙЛЕР ИЛИ метод Рунге-Кутты 4 порядка
===============================

Система ОДУ содержит несколько неизвестных функций.

Идея: все неизвестные собираются в вектор u, а правая часть записывается как F(t,u).

Для Эйлера:
u_next = u + h*F(t,u)

Для метод Рунге-Кутты 4 порядка формулы такие же, но k1, k2, k3, k4 являются векторами.

Данные: F(t,u), u0, t0, t_end, h, method.
Плюс: можно решать уравнения высокого порядка через систему первого порядка.
Минус: нужно правильно переписать систему.

Короткий ответ: систему ОДУ решают так же, как одно уравнение, но вместо числа используется вектор.


6.6. СРАВНЕНИЕ ЭЙЛЕРА И метод Рунге-Кутты 4 порядка
===========================

Сравнение Эйлера и метод Рунге-Кутты 4 порядка показывает влияние метода на точность.

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

Что сравнивают:
- конечное значение y
- графики
- разницу между ответами

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

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


6.7. АДАМС-БАШФОРТ 2 + АДАМС-МУЛТОН 2
=====================================

Методы Адамса являются многошаговыми методами.

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

Адамс-Башфорт - явный метод, часто предиктор.
Адамс-Мултон - корректор.

Формулы:
y_pred = y_n + h/2*(3*f_n - f_prev)
y_corr = y_n + h/2*(f(t_next,y_pred) + f_n)

Данные: f(t,y), t0, y0, t_end, h.
Плюс: использует информацию с прошлых шагов.
Минус: нужны стартовые значения.

Короткий ответ: Башфорт дает прогноз, Мултон исправляет прогноз.


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

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

Идея: сигнал раскладывается на гармоники.
Коэффициент X[k] показывает вклад частоты k.

Формула:
X[k] = сумма x[n]*exp(-j*2*pi*k*n/N)

Обратное ДПФ:
x[n] = 1/N * сумма X[k]*exp(j*2*pi*k*n/N)

Данные: signal, N.
Что смотреть: abs(X[k]) - амплитуда частоты k.
Плюс: показывает спектр.
Минус: прямое ДПФ требует много операций.

Короткий ответ: ДПФ показывает частотный состав дискретного сигнала.


7.2. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ - БПФ / FFT
=============================================

БПФ - быстрый алгоритм вычисления ДПФ.

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

Данные: signal, N. В простом варианте N должно быть степенью двойки.
Плюс: быстрее прямого ДПФ.
Минус: сложнее и требует подходящей длины сигнала.

Короткий ответ: БПФ дает тот же спектральный смысл, что и ДПФ, но считает быстрее.


8.1. ЗАГОТОВКА ТЕКСТА ДЛЯ ОТВЕТА
================================

Это не метод, а шаблон оформления ответа.

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

Короткий ответ: теория должна быть короткой, но обязательно с формулой и смыслом метода.
ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ

Численное интегрирование нужно, чтобы приближенно найти определенный интеграл.
Геометрическая идея: интеграл - это площадь под графиком на отрезке [a,b].

Шаг:
h = (b-a)/N

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

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

АНАЛИТИЧЕСКИЕ, ГРАФИЧЕСКИЕ И ЧИСЛЕННЫЕ МЕТОДЫ

Аналитический метод дает формулу или точное решение.
Плюс: точность и теоретический анализ.
Минус: не всегда возможно.

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

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


ДОПОЛНИТЕЛЬНЫЕ РАЗВЕРНУТЫЕ ОПРЕДЕЛЕНИЯ

IEEE 754 и машинная точность

Число с плавающей точкой хранится как знак, мантисса и порядок. В double используется 64 бита: 1 бит знака, 11 бит порядка и 52 бита мантиссы. Из-за конечной мантиссы большинство вещественных чисел хранится приближенно. Машинный eps показывает уровень относительной ошибки округления. Для double он примерно равен 2.22e-16.

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

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

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

Сжимающее отображение

Отображение g называется сжимающим, если существует число L<1, такое что abs(g(x)-g(y)) <= L*abs(x-y). В методе простых итераций это означает, что точки сближаются. Если g сжимающее, то существует единственная неподвижная точка, и итерации x_next=g(x) сходятся к ней. Для гладкой функции часто проверяют max abs(g_prime(x)) < 1.

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

Локальная ошибка - ошибка одного шага, если предыдущее значение было точным. Глобальная ошибка - ошибка, накопленная к концу всего интервала. У метод Рунге-Кутты 4 порядка локальная ошибка порядка h^5, а глобальная порядка h^4. У Эйлера глобальная ошибка порядка h.

Явные и неявные методы

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

Жесткие системы ОДУ

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

Интерполяция, экстраполяция, аппроксимация

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

SVD и PCA

SVD представляет матрицу как A=U*S*V^T. Сингулярные числа показывают важность компонент. В изображениях первые сингулярные компоненты сохраняют главные детали, а малые компоненты часто отвечают за шум. PCA ищет направления максимальной дисперсии данных и связан с собственными значениями ковариационной матрицы. На практике PCA часто считают через SVD.

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

Разреженная матрица содержит много нулей. Вместо хранения всех элементов хранят только ненулевые элементы и их позиции. Форматы: COO, CSR, CSC. Это экономит память и ускоряет умножение матрицы на вектор, если ненулевых элементов мало.

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

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

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

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

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

Частота дискретизации fs - это число отсчетов в секунду. Максимальная частота, которую можно различить без искажения, равна fs/2. Это частота Найквиста. Если в сигнале есть частоты выше fs/2, возникает алиасинг: высокие частоты выглядят как ложные низкие.


БАНК ВОПРОСОВ ИЗ ЗАГРУЖЕННОГО ФАЙЛА

# 1. Решение нелинейных уравнений

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


Метод бисекции работает с отрезком [a, b], на концах которого функция имеет разные знаки (f(a) * f(b) < 0). По теореме о промежуточном значении (теорема Больцано-Коши): если f непрерывна на [a, b] и принимает на концах значения разных знаков, то на отрезке гарантированно есть точка, где f = 0. Метод делит отрезок пополам, оставляя ту половину, где сохраняется смена знака, поэтому корень всегда остается внутри и сходимость гарантирована.

Сравнение с методом секущих: бисекция сходится линейно (длина отрезка сокращается вдвое за итерацию, q = 0.5), но абсолютно надежна. Метод секущих сходится быстрее (сверхлинейно, порядок около 1.618), но не гарантирует сходимость и может расходиться при неудачных начальных точках.

Устойчивость к ошибкам округления: бисекция очень устойчива - она лишь сравнивает знаки и не усиливает погрешности; ошибка вычисления f(m) порядка eps_machine * |f(m)| пренебрежимо мала по сравнению с tol. Метод секущих вычисляет разности близких значений функции, что при сходимости приводит к потере значимости и большей чувствительности к округлению.

---

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


Минимизация числа итераций: число шагов оценивается как n >= log2((b-a)/eps),
то есть зависит только от длины начального отрезка. Поэтому стратегия -
максимально сузить начальный отрезок, используя информацию о функции
(анализ производной, монотонность, график), прежде чем запускать
бисекцию.

Верные цифры: в строгом (узком) смысле верными считаются разряды, в
которых погрешность не превышает 0.5 единицы последнего разряда; в
широком смысле - разряды, где погрешность не превышает единицу
последнего разряда. Это напрямую связано с правилами округления:
корректно округленное число имеет все цифры верными в строгом смысле.
При tol = 10^(-5) гарантировано примерно 5 верных значащих цифр.

---

### В: Когда модифицированный метод Ньютона предпочтителен по сравнению с обычным методом Ньютона? Как ошибки в вычислении производной влияют на сходимость?


Модифицированный метод Ньютона фиксирует производную (или якобиан) один раз в начальной точке x0 и переиспользует ее на всех итерациях:
x_{n+1} = x_n - f(x_n)/f'(x_n).
Он предпочтителен, когда вычисление производной дорого (например, большой якобиан для системы), когда производную трудно получить аналитически или когда решается много похожих задач.

Цена - скорость: обычный метод Ньютона сходится квадратично, а модифицированный лишь линейно (множитель q = |1 - f'(x0)/f'(x*)|). Ошибки в вычислении производной не разрушают сходимость, пока приближение f'(x0) сохраняет правильный знак и разумную величину: они лишь замедляют ее (увеличивают q). Однако грубо неверная производная (особенно с неправильным знаком) может привести к расходимости.

---

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


Метод Ньютона сходится только локально: при хорошем начальном приближении вблизи корня - квадратично, но при плохом старте может расходиться или уходить к другому корню. В задаче Ван-дер-Ваальса удачный старт - объем идеального газа V0 = RT/P.

Сравнение с бисекцией. Скорость: Ньютон квадратичен, бисекция линейна (q = 0.5). Требования к функции: бисекции достаточно непрерывности и смены знака на концах; Ньютону нужна дифференцируемость и вычислимая производная f', а также невырожденность f'(x*) != 0. Надежность: бисекция сходится всегда, Ньютон - нет.

Пример несходимости: для f(x) = x^(1/3) производная в корне бесконечна, и итерации Ньютона расходятся (удаляются от 0). Также метод зацикливается или уходит в бесконечность, если f'(x) ~ 0 рядом со стартовой точкой (горизонтальная касательная).

---

## 2. Системы нелинейных уравнений

В: Каковы условия сходимости метода Ньютона для систем нелинейных уравнений? Сравните метод Ньютона для систем с методом Гаусса-Зейделя по вычислительной сложности и устойчивости к ошибкам округления.


Условия сходимости метода Ньютона для систем: якобиан J(x*) в корне невырожден (det J != 0), функции достаточно гладкие, а начальное приближение лежит в окрестности корня. При этих условиях сходимость квадратичная.

Вычислительная сложность: на каждой итерации Ньютон требует вычисления якобиана и решения линейной системы - O(n^3). Метод Гаусса-Зейделя (итерации вида x_{n+1} = g(x_n)) стоит O(n^2) на итерацию и не требует якобиана, но сходится лишь линейно и нуждается в диагональном преобладании или малой константе Липшица.

Устойчивость к ошибкам округления: когда |det J| -> 0 (якобиан плохо обусловлен), решение приращения dx становится неточным и сходимость Ньютона ухудшается. Гаусс-Зейдель в этом смысле мягче, но компенсирует это медленной сходимостью.

---

В: Сравните метод Гаусса-Зейделя с методом Ньютона по скорости сходимости и устойчивости к ошибкам округления. Как эти понятия связаны с ошибками вычислений с плавающей точкой?


Скорость: метод Ньютона - квадратичная сходимость (число верных знаков примерно удваивается за итерацию); Гаусс-Зейдель - линейная сходимость (ошибка убывает в постоянное число раз). Ньютон делает меньше итераций, но каждая дороже.

Устойчивость: устойчивость обоих методов падает, когда задача плохо обусловлена. Для Ньютона критичен плохо обусловленный якобиан. В арифметике с плавающей точкой (IEEE 754) это проявляется так: вычитание близких чисел при формировании невязки F(x) и решении системы вызывает потерю значимости, а накопление ошибок округления за итерации ограничивает достижимую точность - нет смысла задавать tol меньше уровня машинной погрешности.

---

# 3. Собственные значения и степенной метод

**В: Что такое спектральный радиус матрицы и как он связан с собственными значениями? Как зазор между собственными значениями влияет на сходимость? Как круги Гершгорина помогают оценить собственные значения?**


Спектральный радиус rho(A) = max |lambda_i| - наибольший модуль среди всех собственных значений матрицы. Именно его находит степенной метод.

Зазор и сходимость: степенной метод сходится со скоростью, пропорциональной |lambda_2/lambda_1|^k. Чем больше зазор между наибольшим и вторым по модулю собственными значениями, тем быстрее сходимость; при малом зазоре она очень медленная.

Круги Гершгорина: каждое собственное значение лежит хотя бы в одном круге D_i = { z : |z - a_ii| <= R_i }, где R_i - сумма модулей внедиагональных элементов i-й строки. Круги дают быструю локализацию спектра без точного вычисления собственных значений и помогают оценить, например, диапазон rho(A).

---

В: Как зазор между собственными значениями влияет на скорость сходимости? Как ошибки округления в арифметике с плавающей точкой (стандарт IEEE754) могут повлиять на точность вычислений? Как можно было бы минимизировать их влияние?


Зазор и сходимость: скорость степенного метода (и QR со сдвигами) определяется отношением соседних собственных значений. Малый зазор -> медленная сходимость. Степенной метод со сдвигом заменяет A на (A - muI): подбор mu увеличивает относительный зазор у нужного собственного значения и ускоряет сходимость к нему.

Ошибки округления (IEEE 754): число double занимает 64 бита (1 знак, 11 порядок, 52 мантисса), машинный эпсилон eps_machine ~ 2.22 * 10^(-16). При малом зазоре ошибки округления могут имитировать ложную сходимость или мешать различить близкие собственные значения.

Минимизация влияния: нормировать вектор на каждой итерации (предотвращает переполнение/исчезновение порядка), использовать отношение Релея для оценки lambda, применять сдвиги и не задавать допуск ниже уровня машинной точности.

---

В: Напишите функцию, которая находит собственные векторы методом вращений. Проверьте сходимость результата с точностью xi = 0.001. (теоретический аспект: применимость метода)


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

Если матрица несимметрична, классический метод Якоби неприменим. В этом случае собственные значения находят через характеристический многочлен (для малых матриц) либо степенным методом с дефляцией: находят наибольшее собственное значение и вектор, затем "вычитают" найденную компоненту A - lambda * v * v^T и повторяют. Контроль сходимости - по малости изменения вектора/значения между итерациями (< xi).

---

# 4. SVD и анализ данных

**В: Как вычисление SVD используется для анализа изображений? Как это связано с собственными значениями? Объясните связь с вычислением собственных значений матрицы ковариации.**


Сингулярное разложение представляет матрицу как A = U * Sigma * V^T, где U и V ортогональны, а Sigma - диагональ неотрицательных сингулярных чисел sigma_1 >= sigma_2 >= ... . При анализе изображений матрицу пикселей приближают суммой нескольких первых сингулярных компонент (низкоранговое приближение): это сжимает изображение, сохраняя главные детали и отбрасывая мелкие, отвечающие малым sigma.

Связь с собственными значениями: сингулярные числа A - это корни из собственных значений матрицы A^T A (или A A^T), а правые/левые сингулярные векторы - собственные векторы этих матриц.

Связь с ковариацией (PCA): если данные центрированы, матрица ковариации пропорциональна A^T A. Ее собственные векторы - главные компоненты (направления максимальной дисперсии), а собственные значения - величины дисперсии вдоль них. Поэтому SVD матрицы данных напрямую дает результат метода главных компонент.

---

# 5. Умножение матриц: алгоритм Штрассена

**В:** Как алгоритм Штрассена оптимизирует умножение матриц? Как это влияет на асимптотическую сложность в нотации big-O? Объясните, как архитектура памяти влияет на производительность матричных операций.


Наивное умножение матриц n*n требует n3 скалярных умножений - сложность O(n3). Штрассен разбивает каждую матрицу на 4 блока и вычисляет произведение через 7 рекурсивных умножений блоков вместо 8 (ценой большего числа сложений).

Влияние на сложность: рекуррента дает O(n^(log_2 7)) ~ O(n^(2.807)), что
асимптотически лучше O(n^3). Для n = 2^k это 7^k умножений вместо 8^k; экономия
(7/8)^k растет с размером (для n = 16 - около 41 %).

Архитектура памяти: реальная производительность зависит не только от
числа операций. Наивное блочное умножение кэш-дружелюбно
(последовательный доступ к данным). Штрассен создает много временных
матриц (суммы/разности блоков), что увеличивает обращения к памяти и
кэш-промахи. Поэтому на малых матрицах он проигрывает, а выигрыш
проявляется только при больших n (примерно n >= 100).


В: Какова точность центральной разности для аппроксимации второй производной? Как ошибка зависит от шага h? Сравните центральную разность с прямой разностью по точности и вычислительным затратам.


Вторая производная аппроксимируется формулой f''(x) ~ (f(x+h) - 2f(x) + f(x-h))/h^2 с погрешностью O(h^2): уменьшение h в 10 раз снижает ошибку усечения примерно в 100 раз. Прямая (односторонняя) аппроксимация второй производной имеет лишь порядок O(h).

Затраты: центральная формула использует три значения функции (x-h, x, x+h) и симметрична, за счет чего члены нечетного порядка в разложении Тейлора сокращаются - отсюда более высокий порядок точности. При очень малом h (h < sqrteps_machine ~ 10^(-8)) деление на h^2 усиливает ошибку округления; оптимум для второй производной примерно h ~ eps_machine^(1/4) ~ 10^(-4).

---

# 7. Интерполяция

**В: Объясните, как многочлен Лагранжа обеспечивает точное прохождение через заданные точки. Как степень полинома влияет на точность интерполяции для зашумленных данных?**


Полином Лагранжа строится из базисных многочленов L_i(x), каждый из которых равен 1 в своем узле x_i и 0 во всех остальных узлах (свойство L_i(x_j) = delta_ij). Поэтому сумма sum y_i * L_i(x) в каждом узле x_i дает ровно y_i - полином проходит точно через все заданные точки. По n точкам строится единственный полином степени n-1.

Влияние степени на зашумленных данных: высокая степень (много узлов) приводит к феномену Рунге - сильным осцилляциям полинома, особенно у концов отрезка. Если данные содержат шум, интерполяция, проходящая точно через все точки, повторяет и усиливает шум. Для зашумленных данных лучше использовать сглаживающие методы (метод наименьших квадратов) или интерполяцию сплайнами невысокой степени, а не полином высокой степени.

---

# 8. Решение обыкновенных дифференциальных уравнений

**В: Что такое локальная и глобальная ошибки в численных методах для ОДУ? Как порядок точности метода влияет на эти ошибки? Объясните понятие устойчивости численных методов для ОДУ.**


Локальная ошибка (ошибка усечения на шаге) - погрешность за один шаг при условии, что предыдущее значение точное. Глобальная ошибка - накопленная погрешность к концу отрезка интегрирования. Обычно глобальная ошибка на один порядок ниже локальной: у метод Рунге-Кутты 4 порядка локальная O(h^5), глобальная O(h^4).

Порядок точности p означает, что глобальная ошибка ведет себя как O(h^p):
чем выше порядок, тем быстрее падает ошибка при уменьшении шага. Метод
Эйлера имеет порядок 1, Хойн (предиктор-корректор) - 2, метод Рунге-Кутты 4 порядка - 4.
Устойчивость: метод устойчив, если ошибки (округления и начальные
возмущения) не нарастают неограниченно при интегрировании. Для тестового
уравнения y' = lambday у каждого явного метода есть область устойчивости по h:
например, явный Эйлер устойчив при |1 + hlambda| <= 1, метод Рунге-Кутты 4 порядка - при |hlambda| <= 2.785. Для
жестких задач явные методы требуют слишком малого шага, и выгоднее
неявные методы.

---

В: Как геометрическая интерпретация метода Рунге-Кутта 4-го порядка помогает понять его работу? Как локальная ошибка усечения влияет на глобальную ошибку? Сравните метод предиктора-корректора Эйлера с методом Рунге-Кутты по точности и вычислительным затратам.


Геометрическая интерпретация метод Рунге-Кутты 4 порядка: коэффициенты k1...k4 - это наклоны решения в начале шага (k1), дважды в середине (k2, k3) и в конце (k4).
Итоговое приращение - взвешенное среднее этих наклонов с весами (1/6, 2/6, 2/6, 1/6), где средние отдан больший вес. Такое усреднение "угадывает" кривизну решения на шаге и дает высокую точность.

Связь локальной и глобальной ошибок: за один шаг метод Рунге-Кутты 4 порядка вносит локальную ошибку O(h^5); при прохождении около 1/h шагов эти ошибки накапливаются, давая глобальную ошибку O(h^4).

Сравнение: предиктор-корректор Эйлера (Хойн) использует 2 вычисления f на шаг и имеет глобальный порядок O(h^2); метод Рунге-Кутты 4 порядка использует 4 вычисления f на шаг и порядок O(h^4). метод Рунге-Кутты 4 порядка вдвое дороже по числу вызовов f, но при той же точности позволяет брать гораздо больший шаг, поэтому обычно эффективнее для гладких задач.

---

В: Сравните метод Адамса-Мултона с методом Рунге-Кутты 4-го порядка (порядок сходимости, вычислительная сложность на шаг, устойчивость, применимость к жестким системам ОДУ).
Объясните, в каких сценариях метод Адамса-Мултона предпочтительнее, а в каких - метод Рунге-Кутты.

Порядок: оба метода можно сделать 4-го порядка (О(h^4)). Вычислительная сложность: метод Рунге-Кутты 4 порядка требует 4 вычисления правой части f на каждом шаге; многошаговый Адамс-Мултон (в схеме РЕСЕ) - обычно лишь 1-2, переиспользуя значения f с предыдущих шагов, что экономично при дорогой f.
Устойчивость и жесткость: неявный метод Адамса-Мултона имеет лучшие свойства устойчивости и пригоден для жестких систем, тогда как явный метод Рунге-Кутты 4 порядка на жестких задачах требует чрезмерно малого шага.

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

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

---

В: Как фазовые портреты помогают в анализе систем дифференциальных уравнений? Может ли адаптивный шаг улучшить точность решения ОДУ? Как это связано с устойчивостью и ошибками округления?


Фазовые портреты: строятся в координатах фазовых переменных (например, (y, y') или (y_1, y_2)) и показывают траектории системы без явного решения во времени. По ним видно тип особых точек (узел, фокус, седло, центр), устойчивость равновесий, наличие предельных циклов - то есть качественное поведение системы.

Адаптивный шаг: оценивает локальную ошибку и уменьшает h там, где
решение быстро меняется (жесткие участки), и увеличивает там, где оно
гладкое. Это улучшает точность при той же вычислительной стоимости и
помогает удерживаться в области устойчивости метода.

Связь с устойчивостью и округлением: слишком крупный шаг может вывести
метод за границу устойчивости (ошибки нарастают), а слишком мелкий -
увеличить число шагов и накопление ошибок округления. Адаптивный шаг
ищет баланс между ошибкой усечения и ошибкой округления.

---

В: Как ДПФ помогает выделить частотные компоненты сигнала?
Как наличие шума влияет на спектр? Как можно уменьшить влияние шума? Объясните, как быстрое преобразование Фурье (БПФ) уменьшает вычислительную сложность по сравнению с обычным ДПФ. В чем принцип работы БПФ?


Выделение частот: ДПФ переводит сигнал из временной области в частотную по формуле X[k] = sum x[n] * e^(-2pi i kn/N). Каждый коэффициент X[k] показывает вклад гармоники с частотой k; пики амплитудного спектра соответствуют доминирующим частотам сигнала.

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

Уменьшение шума: фильтрация в частотной области - обнуление/ослабление коэффициентов вне интересующих частот (порог по амплитуде, низкочастотный фильтр), затем обратное преобразование. Также помогает усреднение нескольких реализаций и увеличение длины выборки N.

БПФ: прямое ДПФ через матрицу стоит O(N^2). Быстрое преобразование Фурье (алгоритм Кули-Тьюки) рекурсивно разбивает ДПФ длины N на два ДПФ длины N/2 (по четным и нечетным отсчетам) и комбинирует их за O(N), что в сумме дает O(N log N). Принцип - "разделяй и властвуй" с переиспользованием общих множителей-поворотов.

---

В: Как частота дискретизации влияет на разрешение частотного спектра в ДПФ? Как шум может повлиять на точность выделения частот? Объясните, как быстрое преобразование Фурье (БПФ) уменьшает вычислительную сложность по сравнению с ДПФ. Как это связано с разбиением сигнала?


Частота дискретизации и разрешение: число отсчетов N и частота дискретизации определяют частотное разрешение Deltaf = f_s / N (или 1/N в нормированных единицах). Чем больше точек на интервале, тем мельче шаг по частоте и тем лучше разделяются близкие частоты; при малом N соседние компоненты сливаются. Частота дискретизации также ограничивает максимальную различимую частоту (критерий Найквиста).

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

БПФ и разбиение сигнала: прямое ДПФ - O(N^2). БПФ рекурсивно делит сигнал на четные и нечетные отсчеты, вычисляет два ДПФ половинной длины и объединяет их за линейное время. Это "разбиение сигнала" и переиспользование промежуточных результатов снижает сложность до O(N log N).

---

### В: Как ДПФ преобразует сигнал в частотную область? Почему это важно для анализа периодических сигналов?


ДПФ раскладывает дискретный сигнал по базису комплексных экспонент (гармоник) разных частот:
X[k] = Sigma x[n] * e^(-2pi i k n / N)
Коэффициент X[k] - это амплитуда и фаза гармоники с частотой, соответствующей индексу k. Так сигнал, заданный значениями во времени, представляется набором частотных компонент.

Важность для периодических сигналов: периодический сигнал состоит из суммы гармоник, и ДПФ прямо выявляет их - позволяет определить доминирующие частоты, амплитуды и периоды компонент, обнаружить скрытую периодичность (в том числе сезонность во временных рядах) и выполнить фильтрацию шума в частотной области.

---

Сравнение с QR-разложением. Применимость: QR раскладывает матрицу как произведение ортогональной Q и треугольной R и существует для любой матрицы (это разовая факторизация); разложение Шура раскрывает спектр и для общей матрицы получается только итерационно. Сложность: одно QR-разложение стоит O(n^3); разложение Шура вычисляют QR-алгоритмом - итерационным процессом из многих QR-шагов (с предварительным приведением к гессенберговой форме), что в сумме дороже.

Приложения: вычисление собственных значений (QR-алгоритм опирается на форму Шура), решение матричных уравнений (например, уравнения Сильвестра и Ляпунова), вычисление функций от матриц и анализ устойчивости динамических систем.

---

# 1. Числа с плавающей точкой и стандарт IEEE 754

**В: Как устроено представление чисел с плавающей точкой (стандарт IEEE 754) и какие ошибки представления при этом возникают?**

Число с плавающей точкой хранится в виде знака * мантисса * 2^(порядок). По стандарту IEEE 754 одинарная точность (float) занимает 32 бита (1 знак, 8 порядок, 23 мантисса), двойная (double) - 64 бита (1 знак, 11 порядок, 52 мантисса). Мантисса нормализована (старший бит подразумевается единичным).

Ошибки представления: множество представимых чисел конечно и неравномерно (плотность убывает с ростом величины). Большинство вещественных чисел (даже простые десятичные дроби вроде 0.1) не представимы точно и округляются к ближайшему представимому.
Относительная ошибка такого округления ограничена машинным эпсилоном: для double eps_machine ~ 2.22 * 10^(-16). Стандарт также определяет специальные значения: +/-0, +/-infinity и NaN.

---

# B: Что такое переполнение (overflow) и потеря порядка (underflow)?

Overflow (переполнение) возникает, когда результат по модулю превышает максимально представимое число (для double порядка 1.8*1030⁸): результат становится +/-infinity. Underflow (исчезновение порядка) - когда результат по модулю меньше наименьшего нормализованного числа (около 2.2*10⁻30⁸): он представляется денормализованным числом со сниженной точностью или округляется до нуля.

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

---

В: Что такое накопление ошибок округления и потеря значимости?
Как суммирование по Кахану помогает с этим бороться?

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

Потеря значимости (катастрофическое сокращение): при вычитании двух
близких чисел старшие совпадающие разряды сокращаются, и в результате
остаются в основном ошибочные младшие разряды - относительная
погрешность резко возрастает. Поэтому опасны формулы вида f(x+h) - f(x)
при малом h.

Суммирование по Кахану: при последовательном сложении хранится
дополнительная переменная-компенсация с, в которую накапливается
потерянная при округлении часть каждой суммы и которая возвращается на следующем шаге. В результате итоговая ошибка почти не зависит от числа слагаемых (вместо роста ~ O(n) * eps она остается ~ O(1) * eps), что важно при суммировании длинных рядов и скалярных произведений.
# В: Что такое интерполяция сплайнами и метод кубической сплайн-интерполяции?

Сплайн - кусочно-полиномиальная функция: на каждом отрезке между узлами свой полином невысокой степени, а в узлах полиномы "сшиваются" с условиями гладкости. Это сочетает достоинства локальной интерполяции (нет осцилляций Рунге) с гладкостью.

Кубический сплайн: на каждом отрезке полином 3-й степени; в узлах совпадают значения, первые и вторые производные, что дает непрерывную кривизну (гладкую кривую без изломов). Коэффициенты находятся из системы уравнений (обычно трехдиагональной, решаемой за O(n)) с краевыми условиями (например, естественный сплайн: вторые производные на концах равны нулю). Кубические сплайны широко используются для гладкой интерполяции и в компьютерной графике.

---

# 6. Линейная алгебра: операции, QR, Хаусхолдер, гессенберг

**В: Каковы основные операции вычислительной линейной алгебры и их сложность?**

Базовые операции и их типичная сложность для плотных матриц n * n:
скалярное произведение и сложение векторов - O(n); умножение матрицы на вектор - O(n^2); умножение матриц - O(n^3) наивно (или O(n^(2.807)) по Штрассену); решение системы методом Гаусса и LU-разложение - O(n^3);
QR-разложение - O(n^3). На этих операциях строятся методы решения систем, наименьших квадратов и поиска собственных значений.

---

### В: Что такое отражения Хаусхолдера и как они используются?

Отражение Хаусхолдера - ортогональное преобразование H = I - 2 * v * v^T / (v^T v),
которое зеркально отражает векторы относительно гиперплоскости с
нормалью v. Подбором v можно одним отражением обнулить все элементы
вектора ниже выбранного.

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

---

В: Что такое верхне-гессенбергова форма и как к ней приводят матрицу?

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

Зачем: гессенбергова форма - подготовительный шаг QR-алгоритма; на ней каждая итерация QR стоит O(n^2) вместо O(n^3). Для симметричной матрицы гессенбергова форма становится трехдиагональной.

---

### B: Как работает QR-алгоритм, какова его сходимость и сложность?

QR-алгоритм ищет собственные значения: на каждом шаге раскладывается A_k = Q_k * R_k и формирует A_{k+1} = R_k * Q_k (преобразование подобия).
Последовательность сходится к (квази)треугольной форме Шура, на диагонали которой - собственные значения.

Сходимость и сложность: скорость зависит от зазоров между собственными значениями; ее ускоряют сдвигами (QR со сдвигами). С предварительным приведением к гессенберговой форме одна итерация стоит O(n^2), а всего метод обычно дешев на практике. Это стандартный алгоритм вычисления.

---

# 7. SVD, PCA и PageRank

**В: Что такое метод главных компонент (PCA) и как он связан с поиском сингулярных значений?**

PCA ищет ортогональные направления (главные компоненты), вдоль которых дисперсия центрированных данных максимальна. Эти направления - собственные векторы ковариационной матрицы, а величина дисперсии вдоль них - собственные значения.

Связь с SVD: для центрированной матрицы данных X главные компоненты совпадают с правыми сингулярными векторами X, а сингулярные числа задают разброс вдоль них (sigma_1^2 пропорциональны дисперсиям). Поэтому PCA на практике вычисляют через SVD - это устойчившее, чем явно строить ковариацию. Прикладные аспекты: понижение размерности, сжатие, шумоподавление, визуализация многомерных данных.

---

В: В чем состоит задача Google PageRank и как она сводится к собственному вектору?

PageRank оценивает "важность" веб-страниц по структуре ссылок. Модель - случайный серфер, который с некоторой вероятностью переходит по ссылкам, а с малой вероятностью (демпфирование) прыгает на случайную страницу. Это задает стохастическую матрицу переходов.

Ранги страниц - это стационарное распределение цепи Маркова, то есть собственный вектор матрицы переходов, отвечающий наибольшему собственному значению lambda = 1. Его находят степенным методом, который эффективен для огромных разреженных матриц веба (умножение разреженной матрицы на вектор дешево).

---

# 8. Плотные и разреженные матрицы

**В: Чем плотные матрицы отличаются от разреженных и какие есть способы хранения разреженных матриц?**

Плотная матрица хранит все n^2 элементов. Разреженная содержит в основном нули, и хранить их явно расточительно - запоминают только ненулевые элементы и их позиции.

Форматы хранения: COO (coordinate) - тройки (строка, столбец, значение); CSR (compressed sparse row) - массив значений, их столбцовых индексов и указателей на начала строк; CSC - то же по столбцам; DIA/LIL и другие для специфичных структур. Выигрыш: память O(nnz) вместо O(n^2), а умножение разреженной матрицы на вектор - O(nnz) вместо O(n^2), где nnz - число ненулевых элементов. В курсе для этого используется модуль scipy.sparse.

---

# 9. Численное дифференцирование и интегрирование

**В: Чем различаются методы прямой, обратной и центральной разности?**

Прямая (правая) разность:
f'(x) ~ (f(x+h) - f(x))/h
- использует точку справа, порядок точности O(h). Обратная (левая) разность:
f'(x) ~ (f(x) - f(x-h))/h
- использует точку слева, тоже O(h). Центральная разность:
f'(x) ~ (f(x+h) - f(x-h))/(2h)
- симметрична, порядок O(h^2).

Центральная точнее при том же h (симметрия сокращает члены нечетного порядка в разложении Тейлора), но требует значений по обе стороны от точки. Прямая/обратная незаменимы у границ области, где сосед есть только с одной стороны.

---

В: Что такое сетка дифференцирования, ошибка сокращения (усечения) и ошибка округления? Как они определяют оптимальный шаг?

Сетка дифференцирования - набор дискретных точек (узлов) с шагом h, в которых вычисляется функция для приближения производных. Качество аппроксимации зависит от h.

Ошибка усечения (сокращения) - погрешность самой разностной формулы; она убывает при уменьшении h (например, как O(h) или O(h^2)). Ошибка округления, наоборот, растет при малом h, потому что в формулах делится разность близких чисел на малое h. Суммарная ошибка имеет минимум при некотором оптимальном h: для центральной разности первой производной h ~ eps_machine^(1/2), для второй - около eps_machine^(1/4).

---

В: В чем состоит правило Симпсона для численного интегрирования и какова его точность?

Правило Симпсона приближает интеграл, заменяя подынтегральную функцию на каждом сдвоенном отрезке параболой (по трем точкам). Формула:
∫ f(x) dx ~ (h/3) * (f_0 + 4f_1 + 2f_2 + 4f_3 + ... + f_n),
где коэффициенты чередуются 4 и 2.
Точность: правило Симпсона имеет погрешность O(h^4) и точно интегрирует многочлены до 3-й степени включительно - это заметно точнее метода трапеций (O(h^2)) при той же сетке. Требует четного числа интервалов.

---

# 10. Типы и свойства методов для ОДУ

**В: Какие бывают типы ОДУ и постановок задач для них?**

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

---

В: В чем разница между явными и неявными методами? Что такое многошаговые методы?

Явный метод выражает новое значение y_{n+1} непосредственно через уже известные величины (например, явный Эйлер, метод Рунге-Кутты 4 порядка) - прост в реализации, но имеет ограниченную область устойчивости. Неявный метод задает y_{n+1} уравнением, где оно входит и в правую часть (например, неявный Эйлер, методы Адамса-Мултона), поэтому на каждом шаге решается уравнение, зато устойчивость гораздо лучше - это важно для жестких задач.

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

---

### В: Зачем нужен адаптивный шаг при решении ОДУ?

Адаптивный шаг автоматически подбирает h по оценке локальной ошибки: уменьшает его на участках быстрого изменения решения и увеличивает там, где решение гладкое. Это обеспечивает заданную точность при минимальном числе шагов и помогает удерживать метод в области устойчивости. Оценку ошибки получают, например, сравнением шагов разного порядка (вложенные методы Рунге-Кутты-Фельберга).

---

# 11. Согласованность, устойчивость, сходимость

**В: Что такое согласованность, устойчивость и сходимость численного метода и как они связаны?**

Согласованность (consistency): разностная схема при h -> 0 аппроксимирует исходное дифференциальное уравнение, то есть локальная ошибка усечения стремится к нулю. Устойчивость (stability): малые возмущения (ошибки округления, начальные ошибки) не нарастают неограниченно в ходе вычислений. Сходимость (convergence): численное решение при h -> 0 стремится к точному.

Связь выражает теорема Лакса (для корректно поставленных линейных задач): согласованность + устойчивость <-> сходимость. То есть одной аппроксимации недостаточно - без устойчивости метод может расходиться, даже будучи согласованным.

---

### В: Чем строгая устойчивость отличается от нестрогой (слабой)?

Для тестового уравнения y' = lambday метод порождает множитель роста на шаг.
Строгая (абсолютная) устойчивость означает, что в заданной области параметра h * lambda ошибки строго затухают (множитель по модулю < 1) - это нужно, например, для жестких задач. Нестрогая (слабая) устойчивость допускает, что возмущения не нарастают, но и не затухают (множитель по модулю = 1), например осцилляции с постоянной амплитудой: метод не "взрывается", но и не подавляет ошибки. Различение важно при выборе шага и метода для конкретной задачи.

---

# 12. Детерминированный хаос и динамические системы

## В: Что такое детерминированный хаос, бифуркация и странные аттракторы?

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

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

Странный аттрактор - множество в фазовом пространстве, к которому притягиваются траектории хаотической системы; оно имеет сложную (фрактальную) структуру и не сводится к точке или циклу (классический пример - аттрактор Лоренца). Численное моделирование таких систем особенно чувствительно к ошибкам округления.

---

В: Что такое фильтрация сигналов и как преобразование Фурье применяют для анализа сезонности во временных рядах?

Фильтрация - подавление нежелательных частотных компонент. В частотной области это делается просто: вычисляют спектр (ДПФ/БПФ), ослабляют или обнуляют ненужные частоты (низкочастотный фильтр убирает высокочастотный шум, высокочастотный - медленный тренд, полосовой - оставляет нужный диапазон), затем выполняют обратное преобразование.
Анализ сезонности: временной ряд (продажи, температура и т. п.) раскладывают по частотам. Пики амплитудного спектра на определенных частотах соответствуют периодическим (сезонным) компонентам: например, пик на частоте 1/12 для месячных данных указывает на годовую сезонность.
Так преобразование Фурье выявляет скрытые периодичности и их периоды.

---

# 13. Сигналы: характеристики и спектры

**В: Дайте определения основных характеристик сигнала: амплитуда, период, частота, длина волны, частота дискретизации, герц, угловая частота, фаза.**

Амплитуда - максимальное отклонение сигнала от среднего значения.
Период T - время одного полного колебания. Частота f = 1/T - число колебаний в секунду, измеряется в герцах (Гц). Угловая частота omega = 2pif - скорость изменения фазы в радианах в секунду. Фаза - сдвиг колебания во времени (аргумент синуса/косинуса), задает "положение" волны в начальный момент.

Длина волны lambda - пространственный период (расстояние между соседними одинаковыми фазами), связана со скоростью распространения:
lambda = v/f.
Частота дискретизации f_s - число отсчетов в секунду при оцифровке сигнала; по теореме Котельникова-Найквиста она должна быть не меньше удвоенной максимальной частоты сигнала, иначе возникает наложение (алиасинг).

---

В: Чем амплитудный спектр отличается от частотного (фазового) спектра?

Преобразование Фурье дает для каждой частоты комплексный коэффициент.
Амплитудный спектр - зависимость модуля этого коэффициента от частоты:
он показывает, насколько сильно представлена каждая частота (высота пиков = вклад гармоник).
Фазовый (частотный) спектр - зависимость аргумента (фазы) коэффициента от частоты: он описывает временной сдвиг каждой гармоники.

Для анализа "какие частоты есть в сигнале" обычно используют амплитудный спектр; фазовый важен при восстановлении сигнала и анализе его формы.
В: Как алгоритм Штрассена уменьшает количество умножений по сравнению с наивным алгоритмом? Как это влияет на асимптотическую сложность? Опишите, как архитектура памяти влияет на производительность алгоритма Штрассена. В каких приложениях он используется?


Сокращение умножений: на каждом уровне рекурсии Штрассен заменяет 8 блочных умножений на 7. Для матриц размера 2^k * 2^k это дает 7^k скалярных умножений против 8^k = n^3 у наивного метода. Асимптотика улучшается до O(n^(2.807)).

Архитектура памяти: множество промежуточных матриц повышает потребление памяти и число кэш-промахов, поэтому на практике Штрассена применяют рекурсивно лишь до некоторого порога размера, а ниже переключаются на наивное (кэш-эффективное) умножение.

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

---

В: Объясните, как архитектура памяти влияет на производительность алгоритмов умножения матриц. Как суммирование по Кахану может улучшить точность?


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

Суммирование по Кахану: при сложении многих чисел с плавающей точкой младшие биты теряются на каждом шаге, и ошибка накапливается. Алгоритм Кахана хранит отдельную переменную-компенсацию, в которую собирает потерянную при округлении часть и добавляет ее на следующем шаге. Это резко снижает накопление ошибки округления (погрешность почти не зависит от числа слагаемых), что важно при суммировании скалярных произведений в матричных операциях.

---

В: Какова точность центральной разности для аппроксимации первой производной? Как ошибка зависит от шага h? Сравните прямую разность с центральной разностью по точности и вычислительным затратам.


Центральная разность f'(x) ~ (f(x+h) - f(x-h))/(2h) имеет погрешность аппроксимации O(h2): при уменьшении h в 10 раз ошибка усечения падает примерно в 100 раз. Прямая разность f'(x) ~ (f(x+h) - f(x))/h имеет погрешность O(h): уменьшение h в 10 раз снижает ошибку лишь в 10 раз.

Сравнение: по точности центральная разность на порядок лучше при том же h. По вычислительным затратам она требует двух вычислений функции (в x+h и x-h), прямая - тоже двух (в x+h и x), так что центральная разность дает выигрыш в точности практически бесплатно. При слишком малом h обе формулы начинают страдать от ошибки округления (вычитание близких чисел), поэтому существует оптимальный шаг.

---

# 2. Погрешности: абсолютная, относительная, накопление

**В: Что такое абсолютная и относительная погрешности, и как они связаны со значащими цифрами?**

Абсолютная погрешность - модуль разности точного значения x и приближенного \hat{x}:
Delta = |x - \hat{x}|.
Относительная погрешность - отношение delta = Delta / |x| (часто в процентах), оно показывает точность независимо от масштаба величины.

Связь со значащими цифрами: число верных значащих цифр приближенно определяется относительной погрешностью - если delta ~ 10^(-k), то верны примерно k значащих цифр. Значащие цифры - это все цифры записи, начиная с первой ненулевой; именно относительная погрешность (а не абсолютная) отражает их количество.

---

# В: Как погрешности распространяются и накапливаются при вычислениях?

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

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

---

# 3. Сложность алгоритмов и профилирование в Python

## В: Что такое сложность алгоритма и нотация big-O?

Сложность алгоритма описывает, как растут затраты (время или память) с увеличением размера входа n. Нотация big-O дает верхнюю асимптотическую оценку, отбрасывая константы и младшие члены: O(1) - постоянная, O(log n) - логарифмическая, O(n) - линейная, O(n log n), O(n2), O(n3), O(2ⁿ) - экспоненциальная.

Примеры из курса: наивное умножение матриц - O(n3), Штрассен - O(n^(2.807)), бисекция - O(log((b-a)/eps)) итераций, ДПФ - O(N2), БПФ - O(N log N). Big-O позволяет сравнивать алгоритмы независимо от конкретной машины.

---

# В: Как профилируют код в Python и зачем это нужно?

Профилирование измеряет, сколько времени и ресурсов тратит каждая часть программы, чтобы найти узкие места. В Python для этого используют модули cProfile и profile (детальная статистика по функциям), timeit (точный замер коротких фрагментов), а также построчные профилировщики и анализаторы памяти.

Смысл: асимптотика big-O описывает рост, но реальная скорость зависит от констант, работы с памятью и накладных расходов интерпретатора.
Профилирование показывает, какую именно функцию стоит оптимизировать (например, векторизовать через NumPy), вместо преждевременной оптимизации наград.

---

# 4. Сжимающие отображения и теория сходимости

**В: Что такое сжимающее отображение и что утверждает теория сжимающих отображений?**

Отображение g сжимающее на множестве, если существует константа 0 <= L < 1 такая, что |g(x) - g(y)| <= L * |x - y| для всех x, y из этого множества. То есть оно сближает любые две точки.

Принцип сжимающих отображений (теорема Банаха о неподвижной точке): сжимающее отображение полного множества в себя имеет единственную неподвижную точку x* = g(x*), и итерации x_{n+1} = g(x_n) сходятся к ней из любого начального приближения. На этом основан метод простых итераций для решения уравнений вида x = g(x).

---

В: Что такое константа Липшица и как она задает критерии и скорость сходимости?

Константа Липшица L - наименьшая константа в условии |g(x) - g(y)| <= L * |x - y|. Для гладкой g на отрезке L = max|g'(x)|. Критерий сходимости простых итераций: L < 1 (отображение сжимающее).

Скорость сходимости линейная: ошибка убывает примерно как e_n ~ L^n * e_0, то есть в L раз за итерацию. Чем меньше L, тем быстрее. Можно заранее оценить число итераций для нужной точности. Если L >= 1, сходимость не гарантирована. Критериями остановки служат малость приращения |x_{n+1} - x_n| или невязки.

---

# 5. Виды интерполяции и сплайны

**В: Чем отличаются интерполяция, экстраполяция и аппроксимация?**

Интерполяция - построение функции, проходящей точно через заданные узлы, и оценка значений внутри диапазона узлов. Экстраполяция - оценка значений вне диапазона узлов (менее надежна, ошибка быстро растет).
Аппроксимация - приближение данных функцией, которая не обязана проходить через точки точно (например, методом наименьших квадратов); она предпочтительна для зашумленных данных.

---

В: В чем разница между глобальной и локальной интерполяцией?
Приведите примеры (ступенчатая, линейная, квадратичная).

Глобальная интерполяция строит один полином по всем узлам сразу (например, полином Лагранжа). Недостаток - при большом числе узлов высокая степень дает осцилляции (феномен Рунге). Локальная интерполяция использует на каждом участке лишь несколько соседних узлов.

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

# Дополнительные темы для нестандартных случаев

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

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

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

## Метод Гаусса-Зейделя
Метод Гаусса-Зейделя решает систему линейных уравнений A*x=b итерационно. На каждом шаге новые значения неизвестных сразу используются для вычисления следующих неизвестных.

Метод хорошо работает для диагонально преобладающих матриц и некоторых положительно определенных матриц. Критерий остановки - маленькое изменение x или маленькая невязка ||A*x-b||.

Плюс: простой и не требует прямого разложения матрицы. Минус: может не сойтись, если матрица не подходит.

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

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

## Вторая производная центральной разностью
Вторая производная может быть приближенно найдена формулой
f_second(x) = (f(x+h) - 2*f(x) + f(x-h)) / h^2.

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

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

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

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

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

## Частотная сетка, Найквист и алиасинг
Если сигнал имеет N отсчетов и частоту дискретизации fs, то шаг частотной сетки равен df = fs/N. Частота Найквиста равна fs/2. Частоты выше fs/2 не различаются корректно и могут перейти в ложные низкие частоты. Это называется алиасинг.

Чем больше N при фиксированной fs, тем лучше частотное разрешение.

## Метод наименьших квадратов
Метод наименьших квадратов строит приближающую функцию так, чтобы сумма квадратов ошибок была минимальной. Для прямой y = a*x + b параметры a и b находятся из нормальных уравнений.

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

## PageRank как степенной метод
PageRank ищет стационарный вектор важности страниц. Его можно понимать как степенной метод для матрицы переходов. На каждом шаге новый ранг получается умножением матрицы переходов на текущий вектор рангов.

Коэффициент damping обычно берут около 0.85. Он учитывает случайный переход на любую страницу и делает метод устойчивее.

## QR через отражения Хаусхолдера
QR-разложение через отражения Хаусхолдера представляет матрицу как A = Q*R, где Q ортогональная, а R верхнетреугольная. Идея - занулять элементы ниже диагонали отражениями.

Этот способ обычно устойчивее классического Грамма-Шмидта, потому что лучше сохраняет ортогональность Q при ошибках округления.

# Редкие темы, которые могут попасться на экзамене

## SVD
SVD - сингулярное разложение матрицы. Оно записывается как A = U * Sigma * V^T. Матрицы U и V ортогональные, а Sigma содержит сингулярные числа. Сингулярные числа показывают важность направлений в данных. Малые сингулярные числа часто можно отбросить, если нужна низкоранговая аппроксимация или сжатие.

Связь с собственными значениями: сингулярные числа равны корням из собственных значений матрицы A^T A. То есть сначала можно рассмотреть B = A^T A, найти ее собственные значения lambda_i, а потом взять sigma_i = sqrt(lambda_i).

## PCA
PCA - метод главных компонент. Он ищет новые оси, вдоль которых данные имеют максимальную дисперсию. Сначала данные центрируют, то есть из каждого признака вычитают среднее. Потом строят ковариационную матрицу и ищут ее собственные значения и собственные векторы.

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

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

COO хранит три списка: номера строк, номера столбцов и значения. CSR хранит data, indices и indptr. data - ненулевые значения, indices - номера столбцов, indptr - где начинается каждая строка. Память становится O(nnz) вместо O(n^2), где nnz - число ненулевых элементов.

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

Машинный эпсилон - это примерный уровень относительной ошибки округления. Для double он около 2.22e-16.

Overflow - переполнение, когда число слишком большое и превращается в бесконечность. Underflow - потеря порядка, когда число слишком маленькое и может округлиться к нулю.

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

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

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

## Спектральный радиус
Спектральный радиус матрицы - это максимум модулей ее собственных значений: rho(A) = max |lambda_i|. Степенной метод обычно ищет собственное значение с наибольшим модулем.

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

## Отношение Релея
Отношение Релея считается по формуле lambda = (A*x, x)/(x, x). Оно дает оценку собственного значения по текущему вектору x. В степенном методе его часто используют для уточнения lambda.

## Круги Гершгорина
Круги Гершгорина дают области, где могут лежать собственные значения. Центр круга - диагональный элемент a_ii. Радиус - сумма модулей остальных элементов строки. Все собственные значения лежат в объединении этих кругов.

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

## Нормальная матрица и разложение Шура
Матрица называется нормальной, если A*A^T = A^T*A. Разложение Шура имеет вид A = Q*T*Q^T, где Q ортогональная, а T верхнетреугольная. Для нормальной матрицы T получается диагональной. Поэтому нормальные матрицы хорошо диагонализуются ортогональными преобразованиями.

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

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

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

Для метода Рунге-Кутты 4 порядка локальная ошибка имеет порядок h^5, а глобальная - h^4.

## Согласованность, устойчивость и сходимость
Согласованность значит, что разностная схема при h -> 0 приближает исходное уравнение. Устойчивость значит, что ошибки не растут бесконтрольно. Сходимость значит, что численное решение стремится к точному.

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

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

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

## Константа Липшица
Для простых итераций x = phi(x) важно, чтобы около решения было |phi'(x)| < 1. Тогда phi является сжимающим отображением, и итерации сходятся. Если это число близко к 1, сходимость медленная. Если больше 1, итерации могут расходиться.

## ДПФ, БПФ, Найквист
ДПФ переводит сигнал из временной области в частотную. БПФ считает то же самое быстрее: O(N log N) вместо O(N^2).

Частотное разрешение df = fs/N. Частота Найквиста равна fs/2. Частоты выше fs/2 могут исказиться и дать aliasing.

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

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

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

## Правило Рунге
Правило Рунге оценивает ошибку по двум расчетам: с шагом h и с шагом h/2. Если порядок метода p, то ошибка примерно равна |y_{h/2} - y_h|/(2^p - 1). Это помогает понять, достаточно ли маленький шаг.