- •1. Структура погрешности в численном анализе.
- •2.3.Округление.
- •4. Понятие близости в метрическом пространстве.
- •Примеры классов функций и соответствующих нормированных пространств.
- •Задача наилучшего приближения в нормированном пространстве.
- •Задача приближения полиномами.
- •Интерполяция.
- •Конечные разности.
- •7.Интерполяционный многочлен Ньютона.
- •6.Запись интерполяционного многочлена для равноотстоящих узлов.
- •9. Среднеквадратичное приближение функции.
- •10. Классические ортогональные многочлены и их применение в задачах приближения функций.
- •11.Полиномы Лежандра. Построение и использование в задачах ср.Кв.Приближения.
- •С другой стороны
- •12. Некоторые общие свойства ортогональных полиномов.
- •13. Многочлены Чебышева, их свойства .
- •14.Первые применения многочленов Чебышева к задаче интерполяции.
- •15. Квадратурные формулы на основе интерполяций.
- •Формулы Ньютона-Котеса.
- •18 Квадратурные формулы Гаусса-Кристоффеля.
- •19. Запишем квадратурную формулу для произвольного, но фиксированного распределения узлов :
- •21 .Принцип сжатых отображений.
- •23 Метод Ньютона.
- •24.Численные методы линейной алгебры.
- •Стационарные итерационные процедуры. Теоремы о сходимости.
- •41.Постановка краевой задачи для оду второго порядка:
- •47.Аппроксимация, устойчивость и сходимость разностных схем.
23 Метод Ньютона.
Пусть снова задано уравнение f(x)=0. Запишем его в виде , где и . Пусть хк – некоторое приближение к корню х*. Для ускорения сходимости итераций желательно, чтобы был как можно меньше. Положим , то есть
Отсюда находим, что . Подставляя в исходное уравнение, получаем рекуррентную формулу: . Это и есть итерационная процедура Ньютона.
24.Численные методы линейной алгебры.
К численным методам линейной алгебры относятся: численные методы решения систем алгебраических уравнений (ЛАУ), обращение матриц, вычисление определителя матрицы, вычисление собственных значений и собственных векторов матриц. Численные методы решения систем ЛАУ можно разбить на две группы: прямые методы (метод исключения Гаусса и его модификации) и так называемые итерационные методы. Метод Гаусса подробно рассматривается в курсе линейной алгебры, где, в частности показывается, что число арифметических действий, затрачиваемых на приведение системы к треугольному виду пропорционально n3. При вычислении определителя методом Гаусса затрачивается арифметических действий. Несмотря на очевидные преимущества прямых методов (конечность действий), их применение не всегда возможно. Если матрица A линейной системы плохо обусловлена, то вследствие неизбежных ошибок округления на ЭВМ, полученное приближенное решение системы может оказаться сколь угодно далеким от точного решения. Чтобы разобраться в этом вопросе, нам понадобится понятие нормы матрицы, спектра матрицы и обсудить некоторые дополнительные свойства матриц, связанные с этими понятиями.
25.
Нормы матриц. Спектральные свойства матриц. Пусть , Обозначим Mn - множество квадратных матриц . Пусть каждой матрице поставлено в соответствие число .Это число называется нормой матрицы A, если выполняются следующие аксиомы:
1. . 2. . 3. (неравенство треугольника).
4. (кольцевое свойство).
Определение.Норма называется мультипликативной, если выполняются все четыре аксиомы, и аддитивной, если выполняются первые три аксиомы.
Следствие. Если норма матрицы A – мультипликативна, то согласно свойству 4: . Пусть . Определим норму матрицы следующим образом:
. (1) Таким образом, определенная норма матрицы называется подчиненной векторной норме .
Определение. Если матричная норма удовлетворяет условию , (2) то такая норма называется согласованной с нормой вектора.
Следствие 1.Любая подчиненная норма является также и согласованной (обратное вообще говоря, неверно).
Действительно, из (1) в силу определения супремума: , Тот факт, что обратное неверно, подтверждается конкретными примерами матричных норм, с которыми мы познакомимся далее.
Следствие 2. Пусть A=E и норма матрицы – подчиненная векторной норме. Тогда, поскольку Ex=x, то и из (1) немедленно следует что Полученное условие можно считать необходимым условием подчиненной нормы. Определим некоторые наиболее употребительные на практике матричные нормы.
- евклидова норма (норма Фробениуса: norm(a, ‘fro’)- в MATLAB),
- “столбцовая” норма (norm(a, 1)),
- “строчная” норма (norm(a, inf)),
- “спектральная” норма (norm(a)=norm(a, 2)), где - так называемые сингулярные числа матрицы А.
Замечание. Все приведенные выше нормы матриц согласованы с соответствующей нормой вектора. Спектральная норма является к тому же и подчиненной евклидовой норме вектора. Кроме того, среди всех возможных норм, согласованных с евклидовой нормой вектора, спектральная норма принимает минимальное значение.
Определение 1. Число (вообще говоря, комплексное) называется собственным значением матрицы А, соответствующим собственному вектору x, если выполняется условие: . (3)
Определение 2. Множество всех собственных чисел матрицы А , записанных с учетом их кратности, называется спектром матрицы А и обозначается S(A).
Определение 3. Спектральным радиусом квадратной матрицы А называется максимальный из модулей ее собственных значений. Заметим, что система (3) эквивалентна следующей однородной системе уравнений: . (4)
Как известно из курса линейной алгебры, система (4) имеет нетривиальные решения тогда и только тогда, когда . (5) Уравнение (5)- алгебраическое уравнение n-ой степени относительно .
Все его корни – собственные числа матрицы А. Имеет место следующая
Теорема 1. Для любой квадратной матрицы и любой согласованной матричной нормы имеет место неравенство:
Пусть - произвольное собственное значение матрицы A, и - соответствующий собственный вектор . Оценим по норме Определение 4. Сингулярным числом матрицы А называется собственное значение матрицы .
Определение 5. Матрица А называется положительно (неотрицательно) определенной (пишут: или ), если соответствующая квадратичная форма .
Простейшие следствия из определений.
Следствие 1. Критерий Сильвестра: все ведущие угловые миноры матрицы А положительны.
Следствие 2. , причем . следует из критерия Сильвестра
Следствие 3. все собственные значения . Пусть - собственное значение, соответствующее собственному вектору x.
По условию результат.
Следствие 4. Пусть А – вещественная матрица матрица Имеем: {по свойству скалярного произведения}
Следствие 5. Сингулярные числа вещественной матрицы А – неотрицательны Следует из С3 и С4.
Следствие 6. Пусть А – вещественная матрица .
Имеем:
Следствие 7. Если А – невырожденная матрица собственные значения матриц А и A-1 взаимообратны.
Пусть результат.
Обусловленность матриц и систем уравнений. Пусть дана система ЛАУ с невырожденной матрицей А : Ax=b, (6) и пусть вектор правой части b вычисляется с ошибкой . Заменим правую часть “возмущенным” значением , тогда решение приобретет ошибку и система примет вид:
. (7) Оценим относительную ошибку решения в зависимости от относительной
величины возмущения правой части . Из (6) и (7) следует: или
{согласованность матриц} (8) С другой стороны, из (6) следует подставим в (8) .
(9)
Определение 6. Число называется числом обусловленности матрицы А. Таким образом, из (9) следует, что максимальная относительная ошибка решения пропорциональна числу обусловленности матрицы А: .
Если (система уравнений плохо обусловлена), то небольшие погрешности вычисления правой части (небольшие “возмущения”) могут приводить к весьма большим отклонениям от точного решения.
Заметим, что это явление не связано с явлением неустойчивости (т.е. накоплением ошибок при вычислениях), а является следствием специфического свойства матрицы А и наблюдается даже в том случае, когда все вычисления делаются абсолютно точно, а возмущение правой части вызвано неточностями начальных данных при формировании системы. На семинаре и лабораторной работе будут рассмотрены примеры плохо обусловленных систем.
26
Итерационные методы решения систем ЛАУ.Рассмотрим вначале систему ЛАУ вида x=Tx+d, , T- матрица (10) Назовем эту систему системой “второго рода”, в отличии от вида системы (1) – системы “первого рода”. Систему второго рода (10) естественно пытаться решать итерационным методом
, k=0,1,….. (11) В этом методе используются лишь операции сложения и умножения, и не используется операция деления – наиболее опасная для накопления ошибок. Очевидно, что оператор Т - линейный и отображает Rn в себя. Тогда согласно У2 из лекции 10, если для какой-либо из матричных норм выполняются условия теоремы 1 существует единственная неподвижная точка x* оператора Т, удовлетворяющая системе x*=Tx*+d, (12) причем процедура (11) сходится к точке x* со скоростью геометрической прогрессии. Действительно, из (11) и (12) xk+1-x*=T(xk-x*)={продолжая рекурсию}=…=Tk(x0-x*) Оценивая по норме, получаем: {согласованность+мультипликативность матричной нормы} при результат: сходимость с линейной скоростью.
27