Решение задачи об оптимальной интерполяции с помощью дискретного преобразования Фурье (ДПФ) (стр. 6 из 8)

что и требовалось установить.

§ 7. Решение задачи оптимальной интерполяции

Допустим, что

- натуральное число. Рассмотрим следующую экстремальную задачу:

(1)

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

заданные значения

а гладкость данного вектора характеризуется квадратом нормы конечной разности r – го порядка. Чаще всего рассматривается случай, когда r=2.

Проведём замену переменных

После чего перепишем задачу (1) в компонентах

Этот процесс начнём с целевой функции. Как было показано в последнем примере предыдущего параграфа

где

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

Отметим только, что здесь

Введём обозначение

Тогда

(2)

Теперь обратимся к ограничениям. Имеем

Таким образом, ограничения задачи (1) принимают вид

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

по экспоненциальному базису. Она равносильна тому, что

(3)

где

На основании (2) и (3) приходим к эквивалентной постановке задачи (1):

(4)

Последняя задача, т.е. задача (4) распадается на m независимых подзадач, соответствующих разным

(5)

Поскольку

, то при

приходим к задаче

Решение этой задачи имеет вид

(6)

Заметим только, что минимальное решение целевой функции равно нулю.

Допустим теперь, что

В этом случае мы данную задачу решаем методом множителей Лагранжа.

Строим функцию Лагранжа:

Итак,

(7)

Чтобы найти

воспользуемся ограничениями

Из этого выражения находим

Подставив

в (7), получим решение задачи (4) при

Введём обозначение

Тогда окончательное решение запишется в виде

(8)

Формулы (6) и (8) определяют

на всём основном периоде

По формуле обращения находим единственное решение задачи (1):

(9)

При этом минимальное значение целевой функции задачи (1) складывается из минимальных значений целевых функций задач (5) при

, так, что

Преобразуем (9) к более удобному для вычислений виду. Индексы

представим в виде

Согласно (6) и (8) запишем

Таким образом, приходим к следующей схеме решения задачи (1):

1. в первую очередь, формируем два массива констант, зависящих только от m, n и r:

одномерный

и (по столбцам) составляем двумерный

2. вычисляем

при

3. после этого вводим двумерный массив В со столбцами

4. и наконец, применяя обратное ДПФ порядка m ко всем n-1 строкам матрицы В, получаем решение задачи (1):

Решения задач

Задача 1. Докажите, что

Доказательство. По определению сравнения

Используя свойства сравнений, получим

Или в одну строку

т.е. 12 есть остаток от данного деления.

Задача 2. Пусть

и даны два вектора

Требуется найти

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

Задача 3. Докажите, что

Доказательство. Докажем данное равенство методом математической индукции.

При n=1 имеем верное равенство

Пусть n=k

Тогда

Равенство доказано.

Задача 4. (Китайская теорема об остатках). Предположим, что

, причём сомножители

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

или

(1)

имеет единственное решение на множестве

при любых

Найдите это решение.