Численные методы
.pdf
Метод Зейделя можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (k+1)-го приближения к неизвестному при I > 1 используют
уже найденные (k+1)-е приближения к неизвестным |
… |
а не k-е приближения как методе |
Якоби. |
|
|
На (k+1) –й итерации компоненты приближения |
вычисляются по формулам |
|
Введем нижнюю и верхнюю треугольные матрицы
Тогда расчетные формулы метода примут компактный вид:
Заметим, что |
и поэтому решение исходной системы удовлетворяет равенству |
Достаточные условия сходимости |
|
|
|
где |
одна из норм |
Тогда при любом выборе начального приближения |
|
метод Зейделя сходится со скоростью геометрической прогрессии,знаменатель которой |
|||
Доказательство: Пусть выполнено условие |
Тогда при любом выборе начального |
||
приближения метода Зейделя сходится и верна оценка погрешности
Где q= |
|
|
|
Вычисляя нормы левой и правой частей этого равенства и используя свойства норм, получим
Следовательно
Имеем |
поэтому |
при n |
. |
|
Апостериорная оценка погрешности. |
|
|||
Если выполнено условие |
то для метода Зейделя справедлива апостериорная оценка |
|||
погрешности |
|
|
|
|
|
|
|
|
|
Предположим k = n-1 и запишем в следующем виде
Тогда
Полученное неравенство позволяет сформулировать критерий окончания итерационного
процесса. Если требуется найти решение с точностью |
то итерации метода Зейделя следует |
|||||
вести до выполнения неравенства |
|
|
|
|
||
|
|
|
||||
Или |
; |
|
|
|
|
|
|
|
|
|
|
||
|
Геометрическая интерпретация вывода |
|||||
Суть метода релаксации состоит в следующем. После вычисления i-й компоненты (k+1)-го приближения по формуле метода Зейделя производят дополнительно смещение этой компоненты на величину где – параметр релаксации. И вычисляется по формуле
17.Приближение функций. Постановка задачи. Глобальная интерполяция многочленами. Постановка задачи. Существование и единственность интерполяционного многочлена.
Возникающие проблемы нередко удается решить следующим образом. Функцию f(x) приближенно заменяют другой функцией g(x) вычисляемые значения которой и принимают за приближенные значения функции f. Конечно такая замена оправдана лишь тогда ,когда значения g(x) вычисляются быстро и надежно, а погрешность приближения f(x)-g(x) достаточно мала. Обсудим некоторые вопросы ,с которыми в каждом конкретном случае приходится сталкиваться при выборе постановки задачи приближения и метода ее решения
1)Необходимо решить какую информацию о функции f можно использовать как входные данные для вычисления приближения g.
2)Полезно иметь некоторую дополнительную априорную информацию об аппроксимируемой функции. Часто она бывает качественного характера.
3)Знание свойств функции f позволяет сознано выбирать класс G аппроксимирующей
функции. Часто такой класс представляет собой параметрическое семейство функций вида y=g(x,a)= и выбор конкретной аппроксимирующей функции g осуществляется с помощью выбора параметров
Широко используются классы функций вида
Являющихся линейными комбинациями фиксированного набора некоторых базисных
функций |
… |
Функцию |
часто называют обобщенным многочленом по |
||
системе функций |
|
… |
а число m – его степенью. |
|
|
Если в качестве базисных функций берутся степенные функции |
то возникает задача |
||||
приближения алгебраическими многочленами. |
|
||||
Отметим что методы приближения функций алгебраическими многочленами играют важную роль в численном анализе и наиболее глубоко разработаны.Одна из причин этого состоит в том что многочлены. Легко вычисляются без труда диффиринцируются и интегрируются.
Тригонометрические многочлены
Часто используемые для аппроксимации периодических на отрезке [0,1] функций также могут
быть записаны в виде |
|
|
) если в качестве базисных функций |
|
выбрать |
, |
, |
, |
, |
использовав формулу exp |
|
, |
|
|
4)Необходим критерий выбора в классе G конкретной аппроксимирующей функции g, являющейся в смысле этого критерия наилучшим приближениям к f.
Глобальная интерполяция
В случае глобальной интерполяции отыскивается единый полином на всем интервале [a, b], т.е. строится полином, который используется для интерполяции функции f(x) на всем интервале изменения аргумента x. Будем искать интерполирующую функцию в виде полинома (многочлена) m–ой степени Pm(x)=a0+a1x+a2x2+a3x3+…+am xm. Какова должна быть степень многочлена, чтобы удовлетворить всем условиям интерполяции? Допустим, что заданы две точки: (x0, f0) и (x1, f1), т.е. N=1. Через эти точки можно провести единственную прямую, т.е. интерполирующей функцией будет полином первой степени P1(x)=a0+a1x. Через три точки (N=2) можно провести параболуP2(x)=a0+a1x+a2x2 и т.д. Рассуждая таким способом, можно предположить, что искомый полином должен иметь степень N .
18. Интерполяционный многочлен Лагранжа. Интерполяционный многочлен Ньютона с конечными и разделенными разностями. Свойства разделенных разностей. Погрешность интерполяционных гладких функций (без доказательства)
Интерполяционный многочлен Лагранжа
Как не трудно видеть |
тавляет собой многочлен степени n удовлетворяющий условию |
Интерполяционный многочлен Ньютона c разделенными разностями
Интерполяционный многочлен Ньютона с конечными разностями
Свойства разделенных разностей |
|
1) Разделенная разность |
является симметричной функцией своих |
аргументов |
т.е. ее значения не меняется при любой их перестановке. |
2) Пусть функция f имеет на отрезке [a, b] содержащем точки x |
|
производную |
порядка k. Тогда справедливо равенство |
|
где некоторая точка |
|
расположенная на интервале [a, b].
3) В случае когда таблица значений аргумента имеет постоянный шаг h разделенная и
конечная разности связаны равенством о
Погрешность гладких функций
19. Метод наименьших квадратов. Вывод нормальной системы метода. Приближение алгебраическими многочленами.
Пусть для исходных |
(нумерацию лучше начинать с единицы) выбран вид |
|
эмпирической зависимости |
|
|
Параметры |
будем находить из условия минимума функции S( |
В этом |
состоит метод наименьших квадратов (МНК)
Известно, что в точке минимума все частные производные от S по
,
Рассмотрим применение МНК для частного случая, широко используемого на практике. В качестве эмпирической функции рассмотрим полином
Вычислим производные
Приравнивая эти выражения нулю и собирая коэффициенты при неизвестных 
, получим следующую систему линейных уравнений:
Данная система уравнений называется нормальной. Решая эту систему линейных уравнений,
получаем коэффициенты
В случае полинома первого порядка m=1, т.е. 
, система нормальных уравнений примет вид:
Прим m=2 имеем
Как правило, выбирают несколько эмпирических зависимостей. По МНК находят коэффициенты этих зависимостей и среди них находят наилучшую по минимальной сумме отклонений.
20.Численное интегрирование. Формула левых и правых и центральных прямоугольников. Геометрическая иллюстрация, элементарная и составная формулы, оценка погрешности (левых прямоугольников с доказательствами).
Метод прямоугольников — метод численного интегрирования функции одной переменной, заключающийся в замене подынтегральной функции на многочлен нулевой степени, то есть константу, на каждом элементарном отрезке. Если рассмотреть график подынтегральной функции, то метод будет заключаться в приближённом вычислении площади под графиком суммированием площадей конечного числа прямоугольников, ширина которых будет определяться расстоянием между соответствующими соседними узлами интегрирования, а высота — значением подынтегральной функции в этих узлах. Алгебраический порядок точности равен 0.
Элементарная формула
Формула центральных прямоугольников (составная) |
|
Формула Левых прямоугольников (составная) |
) |
Формула Правых прямоугольников (составная) |
) |
Оценка погрешности
Доказательство: Представим погрешность |
формулы прямоугольников в виде |
Используя формулу Тейлора
где
21.Численное интегрирование. Формула трапеции. Геометрическая иллюстрация, элементарная
исоставная формулы, оценка погрешности (с доказательством).
–Составная
–элементарная
Оценка погрешности
Доказательство: Для элементарной формулы трапеции верно равенство
Используя оценку погрешности линейной интерполяции, имеем
22. Численное интегрирование. Формула Симпсона. Идея вывода, элементарная и составная формулы, оценка погрешности (без доказательства).
Идея вывода
Если площадь элементарной криволинейной трапеции заменить площадью фигуры расположенной под параболой, проходящей через точки
То получим приближенное равенство |
. Здесь |
- интерполяционный многочлен |
||
второй степени с узлами |
|
|
. |
|
Интегрируя приходим к элементарной квадратурной формуле.
Элементарная формула Симпсона
Составная формула Симпсона
)
Оценка погрешности
23. Численное интегрирование. Правило Рунге апостериорная оценка погрешности. Уточнение по Рунге. Понятие о формулах Ньютона-Котеса.
Правило Рунге — правило оценки погрешности численных методов.
Основная идея состоит в вычислении приближения выбранным методом с шагом h, а затем с шагом h/2, и дальнейшем рассмотрении разностей погрешностей для этих двух вычислений
Уточнение по Рунге
Формулы Ньютона-Котэса
m=1 – Формула Трапеций
m=2 формула Симпсона
m=3 правило 3/8
m=4 Формула
Милна(Формула Боде)
m=5
Формула Вэддла m=6
Оценки погрешностей формул Ньютона-Котеса:
24. Численное дифференцирование. Левая, правая и центральная разностные производные. Геометрическая интерпретация. Оценка погрешности, порядок точности. Вторая разностная производная. Оценка погрешности. Порядок точности. Понятие о формулах интерполяционного типа.
-правая разностная производная
-левая разностная производная
центральная разностная производная
Оценка погрешности
Вторая разностная производная вторая разностная производная