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



Пусть есть таблица из N точек и значений функции в этих точках.

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

Аппроксимация - приближение кривой, не обязательно проходящей через все точки. Основные методы аппроксимации обладают (и это очень ценно) свойством 'local control': изменение значения функции в одной точке влечет за собой перевычисление лишь 1-3 формул (это гораздо лучше, чем N формул, особенно в реальных приложениях компьютерной графики).


  Алгоритмы из 'Практикума на ЭВМ' К.Ю. Богачева





Скачать методичкуzip

Глава I. МЕТОДЫ ПРИБЛИЖЕНИЯ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ
§1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОЙ ИНТЕРПОЛЯЦИИ
§2. ОБУСЛОВЛЕННОСТЬ БАЗИСА
§3. ИНТЕРПОЛЯЦИОННЫЙ МНОГОЧЛЕН ЛАГРАНЖА
§4. РАЗДЕЛЕННЫЕ РАЗНОСТИ
§5. ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА НЬЮТОНА
§6. ИНТЕРПОЛЯЦИЯ "ДВИЖУЩИМИСЯ" МНОГОЧЛЕНАМИ
§7. ОЦЕНКИ ПОГРЕШНОСТИ ИНТЕРПОЛЯЦИОННОЙ ФОРМУЛЫ НЬЮТОНА
§8. РАЗДЕЛЕННЫЕ РАЗНОСТИ С КРАТНЫМИ УЗЛАМИ
§9. ИНТЕРПОЛЯЦИЯ С КРАТНЫМИ УЗЛАМИ
§10. ВЫЧИСЛЕНИЕ ПРОИЗВОДНЫХ МНОГОЧЛЕНА В ФОРМЕ НЬЮТОНА
§11. МНОГОЧЛЕНЫ ЧЕБЫШЕВА
§12. МИНИМИЗАЦИЯ ПОГРЕШНОСТИ ИНТЕРПОЛЯЦИИ ЗА СЧЕТ ВЫБОРА УЗЛОВ
§13. РАЗЛОЖЕНИЕ ПО МНОГОЧЛЕНАМ ЧЕБЫШЕВА
    §13.1. Постановка задачи линейной интерполяции
    §13.2. Алгоритм построения разложения
    §13.3. Оценка количества арифметических операций
    §13.4. Связь разложения по многочленам Чебышева и интерполяции
§14. ПРЕИМУЩЕСТВА КУСОЧНО-МНОГОЧЛЕННОЙ АППРОКСИМАЦИИ
§15. КУСОЧНО-ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ
§16. КУСОЧНО-ЛИНЕЙНАЯ АППРОКСИМАЦИЯ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ
    §16.1. Постановка задачи линейной интерполяции
    §16.2. Вычисление матрицы системы задачи линейной интерполяции
    §16.3. Свойства приближающей функции
    §16.4. Вычисление правой части системы задачи линейной интерполяции
§17. АППРОКСИМАЦИЯ МНОГОЧЛЕНАМИ ЧЕБЫШЕВА МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ
    §17.1. Интегральные свойства многочленов Чебышева
    §17.2. Постановка задачи линейной интерполяции
    §17.3. Вычисление коэффициентов разложения
    §17.4. Алгоритм вычисления коэффициентов разложения
    §17.5. Оценка количества арифметических операций
§18. КУСОЧНО-ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ НЕГЛАДКИХ ФУНКЦИЙ НА СПЕЦИАЛЬНЫХ СЕТКАХ
§19. ИНТЕРПОЛЯЦИЯ КУСОЧНО-КУБИЧЕСКИМИ ФУНКЦИЯМИ
    §19.1. Общая схема
    §19.2. Алгоритм вычисления коэффициентов многочлена Рi
    §19.3. Кусочная интерполяция кубическими многочленами Эрмита
    §19.4. Кусочная интерполяция кубическими многочленами Бесселя
    §19.5. Кусочная интерполяция кубическими многочленами методом Акимы
    §19.6. Кусочная интерполяция кубическими многочленами с использованием разделенных разностей
    §19.7. Интерполяция кубическими сплайнами
    §19.8. Определение недостающих граничных условий
        §19.8.1. Определение недостающих граничных условий по известным значениям первой производной функции в граничных узлах
        §19.8.2. Определение недостающих граничных условий по известным значениям второй производной функции в граничных узлах
        §19.8.3. "Естественные" граничные условия
        §19.8.4. Условие "отсутствия узла" в приграничных узлах
        §19.8.5. Дополнительный узел в приграничных узлах
        §19.8.6. Экстраполяция в приграничных узлах
§20. ИНТЕРПОЛЯЦИЯ ПАРАБОЛИЧЕСКИМИ СПЛАЙНАМИ
    §20.1. Общая схема
    §20.2. Алгоритм вычисления коэффициентов многочлена Рi
    §20.3. Интерполяция параболическими сплайнами
    §20.4. Определение недостающих граничных условий
        §20.4.1. Определение недостающих граничных условий по известным значениям первой производной функции в граничных узлах
        §20.4.2. Определение недостающих граничных условий по известным значениям второй производной функции в граничных узлах
        §20.4.3. "Естественные" граничные условия
        §20.4.4. Условие "отсутствия узла" в приграничных узлах
        §20.4.5. Дополнительный узел в приграничных узлах
        §20.4.6. Экстраполяция в приграничных узлах

Глава II. МЕТОДЫ ПРИБЛИЖЕНИЯ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ
§1. ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ ТЕНЗОРНЫМИ ПРОИЗВЕДЕНИЯМИ
    §1.1. Постановка задачи интерполяции тензорными произведениями и теорема корректности
    §1.2. Оценка числа арифметических операций
    §1.3. Алгоритм интерполяции тензорными произведениями
    §1.4. Программная реализация алгоритма
    §1.5. Интерполяции тензорными произведениями в случае многочленной аппроксимации
        §1.5.1. Интерполяционный многочлен Лагранжа
        §1.5.2. Разделенные разности для функции многих переменных
        §1.5.3. Интерполяционная формула Ньютона
        §1.5.4. Интерполяция "движущимися" многочленами
        §1.5.5. Интерполяция с кратными узлами
        §1.5.6. Разложение по многочленам Чебышева
        §1.5.7. Аппроксимация многочленами Чебышева методом наименьших квадратов
    §1.6. Интерполяции тензорными произведениями в случае кусочно-многочленной аппроксимации
        §1.6.1. Кусочно-линейная интерполяция
        §1.6.2. Кусочно-линейная аппроксимация методом наименьших квадратов
        §1.6.3. Кусочно-кубическая интерполяция
        §1.6.4. Кусочно-квадратичная интерполяция
§2. ПРИБЛИЖЕНИЕ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ МЕТОДОМ КОНЕЧНЫХ ЭЛЕМЕНТОВ
    §2.1. Постановка задачи линейной интерполяции
    §2.2. Способы построения триангуляции области
    §2.3. Приближение функций в треугольнике
        §2.3.1. Постановка задачи линейной интерполяции
        §2.3.2. Приближение функций в прямоугольном треугольнике
        §2.3.3. Приближение линейными функциями
        §2.3.4. Приближение квадратическими функциями
        §2.3.5. Приближение кубическими функциями
ПРОГРАММА КУРСА
ЛИТЕРАТУРА