ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНУЮ МАТЕМАТИКУ Лекция 8 27 октября 2009 Методы решения нелинейных систем уравнений Задача интерполяции (гладкого восполнения функций) - презентация

1 ВВЕДЕНИЕ В ВЫЧИСЛИТЕЛЬНУЮ МАТЕМАТИКУ Лекция 8 27 октября 2009 Методы решения нелинейных систем уравнений Задача интерполяции (гладкого восполнения функций)

2 3. Методы решения нелинейных систем уравнений Метод Ньютона

3 3. Методы решения нелинейных систем уравнений Теорема о сходимости метода Ньютона Пуст в окрестности корня существуют все вторые производные и

4 3. Методы решения нелинейных систем уравнений Теорема о сходимости метода Ньютона Отображение равномерно невырождено, то есть Тогда метод Ньютона сходится в этой окрестности, его скорость квадратична

5 3. Методы решения нелинейных систем уравнений Доказательство

6 3. Методы решения нелинейных систем уравнений Доказательство

7 4. Задача интерполяции Общая постановка Пусть задана совокупность узлов интерполяции или сетка на некотором отрезке [a, b]. Совокупность узлов Сеточная проекция функции f(t) на [a, b], т.е. таблица, эту таблицу задает оператор ограничения на сетку или рестрикции (от английского restriction) R.

8 4. Задача интерполяции Задача состоит в том, чтобы по таблице {f n } восстановить непрерывную функцию. Обозначим ее через F(t). Разумеется, она отличается от исходной функции f(t), причем такое восстановление неоднозначно и осуществляется оператором интерполяции I. Сама функция F(t) называется интерполирующей или интерполянтом. Необходимо оценить потерю информации при действии этого оператора, т. е. величину зависящую от типа оператора интерполяции и свойств f(t), в частности, ее гладкости.

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

10 Интерполяция обобщенными полиномами

11 4. Задача интерполяции Интерполяция обобщенными полиномами

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

13 Алгебраическая интерполяция

14 4. Задача интерполяции Теорема. Пусть среди сеточных узлов нет кратных. Тогда решение задачи алгебраической интерполяции существует и единственно, т.е. для любой сеточной функции, определенной в N+1 узле, существует единственный полином степени не выше N, принимающий в заданных точках заданные значения.

15 4. Задача интерполяции Доказательство

16 4. Задача интерполяции Конструктивное решение задачи интерполяции – полином в форме Лагранжа Интерполяционный базис

17 4. Задача интерполяции Полином в форме Лагранжа

18 4. Задача интерполяции Теорема об остаточном члене интерполяции

19 4. Задача интерполяции Теорема об остаточном члене интерполяции Пусть функция f(t) имеет на отрезке [a, b] N + 1 ограниченную производную. Тогда

20 4. Задача интерполяции Доказательство имеет, по крайней мере, N + 2 нуля Их можно указать. Точки х = t n (n = 0, …, N) нули, поскольку f(t n ) = L(t n ), а последнее слагаемое обращается в них в нуль.,

21 4. Задача интерполяции Доказательство (продолжение)

22 4. Задача интерполяции Доказательство

23 4. Задача интерполяции Следствие – экстраполяция функций

24 4. Задача интерполяции Минимизация остаточного члена за счет выбора узлов инетерполяции

25 4. Задача интерполяции Нули полинома Чебышева Или сетка из экстремумов полинома Чебышева

26 4. Задача интерполяции Связь алгебраической интерполяции на Чебышевской сетке и тригнометрической интерполяцией

27 4. Задача интерполяции Обусловленность задачи интерполяции

28 4. Задача интерполяции Обусловленность задачи интерполяции

29 4. Задача интерполяции Функция Лебега и постоянная Лебега (данной сетки)

30 4. Задача интерполяции Постоянная Лебега – норма оператора алгебраической интерполяции!

31 4. Задача интерполяции Приведем (без доказательства) примерные оценки роста постоянной Лебега в зависимости от числа узлов сетки. Константа Лебега растет примерно как l N ~ 2 N для равномерной сетки и l N ~ ln(N) для сетки с чебышевским набором узлов. Доказано, что рост константы Лебега для последней сетки асимптотически стремится к минимально возможному, и сетка с чебышевскими узлами близка к оптимальной для задач интерполяции.

32 4. Задача интерполяции Вопросы?