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

1 Функциональные пространства Введение Во многих приложениях необходимо оценивать степень близости между собой математических объектов – чисел, векторов, функций. Например, при исследовании сходимости числовых и функциональных рядов, в задачах приближенного решения уравнений и их систем, аппроксимации и интерполяции, в задачах численного интегрирования и дифференцирования функций. Множество функций в месте со способом определения близости между функциями будем называть функциональным пространством.

2 Топологические пространства Наиболее общим видом пространств являются топологические пространства. Для каждой точки по некоторым правилам назначается система ее окрестностей. Точка является пределом заданной последовательности, если в любой окрестности точки содержится точка из этой последовательности.

3 Метрические пространства Более частный, по сравнению с топологическими, вид пространств. Здесь степень близости между элементами задается числом - для каждой пары элементов x, y определено расстояние между элементами: Последнее утверждение называется неравенством треугольника. Примером метрики является расстояние по геодезической в горной местности. Метрика не обладает трансляционной инвариантностью:

4 Сфера, шар, расстояние от точки до множества в метрическом пространстве Сфера радиуса R с центром в точке a: Открытый шар радиуса R с центром в точке a: Замкнутый шар радиуса R с центром в точке a: Расстояние от точки a до множества M:

5 Нормированные пространства - - Векторные пространства, в которыах определена длина вектора – его норма: Норма позволяет определить расстояние между векторами: которое обладает трансляционной инвариантностью :

6 Сфера, шар, расстояние от точки до множества в нормированном пространстве Сфера радиуса R с центром в точке a: Открытый шар радиуса R с центром в точке a: Замкнутый шар радиуса R с центром в точке a: Расстояние от точки a до множества M:

7 Простанства L 2 и C - - Наиболее известные нормированные функциональные пространства. Для функций одной переменной: Для функций многих переменных:

8 Геометрический смысл норм в простанствах L 2 и C Норма C соответствует равномерной сходимости. Если то расстояние между графиками f(x) и g(x) не превышает ε. Норма L 2 используется, например, при исследовании сходимости рядов Фурье. Она накладывает гораздо более слабые ограничения на близость между функциями, чем норма C. Функции f(x) и g(x) могут быть близки по норме L 2, но далеки по норме C.

9 Гильбертовы пространства В линейном комплексном пространстве H вводится комплекснозначная функция двух переменных, называемая скалярным произведением, со свойствами: Скалярное произведение позволяет ввести норму

10 Ортогональность в гильбертовом пространстве Два вектора называются ортогональными, если их скалярное произведение равно нулю. Полная система взаимно ортогональных векторов единичной длины образует базис в гильбертовом пространстве: Совокупность векторов, ортогональных заданному, образуют гиперплоскость: В L 2 можно ввести скалярное произведение по правилу:

11 ЧИСЛЕННОЕ РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ Рассматривается одна из самых важных задач линейной алгебры решение систем линейных алгебраических уравнений (СЛАУ), в которых число уравнений рав­но числу неизвестных:

12 или в сокращенной записи: Коэффициентыпри неизвестных образуют матрицу системы

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

14 ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ Формулы Крамера Прямыми называются методы, которые позволяют получить точное решение невырожденной системы за конечное число операций. Формулы Крамера представляют компоненты решения системы (1) в виде отношения двух определителей: где

15 Здесь матрицаполучается из матрицы заменой ее j-го столбца столбцом правых частей системы С теоретической точки зрения формулы Крамера дают исчерпывающее решение проблемы. Чтобы найти решение системы, нужно подсчитать определитель. Это можно сделать за конечное число арифметических операций

16 Однако с точки зрения практики большое значение имеет фактическое число необходимых операций. Здесь нас и поджидает главная трудность. Определитель n-го порядка – это n! слагаемых, каждое из которых является произведением n чисел. Таким образом, для его вычисления нужно выполнить (n-1)n! умножений и n! сложений, т.е. всего n*n! арифметических операций. Оценим это число. При n>>1 число n! можно подсчитать с помощью асимптотической формулы Стирлинга: Даже при небольшом значении n=20 эта формула дает астрономическое число операций

17 Компьютеру, производительность которого составляет m операций/с, для вычисления определителя 20-го порядка понадобится (5*10^19)/m секунд. В частности, при операций/сек получим 5*10^9 сек = 170 лет Даже увеличение производительности компьютера на два, три порядка не спасает положения. Такие результаты получены при n=20, в то время как в современных прикладных задачах приходится решать системы с n=10^6 и более уравнений. Из проведенного анализа ясно, что рассчитывать решение СЛАУ по формулам Крамера с вычислением определителей «в лоб» невозможно, т.е. практическая ценность этих формул невелика.

18 Метод Гаусса Блестящий конструктивный выход из критической ситуации, описанной выше, дает метод Гаусса. Этот метод удобно условно разделить на два этапа. На первом этапе (прямой ход) система приводится к треугольному виду. Затем на втором этапе (обратный ход) осуществляется последовательное отыскание неизвестных из этой треугольной системы. Не ограничивая общности, будем считать, что коэффициент который называют ведущим элементом отличен от нуля В обратном случае поменяем местами уравнения с номерами 1 и i, при котором

19 Разделим все члены первого уравнения на и обозначим новые значения коэффициентов этого уравнения череза правую часть через Вычтем из каждого i-го уравнения системы (i=2,3,…,n) преобразованное первое уравнение, умноженное на Проделав это, мы исключим неизвестное из всех уравнений, кроме первого.

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

21 Естественно выделить «укороченную» систему, содержащую (n-1) уравнение: Продолжая далее процесс исключения, после (n-1)-го шага редуцируем исходную систему к виду

22 или в матричной форме Здесь C является верхней треугольной матрицей с единицами на главной диагонали: Построение указанной системы завершает прямой ход метода Гаусса.

23 Обратный ход состоит в последовательном определении неизвестных в обратном порядке: Подсчитаем число арифметических операций, которое требуется выполнить при решении СЛАУ по методу Гаусса.

24 - Количество шагов при реализации метода Гаусса - Количество шагов при реализации метода Крамера Оно не идет ни в какое сравнение с числом, которое требуют формулы Крамера при прямом вычислении определителей. Описанная выше процедура решения системы (1) методом Гаусса может оказаться неустойчивой по отношению к случайным ошибкам, которые неизбежны при компьютерных расчетах в результате округления чисел из- за конечной длины машинного слова.

25 Если матрица С оказалась такой, что все ее элементы удовлетворяют условию то роль ошибок округления в процессе вычислений то роль ошибок округления в процессе вычислений будет нивелироваться. Для того, чтобы добиться выполнения этого неравенства, процедуру выделения наибольшего по модулю элемента в очередной строке и превращения его в ведущий элемент нужно повторять во время каждого шага прямого хода метода Гаусса.

26 Метод прогонки При решении многих задач приходится иметь дело с системами линейных уравнений вида Дополнительные соотношения часто называют краевыми условиями для системы с дополнительными соотношениями

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

28 - Прямой ход прогонки Здесь величиныполучившие название прогоночных коэффициентов, подлежат определению исходя из условий задачи. Для реализации описанной программы выразим через

29 и подставимивыраженные через в исходные уравнения. В результате получим Последние соотношения будут заведомо выполняться, и притом независимо от решения, если потребовать, чтобы при имели место равенства

30 -Обратный ход прогонки Отсюда следуют рекуррентные соотношения для прогоночных коэффициентов: Граничное условие на левом конце интервала и соотношение непротиворечивы, если положить чем и завершаем этап вычисления прогоночных коэффициентов

31 Далее, согласно граничному условию на правом конце интервала, Отсюда можно найти остальные неизвестные в процессе обратной прогонки. С увеличением размеров системы число арифметических операций будет расти пропорционально n. Таким образом, метод прогонки в пределах сферы своего возможного применения является существенно более экономичным, чем метод Гаусса. К этому следует добавить особую простоту его программной реализации на компьютере.

32 Во многих прикладных задачах, которые приводят к СЛАУ с трехдиагональной матрицей, ее коэффициенты удовлетворяют неравенствам которые выражают свойство диагонального преобладания. Это неравенство приводит к соотношению что делает прогонку устойчивой.

33 ОБУСЛОВЛЕННОСТЬ СЛАУ Серьезным препятствием при решении систем линейных алгебраических уравнений может оказаться возможность заметного отклонения приближенного решения от точного из-за незначительных возмущений правых частей уравнений, которые неизбежно возникают в приближенных вычислениях. Причиной такого нежелательного эффекта часто оказывается так называемая плохая обусловленность матрицы системы линейных уравнений.

34 Рассмотрим линейное вещественное евклидово пространство, элементами которого являются вектора в виде упорядоченной системы чисел В пространстве определены скалярное произведение и евклидова норма Норма матрицы

35 удовлетворяющая трем аксиомам нормы: тогда и только тогда, когда (неравенство треугольника). Для скалярного произведения справедливо неравенство Коши-Буняковского

36 Рассмотрим квадратную матрицу A размером Она определяет линейное преобразование или Введем величину которую принято называть нормой матрицы A

37 Записывая ненулевой вектор в виде где - вектор единичной длины получаем эквивалентное представление для нормы Отсюда следует, что в конечномерном пространстве норма матрицы ограничена Наконец, из определения нормы следует, что

38 Корректность решения СЛАУ Следуя Адамару, будем называть задачу корректной, если выполняются три условия: 1) решение задачи существует 2) решение задачи единственное; 3) решение задачи непрерывно зависит от входных данных. Обсудим с точки зрения этого определения задачу решения СЛАУ с неравным нулю определителем считая матрицу A фиксированной и рассматривая в качестве входных данных вектор правых частей системы.

39 Условие Гарантирует существование у матрицы A обратной матрицы через которую решение системы можно записать в виде Пусть теперь правая часть подверглась возмущению Тогда возмущение решения можно записать в виде

40 Отсюда получаем Это неравенство доказывает непрерывную зависимость возмущения решения от возмущения правой части : при Это означает, что решение СЛАУ с неравным нулю определителем - корректная математическая задача: для нее выполняются все три требования корректности Адамара.

41 Число обусловленности матрицы Исходное уравнение позволяет написать неравенство Числоназывается числом обусловленности матрицы A. Оно позволяет оценить относительную погрешность решения через относительную погрешность возмущения правой части. Матрицы с большим числом обусловленности и соответствующие им СЛАУ называют плохо обусловленными.

42 А = А*, Число обусловленности матрицы A может быть рассчитано как Число обусловленности может быть выражено через собственные числа матрицы. Пусть Тогда справедливо неравенство Для симметричных матриц это неравенство переходит в равенство

43 ИТЕРАЦИОННЫЕ МЕТОДЫ Мы видели, что процедура решения СЛАУ с плохо обусловленной матрицей А может приводить к существенным отклонениям получаемого ответа от точного решения при незначительных возмущениях правой части. Этого недостатка лишены итерационные методы реше­ния СЛАУ. При их применении ответ получается в процессе построения последовательных приближений (итераций).

44 При обсуждении итерационных методов решения СЛАУ ограничимся линейными одношаговыми алгоритмами, которые обычно записывают в стандартной канонической форме: Итерационный процесс может быть использован для решения СЛАУ только при условии сходимости. Рассмотрим итерационный процесс при котором когда матрица В и итерационный параметр не зависят от индекса к. (*)(*)

45 Теорема Самарского. Пусть А самосопряженная положительно определенная матрица, и Тогда при любом выборе нулевого приближения итерационный процесс, который определяется рекуррентной формулой (* ) сходится к решению исходной системы при условии Достаточные условия сходимости такого процесса дает следующая теорема.

46 Метод простой итерации Такое название получил метод, при котором в качестве матрицы В выбирается единичная матрица: В =I, а итерационный параметр предполагается независящим от номера итерации к.

47 Для того чтобы метод простой итерации сходился к решению исходной системы при любом выборе начального приближения, необходимо и достаточно, чтобы все собственные значения оператора перехода S были по модулю меньше единицы

48 Неявные итерационные методы Метод Зейделя Рассмотрим произвольную квадратную матрицу A и разложим ее в сумму трех матриц где D диагональная часть матрицы А, которая содержит элементы, стоящие на главной диагонали:

49 - нижняя треугольная матрица: - верхняя треугольная матрица: В классическом методе Зейделя, записанном в канони­ ческой форме, полагают

50 Перейдем от векторной формы записи рекуррентной формулы к построчной: Уравнения позволяют последовательно рассчитать компоненты вектора (к + 1)-й итерации подобно тому, как это делалось во время обратного хода в методе Гаусса:

51 Алгоритм в методе Зейделя прост и удобен для вычислений. Он не требует никаких действий с матрицей А. Достаточные условия сходимости метода Зейделя определяется теоремой Самарского. Т.е. метод сходится, в случае, когда матрица А является самосопряженной и положительно определенной. Кроме того, метод Зейделя сходится для любой системы, в которой матрица А обладает свойством диагонального преобладания.

52 Метод верхней релаксации Модифицируем метод Зейделя. С этой целью введем параметр и запишем рекуррентное соотношение в виде В явном виде

53 Достаточное условие для сходимости итерационной последовательности метода верхней релаксации имеет вид Можно поставить вопрос об оптимальном выборе параметра, при котором метод сходится быстрее всего. Теоретическое исследование, показывает, что такое значение существует и может быть выражено через наибольшее и наименьшее собственные значения матрицы А. Однако на практике его приходится подбирать экспериментально методом проб и ошибок.

54 ЧИСЛЕННОЕ РЕШЕНИЕ УРАВНЕНИЙ Метод половинного деления

55 Метод итераций принцип сжимающих отображений

56 Метод касательных (метод Ньютона)

57

58 ПРИБЛИЖЕНИЕ ФУНКЦИЙ ИНТЕРПОЛИРОВАНИЕ

59

60 Интерполирование полиномами Определитель Ван-дер-Монда

61 Построение интерполяционного полинома в форме Лагранжа

62 Сравнение графиков функции (сплошная линия) и интерполяционного полинома(штриховая линия)

63 Интерполяционный полином в форме Ньютона

64

65 График функции

66 Интерполяционный полином Эрмита - максимальное значение модуля функции

67 Интерполирование кубическими сплайнами

68

69

70 Сходимость и точность интерполирования сплайнами Пусть f(x) непрерывна на сегменте [а, b], тогда

71 Метод наименьших квадратов Метод наименьших квадратов был предложен Гауссом и Лежандром в конце XVIII начале XIX века в связи с проблемой обработки экспериментальных данных. В этом случае задача построения функции непрерывного аргумента по дискретной информации характеризуется двумя особен­ностями: 1. Число точек, в которых проводятся измерения, обычно бывает достаточно большим. 2. Значения функции в точках сетки определяются приближенно в связи с неизбежными ошибками измерения

72 В методе наименьших квадратов аппроксимирующая функция у(х) ищется в виде суммы, содержащей сравнительно небольшое число слагаемых Найти такой набор коэффициентов, при которых суммарная квадратичная погрешность J оказывается минимальной

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

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

75 ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ Универсальные алгоритмы вычисления определенных интегралов дают формулы численного интегрирования или, как их обычно называют, квадратурные формулы (буквально - формулы вычисления площадей). Квадратурные формулы имеют вид Узлы и веса подбираются таким образом, чтобы выполнялось предельное равенство

76 Квадратурная формула прямоугольников Возьмем произвольное целое число n и разобьем отрезок [а, b], по которому ведется интегрирование, на n равных отрезков длиной h = (b-a)/n Средние точки этих отрезков:

77 Построим с помощью проведенного разбиения интегральную сумму, в которой значения функции f(x) для каждого отрез­ка вычисляются в его средней точке Величинапредставляет собой сумму площадей прямоугольников с одинаковыми основаниями h = (b - a)/n и высотами Она аппроксимирует площадь криволинейной трапеции, соответствующей исходному интегралу

78 Геометрическая интерпретация формулы прямоугольников

79 Квадратурная формула трапеций Идея вывода квадратурных формул трапеций и Симпсона иная. Она заключается в том, чтобы сопоставить подынтегральной функции f(x) близкую ей функцию, которую можно проинтегрировать, и приближенно заменить искомый интеграл I интегралом от этой функции. Для формулы трапеций в качестве аппроксимирующей функции берется кусочно-линейная функция. На каждом из частичных сегментов она задается формулой

80 Геометрическая интерпретация формулы трапеций Этот результат имеет простой геометрический смысл: фигура, ограниченная снизу отрезком оси х, сверху отрезком прямой, с боков вертикальными прямыми, представляет собой трапецию

81 Квадратурная формула Симпсона Теперь для аппроксимации функции f(x) используется не кусочно-линейное, а кусочно-квадратичное интерполирование.

82 Проинтегрировав полином второй степени по отрезку получим Интеграл от функции равен сумме интегралов no всему отрезку [a, b]

83 Сходимость и точность квадратурных формул прямоугольников, трапеций и Симпсона После того как мы установили, что величины являются интегральными суммами, проблема сходимости рассмотренных методов численного интегрирования решается элементарно. Их сходимость имеет место для любой интегрируемой функции:

84 Асимптотические представления остаточных членов квадратурных формул прямоугольников, трапеций и Симпсона имеют вид Точность квадратурных формул возрастает при увеличении n где- мажоранты производных функции f(х):

85 Апостериорные оценки погрешности при численном интегрировании В латинском языке существуют два термина – антонима: априори (a priori) и апостериори (a posteriori). Первый означает изначально, независимо от опыта, второй - на основании опыта. Оба они часто используются в вычислительной математике, подразделяя информацию на ту, которая известна до начала вычислений, и ту, которая получается в процессе вычислений.

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