Численные методы решения задач презентация

Содержание

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

Слайд 1ИНФОРМАТИКА

Тема 6.

Численные методы решения задач.

Слайд 2Интерполяция – приближенное или точное нахождение какой-либо величины по известным отдельным

значениям этой же или других величин, связанных с ней.

В первоначальном понимании интерполяция – это восстановление функции по известным ее значениям или значениям ее производных в заданных точках.

Экстраполяция – продолжение функции за пределами ее области определения.

6.5. Интерполяция и приближение полиномами







Слайд 3Постановка задачи. Предположим, что функция f(x) известна в (N+1) точке: (x0;y0),

(x1;y1),…, (xN;yN).
Значения xk принадлежат интервалу [a;b] и удовлетворяют условиям



















Точки (x0;y0), (x1;y1),…, (xN;yN) называются узловыми.

Условие прохождения интерполяционной функции через узловые точки называют условием Лагранжа.

Слайд 4Интерполяционная функция φ(x) имеет вид многочлена










6.5.1. Интерполяция алгебраическим полиномом















Слайд 5
Схема Горнера
Фрагмент программы на языке Си

p=c[n];
for(i=n-1; i>=0; i--)
p=c[i]+p*x;

Количество

Обычный способ Схема операций Горнера
Сложение
Умножение



Слайд 6
Интерполяционный полином Лагранжа имеет вид:










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








Достоинством полинома Лагранжа является

то, что не требуется предварительного определения коэффициентов полинома.



Слайд 7
Интерполяционный полином Ньютона имеет вид:

6.5.3. Интерполяционный полином Ньютона

– коэффициенты полинома

Ньютона.

Коэффициенты полинома Ньютона находятся исходя из выполнения условия Лагранжа.










Слайд 8
Аналитическая формула, по которой находятся коэффициенты полинома, имеет сложный вид
Итерационная

процедура очень простая.




























Слайд 9
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 10
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 11
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 12
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 13
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 14
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 15
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 16
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 17
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 18
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 19
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 20
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 21
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 22
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 23
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.




























Слайд 24
Пример. Найти значения коэффициентов полинома Ньютона для шести узловых – точек.








Слайд 25
Проверка.






К достоинствам данного метода можно отнести
меньшая погрешность интерполяции при близкорасположенных

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

Недостатком является проведение предварительных расчетов коэффициентов.

Слайд 26Сплайном называется функция, определенная на отрезке [a; b], совпадающая на частичных

отрезках [xi; xi+1] с некоторым алгебраическими многочленами степени не выше m и имеющая непрерывную (m–1)-ю производную.

Параболическим сплайном называют совокупность многочленов второй степени вида


6.5.4. Интерполяция параболическим сплайном




– коэффициенты параболических полиномов
– число узловых точек

Слайд 27Коэффициенты ai, bi, ci находятся при решении системы линейных уравнений, которые

получаются из выполнения трех условий:

равенство значений сплайна и аппроксимируемой функции в узлах (условие Лагранжа)

непрерывность первой производной в узловых точках:


равенство некоторому значению D первой производной в начале или на конце интервала: или





– первая производная параболического многочлена







Слайд 28
Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.






Слайд 29
Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.






Слайд 30
Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.










Слайд 31
Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.














Слайд 32
Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.


















Слайд 33
В общем случае итерационная процедура нахождения коэффициентов параболического сплайна следующая:
1. Находятся

значения hK при K=0, 1, 2,…, (N–1) по формуле

2. Находятся значения zK при K=0, 1, 2,…, (N–1) по формуле


3. Находятся значения aK, bK, cK при K=0, 1, 2,…, (N–1) по формулам
если задано значение первой производной D в начале интервала интерполяции

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























Слайд 34






















Пример. Найти коэффициенты параболического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}, а производная в конце интервала равна нулю.









Слайд 35Кубическим сплайном называют совокупность многочленов третьей степени вида

6.5.5. Интерполяция кубическим сплайном



–

коэффициенты кубических полиномов
– число узловых точек



Слайд 36Коэффициенты ai, bi, ci, di находятся при решении системы линейных уравнений,

которые получаются из выполнения трех условий:

равенство значений сплайна и аппроксимируемой функции в узлах (условие Лагранжа)

непрерывность первой и второй производной в узловых точках:


равенства нулю вторых производных на концах интервала:





– первая производная кубического многочлена
– вторая производная кубического многочлена













Слайд 37
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.








Слайд 38
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.












Слайд 39
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.













Слайд 40
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.
















Слайд 45
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.



















Слайд 47
В общем случае итерационная процедура нахождения коэффициентов кубического сплайна следующая:
1. Находятся

значения hK при K=0, 1, 2,…, (N–1) по формуле

2. Находятся значения gK при K=0, 1, 2,…, (N–1) по формуле

3. Находятся значения uK при K=0, 1, 2,…, (N–1) по формуле

4. Находятся значения mK при решении системы линейных уравнений
























Слайд 48
В общем случае итерационная процедура нахождения коэффициентов кубического сплайна следующая:
5. Принимается

m0 = mN = 0

6. Находятся значения коэффициентов aK, bK, cK, dK кубических полиномов при K=0, 1, 2,…, (N–1) по формулам

























Слайд 49
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.




























Слайд 50
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 51
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 52
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 54
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 55
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 56
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 57
Пример. Найти коэффициенты кубического сплайна для следующих значений узловых точек: {0;0},

{1;0,5}, {2;2}, {3;1,5}.





























Слайд 586.5.6. Метод наименьших квадратов

Постановка задачи.
Известно, что узловые точки (x1;y1), (x2;y2),…,

(xN;yN) определены с экспериментальной погрешностью.
Требуется найти интерполирующую функцию φ(x), которая бы проходила так, чтобы ошибки интерполяции были бы минимальны.

Слайд 596.5.6. Метод наименьших квадратов

– базисные функции.


– среднеквадратичная ошибка интерполяции.

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

методу наименьших квадратов сводится к нахождению значений коэффициентов c1, c2,…, cm, при которых величина Q получает минимальное значение.

Слайд 606.5.6. Метод наименьших квадратов






Слайд 616.5.6. Метод наименьших квадратов






Слайд 65
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется найти по

методу наименьших квадратов прямую, проходящую через начало координат.






























Слайд 66
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется найти по

методу наименьших квадратов прямую, проходящую через начало координат.








































Слайд 67
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести произвольную

прямую по методу наименьших квадратов.




























Слайд 68
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести произвольную

прямую по методу наименьших квадратов.









































Слайд 69
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести произвольную

прямую по методу наименьших квадратов.





















Слайд 70
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести произвольную

прямую по методу наименьших квадратов.





















Слайд 71
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести параболу

по методу наименьших квадратов.




























Слайд 72
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести параболу

по методу наименьших квадратов.


































Слайд 73
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести параболу

по методу наименьших квадратов.


































Слайд 74
Пример. Даны результаты измерений: {0;0}, {1;0,5}, {2;2}, {3;1,5}. Требуется провести параболу

по методу наименьших квадратов.











































Слайд 78








































Значение Q составило:
для прямой, проходящей через начало координат – 0,71
для

произвольной прямой – 0,7
для параболы – 0,45



Слайд 79








































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

Q, а с другой стороны, к увеличению времени вычисления неизвестных коэффициентов c1, c2, cm.

Для оценки приемлемого значения числа степени многочлена используют величину




За оптимальное значение степени многочлена следует принять то значение m, начиная с которого величина σm стабилизируется или начинает возрастать.

Слайд 806.5.7. Интерполяция тригонометрическим полиномом

Если требуется провести интерполяцию данных, имеющий периодический характер,

то в качестве базисных функций φ1(x), φ2(x),…, φm(x) выбираются периодические функции.

Тригонометрический полином порядка M имеет вид


Коэффициенты тригонометрического полинома находятся по методу наименьших квадратов.





Слайд 81
Пример. Аппроксимировать функцию y=5·x на интервале [–π; π] тригонометрическими полиномами порядка

1, 2 и 3. Тринадцать узловых точек расположены равномерно на данном интервале.
















































Слайд 82
Пример. Аппроксимировать функцию y=5·x на интервале [–π; π] тригонометрическими полиномами порядка

1, 2 и 3. Тринадцать узловых точек расположены равномерно на данном интервале.















































Слайд 846.5.8. Интерполяция кривой Безье

Пьер Безье – французский инженер компании Рено, разработчик

системы проектирования UNISURF


Поль де Фаже де Кастельжо – французский математик и физик, автор рекурсивного способа построения кривых Безье







Слайд 856.5.8. Интерполяция кривой Безье

Кривая Безье – это параметрическая кривая, задаваемая выражением

–

функция компонент векторов опорных вершин

– базисные функции кривой Безье.








Слайд 86Кубические кривые Безье (n=3) широко используются в графических редакторах












Слайд 87Пример построения кубической кривой Безье (n=3)












Слайд 88Пример построения кубической кривой Безье (n=3)












Слайд 89Пример построения кубической кривой Безье (t=0,25)












Слайд 90Пример построения кубической кривой Безье (t=0,25)












Слайд 91Пример построения кубической кривой Безье (t=0,25)












Слайд 92Пример построения кубической кривой Безье (t=0,25)












Слайд 93Пример построения кубической кривой Безье (t=0,5)












Слайд 94Пример построения кубической кривой Безье












Слайд 95Пример построения кубической кривой Безье












Слайд 96Пример построения кривой Безье 4-й степени












Похожие презентации

Задачи линейного программирования. (Тема 3) 342
Sources of Information 446
1С:Предприятие 8. Управление сервисным центром 244
Калькулятор для умных часов AWCalculator 257
Языковая личность интервьюера в современном массмедийном дискурсе (на материале экспертного и портретного интервью) 353
Макросы в офисных приложениях 499

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

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

Для правообладателей

Яндекс.Метрика