Методы приближения функций

Задача линейной интерполяции

Интерполяционный многочлен Лагранжа

Требования к программе и заготовка

https://maxxk.github.io/programming-semester-6/

Задача линейной интерполяции

Дано: исходная функция $f : X → Y$, «базис» $g_i : X → Y \qquad f, g_i ∈ F(X,Y)$, условия интерполяции $λ_j : F(X, Y) → 𝐑$

Найти: $Pf = \sum\limits^n_{i=1} α_i \, g_i$, такую, что $λ_j[Pf] = λ_j[f]$.

$\color{red}{λ_j(f)}$, $\color{blue}{f}$, $\color{green}{Pf}$

Постановка задачи линейной интерполяции

$G(X, Y)$ — линейная оболочка $\{g_i\}$ в $F(X,Y)$

$Λ(X, Y)$ — линейная оболочка $\{λ_j\}$ в $F^*(X, Y)$

Найти $P : F(X, Y) → G(X, Y)$ т.ч. $λ(f)=λ(Pf) | λ ∈ Λ$.

Теорема (с. 12). При линейно независимых $g_i$ и $λ_j$:

Задача линейной интерполяции корректна $⇔$ $m=n$ и матрица $A = (λ_j(g_i))$ обратима;
Вектор коэффициентов $α = (α_i) = A^{-1} (λ_j(f)) $;
$P ∘ P = P$.

$Pf ≡ Σ_i α_i g_i$

Обусловленность базиса

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

Число обусловленности базиса $g_i$: $\mathrm{cond}(g_i) = \dfrac{\min_α{K(α)}}{\max_α{K(α)}}$

$K(α) = \dfrac{\| \sum α_i g_i \|_G}{\| α \|}$

Интерполяционный многочлен Лагранжа

Работаем с функциями одной переменной на отрезке $f : 𝐑 ⊃ [a, b] → 𝐑$
Для точек $x_1 < x_2 < … < x_n$ и условий $λ_j = f(x_j)$:

$l_i(x) = \prod\limits_{j \neq i} \dfrac{x - x_j}{x_i - x_j}$

$λ_j(l_i) = δ_{ij}$

$L f = \sum f(x_i) l_i$

Число обусловленности: $κ ⩾ C e^{n/2}$

Наивная реализация

$Y_i = \dfrac{f(x_i)}{\prod\limits_{j \neq i} (x_i - x_j)}\qquad$ $n^2 - n$ операций
$φ(x) = \prod_i (x - x_i) \qquad$ $n (- 1)$ операций
$L f(x) = φ(x) \sum \dfrac{Y_i}{x - x_i}\qquad$ $n \pm 1$ операций
— есть значительно более быстрый способ.

Задача II

Требования ко второй задаче и заготовку программного кода можно скачать в дисплейных классах.
Для этого в терминале нужно запустить текстовый браузер lynx:
lynx
Для сохранения файла на диск стрелками выделите ссылку на файл и нажмите D. Этот же файл доступен по ссылке: https://goo.gl/HCXKZV

Задача II

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

int method_init(int n, double a, double b, double *values, double *derivatives, double *state);
double method_compute(int n, double x, double *state)

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

method_init

int method_init(int n, double a, double b, double *values, double *derivatives, double *state);

Первая функция вычисляет коэффициенты приближения и сохраняет их в массив state. Аргументы первой функции:

n — количество точек
a, b — границы отрезка приближения
values — массив значений в точках
derivatives — массив производных в точках
state — память для хранения коэффициентов приближения

method_compute

Вторая функция вычисляет значение приближения $Pf$, заданное в массиве state в точке x.

n — количество точек, по которым выполнялось приближение
x — аргумент функции
state — массив коэффициентов приближения

Тем, кто использует C++ может быть удобнее написать класс, который хранит n и state в полях. Тогда можно единообразно обрабатывать при рисовании исходную функцию и приближение (через базовый класс).

Графический интерфейс

Будем использовать заготовку на Qt. Для этого нужно скачать graph_qt4.zip через lynx, или по ссылке: https://goo.gl/OVGfVe

Для сборки вам понадобится установленная версия Qt4 и команды:

qmake
make

В дисплейных классах вместо qmake нужно использовать команду qmake-qt4