---

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

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

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

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


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

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

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

---

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


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

Верные цифры: в строгом (узком) смысле верными считаются разряды, в
которых погрешность не превышает 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. Собственные значения и степенной метод

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


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

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

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

---

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


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

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

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

---

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


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

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

---

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

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


Сингулярное разложение представляет матрицу как A = U · Σ · V^T, где U и V ортогональны, а Σ - диагональ неотрицательных сингулярных чисел σ_1 ≥ σ_2 ≥ ... . При анализе изображений матрицу пикселей приближают суммой нескольких первых сингулярных компонент (низкоранговое приближение): это сжимает изображение, сохраняя главные детали и отбрасывая мелкие, отвечающие малым σ.

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

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

---

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

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


Наивное умножение матриц n×n требует n³ скалярных умножений - сложность O(n³). Штрассен разбивает каждую матрицу на 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 < √ε_machine ≈ 10^(-8)) деление на h^2 усиливает ошибку округления; оптимум для второй производной примерно h ≈ ε_machine^(1/4) ≈ 10^(-4).

---

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

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


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

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

---

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

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


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

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

---

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


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

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

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

---

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

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

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

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

---

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


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

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

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

---

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


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

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

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

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

---

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


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

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

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

---

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


ДПФ раскладывает дискретный сигнал по базису комплексных экспонент (гармоник) разных частот:
X[k] = Σ x[n] · e^(-2π 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 ε_machine ≈ 2.22 · 10^(-16). Стандарт также определяет специальные значения: ±0, ±∞ и NaN.

---

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

Overflow (переполнение) возникает, когда результат по модулю превышает максимально представимое число (для double порядка 1.8·10³⁰⁸): результат становится ±∞. Underflow (исчезновение порядка) - когда результат по модулю меньше наименьшего нормализованного числа (около 2.2·10⁻³⁰⁸): он представляется денормализованным числом со сниженной точностью или округляется до нуля.

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

---

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

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

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

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

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

Кубический сплайн: на каждом отрезке полином 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, а сингулярные числа задают разброс вдоль них (σ_1^2 пропорциональны дисперсиям). Поэтому PCA на практике вычисляют через SVD - это устойчившее, чем явно строить ковариацию. Прикладные аспекты: понижение размерности, сжатие, шумоподавление, визуализация многомерных данных.

---

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

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

Ранги страниц - это стационарное распределение цепи Маркова, то есть собственный вектор матрицы переходов, отвечающий наибольшему собственному значению λ = 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 ≈ ε_machine^(1/2), для второй - около ε_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} непосредственно через уже известные величины (например, явный Эйлер, RK4) - прост в реализации, но имеет ограниченную область устойчивости. Неявный метод задаёт y_{n+1} уравнением, где оно входит и в правую часть (например, неявный Эйлер, методы Адамса-Мултона), поэтому на каждом шаге решается уравнение, зато устойчивость гораздо лучше - это важно для жёстких задач.

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

---

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

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

---

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

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

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

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

---

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

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

---

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

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

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

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

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

---

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

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

---

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

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

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

Длина волны λ - пространственный период (расстояние между соседними одинаковыми фазами), связана со скоростью распространения:
λ = 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(h²): при уменьшении 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}:
Δ = |x - \hat{x}|.
Относительная погрешность - отношение δ = Δ / |x| (часто в процентах), оно показывает точность независимо от масштаба величины.

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

---

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

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

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

---

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

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

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

Примеры из курса: наивное умножение матриц - O(n³), Штрассен - O(n^(2.807)), бисекция - O(log((b-a)/ε)) итераций, ДПФ - O(N²), БПФ - 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). Это помогает понять, достаточно ли маленький шаг.