- •1. Структура погрешности в численном анализе.
- •2.3.Округление.
- •4. Понятие близости в метрическом пространстве.
- •Примеры классов функций и соответствующих нормированных пространств.
- •Задача наилучшего приближения в нормированном пространстве.
- •Задача приближения полиномами.
- •Интерполяция.
- •Конечные разности.
- •7.Интерполяционный многочлен Ньютона.
- •6.Запись интерполяционного многочлена для равноотстоящих узлов.
- •9. Среднеквадратичное приближение функции.
- •10. Классические ортогональные многочлены и их применение в задачах приближения функций.
- •11.Полиномы Лежандра. Построение и использование в задачах ср.Кв.Приближения.
- •С другой стороны
- •12. Некоторые общие свойства ортогональных полиномов.
- •13. Многочлены Чебышева, их свойства .
- •14.Первые применения многочленов Чебышева к задаче интерполяции.
- •15. Квадратурные формулы на основе интерполяций.
- •Формулы Ньютона-Котеса.
- •18 Квадратурные формулы Гаусса-Кристоффеля.
- •19. Запишем квадратурную формулу для произвольного, но фиксированного распределения узлов :
- •21 .Принцип сжатых отображений.
- •23 Метод Ньютона.
- •24.Численные методы линейной алгебры.
- •27 Стационарные итерационные процедуры. Теоремы о сходимости.
- •33-34Численное дифференцирование.
- •35-36.Численные методы решения задачи Коши.
- •37-39.Методы Рунге-Кутта.
- •41.Постановка краевой задачи для оду второго порядка:
- •47.Аппроксимация, устойчивость и сходимость разностных схем.
27 Стационарные итерационные процедуры. Теоремы о сходимости.
Пусть задана система ЛАУ общего вида (первого рода): Ax=b; x,b Rn, . (1) Требуется привести данную систему к виду x=Tx+d (2) с матрицей (оператором) Т, удовлетворяющей условию в какой либо матричной норме. Рассмотрим простейший прием такого преобразования.x=x-H(Ax-b), (3)
где Н- некоторая невырожденная матрица. Из (3) следует, что x=Tx+d, где (4) T=E-HA, d=Hb.
Некоторые определения.
Итерационная процедура, основанная на представлении (3) xk=xk-1-H(Axk-1-b) (5) называется линейной стационарной итерационной процедурой; при этом матрица Т в представлении (4) называется матрицей перехода, а матрица Н – матрицей расщепления.
Более общая линейная нестационарная итерационная процедура записывается в виде:
xk= xk-1-Hk(A xk-1-b), где Hk – матрица расщепления k-го шага. Соответственно матрица перехода Tk=E-HkA – называется матрицей перехода k-го шага. Ниже будут более подробно рассмотрены стационарные итерационные процедуры. Связь условия сходимости линейного стационарного процесса со свойствами спектра матрицы Т устанавливает следующая теорема.
Теорема 1. Пусть система (4) имеет единственное решение стационарная процедура
(6) сходится к решению системы (4) при тогда и только тогда, когда все собственные значения матрицыТ по модулю меньше 1.
Достаточность. Заметим, что условие теоремы равносильно условию . Пусть x* - точное (и единственное) решение системы (4). Запишем следующую систему:
Вычитая из первого уравнения второе, получаем: xk- x* = T(xk-1- x*).
Обозначим - ошибкаk-ого шага. Тогда
(7)
является итерационной процедурой для операторного уравнения r=Tr, достаточным условием сходимости которой, согласно принципу сжатых отображений, является условие .Заметим, что матрица Т- вещественная. Рассмотрим в качестве нормы матрицы Т- спектральную норму:по условию теоремыи достаточность доказана.
Необходимость. От противного. Пусть одно из собственных значений матрицы Т, например, и пустьy - соответствующий собственный вектор: . Выберем начальное приближение в виде, гдеС - некоторая константа. Запустим итерационную процедуру:
не может быть нарушено условие .
28.
Рассмотрим простейший прием такого преобразования. x=x-H(Ax-b), (3) где Н- некоторая невырожденная матрица. Из (3) следует, что x=Tx+d, где (4) T=E-HA, d=Hb. Итерационная процедура, основанная на представлении (3) xk=xk-1-H(Axk-1-b) (5) называется линейной стационарной итерационной процедурой; при этом матрица Т в представлении (4) называется матрицей перехода, а матрица Н – матрицей расщепления.
Рассмотрим некоторые частные случаи стационарных процедур, зависящих от выбора матрицы Н. Пусть матрица перехода в этом случае имеет вид:T=E-A. Получаем так называемый метод простых итераций, или метод Ричардсона. Выясним условия сходимости метода Ричардсона. Пусть собственное значение матрицыТ, собственное значение матрицы А. является корнем характеристического уравнения , корнем уравнения или: , откуда следует, что. Согласно теореме 1, условие сходимости: Последнее условие, например, выполняется, если
и .
Теорема 1.Пусть система (4) имеет единственное решение стационарная процедура
сходится к решению системы
x=Tx+d, где T=E-HA, d=Hb. при тогда и только тогда, когда все собственные значения матрицыТ по модулю меньше 1.
29.
Рассмотрим простейший прием такого преобразования. x=x-H(Ax-b), (3) где Н- некоторая невырожденная матрица. Из (3) следует, что x=Tx+d, где (4) T=E-HA, d=Hb. Итерационная процедура, основанная на представлении (3) xk=xk-1-H(Axk-1-b)(5) называется линейной стационарной итерационной процедурой; при этом матрица Т в представлении (4) называется матрицей перехода, а матрица Н – матрицей расщепления.
Пусть , гденекоторый параметр сходимости, с помощью которого можно оптимизировать процедуру Ричардсона. Матрица перехода в этом случае имеет вид:.
Теорема 2.Пусть и ,является оптимальным значением параметра сходимостиобобщенной итерационной процедуры Ричардсона:.
Т.к. ,то все собственное значения матрицы А m, M>0 и .Выберем в качестве матричной нормы - спектральную норму. По определению,, поэтому, чем меньше спектральный радиус, тем быстрее сходится итерационная процедура в соответствии с принципом сжатых отображений. Пустьсобственное значение матрицыкорень уравнения
, - корень уравнения:
Из сравнения двух характеристических уравнений Таким образом, имеем.
Так как функция кусочно линейна по, то достигается на концах отрезка
|
Найдем такое , для которого. (8)
Легко проверить, что при выполняются следующее условие:- обозначим.Покажем, что полученное значениекак раз и является оптимальным в смысле критерия (8).
Пусть, например, .
Из последних равенств видно, что при любом знаке один из модулей будет, т.е., что и требовалось доказать.
30-32
Релаксационные методы.
Пусть задана система ЛАУ общего вида (первого рода): Ax=b; x,b Rn, . (1) Требуется привести данную систему к виду x=Tx+d (2) с матрицей (оператором) Т, удовлетворяющей условию в какой либо матричной норме. Рассмотрим простейший прием такого преобразования.x=x-H(Ax-b), (3)
где Н- некоторая невырожденная матрица. Из (3) следует, что x=Tx+d, где (4) T=E-HA, d=Hb.
Итерационная процедура, основанная на представлении (3) xk=xk-1-H(Axk-1-b) (5) называется линейной стационарной итерационной процедурой; при этом матрица Т в представлении (4) называется матрицей перехода, а матрица Н – матрицей расщепления.
В данном классе методов приведение системы (1) к виду (4) осуществляется с помощью расщепления матрицы А, т.е. ее представления в виде: A=D-CL-CU ,(9) где
D=- диагональная матрица,CL=-строго нижняя (левая) треугольная матрица, CU=-строго верхняя (правая) треугольная матрица. Подставляя представление (9) в систему (1) Ax=b Dx=(CL+CU)x+b x=D-1(CL+CU)x+ D-1b x=Tx+d, где T= D-1(CL+CU)= D-1(D-A)=E- D-1A, d= D-1b, H= D-1 - матрица расщепления. Получаемый при этом итерационный метод называется методом Якоби. Необходимое условие сходимости: (иначе не существуетD-1). Достаточные условия сходимости в соответствии с теоремой 1: . Или более простое условие: пусть матрицаА - вещественная, причем (такая матрицаА называется матрицей со строгим диагональным преобладанием).
Метод Якоби может быть оптимизирован следующим образом. Снова воспользуемся разложением (9) и запишем систему в виде: x=D-1CLx+ D-1CUx+d. (10) Нетрудно убедиться, что при покомпонентной записи (10) , где
вектор gLx содержит только первые (i-1) компонент вектора х , а вектор gUx - содержит компоненты, начиная с (xi+1) . (11) Процедура (11) носит название итерационный метод Гаусса-Зейделя Условия сходимости - те же, что и для метода Якоби, но при этом получается дополнительное ускорение процедуры. Более эффективное ускорение сходимости метода Зейделя может быть достигнуто с помощью ускоряющего множителя (как в обобщенном методе Ричардсона). Получающийся при этом алгоритм носит название “метод последовательной верхней релаксации” и реализуется в два этапа:
(12) где -релаксационный параметр. Если , то приитерационная процедура сходится.
Теорема 1. Пусть система (4) имеет единственное решение стационарная процедура
(6) сходится к решению системы (4) при тогда и только тогда, когда все собственные значения матрицыТ по модулю меньше 1.