ПЛАН ЗАНЯТТЯ No 23
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Обчислення значень поліномів та інтерполяція функцій. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: розглянути сортування масивів методом Шелла . Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Савченко В.С. Разработка алгоритмов: от простого к сложному.
Учебное пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с. 2. Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры
данных в Delphi: Пер. с англ./ Бакнелл Джулиан М.: СПб ООО «ДиасофтЮП», 2003. – 560 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Обчислення значень поліномів та інтерполяція функцій.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No15 Тема: Обчислення значень поліномів та інтерполяція функцій.
Интерполяция функций является одним из фундаментальных разделов вычислительной математики. До появления компьютеров для многих практических вычислений применялись таблицы элементарных функций (синусов, логарифмов и т. п.). Для получения достаточно точных результатов при значениях аргументов, расположенных между узловыми точками, для которых даны табличные значения функции, решалась задача интерполяции (в переводе - «между полюсами»). В наиболее простом случае соседние точки графика этой функции соединялись отрезком прямой (линейная интерполяция). Собственно, густота точек таблицы и выбиралась в расчете на интерполяцию. Например, выражение «четырехзначные таблицы» означает, что для любого значения аргумента, а не только для указанных в таблице в качестве узловых, путем интерполяции, (как правило, линейной) можно получить значение табулированной функции с точностью до четырех значащих цифр. Основополагающее значение задачи интерполяции объясняется также тем, что многие методы решения задач численного дифференцирования, интегрирования, решения дифференциальных и интегральных уравнений сводятся к дифференцированию и интегрированию интерполяционного многочлена. После появления компьютеров значение задачи интерполяции функций, заданных таблично, не потеряло актуальности, поскольку в результате численного решения сложных задач получается ряд значений искомой функции при разных значениях входного параметра. Получение большого числа таких значений сопряжено с большими затратами машинного времени. Применение интерполяции в этом случае позволяет существенно уменьшить эти затраты. Однако, в отличие от задачи интерполяции известной функции, в этом случае информация об искомой функции ограничивается таблицей ее значений. Эта задача является некорректной, поскольку существует бесконечное множество функций, имеющих заданное конечное число известных значений. В связи с этим задача интерполяции в реальных условиях есть важнейшая проблема вычислительной математики, решение которой позволяет найти ключ к решению многих других задач, необходимых для практики. Интерполя ция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчѐтами часто приходится оперировать наборами значений, полученных экспериментальным путѐм или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией кривой. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.
Рассмотрим систему несовпадающих точек
. Пусть значения функции
Задача интерполяции состоит в поиске такой функции
— интерполирующей функцией или интерполянтом.
Постановка задачи Пусть некоторая функция f(x) задана своими значениями y
j
=f(x
j
) на дискретном множестве точек x
j
., j=0,...,m. Требуется приближенно определить аналитический вид этой функции и тем самым получить возможность вычислить ее значения в промежуточных точках x∈(x
j
,x
j+1
). График, иллюстрирующий данную задачу, изображен на рис. 1.1.
Рис. 1.1. К задаче интерполяции функций.
Интерполирующую функцию будем искать в виде алгебраического многочлена
n
n
)( ∑
i i
=
i
. (1.1)
Поскольку многочлен )(xP
n
xP
=
xa 0
в узловых точках должен совпадать с заданными значениями функции, то задача сводится к решению системы линейных алгебраических уравнений
n ∑
yxa
ji i
= j
nkkj = + (1.2) i
= относительно неизвестных a
i
, ,, 0
(k – номер начальной узловой точки, используемой в данном расчете).
Способы интерполяции Интерполяция полиномами
называют • Точки
узлами интерполяции, а их совокупность — интерполяционной сеткой.
- Пары
называют точками данных или базовыми точками.
- Разность между «соседними» значениями
— шагом интерполяционной сетки. Он может быть как переменным так и постоянным.
- Функцию
известны только в этих точках:
(
из заданного класса функций, что
) из некоторой области
На практике чаще всего применяют интерполяцию полиномами. Это связано прежде всего с тем, что полиномы легко вычислять, легко аналитически находить их производные и множество полиномов плотно в пространстве непрерывных функций (теорема Вейерштрасса).
Лине йная интерполя ция — интерполяция алгебраическим двучленом P
1
(x) = ax + b функции f, заданной в двух точках x
0
и x
1
отрезка [a, b].
Геометрическая интерпретация
Геометрически это означает замену графика функции f прямой, проходящей через точки (x
0
,f(x
0
)) и (x
1
,f(x
1
)).
Уравнение такой прямой имеет вид:
отсюда для
Это и есть формула линейной интерполяции, при этом
где R
1
Справедлива оценка
(x) — погрешность формулы:
Для перегляду тексту необхідно залогінитись.